1、計算機學科的基本概念計:數數或者進行計數算:算籌等工具計算:最原始的含義利用計算工具進行計數進一步，計算首先指數的加減乘除、平方、開方等初等運算，其次為函數的微分、積分等高等運算，以及方程的求解、代數的化簡、定理的證明等。1 計算與計算科學計算與計算科學n計算的本質是什么呢？n1930年代，哥德爾、丘奇、圖靈等數學家的工作，人們才弄清楚什么是計算的本質，什么是可計算的、什么是不可計算的等根本性問題。n抽象地說，所謂計算，就是從一個符號串f變換成另一個符號串g。n如，從符號串12+3變換成15就是一個加法計算。如果符號串f是X2，而符號串g是2x,從f到g的計算就是微分。n定理證明也如此。令f表

2、示一組公理和推導規則，令g是一個定理,那么從f到g的一系列變換就是定理g的證明。n文字翻譯也是計算，如f代表一個英文句子，而g為含意相同的中文句子，那么從f到g就是把英文翻譯成中文。計算的本質計算的本質n這些變換間有什么共同點？為什么把它們都叫做計算？n因為它們都是從己知符號(串)開始，一步一步地改變符號(串)，經過有限步驟，最后得到一個滿足預先規定的符號(串)的變換過程。計算的本質計算的本質計算的類型計算的類型n 從類型上講，主要有兩大類：數值計算和符號推導。n數值計算包括實數和函數的加減乘除、幕運算、開方運算、方程的求解等。n符號推導包括代數與各種函數的恒等式、不等式的證明，幾何命題的證明

3、等。n無論是數值計算還是符號推導,它們在本質上是等價的、一致的，即二者是密切關聯的，可以相互轉化，具有共同的計算本質。n隨著數學的發展,還可能出現新的計算類型。什么是可計算的什么是可計算的?可計算的可計算的描述方式：形式系統描述方式：形式系統例：狼羊白菜過河問題描述例：狼羊白菜過河問題描述n問題：農夫帶著狼、羊、白菜從河的左岸到河的右岸，農夫每次只能帶一樣東西多河，而且，沒有農夫看管，狼會吃羊，羊會吃白菜。n 提示：利用圖論解決問題。解：渡河的方法如下： 第一次，獵人把羊帶至右崖； 第二次，獵人單身回左岸，把白菜帶至右岸，此 時右岸有獵人，羊和白菜； 第三次，獵人再把羊帶回左岸，放下羊，把狼帶

4、至右岸，此時右岸有獵人，狼和白菜； 第四次，獵人單身回到左岸，最后把羊帶至右岸，便可完成渡河的任務。 n這是一個著名的古題，同樣也是“圖論”應用的經典例子。 首先，用字母P、L、C和X分別代表獵人、狼、羊和白菜，即P獵人，L狼，C羊，X白菜。用字母的組合表示左岸的情況。n開始時，狼、羊、白菜和獵人全在左岸，用LCXP表示；若左岸只剩下狼時，就用L表之，等等。n因為狼和羊、羊和白菜不能在無人監視的情況下共處，所以在整個渡河過程中，左岸始終不允許出現LC、CX、LP和XP所表示的情況。n仔細地列出左岸所允許出現的全部情況，它們是： LCXP，LCP，CXP，LXP，LX，CP，C，L，X，其中記號

5、表示左岸已空無所有。n用A表示LCXP，用B表示，那么只要在圖中找到一條由A到B的通道（折線），實際上就給出了一個滿足題意的過渡方法。狼羊白菜過河問題解法狼羊白菜過河問題解法n用1表示在左岸,0表示在右岸.n用頂點序號的二進制碼的0位表示農夫,1位表示狼,2位表示羊,3位表示菜.n那么,總共可能有16個頂點0-15.頂點0表示全在左岸,頂點15表示全在右岸.n有些頂點是不允許存在的,比如頂點3,表示農夫和狼在右岸,羊和菜在左岸,羊會吃掉菜.要把所有這類的頂點去掉.n在剩下的頂點中,要找出所有的可能的邊.比如頂點5表示農夫和羊在右,狼和菜在左,頂點4表示羊在右,那么就存在頂點5到頂點4的有向邊.

6、n至此,圖已構造完畢,問題就轉換成找到一條從頂點0到頂點15的合理路徑.編程作業：八皇后問題。n是19世紀著名數學家高斯1850年提出：n在8X8格的國際象棋上擺放八個皇后，使其不能互相攻擊，即任意兩個皇后都不能處于同一行、同一列或同一斜線上，問有多少種擺法。計算科學正是在探索計算科學正是在探索“什么是計算？什么是什么是計算？什么是可計算的？什么是不可計算的？可計算的？什么是不可計算的？”這這些根本些根本性問題的基礎上形成的。性問題的基礎上形成的。悖論舉例n某理發師發誓“要給所有不自已理發的人理發，不給所有自己理發的人理發”。n現在的問題是“誰為該理發師理發？”。n首先，若理發師給自己理發，那

