第2章計(jì)算機(jī)科學(xué)的基本概念和基本知識(shí)

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

2、某種形式來表示事物。形式化方法是在對(duì)事物描述形式化的基礎(chǔ)上，通過研究事物的形式變化規(guī)律來研究事物變化化的基礎(chǔ)上，通過研究事物的形式變化規(guī)律來研究事物變化規(guī)律的全體方法的總稱。規(guī)律的全體方法的總稱。1.1.1 1.1.1 計(jì)算模型與圖靈機(jī)計(jì)算模型與圖靈機(jī) 所謂計(jì)算模型是刻劃計(jì)算這一概念的一種抽象的形式系所謂計(jì)算模型是刻劃計(jì)算這一概念的一種抽象的形式系統(tǒng)或數(shù)學(xué)系統(tǒng)，而算法是對(duì)計(jì)算過程步驟（或狀態(tài)的一種刻統(tǒng)或數(shù)學(xué)系統(tǒng)，而算法是對(duì)計(jì)算過程步驟（或狀態(tài)的一種刻精選ppt2劃，是計(jì)算方法的一種能行實(shí)現(xiàn)方式。在計(jì)算機(jī)科學(xué)中，我劃，是計(jì)算方法的一種能行實(shí)現(xiàn)方式。在計(jì)算機(jī)科學(xué)中，我們通常所說的計(jì)算模型，并不是指

3、在其靜態(tài)或動(dòng)態(tài)數(shù)學(xué)描述們通常所說的計(jì)算模型，并不是指在其靜態(tài)或動(dòng)態(tài)數(shù)學(xué)描述基礎(chǔ)上建立求解某一基礎(chǔ)上建立求解某一( (類類) )問題計(jì)算方法的數(shù)學(xué)模型，而是指問題計(jì)算方法的數(shù)學(xué)模型，而是指具有狀態(tài)轉(zhuǎn)換特征，能夠?qū)λ幚淼膶?duì)象的數(shù)據(jù)或信息進(jìn)行具有狀態(tài)轉(zhuǎn)換特征，能夠?qū)λ幚淼膶?duì)象的數(shù)據(jù)或信息進(jìn)行表示、加工、變換、輸出的數(shù)學(xué)機(jī)器。由于觀察計(jì)算的角度表示、加工、變換、輸出的數(shù)學(xué)機(jī)器。由于觀察計(jì)算的角度不同，產(chǎn)生了各種不同的計(jì)算模型。不同，產(chǎn)生了各種不同的計(jì)算模型。 遞歸函數(shù)、遞歸函數(shù)、TuringTuring機(jī)等機(jī)等 (1) s(x)(1) s(x)x x1 1 （后繼函數(shù)）（后繼函數(shù)） (2) o(x

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

5、，那么，圖靈機(jī)就停機(jī)，計(jì)算任務(wù)宣告完是一個(gè)結(jié)束狀態(tài)，那么，圖靈機(jī)就停機(jī)，計(jì)算任務(wù)宣告完成，此時(shí)帶上的內(nèi)容就是計(jì)算的輸出結(jié)果。成，此時(shí)帶上的內(nèi)容就是計(jì)算的輸出結(jié)果。精選ppt4 例例1 1 M M的字母表的字母表A A00，1 1，bb，b b表示空格。狀態(tài)集表示空格。狀態(tài)集Q Qqq1 1，q q2 2，q q3 3 ，其中，指定，其中，指定q q1 1是開始狀態(tài)，是開始狀態(tài)，q q3 3是終止?fàn)顟B(tài)。是終止?fàn)顟B(tài)。 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； 對(duì)圖靈機(jī)的工作過程從不同的角度考察，可以給予不對(duì)圖靈機(jī)的工作過程從不同的角度考察，可以給予不同的解釋。同的解釋。 第一第一，把圖靈機(jī)看作識(shí)別器，即判斷帶子上最初的內(nèi)，把圖靈機(jī)看作識(shí)別器，即判斷帶子上最初的內(nèi)精選ppt5容能否被圖靈機(jī)所接受。假定圖靈機(jī)從左向右掃描完帶子上容能否被圖靈機(jī)所接受。假定圖靈機(jī)從左向右掃描完帶子上的內(nèi)容后停機(jī)則為接受，否則為不接受。的內(nèi)容后停機(jī)則為接受，否則為不接受。

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

