計算機學科的根本問題課件

●從字源上考察：計：從言從十，有數(shù)數(shù)或計數(shù)的含義；算：從竹從具，指計算工具?！瘛冬F(xiàn)代漢語詞典》對計算的定義：根據(jù)已知數(shù)通過數(shù)學方法求得未知數(shù)。什么是計算●直觀的計算：數(shù)的加減乘除；函數(shù)的微分、積分；微分方程的求解；定理的證明推導等等?！裼嬎愕膶嵸|(zhì)：從一個符號串f（輸入）得出另一個符號串g（輸出）?！駭?shù)學概念→普適概念什么是計算計算的例子●從符號串“12+3”變換成符號串“15”——加法計算●符號串“x2”變換成符號串“2x”——微分；●

f表示一組公理和推導規(guī)則，g是一個定理，那么從f到g的一系列變換——定理g的證明；●符號串f代表一個英文句子，符號串g為含義相同的中文句子，那么從f到g的變換——英文翻譯成中文；這些變換有什么共同點？為什么他們都叫做計算？圖靈模型有限狀態(tài)控制器工作帶……●一條無限長的工作帶：工作帶上的每個單元可以存放一個符號；所有允許出現(xiàn)的符號屬于一個預先規(guī)定好的字母表。

圖靈模型有限狀態(tài)控制器工作帶……●一個讀寫頭：讀寫頭可以左移一個單元、右移一個單元或者保持不動。圖靈模型有限狀態(tài)控制器工作帶……●一個控制器：控制器在每個時刻處于一定的狀態(tài)，當讀寫頭從工作帶上讀出一個符號后，控制器就根據(jù)這個符號和當時的機器狀態(tài)，指揮讀寫頭進行讀寫或者移動，并決定是否改變機器狀態(tài)。計算與可計算所謂計算就是計算者（人或機器）對一條可以無限延長的工作帶上的符號串執(zhí)行指令，一步一步地改變工作帶上的符號串，經(jīng)過有限步驟，最后得到一個滿足預先規(guī)定的符號串的變換過程。什么樣的任務才是可計算的任務？這是計算機科學必須要回答的一個最基本的問題。這是關(guān)系到計算機能做什么、不能做什么的根本問題。類比：什么樣的衣服才是洗衣機可洗的？(q0,aaRq0)(q0,bxLq1)(q1,xxLq1)(q1,axRq2)(q1,BBHqN)(q2,xxRq2)程序假定n＝2，輸入符號串ω＝aabb用圖靈模型來計算控制器工作帶BaabbB指令機器狀態(tài)當前讀到的字符當前寫入的字符讀寫頭的動作R:右移L:左移H:不動下一機器狀態(tài)讀寫頭(q0,aaRq0)(q0,bxLq1)(q1,xxLq1)(q1,axRq2)(q1,B

BHqN)(q2,xxRq2)讀寫頭程序字母表：{a,b,B}用圖靈模型來計算控制器工作帶BaabbB讀寫頭掃描到符號a，則繼續(xù)往右走(q0,aaRq0)(q0,bxLq1)(q1,xxLq1)(q1,axRq2)(q1,B

BHqN)(q2,xxRq2)讀寫頭程序用圖靈模型來計算控制器工作帶BaabbB讀寫頭掃描到符號b，將當前單元寫入字符x，并使讀寫頭往左走，轉(zhuǎn)移到狀態(tài)q1。

(q0,aaRq0)(q0,bxLq1)(q1,xxLq1)(q1,axRq2)(q1,B

BHqN)(q2,xxRq2)讀寫頭程序用圖靈模型來計算控制器工作帶BaaxbB讀寫頭掃描到符號b，將當前單元寫入字符x，并使讀寫頭往左走，轉(zhuǎn)移到狀態(tài)q1。

(q0,aaRq0)(q0,bxLq1)(q1,xxLq1)(q1,axRq2)(q1,B

BHqN)(q2,xxRq2)讀寫頭程序用圖靈模型來計算控制器工作帶BaaxbB讀寫頭掃描到符號a，則把a改為標記x，并使讀寫頭往右走，轉(zhuǎn)移到狀態(tài)q2

(q0,aaRq0)(q0,bxLq1)(q1,xxLq1)(q1,axRq2)(q1,B

BHqN)(q2,xxRq2)讀寫頭程序用圖靈模型來計算控制器工作帶Bax

xbB讀寫頭掃描到標記x，則繼續(xù)往右走

(q2,bxLq1)(q2,BBLq3)(q3,xxLq3)(q3,aaH

qN)(q3,BBHq4)讀寫頭程序用圖靈模型來計算控制器工作帶Bax

xbB若讀寫頭掃描到符號b，則把b改為標記x，并使讀寫頭往左走，轉(zhuǎn)移到狀態(tài)q1

讀寫頭程序用圖靈模型來計算控制器工作帶Bax

x

xB若讀寫頭掃描到符號b，則把b改為標記x，并使讀寫頭往左走，轉(zhuǎn)移到狀態(tài)q1

(q0,aaRq0)(q0,bxLq1)(q1,xxLq1)(q1,axRq2)(q1,B

BHqN)(q2,xxRq2)讀寫頭程序用圖靈模型來計算控制器工作帶Bax

x

xB讀寫頭掃描到符號a，則把a改為標記x，并使讀寫頭往右走，轉(zhuǎn)移到狀態(tài)q2；