7、他就是一個“自己理發的人”，依其誓言“他不給自己理發”；n其次，若“他不給自己理發”，依其誓言，他就必須“給自己理發” 圖靈等提出圖靈等提出可計算函數的模型對計算科學產生可計算函數的模型對計算科學產生深遠深遠影響。影響。圖靈機模型n1936年，圖靈向倫敦權威的數學雜志投了一篇論文，題為”論可計算及其在判定問題中的應用“。在這篇開創性的論文中，圖靈給”可計算性“下了一個嚴格的數學定義，并提出”圖靈機（Turing Machine）“的設想。n”圖靈機“并不是一種具體的機器，而是一種思想，可制造一種十分簡單但運算能力極強的計算裝置，用來計算所有能想象得到的可計算函數。圖靈機模型圖靈機模型圖靈機模型

8、圖靈機模型圖靈的基本思想是用機器來模擬人們用紙筆進行圖靈的基本思想是用機器來模擬人們用紙筆進行數學運算的過程，為了模擬人的這種運算過程，圖數學運算的過程，為了模擬人的這種運算過程，圖靈構造出一臺假想的機器，該機器由以下幾個部分靈構造出一臺假想的機器，該機器由以下幾個部分組成：組成： 有限狀態 控制器工作帶n 一條無限長的工作帶：工作帶上的每個單元可以存放一個符號；所有允許出現的符號屬于一個預先規定好的字母表。 n 一個讀寫頭：讀寫頭可以左移一個單元、右移一個單元或者保持不動。有限狀態 控制器工作帶n 一個控制器：控制器在每個時刻處于一定狀態，當讀寫頭從工作帶上讀出一個符號后，控制器就根據這個符

9、號和當時的機器狀態，指揮讀寫頭進行讀寫或者移動，并決定是否改變機器狀態。有限狀態 控制器工作帶計算與可計算計算與可計算所謂計算就是計算者（人或機器）對一條可以無限所謂計算就是計算者（人或機器）對一條可以無限延長的工作帶上的符號串執行指令，一步一步地改延長的工作帶上的符號串執行指令，一步一步地改變工作帶上的符號串，經過有限步驟，最后得到一變工作帶上的符號串，經過有限步驟，最后得到一個滿足預先規定的符號串的變換過程。個滿足預先規定的符號串的變換過程。 n控制器的命令可以用五元組表示： （q1,s1,s2,r,q2）q1:當前狀態；s1:讀寫頭從當前讀入的數據；s2:讀寫頭即將寫入當前方格的數據；r

10、:讀寫頭移動（右/左/不動）q2:新狀態n一旦圖靈機在運行中進入了一個狀態，而且這個狀態就是一個結束狀態，那么，圖靈機就停機，計算任務完成，此時帶上的內容就是計算輸出的結果。例：圖靈機MnM的字母表A=0,1,b,b表示空格。狀態集Q=q1,q2,q3,其中，q1為開始狀態，q3為終止狀態。M的程序（控制器的命令）如下：nq1 0 1 R q1nq1 1 0 R q1nq1 b b R q2nq2 b b L q3nq2 0 0 H q1nq1 1 1 H q1n其中，L,R,H分別表示讀寫頭向左移動一格、向右移動一格、保持不動三個基本操作。n假如此時M讀入是11100b0011，讀寫頭對準第

11、一個1，狀態為q1，請給出輸出結果。nb b b 1 1 0 0 b 0 0 1 1 b b bq1q1構造該圖靈機的基本思想：使讀寫頭往返移動，每往返移構造該圖靈機的基本思想：使讀寫頭往返移動，每往返移動一次，就成對地對輸入符號串動一次，就成對地對輸入符號串左端的一個左端的一個a和右端的一和右端的一個個b匹配并做標記匹配并做標記x。如果恰好把輸入符號串。如果恰好把輸入符號串的所有符號的所有符號都做了標記，說明左端的符號都做了標記，說明左端的符號a和右端的符號和右端的符號b的個數相等；的個數相等；否則，說明左端的符號否則，說明左端的符號a和右端的符號和右端的符號b的個數不相等，或的個數不相等，

12、或者符號者符號a和和b交替出現。交替出現。 例：例：構造一個識別符號串構造一個識別符號串anbn（n1）的圖靈機）的圖靈機控制器的操作指令（也就是程序）如下：(q0 a a R q0) (q0 b x L q1)(q1 x x L q1) (q1 a x R q2) (q1 B B H qN)(q2 x x R q2) (q2 b x L q1) (q2 B B L q3)(q3 x x L q3) (q3 a a H qN) (q3 B B H qF)控制器的指令序列對應一個狀態轉移圖，計算就是在執行指令的過程進行狀態的變化，也是變換符號的過程。 (q0, a a R q0) (q0, b

13、x L q1)(q1, x x L q1)(q1, a x R q2)(q1, B B H qN)(q2, x x R q2)程序假定假定n2，輸入符號串，輸入符號串aabb，圖靈機的工作過程如下：圖靈機的工作過程如下：控制器B a a b b B指令機器狀態當前讀到的字符當前寫入的字符讀寫頭的動作R:右移L:左移H:不動下一機器狀態讀寫頭計算機學科概論（第2版）清華大學出版社(q0, a a R q0) (q0, b x L q1)(q1, x x L q1)(q1, a x R q2)(q1, B B H qN)(q2, x x R q2)讀寫頭程序控制器B a a b b B讀寫頭掃描到

