Lecture 1: Algorithms and Computation
課程目的
- 解決電腦上遇到的問題
- 證明正確性
- 探討效率
並且很著重溝通，說服別人你做的事是正確且有效率的。
何謂電腦問題
你有輸入，需要輸出。
A輸入的正確解答是BCD輸出，解決這個問題的方法就是電腦問題。
演算法
給一個輸入，軟體或方法給一個「正確」輸出，就是演算法。
範例：學生生日相同與否演算法
方法一
記錄所有學生的生日，每次紀錄新資料時，比對已記錄資料，若有相同生日，回傳「是」。
時間複雜度：O(n)
空間複雜度：O(n)
正確性
歸納法證明
若前K名學生有人的生日一樣，在問第K+1名學生之前回傳「是」。
若K=0，則回傳「否」。
則K=K'時，會出現兩種情況：
- K’已回傳「是」，有相同解。
- K’沒有相同解，比較K’+1。
效率
衡量效率時需要顧慮電腦性能與輸入資料規模，所以不比較時間，而比較輸出答案所需的執行次數。
為此會需要用到「漸近分析」，會在之後被討論到。
預期演算法會隨著輸入大小改變輸出所需時間。
漸近符號（asymptotic notation）
大 O 符號（Big O notation）：最高上限
大 Ω 符號（Big Omega notation）：最低下限
大 θ 符號（Big Theta notation）：上下限之間的區間
計算模型
Word RAM
「Word」代表的是CPU可以處裡的資料量，RAM就是記憶體（Random access memory）。
現在的作業系統大多是64bits，以前是32bits。
32bits最多只能有2^32bytes的儲存空間，大約4GB。
64bits可以有2^64bytes，大約20EB，短時間內用不完就對了。
CPU
可以進行數字運算、邏輯判斷、Bitwise Operation
資料結構
前八堂課會討論資料結構，會討論儲存大資料的方法與怎麼讓CPU可以操作這些資料。