(q0,aaRq0)(q0,bxLq1)(q1,xxLq1)(q1,axRq2)(q1,B

BHqN)(q2,xxRq2)讀寫頭程序用圖靈模型來計算控制器工作帶Bx

x

x

xB讀寫頭掃描到標記x，則繼續(xù)往右走

(q0,aaRq0)(q0,bxLq1)(q1,xxLq1)(q1,axRq2)(q1,B

BHqN)(q2,xxRq2)讀寫頭程序用圖靈模型來計算控制器工作帶Bx

x

x

xB讀寫頭掃描到標記x，則繼續(xù)往右走

(q0,aaRq0)(q0,bxLq1)(q1,xxLq1)(q1,axRq2)(q1,B

BHqN)(q2,xxRq2)讀寫頭程序用圖靈模型來計算控制器工作帶Bx

x

x

xB讀寫頭掃描到空白符B，說明符號b已處理完畢，則把狀態(tài)改為q3，并使讀寫頭往左走

(q2,bxLq1)(q2,BBLq3)(q3,xxLq3)(q3,aaH

qN)(q3,BBHq4)讀寫頭程序用圖靈模型來計算控制器工作帶Bx

x

x

xB讀寫頭掃描到空白符B，說明符號b已處理完畢，則把狀態(tài)改為q3，并使讀寫頭往左走

(q2,bxLq1)(q2,BBLq3)(q3,xxLq3)(q3,aaH

qN)(q3,BBHq4)讀寫頭程序用圖靈模型來計算控制器工作帶Bx

x

x

xB讀寫頭掃描到標記x，則繼續(xù)往左走

(q2,bxLq1)(q2,BBLq3)(q3,xxLq3)(q3,aaH

qN)(q3,BBHq4)讀寫頭程序用圖靈模型來計算控制器工作帶Bx

x

x

xB讀寫頭掃描到空白符B，說明符號a和b已成對標記，轉(zhuǎn)移到狀態(tài)q4，達到接受狀態(tài)。

(q2,bxLq1)(q2,BBLq3)(q3,xxLq3)(q3,aaH

qN)(q3,BBHq4)從圖靈機我們看到了什么？●圖靈機在一定程度上反映了人類最基本的、最原始的計算能力，它的基本動作非常簡單、機械、確定。因此，有條件用真正的機器來實現(xiàn)圖靈機?！癯绦虿⒎潜仨氻樞驁?zhí)行，指令中關(guān)于下一狀態(tài)的指定，實際上表明指令可以不按程序中所表示的順序執(zhí)行。這意味著，雖然程序只能按線性順序來表示指令序列，但程序的實際執(zhí)行可以與表示的順序不同。●計算的對象、中間結(jié)果和最終結(jié)果都在帶上，程序則在控制器中。這意味著什么？思考：將做一件復雜事情的過程分解成許多簡單的、機械的步驟，你是否有過成功的經(jīng)驗？●計算機科學的研究目標是用計算機來求解人類所面臨的各種問題，問題本身的內(nèi)在復雜性決定了求解這個問題的算法的計算復雜性。●如何判定一個問題的復雜性？●如何區(qū)分一個問題是“易解”的還是“難解”的？●許多情況下，問題的內(nèi)在復雜性是很困難確定的，人們對許多問題至今無法確切地了解其內(nèi)在的計算復雜性。易解問題與難解問題●

將多項式時間復雜性作為易解問題和難解問題的分界線?！駥⒋嬖诙囗検綍r間算法的問題看作是易解問題，例如排序問題、串匹配問題等?！駥⑿枰笖?shù)時間算法解決的問題看作是難解問題，例如漢諾塔問題、TSP問題等。易解問題與難解問題●計算復雜性理論有兩個基本的論題：Turing論題和Cook論題，前者利用圖靈機指出了哪些問題是可計算的，后者則指出在可計算的問題中，只有在多項式時間內(nèi)可計算的問題才是實際可計算的?！馮uring論題中“有限次計算”是一個相當寬松的條件，即使需要計算幾個世紀的問題，在理論上也都是可計算的?！馛ook論題將可計算問題進一步劃分成兩類，一類是實際可計算的，稱為P類問題，另一類是實際不可計算的，稱為NP類問題。P類問題與NP類問題【定義1】設(shè)A是求解問題Π的一個算法，如果在算法的整個執(zhí)行過程中，每一步只有一個確定的選擇，則稱算法A是確定性算法?！径x2】可以用多項式時間的確定性算法來判定或求解的問題稱為P類問題。

理解起來，確定性算法在執(zhí)行過程中，每一個步驟都有一個確定的選擇，如果重新用同一輸入實例運行算法，所得的結(jié)果嚴格一致。例如我們前面介紹過的排序算法、歐幾里德算法等都屬于P類問題。事實上，P類問題就是易解問題。P類問題與NP類問題【定義3】設(shè)A是求解問題Π的一個算法，如果算法A以如下猜測并驗證的方式工作，則稱算法A是非確定性算法：（1）猜測階段：對問題的輸入實例產(chǎn)生一個任意字符串y，在算法的每一次運行時，串y的值可能不同，因此，猜測以一種非確定的形式工作。（2）驗證階段：用一個確定性算法驗證兩件事：首先，檢查在猜測階段產(chǎn)生的串y的形式是否合適，如果不合適，則算法停