8、對(duì)給定的輸入集合InIn，得到輸出集合，得到輸出集合OutOut00n n1 1n nnNnN。其中，。其中，N N是全體自然數(shù)的集合。是全體自然數(shù)的集合。 第三第三，把圖靈機(jī)看作計(jì)算器，相當(dāng)于一個(gè)函數(shù)。圖靈機(jī)，把圖靈機(jī)看作計(jì)算器，相當(dāng)于一個(gè)函數(shù)。圖靈機(jī)的輸入是函數(shù)的自變量的值，圖靈機(jī)的輸出是函數(shù)的值。的輸入是函數(shù)的自變量的值，圖靈機(jī)的輸出是函數(shù)的值。 例例4 4 圖靈機(jī)可以計(jì)算下列函數(shù)：圖靈機(jī)可以計(jì)算下列函數(shù)：精選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)。 第一和第二個(gè)函數(shù)讀者不難從圖靈機(jī)的定義出發(fā)感悟第一和第二個(gè)函數(shù)讀者不難從圖靈機(jī)的定義出發(fā)感悟到它們是圖靈機(jī)可以計(jì)算的函數(shù)，而第三個(gè)函數(shù)就比較復(fù)到它們是圖靈機(jī)可以計(jì)算的函數(shù)，而第三個(gè)函數(shù)就比較復(fù)雜，一時(shí)難于判斷。順便提一下，第三個(gè)函數(shù)叫做阿克曼雜，一時(shí)難于判斷。順便提一下，第三個(gè)函數(shù)叫做阿克曼函數(shù)，它是阿克曼（函數(shù)，它是阿克曼（W.AckermannW.Ackermann）在研究原始遞歸函數(shù)和）在研究原始遞歸函數(shù)和遞歸函數(shù)的關(guān)系時(shí)給出的。這個(gè)函數(shù)在計(jì)算理論中具有重遞歸函數(shù)的關(guān)系時(shí)給出的。

10、這個(gè)函數(shù)在計(jì)算理論中具有重要價(jià)值。事實(shí)上，圖靈機(jī)還可以計(jì)算形式上比第三個(gè)函數(shù)要價(jià)值。事實(shí)上，圖靈機(jī)還可以計(jì)算形式上比第三個(gè)函數(shù)更復(fù)雜的函數(shù)。更復(fù)雜的函數(shù)。 沿著這樣一種思路，圖靈機(jī)被證明具有很強(qiáng)的計(jì)算能沿著這樣一種思路，圖靈機(jī)被證明具有很強(qiáng)的計(jì)算能力，它與力，它與3030年代發(fā)展的遞歸函數(shù)論（一種能行可計(jì)算性理年代發(fā)展的遞歸函數(shù)論（一種能行可計(jì)算性理精選ppt7論）中一類最一般的可計(jì)算函數(shù)（部分遞歸函數(shù)或部分可論）中一類最一般的可計(jì)算函數(shù)（部分遞歸函數(shù)或部分可計(jì)算函數(shù)）在計(jì)算表達(dá)能力上是等價(jià)的。然而，圖靈機(jī)簡(jiǎn)計(jì)算函數(shù)）在計(jì)算表達(dá)能力上是等價(jià)的。然而，圖靈機(jī)簡(jiǎn)潔的構(gòu)造和運(yùn)行原理隱含了存儲(chǔ)程序的原