14、符號a，則繼續往右走 計算機學科概論（第2版）清華大學出版社(q0, a a R q0) (q0, b x L q1)(q1, x x L q1)(q1, a x R q2)(q1, B B H qN)(q2, x x R q2)讀寫頭程序控制器B a a b b B讀寫頭掃描到符號a，則繼續往右走 計算機學科概論（第2版）清華大學出版社(q0, a a R q0) (q0, b x L q1)(q1, x x L q1)(q1, a x R q2)(q1, B B H qN)(q2, x x R q2)讀寫頭程序控制器B a a b b B讀寫頭掃描到符號b，將當前單元寫入字符x，并使讀寫頭

15、往左走，轉移到狀態q1。 計算機學科概論（第2版）清華大學出版社(q0, a a R q0) (q0, b x L q1)(q1, x x L q1)(q1, a x R q2)(q1, B B H qN)(q2, x x R q2)讀寫頭程序控制器B a a x b B讀寫頭掃描到符號b，將當前單元寫入字符x，并使讀寫頭往左走，轉移到狀態q1。 計算機學科概論（第2版）清華大學出版社(q0, a a R q0) (q0, b x L q1)(q1, x x L q1)(q1, a x R q2)(q1, B B H qN)(q2, x x R q2)讀寫頭程序控制器B a a x b B讀寫

16、頭掃描到符號a，則把a改為標記x，并使讀寫頭往右走，轉移到狀態q2 計算機學科概論（第2版）清華大學出版社(q0, a a R q0) (q0, b x L q1)(q1, x x L q1)(q1, a x R q2)(q1, B B H qN)(q2, x x R q2)讀寫頭程序控制器B a x x b B讀寫頭掃描到符號a，則把a改為標記x，并使讀寫頭往右走，轉移到狀態q2 計算機學科概論（第2版）清華大學出版社(q0, a a R q0) (q0, b x L q1)(q1, x x L q1)(q1, a x R q2)(q1, B B H qN)(q2, x x R q2)讀寫頭

17、程序控制器B a x x b B讀寫頭掃描到標記x，則繼續往右走 計算機學科概論（第2版）清華大學出版社(q2, b x L q1) (q2, B B L q3)(q3, x x L q3)(q3, a a H qN)(q3, B B H q4)讀寫頭程序控制器B a x x b B若讀寫頭掃描到符號b，則把b改為標記x，并使讀寫頭往左走，轉移到狀態q1 計算機學科概論（第2版）清華大學出版社讀寫頭程序控制器B a x x x B若讀寫頭掃描到符號b，則把b改為標記x，并使讀寫頭往左走，轉移到狀態q1 (q0, a a R q0) (q0, b x L q1)(q1, x x L q1)(q1

18、, a x R q2)(q1, B B H qN)(q2, x x R q2)計算機學科概論（第2版）清華大學出版社讀寫頭程序控制器B a x x x B讀寫頭掃描到標記x，則繼續往左走 (q0, a a R q0) (q0, b x L q1)(q1, x x L q1)(q1, a x R q2)(q1, B B H qN)(q2, x x R q2)計算機學科概論（第2版）清華大學出版社讀寫頭程序控制器B a x x x B讀寫頭掃描到符號a，則把a改為標記x，并使讀寫頭往右走，轉移到狀態q2； (q0, a a R q0) (q0, b x L q1)(q1, x x L q1)(q1

19、, a x R q2)(q1, B B H qN)(q2, x x R q2)計算機學科概論（第2版）清華大學出版社讀寫頭程序控制器B x x x x B讀寫頭掃描到標記x，則繼續往右走 (q0, a a R q0) (q0, b x L q1)(q1, x x L q1)(q1, a x R q2)(q1, B B H qN)(q2, x x R q2)計算機學科概論（第2版）清華大學出版社讀寫頭程序控制器B x x x x B讀寫頭掃描到標記x，則繼續往右走 (q0, a a R q0) (q0, b x L q1)(q1, x x L q1)(q1, a x R q2)(q1, B B

20、H qN)(q2, x x R q2)計算機學科概論（第2版）清華大學出版社讀寫頭程序控制器B x x x x B讀寫頭掃描到標記x，則繼續往右走 (q0, a a R q0) (q0, b x L q1)(q1, x x L q1)(q1, a x R q2)(q1, B B H qN)(q2, x x R q2)計算機學科概論（第2版）清華大學出版社讀寫頭程序控制器B x x x x B讀寫頭掃描到空白符B，說明符號b已處理完畢，則把狀態改為q3，并使讀寫頭往左走 (q2, b x L q1) (q2, B B L q3)(q3, x x L q3)(q3, a a H qN)(q3, B

21、 B H q4)計算機學科概論（第2版）清華大學出版社讀寫頭程序控制器B x x x x B讀寫頭掃描到空白符B，說明符號b已處理完畢，則把狀態改為q3，并使讀寫頭往左走 (q2, b x L q1) (q2, B B L q3)(q3, x x L q3)(q3, a a H qN)(q3, B B H q4)計算機學科概論（第2版）清華大學出版社讀寫頭程序控制器B x x x x B讀寫頭掃描到標記x，則繼續往左走 (q2, b x L q1) (q2, B B L q3)(q3, x x L q3)(q3, a a H qN)(q3, B B H q4)計算機學科概論（第2版）清華大學出

