# 演算法筆記 [TOC] ## [github連結](https://github.com/ccc112a/py2cs) ## 第一週 演算法+資料結構=程式 [bubble sort程式](https://github.com/ccc112a/py2cs/blob/master/02-%E6%BC%94%E7%AE%97%E6%B3%95/01-%E8%A4%87%E9%9B%9C%E5%BA%A6/01-bigO/bubbleSort.py):Big-O(n^2^) [distance程式](https://github.com/ccc112a/py2cs/blob/master/02-%E6%BC%94%E7%AE%97%E6%B3%95/01-%E8%A4%87%E9%9B%9C%E5%BA%A6/01-bigO/distance.py):Big-O(1) [matrixMul程式](https://github.com/ccc112a/py2cs/blob/master/02-%E6%BC%94%E7%AE%97%E6%B3%95/01-%E8%A4%87%E9%9B%9C%E5%BA%A6/01-bigO/matrixMul.py):Big-O(n^3^) * 矩陣分割之後可以只有O(n^2.71^),最近有AI突破了 但我查到最少的是O(n^2.3728596),[連結](https://www.qbitai.com/2021/03/22553.html) 嚴格定義:是算法才能有big-O,(不會停的東西不是算法) [infinite](https://github.com/ccc112a/py2cs/blob/master/02-%E6%BC%94%E7%AE%97%E6%B3%95/01-%E8%A4%87%E9%9B%9C%E5%BA%A6/01-bigO/infinite.py):嚴格定義下沒有big-O,寬鬆定義是big-O(∞) 圖靈停止問題:無法用一個程式判斷另一個程式會不會停,就算寫了也無法100%正確 Kurt Gödel(庫爾特·哥德爾):最早用數學領域提出不可判定停止問題 * 哥德爾完備定理:看不太懂,[定理連結](https://zh.wikipedia.org/zh-tw/%E5%93%A5%E5%BE%B7%E5%B0%94%E5%AE%8C%E5%A4%87%E6%80%A7%E5%AE%9A%E7%90%86) * 哥德爾不完備定理:看不太懂,[定理連結](https://zh.wikipedia.org/zh-tw/%E5%93%A5%E5%BE%B7%E5%B0%94%E4%B8%8D%E5%AE%8C%E5%A4%87%E5%AE%9A%E7%90%86) 2^n^,10^n^在演算法的角度沒有差別 常數不為0多小都沒關係 算法指的是方法,所以不受限於程式語言,但要具體的表明輸入輸出,步驟等等 多**層**迴圈的big-O是O(n^2^) 多**個**迴圈的big-O是O(n) 自己寫遞迴要小心重複算的問題 log n比根號好 費氏數列用遞迴會重算很多重複的,可以用動態規劃,查表法加快 [查表法費氏數列](https://github.com/ccc112a/py2cs/blob/master/02-%E6%BC%94%E7%AE%97%E6%B3%95/02-%E6%96%B9%E6%B3%95/01-%E6%9F%A5%E8%A1%A8%E6%B3%95/fiboanacci/fibonacci_lookup.py):用表記下已經算過的數字 動態規劃:有系統的建表 ### 習題 1. 費氏數列迴圈法 2. 寫出四種算出2^n^的方法 ## 第二周 遞迴轉迴圈很困難 透過遞迴的方式能處理很多迴圈難做的程式 Lisp:沒有迴圈的程式語言,函數程式語言 haskell:函數式程式語言 雜湊不能回推,會碰撞,無法做逆向工程 雜湊在密碼學上很重要 sha256是位數固定的雜湊 ,碰撞機率低,[sha程式](https://github.com/ccc112a/py2cs/blob/master/02-%E6%BC%94%E7%AE%97%E6%B3%95/02-%E6%96%B9%E6%B3%95/02b-%E9%9B%9C%E6%B9%8A%E6%B3%95/sha/hash.py) 大約2^128^會第一次碰撞 能夠列舉才能暴力法 挖礦是暴力法,靠雜湊值 挖礦是一種猜數字遊戲,主要看雜湊前導0,現在是18個0 挖礦跟協助維護比特幣系統都可以得到比特幣 乙太幣有智能合約,能在區塊鏈上跑程式 ### 習題 1. 寫一個可以列舉排列的程式 ## 第三周 暴力法:全面且大量的搜尋 系統式暴力:不會重複,照順序(效能好的一定比較快) 隨機式暴力:會重複,隨機嘗試(不看效能,看運氣) IEEE(Institute of Electrical and Electronics Engineers):電機電子工程師學會 ACM(Association for Computing Machinery):電腦協會 [IEEE754](https://zh.wikipedia.org/zh-tw/IEEE_754):浮點數標準 判斷浮點數不要用等於,因為會有微小誤差 暴力法怕:高維函數,多變數函數 [蝴蝶效應](https://zh.wikipedia.org/zh-tw/%E8%9D%B4%E8%9D%B6%E6%95%88%E5%BA%94):微小的事物會帶來巨大的改變 迭代有可能混沌,收斂,發散,震盪 後兩節課都在寫習題,所以無筆記 ### 習題 1. 求解x^2^-x+1=0(迭代法3種+暴力法) ## 第四周 [巴斯卡三角形](https://zh.wikipedia.org/zh-tw/%E6%9D%A8%E8%BE%89%E4%B8%89%E8%A7%92%E5%BD%A2):每一個數都是左上跟右上兩個數字的合 [歐基里德算法](https://zh.wikipedia.org/zh-tw/%E8%BC%BE%E8%BD%89%E7%9B%B8%E9%99%A4%E6%B3%95):用來算最大公因數 [student t-test](https://zh.wikipedia.org/zh-tw/%E5%8F%B8%E5%BE%92%E9%A0%93t%E6%AA%A2%E5%AE%9A):統計學的重要東西 AI和機器學習會用到很多很難的機率統計 平行指令:在同一行做兩件事,例如 `x,y = y , x%y` 生成語法本身就是一種遞迴 [leetcode](https://leetcode.com/):要面試厲害公司可以刷,很難,老師講的easy的題目就聽不懂解法了 呼叫函式時要先算出參數,要小心這個機制 [哈斯凱爾·布魯克·柯里(Haskell Brooks Curry)](https://zh.wikipedia.org/zh-tw/%E5%93%88%E6%96%AF%E5%87%AF%E5%B0%94%C2%B7%E6%9F%AF%E9%87%8C):函數式編程的始祖 #### python語法: lambda:一種匿名函數的創建方式,且是底層的 map:回傳經過處理的所有數字 filter:回傳滿足條件的選項 reduce:回傳一個累加的結果 ,(用reduce 需 from functools import reduce) [參考程式碼](https://github.com/ccc112a/py2cs/blob/master/02-%E6%BC%94%E7%AE%97%E6%B3%95/02-%E6%96%B9%E6%B3%95/04b-%E5%87%BD%E6%95%B8%E5%BC%8F%E7%B7%A8%E7%A8%8B/01-fp/fp.py) ## 第五周 combinator: 聽不懂,有點複雜,[介紹網址](https://medium.com/@adambene/fixed-point-combinators-in-javascript-c214c15ff2f6) [u combinator程式碼](https://github.com/ccc112a/py2cs/blob/master/02-%E6%BC%94%E7%AE%97%E6%B3%95/02-%E6%96%B9%E6%B3%95/04b-%E5%87%BD%E6%95%B8%E5%BC%8F%E7%B7%A8%E7%A8%8B/07-combinator/ucombinator1.py), [y combinator程式碼](https://github.com/ccc112a/py2cs/blob/master/02-%E6%BC%94%E7%AE%97%E6%B3%95/02-%E6%96%B9%E6%B3%95/04b-%E5%87%BD%E6%95%B8%E5%BC%8F%E7%B7%A8%E7%A8%8B/07-combinator/ycombinator1.py) ,[z combinator程式碼](https://github.com/ccc112a/py2cs/blob/master/02-%E6%BC%94%E7%AE%97%E6%B3%95/02-%E6%96%B9%E6%B3%95/04b-%E5%87%BD%E6%95%B8%E5%BC%8F%E7%B7%A8%E7%A8%8B/07-combinator/zcombinator1.py) [lambda calculus](https://zh.wikipedia.org/wiki/%CE%9B%E6%BC%94%E7%AE%97) 沒有資料結構,所以都是用pair(需自己寫),[pair程式碼](https://github.com/ccc112a/py2cs/blob/master/02-%E6%BC%94%E7%AE%97%E6%B3%95/02-%E6%96%B9%E6%B3%95/04b-%E5%87%BD%E6%95%B8%E5%BC%8F%E7%B7%A8%E7%A8%8B/08-list/pair.py) [Alonzo Curch](https://en.wikipedia.org/wiki/Alonzo_Church):用另一個面向證明圖靈停止定理,時間比圖靈早[證明的paper](https://ics.uci.edu/~lopes/teaching/inf212W12/readings/church.pdf) [皮亞諾公理系統](https://zh.wikipedia.org/zh-tw/%E7%9A%AE%E4%BA%9A%E8%AF%BA%E5%85%AC%E7%90%86) [希爾伯特23個問題](https://zh.wikipedia.org/zh-tw/%E5%B8%8C%E5%B0%94%E4%BC%AF%E7%89%B9%E7%9A%8423%E4%B8%AA%E9%97%AE%E9%A2%98) [Microsoft Bing](https://www.bing.com/create):用文字生成圖片 多人處理,並回推github專案時不要用 -A 參數,因為會增加很多垃圾 多人合作時要善用branch 檢查存不存在,不存在的話創建新的branch指令:git checkout -b 要創建的名字 通常測試不會用print,會有assert 測試很重要,通常會有專門的測試工程師 ## 第六周 可以用算分數的方式決定排序的正確與否 AI=優先=算分數+搜尋 現在AI主要用用梯度下降法 牛頓,萊布尼茲發明微積分,現在都採用萊布尼茲符號 [梯度下降法](https://zh.wikipedia.org/zh-tw/%E6%A2%AF%E5%BA%A6%E4%B8%8B%E9%99%8D%E6%B3%95):可以找到局部最低和最高點 評分在AI裡非常重要 爬山演算法:若右比左高,往右,左比右高就往左,找到的不一定是全圖最高點 用爬山演算法算最大值時只需在return時加負號,[一維程式碼(已加負號)](https://github.com/ccc112a/py2cs/blob/master/02-%E6%BC%94%E7%AE%97%E6%B3%95/02-%E6%96%B9%E6%B3%95/05c-%E7%88%AC%E5%B1%B1%E6%BC%94%E7%AE%97%E6%B3%95/hillClimbing1/hillClimbing1.py) ### 習題 1. 寫一個爬山演算法,能算出任何函數的山頂 2. (紅利題)寫一個梯度下降法,能找到任何向量函數的谷底 ## 第七周 用梯度下降法找的都會是有最小值的(不然會找到負無限大) 梯度計算,好難,聽不太懂,[程式碼](https://github.com/ccc112a/py2cs/blob/master/02-%E6%BC%94%E7%AE%97%E6%B3%95/02-%E6%96%B9%E6%B3%95/05f-%E6%A2%AF%E5%BA%A6%E4%B8%8B%E9%99%8D%E6%B3%95/02-%E6%A2%AF%E5%BA%A6/xyGradient.py) 高維的連續可維函數可以做偏微分 [梯度下降程式碼](https://github.com/ccc112a/py2cs/blob/master/02-%E6%BC%94%E7%AE%97%E6%B3%95/02-%E6%96%B9%E6%B3%95/05f-%E6%A2%AF%E5%BA%A6%E4%B8%8B%E9%99%8D%E6%B3%95/03-%E6%A2%AF%E5%BA%A6%E4%B8%8B%E9%99%8D%E6%B3%95/gd.py) [反傳遞演算法](https://zh.wikipedia.org/wiki/%E5%8F%8D%E5%90%91%E4%BC%A0%E6%92%AD%E7%AE%97%E6%B3%95):常應用於神經網路 輸入值不需要再算偏微分 [反傳遞文章參考](https://karpathy.github.io/neuralnets/) [反傳遞程式碼](https://github.com/ccc-py/micrograd/blob/master/ccc/engine.py) [向量資料庫](https://aws.amazon.com/tw/what-is/vector-databases/):可以儲存較久的記憶 ### 習題 1. 把習題6改用 micrograd 的反傳遞算法算梯度 ## 第八周 [模擬退火法](https://zh.wikipedia.org/wiki/%E6%A8%A1%E6%8B%9F%E9%80%80%E7%81%AB):爬山演算法的變形,可以跨越小山丘(但必須是非常非常小的山丘) [貪婪演算法](https://zh.wikipedia.org/zh-tw/%E8%B4%AA%E5%BF%83%E7%AE%97%E6%B3%95):每次都朝進步最多的地方走 [霍夫曼編碼](https://zh.wikipedia.org/zh-tw/%E9%9C%8D%E5%A4%AB%E6%9B%BC%E7%BC%96%E7%A0%81)是一種貪婪演算法 [圖靈獎](https://zh.wikipedia.org/zh-tw/%E5%9B%BE%E7%81%B5%E5%A5%96):在電腦方面有重大貢獻的獎項 [圖靈](https://zh.wikipedia.org/zh-tw/%E8%89%BE%E4%BC%A6%C2%B7%E5%9B%BE%E7%81%B5):圖靈機,證明停止問題不可解,圖靈測試 [ELIZA](https://zh.wikipedia.org/zh-tw/ELIZA):第一個聊天機器人 #### 圖靈獎得獎名單: 1966第一屆:[艾倫·佩利](https://zh.wikipedia.org/zh-tw/%E8%89%BE%E4%BC%A6%C2%B7%E4%BD%A9%E5%88%A9),編譯器和程式語言貢獻 1967第二屆:[莫里斯·威爾克斯](https://zh.wikipedia.org/zh-tw/%E8%8E%AB%E9%87%8C%E6%96%AF%C2%B7%E5%A8%81%E5%B0%94%E5%85%8B%E6%96%AF),第一台有libary的計算機 1968第三屆:[理察·衛斯里·漢明](https://zh.wikipedia.org/zh-tw/%E7%90%86%E6%9F%A5%E5%BE%B7%C2%B7%E8%A1%9B%E6%96%AF%E9%87%8C%C2%B7%E6%BC%A2%E6%98%8E):[hamming code](https://zh.wikipedia.org/zh-tw/%E6%B1%89%E6%98%8E%E7%A0%81)(可以檢查錯誤) 1969第四屆:[馬文·明斯基](https://zh.wikipedia.org/zh-tw/%E9%A9%AC%E6%96%87%C2%B7%E9%97%B5%E6%96%AF%E5%9F%BA),提出單層感知器不能解決XOR問題 1970第五屆:[詹姆斯·威爾金森](https://zh.wikipedia.org/zh-tw/%E8%A9%B9%E5%A7%86%E6%96%AF%C2%B7%E5%A8%81%E5%B0%94%E9%87%91%E6%A3%AE),矩陣運算貢獻 1971第六屆:[約翰·麥卡錫](https://zh.wikipedia.org/zh-tw/%E7%BA%A6%E7%BF%B0%C2%B7%E9%BA%A6%E5%8D%A1%E9%94%A1),發明LISP,提出人工智慧 1972第七屆:[艾茲赫爾·戴克斯特拉](https://zh.wikipedia.org/zh-tw/%E8%89%BE%E5%85%B9%E8%B5%AB%E5%B0%94%C2%B7%E6%88%B4%E5%85%8B%E6%96%AF%E7%89%B9%E6%8B%89):GOTO有害論,銀行家算法 1973第八屆:[查爾斯·巴赫曼](https://zh.wikipedia.org/zh-tw/%E6%9F%A5%E5%B0%94%E6%96%AF%C2%B7%E5%B7%B4%E8%B5%AB%E6%9B%BC),網狀資料庫,三層模型 1974第九屆:[高德納](https://zh.wikipedia.org/zh-tw/%E9%AB%98%E5%BE%B7%E7%BA%B3),[LR parsers](https://zh.wikipedia.org/zh-tw/LR%E5%89%96%E6%9E%90%E5%99%A8)(剖析器) 1975第十屆:[艾倫·紐厄爾](https://zh.wikipedia.org/wiki/%E8%89%BE%E4%BC%A6%C2%B7%E7%BA%BD%E5%8E%84%E5%B0%94)+[司馬賀](https://zh.wikipedia.org/zh-tw/%E5%8F%B8%E9%A9%AC%E8%B4%BA),人工智慧方面 1976第十一屆:[麥可·拉賓](https://zh.wikipedia.org/zh-tw/%E8%BF%88%E5%85%8B%E5%B0%94%C2%B7%E6%8B%89%E5%AE%BE_(%E7%A7%91%E5%AD%A6%E5%AE%B6))+[達納·斯科特](https://zh.wikipedia.org/zh-tw/%E8%BE%BE%E7%BA%B3%C2%B7%E6%96%AF%E7%A7%91%E7%89%B9),有限自動機與判定問題 1977第十二屆:[約翰·巴科斯](https://zh.wikipedia.org/zh-tw/%E7%B4%84%E7%BF%B0%C2%B7%E5%B7%B4%E7%A7%91%E6%96%AF),[BNF](https://zh.wikipedia.org/zh-tw/%E5%B7%B4%E7%A7%91%E6%96%AF%E8%8C%83%E5%BC%8F)(上下文無關文法的語言) 1978第十三屆:[羅伯特·弗洛伊德](https://zh.wikipedia.org/zh-tw/%E7%BD%97%E4%BC%AF%E7%89%B9%C2%B7%E5%BC%97%E6%B4%9B%E4%BC%8A%E5%BE%B7),最短路徑 1979第十四屆:[肯尼斯·艾佛森](https://zh.wikipedia.org/zh-tw/%E8%82%AF%E5%B0%BC%E6%96%AF%C2%B7%E8%89%BE%E4%BD%9B%E6%A3%AE),J語言 1980第十五屆:[東尼·霍爾](https://zh.wikipedia.org/zh-tw/%E6%9D%B1%E5%B0%BC%C2%B7%E9%9C%8D%E7%88%BE),演算法,程式語言貢獻 1981第十六屆:[埃德加·科德](https://zh.wikipedia.org/zh-tw/%E5%9F%83%E5%BE%B7%E5%8A%A0%C2%B7%E7%A7%91%E5%BE%B7),關聯式資料庫 1982第十七屆:[史蒂芬·庫克](https://zh.wikipedia.org/zh-tw/%E5%8F%B2%E8%92%82%E8%8A%AC%C2%B7%E5%BA%93%E5%85%8B),[NP-complete](https://zh.wikipedia.org/zh-tw/NP%E5%AE%8C%E5%85%A8)(演算法) 1983第十八屆:[肯·湯普遜](https://zh.wikipedia.org/zh-tw/%E8%82%AF%C2%B7%E6%B1%A4%E6%99%AE%E9%80%8A)+[丹尼斯·里奇](https://zh.wikipedia.org/zh-tw/%E4%B8%B9%E5%B0%BC%E6%96%AF%C2%B7%E9%87%8C%E5%A5%87),C語言,UNIX作業系統 1984第十九屆:[尼克勞斯·維爾特](https://zh.wikipedia.org/zh-tw/%E5%B0%BC%E5%85%8B%E5%8A%B3%E6%96%AF%C2%B7%E7%BB%B4%E5%B0%94%E7%89%B9),各種程式語言(Pascal,Euler,Oberon...),[EBNF](https://zh.wikipedia.org/zh-tw/%E6%89%A9%E5%B1%95%E5%B7%B4%E7%A7%91%E6%96%AF%E8%8C%83%E5%BC%8F) 1985第二十屆:[理察·卡普](https://zh.wikipedia.org/zh-tw/%E7%90%86%E6%9F%A5%E5%BE%B7%C2%B7%E5%8D%A1%E6%99%AE),證明NP-complete的21個問題 1986第二十一屆:[約翰·霍普克洛夫特](https://zh.wikipedia.org/zh-tw/%E7%B4%84%E7%BF%B0%C2%B7%E9%9C%8D%E6%99%AE%E5%85%8B%E6%B4%9B%E5%A4%AB%E7%89%B9)+[羅伯特·塔揚](https://zh.wikipedia.org/zh-tw/%E7%BE%85%E4%BC%AF%E7%89%B9%C2%B7%E5%A1%94%E6%8F%9A),二分圖,各種算法 1987第二十二屆:[約翰·科克](https://zh.wikipedia.org/zh-tw/%E7%BA%A6%E7%BF%B0%C2%B7%E7%A7%91%E5%85%8B),RISC架構 1988第二十三屆:[伊凡·蘇澤蘭](https://zh.wikipedia.org/zh-tw/%E4%BC%8A%E5%87%A1%C2%B7%E8%98%87%E6%BE%A4%E8%98%AD),計算機圖形學,視窗電腦 1989第二十四屆:[威廉·卡韓](https://zh.wikipedia.org/zh-tw/%E5%A8%81%E5%BB%89%C2%B7%E5%8D%A1%E9%9F%93),IEEE754,浮點數 1990第二十五屆:[費南多·柯巴托](https://zh.wikipedia.org/zh-tw/%E8%B2%BB%E5%8D%97%E5%A4%9A%C2%B7%E6%9F%AF%E5%B7%B4%E6%89%98),[CTSS](https://zh.wikipedia.org/zh-tw/%E7%9B%B8%E5%AE%B9%E5%88%86%E6%99%82%E7%B3%BB%E7%B5%B1)(分時系統),[Multics](https://zh.wikipedia.org/zh-tw/Multics)(多工資訊與計算系統) 1991第二十六屆:[羅賓·米爾納](https://zh.wikipedia.org/zh-tw/%E7%BD%97%E5%AE%BE%C2%B7%E7%B1%B3%E5%B0%94%E7%BA%B3),[ML語言](https://zh.wikipedia.org/zh-tw/ML%E8%AF%AD%E8%A8%80)(函數式語言) 1992第二十七屆:[巴特勒·蘭普森](https://zh.wikipedia.org/zh-tw/%E5%B7%B4%E7%89%B9%E5%8B%92%C2%B7%E8%98%AD%E6%99%AE%E6%A3%AE),個人圖形化電腦 1993第二十八屆:[尤里斯·哈特馬尼斯](https://zh.wikipedia.org/zh-tw/%E5%B0%A4%E9%87%8C%E6%96%AF%C2%B7%E5%93%88%E7%89%B9%E9%A9%AC%E5%B0%BC%E6%96%AF)+[理察·斯特恩斯](https://zh.wikipedia.org/zh-tw/%E7%90%86%E6%9F%A5%E5%BE%B7%C2%B7%E6%96%AF%E7%89%B9%E6%81%A9%E6%96%AF),建立複雜度階層 1994第二十九屆:[愛德華·費根鮑姆](https://zh.wikipedia.org/zh-tw/%E6%84%9B%E5%BE%B7%E8%8F%AF%C2%B7%E8%B2%BB%E6%A0%B9%E9%AE%91%E5%A7%86),建立DENDRAL+[拉吉·瑞迪](https://zh.wikipedia.org/zh-tw/%E6%8B%89%E5%90%89%C2%B7%E7%91%9E%E8%BF%AA),自動駕駛 1995第三十屆:[曼紐爾·布盧姆](https://zh.wikipedia.org/zh-tw/%E6%9B%BC%E7%BA%BD%E5%B0%94%C2%B7%E5%B8%83%E5%8D%A2%E5%A7%86),布魯姆加速定理,提出BG(一種非對稱式加密系統) 1996第三十一屆:[阿米爾·伯努利](https://zh.wikipedia.org/zh-tw/%E9%98%BF%E7%B1%B3%E5%B0%94%C2%B7%E4%BC%AF%E5%8A%AA%E5%88%A9),引入時序 1997第三十二屆:[道格拉斯·恩格爾巴特](https://zh.wikipedia.org/zh-tw/%E9%81%93%E6%A0%BC%E6%8B%89%E6%96%AF%C2%B7%E6%81%A9%E6%A0%BC%E5%B0%94%E5%B7%B4%E7%89%B9),發明滑鼠,圖形介面互動先驅 1998第三十三屆:[詹姆斯·尼古拉·格雷](https://zh.wikipedia.org/zh-tw/%E8%A9%B9%E5%A7%86%E6%96%AF%C2%B7%E5%B0%BC%E5%8F%A4%E6%8B%89%C2%B7%E6%A0%BC%E9%9B%B7),資料庫方面貢獻 1999第三十四屆:[佛瑞德·布魯克斯](https://zh.wikipedia.org/zh-tw/%E4%BD%9B%E7%91%9E%E5%BE%B7%C2%B7%E5%B8%83%E9%AD%AF%E5%85%8B%E6%96%AF),開發OS/360 2000第三十五屆:[姚期智](https://zh.wikipedia.org/zh-tw/%E5%A7%9A%E6%9C%9F%E6%99%BA),密碼學,偽隨機數生成 2001第三十六屆:[奧利-約翰·達爾](https://zh.wikipedia.org/zh-tw/%E5%A5%A7%E5%88%A9-%E7%B4%84%E7%BF%B0%C2%B7%E9%81%94%E7%88%BE)+[克利斯登·奈加特](https://zh.wikipedia.org/zh-tw/%E5%85%8B%E5%88%A9%E6%96%AF%E7%99%BB%C2%B7%E5%A5%88%E5%8A%A0%E7%89%B9),發明simula物件導向程式語言 2002第三十七屆:[羅納德·李維斯特](https://zh.wikipedia.org/zh-tw/%E7%BD%97%E7%BA%B3%E5%BE%B7%C2%B7%E6%9D%8E%E7%BB%B4%E6%96%AF%E7%89%B9)+[阿迪·薩莫爾](https://zh.wikipedia.org/zh-tw/%E9%98%BF%E8%BF%AA%C2%B7%E8%90%A8%E8%8E%AB%E5%B0%94)+[倫納德·阿德曼](https://zh.wikipedia.org/zh-tw/%E4%BC%A6%E7%BA%B3%E5%BE%B7%C2%B7%E9%98%BF%E5%BE%B7%E6%9B%BC),發明RSA算法 2003第三十八屆:[艾倫·凱](https://zh.wikipedia.org/zh-tw/%E8%89%BE%E4%BC%A6%C2%B7%E5%87%AF),物件導向方面貢獻 2004第三十九屆:[文頓·瑟夫](https://zh.wikipedia.org/zh-tw/%E6%96%87%E7%89%B9%C2%B7%E7%91%9F%E5%A4%AB)+[羅伯特·卡恩](https://zh.wikipedia.org/zh-tw/%E7%BD%97%E4%BC%AF%E7%89%B9%C2%B7%E5%8D%A1%E6%81%A9),TCP/IP協定 2005第四十屆:[彼得·諾爾](https://zh.wikipedia.org/zh-tw/%E5%BD%BC%E5%BE%97%C2%B7%E8%AB%BE%E7%88%BE),Algol 60 語言 2006第四十一屆:[法蘭·艾倫](https://zh.wikipedia.org/zh-tw/%E6%B3%95%E5%85%B0%C2%B7%E8%89%BE%E4%BC%A6),編譯器方面貢獻 2007第四十二屆:[愛德蒙·克拉克](https://zh.wikipedia.org/zh-tw/%E7%88%B1%E5%BE%B7%E8%92%99%C2%B7%E5%85%8B%E6%8B%89%E5%85%8B)+[艾倫·愛默生](https://zh.wikipedia.org/zh-tw/%E8%89%BE%E4%BC%A6%C2%B7%E7%88%B1%E9%BB%98%E7%94%9F)+[約瑟夫·斯發基斯](https://zh.wikipedia.org/zh-tw/%E7%BA%A6%E7%91%9F%E5%A4%AB%C2%B7%E6%96%AF%E5%8F%91%E5%9F%BA%E6%96%AF),開發debugger 2008第四十屆:[芭芭拉·利斯科夫](https://zh.wikipedia.org/zh-tw/%E8%8A%AD%E8%8A%AD%E6%8B%89%C2%B7%E5%88%A9%E6%96%AF%E7%A7%91%E5%A4%AB),分散式程式語言方面 2009第四十一屆:[查爾斯·薩克爾](https://zh.wikipedia.org/zh-tw/%E6%9F%A5%E5%B0%94%E6%96%AF%C2%B7%E8%90%A8%E5%85%8B%E5%B0%94),第一台現代式窗型個人電腦 2010第四十二屆:[萊斯利·瓦利安特](https://zh.wikipedia.org/zh-tw/%E8%8E%B1%E6%96%AF%E5%88%A9%C2%B7%E7%93%A6%E5%88%A9%E5%AE%89%E7%89%B9),演算法方面貢獻 2011第四十三屆:[朱迪亞·珀爾](https://zh.wikipedia.org/zh-tw/%E6%9C%B1%E8%BF%AA%E4%BA%9A%C2%B7%E7%8F%80%E5%B0%94),發明貝式網路 2012第四十四屆:[莎菲·戈德瓦塞爾](https://zh.wikipedia.org/zh-tw/%E8%8E%8E%E8%8F%B2%C2%B7%E6%88%88%E5%BE%B7%E7%93%A6%E5%A1%9E%E5%B0%94)+[希爾維奧·米卡利](https://zh.wikipedia.org/zh-tw/%E5%B8%8C%E7%88%BE%E7%B6%AD%E5%A5%A7%C2%B7%E7%B1%B3%E5%8D%A1%E5%88%A9),密碼科學方面貢獻 2013第四十五屆:[萊斯利·蘭波特](https://zh.wikipedia.org/zh-tw/%E8%8E%B1%E6%96%AF%E5%88%A9%C2%B7%E5%85%B0%E6%B3%A2%E7%89%B9),引果邏輯時序,安全性與存活度,循序一致性...等理論 2014第四十六屆:[麥可·史東布雷克](https://zh.wikipedia.org/zh-tw/%E8%BF%88%E5%85%8B%E5%B0%94%C2%B7%E6%96%AF%E9%80%9A%E5%B8%83%E9%9B%B7%E5%85%8B),資料庫系統貢獻 2015第四十七屆:[惠特菲爾德·迪菲](https://zh.wikipedia.org/zh-tw/%E6%83%A0%E7%89%B9%E8%8F%B2%E7%88%BE%E5%BE%B7%C2%B7%E8%BF%AA%E8%8F%B2)+[馬丁·赫爾曼](https://zh.wikipedia.org/zh-tw/%E9%A6%AC%E4%B8%81%C2%B7%E8%B5%AB%E7%88%BE%E6%9B%BC),發明迪菲-赫爾曼密鑰交換 2016第四十八屆:[提姆·柏內茲-李](https://zh.wikipedia.org/zh-tw/%E8%92%82%E5%A7%86%C2%B7%E4%BC%AF%E7%BA%B3%E6%96%AF-%E6%9D%8E),發明全球資訊網 2017第四十九屆:[約翰·軒尼詩](https://zh.wikipedia.org/zh-tw/%E7%B4%84%E7%BF%B0%C2%B7%E8%BB%92%E5%B0%BC%E8%A9%A9)+[大衛·帕特森](https://zh.wikipedia.org/zh-tw/%E5%A4%A7%E8%A1%9B%C2%B7%E5%B8%95%E7%89%B9%E6%A3%AE_(%E5%AD%B8%E8%80%85)),計算機結構方面貢獻 2018第五十屆:[約書亞·班吉歐](https://zh.wikipedia.org/zh-tw/%E7%BA%A6%E4%B9%A6%E4%BA%9A%C2%B7%E6%9C%AC%E5%B8%8C%E5%A5%A5)+[傑佛瑞·辛頓](https://zh.wikipedia.org/zh-tw/%E6%9D%B0%E5%BC%97%E9%87%8C%C2%B7%E8%BE%9B%E9%A1%BF)+[楊立昆](https://zh.wikipedia.org/zh-tw/%E6%9D%A8%E7%AB%8B%E6%98%86),深度學習 2019第五十一屆:[艾德文·卡特姆](https://zh.wikipedia.org/zh-tw/%E8%89%BE%E5%BE%B7%E6%96%87%C2%B7%E5%8D%A1%E7%89%B9%E5%A7%86)+[派屈克·漢拉恩](https://zh.wikipedia.org/zh-tw/%E5%B8%95%E7%89%B9%E9%87%8C%E5%85%8B%C2%B7%E6%B1%89%E6%8B%89%E6%81%A9),3D圖型學貢獻 2020第五十二屆:[阿爾佛雷德·艾侯](https://zh.wikipedia.org/zh-tw/%E9%98%BF%E5%B0%94%E4%BD%9B%E9%9B%B7%E5%BE%B7%C2%B7%E8%89%BE%E4%BE%AF)+[傑弗瑞·烏爾曼](https://zh.wikipedia.org/zh-tw/%E6%9D%B0%E5%BC%97%E7%91%9E%C2%B7%E4%B9%8C%E5%B0%94%E6%9B%BC),程式語言演算法與理論方面 2021第五十三屆:[傑克·唐加拉](https://zh.wikipedia.org/zh-tw/%E6%9D%B0%E5%85%8B%C2%B7%E5%94%90%E5%8A%A0%E6%8B%89),數值分析貢獻 2022第五十四屆:[勞勃·梅特卡夫](https://zh.wikipedia.org/zh-tw/%E7%BE%85%E4%BC%AF%E7%89%B9%C2%B7%E6%A2%85%E7%89%B9%E5%8D%A1%E5%A4%AB),乙太網路發明 [CSMA](https://zh.wikipedia.org/zh-tw/%E8%BD%BD%E6%B3%A2%E4%BE%A6%E5%90%AC%E5%A4%9A%E8%B7%AF%E8%AE%BF%E9%97%AE):檢測不會碰撞才傳送 ## 第九周 霍夫曼編碼是一種壓縮方法 [entropy](https://zh.wikipedia.org/zh-tw/%E7%86%B5):接收的每條消息中包含的資訊的平均量(平均編碼資訊量) [heapsort](https://zh.wikipedia.org/zh-tw/%E5%A0%86%E6%8E%92%E5%BA%8F):堆積排序法 [隨機變數](https://zh.wikipedia.org/zh-tw/%E9%9A%8F%E6%9C%BA%E5%8F%98%E9%87%8F):隨機試驗結果的變數 [廣度優先搜尋](https://zh.wikipedia.org/zh-tw/%E5%B9%BF%E5%BA%A6%E4%BC%98%E5%85%88%E6%90%9C%E7%B4%A2)(BFS):從根往下,沿寬度遍歷 [深度優先搜尋](https://zh.wikipedia.org/zh-tw/%E6%B7%B1%E5%BA%A6%E4%BC%98%E5%85%88%E6%90%9C%E7%B4%A2)(DFS):從根往下,搜到無子節點在換下一條 [深度,廣度優先搜尋程式碼](https://github.com/ccc112a/py2cs/blob/master/02-%E6%BC%94%E7%AE%97%E6%B3%95/02-%E6%96%B9%E6%B3%95/06-%E6%90%9C%E5%B0%8B%E6%B3%95/02-search/graph_search.py) ### 習題 1. 用搜尋演算法求下列其中一個問題的解 老鼠走迷宮 《狼、羊、甘藍菜》過河的問題 八個皇后問題 ## 第十周 [狼、羊、甘藍菜問題程式碼(js)](https://github.com/ccc112a/py2cs/blob/master/02-%E6%BC%94%E7%AE%97%E6%B3%95/02-%E6%96%B9%E6%B3%95/06-%E6%90%9C%E5%B0%8B%E6%B3%95/Q2-river/%E7%BF%92%E9%A1%8C%EF%BC%9A%E3%80%8A%E7%8B%BC%E3%80%81%E7%BE%8A%E3%80%81%E7%94%98%E8%97%8D%E8%8F%9C%E3%80%8B%E9%81%8E%E6%B2%B3%E7%9A%84%E5%95%8F%E9%A1%8C.md) [狼、羊、甘藍菜問題程式碼(py)](https://github.com/ccc112a/py2cs/blob/master/02-%E6%BC%94%E7%AE%97%E6%B3%95/02-%E6%96%B9%E6%B3%95/06-%E6%90%9C%E5%B0%8B%E6%B3%95/Q2-river/river.py) [LLAMA](https://zh.wikipedia.org/zh-tw/LLaMA):大型語言訓練模型,[官方網站](https://ai.meta.com/llama/) 單一的.c檔可以直接載入llama:[程式碼](https://github.com/karpathy/llama2.c) [zig](https://ziglang.org/):想取代C,但不想像C++這麼複雜,適合寫作業系統 [bun](https://bun.sh/):可以比deno和node.js更快 純數學領域:代數,幾何,分析 ## 習題 1. 請寫一個程式可以求解 n 次多項式 ## 第十一周 [施特拉森演算法](https://zh.wikipedia.org/zh-tw/%E6%96%BD%E7%89%B9%E6%8B%89%E6%A3%AE%E6%BC%94%E7%AE%97%E6%B3%95):計算矩陣乘法的演算法 動態規劃法:把原問題分解成多個簡單的子問題 用動態規劃法算巴斯卡三角形:[程式碼](https://github.com/ccc112a/py2cs/blob/master/02-%E6%BC%94%E7%AE%97%E6%B3%95/02-%E6%96%B9%E6%B3%95/08-%E5%8B%95%E6%85%8B%E8%A6%8F%E5%8A%83%E6%B3%95/combinatorial/CnkDynamic.py) [編輯距離](https://github.com/ccc112a/py2cs/blob/master/02-%E6%BC%94%E7%AE%97%E6%B3%95/02-%E6%96%B9%E6%B3%95/08-%E5%8B%95%E6%85%8B%E8%A6%8F%E5%8A%83%E6%B3%95/combinatorial/CnkDynamic.py):看需要多少次編輯才能將一個字符串變成另一個字符串,生物學經常用到,[程式碼](https://github.com/ccc112a/py2cs/blob/master/02-%E6%BC%94%E7%AE%97%E6%B3%95/02-%E6%96%B9%E6%B3%95/08-%E5%8B%95%E6%85%8B%E8%A6%8F%E5%8A%83%E6%B3%95/editDistance/editDistance.py) [UUID](https://zh.wikipedia.org/zh-tw/%E9%80%9A%E7%94%A8%E5%94%AF%E4%B8%80%E8%AF%86%E5%88%AB%E7%A0%81):一個128位元的識別碼(不易衝碼) [GUID](https://zh.wikipedia.org/zh-tw/%E5%85%A8%E5%B1%80%E5%94%AF%E4%B8%80%E6%A0%87%E8%AF%86%E7%AC%A6):128位元長的二進位整數(不易衝碼),[程式碼](https://github.com/ccc112a/py2cs/blob/master/02-%E6%BC%94%E7%AE%97%E6%B3%95/02-%E6%96%B9%E6%B3%95/09a-%E9%9A%A8%E6%A9%9F%E6%B3%95/guid.py) [蒙地卡羅法](https://zh.wikipedia.org/zh-tw/%E8%92%99%E5%9C%B0%E5%8D%A1%E7%BE%85%E6%96%B9%E6%B3%95):用亂數解決各種計算問題 [蒙地卡羅法算pi](https://github.com/ccc112a/py2cs/blob/master/02-%E6%BC%94%E7%AE%97%E6%B3%95/02-%E6%96%B9%E6%B3%95/09b-%E8%92%99%E5%9C%B0%E5%8D%A1%E7%BE%85%E6%B3%95/01-pi/monteCarloPi.py) ### 習題 1. (紅利題):用遞迴寫最小編輯距離 ## 第十二周 [拉斯維加斯算法](https://zh.wikipedia.org/zh-tw/%E6%8B%89%E6%96%AF%E7%BB%B4%E5%8A%A0%E6%96%AF%E7%AE%97%E6%B3%95) [T檢定](https://zh.wikipedia.org/zh-tw/%E5%8F%B8%E5%BE%92%E9%A0%93t%E6%AA%A2%E5%AE%9A):在統計學中非常重要,[程式碼](https://github.com/ccc112a/py2cs/blob/master/02-%E6%BC%94%E7%AE%97%E6%B3%95/02-%E6%96%B9%E6%B3%95/09b-%E8%92%99%E5%9C%B0%E5%8D%A1%E7%BE%85%E6%B3%95/03-centrolLimit/ttest1.py) [布萊克-休斯模型](https://zh.wikipedia.org/zh-tw/%E5%B8%83%E8%8E%B1%E5%85%8B-%E8%88%92%E5%B0%94%E6%96%AF%E6%A8%A1%E5%9E%8B):經濟學中的重要模型,有隨機性 在算機率的不一定都是蒙地卡羅,蒙地卡羅要有隨機性 [馬克夫練](https://zh.wikipedia.org/zh-tw/%E9%A9%AC%E5%B0%94%E5%8F%AF%E5%A4%AB%E9%93%BE) gibbs在算所有進出機率平衡,[gibbs程式碼](https://github.com/ccc112a/py2cs/blob/master/02-%E6%BC%94%E7%AE%97%E6%B3%95/02-%E6%96%B9%E6%B3%95/09b-%E8%92%99%E5%9C%B0%E5%8D%A1%E7%BE%85%E6%B3%95/05-markov/gibbs.py) [貝氏定理](https://zh.wikipedia.org/zh-tw/%E8%B4%9D%E5%8F%B6%E6%96%AF%E5%AE%9A%E7%90%86):機率統計上常用到,從A->B的機率推論出B->A的機率 [貝氏分類器](https://zh.wikipedia.org/zh-tw/%E6%9C%B4%E7%B4%A0%E8%B4%9D%E5%8F%B6%E6%96%AF%E5%88%86%E7%B1%BB%E5%99%A8),[程式碼](https://github.com/ccc112a/py2cs/blob/master/02-%E6%BC%94%E7%AE%97%E6%B3%95/02-%E6%96%B9%E6%B3%95/09b-%E8%92%99%E5%9C%B0%E5%8D%A1%E7%BE%85%E6%B3%95/06-bayes/naiveProb.py) [隱馬克夫模型](https://zh.wikipedia.org/zh-tw/%E9%9A%90%E9%A9%AC%E5%B0%94%E5%8F%AF%E5%A4%AB%E6%A8%A1%E5%9E%8B) [期望最大化算法(EM算法)](https://zh.wikipedia.org/zh-tw/%E6%9C%80%E5%A4%A7%E6%9C%9F%E6%9C%9B%E7%AE%97%E6%B3%95),[EM程式碼](https://github.com/ccc112a/py2cs/blob/master/02-%E6%BC%94%E7%AE%97%E6%B3%95/02-%E6%96%B9%E6%B3%95/09b-%E8%92%99%E5%9C%B0%E5%8D%A1%E7%BE%85%E6%B3%95/08-em/em.py) [受限玻爾茲曼機](https://zh.wikipedia.org/zh-tw/%E5%8F%97%E9%99%90%E7%8E%BB%E5%B0%94%E5%85%B9%E6%9B%BC%E6%9C%BA):與AI有關係,在神經網路的學習方面 [基因演算法](https://zh.wikipedia.org/zh-tw/%E9%81%97%E4%BC%A0%E7%AE%97%E6%B3%95):用程式模擬物競天擇,適者生存 [A*搜尋演算法](https://zh.wikipedia.org/zh-tw/A*%E6%90%9C%E5%B0%8B%E6%BC%94%E7%AE%97%E6%B3%95),[A*程式碼](https://github.com/ccc112a/py2cs/blob/master/02-%E6%BC%94%E7%AE%97%E6%B3%95/02-%E6%96%B9%E6%B3%95/06-%E6%90%9C%E5%B0%8B%E6%B3%95/05a-Astar/astar.py)(這個程式好玩~),給定起點,終點,中間障礙,程式會找出一條路 ## 第十三周 前處理法:建索引...等等 委託法:尋找別人寫好的函式庫,可以用[這個網站](https://pypi.org/) [線性規劃](https://zh.wikipedia.org/zh-tw/%E7%BA%BF%E6%80%A7%E8%A7%84%E5%88%92):在限制中找最大值,可以有小數 [單體法](https://zh.wikipedia.org/zh-tw/%E7%BA%BF%E6%80%A7%E8%A7%84%E5%88%92):線性規劃的一種方法,但效率不高 [B-tree](https://zh.wikipedia.org/zh-tw/B%E6%A0%91):一種樹狀資料結構 分層法:針對複雜的系統拆成小層處理 [化約法](https://zh.wikipedia.org/zh-tw/%E6%AD%B8%E7%B4%84):將一個問題轉換成另一個問題,求解後對應回原問題之解的方法 [整數規劃](https://zh.wikipedia.org/zh-tw/%E6%95%B4%E6%95%B0%E8%A7%84%E5%88%92):在限制中找最大值,只能有整數解,會是NP-complete問題 [希爾伯特23個問題](https://zh.wikipedia.org/zh-tw/%E5%B8%8C%E5%B0%94%E4%BC%AF%E7%89%B9%E7%9A%8423%E4%B8%AA%E9%97%AE%E9%A2%98) [歸結原理](https://zh.wikipedia.org/zh-tw/%E5%BD%92%E7%BB%93%E5%8E%9F%E7%90%86) [哥德爾完備定理](https://zh.wikipedia.org/zh-tw/%E5%93%A5%E5%BE%B7%E5%B0%94%E5%AE%8C%E5%A4%87%E6%80%A7%E5%AE%9A%E7%90%86):在一階邏輯中的所有公式都可以證明 [喬姆斯基](https://zh.wikipedia.org/wiki/%E8%AF%BA%E5%A7%86%C2%B7%E4%B9%94%E5%A7%86%E6%96%AF%E5%9F%BA):生成語法,語言方面的大師 [喬姆斯基階乘](https://zh.wikipedia.org/zh-tw/%E4%B9%94%E5%A7%86%E6%96%AF%E5%9F%BA%E8%B0%B1%E7%B3%BB) [BNF(Backus Normal Form)](https://zh.wikipedia.org/zh-tw/%E5%B7%B4%E7%A7%91%E6%96%AF%E8%8C%83%E5%BC%8F):一種上下文無關文法的語言 [有限狀態機](https://zh.wikipedia.org/zh-tw/%E6%9C%89%E9%99%90%E7%8A%B6%E6%80%81%E6%9C%BA) ### 習題 1. 把從希爾伯特經圖靈到 NP-Complete 的故事寫下來 ## 第十四周 [希爾伯特23個問題](https://zh.wikipedia.org/zh-tw/%E5%B8%8C%E5%B0%94%E4%BC%AF%E7%89%B9%E7%9A%8423%E4%B8%AA%E9%97%AE%E9%A2%98) 連續統假設:一步步推論出結果[程式碼](https://github.com/ccc112a/py2cs/blob/master/06-%E8%A8%88%E7%AE%97%E7%90%86%E8%AB%96/01-%E5%B8%8C%E7%88%BE%E4%BC%AF%E7%89%B9%E7%9A%84%E5%95%8F%E9%A1%8C.md) [羅素悖論](https://zh.wikipedia.org/zh-tw/%E7%BD%97%E7%B4%A0%E6%82%96%E8%AE%BA):使希爾伯特第二個問題受到矛盾 [哥德爾完備定理](https://zh.wikipedia.org/zh-tw/%E5%93%A5%E5%BE%B7%E5%B0%94%E5%AE%8C%E5%A4%87%E6%80%A7%E5%AE%9A%E7%90%86) [丘奇函數](https://zh.wikipedia.org/zh-tw/%E9%82%B1%E5%A5%87%E6%95%B0):一套代換系統,為函數式編程領域先驅 [圖靈機](https://zh.wikipedia.org/zh-tw/%E5%9B%BE%E7%81%B5%E6%9C%BA):一種計算模型 [丘奇-圖靈猜想](https://zh.wikipedia.org/zh-tw/%E9%82%B1%E5%A5%87-%E5%9B%BE%E7%81%B5%E8%AE%BA%E9%A2%98):任何在算法上可計算的問題同樣可由圖靈機計算 [SAT問題](https://zh.wikipedia.org/zh-tw/%E5%B8%83%E5%B0%94%E5%8F%AF%E6%BB%A1%E8%B6%B3%E6%80%A7%E9%97%AE%E9%A2%98):第一個NP完全問題 P: [確定型圖靈機](https://zh.wikipedia.org/wiki/%E5%9B%BE%E7%81%B5%E6%9C%BA)可以在多項式時間內解決的問題 NP: [非確定型圖靈機](https://zh.wikipedia.org/zh-tw/%E9%9D%9E%E7%A1%AE%E5%AE%9A%E5%9E%8B%E5%9B%BE%E7%81%B5%E6%9C%BA)可以在多項式時間內解決的問題 [量子電腦](https://zh.wikipedia.org/zh-tw/%E9%87%8F%E5%AD%90%E8%AE%A1%E7%AE%97%E6%9C%BA)是機率波的機器 [ENIAC](https://zh.wikipedia.org/zh-tw/%E9%9B%BB%E5%AD%90%E6%95%B8%E5%80%BC%E7%A9%8D%E5%88%86%E8%A8%88%E7%AE%97%E6%A9%9F):早期通用型電腦 [馮紐曼架構](https://zh.wikipedia.org/zh-tw/%E5%86%AF%C2%B7%E8%AF%BA%E4%BC%8A%E6%9B%BC%E7%BB%93%E6%9E%84):目前的電腦架構 ## 第十五周 [逼近法](https://zh.wikipedia.org/zh-tw/%E9%80%BC%E8%BF%91%E7%90%86%E8%AE%BA):運用函數無限的逼近正確答案,會有誤差 [史特靈公式](https://zh.wikipedia.org/zh-tw/%E5%8F%B2%E7%89%B9%E9%9D%88%E5%85%AC%E5%BC%8F):用來取n階乘近似值的公式 [蝴蝶效應](https://zh.wikipedia.org/zh-tw/%E8%9D%B4%E8%9D%B6%E6%95%88%E5%BA%94):在動態系統中,一個小改變會造成之後巨大的誤差(逼近法裡的誤差就是) 多次微分過後的誤差會非常巨大,可以換用符號微分(基本不會有誤差) [泰勒級數](https://zh.wikipedia.org/zh-tw/%E6%B3%B0%E5%8B%92%E7%BA%A7%E6%95%B0)(也是一種逼近) [黎曼積分](https://zh.wikipedia.org/zh-tw/%E9%BB%8E%E6%9B%BC%E7%A7%AF%E5%88%86)(也是一種逼近):用很多個矩形和逼近一個曲線的面積 [單純貝氏分類器](https://zh.wikipedia.org/wiki/%E6%9C%B4%E7%B4%A0%E8%B4%9D%E5%8F%B6%E6%96%AF%E5%88%86%E7%B1%BB%E5%99%A8):利用假設事件機率都獨立,來推斷綜合的機率 [Kubernetes(K8s)](https://zh.wikipedia.org/zh-tw/Kubernetes):一種容器系統,速度很快,google的,可能會取代docker [淘寶架構演進](https://www.readfog.com/a/1665362910517497856):因為docker的技術出現,造成架構的演進 [傅立葉轉換](https://zh.wikipedia.org/zh-tw/%E5%82%85%E9%87%8C%E5%8F%B6%E5%8F%98%E6%8D%A2):處理懸波和週期函數 一維適合處理語音 二維適合處理影像(可以用來壓縮,大概20倍,例如:jpg檔) [沃爾什轉換](https://zh.wikipedia.org/zh-tw/%E6%B2%83%E7%88%BE%E4%BB%80%E8%BD%89%E6%8F%9B) [海蒂·拉瑪](https://zh.wikipedia.org/zh-tw/%E6%B5%B7%E8%92%82%C2%B7%E6%8B%89%E7%8E%9B):研發秘密通信系統(日後成為5G的技術關鍵) [拉普拉斯轉換](https://zh.wikipedia.org/zh-tw/%E6%8B%89%E6%99%AE%E6%8B%89%E6%96%AF%E5%8F%98%E6%8D%A2):用在解微分方程式,先轉成多項式去解,後再轉回微分方程式 [Z轉換](https://zh.wikipedia.org/zh-tw/Z%E8%BD%89%E6%8F%9B) ## 第十六周 python有支援複數,但是是用j表示 手機內的RF模組基本上都是高通做的(高通前身是[Linkabit](https://en.wikipedia.org/wiki/Linkabit)) [摩爾定律](https://zh.wikipedia.org/zh-tw/%E6%91%A9%E5%B0%94%E5%AE%9A%E5%BE%8B)(最近已經失效了):電晶體兩年會長一倍 [威廉·肖克利](https://zh.wikipedia.org/zh-tw/%E5%A8%81%E5%BB%89%C2%B7%E8%82%96%E5%85%8B%E5%88%A9):和另一個人發明電晶體,發明MOS(目前主流是CMOS) [相量](https://zh.wikipedia.org/zh-tw/%E7%9B%B8%E9%87%8F) [Norm](https://zh.wikipedia.org/zh-tw/%E8%8C%83%E6%95%B0)(人工智慧中重要的東西) 任何東西經過轉換之後都可以用700維向量表示 線性代數橫跨代數和幾何 這周教的大部分都是數學,我數學不適很好,所以很多都聽不太懂 ## 第十七周 [正規表達式](https://zh.wikipedia.org/zh-tw/%E6%AD%A3%E5%88%99%E8%A1%A8%E8%BE%BE%E5%BC%8F):用簡單字串來描述、符合文中全部符合指定格式的字串 +代表1以上 *代表0以上 ?代表0到1之間 [KMP演算法](https://zh.wikipedia.org/zh-tw/KMP%E7%AE%97%E6%B3%95):一種字串對比的演算法 霍夫曼編碼用來壓縮很差,用[LZW](https://zh.wikipedia.org/zh-tw/LZW)壓所更好 [Trie](https://zh.wikipedia.org/zh-tw/Trie):一種多元樹 [Radix Trie](https://zh.wikipedia.org/zh-tw/%E5%9F%BA%E6%95%B0%E6%A0%91):一種相較Trie更省空間的樹 [倒排索引](https://zh.wikipedia.org/zh-tw/%E5%80%92%E6%8E%92%E7%B4%A2%E5%BC%95):一種前處理 [PageRank](https://zh.wikipedia.org/zh-tw/PageRank):google用來對搜尋結果中的網頁進行排名的一種演算法 [離散餘弦轉換](https://zh.wikipedia.org/zh-tw/%E7%A6%BB%E6%95%A3%E4%BD%99%E5%BC%A6%E5%8F%98%E6%8D%A2) 圖形理論可以使用[NetworkX](https://networkx.org/)這個套件 [戴克斯特拉演算法](https://zh.wikipedia.org/wiki/%E6%88%B4%E5%85%8B%E6%96%AF%E7%89%B9%E6%8B%89%E7%AE%97%E6%B3%95) [最大流問題](https://zh.wikipedia.org/zh-tw/%E6%9C%80%E5%A4%A7%E6%B5%81%E9%97%AE%E9%A2%98):在一個單源點、單匯點的網路流中找到一條最大的流 [凱薩密碼](https://zh.wikipedia.org/zh-tw/%E5%87%B1%E6%92%92%E5%AF%86%E7%A2%BC):位移加密 [維吉尼亞密碼](https://zh.wikipedia.org/zh-tw/%E7%BB%B4%E5%90%89%E5%B0%BC%E4%BA%9A%E5%AF%86%E7%A0%81) [XOR加密](https://zh.wikipedia.org/zh-tw/%E5%BC%82%E6%88%96%E5%AF%86%E7%A0%81):先轉成ASCII後進行XOR運算 [AES](https://zh.wikipedia.org/zh-tw/%E9%AB%98%E7%BA%A7%E5%8A%A0%E5%AF%86%E6%A0%87%E5%87%86):美國聯邦政府採用的一種區塊加密標準,用來取代DES [迪菲-赫爾曼金鑰交換](https://zh.wikipedia.org/wiki/%E8%BF%AA%E8%8F%B2-%E8%B5%AB%E7%88%BE%E6%9B%BC%E5%AF%86%E9%91%B0%E4%BA%A4%E6%8F%9B):影響後來RSA加密法 [RSA加密](https://zh.wikipedia.org/zh-tw/RSA%E5%8A%A0%E5%AF%86%E6%BC%94%E7%AE%97%E6%B3%95) [伽羅瓦體](https://zh.wikipedia.org/wiki/%E6%9C%89%E9%99%90%E5%9F%9F)
Last changed by  
 
siyu0927
272
Published on HackMD