11、始思想，深刻地潔的構(gòu)造和運(yùn)行原理隱含了存儲(chǔ)程序的原始思想，深刻地揭示了現(xiàn)代通用電子數(shù)字計(jì)算機(jī)最核心的內(nèi)容。揭示了現(xiàn)代通用電子數(shù)字計(jì)算機(jī)最核心的內(nèi)容。 圖靈獎(jiǎng)圖靈獎(jiǎng) 2.1.2 2.1.2 二進(jìn)制二進(jìn)制 也許是圖靈機(jī)讀寫帶上只出現(xiàn)兩個(gè)符號(hào)啟發(fā)了研究者，也許是圖靈機(jī)讀寫帶上只出現(xiàn)兩個(gè)符號(hào)啟發(fā)了研究者，在當(dāng)時(shí)的技術(shù)條件下，從便于元器件的設(shè)計(jì)和制造考慮，在當(dāng)時(shí)的技術(shù)條件下，從便于元器件的設(shè)計(jì)和制造考慮，計(jì)算機(jī)的研制很自然地選擇了二進(jìn)制。后來的實(shí)踐也證明計(jì)算機(jī)的研制很自然地選擇了二進(jìn)制。后來的實(shí)踐也證明了這種選擇具有極大的優(yōu)點(diǎn)。了這種選擇具有極大的優(yōu)點(diǎn)。 十進(jìn)制數(shù)的表示十進(jìn)制數(shù)的表示 例如，例如，199

12、7.6301997.630這個(gè)數(shù)可以寫成：這個(gè)數(shù)可以寫成： 1997.6301997.6301 110103 39 910102 29 910101 17 710100 0 6 61010-1-13 31010-2-20 01010-3-3精選ppt8 一般地，任何一個(gè)十進(jìn)制數(shù)一般地，任何一個(gè)十進(jìn)制數(shù)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稱為十進(jìn)制的基數(shù)稱為十進(jìn)制的基數(shù),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為正整數(shù)。小數(shù)點(diǎn)的位置不言自明。為正整數(shù)。小數(shù)點(diǎn)的位置不言自明。 二進(jìn)制和十進(jìn)制一樣，是一種數(shù)制，它用于表示數(shù)的符二進(jìn)制和十進(jìn)制一樣，是一種數(shù)制，它用于表示數(shù)的符號(hào)（數(shù)字）由于在書寫中的位置不同而具有不同的值。二進(jìn)號(hào)（數(shù)字）由于在書寫中的位置不同而具有不同的值。二進(jìn)制表示數(shù)的符號(hào)只有兩個(gè)，即制表示數(shù)的符號(hào)只有兩個(gè)，即0 0和和1 1，其數(shù)值與十進(jìn)制中的，其數(shù)值與十進(jìn)制中的0 0和和1 1相同。此外，與十進(jìn)制不同之處在于二進(jìn)制數(shù)是逢二進(jìn)一。相同。此外，與十

14、進(jìn)制不同之處在于二進(jìn)制數(shù)是逢二進(jìn)一。精選ppt9 例如，十進(jìn)制數(shù)與二進(jìn)制數(shù)中的一些可作如下對(duì)應(yīng)：例如，十進(jìn)制數(shù)與二進(jìn)制數(shù)中的一些可作如下對(duì)應(yīng)： 十進(jìn)制十進(jìn)制 二進(jìn)制二進(jìn)制 (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) 一般地，任何一個(gè)二進(jìn)制數(shù)一般地，任何一個(gè)二進(jìn)制數(shù)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稱為二進(jìn)制的基數(shù)，稱為二進(jìn)制的基數(shù)，k ki i0,1,m,n0,1,m,n為正整數(shù)。為正整數(shù)。 進(jìn)一步，讀者可從十進(jìn)制數(shù)和二進(jìn)制數(shù)的一般表示公進(jìn)一步，讀者可從十進(jìn)制數(shù)和二進(jìn)制數(shù)的一般表示公式得到啟發(fā)，將這種表示推廣到更一般的任意進(jìn)制，不同式得到啟發(fā)，將這種表示推廣到更一般的任意進(jìn)制，不同之處只是基數(shù)不一樣。之處只是基數(shù)不一樣。 二進(jìn)制的運(yùn)算規(guī)則比十進(jìn)制的運(yùn)算規(guī)則簡(jiǎn)

