# 每天登入看一次
1. onto公式
1. onto(5,3)(3 0)5^3 - (3 1)5^2 + (3 2)5^1 -(3 3)5^0
2. 不同分不同
3. 不同分相同再 / n!
3. homogeneous 虛根
1. https://web.math.sinica.edu.tw/math_media/d341/34104.pdf
2. 總之先轉成 a+bi a-bi
3. p是 sqrt(a^2 + b^2)
4. theta 是 tan^-1(b/a)
5. 通解= <font color="red">p^n *(C0*(cos(n * theta)) + C1*(sin(n * theta)))</font>
5. generating function
1. 頭痛
2. 要記一些常見GF
3. 1/1-x = 1 -> 1 x x^2...
4.
4. IEEE754 特殊表示 全0 全1
1. 2^128 全1 mantissa0 是 無限 負無限
2. 全1mantissa有值 是 NAN
3. 全0是0 就是去掉mantissa的leading one
4. 非general能表示超過
5. IEEE754 正負範圍 因為被全 0 1 bound住 general範圍是在 -126 ~ 127
6. 為啥對其大的 因為小的那邊可依ROUND 掉
5. big little endian 在mips是32位元 所以一次要看兩個16進為符號
1. 1A2B3C4D
2. 4D3C2B1A
3. 
6. 
1. 只有regdst跟memtoreg有 dont care
2. Rtype memreg是0 因為不會從mem裡面拿值
3. <font color=red>RegDst要背 R是1 (拿I值得都是0)LW,ITYPE是0</font>
4. 試著用rtype要兩個REG回憶
5. <font color=red>Rtype 的 ALUop是10 BEQ是01 其他是00 沒有11 </font>
6. signExtension
7. 注意PC+4 他在搞(不管由沒有branch都會+4)
8. 
7. partial order
8. <font color="red">忘卻的記憶 vector角度 cos^-1( a。b / |a||b| )</font>
9. PDP^-1 的P 是orthogonal matrix
10. positive defined positive semi define
1. 正定矩陣
1. n*n 特徵值皆為正
11. deadlock 條件
1. mutual exclusion
2. circular waiting
3. hold and wait
4. non preempt
12. critical section
1. mutual exclusion
2. bound waiting
3. progress
13. race condition兩個解法
1. 直接幹掉inturrupt disable
1. 防preempt
3. critical section
1. spinlock(busy waiting)不適用於單核
2. 層級
1. monitor
2. semaphere
3. disable inturrupt
4. (hardware instruction support)test-set swap(兩個功能差不多)
3. bakery 如果拿到一樣的號碼 就看PID小的 因維PID唯一所以mutual exclusion
14. 酷酷知識 typedef 是 declartion不是definition
15. OS
1. L1 cache
1. write through write back 皆可
2. 注重 hit time

