Chapter12运算理论.ppt

Chapter 12 運算理論,12.1 函數及其運算 12.2 杜林機器 12.3 全能程式語言 12.4 不可計算函數 12.5 問題的複雜度 12.6 公開金鑰密碼學,12.1 函數及其運算,函數（function）是一種介於一群可能的輸入值與一群輸出值的對應關係，而使得每一個可能的輸入均可對應到一個唯一的輸出。 決定一個函數在指定特定輸入值之後會產生特定輸出值的過程，稱為函數計算（computing the function）。 這些函數的計算超出任何演算法系統的能力，這類函數稱為不可計算的（noncomputable），輸出值可以用演算法依輸入值決定的函數則稱為可計算的（computable）。,圖 12.1 試圖顯示出一個將碼的度量轉換成公尺,12.2 杜林機器,杜林機器基礎 一部杜林機器（Turing machine）具有一個控制單元，可以利用讀/寫頭在磁帶上讀寫符號（圖 12.2）。 任何時間，機器必須處於一組有限數量的狀況，稱為狀態（state）中的一種狀況。開始於起始狀態（start state），停止為停止狀態（halt state）。 機器的磁帶看起來如右圖：,圖 12.2 杜林機器的元件,圖 12.3 將其數值遞增的杜林機器,一個能用杜林機器計算出的函數即稱為杜林可計算（Turing computable）。 杜林機器的計算能力涵蓋了任何演算式機器的計算能力。 這個假設稱為 Church-Turing 命題。 這個假說的重要性是，它使我們可以洞察計算機器的能力及極限。,12.3 全能程式語言,一個簡單的命令式程式語言，它足以讓我們表示出計算所有杜林可計算函數的程式。 稱為全能程式語言（universal programming language）。 精簡程式語言 clear name; incr name; decr name;,一個控制結構（control structure），以 while-end 表示：,用精簡程式語言寫程式 真正目標是探究哪些是可能的（possible），而不是研究哪些是實際可行的（practical）。 精簡程式語言的全能性 研究學者已經證明，精簡程式語言可以用來表示各種能計算出杜林可計算函數的演算法。 隱喻著任何可計算函數都可以被以此精簡程式語言所寫的程式計算出來。,圖 12.4 用來計算 X Y 的精簡程式, 圖 12.5 將指令 “copy Today to Tomorrow” 轉換成精簡程式語言程式,12.4 不可計算函數,停止問題 停止問題是試圖預言，一個程式在某特定條件下啟動後是否會終結（或停止）的問題。 自我參用（self-reference）的技術亦即一個物件參用本身的觀念。 自我終結的（self-terminating）：一個程式是自我終結的，如果其執行以其本身作為輸入而會終止時。,圖 12.6 測試一個程式是否會自我終結,停止問題的不可解本質 圖 12.7。 解決停止問題已超過任何演算法系統的能力範疇。這類問題即被稱為不可解問題（unsolvable problems）。,圖 12.7 證明停止問題的不可解本質,12.5 問題的複雜度,衡量一個問題的複雜度 如果一個問題的所有解決方法都需要耗費很多時間，那它就可被視為是複雜的。這種概念常被稱為時間複雜度（time complexity）。 研究一個演算法的效率就是研究演算法的時間複雜度。 big O 符號（big 符號的變形）被用來表示問題的複雜度。 排序問題的較佳解法的一個實例是合併排序法。 合併排序演算法歸類為 O(n 1g n)。,圖 12.8 合併兩個清單的 MergeLists 程式,圖 12.9 實作合併排序演算法的 MergeSort 程式,圖 12.10 合併排序演算法所產生的階層式子問題,多項式問題相較於非多項式問題 一個問題是多項式問題（polynomial problem），表示這個問題是屬於 O( f(n) ，其中 f(n) 本身是一個多項式或是受限於某一個多項式。包含所有多項式問題的集合傳統上都以大寫字母 P 來表示。 許多理論上可解但又不在集合 P 之中的問題，從實務的角度這些問題基本上是不可解，稱這些問題是不可解的（intractable）。,圖 12.11 常用數學式 n、lg n、n lg n 和 n2 的圖形,NP 問題 推銷員旅行問題：有一個推銷員，想要拜訪在不同城市的每一個客戶，但是不超過他的旅費預算。 執行前一刻仍無法事先決定指令的執行結果，這種指令是非既定的（nondeterministic），內含這類指令的演算法稱為非既定性演算法（nondeterministic algorithm）。 一個能夠以非既定演算法在多項式時間內解決的問題，稱為非既定性多項式問題（nondeterministic polynomial problem），或簡稱 NP 問題（NP problem）。 NP 完整性問題（NP-complete problems）。 其中一個問題的多項式時間解法一定可以同樣地提供其他在集合 NP 中的問題多項式時間解法。,12.6 公開金鑰密碼學,RSA 演算法（RSA algorithm） 這種加密系統稱為公開金鑰加密系統（public-key encryption system），加密金鑰也常被稱為公開金鑰（public key），而解密金鑰則被稱為私密金鑰（private key）（圖 12.13）。,圖 12.12 問題的分類圖,圖 12.13 公開金鑰加密系統,模數符號 “x mod m” 表示數值 x 除以 m 時所得的餘數。 對任意正整數 k 1 = mk(p1)(q1)(mod pq) RSA 公開金鑰密碼學 一套 RSA 公開金鑰加