16、單得多。二進(jìn)制的運(yùn)算規(guī)則比十進(jìn)制的運(yùn)算規(guī)則簡(jiǎn)單得多。只只要建立兩種進(jìn)制的數(shù)據(jù)之間的轉(zhuǎn)換方法，那么，二進(jìn)制將要建立兩種進(jìn)制的數(shù)據(jù)之間的轉(zhuǎn)換方法，那么，二進(jìn)制將具有更多的優(yōu)勢(shì)。具有更多的優(yōu)勢(shì)。計(jì)算機(jī)的理論基礎(chǔ)是邏輯和代數(shù)。當(dāng)二計(jì)算機(jī)的理論基礎(chǔ)是邏輯和代數(shù)。當(dāng)二進(jìn)制與同樣只使用進(jìn)制與同樣只使用“真真”和和“假假”兩個(gè)值的邏輯代數(shù)建立兩個(gè)值的邏輯代數(shù)建立了聯(lián)系后，這就為計(jì)算機(jī)的邏輯設(shè)計(jì)提供了便利的工具。了聯(lián)系后，這就為計(jì)算機(jī)的邏輯設(shè)計(jì)提供了便利的工具。精選ppt11 2.2 2.2 存儲(chǔ)程序式計(jì)算機(jī)的基本結(jié)構(gòu)與工作原理存儲(chǔ)程序式計(jì)算機(jī)的基本結(jié)構(gòu)與工作原理 圖靈機(jī)的出現(xiàn)為現(xiàn)代計(jì)算機(jī)的發(fā)明提供了重要的思想

17、。圖靈機(jī)的出現(xiàn)為現(xiàn)代計(jì)算機(jī)的發(fā)明提供了重要的思想。圖靈機(jī)的帶子可以看成是計(jì)算機(jī)的存儲(chǔ)設(shè)備，數(shù)據(jù)可以存圖靈機(jī)的帶子可以看成是計(jì)算機(jī)的存儲(chǔ)設(shè)備，數(shù)據(jù)可以存儲(chǔ)在上面，也可以根據(jù)需要擦去。圖靈機(jī)的命令相當(dāng)于一組儲(chǔ)在上面，也可以根據(jù)需要擦去。圖靈機(jī)的命令相當(dāng)于一組事先設(shè)計(jì)、存儲(chǔ)好了的程序，它們?cè)诳刂破靼才畔?，決定讀事先設(shè)計(jì)、存儲(chǔ)好了的程序，它們?cè)诳刂破靼才畔拢瑳Q定讀寫頭的每一步操作。這樣一種數(shù)學(xué)機(jī)器，如果不考慮它的實(shí)寫頭的每一步操作。這樣一種數(shù)學(xué)機(jī)器，如果不考慮它的實(shí)用性，就思想和原理而言，確實(shí)包含了存儲(chǔ)程序的重要思想。用性，就思想和原理而言，確實(shí)包含了存儲(chǔ)程序的重要思想。 程序與存儲(chǔ)程序式計(jì)算機(jī)程序與