2. L2
1. write back
2. 注重 hit rate
16. virtual mem
block->page
cache miss -> page fault
設計原理
1. 避免IO
1. fully
2. write back
17. pageTable cache TLB不可能的情況
1. 只有三個不可能的情況
2. pageTable miss 但是前面兩個有hit 看圖就懂
3. 流程是CPU的虛擬位址去TLB找到實體位址 再去CACHE看在不在
4. TLB MISS就知道不會在cache直接看PT
5. 有在PT就更新
6. 
18. 屬於問題
1. A∈B 代表A" 元素 " 在B" 集合 "裡面
2. A⊆B 代表A" 集合 " 在B" 集合 "裡面
3. A⊂B 代表A" 集合 " 在B" 集合 "裡面 且A!=B
19. euler path (edge)
1. 條件 "A connected graph has an Eulerian path if and only if it has at most two vertices with an odd degree."
2. euler trail : 起點終點不相同
3. 起終點相同叫做 circuit
20. hanmiliton cycle(vertex)
1. 沒特殊條件
2. NPC
21. planner
1. V-E+R=2 背
2. E<3V-6 從3點數往上推 +
22. two colorable就是bipartite
23. Cycle Wheel Qube K
24. 有明確true false 才是命題 PROPOSITION
25. 要吃變數叫 PREDICATE
26.
1. partial order
1. antisymmetric
2. transitive
3. reflexive
3. total orer
1. partial order
2. 任兩元素有可比性
3. (a,b)(b,a) 都是否就不算
27. hasse diagram
1. 去除 反身 遞移 方向性
28. minmax heap -> 90.
29. fabonaccci
30. SMMH
31. in place sorting
1. sort 不吃額外空間
2. 跟我理解差不多 merge radix ccounting不是
32. failure funtion KMP 可以比對從頭開始的重複字串
1. 子字串每一個failure function傳的值就是跟前面相比最長的子字串
2. 第一次出現的字符必定為0 (有0跟-1 開始的 0比較好理解)
3. failure function 代表的是子字串可以少比對多少個
4. 比對
33. jordan normal form
1. 多次的地方記得頭上放1 解決eigenvector不夠用的時候沒有eigenvalue當similar matrix
35. accounting method finding artomiszed
36. 
37. 真假
38. similar是 Evalue依樣 Evector不一樣
39. define as inner product看一下
40. tag index offset
1. offset是指一個BLOCK的偏移量有幾個BYTE(1 WORD 4 BYTE)
2. index是指 CACHE有幾個BLOCK
3. tag是用來對答案看有沒有HIT
41. equivalence relation
1. reflexive symmetric transitive
42. partial order
1. reflexive antisymmetric transitive
43. hermitian matrix
1. 共扼後 叫A*
2. A*=A 就是 hermitain matrix
3. 如果element是實數保持不變
4. 如果element是a+bi 會變 a-bi
5. 所以symmetric matrix的element都是real就 一定是hermitian matrix
44. 常見演算法 時間複雜度推倒
1. DFS BFS
1. adj matrix 都是n^2
1. 因為要全跑
2. adj list 都是(E+V)
1. 因為不知道E大還是V大
2. 但都會被這兩個條件影響
2. MST
1. kruskal ElogE
1. 排序邊長 一個一個取(E)
2. 所以是排序的下限
3. prim ElogV 我毫無頭緒
1. 用priority queue(heap)實作
2. 以點為權重
5. solin
6. 不長考 但跟prim依樣就好
7. <font color="red">超級注意 用adj matrix 做就是V^2 </font>
3. shortest path
1. dijkstra
1. E+VlogV heap
2. 不可有 負邊 負環
3. bellmen ford
1. matrix是O(V^3)
2. list O(VE)
3. 不可有負環
5. floyd washer
1. 一定要用matrix O(V^3)
2. 不可有負環
4. 排序 其他太基礎
1. radix sort
1. time: O(d*(n+r))
2. space: O(n*r)
3. bucket sort
1. time: O(n+k)
2. space: O(n*r)
4. counting sort
1. time: O(n+k)
2. space: O(n+k)
5. stablility
1. insertion從左到右 一定stable
2. selection 會把前面的元素swap到後面所以unstable
3. merge stable bubble stable
45. symmetric asymmetric antisymmetric 個數
1. symmetric 可選((n*(n+1))/2)
1. (a,b)為1 (b,a)必為1
3. Asymmetric (anti Symmetric的子集合)
1. (a,b)為1 (b,a)必為0
1. 對角必為0
2. 可選((n*(n-1))/2)
3. 用2*2去想一個點可以有幾個選擇
4. Antisymmetric
1. 對角自選 2^n
2. 可選((n*(n-1))/2) 同上
3. 呼之欲出
46. 我根本沒記強連通弱連通
2. 強 : 任兩點AB一定有A>B 跟B>A
3. 弱 : 轉成無向圖後 整個圖是連接的 (無向圖 A可到B B可到A)
47. similar matrix 有依樣的eigen
1. A=P B P^-1
2. Ax=Ex (E是特徵值)
3. P B P^-1 x = Ex
4. B P^-1 x =P^-1 Ex (E是純量提出去)
5. B (P^-1 x) =E (P^-1 x)
6. 特徵值相同 特徵向量不同
48. one to one 且 onto才會有inverse
49. (大)partial total well(小)
50. 0也可以C 就是0 因為被除數變0
51. 所有矩陣都可拆成symmetric+skew symmetric
1. A =1/2(A+A^T) + 1/2(A-A^T)
52. cache inclustion
1. 如果cache miss , enviction from L1 to memory 就會搬動很多東西
1. inclusive :
1. L2包含L1 往下包函 這樣就會就不用往上修改 但是能存的東西變少
2. 
2. exclusive :
1. 不屌 先放L1 L1不夠裝 裝L2
2. L1拔掉(envict) 就往L2裝
3. 
4. 慢 但是能裝的東西變多
3. N