22、版社讀寫頭程序控制器B x x x x B讀寫頭掃描到標記x，則繼續往左走 (q2, b x L q1) (q2, B B L q3)(q3, x x L q3)(q3, a a H qN)(q3, B B H q4)計算機學科概論（第2版）清華大學出版社讀寫頭程序控制器B x x x x B讀寫頭掃描到標記x，則繼續往左走 (q2, b x L q1) (q2, B B L q3)(q3, x x L q3)(q3, a a H qN)(q3, B B H q4)計算機學科概論（第2版）清華大學出版社讀寫頭程序控制器B x x x x B讀寫頭掃描到空白符B，說明符號a和b已成對標記，轉移到

23、狀態q4，達到接受狀態。 (q2, b x L q1) (q2, B B L q3)(q3, x x L q3)(q3, a a H qN)(q3, B B H q4)計算機學科概論（第2版）清華大學出版社從圖靈模型我們看到了什么？從圖靈模型我們看到了什么？n圖靈模型在一定程度上反映了人類最基本的、最原始的圖靈模型在一定程度上反映了人類最基本的、最原始的計算能力，它的基本動作非常簡單、機械、確定。因此，計算能力，它的基本動作非常簡單、機械、確定。因此，可以用真正的機器來實現圖靈機。可以用真正的機器來實現圖靈機。n程序并非必須順序執行，指令中關于下一狀態的指定，程序并非必須順序執行，指令中關于下

24、一狀態的指定，實際上表明指令可以不按程序中所表示的順序執行。這實際上表明指令可以不按程序中所表示的順序執行。這意味著，雖然程序只能按線性順序來表示指令序列，但意味著，雖然程序只能按線性順序來表示指令序列，但程序的實際執行可以與表示的順序不同。程序的實際執行可以與表示的順序不同。n計算的對象、中間結果和最終結果都在帶上，程序則在計算的對象、中間結果和最終結果都在帶上，程序則在控制器中。這意味著什么？控制器中。這意味著什么？為紀念圖靈對計算機的貢獻，美國計算機博物館為紀念圖靈對計算機的貢獻，美國計算機博物館于于19661966年設立了年設立了“圖靈獎圖靈獎”n圖靈機在計算機歷史上與”馮.諾依曼機“

25、齊名。n馮.諾依曼的助手弗蘭克曾在一封信中寫道：”.計算機的基本概念屬于圖靈。按照我的看法，馮.諾依曼的基本作用是使世界認識了由圖靈引入的計算機的基本概念.”59馮馮 諾依曼生平簡介諾依曼生平簡介60馮諾依曼/圖靈nStored Program conceptnMain memory storing programs and data主存儲器主存儲器：用于存儲數據和指令：用于存儲數據和指令nALU operating on binary data能夠操作二進制數的能夠操作二進制數的算術邏輯單元算術邏輯單元nControl unit interpreting instructions from

26、memory and executing控制器控制器：解釋內存中的指令并執行：解釋內存中的指令并執行nInput and output equipment operated by control unit由控制器操縱的由控制器操縱的輸入、輸出設備輸入、輸出設備6162計算機學科概論（第2版）清華大學出版社 存儲器 運算器 控制器 輸出設備 輸入設備1. 輸入設備：用于將程序（指令的集合，告訴計算機做什么以及怎么做的工作步驟）和數據從外界輸入計算機（存儲器），供計算機處理，主要任務是數字化。馮馮諾伊曼體系結構諾伊曼體系結構計算機學科概論（第2版）清華大學出版社 存儲器 運算器 控制器 輸出設備

27、輸入設備2. 存儲器：是計算機的記憶裝置，用于存放程序和數據。計算機學科概論（第2版）清華大學出版社 存儲器 運算器 控制器 輸出設備 輸入設備3. 運算器：是計算機對數據進行加工處理的部件，完成加、減、乘、除等基本算術運算和與、或、非等基本邏輯運算。計算機學科概論（第2版）清華大學出版社 存儲器 運算器 控制器 輸出設備 輸入設備4. 控制器：用于控制計算機各部件協調工作。控制器從存儲器中取出指令（告訴計算機做什么以及怎么做）并根據指令向有關部件發出控制命令。計算機學科概論（第2版）清華大學出版社 存儲器 運算器 控制器 輸出設備 輸入設備5. 輸出設備：用于將計算機的處理結果轉換成外界能夠