18、存儲(chǔ)程序式計(jì)算機(jī) 圖靈機(jī)誕生后不到十年，在以馮圖靈機(jī)誕生后不到十年，在以馮諾依曼為代表的一批諾依曼為代表的一批科學(xué)家的努力下，現(xiàn)代存儲(chǔ)程序式電子數(shù)字計(jì)算機(jī)的基本結(jié)科學(xué)家的努力下，現(xiàn)代存儲(chǔ)程序式電子數(shù)字計(jì)算機(jī)的基本結(jié)構(gòu)與工作原理被確定下來。它主要由如下的五部分組成（見構(gòu)與工作原理被確定下來。它主要由如下的五部分組成（見P8P8圖）：圖）： 存儲(chǔ)器，運(yùn)算器，控制器，輸入設(shè)備，輸出設(shè)備存儲(chǔ)器，運(yùn)算器，控制器，輸入設(shè)備，輸出設(shè)備精選ppt12 在學(xué)科的發(fā)展歷程中，習(xí)慣上，人們將不帶有軟件系在學(xué)科的發(fā)展歷程中，習(xí)慣上，人們將不帶有軟件系統(tǒng)的存儲(chǔ)程序式電子數(shù)字計(jì)算機(jī)系統(tǒng)稱為硬件裸機(jī)，將硬統(tǒng)的存儲(chǔ)程序式電子

19、數(shù)字計(jì)算機(jī)系統(tǒng)稱為硬件裸機(jī)，將硬件裸機(jī)，參與構(gòu)成硬件裸機(jī)的各類部件及其研究范疇統(tǒng)稱件裸機(jī)，參與構(gòu)成硬件裸機(jī)的各類部件及其研究范疇統(tǒng)稱為硬件（方向）。為硬件（方向）。 2.3 2.3 數(shù)字邏輯與集成電路數(shù)字邏輯與集成電路 數(shù)字邏輯數(shù)字邏輯是數(shù)字電路邏輯設(shè)計(jì)的簡(jiǎn)稱，其內(nèi)容是應(yīng)用是數(shù)字電路邏輯設(shè)計(jì)的簡(jiǎn)稱，其內(nèi)容是應(yīng)用數(shù)字電路進(jìn)行數(shù)字系統(tǒng)邏輯設(shè)計(jì)。電子數(shù)字計(jì)算機(jī)是由具數(shù)字電路進(jìn)行數(shù)字系統(tǒng)邏輯設(shè)計(jì)。電子數(shù)字計(jì)算機(jī)是由具有各種邏輯功能的邏輯部件組成的，這些邏輯部件按其結(jié)有各種邏輯功能的邏輯部件組成的，這些邏輯部件按其結(jié)構(gòu)可分為組合邏輯電路和時(shí)序邏輯電路。構(gòu)可分為組合邏輯電路和時(shí)序邏輯電路。組合邏輯電路組合

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

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

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

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

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

25、用與集合運(yùn)算“交交”、“并并”、“補(bǔ)補(bǔ)”是一致的。一旦門電路中僅使用是一致的。一旦門電路中僅使用兩個(gè)電平信號(hào)兩個(gè)電平信號(hào)0 0和和1 1，引入二進(jìn)制及其運(yùn)算規(guī)則，那么，用，引入二進(jìn)制及其運(yùn)算規(guī)則，那么，用門電路及其組門電路及其組精選ppt16合就可以實(shí)現(xiàn)二進(jìn)制的各種運(yùn)算，而對(duì)復(fù)雜電路的計(jì)算，合就可以實(shí)現(xiàn)二進(jìn)制的各種運(yùn)算，而對(duì)復(fù)雜電路的計(jì)算，如電路的化簡(jiǎn)就有可能通過布爾代數(shù)的方法進(jìn)行。事實(shí)上如電路的化簡(jiǎn)就有可能通過布爾代數(shù)的方法進(jìn)行。事實(shí)上也正是如此。也正是如此。 由此可見，真正構(gòu)成計(jì)算機(jī)科學(xué)基本的、核心的內(nèi)容由此可見，真正構(gòu)成計(jì)算機(jī)科學(xué)基本的、核心的內(nèi)容是圍繞計(jì)算而展開的大量帶有規(guī)律性的知識(shí)，

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

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

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

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