E(none inclusive none exclusive)
1. 高層出現底層要出現 移除就是你家的事
2. 
53. 
54. replacment 去看 轉成tag index offset
55. tag hit index hit才cache hit
56. tag miss index hit block replace
55. forwarding 4 情況
1. mem/wb.rd= id/exe.rs
2. exe/mem.rd = id/exe.rs
3. mem/wb.rd= id/exe.rt
4. exe/mem.rd = id/exe.rt
5. <font color="red">注意 有forwarding的load-use 1Stall 沒有的都是兩stall</font>
56. 
57. 
58. 
59. 
60. 
61. 自訂義 DP 0/1
1. 重點就是 把新物體放進去 每一動都比較
2. DP[i-1][j](頭上沒放自己的時候的最佳解)
3. V + DP[i-1][j-W](自己放進去 + 扣掉自己權重的最佳解)
4. 就知道要不要放進去
63. LICS(LCS 變形)
1. 一定要increasing 那就先排序
64. DP解 max chain
1. 根本窮舉
2. N^3 每一次確定一個矩陣的值 都要N^2的檢查
3. 邊放矩陣長度 N^2的上三角矩陣
65. edmond KARP
1. O(VE^2) 直接背ㄅ
2. ford fuckson 被流 bound 是 O(f*E)
66. 費馬小 費馬小推廣
1. a^p-1=1 mod p where p is prime
2. a^互質個數(p) = 1 mod p p is not prime
3. 背第二個 可以推第一個
37. relation
1. relation個數 2^(m*n)
2. irreflexive 不是 not reflexive 是(i,i)必為0
3. asymmetric 對角必為0 anti 對角可自選
4. 個數 想一下 很酷 底是3 anti多乘對角
5. :::spoiler
symmetric 2 ^(n(n+1/2))
aSymmetric 3^(n(n-1)/2) 想一下一個element的可能性
antiSymmetric 2^n * 3^(n(n-1)/2) 多一個對角
:::
6. (1,2,3) 的 ER 個數就是8 就是全關係
68. 6人中 一定有3人彼此認識或彼此不認識
1. 從其中一人角度去想
2. 三角形很重要
3. 畫圖出來就有答案
69. 
70. DM not ALL 先判斷ALL再NOT
71. 任何矩陣都可以由 symmetric + asymmetric組成
72. 微分會保純量積跟加法
73. linear transform V->W 0向量 一定project到0向量
1. 
74. 費伯納西撒取 跟百諾米歐撒取 該認真地看一下了
1. 費伯納西
75. e04 orthogonal set裡面有0阿 不會LI阿阿阿阿阿
76. cycle decomposition
1. (1,2,3,4,5,6,7,8)
2. (2,6,5,8,3,1,7,4)
3. 那就是1 2 6 一組 3 5 一組 7一組 4 8 一組
4. 尼瑪
77. peak不只一個 所以一直往高處爬(看左右鄰居) 一定能找到peak
78. reweight graph
1. 用bellmanford找每一個點的最小值
2. edge(a to b)=origin(a to b)+bell(a)-bell(b)
3. 這樣負邊就不見了
79. 靠邀 heapify 跟maxheapify不一樣
1. heapify 建構整個heap O(N)
2. maxheapify 調整maxheap有錯的地方 O(LOGN)
30. <font color="red">in place sorting 第二次</font>
1. sort 不吃額外空間
2. 跟我理解差不多 merge radix ccounting不是
81. kmp 人名組成 先FAILURE FUNCTION
1. FAILURE 0開頭 依樣就塞1
2. AABAABABBA
3. 0101231001
2. 每一次比對失敗就ROLLBACK回failure function的數字
82. https://medium.com/algorithm-solving/johnsons-algorithm-c461506fccae
83. 救命
83. e04 best fit 沒internal frag
1. 相對其他方法不太有了
84. set A/B =A-(A and B)
85. 1 2 3 4 的GF 是 微分 1/1-x 微分 1/(1-x)^2
1. 再來都是國小運算
86. 靠邀阿 adj 是砍轉置的位置 A12 是 砍A21
87. QR fraction 是M*n 矩陣 M>=n (操)
88. EULER PATH 跟CIRCUIT 條件不一樣
1. PATH : ODD DEGREE 要是2以下
2. CIRCUIT : 全部DEGREE 要是EVEN
89. multi adjcent list
1. 會給沒用的邊 要看一開始的指向
2. 邊的標記|連到的V1 | 連到的V2 | 指標指向下一個有用到V1 | 指標指向下一個有用到V1
90. min max heap (level)
1. 刪除依樣 把最後一個節點塞進ROOT
2. 一次跳兩層 因為下一個最小一定在GRAND LEVEL
3. 若違反就慢慢推回去
91. DEAP
1. 左min右max
2. 左[i]<右[i]
3. DELETE的時候
1. 先刪除MIN 或MAX
2. 重新建立MIN HEAP或 MAX HEAP
3. 比對左右大小關係 若右邊的NODE是NULL 就跟NULL的PARENT比較
92. 234 deletion
1. 刪子節點
1. 沒變空 結束
2. 變空 跳第三個
2. 刪內部節點
1. 跟inorder下一序列戶換 再刪除
2. 檢查第三點
3. 刪完為空 (抓inorder的下一個序列)
93. virtual -> physical translation
94. DMA 流程圖
95. fully direct
1. 就是在一樣大小的CACHE裡面
2. fully 不管 就是塞
3. DIRECT就是對應
4. TWO WAY就是對應到的地方有兩個位置可以放
5. 舉例CACHE SIZE 是4
6. 0 1 2 4塞進去 LRU
1. direct : 0 | 4 | 2 | X
2. two way : 2 4 | 1 X
3. FULLY : | 0 1 2 4 |
96. one to one 且 onto 就是 equivalance 也是那三個特性
97. 坐一圈 先想N! 然後想想怎樣會判定依樣
1. 當作成一圈ABCD BCDA CDAB DABC 會變一樣的
2. 所以組合數要除以n
3. 所以答案是n!/n = (n-1)!
98. 反證 換植換為 https://yungchiehhsieh.wordpress.com/2016/08/20/contadiction%E5%92%8Ccontaposition%E7%9A%84%E4%B8%8D%E5%90%8C/
99. DP總整理
1. 最小成本編輯 I(insert)R(replace)D(deletion) 0 45 90 魔術
1. 看了一小 真的小沒想法
2. 矩陣乘乘
1. 接近窮舉了O(n^3)
3. 最佳二元搜索

