###### tags: `說明`
:::danger
筆記內容用於個人學習，大都整理自公開的網路資訊，再加上自己的學習心得
:::

---
[TOC]

---
# 計算機結構 & 計算機概論

## 電腦的發展史
### 第 0 代電腦(1939-1946)
3，000 個以上的繼電器(Relay)和多量的齒輪

電腦的試作機為1944年艾肯教授所完成的哈佛大學的 ASCC-MARK-I 。在MARK-I中，使用了3，000個以上的繼電器 (Relay)和多量的齒輪，MARK-I為電氣機械式的電腦。MARK-I 採用的構想與今天的電系統的構想，幾乎相同 。為執行計算，事先排定指令，編製程序手冊，並將它轉換於紙帶上，成為打孔的組合，指示機械，如此使機械能依循程序 手冊，實行計算。這種處理方式稱為，自動逐次控制方式。
### 第 1 代電腦(1946-1959)
==真空管時期==: _目的是用來計算砲彈彈道而誕生_

第二次世界大戰期間，美國軍方要求賓州大學莫奇來（Mauchly）博士和他的學生愛克特（Eckert）設計以真空管取代繼電器的"電子化"電腦ENIAC，目的是用來計算砲彈彈道。這部機器使用了18800個真空管，長50英呎，寬30英呎，佔地1500平方英呎，重達30噸（大約是一間半的教室大，六隻大象重）。它的計算速度快，大約一秒鐘可以做300多個乘法運算。然而，這部龐然大物所產生的熱量造成嚴重的冷卻問題，同時消耗大量電力。另外，真空管的損耗率相當高，幾乎每15分鐘就可能燒掉一支真空管，操作人員須花15分鐘以上的時間才能找出壞掉的管子，使用上極不方便。
### 第 2 代電腦(1959-1964)
==電晶體時期==

西元1948年美國貝爾實驗室的科學家J.Bardeen、H. W. Brattain和W. Shockley共同發展出電晶體，這項發明給一般的電子應用帶來極大的變革，尤其是電腦。它使電腦的體積更小，重量更輕，省電，故障率降低，計算能力更快。由貝爾實驗室製造的第二代電腦TX-0，便是用了800個電晶體所製造出來的。由於體積大幅縮小，重量輕，使得電腦的應用範圍由軍事用途擴大到政府機關行政用途。

這時期高階程式語言也發展出來了，程式師只要將注意力集中在解決問題上，不再需要自己去應付機器所有的細節，對未來的資訊工業發展，有重要的影響。
### 第 3 代電腦(1964-1970)
==積體電路時期==

西元1964年，美國IBM公司用積體電路設計成功的IBM SYSTEM-360型電腦問世後，開啟了第三代電腦的序幕。西元1959年，德州儀器和Fairchild半導體公司共同推出積體電路（Intergrated Circuit, IC）。它由矽作成，是一種能傳導電流的晶體，一片比八分之一英吋還小的晶片上，包含了幾百個電子原件，構成一個完整的電子電路。一個一公分平方的晶片就可以存放相當於一份報紙的字數，而且計算速度幾乎快到以十億分之一秒為單位。另外，使用三千三百萬個小時後，才可能發生故障，因此耗用能源少，價格更為低廉。

同時，多元語言程式廣為應用，打字機式操作的遙控作業逐漸普遍，促進了預先定位和信用確認範疇的消費者服務業之繁榮。

### 第 4 代電腦(1970-1990)
==超大型積體電路時期 **(VLSI)**==

西元1975年，超大型積體電路（VLSI）被完成，一片積體電路晶片可裝進上萬個電子原件，體積比第一代電腦小了數百倍，計算速度卻快了千倍以上。它促進了設計電子電路、資料通訊、計算機軟硬體和輸入／輸出裝置的長遠進步。這種晶片製造的電腦，就是近代風行的個人電腦（PC, Personal Computer）。

　　延續超大型積體電路而發展的微處理機（一片晶片上的通用處理機），體積小，能力強大而價格低廉，更可實際應用於家庭和商業利用於每一種機器上，如：微波爐、冷氣機、音響、電視、洗衣機等等。無庸置疑，電腦將是日常生活中不可或缺的一環。

　　到目前為止，個人電腦一直扮演時代進步的重要工具，在這個時代，資訊工業正處於快速成長階段，進步之快讓人無法喘息，微處理機（CPU）的處理速度與日俱增，由美國英代爾公司（INTEL Corp.）所研發的電腦晶片，從1989年到1998年短短的十年內，將CPU只有8MHz的處理速度，發展到目前的300MHz以上，以往複雜的立體動畫浮點運算，原本要花二十幾天的計算時間，現在只要一分半鐘，甚至更快的速度便可完成。
### 第 5 代電腦(1990-現在)
==AI==

人工智慧簡稱為AI，前面四個時期都是由於硬體部份技術的進步。第五代電腦的來臨是由於軟體上的突破，而且可能製造出真正有智慧的電腦。日本把1990年的第五代電腦的實現視為國家重點發展，政府與工業界預計投資十億美元在研究發展上。這個時期發展的電腦希望具有像人類一樣有學習、判斷、思考及推理的能力。


___
## 電腦硬體的五大單元
1. 輸入單元(Input Unit)簡稱 **IU**
2. 輸出單元(Output Unit)簡稱 **OU**
3. 控制單元(Control Unit)簡稱 **CU**
4. 記憶單元(Memory Unit)簡稱 **MU**
5. 算術邏輯單元(Arithmetic & Logic Unit)簡稱 **ALU**

___
## 固態硬碟
1. SLC(Single-Level Cell)
單層儲存
即 1 bit/cell，速度快壽命長，價格貴，約 10 萬次擦寫壽命
3. MCL(Multi-Level Cell)
多層儲存
即 2 bit/cell，速度一般壽命一般，價格一般，約 3000---10000 次擦寫壽命
3. TLC(Triple-Level Cell)
三層儲存
即 3 bit/cell，速度慢壽命短，價格便宜，約 500-1000 次擦寫壽命

錯誤率：SLC＜MLC＜TLC
速度、壽命及成本：TLC＜MLC＜SLC

---
## 階層式記憶體

___
## 記憶體 RAM(Random Access Memory)
### SRAM (Static RAM)
#### 靜態隨機存取記憶體
**(揮發性記憶體)**
SRAM 速度非常快，是目前讀寫 ==**最快的存儲設備了**==，但是它也非常昂貴，所以只在要求很苛刻的地方使用，譬如 CPU 的==一級快取==(L1 Cache)，二級快取(L2 Cache)

:::info
目前的快取記憶體分為L1、L2、L3，存取速度
L1 > L2 > l3
:::
靜態隨機存取記憶體（Static Random Access Memory，SRAM）是隨機存取記憶體的一種。所謂的「靜態」，是指這種記憶體 ==**只要保持通電，裡面儲存的資料就可以恆常保持**==[1]。相對之下，動態隨機存取記憶體（DRAM）裡面所儲存的數據就需要週期性地更新。
:::danger
然而，當電力供應停止時，SRAM儲存的數據還是會消失（被稱為volatile memory）
:::
這與在斷電後還能儲存資料的ROM或快閃記憶體是不同的

所謂動態隨機存儲器 DRAM 是用 MOS 電路和==電容==來作存儲元件的。由於==電容會放電，所以需要定時充電==以維持存儲內容的正確，例如互隔 2ms 刷新一次，因此稱這為動態存儲器。

所謂靜態隨機存儲器 SRAM 是用雙極型電路或 MOS 電路的觸發器來作存儲元件的，它沒有電容放電造成的刷新問題。只要有電源正常供電，觸發器就能穩定地存儲數據。

:::success
- 電力停止供應 DRAM 跟 SRAM 數據都遺失，所以才是揮發性記憶體
- 電力保持通電的情況下 SRAM 資料可以保持住，但 DRAM 還要定時充電才可以保持住資料，因要定時充電 (refreshing)所以才叫動態
:::
### DRAM (Dynamic RAM)(揮發性記憶體)
#### 動態隨機存取記憶體
**(揮發性記憶體)**
DRAM 保留數據的時間很短，速度也比SRAM慢，不過它還是比任何的ROM都要快，但從價格上來說DRAM相比SRAM要便宜很多，計算機內存就是DRAM的

動態隨機存取記憶體（Dynamic Random Access Memory，DRAM）是一種半導體記憶體，主要的作用原理是利用電容內儲存==電荷的多寡來代表一個二進位位元（bit）是1還是0==。由於在現實中電晶體會有漏電電流的現象，導致電容上所儲存的電荷數量並不足以正確的判別資料，而導致資料毀損
:::info
因此對於 DRAM 來說，周期性地充電是一個無可避免的要件
:::
由於這種 ==**需要定時重新整理(refreshing) 的特性，因此被稱為「動態」記憶體**==。相對來說，靜態記憶體（SRAM）只要存入資料後，縱使不重新整理也不會遺失記憶。

與 SRAM 相比，DRAM 的優勢在於結構簡單
:::success
每一個位元的資料都只需一個電容跟一個電晶體來處理
:::
相比之下在 SRAM 上一個位元通常需要六個電晶體。正因這緣故，DRAM 擁有非常高的密度，單位體積的容量較高因此成本較低。但相反的，DRAM 也有存取速度較慢，耗電量較大的缺點。