28、識別的文字、電壓等信息并輸出。計算機學科概論（第2版）清華大學出版社計算機：是能夠按照事先存儲的程序，自動、高速地對數據進行輸入、處理、輸出和存儲的系統。計算機=數據處理機數據結果整數、實數、文字、聲音、圖形、圖像等，甚至包括電壓、表情等整數、實數、文字、聲音、圖形、圖像等，甚至包括各種控制動作計算機學科概論（第2版）清華大學出版社 輸入：接收由輸入設備（如鍵盤、鼠標等）提供的數據。 處理：對數值、邏輯字符等各種類型的數據進行操作，按指定的方式進行轉換和加工。 輸出：將處理所產生的結果等送到相關輸出設備（如顯示器、打印機、繪圖儀等）。 存儲：可以存儲程序和數據。計算機學科概論（第2版）清華大學

29、出版社 馮諾依曼體系結構的主要特征：存儲程序。 存儲程序：事先編制好程序并將程序（指令的集合）和數據存入計算機的存儲器中，計算機在運行時就能自動、連續地從存儲器中逐條取出指令并執行，因此，計算機的工作過程就是運行程序的過程，也就是執行指令的過程。 指令：指示計算機執行特定操作（告訴計算機做什么以及如何做）的命令， 一條指令是計算機硬件可以執行的一步操作。 計算機學科概論（第2版）清華大學出版社（1）取指令（讀取）：控制器從存儲器中取出一條指令；（2）分析指令（譯碼）：控制器分析所取指令的操作碼，確定執行什么操作；（3）執行指令（執行）：控制器根據所取指令的含義，發出相應的操作命令，控制運算器進

30、行指定的運算。“讀取-譯碼-執行”指令執行周期，稱為機器周期。72小結：馮諾依曼結構的主要思想計算機學科概論（第2版）清華大學出版社n 計算機系統計算機系統由計算機硬件和計算機軟件構成；由計算機硬件和計算機軟件構成；n 計算機硬件計算機硬件：構成計算機系統的所有物理器件（集成電：構成計算機系統的所有物理器件（集成電路、電路板以及其他電子元件等）、部件和設備（控制路、電路板以及其他電子元件等）、部件和設備（控制器、運算器、存儲器、輸入器、運算器、存儲器、輸入/輸出設備等）的集合；輸出設備等）的集合；n 計算機軟件計算機軟件：用程序設計語言編寫的程序，以及運行程：用程序設計語言編寫的程序，以及運行

31、程序所需的文檔、數據的集合。序所需的文檔、數據的集合。n 計算機誕生之日起，人們探索的重點不僅在于建造運算計算機誕生之日起，人們探索的重點不僅在于建造運算速度更快、處理能力更強的計算機，而且在于開發能讓速度更快、處理能力更強的計算機，而且在于開發能讓人們更有效地使用這種計算設備的各種軟件。人們更有效地使用這種計算設備的各種軟件。 計算機學科概論（第2版）清華大學出版社重點：讓計算機能夠良好地運轉起來重點：解決真實世界的問題計算機學科概論（第2版）清華大學出版社物理層反映了在計算機上表示信息的方式，換言之，如何表示數值、字符、文字、聲音、圖形和圖像等信息，如何使門和電路控制電流實現數據的存儲和運

32、算。 二進制數字世界：信息（數據、指令）的編碼電子元件：門、邏輯電路、集成電路 硬件計算機學科概論（第2版）清華大學出版社機器層反映了構成計算機硬件的主要部件、部件的主要性能以及這些部件之間的連接方式。 二進制數字世界：信息（數據、指令）的編碼電子元件：門、邏輯電路、集成電路 計算機部件：存儲器、CPU、輸入/輸出設備 硬件計算機學科概論（第2版）清華大學出版社系統軟件用于擴展計算機的硬件功能，維護整個計算機系統，為應用開發人員提供平臺支持。 計算機硬件 硬件軟件工具軟件、語言翻譯程序 操作系統：計算機的管家 系統軟件層閱讀：奠定計算機理論基礎的重要人物閱讀：奠定計算機理論基礎的重要人物和思想

33、和思想n布爾及邏輯代數n香農及計算機開關電路n圖靈及圖靈機、圖靈測試n阿塔納索夫及ABC計算機n維納及計算機設計五原則n馮.諾依曼及馮.諾依曼結構思考題：思考題：2 什么是計算機學科n計算機學科的定義計算機學科的定義n計算機學科是研究計算機的設計、制造和利用計計算機學科是研究計算機的設計、制造和利用計算機進行信息獲取、表示、存儲、處理、控制等算機進行信息獲取、表示、存儲、處理、控制等的理論、原則、方法和技術的學科，包括科學和的理論、原則、方法和技術的學科，包括科學和技術兩方面。技術兩方面。計算機科學側重于研究現象、揭示規律。計算機科學側重于研究現象、揭示規律。計算機技術側重于研制計算機和研究使