4. LCS
1. 一樣取斜上+1
2. 不一樣取 上面左邊 大的
5. 0/1 knapsack
1. 拿(dp[i-1][w-arr[i]]+arr[i])或不拿(dp[i-1][w])
2. O(nW)時複
3. pesudo polnomial 實際上是NPC問題
6. subsset sum
1. 0/1 同類型的替身
7. floyd washer
1. O(N^3)
2. j->n i->n k->n
dist[i][k]=min(dist[i][j]+dist[j][k],dist[i][k])
3. 注意要改變的是裡面兩層就好
8. matrix chaining
1. 自殺 再問自殺
9. optimal binary search tree
1. 跟上面很像 回家看懂記得回來
99. SOP POS sum of product
1. sum of product就是加一個 NOT
2. 記得是0 所以最後要倒過來
3. DEMORGAN
100. memory lantancy hiding
101. 判斷connected 關節點
1. 網址 : https://sites.google.com/view/zsgititit/home/jin-jiec-cheng-shi-she-ji-2/tu-xing-yan-suan-fa-guan-jie-dian-articulation-point
103. orthogonal QT=Q-1
104. 假設在一個R4空間的GRAM SCAMDIT沒辦法SPAN R4
1. 假設 一個向量 A
2. A內積其他向量為0
3. 推出A
4. EX : A=(x,w,y,z) 有另外三個向量(不足以SPAN R4)
5. 內基三者可以得到無窮解 用columnspace法 求出span
105. pesudo graph
106. 11
106. 白癡 addr就是memory的大小
1. 對應到cache 就是index+offset
2. cache大小就是2^ index+offset
107. 0不是EV
108. UMA CPU 幹同一個MEM
109. EXTEND MM 如果 f(n)/log^2以上就丟掉logn
110. full rank > one LeastSquareError otherwise infinite
111. Kadane’s Algorithm
112. 找最長的MAXSUBARRAY
1. 本質上就是A[i+1]的最大包含A[i]
2. https://www.shubo.io/maximum-subarray-problem-kadane-algorithm/
3. 所以寫成二為 取(上面) 不取跟取誰大(下面)
112. BEQ事跳到 PC + 4 + 4*offset
113. min cut 就是S可到 S不可到(在流完的residual graph裡)
114. https://zh.wikipedia.org/zh-tw/%E5%93%A5%E5%BE%B7%E5%B7%B4%E8%B5%AB%E7%8C%9C%E6%83%B3
115. https://medium.com/algorithm-solving/johnsons-algorithm-c461506fccae
115. JOHNSON ALGO
116. ! [image](https://hackmd.io/_uploads/SkIY3piFT.png)
117. 

115. transform basis from a to b
116. 有啥問題
117. A(basis)*X(A prev) = B(basis)*X(B prev) [在不同觀點下看同一個vector x]
118. 那麼 X(A prev) = A(basis)^-1 * B(basis)*X(B prev)
119. 所以A(basis)^-1 * B(basis)乘上X(B prev) 就會是 X(A prev)
120. 那麼A(basis)^-1 * B(basis) 就是transform X(B prev) 到 X(A prev)
1. -1比較機車 便那邊
2. 
2. 矻矻數學證明
3. 
3. LU 可以轉LDU 再轉LL^T
4. 
4. DET 酷酷證明
5. 
5. 
6. 
7. 
8. 
9. 
10. 
11. 
1. 多做
12. 
1. 
2. 
3. 矩陣正交可以用快速投影
4. 
4. 沒有足夠的SPAN 也要用快速投影
5. 但要記得 要現做GRAM SCAMDIT讓他們正交
4. definite 定義是 symmetric
5. positive 或negative 取決於他是EValue全正或全負
5. house holding 找reflexive
1. tansition matrix of space A
2. find orthogonal complement of　A
3. T = I- 2 / (A^T*A) * (A*A^T)
4. T(input) = 反射reflexive對應位置
### OS
2. 
3. 
4. ![image](https://hackmd.io/_uploads/H1bIwAQcT.png
5. 
6. 
7. 
8. 

### 演算
1. 
2. 
3. quicksort average analize
4. 
4. 
5. LCS 一樣左上+1 不一樣 左邊,上面大的
6. OBST(沒失敗點的版本) 
7. failure node's weight is equal to the connect node
8. 
9. 
10. 
11. 總之failure 要先算
12. failure = 上一行 + Ni + Fi
13. 第一行就是抄failure 進去 C 不算
12. 
1. R 是用來建樹 R的值就是ROOT的值
8. BST數量 (2n,n)/n+1