30、令系統(tǒng)是不同的。 指令系統(tǒng)的日漸增大雖然給用戶的程序設(shè)計(jì)帶來了方便，指令系統(tǒng)的日漸增大雖然給用戶的程序設(shè)計(jì)帶來了方便，但也帶來了硬件設(shè)計(jì)復(fù)雜性的增加和因譯碼、存儲(chǔ)、尋址等但也帶來了硬件設(shè)計(jì)復(fù)雜性的增加和因譯碼、存儲(chǔ)、尋址等開銷的增大而使運(yùn)算速度下降。研究發(fā)現(xiàn)，開銷的增大而使運(yùn)算速度下降。研究發(fā)現(xiàn)，指令系統(tǒng)存在著指令系統(tǒng)存在著改進(jìn)的必要和可能。改進(jìn)的必要和可能。 真正使研究人員對(duì)指令系統(tǒng)進(jìn)行較大改進(jìn)的原因是超大真正使研究人員對(duì)指令系統(tǒng)進(jìn)行較大改進(jìn)的原因是超大規(guī)模集成電路（規(guī)模集成電路（VLSIVLSI）技術(shù)的發(fā)展和采用微程序技術(shù)實(shí)現(xiàn)體）技術(shù)的發(fā)展和采用微程序技術(shù)實(shí)現(xiàn)體系結(jié)構(gòu)設(shè)計(jì)思想的過程中硬件復(fù)

31、雜性的不斷增長(zhǎng)帶來的技術(shù)系結(jié)構(gòu)設(shè)計(jì)思想的過程中硬件復(fù)雜性的不斷增長(zhǎng)帶來的技術(shù)上的困難，使人們開始認(rèn)識(shí)到在進(jìn)行計(jì)算機(jī)系統(tǒng)設(shè)計(jì)時(shí)，應(yīng)上的困難，使人們開始認(rèn)識(shí)到在進(jìn)行計(jì)算機(jī)系統(tǒng)設(shè)計(jì)時(shí)，應(yīng)精選ppt19公平對(duì)待硬件與軟件的地位，使兩者平衡負(fù)擔(dān)整個(gè)系統(tǒng)的復(fù)公平對(duì)待硬件與軟件的地位，使兩者平衡負(fù)擔(dān)整個(gè)系統(tǒng)的復(fù)雜性。這一認(rèn)識(shí)的轉(zhuǎn)變直接導(dǎo)致了精簡(jiǎn)指令系統(tǒng)計(jì)算機(jī)雜性。這一認(rèn)識(shí)的轉(zhuǎn)變直接導(dǎo)致了精簡(jiǎn)指令系統(tǒng)計(jì)算機(jī)（RISCRISC）的誕生。所謂）的誕生。所謂RISCRISC是根據(jù)指令系統(tǒng)中各種指令應(yīng)用是根據(jù)指令系統(tǒng)中各種指令應(yīng)用的規(guī)律，將最常用的指令，以及一些控制較為簡(jiǎn)單的寄存器的規(guī)律，將最常用的指令，以及一些控制

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

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

34、號(hào)除法 mulmul 無符號(hào)乘法無符號(hào)乘法negneg 求補(bǔ)求補(bǔ) xchgxchg 交換交換 testtest 邏輯比較邏輯比較 jmpjmp 無條件轉(zhuǎn)移無條件轉(zhuǎn)移 有了匯編語言，就得編寫和設(shè)計(jì)匯編語言翻譯程序（簡(jiǎn)有了匯編語言，就得編寫和設(shè)計(jì)匯編語言翻譯程序（簡(jiǎn)稱匯編程序），專門負(fù)責(zé)把使用匯編語言書寫的程序翻譯成稱匯編程序），專門負(fù)責(zé)把使用匯編語言書寫的程序翻譯成可直接執(zhí)行的機(jī)器指令程序。一般說來，匯編程序被看成是可直接執(zhí)行的機(jī)器指令程序。一般說來，匯編程序被看成是系統(tǒng)軟件的一部分。系統(tǒng)軟件的一部分。 當(dāng)然，匯編語言在可讀性和編寫程序時(shí)仍然是不能令人當(dāng)然，匯編語言在可讀性和編寫程序時(shí)仍然是不能

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

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

