1、精選ppt1第二章第二章 計算機科學的基本概念和基本知識計算機科學的基本概念和基本知識2.1 2.1 計算模型與二進制計算模型與二進制 數學不等于計算，但數學確實起源于對計算的研究。數學不等于計算，但數學確實起源于對計算的研究。 數學、計算模型（計算方法、數學機器）、形式化與形數學、計算模型（計算方法、數學機器）、形式化與形式化方法式化方法 我們說，形式是事物的內容存在的外在方式、形狀和結我們說，形式是事物的內容存在的外在方式、形狀和結構的總和。所謂形式化是將事物的內容與形式相分離，用事構的總和。所謂形式化是將事物的內容與形式相分離，用事物的某種形式來表示事物。形式化方法是在對事物描述形式物的

2、某種形式來表示事物。形式化方法是在對事物描述形式化的基礎上，通過研究事物的形式變化規律來研究事物變化化的基礎上，通過研究事物的形式變化規律來研究事物變化規律的全體方法的總稱。規律的全體方法的總稱。1.1.1 1.1.1 計算模型與圖靈機計算模型與圖靈機 所謂計算模型是刻劃計算這一概念的一種抽象的形式系所謂計算模型是刻劃計算這一概念的一種抽象的形式系統或數學系統，而算法是對計算過程步驟（或狀態的一種刻統或數學系統，而算法是對計算過程步驟（或狀態的一種刻精選ppt2劃，是計算方法的一種能行實現方式。在計算機科學中，我劃，是計算方法的一種能行實現方式。在計算機科學中，我們通常所說的計算模型，并不是指

3、在其靜態或動態數學描述們通常所說的計算模型，并不是指在其靜態或動態數學描述基礎上建立求解某一基礎上建立求解某一( (類類) )問題計算方法的數學模型，而是指問題計算方法的數學模型，而是指具有狀態轉換特征，能夠對所處理的對象的數據或信息進行具有狀態轉換特征，能夠對所處理的對象的數據或信息進行表示、加工、變換、輸出的數學機器。由于觀察計算的角度表示、加工、變換、輸出的數學機器。由于觀察計算的角度不同，產生了各種不同的計算模型。不同，產生了各種不同的計算模型。 遞歸函數、遞歸函數、TuringTuring機等機等 (1) s(x)(1) s(x)x x1 1 （后繼函數）（后繼函數） (2) o(x

4、)(2) o(x)0 0 （零函數）（零函數） (3) U(3) Uj j(n)(n)(x(x1 1，x x2 2，x xn n) )x xj j （射影函數）（射影函數） 由初始函數和有限次使用算子可以構造各種復雜的遞歸由初始函數和有限次使用算子可以構造各種復雜的遞歸函數，或者可計算函數。函數，或者可計算函數。 圖靈機的示意圖圖靈機的示意圖精選ppt3控制器的命令可表示為：控制器的命令可表示為： （狀態，符號）（狀態，符號）（寫符號，移動，狀態）；（寫符號，移動，狀態）； 控制器控制器 一旦圖靈機在運行中進入了一個狀態，而且這個狀態一旦圖靈機在運行中進入了一個狀態，而且這個狀態是一個結束狀態

5、，那么，圖靈機就停機，計算任務宣告完是一個結束狀態，那么，圖靈機就停機，計算任務宣告完成，此時帶上的內容就是計算的輸出結果。成，此時帶上的內容就是計算的輸出結果。精選ppt4 例例1 1 M M的字母表的字母表A A00，1 1，bb，b b表示空格。狀態集表示空格。狀態集Q Qqq1 1，q q2 2，q q3 3 ，其中，指定，其中，指定q q1 1是開始狀態，是開始狀態，q q3 3是終止狀態。是終止狀態。 M M的程序（控制器的命令）如下：的程序（控制器的命令）如下： q q1 1 0 1 R q 0 1 R q1 1； q q1 1 1 0 R q 1 0 R q1 1； q q1

6、1 b b R q b b R q2 2； q q2 2 b b L q b b L q3 3； q q2 2 0 0 H q 0 0 H q1 1； q q2 2 1 1 H q 1 1 H q1 1； 對圖靈機的工作過程從不同的角度考察，可以給予不對圖靈機的工作過程從不同的角度考察，可以給予不同的解釋。同的解釋。 第一第一，把圖靈機看作識別器，即判斷帶子上最初的內，把圖靈機看作識別器，即判斷帶子上最初的內精選ppt5容能否被圖靈機所接受。假定圖靈機從左向右掃描完帶子上容能否被圖靈機所接受。假定圖靈機從左向右掃描完帶子上的內容后停機則為接受，否則為不接受。的內容后停機則為接受，否則為不接受。

7、 例例2 2 一臺圖靈機可以設計成識別下面的序列：一臺圖靈機可以設計成識別下面的序列： 1000110, 10011101, 0101010111000110, 10011101, 010101011。 第二第二，把圖靈機看作生成器，對給定的輸入集合，考察，把圖靈機看作生成器，對給定的輸入集合，考察輸出集合，并研究輸入輸出集合性質之間的關系，這就研究輸出集合，并研究輸入輸出集合性質之間的關系，這就研究了圖靈機的生成能力。了圖靈機的生成能力。 例例3 3 設一臺圖靈機的輸入集合為設一臺圖靈機的輸入集合為InIn11n n0 0n nnNnN，可設，可設計一臺圖靈機，對給定的輸入集合計一臺圖靈機，