與大部分的隨機存取記憶體（RAM）一樣，由於存在 DRAM 中的資料會在電力切斷以後很快消失，因此它屬於一種 ==**揮發性記憶體（volatile memory）裝置**==。
### SDRAM (Synchronous Dynamic RAM)
#### 同步動態隨機存取記憶體
**(揮發性記憶體)**
是有一個 **同步接口的動態隨機存取記憶體（DRAM）**。

通常 DRAM 是有一個非同步接口的，這樣它可以隨時回應控制輸入的變化。而 SDRAM 有一個同步接口，在回應控制輸入前會等待一個時脈訊號，這樣就能和電腦的系統匯流排同步。時脈被用來驅動一個有限狀態機，對進入的指令進行管線(Pipeline)操作。這使得SDRAM與沒有同步接口的非同步 DRAM (asynchronous DRAM)相比，可以有一個更複雜的操作模式。

SDRAM 在電腦中被廣泛使用，從起初的 SDRAM 到之後一代的 DDR（或稱 DDR1），然後是 DDR2 和 DDR3 進入大眾市場，2015年開始 DDR4 進入消費市場。

### MRAM(Magnetoresistive Random Access Memory)
#### 磁阻式隨機存取記憶體
**(非揮發性記憶體)**

磁阻式隨機存取記憶體（Magnetoresistive Random Access Memory，縮寫為 MRAM），是一種非易失性記憶體技術，從1990年代開始發展。這個技術的擁護者認為，這個技術速度接近 SRAM，具有快閃記憶體的非揮發性，容量密度及使用壽命不輸 DRAM，平均能耗遠低於 DRAM，成為真正的通用型記憶體（Universal memory）[1]。它目前由Everspin公司生產，其他公司，包括格羅方德(GlobalFoundries)和三星集團已經宣布產品計劃[2][3]。

傳統的 RAM 晶片技術不同，MRAM 中的**==數據不作為電荷或電流流動存儲，而是由磁存儲元件存儲**==

---
## 記憶體 ROM(Read Only Memory)
### PROM(Programmable read-only memory)
**(非揮發性記憶體)**

PROM是一次性的，也就是軟件灌入後，就無法修改了，這種是早期的產品，現在已經不可能使用了

可程式化唯讀記憶體（英語：Programmable read-only memory），縮寫為 PROM 或 FPROM，是一種電腦儲存記憶晶片，每個位元都由熔絲或反熔絲的狀態決定資料內容。這種記憶體用作永久存放程式之用。常用於電子遊戲機、電子詞典等預存固定資料或程式的各式電子產品之上。PROM 與狹義的 ROM（Mask ROM）的差別在於前者可在IC製造完成後才依需要寫入資料，後者的資料需在製造IC時一併製作在裡面。

### EPROM (Erasable Programmable Read Only Memory)
#### 抹除式可複寫唯讀記憶體
**(非揮發性記憶體)**

EPROM 是通過紫外光的照射擦出原先的程序，是一種通用的存儲器

可擦拭可規劃式唯讀記憶體（英語：Erasable Programmable Read Only Memory），由以色列工程師 Dov Frohman 發明，是一種斷電後仍能保留資料的電腦儲存晶片——即非揮發性的（非揮發性）。它是一組浮柵電晶體，被一個提供比電子電路中常用電壓更高電壓的電子器件分別編程。
:::info
一旦編程完成後，EPROM只能用 **強紫外線照射來擦除**
:::
通過封裝頂部能看見矽片的透明窗口，很容易識別EPROM，這個窗口同時用來進行紫外線擦除。

### EEPROM (Electrically-Erasable Programmable Read-Only Memory)
#### 電子抹除式可複寫唯讀記憶體
**(非揮發性記憶體)**
EEPROM 是通過電子擦出，價格很高，寫入時間很長，寫入很慢。

EEPROM，或寫作 E^2^PROM，全稱電子抹除式可複寫唯讀記憶體 （英語：Electrically-Erasable Programmable Read-Only Memory）
:::info
是一種可以通過 **電子方式** 多次複寫的半導體儲存裝置
:::
相比 EPROM，EEPROM 不需要用紫外線照射，也不需取下，就可以用特定的電壓，來抹除晶片上的資訊，以便寫入新的資料。

:::success
- 低電壓寫入
- 高電壓抹除
:::

### FLASH(Flash memory)
#### 快閃記憶體
**(非揮發性記憶體)**
快閃記憶體（英語：flash memory），是一種電子清除式可程式唯讀記憶體的形式，允許在==操作中被多次擦或寫的記憶體==。這種科技主要用於一般性資料儲存，以及在電腦與其他數位產品間交換傳輸資料，**如記憶卡與隨身碟**。
快閃記憶體是一種特殊的、以大區塊抹寫的EEPROM。早期的快閃記憶體進行一次抹除，就會清除掉整顆晶片上的資料。

快閃記憶體的成本遠較可以位元組為單位寫入的EEPROM來的低[1]，也因此成為非揮發性固態儲存最重要也最廣為採納的技術。像是PDA、筆記型電腦、數位隨身聽、數位相機與手機上均可見到快閃記憶體。此外，快閃記憶體在遊戲主機上的採用也日漸增加，藉以取代儲存遊戲資料用的EEPROM或帶有電池的SRAM。

快閃記憶體是非揮發性的記憶體。這表示單就儲存資料而言，它是不需要消耗電力的。與硬碟相比，快閃記憶體也有更佳的動態抗震性。這些特性正是快閃記憶體被行動裝置廣泛採用的原因。快閃記憶體還有一項特性：當它被製成記憶卡時非常可靠──即使浸在水中也足以抵抗高壓與極端的溫度。快閃記憶體的寫入速度往往明顯慢於讀取速度。
___
## Amdahl's law
### 阿姆達爾定律
阿姆達爾定律（英語：Amdahl's law，Amdahl's argument），一個計算機科學界的經驗法則，因吉恩·阿姆達爾而得名。它代表了處理器並行運算之後效率提升的能力。

並行計算中的加速比是用並行前的執行速度和並行後的執行速度之比來表示的，它表示了在並行化之後的效率提升情況。

阿姆達爾定律是固定負載（計算總量不變時）時的量化標準。可用公式：
表示問題規模的串行分量（問題中不能並行化的那一部分）和並行分量，p表示處理器數量。

阿姆達爾法則（Amdahl's law）是一個計算如何有效率進行資源分配的好工具
白話點
**$$ S = \frac{1}{(1-a)+{a\over n}} $$**

:::info
S：表示「總系統」提升的效率是原來的 S 倍。
a：表示「部分系統」影響「總系統」效率的比率。
n：表示「部分系統」提升的效率是原來的 n 倍。
:::

記憶體的讀取時間，佔了電腦程序運算20%的時間
處理器的運算時間，佔了電腦程序運算60%的時間

而今天有兩項技術

1. 將記憶體讀取速度提高5倍
S=1/((1-20%)+(20%/5))
S===1.19== (也就是120%)
2. 將處理器速度提高50%
S=1/((1-60%)+(60%/1.5))
S===1.25== (也就是125%)

請問要優先開發技術1還是技術2？

___
## 輸出入設備定址方法
內存映射輸入輸出（英語：Memory-mapped I/O, MMIO，簡稱為內存映射IO），以及埠映射輸入輸出（port-mapped I/O, PMIO，也叫作獨立輸入輸出（isolated I/O），是PC機在中央處理器（CPU）和外部設備之間執行輸入輸出操作的兩種方法，這兩種方法互為補充。
### Isolated I/O addressing
#### 獨立輸入輸出

PMIO通常使用一組專門為IO設計的CPU指令來執行IO操作。比如在基於x86和x86-64架構的微處理器中使用in/out指令。這兩條指令有一些不同的形式，分別用來在CPU的EAX暫存器（或高16位/低16位/高8位/低8位）和IO設備的某個埠之間完成對單字節/雙字節/四字節數據的操作(比如對out指令，分別有outb, outw和outl) 。IO設備有一個和內存地址空間相互獨立的IO地址空間。IO設備通過專用IO針腳或者專用的匯流排和CPU相連。因為這個IO地址空間和內存地址空間相互獨立，所以有時候稱為獨立I/O.

### Memory-mapped I/O MMIO
#### 內存映射I/O（不要和內存映射文件的輸入輸出混淆）

使用相同的地址匯流排來尋址內存和輸入輸出設備（簡稱IO設備）。
:::info
前提是IO設備上的設備內存和暫存器都已經被==映射到內存空間的某個地址==
:::

這樣當CPU訪問某個地址的時候，可能是要訪問某一部份物理內存，也可能是要訪問IO設備上的內存。因此，設備內存也可以通過內存訪問指令來完成讀寫。每個IO設備監測CPU的地址匯流排，並且在發現CPU訪問被分配到本設備的地址區域的時候做出響應，建立數據匯流排和相應設備暫存器之間的連接。為了實現CPU對MMIO設備的訪問，相應的地址空間必須給這些設備保留， 並且不能再分配給系統物理內存。這可以是永久保留，也可以是暫時性的保留。通常來說X86架構都是永久保留的，而在Commodore 64中，由於採用了IO設備和普通內存之間的堆交換技術（bank switching）,可以做到暫時性保留。
___
## 資料傳輸模式
- **並列傳輸** (parallel)