37、、y y的公因數(shù)中的最大者。的公因數(shù)中的最大者。顯然，顯然，gcd(xgcd(x，y)y)可表示為可表示為 gcd(xgcd(x，y)y)maxz z|xmaxz z|x，z|yz|y 這個(gè)問題許多中學(xué)生都會(huì)解，最常見的有著名的歐幾里這個(gè)問題許多中學(xué)生都會(huì)解，最常見的有著名的歐幾里德輾轉(zhuǎn)相除計(jì)算方法。當(dāng)然，還有許多種解法。我們首先從德輾轉(zhuǎn)相除計(jì)算方法。當(dāng)然，還有許多種解法。我們首先從函數(shù)函數(shù)gcd(xgcd(x，y)y)的性質(zhì)出發(fā)來求解。函數(shù)的性質(zhì)出發(fā)來求解。函數(shù)gcd(xgcd(x，y)y)具有如下具有如下性質(zhì)：性質(zhì)： (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（歐幾里德輾轉(zhuǎn)相除計(jì)算方法）（歐幾里德輾轉(zhuǎn)相除計(jì)算方法） 根據(jù)以上性質(zhì)，我們可以設(shè)計(jì)如下算法：根據(jù)以上性質(zhì)，我們可以設(shè)計(jì)如下算法： 算法算法A A（計(jì)算函數(shù)（計(jì)算函數(shù)gcd(xgcd(x，y)y)） A A1 1. . 輸入輸入x x，y y；z z是輔助變量；是輔助變量； A A2 2. .

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

40、么，算法就會(huì)發(fā)生改變。 不難想象，不同的求解方法將產(chǎn)生出不同的算法，不不難想象，不同的求解方法將產(chǎn)生出不同的算法，不同的算法將使我們?cè)O(shè)計(jì)出不同的程序，而決定這個(gè)程序功同的算法將使我們?cè)O(shè)計(jì)出不同的程序，而決定這個(gè)程序功能的本質(zhì)是計(jì)算方法及其算法。一般地說，對(duì)不同計(jì)算方能的本質(zhì)是計(jì)算方法及其算法。一般地說，對(duì)不同計(jì)算方法過程的抽象描述就產(chǎn)生了相應(yīng)的不同算法，但同一算法法過程的抽象描述就產(chǎn)生了相應(yīng)的不同算法，但同一算法由不同的人來寫程序則完全可能設(shè)計(jì)出差別很大的程序。由不同的人來寫程序則完全可能設(shè)計(jì)出差別很大的程序。 憑直覺想象給出的算法往往不是最好的算法。憑直覺想象給出的算法往往不是最好的算法。

41、例例7 7 用程序變換技術(shù)設(shè)計(jì)的計(jì)算函數(shù)用程序變換技術(shù)設(shè)計(jì)的計(jì)算函數(shù)gcd(x,y)gcd(x,y)的程序的程序 利用一種叫做程序變換技術(shù)的程序設(shè)計(jì)方法，可以產(chǎn)利用一種叫做程序變換技術(shù)的程序設(shè)計(jì)方法，可以產(chǎn)生計(jì)算函數(shù)生計(jì)算函數(shù)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； 顯然，這個(gè)程序要一眼看出其功能是困難的。實(shí)際上，顯然，這個(gè)程序要一眼看出其功能是困難的。實(shí)際上，這個(gè)反映輾轉(zhuǎn)相除計(jì)算方法程序經(jīng)過程序變換，形式上已這個(gè)反映輾轉(zhuǎn)相除計(jì)算方法程序經(jīng)過程序變換，形式上已發(fā)生了很大變化。發(fā)生了很大變化。 這兩個(gè)例子進(jìn)一步引發(fā)我們的一些思考：如何確保算這兩個(gè)例子進(jìn)一步引發(fā)我們的一些思考：如何確保算法和程序的正確性？既然求解同一個(gè)問題可以有不同的方法和程序的正確性？既然求解同

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