34、用計算機進行計算機技術側重于研制計算機和研究使用計算機進行信息處理的方法和手段。信息處理的方法和手段。科學與技術相輔相成，相互作用。科學與技術相輔相成，相互作用。計算機學科還具有較強的工程性計算機學科還具有較強的工程性理論教學與實踐教學并重。理論教學與實踐教學并重。基礎理論知識扎實基礎理論知識扎實/ /動手能力強。動手能力強。計算機學科是科學性計算機學科是科學性/ /工程性工程性/ /技術性的統一技術性的統一側重點不同的學科分支側重點不同的學科分支計算機科學計算機科學/ /計算機工程計算機工程/ /軟件工程軟件工程/ /信息技術。信息技術。計算機學科和數學密切相關計算機學科和數學密切相關 3

35、計算機學科的經典問題n程序設計方法學程序設計方法學n圖論圖論n進程同步進程同步n計算復雜性計算復雜性nNP問題問題n組合爆炸組合爆炸n人工智能人工智能http:/ 4 計算機學科的計算機學科的根本根本問題問題計算機學科概論（第2版）清華大學出版社不可計算問題的典型例子不可計算問題的典型例子 n停機問題停機問題。給定一個計算機程序和一個特定的輸入，判斷。給定一個計算機程序和一個特定的輸入，判斷該程序是否可以停機。如果停機問題是可計算的，那么編該程序是否可以停機。如果停機問題是可計算的，那么編譯系統就能夠在運行程序之前檢查出程序中是否有死循環，譯系統就能夠在運行程序之前檢查出程序中是否有死循環，事

36、實上，當一個程序處于死循環時，系統無法確切地知道事實上，當一個程序處于死循環時，系統無法確切地知道它只是一個很慢的程序，還是一個進入死循環的程序。它只是一個很慢的程序，還是一個進入死循環的程序。n判斷一個程序中是否包含計算機病毒判斷一個程序中是否包含計算機病毒。實際的病毒檢測程。實際的病毒檢測程序做得很好，通常能夠確定一個程序中是否包含特定的計序做得很好，通常能夠確定一個程序中是否包含特定的計算機病毒，至少能夠檢測現在已經知道的那些病毒，但是算機病毒，至少能夠檢測現在已經知道的那些病毒，但是心懷惡意的人總能開發出病毒檢測程序還不能夠識別出來心懷惡意的人總能開發出病毒檢測程序還不能夠識別出來的新

37、病毒，換言之，不存在一個病毒檢測程序，能夠檢測的新病毒，換言之，不存在一個病毒檢測程序，能夠檢測出所有未來的新病毒。出所有未來的新病毒。計算機學科概論（第2版）清華大學出版社易解問題與難解問題易解問題與難解問題 認識計算機學科認識計算機學科易解問題易解問題n 理論上可計算的問題不一定是實際可計算的。理論上可計算的問題不一定是實際可計算的。n Cook論題論題：一個問題是實際可計算的當且僅當它在圖靈機：一個問題是實際可計算的當且僅當它在圖靈機上經過上經過多項式步驟多項式步驟得到正確的結果。得到正確的結果。n 易解問題易解問題：可以在多項式時間內求解的問題，這類問題在：可以在多項式時間內求解的問題

38、，這類問題在可以接受的時間內實現問題求解。可以接受的時間內實現問題求解。n 難解問題難解問題：需要指數時間求解的問題，這類問題的計算時：需要指數時間求解的問題，這類問題的計算時間隨著問題規模（輸入量的大小）的增長而快速增長，即間隨著問題規模（輸入量的大小）的增長而快速增長，即使中等規模的輸入，其計算時間也是以世紀來衡量的。使中等規模的輸入，其計算時間也是以世紀來衡量的。計算機學科概論（第2版）清華大學出版社難解問題的典型例子難解問題的典型例子漢諾塔問題：在世界剛被創建的時候有一座寶塔（塔漢諾塔問題：在世界剛被創建的時候有一座寶塔（塔A），其），其上有上有64個金碟。所有碟子按從大到小的次序從塔

39、底堆放至塔頂。個金碟。所有碟子按從大到小的次序從塔底堆放至塔頂。緊挨著這座塔有另外兩個寶塔（塔緊挨著這座塔有另外兩個寶塔（塔B和塔和塔C）。從世界創始之）。從世界創始之日起，婆羅門的牧師們就一直在試圖把塔日起，婆羅門的牧師們就一直在試圖把塔A上的碟子移動到塔上的碟子移動到塔C上去，其間借助于塔上去，其間借助于塔B的幫助。每次只能移動一個碟子，任的幫助。每次只能移動一個碟子，任何時候都不能把一個碟子放在比它小的碟子上面。當牧師們完何時候都不能把一個碟子放在比它小的碟子上面。當牧師們完成任務時，世界末日也就到了。成任務時，世界末日也就到了。計算機學科概論（第2版）清華大學出版社ABC難解問題的典型