8、對給定的輸入集合InIn，得到輸出集合，得到輸出集合OutOut00n n1 1n nnNnN。其中，。其中，N N是全體自然數的集合。是全體自然數的集合。 第三第三，把圖靈機看作計算器，相當于一個函數。圖靈機，把圖靈機看作計算器，相當于一個函數。圖靈機的輸入是函數的自變量的值，圖靈機的輸出是函數的值。的輸入是函數的自變量的值，圖靈機的輸出是函數的值。 例例4 4 圖靈機可以計算下列函數：圖靈機可以計算下列函數：精選ppt6 (1) s(x) (1) s(x)x x1 1； (2) o(x)(2) o(x)0 0； (3) A(0(3) A(0，y)y)y y1 1， A(xA(x1 1，0)

9、0)A(xA(x，1)1)， A(xA(x1 1，y y1)1)A(xA(x，A(xA(x1 1，y)y)。 第一和第二個函數讀者不難從圖靈機的定義出發感悟第一和第二個函數讀者不難從圖靈機的定義出發感悟到它們是圖靈機可以計算的函數，而第三個函數就比較復到它們是圖靈機可以計算的函數，而第三個函數就比較復雜，一時難于判斷。順便提一下，第三個函數叫做阿克曼雜，一時難于判斷。順便提一下，第三個函數叫做阿克曼函數，它是阿克曼（函數，它是阿克曼（W.AckermannW.Ackermann）在研究原始遞歸函數和）在研究原始遞歸函數和遞歸函數的關系時給出的。這個函數在計算理論中具有重遞歸函數的關系時給出的。

10、這個函數在計算理論中具有重要價值。事實上，圖靈機還可以計算形式上比第三個函數要價值。事實上，圖靈機還可以計算形式上比第三個函數更復雜的函數。更復雜的函數。 沿著這樣一種思路，圖靈機被證明具有很強的計算能沿著這樣一種思路，圖靈機被證明具有很強的計算能力，它與力，它與3030年代發展的遞歸函數論（一種能行可計算性理年代發展的遞歸函數論（一種能行可計算性理精選ppt7論）中一類最一般的可計算函數（部分遞歸函數或部分可論）中一類最一般的可計算函數（部分遞歸函數或部分可計算函數）在計算表達能力上是等價的。然而，圖靈機簡計算函數）在計算表達能力上是等價的。然而，圖靈機簡潔的構造和運行原理隱含了存儲程序的原

11、始思想，深刻地潔的構造和運行原理隱含了存儲程序的原始思想，深刻地揭示了現代通用電子數字計算機最核心的內容。揭示了現代通用電子數字計算機最核心的內容。 圖靈獎圖靈獎 2.1.2 2.1.2 二進制二進制 也許是圖靈機讀寫帶上只出現兩個符號啟發了研究者，也許是圖靈機讀寫帶上只出現兩個符號啟發了研究者，在當時的技術條件下，從便于元器件的設計和制造考慮，在當時的技術條件下，從便于元器件的設計和制造考慮，計算機的研制很自然地選擇了二進制。后來的實踐也證明計算機的研制很自然地選擇了二進制。后來的實踐也證明了這種選擇具有極大的優點。了這種選擇具有極大的優點。 十進制數的表示十進制數的表示 例如，例如，199

12、7.6301997.630這個數可以寫成：這個數可以寫成： 1997.6301997.6301 110103 39 910102 29 910101 17 710100 0 6 61010-1-13 31010-2-20 01010-3-3精選ppt8 一般地，任何一個十進制數一般地，任何一個十進制數S S都可以表示為：都可以表示為： S Sk kn nk kn-1n-1 k k0 0. k. k-m-m k kn n1010n nk kn-1n-11010n-1n-1k k0 010100 0k k-m-m1010-m-m -m -m k ki i1010i i i in n其中，其中，10

13、10稱為十進制的基數稱為十進制的基數,k,ki i0,1,2,3,4,5,6,7,8,90,1,2,3,4,5,6,7,8,9，m m，n n為正整數。小數點的位置不言自明。為正整數。小數點的位置不言自明。 二進制和十進制一樣，是一種數制，它用于表示數的符二進制和十進制一樣，是一種數制，它用于表示數的符號（數字）由于在書寫中的位置不同而具有不同的值。二進號（數字）由于在書寫中的位置不同而具有不同的值。二進制表示數的符號只有兩個，即制表示數的符號只有兩個，即0 0和和1 1，其數值與十進制中的，其數值與十進制中的0 0和和1 1相同。此外，與十進制不同之處在于二進制數是逢二進一。相同。此外，與十

14、進制不同之處在于二進制數是逢二進一。精選ppt9 例如，十進制數與二進制數中的一些可作如下對應：例如，十進制數與二進制數中的一些可作如下對應： 十進制十進制 二進制二進制 (0) (0)(0) (0) (1) (1) (1) (1) (2) (10) (2) (10) (3) (11) (3) (11) (4) (100) (4) (100) (5) (101) (5) (101) (9) (1001) (9) (1001) (10) (1010) (10) (1010) 一般地，任何一個二進制數一般地，任何一個二進制數S S都可以表示為：都可以表示為：精選ppt10 S Sk kn nk k

15、n-1n-1 k k0 0. k. k-m-m k kn n2 2n nk kn-1n-12 2n-1n-1k k0 02 20 0k k-m-m2 2-m-m -m -m k ki i2 2i i i in n 其中，其中，2 2稱為二進制的基數，稱為二進制的基數，k ki i0,1,m,n0,1,m,n為正整數。為正整數。 進一步，讀者可從十進制數和二進制數的一般表示公進一步，讀者可從十進制數和二進制數的一般表示公式得到啟發，將這種表示推廣到更一般的任意進制，不同式得到啟發，將這種表示推廣到更一般的任意進制，不同之處只是基數不一樣。之處只是基數不一樣。 二進制的運算規則比十進制的運算規則簡

16、單得多。二進制的運算規則比十進制的運算規則簡單得多。只只要建立兩種進制的數據之間的轉換方法，那么，二進制將要建立兩種進制的數據之間的轉換方法，那么，二進制將具有更多的優勢。具有更多的優勢。計算機的理論基礎是邏輯和代數。當二計算機的理論基礎是邏輯和代數。當二進制與同樣只使用進制與同樣只使用“真真”和和“假假”兩個值的邏輯代數建立兩個值的邏輯代數建立了聯系后，這就為計算機的邏輯設計提供了便利的工具。了聯系后，這就為計算機的邏輯設計提供了便利的工具。精選ppt11 2.2 2.2 存儲程序式計算機的基本結構與工作原理存儲程序式計算機的基本結構與工作原理 圖靈機的出現為現代計算機的發明提供了重要的思想

17、。圖靈機的出現為現代計算機的發明提供了重要的思想。圖靈機的帶子可以看成是計算機的存儲設備，數據可以存圖靈機的帶子可以看成是計算機的存儲設備，數據可以存儲在上面，也可以根據需要擦去。圖靈機的命令相當于一組儲在上面，也可以根據需要擦去。圖靈機的命令相當于一組事先設計、存儲好了的程序，它們在控制器安排下，決定讀事先設計、存儲好了的程序，它們在控制器安排下，決定讀寫頭的每一步操作。這樣一種數學機器，如果不考慮它的實寫頭的每一步操作。這樣一種數學機器，如果不考慮它的實用性，就思想和原理而言，確實包含了存儲程序的重要思想。用性，就思想和原理而言，確實包含了存儲程序的重要思想。 程序與存儲程序式計算機程序與

18、存儲程序式計算機 圖靈機誕生后不到十年，在以馮圖靈機誕生后不到十年，在以馮諾依曼為代表的一批諾依曼為代表的一批科學家的努力下，現代存儲程序式電子數字計算機的基本結科學家的努力下，現代存儲程序式電子數字計算機的基本結構與工作原理被確定下來。它主要由如下的五部分組成（見構與工作原理被確定下來。它主要由如下的五部分組成（見P8P8圖）：圖）： 存儲器，運算器，控制器，輸入設備，輸出設備存儲器，運算器，控制器，輸入設備，輸出設備精選ppt12 在學科的發展歷程中，習慣上，人們將不帶有軟件系在學科的發展歷程中，習慣上，人們將不帶有軟件系統的存儲程序式電子數字計算機系統稱為硬件裸機，將硬統的存儲程序式電子

19、數字計算機系統稱為硬件裸機，將硬件裸機，參與構成硬件裸機的各類部件及其研究范疇統稱件裸機，參與構成硬件裸機的各類部件及其研究范疇統稱為硬件（方向）。為硬件（方向）。 2.3 2.3 數字邏輯與集成電路數字邏輯與集成電路 數字邏輯數字邏輯是數字電路邏輯設計的簡稱，其內容是應用是數字電路邏輯設計的簡稱，其內容是應用數字電路進行數字系統邏輯設計。電子數字計算機是由具數字電路進行數字系統邏輯設計。電子數字計算機是由具有各種邏輯功能的邏輯部件組成的，這些邏輯部件按其結有各種邏輯功能的邏輯部件組成的，這些邏輯部件按其結構可分為組合邏輯電路和時序邏輯電路。構可分為組合邏輯電路和時序邏輯電路。組合邏輯電路組合

20、邏輯電路是是由與門、或門和非門等門電路組合形成的邏輯電路；由與門、或門和非門等門電路組合形成的邏輯電路；時序時序邏輯電路邏輯電路是由觸發器和門電路組成的具有記憶能力的邏輯是由觸發器和門電路組成的具有記憶能力的邏輯電路。有了組合邏輯電路和時序邏輯電路，再進行合理的電路。有了組合邏輯電路和時序邏輯電路，再進行合理的設計和安排，就可以設計和安排，就可以表示和實現布爾代數的基本運算表示和實現布爾代數的基本運算。而。而布爾代數只使用布爾代數只使用1 1（真）和（真）和0 0（假）兩個數，這樣，當二進（假）兩個數，這樣，當二進精選ppt13制的加法、乘法等運算與布爾代數的運算建立了對應關系制的加法、乘法等

21、運算與布爾代數的運算建立了對應關系后，就可以用邏輯部件來實現二進制數據的加法、乘法等后，就可以用邏輯部件來實現二進制數據的加法、乘法等各種運算。各種運算。 例例5 5 基本的基本的“與與”、“或或”、“非非”門電路。門電路。 “與與”門電路一般有兩個以上的輸入和一個輸出。圖門電路一般有兩個以上的輸入和一個輸出。圖(a)(a)表示了一個表示了一個“與與”門電路，其輸出門電路，其輸出P P和輸入和輸入A A、B B、C C之間之間的邏輯關系可用下面的式子表示：的邏輯關系可用下面的式子表示： P PABCABC 電路設計中，用高電平信號表示電路設計中，用高電平信號表示1 1，低電平信號表示，低電平信

22、號表示0 0，那么，那么，“與與”門電路只有當輸入門電路只有當輸入A A、B B、C C同時為同時為1 1時，輸出時，輸出P P才為才為1 1，否則，否則，P P為為0 0。 “或或”門電路可以用圖門電路可以用圖(b)(b)表示。一般地說，表示。一般地說，“或或”門門電路是一種具有邏輯加法功能的電路，它有兩個以上的輸電路是一種具有邏輯加法功能的電路，它有兩個以上的輸入和入和精選ppt14一個輸出，其輸出一個輸出，其輸出P P和輸入和輸入A A、B B、C C之間的邏輯關系可用下之間的邏輯關系可用下面的式子表示：面的式子表示： P PA AB BC C 在具體的電路設計中，如果我們用高電平信號表

23、示在具體的電路設計中，如果我們用高電平信號表示1 1，低電平信號表示低電平信號表示0 0，那么，那么，“或或”門電路僅當輸入門電路僅當輸入A A、B B、C C中有一個為中有一個為1 1時，輸出時，輸出P P就為就為1 1，否則，否則，P P為為0 0。 “非非”門電路可以用圖門電路可以用圖(c)(c)表示。一般地說，表示。一般地說，“非非”門門電路是一種具有邏輯取反功能的電路，它只有一個輸入和電路是一種具有邏輯取反功能的電路，它只有一個輸入和一個輸出，其輸出一個輸出，其輸出P P和輸入和輸入A A之間的邏輯關系可用下面的式之間的邏輯關系可用下面的式子表示：子表示： P PA A 在具體的電路

24、設計中，如果我們用高電平信號表示在具體的電路設計中，如果我們用高電平信號表示1 1，低電平信號表示低電平信號表示0 0，那么，那么，“非非”門電路當輸入門電路當輸入A A為為0 0時，輸時，輸出出P P就為就為1 1，否則，當輸入，否則，當輸入A A為為1 1時，輸出時，輸出P P為為0 0。精選ppt15 “與與”、“或或”、“非非”三種門電路示意圖三種門電路示意圖 P P P A B C A B C A （a） （b） （c） 將布爾代數和前面談到的二進制聯系起來，我們可以將布爾代數和前面談到的二進制聯系起來，我們可以看出，看出，“與與”、“或或”、“非非”門電路的作用與集合運算門電路的作

25、用與集合運算“交交”、“并并”、“補補”是一致的。一旦門電路中僅使用是一致的。一旦門電路中僅使用兩個電平信號兩個電平信號0 0和和1 1，引入二進制及其運算規則，那么，用，引入二進制及其運算規則，那么，用門電路及其組門電路及其組精選ppt16合就可以實現二進制的各種運算，而對復雜電路的計算，合就可以實現二進制的各種運算，而對復雜電路的計算，如電路的化簡就有可能通過布爾代數的方法進行。事實上如電路的化簡就有可能通過布爾代數的方法進行。事實上也正是如此。也正是如此。 由此可見，真正構成計算機科學基本的、核心的內容由此可見，真正構成計算機科學基本的、核心的內容是圍繞計算而展開的大量帶有規律性的知識，

26、而不是具體是圍繞計算而展開的大量帶有規律性的知識，而不是具體的實現技術。因為，在將來，我們完全可能發展一種能表的實現技術。因為，在將來，我們完全可能發展一種能表示二進制數及其運算的新技術，它比今天的微電子技術精示二進制數及其運算的新技術，它比今天的微電子技術精度更高、生產價格更便宜。如果真是那樣，這種技術就可度更高、生產價格更便宜。如果真是那樣，這種技術就可能取代微電子技術在計算科學中的地位。近年來科學研究能取代微電子技術在計算科學中的地位。近年來科學研究的發展已顯現出一些很有希望但尚不成熟的技術，如光電的發展已顯現出一些很有希望但尚不成熟的技術，如光電子技術，金屬表面處理技術等。當然，程序技

27、術在可預見子技術，金屬表面處理技術等。當然，程序技術在可預見的將來尚不太可能被別的技術所代替，原因是它與各種應的將來尚不太可能被別的技術所代替，原因是它與各種應用相聯系，而且在形式上易于反映能行性這一本質的計算用相聯系，而且在形式上易于反映能行性這一本質的計算特征，在表達形式上與通常算法的描述較為接近特征，在表達形式上與通常算法的描述較為接近, ,設計和設計和生產的成本也比較低，又不存在工業污染的問題，所以不生產的成本也比較低，又不存在工業污染的問題，所以不精選ppt17易被取代。因此，我們常說，從這個意義上講，軟件技術易被取代。因此，我們常說，從這個意義上講，軟件技術比微電子技術對計算科學更

28、重要一些。比微電子技術對計算科學更重要一些。 2.4 2.4 機器指令與匯編語言機器指令與匯編語言 用計算機求解一個問題，必須事先編制好程序。程序用計算機求解一個問題，必須事先編制好程序。程序是由指令組成的。每一臺計算機都設計規定了一組指令集是由指令組成的。每一臺計算機都設計規定了一組指令集合，稱為機器指令系統。合，稱為機器指令系統。 機器指令的格式一般分為兩部分，如下所示：機器指令的格式一般分為兩部分，如下所示： 指令格式：指令格式： 操作碼操作碼 地址部分地址部分 其中，操作碼指出運算的種類，如，其中，操作碼指出運算的種類，如，跳轉，跳轉等，地址部分用來指示參與運算的數據保存在什么地方，等

29、，地址部分用來指示參與運算的數據保存在什么地方，如存儲器的某個地址或某個寄存器等。操作碼和地址部分如存儲器的某個地址或某個寄存器等。操作碼和地址部分都用二進制代碼表示。都用二進制代碼表示。精選ppt18 機器指令一般可根據其功能劃分為以下幾類：機器指令一般可根據其功能劃分為以下幾類：(1)(1)控制指令；控制指令；(2)(2)算術運算指令；算術運算指令；(3)(3)邏輯運算指令；邏輯運算指令；(4)(4)移位操作指令；移位操作指令；(5)(5)傳送操作指令；傳送操作指令；(6)(6)輸入輸入/ /輸出指令。輸出指令。 應當注意的是，不同的機器，其指令系統是不同的。應當注意的是，不同的機器，其指

30、令系統是不同的。 指令系統的日漸增大雖然給用戶的程序設計帶來了方便，指令系統的日漸增大雖然給用戶的程序設計帶來了方便，但也帶來了硬件設計復雜性的增加和因譯碼、存儲、尋址等但也帶來了硬件設計復雜性的增加和因譯碼、存儲、尋址等開銷的增大而使運算速度下降。研究發現，開銷的增大而使運算速度下降。研究發現，指令系統存在著指令系統存在著改進的必要和可能。改進的必要和可能。 真正使研究人員對指令系統進行較大改進的原因是超大真正使研究人員對指令系統進行較大改進的原因是超大規模集成電路（規模集成電路（VLSIVLSI）技術的發展和采用微程序技術實現體）技術的發展和采用微程序技術實現體系結構設計思想的過程中硬件復

31、雜性的不斷增長帶來的技術系結構設計思想的過程中硬件復雜性的不斷增長帶來的技術上的困難，使人們開始認識到在進行計算機系統設計時，應上的困難，使人們開始認識到在進行計算機系統設計時，應精選ppt19公平對待硬件與軟件的地位，使兩者平衡負擔整個系統的復公平對待硬件與軟件的地位，使兩者平衡負擔整個系統的復雜性。這一認識的轉變直接導致了精簡指令系統計算機雜性。這一認識的轉變直接導致了精簡指令系統計算機（RISCRISC）的誕生。所謂）的誕生。所謂RISCRISC是根據指令系統中各種指令應用是根據指令系統中各種指令應用的規律，將最常用的指令，以及一些控制較為簡單的寄存器的規律，將最常用的指令，以及一些控制

32、較為簡單的寄存器寄存器的操作與寄存器等一起直接做在寄存器的操作與寄存器等一起直接做在VLSIVLSI芯片上，靠減芯片上，靠減少譯碼、存儲、尋址方式和次數等開銷而大大增加運算速度。少譯碼、存儲、尋址方式和次數等開銷而大大增加運算速度。實際上，實際上，RISCRISC主要是一種體系結構設計的思想，而不只是一主要是一種體系結構設計的思想，而不只是一種計算機產品。種計算機產品。RISCRISC技術由于極大地提高了計算機的運算速技術由于極大地提高了計算機的運算速度，因而它的問世被認為是計算機體系結構發展史上的一個度，因而它的問世被認為是計算機體系結構發展史上的一個里程碑。里程碑。 匯編語言匯編語言 匯編

33、語言實際上是由一組匯編指令構成的語言。每一條匯編語言實際上是由一組匯編指令構成的語言。每一條匯編指令用某個西文字符串的縮寫來表示其所代表的操作，匯編指令用某個西文字符串的縮寫來表示其所代表的操作，用符號來代表數據的二進制、八進制和十進制數字序列。大用符號來代表數據的二進制、八進制和十進制數字序列。大多數情況下，一條匯編指令對應一條機器指令，少數對應幾多數情況下，一條匯編指令對應一條機器指令，少數對應幾精選ppt20條機器指令。例如，下面是幾條匯編指令的操作符，右邊中條機器指令。例如，下面是幾條匯編指令的操作符，右邊中文是名稱。文是名稱。 addadd 加法加法 idividiv 有符號除法有符

34、號除法 mulmul 無符號乘法無符號乘法negneg 求補求補 xchgxchg 交換交換 testtest 邏輯比較邏輯比較 jmpjmp 無條件轉移無條件轉移 有了匯編語言，就得編寫和設計匯編語言翻譯程序（簡有了匯編語言，就得編寫和設計匯編語言翻譯程序（簡稱匯編程序），專門負責把使用匯編語言書寫的程序翻譯成稱匯編程序），專門負責把使用匯編語言書寫的程序翻譯成可直接執行的機器指令程序。一般說來，匯編程序被看成是可直接執行的機器指令程序。一般說來，匯編程序被看成是系統軟件的一部分。系統軟件的一部分。 當然，匯編語言在可讀性和編寫程序時仍然是不能令人當然，匯編語言在可讀性和編寫程序時仍然是不能

35、令人滿意的，這導致進一步發展了高級程序設計語言。不過，由滿意的，這導致進一步發展了高級程序設計語言。不過，由于高級語言在使用時通常還是要通過編譯程序逐步將高級語于高級語言在使用時通常還是要通過編譯程序逐步將高級語言寫的程序翻譯成機器指令的程序，而這種翻譯的結果往往言寫的程序翻譯成機器指令的程序，而這種翻譯的結果往往不如機器指令或匯編語言寫的程序效率高，所以，直到今天，不如機器指令或匯編語言寫的程序效率高，所以，直到今天，不少工程師在系統軟件的開發中還在使用機器指令和匯編語不少工程師在系統軟件的開發中還在使用機器指令和匯編語言。言。精選ppt21 2.5 2.5 算法、過程與程序算法、過程與程序

36、 求解一個給定的問題，不同的人常編寫出不同的然而都求解一個給定的問題，不同的人常編寫出不同的然而都是正確的程序，這是為什么呢？是正確的程序，這是為什么呢？ 這里存在兩個層面的問題，一個是與計算方法密切相關這里存在兩個層面的問題，一個是與計算方法密切相關的算法問題，另一個是程序設計的技術問題。的算法問題，另一個是程序設計的技術問題。 例例6 6 給定兩個整數，求它們的最大公因數。給定兩個整數，求它們的最大公因數。 不失一般性，設有不全為不失一般性，設有不全為0 0的整數的整數x x、y y，記，記gcd(xgcd(x，y)y)為為它們的最大公因數，即同時能整除它們的最大公因數，即同時能整除x x

37、、y y的公因數中的最大者。的公因數中的最大者。顯然，顯然，gcd(xgcd(x，y)y)可表示為可表示為 gcd(xgcd(x，y)y)maxz z|xmaxz z|x，z|yz|y 這個問題許多中學生都會解，最常見的有著名的歐幾里這個問題許多中學生都會解，最常見的有著名的歐幾里德輾轉相除計算方法。當然，還有許多種解法。我們首先從德輾轉相除計算方法。當然，還有許多種解法。我們首先從函數函數gcd(xgcd(x，y)y)的性質出發來求解。函數的性質出發來求解。函數gcd(xgcd(x，y)y)具有如下具有如下性質：性質： (1) gcd(a(1) gcd(a，b)b)gcd(bgcd(b，a)

38、a)精選ppt22 (2) gcd(a (2) gcd(a，b)b)gcd(gcd(a a，b)b) (3) gcd(a (3) gcd(a，0)0)|a|a| (4) gcd(a (4) gcd(a，b)b)gcd(bgcd(b，a mod b)a mod b)，0a mod b0a mod bb b（歐幾里德輾轉相除計算方法）（歐幾里德輾轉相除計算方法） 根據以上性質，我們可以設計如下算法：根據以上性質，我們可以設計如下算法： 算法算法A A（計算函數（計算函數gcd(xgcd(x，y)y)） A A1 1. . 輸入輸入x x，y y；z z是輔助變量；是輔助變量； A A2 2. .

39、重復執行如下操作步驟：重復執行如下操作步驟： (1) (1) 若若y y0 0，則輸出，則輸出|x|x|，算法停止，算法停止 (2) (2) 若若y0y0，則，則zx mod yzx mod y，xyxy，yzyz； 有了計算函數有了計算函數gcd(xgcd(x，y)y)的算法，用程序設計語言很容的算法，用程序設計語言很容易寫出可在計算機上執行的程序。算法易寫出可在計算機上執行的程序。算法A A的核心是利用了函的核心是利用了函數數gcd(xgcd(x，y)y)的上述第四條性質。倘若我們使用的不是第四的上述第四條性質。倘若我們使用的不是第四精選ppt23條性質，那么，算法就會發生改變。條性質，那

40、么，算法就會發生改變。 不難想象，不同的求解方法將產生出不同的算法，不不難想象，不同的求解方法將產生出不同的算法，不同的算法將使我們設計出不同的程序，而決定這個程序功同的算法將使我們設計出不同的程序，而決定這個程序功能的本質是計算方法及其算法。一般地說，對不同計算方能的本質是計算方法及其算法。一般地說，對不同計算方法過程的抽象描述就產生了相應的不同算法，但同一算法法過程的抽象描述就產生了相應的不同算法，但同一算法由不同的人來寫程序則完全可能設計出差別很大的程序。由不同的人來寫程序則完全可能設計出差別很大的程序。 憑直覺想象給出的算法往往不是最好的算法。憑直覺想象給出的算法往往不是最好的算法。

41、例例7 7 用程序變換技術設計的計算函數用程序變換技術設計的計算函數gcd(x,y)gcd(x,y)的程序的程序 利用一種叫做程序變換技術的程序設計方法，可以產利用一種叫做程序變換技術的程序設計方法，可以產生計算函數生計算函數gcd(x,y)gcd(x,y)的如下遞歸過程性程序：的如下遞歸過程性程序： Procedure gcd(xProcedure gcd(x，y:inty:int，var z:int)var z:int)； begin if xbegin if x0 then z:0 then z:y y； xy & x0 then gcd(xxy & x0 then gc

42、d(x，y yx x，z)z)；精選ppt24 x xy & x0 then gcd(yy & x0 then gcd(y，x x，z)z) endif endif end end； 顯然，這個程序要一眼看出其功能是困難的。實際上，顯然，這個程序要一眼看出其功能是困難的。實際上，這個反映輾轉相除計算方法程序經過程序變換，形式上已這個反映輾轉相除計算方法程序經過程序變換，形式上已發生了很大變化。發生了很大變化。 這兩個例子進一步引發我們的一些思考：如何確保算這兩個例子進一步引發我們的一些思考：如何確保算法和程序的正確性？既然求解同一個問題可以有不同的方法和程序的正確性？既然求解同

43、一個問題可以有不同的方法，不同的算法，不同的程序，那么，怎么來判斷算法和法，不同的算法，不同的程序，那么，怎么來判斷算法和程序的好壞呢？程序變換是否改變算法呢？程序的好壞呢？程序變換是否改變算法呢？ 上面兩個例子初步表明算法、程序與數學之間存在著上面兩個例子初步表明算法、程序與數學之間存在著密切的聯系。要解決上面的問題，沒有數學和計算科學理密切的聯系。要解決上面的問題，沒有數學和計算科學理論的支持恐怕不行。多年來大學計算機科學本科教學的實論的支持恐怕不行。多年來大學計算機科學本科教學的實踐已反復證明，實際情況正是如此。踐已反復證明，實際情況正是如此。 在計算機科學研究中，事實上存在在計算機科學

44、研究中，事實上存在一條規律：一條規律：一個問一個問精選ppt25題，當它的描述及其求解方法或求解過程可以用構造性數學題，當它的描述及其求解方法或求解過程可以用構造性數學描述，而且該問題所涉及的論域為有窮，或雖為無窮但存在描述，而且該問題所涉及的論域為有窮，或雖為無窮但存在有窮表示時，那么，這個問題一定能用計算機來求解；有窮表示時，那么，這個問題一定能用計算機來求解；反過來，凡是能用計算機求解的問題，也一定能對該問題的反過來，凡是能用計算機求解的問題，也一定能對該問題的求解過程數學化，而且這種數學化是構造性的。求解過程數學化，而且這種數學化是構造性的。 當一個問題的求解獲得了計算方法和算法時，并

45、不等于當一個問題的求解獲得了計算方法和算法時，并不等于萬事大吉了。在許多情況下，找到求解一個問題的算法只是萬事大吉了。在許多情況下，找到求解一個問題的算法只是走完了第一步。至于現實是否可以計算，則取決于算法的存走完了第一步。至于現實是否可以計算，則取決于算法的存在性和計算的復雜性，即取決于該問題是否存在求解算法，在性和計算的復雜性，即取決于該問題是否存在求解算法，算法所需要的時間和空間在數量級上能否被接受。要注意的算法所需要的時間和空間在數量級上能否被接受。要注意的是，有的問題雖然存在求解問題的計算方法，但是，不存在是，有的問題雖然存在求解問題的計算方法，但是，不存在算法。原因有兩種可能：一是

46、計算方法可能不是構造性的；算法。原因有兩種可能：一是計算方法可能不是構造性的；二是雖為構造性的，但計算方法不能保證計算過程在任何初二是雖為構造性的，但計算方法不能保證計算過程在任何初值的情況下都能結束。值的情況下都能結束。精選ppt26 算法復雜性算法復雜性 什么是算法的復雜性呢？什么是算法的復雜性呢？ 使用計算機計算各種問題，需要存儲空間、計算時間。使用計算機計算各種問題，需要存儲空間、計算時間。不同的算法計算所需要的時間和空間是不同的。所謂算法不同的算法計算所需要的時間和空間是不同的。所謂算法的復雜性就是對算法計算所需要的時間和空間的一種度量。的復雜性就是對算法計算所需要的時間和空間的一種

47、度量。由于不同的計算機千差萬別，運算速度和字長可以相差很大，由于不同的計算機千差萬別，運算速度和字長可以相差很大，因此，不可能用算法在某一臺計算機上計算所需要的實際的因此，不可能用算法在某一臺計算機上計算所需要的實際的時間和存儲單元（空間）去衡量這個算法的復雜性。那么，時間和存儲單元（空間）去衡量這個算法的復雜性。那么，怎樣才能準確刻劃算法的計算復雜性呢？怎樣才能準確刻劃算法的計算復雜性呢？ 引入引入漸近增長率漸近增長率的概念來刻劃算法的計算復雜性。漸進的概念來刻劃算法的計算復雜性。漸進增長率用復雜性度量函數表示，該函數表示了算法隨問題規增長率用復雜性度量函數表示，該函數表示了算法隨問題規模大

48、小變化引起的算法中抽象的基本運算執行的次數或存儲模大小變化引起的算法中抽象的基本運算執行的次數或存儲空間量的變化規律。如某個計算問題當輸入規模分別為空間量的變化規律。如某個計算問題當輸入規模分別為1 1，2 2，3 3，n n時，經分析算法中抽象的基本運算次數分別為時，經分析算法中抽象的基本運算次數分別為1 1，4 4，9 9，n n2 2，那么，就可以用函數，那么，就可以用函數n n2 2來刻劃這個算法的時間復來刻劃這個算法的時間復雜性，并稱這個算法的時間復雜性度量為雜性，并稱這個算法的時間復雜性度量為 (n(n2 2) )級。級。精選ppt27有了復雜性度量函數，一旦選定具體計算機，可以根

49、據這臺有了復雜性度量函數，一旦選定具體計算機，可以根據這臺計算機對某個計算機對某個n n值的實際運算速度比較準確地估算出對其他值的實際運算速度比較準確地估算出對其他的的n n值完成計算所需要的時間。于是，對各種算法的復雜值完成計算所需要的時間。于是，對各種算法的復雜性進行分析的關鍵是要設法去找出這樣的函數，它涉及到與性進行分析的關鍵是要設法去找出這樣的函數，它涉及到與數學密切相關的算法的設計原理、思想和方法，算法分析是數學密切相關的算法的設計原理、思想和方法，算法分析是具有智力挑戰性的研究課題。具有智力挑戰性的研究課題。 證比求易算法證比求易算法（本書上的三個中國人算法）（本書上的三個中國人算

50、法） 在算法計算復雜性的研究中，一個算法如果存在圖靈機在算法計算復雜性的研究中，一個算法如果存在圖靈機可計算的多項式時間計算復雜性算法，就將這個算法歸入可計算的多項式時間計算復雜性算法，就將這個算法歸入P P類，如果存在非確定性圖靈機可計算的多項式時間計算復雜類，如果存在非確定性圖靈機可計算的多項式時間計算復雜性算法，就將其歸入性算法，就將其歸入NPNP類。對大多數實際問題來說，找到一類。對大多數實際問題來說，找到一個解可能很難，檢驗一個解常常比較容易，所以都屬于個解可能很難，檢驗一個解常常比較容易，所以都屬于NPNP類。類。現在，計算科學研究中一個懸而未決的重要問題是：現在，計算科學研究中一

51、個懸而未決的重要問題是： P PNPNP？。？。精選ppt28P PNPNP？ 這個問題不僅具有理論上的價值，而且具有重大實這個問題不僅具有理論上的價值，而且具有重大實用價值。因為到目前為止，已經發現了一批可計算但有相當用價值。因為到目前為止，已經發現了一批可計算但有相當難度的問題是屬于難度的問題是屬于NPNP類的，并且常通過證明一個問題與已知類的，并且常通過證明一個問題與已知屬于屬于NPNP類中的某個問題（如可滿足性問題，簡稱類中的某個問題（如可滿足性問題，簡稱SATSAT問題）問題）等價將其歸入等價將其歸入NPNP類。不過，該問題是否屬于類。不過，該問題是否屬于 P P類，即是否能類，即是

52、否能找到多項式時間計算復雜性算法求解該問題，或證明該問題找到多項式時間計算復雜性算法求解該問題，或證明該問題不存在多項式時間計算復雜性算法求解，至今尚未解決。現不存在多項式時間計算復雜性算法求解，至今尚未解決。現在，很多人都猜測秋碧貞楠的看法是對的：求解一個問題總在，很多人都猜測秋碧貞楠的看法是對的：求解一個問題總是比驗證一個問題的解要難，用公式表示也就是是比驗證一個問題的解要難，用公式表示也就是PNPPNP。7070年代初，庫克（年代初，庫克（S. A. CookS. A. Cook）和卡爾普（）和卡爾普（R. M. KarpR. M. Karp）指出，）指出，NPNP類中有一小類問題具有以

53、下性質：迄今為止，這些問題多類中有一小類問題具有以下性質：迄今為止，這些問題多數經過深思熟慮還沒有人找到多項式時間計算復雜性算法。數經過深思熟慮還沒有人找到多項式時間計算復雜性算法。但是，一旦其中的一個問題找到了多項式時間計算復雜性算但是，一旦其中的一個問題找到了多項式時間計算復雜性算法，這個類中的其它問題也能找到多項式時間計算復雜性算法，這個類中的其它問題也能找到多項式時間計算復雜性算法，那么就可以斷定法，那么就可以斷定P PNPNP。換句話說，如果確屬這個。換句話說，如果確屬這個精選ppt29類中的某個問題被證明不存在多項式時間計算復雜性算法，類中的某個問題被證明不存在多項式時間計算復雜性

54、算法，那么，就等于證明了那么，就等于證明了PNPPNP。通常，將這類問題稱為。通常，將這類問題稱為NPNP完全完全性問題。性問題。正是由于這些原因，正是由于這些原因，算法算法被認為是計算科學的核心問題之被認為是計算科學的核心問題之一。一。 定義定義1 1（算法）（算法） 給定問題和設備，一個算法是用該設備給定問題和設備，一個算法是用該設備可理解的語言表示的，解決這個問題的一種方法的精確刻可理解的語言表示的，解決這個問題的一種方法的精確刻劃。特別，算法具有下列特征屬性：劃。特別，算法具有下列特征屬性： (1) (1) 算法應用于一個具體的輸入集合或問題描述將在有窮算法應用于一個具體的輸入集合或問

55、題描述將在有窮步動作序列之后得到結果；步動作序列之后得到結果； (2) (2) 該序列有一個唯一的初始動作；該序列有一個唯一的初始動作； (3) (3) 該序列中的每一個動作有一個唯一的后繼動作；該序列中的每一個動作有一個唯一的后繼動作； (4) (4) 該序列終止時或者得到這個問題的解，或者因該問題該序列終止時或者得到這個問題的解，或者因該問題不可解而獲得不可解說明。不可解而獲得不可解說明。精選ppt30 定義定義1 1是一種百科全書式的定義，在專業上似乎不夠嚴是一種百科全書式的定義，在專業上似乎不夠嚴謹，而且也不適應于不確定性算法和分布式、并行算法。謹，而且也不適應于不確定性算法和分布式、

56、并行算法。 KnuthKnuth的算法定義的算法定義 定義定義2 2（KnuthKnuth算法定義）算法定義） 一個算法，就是一個有窮規則一個算法，就是一個有窮規則的集合，其中之規則確定了一個解決某一特定類型問題的的集合，其中之規則確定了一個解決某一特定類型問題的運算序列。此外，算法的規則序列須滿足如下五個重要條運算序列。此外，算法的規則序列須滿足如下五個重要條件（特性）：件（特性）： (1) (1) 有窮性。算法必須總是在執行有窮步之后結束；有窮性。算法必須總是在執行有窮步之后結束； (2) (2) 確定性。算法的每一個步驟必須是確切地定義的；確定性。算法的每一個步驟必須是確切地定義的； (

57、3) (3) 輸入。算法有零個或多個輸入；輸入。算法有零個或多個輸入； (4) (4) 輸出。算法有一個或多個輸出，即與輸入有某個特定輸出。算法有一個或多個輸出，即與輸入有某個特定關系的量；關系的量； (5) (5) 能行性。算法中有待執行的運算和操作必須是相當基能行性。算法中有待執行的運算和操作必須是相當基本的，即是說，本的，即是說， 它們原則上都是能夠精確地進行的，而且它們原則上都是能夠精確地進行的，而且用筆和紙做有窮次就可以完成。用筆和紙做有窮次就可以完成。精選ppt31 有窮性和能行性是算法最重要的兩個特征。對有些問題有窮性和能行性是算法最重要的兩個特征。對有些問題來說，如果我們給出了

58、一個類似于算法的有窮運算序列，而來說，如果我們給出了一個類似于算法的有窮運算序列，而它對某些輸入可能不停機，那么，我們就稱這樣的運算它對某些輸入可能不停機，那么，我們就稱這樣的運算序列為一個過程。算法和過程都滿足能行性和確定性，唯一序列為一個過程。算法和過程都滿足能行性和確定性，唯一的本質區別是算法的執行必須終止，而過程則不然，它可以的本質區別是算法的執行必須終止，而過程則不然，它可以永不停止。需要指出的是，高級程序設計語言中也有過程的永不停止。需要指出的是，高級程序設計語言中也有過程的概念，但與這里所講的過程不同，那里實際上指的是一種子概念，但與這里所講的過程不同，那里實際上指的是一種子程序

59、。程序。 19601960年代，克努特把計算機科學定義為是研究算法的學年代，克努特把計算機科學定義為是研究算法的學問。不過，由于問。不過，由于19801980年代計算機科學中并行與分布式算法的年代計算機科學中并行與分布式算法的發展與計算機體系結構密切相關，以及學科研究中發展多種發展與計算機體系結構密切相關，以及學科研究中發展多種不同層面計算模型的需要，包括發展非圖靈馮不同層面計算模型的需要，包括發展非圖靈馮諾依曼型諾依曼型計算模型，使許多人認識到研究計算模型與體系結構具有與計算模型，使許多人認識到研究計算模型與體系結構具有與研究算法同等的重要性，從而使今天學術界對計算科學下的研究算法同等的重要

60、性，從而使今天學術界對計算科學下的定義變得比過去更為準確。（見第二章）定義變得比過去更為準確。（見第二章）精選ppt32 一般地說，對任何一個問題，如果有了解決該問題的算一般地說，對任何一個問題，如果有了解決該問題的算法，就可以編制相應的程序。所謂法，就可以編制相應的程序。所謂程序，是一種事先編制好程序，是一種事先編制好了具有特殊功能的指令序列。了具有特殊功能的指令序列。其中，指令既可以是機器指其中，指令既可以是機器指令，匯編語言指令，也可以是高級語言的語句命令，甚至還令，匯編語言指令，也可以是高級語言的語句命令，甚至還可以是用自然語言描述的運算、操作命令。當然，用自然語可以是用自然語言描述的運算、操作命令。當然，用自然語