# 大一計算機概論筆記

## **persudocode 概論：**
是什麼? ans: 草稿(寫下邏輯)
testplan:要測多少次，用什麼樣的資料去測
code converage:確認每行程式都被執行
data converage:各種範圍內的資料都可執行成功

### **Problem solving and Algorithm:**
概念：製作演算法的科學方法
先自己讀課本
#### binary search:
條件：排序後的陣列
概念：不斷的取區間內的中間值進行比對
ex: 0-100 中找23
1.找到50的地址，50比23大，區間改成0～50
2.找到25的地址，25比23大，區間改成0～25
3.找到12的地址，12比23小，區間改成12～25
4.找到18的地址，18比23小，區間改成18～25
5.找到21的地址，21比23小，區間改成21～25
6.找到23的地址
*複雜度為O(logn) 遠小於一個一個找的O(n)
#### bubble sort:

條件：擁有一個陣列
概念：不斷的把最大值交換到最後
ex:array={1,7,4,3,5}
1.array={1,4,3,5,7}
1.交換1，7失敗
2.交換7，4成功array={1,4,7,3,5}
3.交換7，3成功 array={1,4,3,7,5}
4.交換7，5成功 array={1,4,3,5,7}
2.array={1,3,4,5,7}
1.交換1，4失敗
2.交換3，4成功
3.交換4，5失敗
4因最後一位已經確定為最大值，因此不再交換
3.array={1,3,4,5,7}
1.交換1，3失敗
2.交換3，4失敗
3.最後兩位不執行
4.array={1,3,4,5,7}
1.交換1，3失敗
2.後三位不執行
5.結束
*複雜度為O(n^2)比一般的sort大，但是為理解sort的最好範例
*如果你沒注意到，當一直取較大的數時，最後得到的數會是比對範圍內的最大值

[氣泡排序範例點我](https://hackmd.io/@eRA5F9qrRx2xUqx5v3ZPRQ/ry0c5VGf1x)
#### selection sort:
條件：擁有一個陣列
概念：把最小的放到最前面
ex:array={3,2,5,1,4}
1.array={1,2,5,3,4}
2.array={1,2,5,3,4}
3.array={1,2,3,5,4}
4.array={1,2,3,4,5}
*因為第i點會將陣列中的前i項都sort好，因此第i+1點只找i+1到n的最小值
*複雜度為O(n^2次)，跟bubble sort 一樣都是基礎

[選擇排序點我](https://hackmd.io/@eRA5F9qrRx2xUqx5v3ZPRQ/ry8W5KmGJe)
#### bubble sort and selection sort 的比較：
1.一般 bubble 是找最大值，selection 是找最小值，但不一定要如此
2.一般 bubble 是由後往前排， selection 是由前往後排，但反著做也不是不能sort
3.bubble 是以不斷交換得出 最大/最小 值，而 selection 是以for迴圈跑一遍來得出 最大/最小 值並交換
4.二者的最大執行次數都是n*(n+1)/2次，也就是0.5n^2+0.5n，因為常數項太小(把n當成10^5以上)，所以可以忽視，時間複雜度為O(n^2)
*課本是在排序英文，與排序數字是一樣的，a<z, ab<az, az<za, 可以當成（26^幾位數）*ASCII+（26^［幾位數-1］）*ASCII...進行比對

## CH10
### 目錄：
1. OS
2. batch
3. timesharing
4. memory management
5. process management
6. CPU schedualing

### 1. OS:
1. 電腦的核心
2. 可以有很多個，但一次只能運行一個
3. 管控電腦資源（記憶體，輸入輸出等⋯⋯）
4. 存在的意義是讓不同程式"和平共享"資源
5. 一小部分存在ROM，其他存在磁碟
6. 電腦開機時啟動，這過程被稱為Booting

### 2. Batch:
早期為了使資源準備更快而出現
需要相同資源的工作會被分類到同一個batch
現代的batch與以往不同
bat檔 是用來寫系統指令

### 3. Timesharing:
原先time sharing系統包含一個mainframe, OS存在於那裡
所有連接的使用者傳送指令過去執行，在得到結果
造成彷彿每個使用者都有各自的電腦的現象

### 4. Memory management:
* 課本介紹了三種方式
#### A. Single continious:
記憶體一次只放一組程式進去
記憶體總共只有OS和一組程式

#### B. Partition:
* 把記憶體分成多組的空間，再把不同的程式放進不同的空間
* 有三種放法，first fit, best fit, worst fit
* first fit 是把程式放到第一個放得下的空間
* best fit 是把程式放到最小的、可以容納它的空間
* worst fit 是把程式放到最大的空間，看似是最糟糕的做法，但在動態的partition分配中，它是最好的選擇

#### C. Paged memory:
把記憶體分成大量相同大小的frame來裝程式的不同部分
透過一個表格把邏輯地址轉換成實體地址
page = logical_address / frame_size
offset = logical_address % frame_size
Physical_address = Frame * frame_size + offset

優點是每個當下都只需要裝需要執行的那部分程式
會使人感覺記憶體容量無限
適合虛擬環境

### 5. Process management:
分為五種狀態
* New: 程序剛被創立
* Ready: 隨時可以執行
* Waiting: 等待CPU以外的資源
* Running: 執行中
* Terminates: 結束

PCB 是一個OS用來儲存及規劃一個process的資料結構

### 6. CPU schedualing:
課本介紹了三種，並分為兩類，非競爭性與競爭性
#### Nonpreemptive(非競爭性)：
這裏包含兩種方法
##### FCFS：
first come first serve 就只是先來的先執行
##### SJN：
shorest job next 是安排最小執行時間的先執行
由於還沒執行，因此我們不知到他的執行時間有多長，因此不是最受歡迎的
#### Preemptive:
##### Round Robin:
設定一個timeslice
每個程序都輪流跑timeslice的時間
是最公平且最受歡迎的

###### 恭喜讀完第10章 (^_\^)v

## CH11

### 目錄：
1. Dictionary trees
2. File intro
3. Disk schedualing

### Dictionary Trees:
windows 和 linux 系統的資料架構
每個Dictionary裡，不能有重複的名字
注意⚠️斜線方向⚠️
#### absolute address:
從根到目的的路徑
#### relative address:
從現在位置到目的的路徑

### File introduction:
有兩種類型，text, binary
text files 是純文字檔，如.txt 或 程式嗎檔
binary files 是其他

由於所有檔案都是01組成、只是翻譯方式不同，因此更改副檔名不會損毀檔案，只是會開不了檔案

文件有保護機制，只有相應的權限才能做相應的是，不懂的可以參考ppt的權限

文件存取方式有兩種，一種是順序性，另一種是直接性
可以參考磁帶及RAM

### Disk schedualing:
一樣，分三種
#### A. FCFS:
不用多說了
#### B. SSTF:
shortest seek time first 是按照距離現在位置最近的順序去找
#### C. SCAN:
scan 是來回掃描
他還有circular的模式，也就是掃到底時回到原點

###### 恭喜讀完ch 11 🥳

## CH 15