---
# System prepended metadata

title: 考研筆記

---

1.回去看線性映射那邊的座標轉換,矩陣表示。
2.associative在數學是結合性。
3.multiple issue由軟體(compiler)處理稱為static multiple issue，由硬體處理稱為dynamic multiple issue，又稱superscalar。
  最核心的技術是dynamic pipeline scheduling - 選擇下一群要執行的指令並將這些指令重新排序，由於硬體資源足夠多，因此pipeline幾乎不會stall。分為3個主要步驟
     1.in-order issue - 照comiler排定指令的順序，抓指令、解碼指令、抓暫存器。
     2.out-of-order execute - 丟到buffer稱為reservation station，等(“預約”)功能單元的使用權或是等與別的指令產生data dependency的指令forward給該指令。
     3.in-order commit - 會先把運算結果存在reorder buffer，再按照原本資料流的順序提交，寫回暫存器或是記憶體。
4.static multiple issue有MIPS-64,VLIW,IA-64。
5.big-endian:從最高位元開始存資料;little-endian:從最小位元開始存資料。
6.jr是R type。
7.單精度float為1,8,23;倍精度為1,11,52。
8.RAW是True-dependence

---

# 演算法:
## 時間複雜度
![IMG20240120125051](https://hackmd.io/_uploads/rJjp4Adta.jpg)

## Divide and conquer
### 一，merge sort

### 二，matrix multiplication
1.Strassen`s method :用來加速矩陣乘法運算，時間複雜度為n的2.81次方

### 三，The selection problem
![556443](https://hackmd.io/_uploads/r1vKf1Kt6.jpg)

O(n)

### 四，The closest pair problem![rn_image_picker_lib_temp_c9a4bbd7-e061-490b-bea0-9ecc35a85d22](https://hackmd.io/_uploads/SkYxrkYtp.jpg)

O(nlogn)

## Greedy

###  一，kruskal,Prim,sollin 最小生成樹
1.因Kruskal因要從最小開始找，則一定要排序!!時間為O(ElogE)==O(ElogV)
2.Prim會有特定點開始找，用BFS方式去找，時間為O(n)
* Note:判斷是否形成cycle:
if find(u) != find(v) {
  add edge(u,v) to S
  Union(u,v)
else give up edge(u,v)
}


### 二，Max flow(Ford-Fulkerson)
![IMG20240120145934](https://hackmd.io/_uploads/B1TIGgYFT.jpg)
時間為O(fE)  *f為最大流量


### 三，Dijkstra
1.不能處理負邊
![IMG20240120153203](https://hackmd.io/_uploads/HyqnDgtKa.jpg)



###  四，Huffman tree
1.就是小的加起來然後建成霍夫曼樹，編碼即可。

###  五，fractional Knapsack(背包問題)
1.先算CP值=>O(n)
2.再將這些CP值做排序=>O(nlogn)
3.取道達到負重獲取光為止=>O(n)
時間為:O(nlogn)

## DP
### 一。rod cutting
![IMG20240120231203](https://hackmd.io/_uploads/r1uHmDttp.jpg)

### 二。Knapsack0-1(背包問題)
![IMG20240120231442](https://hackmd.io/_uploads/SJK8SPFFT.jpg)
###  三。Matrix-chain multiplication
![rn_image_picker_lib_temp_02718529-e6b2-4945-837a-fb9675b3394f](https://hackmd.io/_uploads/Bysg6PFFT.jpg)




## 圖論

### BFS


### DFS
1.u.d是開始時間(discovery time)，u.f是完成時間(finish time)
![rn_image_picker_lib_temp_6c7cb587-7dc0-4cdb-8475-a9be54e3f880](https://hackmd.io/_uploads/SyAcaZtFT.jpg)


![rn_image_picker_lib_temp_90eaa373-7d0f-47cc-95a9-e339a7f6adb4](https://hackmd.io/_uploads/ryyBebYYp.jpg)
![IMG20240120161952](https://hackmd.io/_uploads/SJ0fVZYFp.jpg)
![IMG20240120162025](https://hackmd.io/_uploads/r146NbKKp.jpg)


### topological-sort
用DFS找，也可藉由拓譜找SCC

### Dijkstra,Bellman-Ford,Floyd-Warshall
1.Dijkstra:不能處理負邊，性質是Greedy
![IMG20240120153203](https://hackmd.io/_uploads/HyqnDgtKa.jpg)
2.Bellman-Ford:可以處理負邊，資結版本是O(V的三次方)，演算法版本是O(VE)
3.Floyd-Warshall可以處理負邊，時間為O(V的三次方)