44、研究中，事實(shí)上存在一條規(guī)律：一條規(guī)律：一個(gè)問一個(gè)問精選ppt25題，當(dāng)它的描述及其求解方法或求解過程可以用構(gòu)造性數(shù)學(xué)題，當(dāng)它的描述及其求解方法或求解過程可以用構(gòu)造性數(shù)學(xué)描述，而且該問題所涉及的論域?yàn)橛懈F，或雖為無窮但存在描述，而且該問題所涉及的論域?yàn)橛懈F，或雖為無窮但存在有窮表示時(shí)，那么，這個(gè)問題一定能用計(jì)算機(jī)來求解；有窮表示時(shí)，那么，這個(gè)問題一定能用計(jì)算機(jī)來求解；反過來，凡是能用計(jì)算機(jī)求解的問題，也一定能對(duì)該問題的反過來，凡是能用計(jì)算機(jī)求解的問題，也一定能對(duì)該問題的求解過程數(shù)學(xué)化，而且這種數(shù)學(xué)化是構(gòu)造性的。求解過程數(shù)學(xué)化，而且這種數(shù)學(xué)化是構(gòu)造性的。 當(dāng)一個(gè)問題的求解獲得了計(jì)算方法和算法時(shí)，并

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

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

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

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

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

50、法） 在算法計(jì)算復(fù)雜性的研究中，一個(gè)算法如果存在圖靈機(jī)在算法計(jì)算復(fù)雜性的研究中，一個(gè)算法如果存在圖靈機(jī)可計(jì)算的多項(xiàng)式時(shí)間計(jì)算復(fù)雜性算法，就將這個(gè)算法歸入可計(jì)算的多項(xiàng)式時(shí)間計(jì)算復(fù)雜性算法，就將這個(gè)算法歸入P P類，如果存在非確定性圖靈機(jī)可計(jì)算的多項(xiàng)式時(shí)間計(jì)算復(fù)雜類，如果存在非確定性圖靈機(jī)可計(jì)算的多項(xiàng)式時(shí)間計(jì)算復(fù)雜性算法，就將其歸入性算法，就將其歸入NPNP類。對(duì)大多數(shù)實(shí)際問題來說，找到一類。對(duì)大多數(shù)實(shí)際問題來說，找到一個(gè)解可能很難，檢驗(yàn)一個(gè)解常常比較容易，所以都屬于個(gè)解可能很難，檢驗(yàn)一個(gè)解常常比較容易，所以都屬于NPNP類。類?，F(xiàn)在，計(jì)算科學(xué)研究中一個(gè)懸而未決的重要問題是：現(xiàn)在，計(jì)算科學(xué)研究中一

51、個(gè)懸而未決的重要問題是： P PNPNP？。？。精選ppt28P PNPNP？ 這個(gè)問題不僅具有理論上的價(jià)值，而且具有重大實(shí)這個(gè)問題不僅具有理論上的價(jià)值，而且具有重大實(shí)用價(jià)值。因?yàn)榈侥壳盀橹梗呀?jīng)發(fā)現(xiàn)了一批可計(jì)算但有相當(dāng)用價(jià)值。因?yàn)榈侥壳盀橹梗呀?jīng)發(fā)現(xiàn)了一批可計(jì)算但有相當(dāng)難度的問題是屬于難度的問題是屬于NPNP類的，并且常通過證明一個(gè)問題與已知類的，并且常通過證明一個(gè)問題與已知屬于屬于NPNP類中的某個(gè)問題（如可滿足性問題，簡(jiǎn)稱類中的某個(gè)問題（如可滿足性問題，簡(jiǎn)稱SATSAT問題）問題）等價(jià)將其歸入等價(jià)將其歸入NPNP類。不過，該問題是否屬于類。不過，該問題是否屬于 P P類，即是否能類，即是

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

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

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

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

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

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

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

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

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