- **序列傳輸** (serial, 又稱串列傳輸
序列傳輸是指資料只透過一條資料線傳輸, 即資
料是以 1 個接著 1 個位元的方式依序傳送, 常
應用在長距離的資料傳輸上, 例如電腦網路上的
資料傳輸。
- **同步傳輸** (synchronous transmission)
一次可傳送數個字元 (characters) 的資料量。
在傳送資料前, 傳送端會先送出同步訊號 (同步
位元) 給接收端, 告知接收端準備開始同步傳
輸。
在傳送的過程中, 雙方會同步計時以便控制資料
的傳送與接收。另外, 為了避免發生資料遺失,
通常會在資料的最後加上一組錯誤偵測位元
(error check bits)。
- **非同步傳輸** (asynchronous transmission)
一次只能傳送1 個字元。為了便於區分每1 個字
元, 通常會在字元的前後分別加上一組起始位元
及終止位元。


___
## 範例:
### BST 二元搜尋樹搜尋鍵值 363 的合法順序
:::success
下列哪些序列可構成二元搜尋樹搜尋鍵值 363 的合法順序？
==`(A)`== 2, 252, 401, 398, 330, 344, 397, 363
==`(B)`== 924, 220, 911, 244, 898, 258, 362, 363
`(C)` 925, 202, 911, 240, 912, 245, 363
==`(D)`== 2, 399, 387, 219, 266, 382, 381, 278, 363
`(E)` 935, 278, 347, 621, 299, 392, 358, 363
:::
:::warning
實際上畫畫看是否存在合法的 BST tree
畫 BST TREE 時要留意每一個數值要
:::danger
比自己上面所對應的數字的右子樹「\」的值大, 比左子樹「/」的值小
:::
___
## 常用搜尋演算法
[搜尋看更詳細可參考該網站的內容](http://notepad.yehyeh.net/Content/Algorithm/Search/LinearSearch/LinearSearch.php)

### ==循序搜尋法(Sequential Search)==
:::info
:mega:概念
> 由右至左，或由左至右一一比對，直到找到鍵值或陣列結束
> :::success
>循序搜尋法(Sequential Search)即線性搜尋法(Linear Search)
> :::
>[color=blue]

>:memo:作法 [color=blue]
> - **無崗哨(衛兵)線性搜尋(Non-Sentinel Linear Search)**
> 直接對數列由右至左，或由左至右一一比對是否有與鍵值相同的元素，需比對陣列值是否與鍵值相同、陣列是否結束
> - **崗哨(衛兵)線性搜尋(Sentinel Linear Serach)**
直接對數列由右至左，或由左至右一一比對
將鍵值放在陣列的 ==**第一個或最後一個元素**==，並把這個元素當成 ==**崗哨(衛兵)**== 一定可以找到與鍵值相同的元素

> 時間複雜度為 ==**Ο(n) ⇒ 線性**== [color=blue]
> :memo:實作範例
> 
> [color=blue]
:::warning
可以省下檢查陣列是否結束的時間，當資料很大時，時間約為無崗哨線性搜尋的一半
:::danger
特性：
- **資料不需事先排序**
- 支援隨機存取(Random Access)機制
- 循序存取(Sequential Access)機制
:::

### ==二分搜尋法(Binary Search)==
:::info
:mega:概念
> 資料 ==**需依大小先排序好**==，對於已排序好的資料，利用已排序的特性來加快搜尋速度
>[color=blue]

>:memo:作法 [color=blue]
> Middle = ⌊(Left + Right)/2⌋
將鍵值鍵值與搜尋範圍的中間資料 data[Middle]作比對
>- key = data[Middle]：找到
>- key < data[Middle]：縮小搜尋範圍 ⇒ Right = Middle-1
>- key > data[Middle]：縮小搜尋範圍 ⇒ Left = Middle+1
> 重複上步驟，直到找到資料或搜尋範圍交叉(找不到)

N個數，最多搜尋幾次才能搜尋得到結果？

2^k-1^= N

k-1=log~2~N

k=(log~2~N)+1

答案為 ==**(log~2~N)+1**==

當 N=1 時, log1=0 0+1=1；因此最少需要搜尋1次。

> 時間複雜度為 ==**Ο(log~2~^n^)**== [color=blue]
> :memo:實作範例
>
> [color=blue]
:::danger
特性：
- **資料需事先排序**
- 支援隨機存取(Random Access)機制
:::
___
## 雜湊搜尋法(Hashing Search)
存取資料時，並不依資料順序存取，是應用資料中某欄位之值代入事先設計好之函數(雜湊函數)，計算資料存放之位置。這種方式稱雜湊法(Hashing)。
【定義】將資料按照某特定法則轉換為資料儲存位置，應用時是以資料鍵值(key value)轉換。

【優點】
1. ==搜尋速度最快。==
2. ==資料不需事先排序。==
3. 在沒發生碰撞(collision)與溢位(overflow)之情況下，只需一次即可讀取。
4. ==搜尋速度與資料量大小無關。==
5. 保密性高，若不知雜湊函術，無法取得資料。

【缺點】
1. 浪費空間(因有溢位資料區)，並且儲存空間的利用率比循序檔差。
2. 有碰撞問題，當資料檔記錄到一定量時會嚴重影響處理速度存取速度。
3. 程式設計比較複雜。
4. 大量資料無效率。
5. 不適合循序型煤體，如磁帶。

【演算法】主要依雜湊函數之計算、碰撞與溢位為考量依據。以下簡單討論幾種雜湊函數與溢位處理方法。

---
## 費氏搜尋法(Fibonacci searching)
費氏搜尋法 (Fibonacci Search) 又稱費伯那搜尋法, 此法與二分法一樣都是以==切割範圍來進行搜尋==, 不同的是費氏搜尋法不以對稱(對半)切割而是以**費氏級數的方式切割**

費氏級數 : 0,1,1,2,3,5,8,... . 也就是除了第 0 及第 1 個元素外, 每個值都是前兩個的值的加總

> 時間複雜度為 ==**Ο(log~2~^n^)**== [color=blue]
> :memo:實作範例
>
> [color=blue]
:::danger
特性：
- **資料需事先排序**
:::info
費式搜尋法的好處是只用到**加減運算,而不須用到乘法及除法**
如此對於 **程式的效率** 有很大的幫助。
:::
平均而言，費氏法的比較次數會少於二元搜尋法，但最壞的情況下則遜於二元法。其平均時間為O(log2^n^)
:::

假設我們要在已經排序好的數列中找到數字：
費氏數列 fib = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144]
查找資料 data = [**-∞**,1,3,5,7,9,13,15,17,19,20]
**~(為了計算方便，通常會將索引0訂作-∞，而數列由索引1開始）~**
搜尋值 key = 5

如果要搜尋 5 的話，則由索引F5（F5表示第五個費式數作為索引，也就是5）開始搜尋，接下來如果數列中的數大於指定搜尋值時，就往左找，小於時就向右，每次找的間隔是F4（第四個費式數作為索引，也就是3）、F3（第三個費式數作為索引，也就是2）、F2（第二個費式數作為索引，也就是1）來尋找，**==當費氏數為0時還沒找到，就表示尋找失敗==**，如下所示：


如果要搜尋19，由於第一個搜尋值索引F5處的值小於19，所以此時必須對齊數列右方，也就是將第一個搜尋值的索引改為F5+2 = 7，然後如同上述的方式進行搜尋，如下所示：


:::info
公式: **n** 為搜尋對象的總個數，**fib[i]** 為第 i 個費式數，必須小於等於 n，若算出 **x** 值，則使用 fib[x] 作為第一個搜尋索引，也就是第 x 個費式數：

fib[i] + m = n
fib[i] >= n + 1
x = i - 1

:::
**決定第一個搜尋值 fib[i]**
第一個搜尋值是如何找法？
1. fib[i]中 **最接近小於或等於** 查找資料的長度大小
要由 **11** 個數字(Key) 找出 5 則
fib[6]= 8，fib[7]= 11，故找 fib[6]，則 **i = 6**，x = **i** - 1 ， **x = 5**
2. **搜尋位置的對齊**
資料索引的最大值 **n = 10**
fib[6] + **m** = 10 ， 8 + **m** = 10，**m = 2**
3. - 如果 fib[x]的值大於搜尋值，則搜尋起點為 **x**~(如上述找5)~
- 如果 fib[x]的值小於搜尋值，則搜尋起點為 **x + m**~(如上述找19)~

4. 由搜尋起點開始，往左或往右按 **fin(x-1)的值** 一路往下跳著找，**==當 fin(0)時還沒找到，就表示尋找失敗==**
___
## 費馬定理
:::info
若 p 為質數且(a,p)互質，則 ==**a^p-1^mod p = 1**==
:::
## 費馬小定理
:::info
若 p 為質數，則 ==**n^p^=n(mod p)**==
:::

___
## 常用排序演算法
[排序看更詳細可參考該網站的內容](http://notepad.yehyeh.net/Content/Algorithm/Sort/Sort.php)

### ==氣泡排序法(Bubble Sort)==
:::info
:mega:概念
> 每執行一輪比對就像水中的氣泡一般(往上)最大值會往邊邊靠(右跑)[color=blue]
>
:memo:作法
> 由未排序中的第一筆開始，與第二筆資料比對若第一筆 > 第二筆 ⇒ ***交換位置(Swap)***
[color=blue]

:memo:實作範例
> 
[color=blue]
:::

### ==合併排序法(Merge Sort)==
:::info
:mega:概念
> 將2個已排序的陣列合併，只需要 N 次比對的線性時間(Linear Time)比對次數最多為：
> 左子數列長度 + 右子數列長度 - 1
> **將數列分成左、右子數列，分別對其作排序及合併**
> 合併排序是 ==**外部排序法**==。
> [color=blue]

:memo:作法
> 將數列對分成左子數列、右子數列
> 分別對左子數列、右子數列作上一個步驟 ⇒ 遞迴(Recursive)
> 將左子數列及右子數列依大小合併成一個新的數列[color=blue]

:memo:實作範例
> 
> [color=blue]
:::
### ==插入排序法(insertion Sort)==
:::info
:mega:概念
> 依序由未排序中的第一筆(正處理的值)，插入到已排序中的適當位置[color=blue]
>
:memo:作法
> 插入時由右而左比較，直到遇到第一個比正處理的值小的值，再插入比較時，若遇到的值比正處理的值大或相等，則將值往右移
[color=blue]

:memo:實作範例
> 
[color=blue]
:::
### ==基數排序法(Radix Sort)==
:::info
:mega:概念
> 又叫基底排序、Bin Sort、Bucket Sort 是一種**分配式**排序(Distribution Sort)
> [color=blue]

:memo:作法
> 利用桶子(Bucket)來分類
以r為基底(Base)時，需準備r個桶子 ⇒ 數值時，基底即為進制
範例：排序10進位數字，需10個桶子
資料的位數即為執行的回合數
數值的範圍在0~9內，需執行1回合
數值的範圍在0~99內，需執行2回合
數值的範圍在0~999內，需執行3回合
[color=blue]

:memo:實作範例
> 
> 
> 
[color=blue]
:::
### ==搖晃排序法(Shaker Sort)==
:::info
:mega:概念
> 搖晃排序法為氣泡排序法的改良[color=blue]
>
:memo:作法
> 每回合會利用氣泡排序法
將未排序資料中**最大值**，移到未排序資料的**最右邊**
將未排序資料中**最小值**，移到未排序資料的**最左邊**
[color=blue]

:memo:實作範例
>[color=blue]
:::

### ==選擇排序法(Selection Sort)==
:::info
:mega:概念
> 第一個 for 迴圈(i) 為數列的每一個位置都執行一次，第二個 for 迴圈(j) 為數列中每一個未排序的位置都拿出來比較後較小的排入第一個 for 迴圈(i) 當次挑選的位置中
[color=blue]
>
:memo:作法
> 依序由未排序中找最小值(or 最大值)，加入到已排序部份的末端
[color=blue]
:::info
排序法 **swap (置換)** 的次數比堆積,插入,合併少
:::

:memo:實作範例
>
[color=blue]
:::

### ==快速排序法(Quick Sort)==
:::info
:mega:概念
> 快速排序法採用**分割與征服(Divide and Conquer)** 策略將問題分解成較小的子問題，用相同的解決程序一一解決後再將子問題的結果整合成原問題的答案
快速排序法是最快的排序法之一
快速排序是 ==**內部排序法**==。
[color=blue]
>
:memo:作法
> 選定一個 ***基準值(Pivot)***
將比基準值(Pivot)**小的數值移到基準值左邊**，形成左子串列
將比基準值(Pivot)**大的數值移到基準值右邊**，形成右子串列
分別對左子串列、右子串列作上述三個步驟 ⇒ **遞迴(Recursive)**
[color=blue]
> :::danger
> 快速排序法的效率和基準值(Pivot)的選擇息息相關
> 每次選擇的基準值(Pivot)愈接近數列的**平均值**或**中> 位數**愈好
> :::
>:memo:實作範例
> 
> 
> 
[color=blue]
:::
#### median of medians 找出中位數 O(n)
只求中位數，要求O(n)，參考 **median of medians** . 此算法可用在 quicksort 和quickselect 中，以 **O(n)** 的時間找到pivot 點進行 partition，可以將 quicksort 的最壞時間複雜度降低至O(nlgn)， quickselect 降至 O(n)。
### ==堆積排序法(Heap Sort)==
:::info
:mega:概念
>利用堆積樹(Heap Tree)的性質來排序最大堆積樹(Max Heap Tree)的根節點一定是最大值，一一與最後一個樹葉節點交換後，取出加入已排序數列將原來的樹重新調整為最大堆積樹
[color=blue]
>
:memo:作法
> 二元樹的一種 ⇒ 每個父節點最多兩個子節點堆積樹為完全二元樹(Complete Binary Tree)的一種 [color=blue]
> > **最小堆積(Min Heap)**：父節點的值小於子節點樹根(root)一定最所有節點的**最小值**
>
> > **最大堆積(Max Heap)**：父節點的值大於子節點根(root)一定最所有節點的**最大值**
>
> 兄弟節點的大小不重要
> 堆積排序法為 **選擇排序法的改良**
>
> :::danger
> 快速排序法的效率和基準值(Pivot)的選擇息息相關
> 每次選擇的基準值(Pivot)愈接近數列的**平均值**或**中位數**愈好
> :::
> :memo:實作範例
> [heap實作圖解請參考](http://notepad.yehyeh.net/Content/Algorithm/Sort/Heap/Heap.php)
[color=blue]
:::
___
## 排序演算法之穩定性與複雜度
排序演算法分為穩定(Stable)和不穩定(Unstable)兩種，是指
:::danger
當資料中有相等數值的兩元素，經過排序之後是否能夠保持原有的相對位置，位置不變就是穩定
:::

當相等的元素是無法分辨的，比如像是整數，穩定性並不是一個問題。然而，假設以下的數對將要以他們的第一個數字來排序。
{(4,1)(3,1)(3,7)(5,6)}
在這個狀況下，有可能產生兩種不同的結果，一個是讓相等鍵值的紀錄維持相對的次序，而另外一個則沒有：

{ (3,1)(3,7)(4,1)(5,6)} （維持次序）穩定

{ (3,7)(3,1)(4,1)(5,6)} （次序被改變）不穩定

整理如下
:::info
:memo: :mega:
> 穩定: **氣合插基搖** [color=red]
> > 練 ***氣合*** 道的人就算被插 ***雞雞*** 也不可 ***搖*** 要保持**穩定**
[name=mohjj][time=2019 ,02 ,23][color=blue]

| |時間複雜度 |空間複雜度|穩定(Y/N)|
| :--------: | :--------: |:--------: |:--------: |
|==氣泡排序法==<br>(Bubble Sort)|B:Ο(n) W/A:Ο(n^2^) |Ο(1) | **Y**
|==合併排序法==<br>(Marge Sort)|**Ο n log n** |Ο(n) | **Y**
|==插入排序法==<br>(Insertion Sort)|B:Ο(n) W/A:Ο(n^2^) |Ο(1) | **Y**
|==基數排序法==<br>(Radix Sort)|Ο(d × (n+r)) |Ο(n × r) | **Y**
|==搖晃排序法==<br>(Shaker Sort)|B:Ο(n) W/A:Ο(n^2^) |Ο(1) | **Y**
|==快速排序法==<br>(Quick Sort)|B/A:Ο(n log n) W:Ο(n^2^) |Ο(log n) ~ Ο(n) | N
|==堆積排序法==<br>(Heap Sort)|**Ο(n log n)** |Ο(1) | N
|==選擇排序法==<br>(Selection Sort)|**Ο(n^2^)**<br>(無論資料順序如何，都會執行兩個迴圈) |Ο(1) | N
:::
___
## 範例:
### CPI(Cycle Per Instruction) 計算
計算機單個指令運行時間，即執行一條指令所需要的時鐘周期
:::success
依據下列資訊計算出 CPI = ？ Integer Arithmetic: IC=95000, CCC=1 Data Transfer: IC=40000, CCC=3 Floating Point: IC=25000, CCC=3 Control Transfer: IC=10000, CCC=4
`(A)` 0.94
==`(B)`== 1.94
`(C)` 2.94
`(D)` 3.94
`(E)` 4.94
:::
:::warning
\begin{align}
& CPI = {(95000 * 1) + (40000 * 3) +(25000 * 3) +(10000 * 4) \over (95000+40000+25000+10000)}
= 1.94
\end{align}
:::
___
## 河內塔(Hanoi Tower)
河內塔(Hanoi Tower)問題搬移為 ==stack==
:::danger
最少移動次數為 2^n^ - 1
:::

河內塔（中國大陸：漢諾塔，香港：河內塔）是根據一個傳說形成的數學問題：

有三根杆子A，B，C。A杆上有 N 個 (N>1) 穿孔圓盤，盤的尺寸由下到上依次變小。要求按下列規則將所有圓盤移至 C 杆：

每次只能移動一個圓盤；
大盤不能疊在小盤上面。
提示：可將圓盤臨時置於 B 杆，也可將從 A 杆移出的圓盤重新移回 A 杆，但都必須遵循上述兩條規則。

問：如何移？最少要移動多少次？

最早發明這個問題的人是法國數學家愛德華·盧卡斯。

傳說越南河內某間寺院有三根銀棒，上串 ==64== 個金盤。寺院裡的僧侶依照一個古老的預言，以上述規則移動這些盤子；預言說當這些盤子移動完畢，世界就會滅亡。這個傳說叫做梵天寺之塔問題（Tower of Brahma puzzle）。但不知道是盧卡斯自創的這個傳說，還是他受他人啟發。

若傳說屬實，僧侶們需要 ==2^64^ -1==步才能完成這個任務；若他們每秒可完成一個盤子的移動，就需要 5849 億年才能完成。整個宇宙現在也不過 137 億年。

這個傳說有若干變體：寺院換成修道院、僧侶換成修士等等。寺院的地點眾說紛紜，其中一說是位於越南的河內，所以被命名為「河內塔」。另外亦有「金盤是創世時所造」、「僧侶們每天移動一盤」之類的背景設定。
___
## Spanning Tree
### 生成樹
從一張圖取出一棵樹，包含圖上所有點。可能有許多種。
當一張圖完全連通，則擁有生成樹。當一張圖不連通，則沒有生成樹，而是擁有許多棵「生成子樹」構成的「生成森林」。

生成樹的權重，是樹上每條邊的權重總和。

:::info
「最小生成樹」。==權重最小==的生成樹。可能有許多種。
:::


### Kruskal's Algorithm
按照邊的權重順序（從小到大）將邊加入生成樹中，但是若加入該邊會與生成樹形成環則不加入該邊。直到樹中含有V-1條邊為止。這些邊組成的就是該圖的最小生成樹。

:::success
每次只選一條 edge、且在==起始時一定要選最小成本的 edge==
:::danger
由 邊 找 點
:::


### Prim's Algorithm
Prim演算法的每一步都會為一棵生長中的樹添加一條邊，該樹最開始只有一個頂點，然後會添加 V-1 個邊。
:::info
每次總是添加生長中的樹和樹中除該生長的==樹以外的部碎形成的切分的具有最小權值的橫切邊==。
:::danger
由 點 找 邊
:::

### Sollin 演算法
:::success
按照頂點順序選擇權重最小的邊，不能形成迴路
:::danger
由 點 找 邊
:::
___
## n 節點 tree
例如 n = 3,需要區別時則節點為A,B,C
> ### `(1)`不同的 **binary tree**[color=red]
> > `(a)` 節點不分彼此的形況: **5 種**
> > 
> > 公式: C(2n,n)/(n+1) = C(6,3)/4 = 5
> >
> > `(b)` 節點區分彼此的形況: **30 種**
> > 有分彼此所以上面 5 情況種都可再排序，故為 5x3! = 30
> > 
> > [color=blue]
> >
> ### `(2)`構成不同的有序樹(ordered tree) : **12 種**
> > :::danger
> > 樹中任意節點的子結點之間有順序關係，表示 child 的順序掉換視為不同，這種樹稱為有序樹
> > :::
> >
> > 首先可構成2種不同型態的結構，因為有序的關係都可再排序，故為 2x3! = 12
> >
> > 
> > [color=blue]
> >
> ### `(3)`構成不同的無序樹(Unordered tree) : **9 種**
> > :::danger
> > unordered 就是將 child 順序對調視為同一種(不包含root)
> > :::
> >
> > 共有以下 9 種
> >
> > 
> ### `(4)`free tree(即 connected acyclic graph) : **3 種**
> > :::danger
> > 自由樹就是一個無迴路的連通圖（沒有確定根，在自由樹中選定一頂點做根，則成為一棵通常的樹）
> > :::
> > free tree 是沒有樹根的，也就是==純粹看路徑上三點排列的方式==
且 ABC, CBA 這種恰好反向排列的情形會因為同構而視為一種
所以有 3!/2=3 種 free tree
> > 
> > [color=blue]
> ### `(5)`free tree(即 connected acyclic graph) : **3 種**
> > :::danger
> > 自由樹就是一個無迴路的連通圖（沒有確定根，在自由樹中選定一頂點做根，則成為一棵通常的樹）
> > :::
> > free tree 是沒有樹根的，也就是==純粹看路徑上三點排列的方式==
且 ABC, CBA 這種恰好反向排列的情形會因為同構而視為一種
所以有 3!/2=3 種 free tree
> > 
> > [color=blue]
___
## 是樹卻不是二元樹例子
___
## Binary Search Tree
### 二元搜尋樹
二元搜尋樹（英語：Binary Search Tree），也稱為有序二元樹（ordered binary tree）或排序二元樹（sorted binary tree），是指一棵 ==**空樹**== 或者具有下列性質的 ==**二元樹**== ：

* 若任意節點的左子樹不空，則左子樹上所有節點的值均小於它的根節點的值；
* 若任意節點的右子樹不空，則右子樹上所有節點的值均大於它的根節點的值；
* 任意節點的左、右子樹也分別為二元搜尋樹；
* 沒有鍵值相等的節點。


==**表示數字大小關係為 左 <= 中 <= 右,且鍵值不能重複**==
___
## DFS(Depth-first search)
### 深度優先搜尋法

是一種用來遍尋一個樹(tree)或圖(graph)的演算法。由樹的根(或圖的某一點當成根)來開始探尋，先探尋邊(edge)上未搜尋的一節點(vertex or node)，並儘可能深的搜索，直到該節點的所有邊上節點都已探尋；就回溯(backtracking)到前一個節點，重覆探尋未搜尋的節點，直到找到目的節點或遍尋全部節點。

ex:
假設起始點為 A，且每一節點由左至右的順序來搜尋下個節點，則結果為: A, B, E, F, D, C, G

:::danger
跟 迷宮問題 一樣都適合用 stack 來解決
:::
## BFS(Breadth-first search)
### 廣度優先搜尋法
是一種圖形(graph)搜索演算法。從圖的某一節點(vertex, node)開始走訪，接著走訪此一節點所有相鄰且未拜訪過的節點，由走訪過的節點繼續進行先廣後深的搜尋。以樹(tree)來說即把同一深度(level)的節點走訪完，再繼續向下一個深度搜尋，直到找到目的節點或遍尋全部節點。

ex:
假設起始點為 A，且每一節點由左至右的順序來搜尋下個節點，則結果為: A, B, C, D, E, F, G

:::danger
適合用 queue 來解決
:::

___
## 運算式前中後序
### 中序（Infix）
平常所使用的運算式，主要是將運算元放在運算子的兩旁，例如a+b/d這樣的式子，這稱之為中序（Infix）表示式，對於人類來說，這樣的式子很容易理 解，但由於電腦執行指令時是有順序的，遇到中序表示式時，無法直接進行運算，而必須進一步判斷運算的先後順序，所以必須將中序表示式轉換為另一種表示方法。
### 後序（Postfix）表示式
用手算的方式來計算後序式的話，可以使用括號法。
:::info
- 將運算子兩旁的運算元依先後順序全括號起來
- ==**右括號取代為左邊最接近的運算子**==（從最內層括號開始）
- 最後去掉所有的括號就可以完成後序表示式
:::

a+b*d+c/d => ((a+(b*d))+(c/d)) -> abd*+cd/+

### 前序（prefix）表示式
:::info
- 將運算子兩旁的運算元依先後順序全括號起來
- ==**左括號取代為右邊最接近的運算子**==
- 最後去掉所有的括號就可以完成前序表示式
:::

a×b＋c×d => ((a×b)＋(c×d)) -> ＋×ab×cd

---
## 由前中後序重新建構原二元樹結構
:::danger
只有先序+後序因為都只能分辨出root,無法分左右
故無法重新建構原二元樹結構
:::
### 先序+中序
先序決定root,再配合中序分左右
### 後序+中序
後序決定root,再配合中序分左右
### 先序+分支度

___
## RISC(reduced instruction set computing)
### 精簡指令集計算
精簡指令集計算（英語：reduced instruction set computing，縮寫：RISC）或簡譯為精簡指令集，是電腦中央處理器的一種設計模式。這種設計思路可以想像成是一家流水線工廠，對指令數目和尋址方式都做了精簡，使其實現更容易，指令並列執行程度更好，編譯器的效率更高。目前常見的精簡指令集微處理器包括DEC Alpha、ARC、ARM、AVR、MIPS、PA-RISC、Power Architecture（包括PowerPC、PowerXCell）和SPARC等。

## CICS(Complex Instruction Set Computing)
### 複雜指令集
複雜指令集（英文：Complex Instruction Set Computing；縮寫：CISC）是一種微處理器指令集架構，每個指令可執行若干低階操作，諸如從記憶體讀取、儲存、和計算操作，全部集於單一指令之中。與之相對的是精簡指令集。

複雜指令集的特點是指令數目多而複雜，每條指令字長並不相等，電腦必須加以判讀，並為此付出了效能的代價。

### RISC vs CISC
現代的CISC中包含了很多複雜指令，這些指令的實現其實是相當于將其分解為多條更為簡單的指令運行。其優點就是簡化代碼，從而提供更多的功能，但由於
指令的執行時間各不相同且差別很大（從幾個時鐘周期到幾十個不等）使得 pipeline 難以設計且不能完全填滿，這樣就造成了時間的浪費從而降低了速度。
相比而言，RISC則具有以下優點
1. RISC 指令系統較小：種類的數量較少，只提供簡單指令。這些指令大多都在 4，5 個時鐘週期內完成。

2. 指令的運算元必須==預存於 register 中==，這樣操作的時間也統一了。
3. 指令長度，定址方式，格式都整齊劃一：這樣可以充分利用流水線，基本上可實現一個時鐘脈衝執行一條指令的目標。
4. RISC 的副程式調用與 CISC 的不同：在 CISC 中，程式調用、返回時需將上下文保存在堆疊中，需要記憶體操作。而 RISC 將它們存放在 register 中，而且參數也使用 register 傳遞。
5. RISC 中斷可視為特殊的副程式鏈結：CISC 中發生中斷時，所有的 register內容都被壓入堆疊，而 RISC 對中斷進行區分對待，分為羽量級和重量級。對羽量級中斷 只保存需要保存的 register 內容；對重量級中斷的處理如同常規中斷。
6. ==RISC== 都採用 piplining、快取記憶體、==不使用微碼==。
7. ==RISC 目標代碼(object code)程式通常較大==

___
## CPU 暫存器分類
暫存器通常分成兩大類
1. **程式設計人員能夠存取的可見暫存器**(使用者暫存器)
–通用暫存器 (general purpose register)
–==資料暫存器 (data register)==
–==位址暫存器 (address register)==
–條件碼暫存器 (condition code register)
2. **程式設計人員無法存取的控制與狀態暫存器**(控制狀態暫存器)
–==程式計數器 (program counter)==
–==指令暫存器 (instruction register)==
–記憶體位址暫存器 (memory address register)
–==記憶體緩衝暫存器 (memory buffer register)==
–ALU緩衝暫存器 (ALU buffer register)
–中斷向量暫存器 (interrupt vector register)
–程式狀態字組 (program status word)

## 管路設計（Pipelining）
管路（pipeline）是一種資料路徑的製作技巧，它可以重疊指令的執行（同步）。管路並不是縮短單獨一個指令的執行時間，而是增加指令的生產量（throughput）。
用管路技術可以每一個指令的執行時間不變，但生產量提昇
- 管路危障（Pipeline Hazards）
下一個指令不能在緊接著的時脈週期被執行，這樣我造成管理無法全速運作。
- 結構危障(Structural Hazards)
在管路中每一個時脈都有數個指令同時被執行，如果硬體不能滿足所有執行中的指令需求時，就會發生結構危障
- **控制危障(Control Hazards)**
當我們做決策時，此決策參考結果還在執行中
解決方法
- **暫停管路（stall）**
- **分支預測（predict）**
- **延遲分支（delayed branch）**
- **資料危障(Data Hazards)**
一個指令的運算元必須參考前面指令的執行結果，但前面的執行結果卻還在管路中沒有執行完
解決方法
- **可以前送（forwarding）**
- **旁傳（bypassing）**

## CPU
什麼是電腦最基本的 ==**執行單位**==?
電腦裡面最核心的部分就是 processor 處理器，而處理器的工作完完全全是依據使用者給它的命令，再依照這些命令來產生對應的行為，而這些命令我們叫做 ==**instruction 指令**==

什麼是電腦最基本的 ==**時間單位**==?
我們知道電腦本身是一個sequential circuit 循序電路 而讓sequential circuit能夠正常順利的運作 最關鍵的就是需要有一個clock 去控制資料的同步以及更新 也因此電腦最基本的時間單位就是 ==**clock cycle**==

:::success
### 基本名詞與公式
### **Clock Cycle (CPU Clock Cycle)**
==時脈==
- 是電腦內部一個類似時鐘的裝置，它每計數一次，稱為一個時脈週期 (clock cycle)，電腦就可以完成少量工作。
### **Clock Cycle Time** ( t )
==時脈週期時間==
- 時脈每計數一次所經過的時間。
### **Clock Rate** ( f )
==時脈頻率==
- 指的是時脈計數的速度，單位為 MHz (百萬赫茲) 或 GHz (十億赫茲)，也就是 ==**每秒鐘**== 可以產生幾百萬次或幾十億次的 clock 。
:::danger
* 時脈頻率( f )
* 時脈週期時間( t )
成反比，互為倒數
:::
- ex:
若 CPU 時脈頻率為 4GHz，其時脈週期為多少？
4 GHz 表示 1 秒可以完成 4 * 10^9^ 次 clock
==**clock cycle time = ${1\over 時脈頻率}$ = ${1\over4*10^9 }$= ${0.25* 10^{-9} =0.25}$ ns**==

### **IC(instruction count)**
- 程式的指令個數

### **CPU TIME**
- CPU 效能比較唯一只能用 CPU TIME(執行時間)來做判斷比較
:::danger
* ==**CPU Time**==
= ${CPU Clock Cycles * Clock Cycle Time}$
= ${CPU Clock Cycles ÷ Clock Rate}$
:::

:::info
延伸名詞與公式
### **CPI(Clocks Per Instruction)**
- 每一個指令需要執行多少個週期
:::danger
* ==**Clock Cycles =**== ${指令個數 * 每個指令的 Clock Cycle}$
* ==**Clock Cycles = ${ IC * CPI}$**==
* ==**CPU TIME = ${ IC * CPI * Clock Cycle Time}$**==
:::
- 平均 CPI
:::success
The average of CPI in a given process is defined by the following:
Where
* **IC~i~** is the number of instructions for a given instruction type i
* **CC~i~** is the clock-cycles for that instruction type
* **IC=Σ~i~(IC~i~)** is the total instruction count.
The summation sums over all instruction types for a given benchmarking process.
:::danger
:::

每一個程式在處理器執行的時候所需要的clock cycle的個數其實就會跟不同類型的指令 以及這個指令所對應到的CPI (cycle per instruction)有關
我們把指令的個數乘上它的CPI 把它給加總起來就會是這個程式在這個處理器裡面執行總共的clock cycle個數
:::danger

平均的CPI就是上面這邊剛才所推導的式子 把它除以全部這個程式裡面到底有多少個指令有一點點像是 ==**加權**== 的效果

:::
### **MIPS(Million Instructions Per Second)**
- 處理器每秒執行百萬個指令。
:::danger
==**MIPS = ${clock rate \over CPI *10^6}$**==
:::
- ex:
A 400MHz processor was used to execute a benchmark program with the following instruction mix and clock cycle count:
:::
___
## FIT(Failure Instance Time)
### 衡量精密科學設備的失效率是以「非特」（FIT） 為單位，1 非特是10^-9^ 小時

## MTTF(MEAN TIME TO FAILURE)
### 平均故障時間 = ${ 1 \over FIT }$
___
## 記憶體配置
1. ==**First Fit**== (最先符合法)：從串列開頭開始尋找，然後將所找到的第一個足夠大的區塊分配給該程式。
2. ==**Next-Fit**== (下一個符合法)：使用環狀串列的結構，每次都從上一次搜尋停止的點開始搜尋，然後將所找到的第一個足夠大的區塊分配給該程式。
3. ==**Best-Fit**== (最佳符合法)：從頭到尾搜尋整個串列一遍，然後將大小最接近的可用區塊分配給該程式。

4. ==**Worst-Fit**== (最差符合法)：則是將==大小最大的區塊分配給程式== (以便留下較大的洞)。
___
## B樹（英語：B-tree）
是一種自平衡的樹，能夠保持數據有序。這種資料結構能夠讓查找數據、順序訪問、插入數據及刪除的動作，都在對數時間內完成。B樹，概括來說是一個一般化的二元搜尋樹（binary search tree）一個節點可以擁有最少2個子節點。與自平衡二元搜尋樹不同，==**B樹適用於讀寫相對大的數據塊的存儲系統，例如磁碟**==。B樹減少定位記錄時所經歷的中間過程，從而加快存取速度。B樹這種資料結構可以用來描述外部存儲。這種資料結構常被應用在資料庫和文件系統的實現上。

根據 Knuth 的定義，一個 m 階的B樹是一個有以下屬性的樹：
* 每一個節點最多有 m 個子節點
* 每一個非葉子節點（除根節點）最少有 ⌈m/2⌉ 個子節點
* 如果根節點不是葉子節點，那麼它至少有兩個子節點
* 有 k 個子節點的非葉子節點擁有 k − 1 個鍵
* 所有的葉子節點都在同一層
### B-tree height
___
## Computer instruction Fetch Phase
:::info
PC -> MAR ->MEMORY -> MDR -> IR -> MAR -> MEMORY -> MDR -> A -> PC +1 -> PC
:::


- ==**Program counter (PC)**==
An incrementing counter that keeps track of the memory address of the instruction that is to be executed next or in other words, holds the address of the instruction to be executed next.

- ==**Memory address register (MAR)**==
Holds the address of a block of memory for reading from or writing to.

- ==**Memory data register (MDR)**==
A two-way register that holds data fetched from memory (and ready for the CPU to process) or data waiting to be stored in memory. (This is also known as the memory buffer register (MBR).)

- ==**Instruction register (IR)**==
A temporary holding ground for the instruction that has just been fetched from memory.

- ==**Control unit (CU)**==
Decodes the program instruction in the IR, selecting machine resources, such as a data source register and a particular arithmetic operation, and coordinates activation of those resources.

- ==**Arithmetic logic unit (ALU)**==
Performs mathematical and logical operations.
- ==**Floating-point unit (FPU)**==
Performs floating-point operations.
___
## 定址摸式
常見的定址模式有如下九種
> ### `(1)`==立即==定址模式[color=red]
> > 指令的運算元欄內的值就是所要的資料，執行時不必再做額外的記憶體讀取動作，可立即使用該運算元欄內的值做運算。[color=blue]
> >
> `### (2)`==直接==(絕對)定址模式
> > 指令的運算元欄內的值表示資料存放於記憶體的實際位址(有效位址，Effective Address)，故需要做一次的記憶體讀取，以取得所需之資料。此模式亦稱為絕對定地模式。
> > 
[color=blue]
> >
> ### `(3)`==間接==定址模式
> > 指令的運算元欄內的值為有效位址的位址值，故需做二次的記憶體讀取，以取得所需之資料。
[color=blue]
> >
> ### `(4)`==索引==定址模式
> > 將指令的運算元欄位內的值加上索引暫存器內的值，以求得存放資料的有效位址。在此模式中，使用者若想讀取記憶體中其它位址的資料，必須藉由改變索引暫存器內的值，而非調整運算元欄位內的值。
[color=blue]
> ### `(5)`==基底==定址模式
> > 將基底暫存器內的值加上指令的運算元欄位內的值，以得到存放資料的==有效位址==。在此模式中，使用者若想讀取記憶體中其它位址的資料，必須藉由改變運算元欄位內的值，而非調整基底暫存器內的值。
[color=blue]
> ### `(6)`==相對==定址模式
> > 將指令的運算元欄位內的值加上程式計數器內的值，以求得存放資料的有效位址。
[color=blue]
> ### `(7)`==暫存器==定址模式
> > 存放資料的有效位址即是指令的運算元欄位內所指定的暫存器。
[color=blue]
> ### `(8)`==暫存器間接==定址模式
> > 存取資料的有效位址即是指令內所指定暫存器內的值。
[color=blue]
> ### `(9)`==隱含==定址模式
> > 此模式的運算元已經被隱含於指令內。如指令CMA 即是對累加器內值做 1 的補數[color=blue]
> >
___
## Dynamic memory allocation
### 動態記憶體分配
又稱為==堆記憶體分配==，是指電腦程式在執行期中分配使用記憶體。它可以當成是一種分配有限記憶體資源所有權的方法。
記憶體隸屬於該程序位址空間 （address space）的 ==**heap section**==
___
## Cache
CPU cache
是一種被電腦的 CPU 用來降低從主記憶體 (Main Memory) 存取資料時所耗費的時間的快取(Cache)。

### Cache Hit
當 CPU 可以從 Cache 中的 Block 裡找到他想要找的資料時，稱為 Cache Hit
### Cache Miss
當 CPU 沒有辦法從 Cache 中的 Block 裡找到他想要找的資料時，稱為 Cache Miss，會導致讀取速度下降，Cache 必須去主記憶體或其他下層記憶體中找到含有 CPU 想要找的資料的 Block，並複製到 Cache 後，才能將資料傳給 CPU。

### Eviction / Replacement
當新的 Block 被複製到 Cache 時，必須將其他 ==**L.R.U**== (Least Recently Used) 的 Block 移除，而此動作稱為 ==**Eviction**==。

### cache block,sets,index,tag 計算
cache由 set 組成， set 由 block(line) 組成， block(line)由 valid bit， tag 和 data(block offset) 組成。

其中 data 是真正要緩存的內存地址中的數據，而 tag 是用來搜索 cache block(line) 的標籤。

==**Block**==
從下級記憶體(例如：主記憶體)複製資料到上級記憶體(例如： Cache)時的最小單位，通常是 64 Bytes (512 Bits)

==**sets**==
用來放 block 的地方

==**index**==
用來聯結 set，所以 2^s^ sets 的 index bis = s

==**Tag**==
是用來區分不同的 Block 的標記。

==**Valid Bit**==
是用來區分一個 Block 裡的資料是否為有效的。
Valid -> 1
Invalid -> 0
:::info
Cache 的大小的計算公式為：C = S x E x B data bytes
S = 2^s^ sets
E = 2^e^ lines per set
B = s^b^ bytes per cache block (data)
:::
___
## Page
### 分頁
許多作業系統，如Linux、Windows、MAC OS X，都使用分頁的方式來管理記憶體。分頁技術應用在虛擬記憶體(Virtual Memory)上，將一塊實體記憶體(Physical Memory)切成數個固定大小的頁框(Frame)，再將一塊虛擬記憶體切成數個固定大小的分頁(Page)，頁框和分頁的大小必須一樣，接著再藉由分頁表(Page Table)將各個分頁去對應實體記憶體的頁框(Frame)。這樣的作法可以帶來多種好處，好比連續的虛擬記憶體空間在實體記憶體空間上也不一定需要連續，使得記憶體更容易配置(Allocate)，因為不需要在雜亂實體記憶體空間上尋找可用的連續空間。另外，**虛擬記憶體空間可以大於等於實體記憶體空間，超出的空間可以使用輔助記憶體(Secondary Memory)，如硬碟、記憶卡等儲存裝置來儲存，等到有需要存取的時候，再 ==替換(Replacement)== 至實體記憶體空間**。
### 分頁錯誤(Page fault)
當作業系統要存取某個分頁時，會先去分頁表中搜尋該分頁的分頁項目(PTE, Page Table Entry)，這個分頁項目會儲存分頁對應的頁框，以及其他關於這個分頁一些資訊，例如這個分頁目前是不是正存在於實體記憶體中(是不是有頁框可以使用)。若要存取的分頁不存在於實體記憶體中，就會發生分頁錯誤(Page fault)，此時就需要替這個分頁尋找一個頁框來使用。這個在發生分頁錯誤後，尋找頁框並使用的動作就稱為分頁替換(Page Replacement)。

### 分頁替換(Page Replacement)
如果實體記憶體中還有沒使用到的頁框，可以直接將分頁的內容從輔助記憶體移進 ==(swap in)== 這個實體記憶體的頁框中；如果實體記憶體中所有的頁框都已經被分頁使用，那麼只好想辦法找出一個未來可能要很久才會再被用到的頁框中其他分頁的內容，將其移出 ==(swap out)== 至輔助記憶體中儲存，接著再將輔助記憶體中要使用的分頁內容移進(swap in)這個實體記憶體的頁框中。由於這個移出移入(swap in/out)的動作需要許多時間來完成，因此我們會希望分頁替換的次數愈少愈好。也就是說，我們要讓分頁被替換後，再次發生分頁錯誤的機會降低。分頁錯誤的次數愈少，作業系統的運作效能就能愈好，同時也能減少對輔助記憶體的讀寫次數，延長硬體壽命。

### 分頁替換演算法(Page Replacement Algorithm)
- FIFO
- LRU
- Second Chancd
- Random
- Optimal

:::success
#### FIFO (First in First out Page Replacement)
:::
==**將存在於實體記憶體頁框中最久的分頁給取代掉**==
實作起來最為容易。流程如下表，表格填色的部份表示下一次分頁錯誤發生時要拿來進行替換的頁框。
:::success
#### LRU (Least Recently Used Page Replacement)
:::
==**將存在於實體記憶體頁框中最久沒用到的分頁給取代掉**==
實作起來比起FIFO稍微困難，需使用計數變數(Counter)去儲存每個在頁框內的分頁使用後閒置的時間，或是如Linked List等額外的資料結構來儲存過去頁框中的分頁使用的順序，但實行起來成效顯著。流程如下表，分頁後數字的部份為最近使用的排序，數字愈小表示愈久之前使用過。
:::success
#### Second Chance (The Clock Page Replacement)
:::
==**基於 FIFO，但是會重新給予被使用到的分頁第二次機會，使其可以跳過一次頁框被別的分頁選擇取代的命運**==
概念上類似LRU，能保留最近使用過的頁框，但比LRU還要容易實作得多。流程如下表，分頁後數字的部份為剩餘可跳過被選擇取代的次數。
:::success
#### Random Page Replacement
:::
==**基於FIFO，只是當沒有可用的頁框時，會隨機選取一個頁框來替換**==

:::success
#### Optimal Page Replacement
:::
==**基於FIFO，只是當沒有可用的頁框時，會隨機選取一個頁框來替換**==
實作起來最非常困難，因為要預知未來可能會存取的分頁，但是這個將會是理想最佳解。

### Belady's Anormal
當 Process 分配到較多的 Frame 數量，有時其 Page Fault Ratio 卻 ==**不降反升**==。
___
## Microwave
### 微波
微波（英語：Microwave，德語：Mikrowellen）是指波長介於紅外線和無線電波之間的電磁波。微波的頻率範圍大約在 300MHz至300GHz之間。所對應的波長為1公尺至1mm之間。微波頻率比無線電波頻率高，通常也稱為「超高頻電磁波」。微波作為一種電磁波也具有波粒二象性。微波的基本性質通常呈現為穿透、反射、吸收三個特性。對於玻璃、塑料和瓷器，微波幾乎是穿越而不被吸收。對於水和食物等就會吸收微波而使自身發熱。而對金屬類東西，則會反射微波[1]

:::success
微波傳輸有方向性，比較不容易受到干擾
:::

## 紅外通訊技術
紅外通訊技術利用紅外線來傳遞數據，是無線通訊技術的一種。

紅外通訊技術不需要實體連線，簡單易用且實現成本較低，因而廣泛應用於小型移動設備互換數據和電器設備的控制中，例如筆記本電腦、個人數碼助理、移動電話之間或與電腦之間進行數據交換（個人網），**電視機、空調的遙控器**等。

由於紅外線的直射特性，==**紅外通訊技術不適合傳輸障礙較多的地方**==，這種場合下一般選用無線電通訊技術或藍牙技術。紅外通訊技術多數情況下傳輸距離短、傳輸速率不高。

___

## 行程狀態(Process State)
一個行程的生命期可以劃分為一組狀態，系統根據PCB 結構中的狀態值控制行程。行程在生命消失前處於且僅處於三種基本狀態之一。

行程的基本狀態有三種：就緒、執行、等待(阻塞)。

1. ==**就緒狀態**==：當行程已分配到除 CPU 以外的所有必要資源後，只要在獲得 CPU，便可立即執行，行程這時的狀態稱為就緒狀態。處於該狀態的行程構成緒列隊。

2. ==**執行狀態**==：行程正在處理器上運行的狀態，該行程已獲得必要的資源，也獲得了處理器，用戶程序正在處理器上運行。

3. ==**等待(阻塞)狀態**==：正在執行的行程由於發生某事件而暫時無法繼續執行時，便放棄處理器而處於暫停狀態，即行程的執行收到阻塞，成為阻塞狀態，也成為等待狀態。






OS 用 multiprogramming 方法得到 CPU 最大使用率，一般 process 一開始都是 CPU Burst，交由 CPU 去處理該 process，接著是 I/O Burst，做 I/O 資料的傳送。在正常的狀況下，process 就在這兩個狀態間一直循環，最後會呼叫一個終止行程執行的 system call 作為行程的結束。

### CPU Scheduler
**Short-term Scheduler**
從記憶體中選出一個已經準備就緒的行程，並且將 CPU 分配給它

CPU scheduling 從在 ready queue 的 process 中挑選 process 進入 CPU 執行。CPU scheduling 選擇的 process 會在以下情況改變

CPU-scheduling decisions may take place under the following four circumstances:
1. When a process switches from the **running state to the waiting state**
2. When a process switches from the **running state to the ready state**
3. When a process switches from the **waiting state to the ready state**
4. When a process **terminates**
### Long-term Scheduler
**Job Scheduler**
從 Spooled (行程池) 中選出行程並且將它們載入記憶體內以便執行
### 中程排班程式
**Medium-term Scheduler**
背後的最主要觀念就是有時可以將行程從記憶體中有效地移開(並且從對 CPU 的競爭中移開)、並減低多元程式規劃的程度(Multiprogramming)
___

## 3. CPU Scheduling 的 preemptive 跟 non-preemptive
:::info
:memo: **Non-preemptive**
> 當一 process 獲得 CPU 後，除非該 process 已經執行完畢，否則不允許被移走。 [color=blue]
> 1. **FIFO(First Come First Serve)**
> 2. ==**SJF(Shortest Job First)**==
> 3. **Priority**
:::

:::info
:memo: **preemptive**
> 當 process 獲得 CPU 後，雖然該 process 尚未執行完畢時，卻允許被移走(離開 CPU) [color=blue]
> 1. **RR(Round Robin)**
> 2. **SRTF(Shortest Remaining Time First)**，為 ==**SJF 的可 preemptive 版本**==
:::
___
## 中斷系統
中斷是指電腦在執行某一程式的過程中，由於電腦系統內、外的某種原因，而必須終止原程式的執行，轉去執行相應的處理程式，待處理結束之後，再回來繼續執行被終止的原程式過程。

::: danger
CPU 接收中斷訊號後會先完成目前正執行中的指令，才會執行中斷指令
:::
### interrupt 發生後，OS 的處理程序
1. 暫停目前 process 的執行，並保存當時執行狀況
2. 根據 interrupt ID 查詢 **interrupt vector**，取出對應的 Interrupt Service Routine( **ISR** ) 起始位址
3. Jump to ISR 的 initial address，執行該 ISR
4. ISR complete
5. OS 恢復原先中斷前的 process 執行

## Interrupt 的種類
- External Interrupt（**外部中斷**）: CPU 外的週邊元件所引起的。（I/O Complete Interrupt, I/O Device error）
- Internal Interrupt（**內部中斷**）:不合法的用法所引起的。（Debug、==Divide-by-zero==、==overflow==）
- Software Interrupt（**軟體中斷**）：使用者程式在執行時，若需要OS 提供服務時，會藉由System Call 來呼叫OS 執行對應的service routine，完成服務請求後，再將結果傳回給使用者程式。

### Programmed I/O
#### **程式 I/O**
當 CPU 與 I/O 要連繫時， CPU 詢問或測試週邊裝置是否備妥(ready)，若尚未則CPU等待(wait)一段時間後，再向週邊裝置測試是否備妥；若備妥，則CPU執行所要 I/O 動作，完畢後再繼續原工作。

:::success
I/O Operation 皆由 CPU 直接控制執行，亦即CPU負責啟動、指揮、中止，因此 CPU 要執行一個程式, 不停的詢問 I/O 模組, 資料好了沒有？是故 CPU 在整個 I/O 過程中, 不曾閒過，這是最浪費 CPU 時間的一種 I/O 作法。
:::
- 優點：
完全軟體方式進行，程式簡單易寫，不需額外硬體，成本低。
- 缺點：
無效率，浪費CPU時間。


### Interrupt I/O
#### **中斷 I/O**
CPU 執行原工作，若週邊裝置有需求，則==發出中斷信號==通知 CPU ，待 CPU 知道後，暫停目前工作(依中斷信號種類，CPU可以不理會，請看下節說明)，對週邊發出中斷認可(INTA)，並依中斷來源種類，跳至中斷服務常式(Interrupt Service Routine，ISR)執行 I/O 動作，完畢後， CPU 再繼續原工作。

- 優點：
1. 有效率，CPU執行原工作，只有週邊有需求時，才對週邊服務。
2. 能做即時控制。
- 缺點：
1. 需額外電路來處理多週邊同時需求。
2. 程式複雜度與成本較高。


### DMA(Direct Memory Access)
#### **直接記憶體存取**
第一與第二種方式，須藉助 CPU 介入彼此間連繫。所謂 DMA，即允許週邊與記憶體兩者直接傳送，不必 CPU介入，完全交給DMA控制器處理。

- 優點：
資料傳送速度快，一般用在大量資料傳送，如磁碟機與記憶體或記憶體與記憶體之間。

- 缺點：
1. 需額外電路、成本高。
2. 程式規劃複雜。
___
## 有向圖
### 強連通,弱連通
在有向圖當中，必須考慮方向，區分兩種情況：
兩點之間
- 雙向皆有路可通，就是「強連通 Strongly Connected 」
- 至少單向有路可通（有可能雙向都通），就是「弱連通 Weakly Connected 」。

### 連通分量
Connected Component
譯作「連通分量」、「連通成分」、「連通元件」、「連通單元」等等，也有人簡稱為「分量」，沒有正式翻譯。

當一張無向圖不連通、分隔成幾個區塊的時候，每一個區塊都是一個「連通分量」。一個獨立的點也是一個連通分量。

一張無向圖的連通分量們，不可能互相重疊。一個連通分量是指在連通的情況下，點數盡量最多、擴展範圍最大的一個子圖；因此，從一個連通分量當中，切下一小塊仍舊連通的子圖，並不能叫做連通分量。


### 強連通分量
Strongly Connected Component
一張有向圖的「強連通分量」，是所有兩點之間，==雙向==皆有路可通的連通分量。一張有向圖的強連通分量們，不可能互相重疊。

兩個點來回都有路徑，這兩條路徑勢必形成一只有向環。一個強連通分量，想必是由很多有向環交疊而成的。


### 弱連通分量
Weakly Connected Component
一張有向圖的「弱連通分量」，是所有兩點之間，==至少單向==有路可通的連通分量。一張有向圖的弱連通分量們，通常會互相重疊。

一個弱連通分量，可以看作是強連通分量的縮圖當中的一條有向路徑。要找最大的弱連通分量，即是縮圖當中，涵蓋最多原點的一條有向路徑。


___
___