40、例子難解問題的典型例子計算機學科概論（第2版）清華大學出版社ABC難解問題的典型例子難解問題的典型例子計算機學科概論（第2版）清華大學出版社難解問題的典型例子難解問題的典型例子1212221222)0(21)1)2(2(21)1(2)(121121- -= =+ + + + += =+ + + + + += = =+ + +- -= =+ +- -= =- - -nnnnhnhnhnhh(64) = 264-1=18,446,744,073,709,551,615 如果每秒移動一次，則僧侶們一刻不停地來回移動，則需要花費5849億年的時間；假定計算機以每秒1000萬個碟子的速度進行移動，則需要

41、花費58,490年的時間。計算機學科概論（第2版）清華大學出版社證比求易證比求易認識計算機學科認識計算機學科NPNP問題問題n 通常來說，求解一個問題往往比較困難，但驗證一個問題相對來說就比較容易，也就是證比求易。n 從是否可以被驗證的角度，計算復雜性理論將難解問題劃分為NP問題和非NP問題。n NP問題：可以在多項式時間內驗證的問題。n NP完全問題：NP問題中有大量問題都具有這樣的特性：可以多項式時間內得到驗證，但是不知道是否可以在多項式時間內得到求解，同時，我們不能證明這些問題中的任何一個無法在多項式時間內得到求解，這類問題稱為NP完全問題。 計算機學科概論（第2版）清華大學出版社NP完

42、全問題的典型例子完全問題的典型例子TSP問題（又稱貨郎擔問題、郵遞員問題、售貨員問題（又稱貨郎擔問題、郵遞員問題、售貨員問題）是數學家克克曼于問題）是數學家克克曼于19世紀初提出的一個數學世紀初提出的一個數學問題，是指旅行家要旅行問題，是指旅行家要旅行n個城市然后回到出發城個城市然后回到出發城市，要求各個城市經歷且僅經歷一次，并要求所走市，要求各個城市經歷且僅經歷一次，并要求所走的路程最短。的路程最短。計算機學科概論（第2版）清華大學出版社8abdc23571否否 18 18a ad dc cb ba a6 6否否 23 23a ad db bc ca a5 5是是 11 11a ac cd

43、db ba a4 4否否 23 23a ac cb bd da a3 3是是 11 11a ab bd dc ca a2 2否否 18 18a ab bc cd da a1 1是否最短是否最短路徑長度路徑長度路徑路徑序號序號NPNP完全問題的典型例子完全問題的典型例子對于具有 n 個頂點的TSP問題，可能的解有 (n-1)!/2個。 10城市的TSP問題有大約180,000個可能解。 20城市的TSP問題有大約60,000,000,000,000,000個可能解。 50城市的TSP問題有大約1062個可能解。計算機學科概論（第2版）清華大學出版社n 考慮考慮TSP問題的驗證形式：給定一個正整數

44、問題的驗證形式：給定一個正整數k，是否存在一，是否存在一條路徑長度小于條路徑長度小于k的簡單回路。的簡單回路。n 假設有一個可以同時測試所有可能答案的超級并行計算機，假設有一個可以同時測試所有可能答案的超級并行計算機，首先生成首先生成TSP問題的所有可能的回路，然后并行驗證所有可問題的所有可能的回路，然后并行驗證所有可能的答案，即把各個邊的代價加起來，驗證路徑長度是否小能的答案，即把各個邊的代價加起來，驗證路徑長度是否小于于k。顯然，這可以在多項式時間內得到驗證。顯然，這可以在多項式時間內得到驗證。NP完全問題的典型例子完全問題的典型例子計算機學科概論（第2版）清華大學出版社n 科學問題的提出

45、和解決是任何一個學科持續發展的動力，科學問題的提出和解決是任何一個學科持續發展的動力，一個學科如果沒有科學問題需要解決，這個學科的生命也就一個學科如果沒有科學問題需要解決，這個學科的生命也就該結束了。該結束了。 n 在計算機學科各個分支學科方向的發展進程中，存在一些在計算機學科各個分支學科方向的發展進程中，存在一些在表現形式上雖然不同，但在科學哲學的解釋下本質上是相在表現形式上雖然不同，但在科學哲學的解釋下本質上是相同或相近的問題，即學科研究與發展普遍關心的基本問題。同或相近的問題，即學科研究與發展普遍關心的基本問題。 什么是科學問題什么是科學問題5.認識計算機學科認識計算機學科科學問題科學問

46、題計算機學科概論（第2版）清華大學出版社為了實現自動計算，人們首先想到要發明和制造自動計算機器，為了實現自動計算，人們首先想到要發明和制造自動計算機器，不僅要在理論上提供計算的平臺不僅要在理論上提供計算的平臺觀察和描述計算的起點，觀察和描述計算的起點，而且要實際制造出能夠真正運行的自動計算機器。進一步地，而且要實際制造出能夠真正運行的自動計算機器。進一步地，從廣義計算的概念出發，計算的平臺在使用上還必須方便，例從廣義計算的概念出發，計算的平臺在使用上還必須方便，例如，計算模型、計算機體系結構、實際的計算機系統、系統軟如，計算模型、計算機體系結構、實際的計算機系統、系統軟件和工具軟件、高級程序設

47、計語言、軟件開發工具與環境等都件和工具軟件、高級程序設計語言、軟件開發工具與環境等都是圍繞這一基本問題展開的，其核心是是圍繞這一基本問題展開的，其核心是計算的能行性計算的能行性。 計算的平臺與環境問題計算的平臺與環境問題 計算機學科概論（第2版）清華大學出版社哲學家共餐問題與計算機資源管理哲學家共餐問題與計算機資源管理 哲學家的生活進程可表示為：（1）思考問題；（2）俄了停止思考，左手拿起一只筷子（如果左側哲學家已持有它，則等待）；（3）右手拿起一只筷子（如果右側哲學家已持有它，則等待）；（4）進餐；（5）放下左手筷子；（6）放下右手筷子；（7）重新回到狀態（1）思考問題； 計算機學科概論（第

48、2版）清華大學出版社程序并發執行時進程同步的兩個關鍵問題程序并發執行時進程同步的兩個關鍵問題死鎖死鎖和和饑餓饑餓：（1）按哲學家的生活進程，當所有的哲學家都同時拿起左）按哲學家的生活進程，當所有的哲學家都同時拿起左手筷子時，則所有哲學家都將拿不到右手筷子，并處于等待手筷子時，則所有哲學家都將拿不到右手筷子，并處于等待狀態，那么，哲學家都將無法進餐，最終餓死。狀態，那么，哲學家都將無法進餐，最終餓死。（2）將哲學家的生活進程修改為當拿不到右手筷子時，就）將哲學家的生活進程修改為當拿不到右手筷子時，就放下左手筷子。但是，可能在一個瞬間，所有的哲學家都同放下左手筷子。但是，可能在一個瞬間，所有的哲學

49、家都同時拿起左手筷子，則自然拿不到右手筷子，于是都同時放下時拿起左手筷子，則自然拿不到右手筷子，于是都同時放下左手筷子，等一會，又同時拿起左手筷子，如此重復下去，左手筷子，等一會，又同時拿起左手筷子，如此重復下去，則所有的哲學家都將無法進餐。則所有的哲學家都將無法進餐。計算機學科概論（第2版）清華大學出版社很久以前，有一個年輕的國王向鄰國一位聰明美麗的公主求婚，公主出了這樣一道題：求出48 770 428 433 377 171的一個因子，若國王能在一天之內求出答案，便接受國王的求婚。 證比求易與并行計算證比求易與并行計算 嫁給我好嗎？那你回答一個問題吧。計算機學科概論（第2版）清華大學出版社

50、國王回去后立即開始逐個數地進行試除，總共試了三萬多個數，還是沒有結果。國王向公主求情，公主將答案相告：223 092 827是它的一個因子，國王很快就驗證了這個數的確能除盡48 770 428 433 377 171。告訴你吧，223 092 827是它的一個因子再給我一次機會吧！計算機學科概論（第2版）清華大學出版社國王立即回國，并向時任宰相的大數學家求教，宰相在仔細地思考后認為這個數為17位，如果這個數存在因子，則最小的一個因子不會超過9位。于是，他給國王出了一個主意：按自然數的順序給全國的老百姓每人編一個號發下去，等公主給出數后，立即將它通報全國，讓每個老百姓用自己的編號去除這個數，除盡

51、了立即上報，賞金萬兩。最后國王用這個辦法求婚成功。國王使用的是串行算法，宰相提出的是一種并行算法。計算機學科概論（第2版）清華大學出版社一個問題在判定為可計算問題后，為求解這個問題，必須給出實際解決該問題的操作序列，同時還必須確保操作序列的資源（時間和空間）消耗是合理的。圍繞這一問題，計算機學科發展了大量與之相關的研究內容與分支學科方向。例如，集成電路技術、數字系統邏輯設計、自動布線技術、RISC技術、數值計算方法、算法設計技術、計算復雜性理論、密碼學、演化計算、人工智能等都是圍繞這一基本問題展開的，其核心是計算的效率。計算過程的能行操作與效率問題計算過程的能行操作與效率問題 計算機學科概論（

52、第2版）清華大學出版社背包問題：給定n種物品和一個容量為C的背包，物品i的重量是wi，其價值為vi，如何選擇裝入背包的物品，使得裝入背包中物品的總價值最大? 背包問題與貪心法背包問題與貪心法 至少有三種看似合理的貪心策略：（1）選擇價值最大的物品。但背包容量可能消耗得太快，使得裝入背包的物品個數減少，從而不能保證目標函數達到最大。（2）選擇重量最輕的物品。但背包的價值沒能保證迅速增長，從而不能保證目標函數達到最大。（3）選擇單位重量價值最大的物品。在背包價值增長和背包容量消耗兩者之間尋找平衡。計算機學科概論（第2版）清華大學出版社例如，有3個物品，其重量分別是20, 30, 10，價值分別為60, 120, 50，背包的容量為50， 背包問題與貪心法背包問題與貪心法 計算機學科概論（第2版）清華大學出版社圖靈測試與人工智能圖靈測試與人工智能 提問者回答者A 回答者B “機器能思考嗎？” “如何才能知道何時是成功了呢？” 如果機器在一場會話中成功