1.1 演算法
什么是演算法
? 若對每個輸入實體，演算法都以正確的輸出停機，則稱該演算法是正確的，并稱正確的演算法解決了給定的計算問題，
? 不正確的演算法對某些輸入實體可能根本不停機，
擴展參考：圖靈停機問題（P616）
問題描述：判斷一個程式是否會在有限時間內結束運行，
? 這個答案是否定的，這里涉及邏輯數學中可計算性理論，
參考教材：
《離散數學及其應用 第8版》 第13章 計算模型
《計算機程式的構造和解釋 第2版》 第4章 元語言抽象
演算法解決哪些問題：
- 互聯網上的網站能夠管理和處理海量資料
- 電子商務中公鑰密碼和數字簽名，以數值演算法和數論為基礎
- 最短路徑問題
- 最長公共子序列問題（LCS），用到動態規劃（DP）
- 機械設計中部件組成，涉及拓撲排序
- 給定平面上n個點，求包含這些點的最小凸多邊形（MCP）
- 資料壓縮、大多項式與整數相乘，涉及離散傅里葉變換，相關有效的演算法——快速傅里葉變換
難題：NP完全問題
NP完全問題的3個特點：
-
不曾找到一個NP完全問題的有效演算法，沒有人能證明NP完全問題確實不存在有效演算法；
-
NP完全問題具有一個非凡的性質：如果任何一個NP完全問題存在有效演算法，那么所有NP完全問題都會存在有效演算法；//“一個有解，個個有解”
-
有幾個NP完全問題類似于（但又不完全同于）一些有些已知有效演算法的問題， //近似演算法
計算機科學家迷戀于如何通過對問題陳述的一個小小的改變來很大地改變其已知最佳演算法的效率，
計算并行性
計算并行性提出的原因：
? 芯片功率密度隨時鐘速度超線性增加，一旦時鐘速度變得足夠快，芯片將有熔化的危險，//不能無限制的加速
解決方案：
? 芯片被設計成包含不止一個而是幾個處理的核，故設計演算法時必須考慮并行性，//硬體上多核并行，軟體上多執行緒并行，執行緒概念的提出就是為了在軟體層面上解決計算并行性問題
1.2 作為一種技術的演算法
? 演算法是當代計算機中使用的大多數技術的核心，
? 是否具有演算法知識與技術的堅實基礎是區分真正熟練的程式員和初學者的一個特征，
Techniques for controlling the complexity of these large systems. In some sense, that’s really what computer science is about.
? –Harold Abelson (SICP的作者)
課后習題答案
參考答案
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/224016.html
標籤：python