第4章計算學科中基本概念

1、第4章計算學科中基本概念第4章 計算學科中的基本概念 第4章計算學科中基本概念4.1 計算模型與二進制第4章計算學科中基本概念計算模型與圖靈機計算模型：刻畫計算這一概念的一種抽象的形式系統(tǒng)或數(shù)學系統(tǒng)。在計算科學中，是指具有狀態(tài)轉換特征，能夠?qū)λ幚淼膶ο蟮臄?shù)據(jù)或信息進行表示、加工、變化、接收、輸出的數(shù)學機器。計算模型的層次：計算某個（類）具體問題的計算方法；按照計算方法對應的程序完成某類問題特定計算所需要的平臺。 在計算能力上具有某種等價性的形式系統(tǒng)。 計算模型的模型（一切計算模型所內(nèi)含的機理）第4章計算學科中基本概念計算模型與圖靈機圖靈的觀點及結論：凡是能用算法方法解決的問題，也一定能用圖靈

2、機解決；凡是圖靈機解決不了的問題，任何算法也解決不了。與圖靈機等價的計算模型：遞歸函數(shù)-演算POST規(guī)范系統(tǒng)圖靈機是從過程這一角度來刻畫計算的本質(zhì)，其結構簡單、操作運算規(guī)則也較少，從而為更多的人所理解。第4章計算學科中基本概念圖靈機 圖靈機由一條兩端可無限延長的帶子、一個讀寫頭以及一組控制讀寫頭工作的命令組成， b b 1 0 1 0 0 0 1 0 b b b 讀 寫 頭 控 制 器 狀 態(tài) ql 第4章計算學科中基本概念圖靈機寫在帶子上的符號為一個有窮字母表：S0，S1，S2，Sp?？梢哉J為這個有窮字母表僅有S0、S1兩個字符，其中S0可以看作是“0”，S1可以看作是“1”，由 “0”和“

3、1”組成的字母表可以表示任何一個數(shù)。第4章計算學科中基本概念由于“0”和“1”只有形式的意義，因此，也可以將S0改稱為“白”，S1改稱為“黑”，甚至，還可以改稱為“桌子”和“老虎”，這樣改稱的目的在于割斷與直覺的聯(lián)系，并加深對布爾域中的值真，假，以及二進制機器本質(zhì)的理解。機器的控制狀態(tài)表為：q1，q2，qm。將一個圖靈機的初始狀態(tài)設為q1，在每一個具體的圖靈機中還要確定一個結束狀態(tài)qw。 第4章計算學科中基本概念一個給定機器的“程序”機器內(nèi)的五元組（qiSjSkR（或L或N）ql）形式的指令集，五元組定義了機器在一個特定狀態(tài)下讀入一個特定字符時所采取的動作。5個元素的含義如下： qi表示機器目

4、前所處的狀態(tài)； Sj表示機器從方格中讀入的符號； Sk表示機器用來代替Sj寫入方格中的符號； R、L、N分別表示向右移一格、向左移一格、不移動；ql表示下一步機器的狀態(tài)。 第4章計算學科中基本概念一個機器計算的結果是從機器停止時帶子上的信息得到的。容易看出，q1S2S2Rq3指令和q3S3S3Lq1指令如果同時出現(xiàn)在機器中，當機器處于狀態(tài)q1，第一條指令讀入的是S2，第二條指令讀入的是S3，那么機器會在兩個方塊之間無休止地工作。另外，如果q3S2S2Rq4和q3S2S4Lq6指令同時出現(xiàn)在機器中，當機器處于狀態(tài)q3并在帶子上掃描到符號S2時，就產(chǎn)生了二義性的問題，機器就無法判定。第4章計算學科

5、中基本概念例子：b表示空格，q1表示機器的初始狀態(tài)， q4表示機器的結束狀態(tài)，設帶子上的輸入信息是10100010，讀入頭位對準最右邊第一個為0的方格，狀態(tài)為初始狀態(tài)q1。規(guī)則如下：q1 0 1 L q2 q1 1 0 L q3 q1 b b N q4q2 0 0 L q2 q2 1 1 L q2 q2 b b N q4q3 0 1 L q2 q3 1 0 L q3 q3 b b N q4 b b 1 0 1 0 0 0 1 0 b b b 讀 寫 頭 控 制 器 狀 態(tài) ql 第4章計算學科中基本概念計算結果是10100011，即對給定的數(shù)加1。 b b 1 0 1 0 0 0 1 0 b

6、b b 讀 寫 頭 控 制 器 狀 態(tài) ql 以上命令計算的是這樣一個函數(shù)：S(x)x1。當沒有輸入時，即初始狀態(tài)所指的方格為空格（b）時，不改變空格符，讀寫頭不動并停機。 第4章計算學科中基本概念圖靈機的計算能力第一，把圖靈機看作識別器，即判斷帶子上最初的內(nèi)容能否被圖靈機所接受。假定圖靈機從左向右掃描完帶子上的內(nèi)容后停機則為接受，否則為不接受。 例2 一臺圖靈機可以設計成識別下面的序列： 1000110, 10011101, 010101011。 第4章計算學科中基本概念圖靈機的計算能力第二，把圖靈機看作生成器，對給定的輸入集合，考察輸出集合，并研究輸入輸出集合性質(zhì)之間的關系，這就研究了圖靈

7、機的生成能力。 例3 設一臺圖靈機的輸入集合為In1n0nnN，可設計一臺圖靈機，對給定的輸入集合In，得到輸出集合Out0n1nnN。其中，N是全體自然數(shù)的集合。第4章計算學科中基本概念圖靈機的計算能力第三，把圖靈機看作計算器，相當于一個函數(shù)。圖靈機的輸入是函數(shù)的自變量的值，圖靈機的輸出是函數(shù)的值。 例4 圖靈機可以計算下列函數(shù)： (1) s(x)x1； (2) o(x)0； (3) A(0，y)y1， A(x1，0)A(x，1)， A(x1，y1)A(x，A(x1，y)。第4章計算學科中基本概念圖靈機的計算能力第一和第二個函數(shù)讀者不難從圖靈機的定義出發(fā)感悟到它們是圖靈機可以計算的函數(shù)，而第

8、三個函數(shù)就比較復雜，一時難于判斷。順便提一下，第三個函數(shù)叫做阿克曼函數(shù)，它是阿克曼（W.Ackermann）在研究原始遞歸函數(shù)和遞歸函數(shù)的關系時給出的。這個函數(shù)在計算理論中具有重要價值。事實上，圖靈機還可以計算形式上比第三個函數(shù)更復雜的函數(shù)。 第4章計算學科中基本概念圖靈機的計算能力圖靈機可以計算S(x)x1（后繼函數(shù)），N(x)0（零函數(shù)），Ui(n)(x1，x2，xn)xi，1in（投影函數(shù)）上述3個函數(shù)的任意組合。從遞歸論中，我們知道這3個函數(shù)屬于初始遞歸函數(shù)，任何原始遞歸函數(shù)都是從這3個初始遞歸函數(shù)經(jīng)有限次的復合、遞歸和極小化操作得到的。從可計算理論可知每一個原始遞歸函數(shù)都是圖靈機可計

9、算的。 第4章計算學科中基本概念4.1 計算模型與二進制第4章計算學科中基本概念計算機的數(shù)字系統(tǒng)計算機采用的是二進制數(shù)字系統(tǒng)?；痉枺?、1進位原則：逢二進一優(yōu)點：易于物理實現(xiàn)二進制數(shù)運算簡單機器可靠性高通用性強缺點：對人來說可讀性差第4章計算學科中基本概念十進制數(shù)的表示各位數(shù)字與它的權相乘，其積相加。例如:27997.63=21*104+ 7*103 + 9* 102 +9* 101 + 7* 100 + 6* 10-1 +3* 10-2 對于任意的十進制數(shù)：S=kn*10n +kn-1*10n-1 +k1*101 + k0*100 +k-1*10-1 + k-m+1*10-m+1 + k

10、-m*10-m(n1, m1)其中，10稱為十進制的基數(shù),ki0,1,2,3,4,5,6,7,8 9，m，n為正整數(shù)。小數(shù)點的位置不言自明。第4章計算學科中基本概念計算機的數(shù)字系統(tǒng) 計算機采用的是二進制數(shù)字系統(tǒng)。二進制和十進制一樣，是一種數(shù)制，它用于表示數(shù)的符號（數(shù)字）由于在書寫中的位置不同而具有不同的值。 基本符號：0、1 進位原則：逢二進一 優(yōu)點：易于物理實現(xiàn)二進制數(shù)運算簡單機器可靠性高通用性強 缺點：對人來說可讀性差第4章計算學科中基本概念二進制數(shù) Sknkn-1 k0. k-m kn2nkn-12n-1k020k-m2-m -m ki2i in 其中，其中，2稱為二進制的基數(shù)，稱為二進

11、制的基數(shù)，ki0,1,m,n為正整數(shù)。為正整數(shù)。 進一步，讀者可從十進制數(shù)和二進制數(shù)的一般表示進一步，讀者可從十進制數(shù)和二進制數(shù)的一般表示公式得到啟發(fā)，將這種表示推廣到更一般的任意進制，公式得到啟發(fā)，將這種表示推廣到更一般的任意進制，不同之處只是基數(shù)不一樣。不同之處只是基數(shù)不一樣。 第4章計算學科中基本概念二進制數(shù) 二進制的運算規(guī)則比十進制的運算規(guī)則簡二進制的運算規(guī)則比十進制的運算規(guī)則簡單得多。只要建立兩種進制的數(shù)據(jù)之間的轉換單得多。只要建立兩種進制的數(shù)據(jù)之間的轉換方法，那么，二進制將具有更多的優(yōu)勢。計算方法，那么，二進制將具有更多的優(yōu)勢。計算機的理論基礎是邏輯和代數(shù)。當二進制與同樣機的理論基

12、礎是邏輯和代數(shù)。當二進制與同樣只使用只使用“真真”和和“假假”兩個值的邏輯代數(shù)建立兩個值的邏輯代數(shù)建立了聯(lián)系后，這就為計算機的邏輯設計提供了便了聯(lián)系后，這就為計算機的邏輯設計提供了便利的工具。利的工具。第4章計算學科中基本概念不同進位計數(shù)制間的轉換 R 進制十進制各位數(shù)字與它的權相乘，其積相加。例如:(11111111.11)2=1*27 + 1*26 + 1* 25 +1* 24 + 1* 23 + 1* 22 +1* 21+ 1* 20+1*2-1+1*2-2 =(255.75)10(3506.2)8=3*83 + 5*82 + 0*81 + 6*80 +2*8-1=(1862.25)10

13、(0.2A)16=2*16-1 +10*16-2=(0.1640625)10第4章計算學科中基本概念二進制與十進制間的轉換 十進制 二進制十進制整數(shù)轉換成二進制的整數(shù)“除R取余”法，例如：2 68 余 數(shù) 2 34 0 低位 2 17 0 2 8 1 2 4 0 2 2 0 2 1 0 0 1 高位所以 68102第4章計算學科中基本概念二進制與十進制間的轉換十進制 二進制十進制小數(shù)轉換成二進制小數(shù)“乘 R 取整”法，例如： 高位 0.31252 = 0 .625 0.625 2 = 1 .25 0.25 2 = 0 .5 0.5 2 = 1 .0所以 0.312510 = 0.01012 第

14、4章計算學科中基本概念不同進位計數(shù)制間的轉換二、八、十六進制的相互轉換每位八進制數(shù)相當于三位二進制數(shù)每位十六進制數(shù)相當于四位二進制數(shù)( 1 0 1 1 0 1 0 . 1 0 )2= ( 0 0 1 0 1 1 0 1 0 . 1 0 0 )2=(132.4)8( 1 0 1 1 0 1 0 . 1 0 )2= ( 0 1 0 1 1 0 1 0 . 1 0 0 0 )2=(5A.8)16(F7)16(1111 0111)2(11110111)2第4章計算學科中基本概念信息的存儲單位位(bit)：度量數(shù)據(jù)的最小單位，表示一位二進制信息。字節(jié)(byte)：由八位二進制數(shù)字組成(1 byte =

15、8 bit)。K 字節(jié) 1 K = 1024 byteM 字節(jié) 1 M = 1024 KG 字節(jié) 1 G = 1024 M T字節(jié) 1T=1024G第4章計算學科中基本概念非數(shù)值信息的表示西文字符：ASCII碼：用7位二進制數(shù)表示一個字符，最多可以表示27=128個字符EBCDIC碼：用8位二進制數(shù)表示一個字符，最多可以表示28=256個字符漢字：應用較為廣泛的是國家標準信息交換用漢字編碼(GB2312-80標準)，簡稱國標碼。是二字節(jié)碼，用二個七位二進制數(shù)編碼表示一個漢字。第4章計算學科中基本概念4.2 存儲程序式計算機的基本結構與工作原理第4章計算學科中基本概念馮諾依曼型計算機 圖靈機的出

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

17、思想。 第4章計算學科中基本概念馮諾依曼型計算機計算機程序是指能夠在計算機系統(tǒng)中運行的程序?，F(xiàn)在的計算機全稱為存儲程序式通用電子數(shù)字計算機。其含義是：在計算機中各種信息用數(shù)字代碼表示，如指令、數(shù)值型數(shù)據(jù)、字符、圖像等。在物理機制上，數(shù)字代碼以數(shù)字型信號出現(xiàn)。 信息表示數(shù)字化-理解計算機工作原理的基本出發(fā)點。第4章計算學科中基本概念馮諾依曼型計算機目前有兩種電信號：模擬信號：一種在時間上連續(xù)的信號，用信號的某些參數(shù)（如幅值）去模擬信息。數(shù)字信號：一種在時間上或空間上不連續(xù)（離散）的信號。 第4章計算學科中基本概念馮諾依曼型計算機采用數(shù)字化方法表示信息的優(yōu)點：抗干擾能力強，可靠性高。位數(shù)增多則數(shù)的

18、表示范圍擴大，可以表示更精確的數(shù)字。 物理上容易實現(xiàn)，并可存儲。 表示信息的類型和范圍極其廣泛。 能用邏輯代數(shù)等數(shù)字邏輯技術進行處理。第4章計算學科中基本概念馮諾依曼型計算機 ENIAC的結構在很大程度上是依照機電系統(tǒng)設計的，還存在重大的線路結構等問題。在圖靈等人工作的影響下，1946年6月，美國杰出的數(shù)學家馮諾依曼（Von Neumann）及其同事完成了關于“電子計算裝置邏輯結構設計”的研究報告，具體介紹了制造電子計算機和程序設計的新思想：存儲程序、順序控制至今為止，大多數(shù)計算機采用的仍然是馮諾依曼型計算機的組織結構，只是作了一些改進而已。因此，馮諾依曼被人們譽為“計算機器之父”。 第4章計

19、算學科中基本概念馮諾依曼型計算機的組織結構 存 儲 器 運 算 器 控 制 器 輸入/輸出設備 命令寄存器 第4章計算學科中基本概念輸入設備和輸出設備第4章計算學科中基本概念輸入設備和輸出設備作用：是將信息輸入計算機和輸出計算機。常用的文字輸入設備是鍵盤（還有掃描儀、穿孔卡片讀入機和鼠標等專用輸入設備）當在鍵盤上按下一個鍵時，按下的鍵通過編碼變換成機器可讀的數(shù)據(jù)形式，如字符“A”變換成ASCII碼“1000001”，該編碼數(shù)據(jù)隨即存入存儲器等待處理，通過與“1000001”對應的字符點陣數(shù)據(jù)在屏幕上顯示一個字符“A”。輸出設備有打印機、顯示器、繪圖儀、磁記錄設備等。 第4章計算學科中基本概念存

20、儲器第4章計算學科中基本概念存儲器存儲器是一種數(shù)據(jù)或信息的存儲部件，它分成很多存儲單元，并按照一定的方式進行排列。每個單元都編了號，稱為存儲地址。指令和數(shù)據(jù)存放在存儲器中,而且對指令和數(shù)據(jù)同等對待，都不加區(qū)別地送到運算器中運算。指令在存儲器中基本上是按執(zhí)行順序存儲的，由指令計數(shù)器指明要執(zhí)行的指令在存儲器中的地址。 第4章計算學科中基本概念存儲器存儲器一般分為內(nèi)存儲器與外存儲器兩大類。內(nèi)存一般安裝在主機板上，根據(jù)材料和工作原理的不同，內(nèi)存可分為隨機存儲器（RAM）和只讀存儲器（ROM）兩種。控制器和運算器只能接受在內(nèi)存中存放的指令和數(shù)據(jù)。 外存一般安裝在主機板之外，例如磁盤就是一種常用的外存。外

21、存上面的信息可長久保存，但這些信息必須讀入內(nèi)存之后才能被控制器和運算器所利用。磁盤按其材料的不同，又可分為軟盤和硬盤兩種。 第4章計算學科中基本概念CPU(運算器和控制器 )central processing unit第4章計算學科中基本概念Register、控制單元計算機中控制數(shù)據(jù)操作的電路并不與主存直接相連這些電路被封裝在一起，即CPUCPU含有自己的存儲單元（register）Register作為臨時空間來存儲CPU所操作的數(shù)，保存算術邏輯單元的輸入與輸出數(shù)據(jù)控制單元負責將主存中的數(shù)據(jù)移到register，然后通知算術邏輯單元所需要的數(shù)據(jù)在哪個register第4章計算學科中基本概念總

22、線總線：CPU與主存之間用總線連接，利用總線CPU通過提供存儲單元目標地址以及讀信號來選擇、讀取數(shù)據(jù)CPU通過提供存儲單元目標地址以及寫信號來放置、寫入信號誰發(fā)明了什么程序存儲的概念：由賓西法尼亞大學Moore電子工程學院的J.P.Echert提出，John von Neumann只是先發(fā)表了程序存儲的概念第4章計算學科中基本概念CPU和主存儲器通過總線相連第4章計算學科中基本概念4.3 數(shù)字邏輯與集成電路第4章計算學科中基本概念數(shù)字邏輯數(shù)字邏輯是數(shù)字電路邏輯設計的簡稱，其內(nèi)容是應用數(shù)字電路進行數(shù)字系統(tǒng)邏輯設計。組成計算機的邏輯部件可分為組合邏輯電路和時序邏輯電路兩種。 組合邏輯電路：由與門、

23、或門和非門等門電路組合而成的邏輯電路。時序邏輯電路：由觸發(fā)器和門電路組成的具有記憶能力的邏輯電路。 第4章計算學科中基本概念門電路“與”門電路：兩個以上的輸入，一個輸出。僅當所有的輸入為1時，輸出才為1。 P=A B C“或”門電路：兩個以上的輸入，一個輸出。僅當有一個輸入為1時，輸出就為1。 P=A + B + C “非”門電路：一個輸入，一個輸出。當輸入為1時，輸出為0；輸入為0時，輸出為1。第4章計算學科中基本概念門電路 “與與”、“或或”、“非非”三種門電路示意圖三種門電路示意圖 P P P A B C A B C A （a） （b） （c） 第4章計算學科中基本概念4.4 機器指令與

24、匯編語言第4章計算學科中基本概念 機器指令為了實現(xiàn)程序存儲的概念，CPU要能識別二進制編碼的指令機器語言指令集合以及編碼系統(tǒng)第4章計算學科中基本概念機器指令用計算機求解一個問題，必須事先編制好程序。程序是由指令組成的。每一臺計算機都設計規(guī)定了一組指令集合，稱為機器指令系統(tǒng)。 機器指令的格式一般分為兩部分，如下所示： 指令格式： 操作碼 地址部分 其中，操作碼指出運算的種類，如，跳轉等，地址部分用來指示參與運算的數(shù)據(jù)保存在什么地方，如存儲器的某個地址或某個寄存器等。操作碼和地址部分都用二進制代碼表示。第4章計算學科中基本概念機器指令機器指令一般可根據(jù)其功能劃分為以下幾類： (1)控制指令；(2)

25、算術運算指令；(3)邏輯運算指令；(4)移位操作指令；(5)傳送操作指令；(6)輸入/輸出指令。應當注意的是，不同的機器，其指令系統(tǒng)是不同的。指令系統(tǒng)的日漸增大雖然給用戶的程序設計帶來了方便，但也帶來了硬件設計復雜性的增加和因譯碼、存儲、尋址等開銷的增大而使運算速度下降。研究發(fā)現(xiàn)，指令系統(tǒng)存在著改進的必要和可能。 第4章計算學科中基本概念指令系統(tǒng)CPU必須能夠解碼并執(zhí)行的機器指令很少一旦計算機可以執(zhí)行一些基本的而且是精選的操作，加入額外的操作理論上是不會改變計算機的能力的是否充分利用這種特性導致了兩種不同的計算機設計：CISC(complex instruction set computer)

26、RISC(reduced instruction set computer)第4章計算學科中基本概念CISC最初人們采用的是進一步增強原有指令的功能，并設置更為復雜的指令的方法采用這種設計思路的計算機被稱為復雜指令系統(tǒng)計算機（CISC）。CISC的思路是由IBM公司提出的，并以1964年IBM研制的IBM 360系統(tǒng)為代表。 第4章計算學科中基本概念CISC缺點80%的指令只在20%的運行時間里用到；一些指令非常繁雜，而執(zhí)行效率甚至比用幾條簡單的基本指令組合的實現(xiàn)還要慢。龐雜的指令系統(tǒng)也給超大規(guī)模集成電路（VLSI）的設計帶來了困難，它不但不利于設計自動化技術的應用，延長了設計周期，增加了成本

27、，容易增加設計中出現(xiàn)錯誤的機會，從而降低了系統(tǒng)的可靠性。 第4章計算學科中基本概念RISC思路主要是通過減少指令總數(shù)和簡化指令的功能來降低硬件設計的復雜度，從而提高指令的執(zhí)行速度。優(yōu)點:與CISC技術相比簡化了指令系統(tǒng)，適合超大規(guī)模集成電路的實現(xiàn)； 提高了機器執(zhí)行的速度和效率；降低了設計成本，提高了系統(tǒng)的可靠性； 提供了直接支持高級語言的能力，簡化了編譯程序的設計。第4章計算學科中基本概念機器指令機器指令系統(tǒng)每臺數(shù)字電子計算機在設計中，都規(guī)定了一組指令。機器語言用機器指令形式編寫的程序。在裸機級，計算機語言關于算法的描述采用的是實際機器的機器指令，它的符號集是0，1，支撐實際機器的理論是圖靈機

28、等計算模型；在圖靈機等計算模型理論的指導下，有關設計形態(tài)的主要成果有馮諾依曼型計算機等具體實現(xiàn)思想和技術，以及各類數(shù)字電子計算機產(chǎn)品。第4章計算學科中基本概念計算機語言在裸機級所取得的主要成果計算機語言抽象理論設計裸機級的主要內(nèi)容和成果 語言的符號集為：0，1；用機器指令對算法進行描述圖靈機（過程語言的基礎）、波斯特系統(tǒng)（字符串處理語言的基礎）、-演算（函數(shù)式語言的基礎）等計算模型馮 諾 依曼型計算機等實現(xiàn)技術；數(shù)字電子計算機產(chǎn)品第4章計算學科中基本概念4.4 機器指令與匯編語言第4章計算學科中基本概念匯編語言匯編語言實際上是由一組匯編指令構成的語言。每一條匯編指令用某個西文字符串的縮寫來表示

29、其所代表的操作，用符號來代表數(shù)據(jù)的二進制、八進制和十進制數(shù)字序列。大多數(shù)情況下，一條匯編指令對應一條機器指令，少數(shù)對應幾條機器指令。例如，下面是幾條匯編指令的操作符，右邊中文是名稱。 add 加法 idiv 有符號除法 mul 無符號乘法 neg 求補 xchg 交換 test 邏輯比較 jmp 無條件轉移第4章計算學科中基本概念匯編語言采用字符和十進制數(shù)來代替二進制代碼的思想。例3.10 對2+6進行計算的算法描述用機器指令對“2+6”進行計算的算法描述： 10110 00010 10匯編語言對“2+6”進行計算的算法描述： MOV AL，6 ADD AL，2 MOV VC，AL 第4章計算

30、學科中基本概念匯編語言語句與特定的機器指令有一一對應的關系，但是它畢竟不同于由二進制組成的機器指令，它還需要經(jīng)匯編程序翻譯為機器指令后才能運行。匯編語言源程序經(jīng)匯編程序翻譯成機器指令，再在實際的機器中執(zhí)行。就匯編語言的用戶而言，該機器是可以直接識別匯編語言的，從而產(chǎn)生了一個屬于抽象形態(tài)的重要概念，即虛擬機的概念。一般說來，匯編程序被看成是系統(tǒng)軟件的一部分。 第4章計算學科中基本概念匯編語言當然，匯編語言在可讀性和編寫程序時仍然是不能令人滿意的，這導致進一步發(fā)展了高級程序設計語言。不過，由于高級語言在使用時通常還是要通過編譯程序逐步將高級語言寫的程序翻譯成機器指令的程序，而這種翻譯的結果往往不如

31、機器指令或匯編語言寫的程序效率高，所以，直到今天，不少工程師在系統(tǒng)軟件的開發(fā)中還在使用機器指令和匯編語言。第4章計算學科中基本概念4.5 算法、數(shù)據(jù)結構與程序第4章計算學科中基本概念4.5 算法、數(shù)據(jù)結構與程序第4章計算學科中基本概念算法的歷史簡介 公元825年，阿拉伯數(shù)學家阿科瓦里茨米（AlKhowarizmi）寫了著名的波斯教科書（Persian Textbook），書中概括了進行四則算術運算的法則?！八惴ā保ˋlgorithm）一詞就來源于這位數(shù)學家的名字。后來，韋氏新世界詞典將其定義為“解某種問題的任何專門的方法”。而據(jù)考古學家發(fā)現(xiàn)，古巴比倫人在求解代數(shù)方程時，就已經(jīng)采用了“算法”的思

32、想。 第4章計算學科中基本概念丟番圖方程的可解性問題 古希臘數(shù)學家丟番圖（Diophantus）：代數(shù)學之父在算術（Arithmetica）一書中提出了有關兩個或多個變量整數(shù)系數(shù)方程的有理數(shù)解問題。對于具有整數(shù)系數(shù)的不定方程，如果只考慮其整數(shù)解，這類方程就叫做丟番圖方程。“丟番圖方程可解性問題”的實質(zhì)為：能否寫出一個可以判定任意丟番圖方程是否可解的算法？ 第4章計算學科中基本概念一個未知數(shù)的線性丟番圖方程的解ax=b，只要a能整除b，就可判定其有整數(shù)解，該整數(shù)解即b/a。第4章計算學科中基本概念兩個未知數(shù)的線性丟番圖方程 的解ax+by=c，先求出a和b的最大公因子d，若d能整除c，則該方程有

33、解（整數(shù)解）。 問：方程13x+26y=52有無整數(shù)解？答：13和26的最大公因子是13，13又可整除52，故該方程有整數(shù)解（如x=2，y=1即方程的解）。例4.2 問：方程2x+4y=15有無整數(shù)解？答：2和4的最大公因子是2，2不能整除15，故該方程無整數(shù)解。 第4章計算學科中基本概念兩個未知數(shù)的線性丟番圖方程 的解：歐幾里德算法 給定兩個正整數(shù)m和n，求它們的最大公因子，即能同時整除m和n的最大正整數(shù)。步驟如下：（1）以n除m，并令所得余數(shù)為r（r必小于n）；（2）若r=0，算法結束，輸出結果n；否則，繼續(xù)步驟（3）；（3）將n置換為m，r置換為n，并返回步驟（1）繼續(xù)進行。第4章計算學

34、科中基本概念例4.3 設m=56，n=32，求m、n的最大公因子算法如下:（1）32除56余數(shù)為24；（2）24除32余數(shù)為8；（3）8除24余數(shù)為0，算法結束，輸出結果8。答：m、n的最大公因子為8。歐幾里德算法既表述了一個數(shù)的求解過程，又表述了一個判定過程，該過程可以判定“m和n是互質(zhì)的”（即除1以外，m和n沒有公因子）這個命題的真假。第4章計算學科中基本概念不難想象，不同的求解方法將產(chǎn)生出不同的算法，不同的算法將使我們設計出不同的程序，而決定這個程序功能的本質(zhì)是計算方法及其算法。一般地說，對不同計算方法過程的抽象描述就產(chǎn)生了相應的不同算法，但同一算法由不同的人來寫程序則完全可能設計出差別

35、很大的程序。憑直覺想象給出的算法往往不是最好的算法。 第4章計算學科中基本概念算法算法的定義和特征 第4章計算學科中基本概念 算法被認為是計算科學的核心問題之一。算法被認為是計算科學的核心問題之一。 第4章計算學科中基本概念1算法的一些定義 定風1：給定問題和設備，一個算法是用該設備可理解的語言表示的，解決這個問題的一種方法的精確刻劃。特別，算法具有下列特征屬性： (1) 算法應用于一個具體的輸入集合或問題描述將在有窮步動作序列之后得到結果； (2) 該序列有一個唯一的初始動作； (3) 該序列中的每一個動作有一個唯一的后繼動作； (4) 該序列終止時或者得到這個問題的解，或者因該問題不可解而

36、獲得不可解說明。第4章計算學科中基本概念1算法的一些定義 定風1：給定問題和設備，一個算法是用該設備可理解的語言表示的，解決這個問題的一種方法的精確刻劃。特別，算法具有下列特征屬性： (1) 算法應用于一個具體的輸入集合或問題描述將在有窮步動作序列之后得到結果； (2) 該序列有一個唯一的初始動作； (3) 該序列中的每一個動作有一個唯一的后繼動作； (4) 該序列終止時或者得到這個問題的解，或者因該問題不可解而獲得不可解說明。第4章計算學科中基本概念定義定義2（Knuth算法定義）算法定義） 一個算法，就是一個有窮規(guī)則的集合，其中之規(guī)則一個算法，就是一個有窮規(guī)則的集合，其中之規(guī)則確定了一個解

37、決某一特定類型問題的運算序列。此外，確定了一個解決某一特定類型問題的運算序列。此外，算法的規(guī)則序列須滿足如下五個重要條件（特性）：算法的規(guī)則序列須滿足如下五個重要條件（特性）： (1) (1) 有窮性。算法必須總是在執(zhí)行有窮步之后結束；有窮性。算法必須總是在執(zhí)行有窮步之后結束； (2) (2) 確定性。算法的每一個步驟必須是確切地定義確定性。算法的每一個步驟必須是確切地定義的；的； (3) (3) 輸入。算法有零個或多個輸入；輸入。算法有零個或多個輸入； (4) (4) 輸出。算法有一個或多個輸出，即與輸入有某輸出。算法有一個或多個輸出，即與輸入有某個特定關系的量；個特定關系的量； (5) (

38、5) 能行性。算法中有待執(zhí)行的運算和操作必須是能行性。算法中有待執(zhí)行的運算和操作必須是相當基本的，即是說，它們原則上都是能夠精確地進行相當基本的，即是說，它們原則上都是能夠精確地進行的，而且用筆和紙做有窮次就可以完成。的，而且用筆和紙做有窮次就可以完成。第4章計算學科中基本概念2算法的重要特性有窮性：一個算法在執(zhí)行有窮步之后必須結束。 如在歐幾里德算法中，由于m和n均為正整數(shù)，在步驟（1）之后，r必小于n，若r0，下一次進行步驟（1）時，n的值已經(jīng)減小，而正整數(shù)的遞降序列最后必然要終止。因此，無論給定m和n的原始值有多大，步驟（1）的執(zhí)行都是有窮次。第4章計算學科中基本概念2算法的重要特性確定

39、性：算法的每一個步驟必須要確切地定義。即算法中所有有待執(zhí)行的動作必須嚴格而不含混地進行規(guī)定，不能有歧義性。 如歐幾里德算法中，步驟（1）中明確規(guī)定“以n除m”，而不能有類似“以n除m或以m除n”這類有兩種可能做法的規(guī)定。輸入：算法有零個或多個的輸入，即在算法開始之前，對算法最初給出的量。 如歐幾里德算法中，有兩個輸入，即m和n。第4章計算學科中基本概念2算法的重要特性輸出：算法有一個或多個的輸出，即與輸入有某個特定關系的量，簡單地說就是算法的最終結果。 如在歐幾里德算法中只有一個輸出，即步驟（2）中的n。能行性：算法中有待執(zhí)行的運算和操作必須是相當基本的。 如：歐幾里德算法最終得出正確的結果。

40、 第4章計算學科中基本概念2算法的重要特性輸出：算法有一個或多個的輸出，即與輸入有某個特定關系的量，簡單地說就是算法的最終結果。 如在歐幾里德算法中只有一個輸出，即步驟（2）中的n。能行性：算法中有待執(zhí)行的運算和操作必須是相當基本的。 如：歐幾里德算法最終得出正確的結果。 第4章計算學科中基本概念2算法的重要特性有窮性和能行性是算法最重要的兩個特征。對有些問題來說，如果我們給出了一個類似于算法的有窮運算序列，而它對某些輸入可能不停機，那么，我們就稱這樣的運算序列為一個過程。算法和過程都滿足能行性和確定性，唯一的本質(zhì)區(qū)別是算法的執(zhí)行必須終止，而過程則不然，它可以永不停止。需要指出的是，高級程序設

41、計語言中也有過程的概念，但與這里所講的過程不同，那里實際上指的是一種子程序。 第4章計算學科中基本概念3算法的形式化定義 算法是一個四元組，即（Q，I，F(xiàn)）。其中：（1）Q是一個包含子集I和的集合，它表示計算的狀態(tài)；（2）I表示計算的輸入集合；（3）表示計算的輸出集合；（4）F表示計算的規(guī)則，它是一個由Q到它自身的函數(shù)，且具有自反性，即對于任何一個元素qQ，有F(q)=q。第4章計算學科中基本概念算法算法實例 第4章計算學科中基本概念例4.4 求1+2+3+100 設變量X表示加數(shù)，Y表示被加數(shù)，用自然語言將算法描述如下：（1）將1賦值給X；（2）將2賦值給Y；（3）將X與Y相加，結果存放在X

42、中；（4）將Y加1，結果存放在Y中；（5）若Y小于或等于100，轉到步驟（3）繼續(xù)執(zhí)行；否則，算法結束，結果為X。第4章計算學科中基本概念例4.5 求解調(diào)和級數(shù)設變量X表示累加和，變量I表示循環(huán)的次數(shù)，自然語言描述算法如下：（1）將0賦值給X；（2）將1賦值給I；（3）將X與1/I相加，然后把結果存入X；（4）將I加1； （5）若I大于等于N，算法結束，結果為X；否則轉到步驟（3）繼續(xù)執(zhí)行。 nHn1312111 第4章計算學科中基本概念例4.6 求解斐波那契數(shù) 0，1，1，2，3，5，8，13，21，34， （1）來 源 于 1 2 0 2 年 意 大 利 數(shù) 學 家 斐 波 那 契（L.P

43、.Fibonacci）在其珠算之書（Liber Abaci）中提出的一個“兔子問題”：假設一對剛出生的兔子一個月后就能長大，再過一個月就能生下一對兔子，并且此后每個月都能生一對兔子，且新生的兔子在第二個月后也是每個月生一對兔子。問：一對兔子一年內(nèi)可繁殖成多少對兔子？第4章計算學科中基本概念在序列（1）中，每個數(shù)都是它的前兩個數(shù)之和，F(xiàn)n表示這個序列的第n個數(shù)，該序列可以形式化的定義為： F0=0，F(xiàn)1=1，F(xiàn)n+2=Fn+1+Fn，n0斐波那契數(shù)列還是一個關于加法算法的典型實例。第4章計算學科中基本概念設變量X表示前一個數(shù)的值，即定義中的Fn，變量Y表示當前數(shù)的值，即定義中的Fn+1，變量Z表

44、示后一個數(shù)的值，即定義中的Fn+2。那么求解問題的自然語言描述如下： 第4章計算學科中基本概念算法設計（1）如果=0，那么將0賦值給Y，并輸出Y，轉步驟（11）繼續(xù)執(zhí)行；（2）將0賦給X，將1賦值給Y；（3）輸出X、Y；（4）將1賦值給I；（5）如果I大于-1，則轉到步驟（11），否則繼續(xù)執(zhí)行；（6）將X和Y的和賦值給Z；（7）將Y賦值給X；（8）將Z賦值給Y；（9）將Y輸出；（10）將I加1，轉步驟（5）繼續(xù)執(zhí)行；（11）算法結束。第4章計算學科中基本概念算法算法的表示方法第4章計算學科中基本概念原語一個算法的表達需要使用一些語言形式自然語言“Visiting grandchildren c

45、an be nerve-racking”,可能即意味著孫子孫女導致了很多問題，也表示去看他們可能會有問題圖形語言：很少人能夠根據(jù)折紙圖給出的步驟成功地疊出一只鳥來，但一個專門學習過折紙的學生可以輕松完成當用來描述算法的語言并沒有被準確定義或者沒有給予足夠信息的時候，交流就會產(chǎn)生問題第4章計算學科中基本概念原語通過建立一個可以描述算法的意義明確的基本塊（原語）集合，計算機科學即就可以解決上述的勾通問題原語描述算法需要建立一個統(tǒng)一的細節(jié)描述級別，原語連同一組表達了原語如何表達復雜的想法的規(guī)定組成了一種程序設計語言組成語法：原語的符號表示語義：表達了原語的意義第4章計算學科中基本概念1自然語言缺點由

46、于自然語言的歧義性，容易導致算法執(zhí)行的不確定性；自然語言的語句一般太長，從而導致了用自然語言描述的算法太長；由于自然語言表示的串行性，因此，當一個算法中循環(huán)和分支較多時就很難清晰地表示出來；自然語言表示的算法不便翻譯成計算機程序設計語言理解的語言。 第4章計算學科中基本概念2流程圖 它采用美國國家標準化協(xié)會ANSI（American National Standard Institute）規(guī)定的一組圖形符號來表示算法。流程圖可以很方便地表示順序、選擇和循環(huán)結構，而任何程序的邏輯結構都可以用順序、選擇和循環(huán)結構來表示，流程圖可以表示任何程序的邏輯結構。用流程圖表示的算法不依賴于任何具體的計算機和

47、計算機程序設計語言，第4章計算學科中基本概念（1）求解例4.4的算法流程圖 X=1 Y=2 X=X+Y Y=Y+1 Y100 結 束 開 始 Y N 第4章計算學科中基本概念（2）求解例4.5的算法流程圖 開 始 X=0 I=1 X=X+1/I I=I+1 I=N 結 束 N Y 第4章計算學科中基本概念（3）求解例4.6的算法流程圖 開 始 n = 0 X = 0 ， Y = 1 P rin t X ， Y I= 1 I n -1 Z = X + Y X = Y Y = Z P rin t Y I= I+ 1 結 束 Y = 0 P rin t Y Y N Y N 第4章計算學科中基本概念3

48、偽代碼（1）求解例4.4的偽代碼算法描述：BEGIN(算法開始) 1 X 2 Ywhile（Y=n)END（算法結束）第4章計算學科中基本概念（3）例4.6的偽代碼算法描述： BEGINif n = =0 0 Y Print Y else 第4章計算學科中基本概念4計算機程序設計語言 計算機程序設計語言描述的算法（程序）是清晰的、簡明的，最終也能由計算機處理的。缺點：算法的基本邏輯流程難于遵循。與自然語言一樣，程序設計語言也是基于串行的用特定程序設計語言編寫的算法限制了與他人的交流，不利于問題的解決；要花費大量的時間去熟悉和掌握某種特定的程序設計語言；要求描述計算步驟的細節(jié)，而忽視算法的本質(zhì)。

49、第4章計算學科中基本概念例4.4的計算機程序設計語言（C語言）的算法描述： main() int X,Y; X=1; Y=2; while(Y=100) X=X+Y; Y=Y+1; ; printf(%d,X);第4章計算學科中基本概念例4.5的計算機程序設計語言（C語言）的算法描述 main() int n; float X,I; printf(Please input n:); scanf(%d,&n); X=0; I=1; 第4章計算學科中基本概念算法算法分析第4章計算學科中基本概念在計算機科學研究中，事實上存在一條規(guī)律：一個問題，當它的描述及其求解方法或求解過程可以用構造性數(shù)學

50、描述，而且該問題所涉及的論域為有窮，或雖為無窮但存在有窮表示時，那么，這個問題一定能用計算機來求解；反過來，凡是能用計算機求解的問題，也一定能對該問題的求解過程數(shù)學化，而且這種數(shù)學化是構造性的。算法分析考慮的問題； 第4章計算學科中基本概念當一個問題的求解獲得了計算方法和算法時，并不等于萬事大吉了。在許多情況下，找到求解一個問題的算法只是走完了第一步。至于現(xiàn)實是否可以計算，則取決于算法的存在性和計算的復雜性，即取決于該問題是否存在求解算法，算法所需要的時間和空間在數(shù)量級上能否被接受。要注意的是，有的問題雖然存在求解問題的計算方法，但是，不存在算法。原因有兩種可能：一是計算方法可能不是構造性的；

51、二是雖為構造性的，但計算方法不能保證計算過程在任何初值的情況下都能結束。算法分析考慮的問題； 第4章計算學科中基本概念解一個問題，往往有若干不同的算法，這些算法決定著根據(jù)該算法編寫的程序性能的好壞。那么，在保證算法正確性的前提下，如何確定算法的優(yōu)劣就是一個值得研究的課題。在算法的分析中，一般應考慮以下3個問題： （1）算法的時間復雜度； （2）算法的空間復雜度； （3）算法是否便于閱讀、修改和測試。 算法分析考慮的問題； 第4章計算學科中基本概念使用計算機計算各種問題，需要存儲空間、計算時間。不同的算法計算所需要的時間和空間是不同的。所謂算法的復雜性就是對算法計算所需要的時間和空間的一種度量。

52、由于不同的計算機千差萬別，運算速度和字長可以相差很大，因此，不可能用算法在某一臺計算機上計算所需要的實際的時間和存儲單元（空間）去衡量這個算法的復雜性。那么，怎樣才能準確刻劃算法的計算復雜性呢？ 什么是算法的復雜性呢？第4章計算學科中基本概念科學家們采用了與問題規(guī)模大小相聯(lián)系的一個近似函數(shù)（稱為漸近增長率）來刻畫算法的計算復雜度。該函數(shù)表示了算法隨問題規(guī)模大小變化引起的算法中抽象的基本運算執(zhí)行的次數(shù)或存儲空間量的變化規(guī)律。例如，某個計算問題當輸入規(guī)模分別為1，2，3，n時，經(jīng)分析算法中抽象的基本運算次數(shù)分別為1，4，9，n2，那么，就可以用函數(shù)n2來刻劃這個算法的時間復雜性，并稱這個算法的時間

53、復雜性度量為(n2)級。（1）算法的時間復雜度； 第4章計算學科中基本概念有了復雜性度量函數(shù)，一旦選定具體計算機，可以根據(jù)這臺計算機對某個n值的實際運算速度比較準確地估算出對其他的n值完成計算所需要的時間。于是，對各種算法的復雜性進行分析的關鍵是要設法去找出這樣的函數(shù)，它涉及到與數(shù)學密切相關的算法的設計原理、思想和方法，算法分析是具有智力挑戰(zhàn)性的研究課題。（1）算法的時間復雜度； 第4章計算學科中基本概念用T(n)表示，n表示問題規(guī)模的大小。使用一個記號Order（數(shù)量級）的第一個字母，允許使用“=”代替“”。如n2+n+1=(n2)（1）算法的時間復雜度； 第4章計算學科中基本概念（1）算法

54、的時間復雜度； 設f(n)是一個關于正整數(shù)n的函數(shù)，若存在一個正 整 數(shù) n0和 一 個 常 數(shù) C ， 當 n n0時 ， T(n) C f(n) 均成立，則稱f(n)為T(n)的同數(shù)量級的函數(shù)。算法時間復雜度T(n)可表示為： T(n)= (f(n)第4章計算學科中基本概念常見的大表示形式有： (1) ：稱為常數(shù)級； (logn)： 稱為對數(shù)級； (n) ：稱為線性級； (nc) ：稱為多項式級； (cn) ：稱為指數(shù)級； (n!) ：稱為階乘級。第4章計算學科中基本概念 在梵天塔問題中，需要移動的盤子次數(shù)為在梵天塔問題中，需要移動的盤子次數(shù)為h(n)=2n-1，則該問題的算法時間復雜度表

55、示，則該問題的算法時間復雜度表示為為 (2n)；例；例4.4的算法時間復雜度表示為的算法時間復雜度表示為 (1)；例例4.5的算法時間復雜度表示為的算法時間復雜度表示為 (n)；例；例4.6的的算法時間復雜度表示為算法時間復雜度表示為 (n)等等。等等。第4章計算學科中基本概念 一般而言，對于較復雜的算法，應將它分一般而言，對于較復雜的算法，應將它分成容易估算的幾個部分，然后用成容易估算的幾個部分，然后用 的求解原則的求解原則計算整個算法的時間復雜度，最好不要采用計算整個算法的時間復雜度，最好不要采用指數(shù)級和階乘級的算法，而應盡可能選用多指數(shù)級和階乘級的算法，而應盡可能選用多項式級或線性級等時

56、間復雜度較小的算法。項式級或線性級等時間復雜度較小的算法。另外，還要在算法最好、平均和最壞的情況另外，還要在算法最好、平均和最壞的情況下區(qū)別執(zhí)行效率的不同。下區(qū)別執(zhí)行效率的不同。第4章計算學科中基本概念 在階乘級的算法中，如果問題規(guī)模在階乘級的算法中，如果問題規(guī)模n為為10，則算法時間復雜度為則算法時間復雜度為10?。ǎ。?，628，800）。）。若要檢驗若要檢驗10！種情況，設每種情況需要！種情況，設每種情況需要1毫秒毫秒的計算時間，則整個計算將需的計算時間，則整個計算將需1小時左右。一小時左右。一般來說，如果選用了階乘級的算法，則當問般來說，如果選用了階乘級的算法，則當問題規(guī)模等于或者大于

57、題規(guī)模等于或者大于10時，就要認真考慮算時，就要認真考慮算法的適用性問題。法的適用性問題。 第4章計算學科中基本概念算法的空間復雜度指算法在執(zhí)行過程中所占存儲空間的大小，用S(n)表示，S為英文單詞Space的第一個字母。與算法的時間復雜度相同算法的空間復雜度S(n)也可表示為： S(n)= (g(n)。 第4章計算學科中基本概念算法算法的研究第4章計算學科中基本概念算法算法：定義一項工作如何完成的步驟的集合在一臺機器可以完成一個任務之前，必須找到完成這個任務的算法并且用與機器兼容的方式來描述一個與機器兼容的算法的描述程序算法的研究開始是作為數(shù)學的一個學科目標：找到描述特定類型問題是如何被解決

58、的指令的集合，如Euclidean算法一旦一個完成任務的算法被找到，任務的實現(xiàn)就不再需要對算法原理的理解，任務的實現(xiàn)僅僅是遵循算法的只是過程現(xiàn)有的解決問題需要的智慧被編碼進了算法第4章計算學科中基本概念算法轉化為智慧通過使用算法來得到并轉化智慧，我們才可以構建起可以表現(xiàn)智慧行為的機器。機器表現(xiàn)的智能等級受到通過算法轉化的智慧所限制如果沒有解決問題的算法，意味著問題的解決方案超出了機器的能力范圍算法的開發(fā)就成了計算機領域的一個主要目標如何找到算法一個十分接近于尋找通用問題解決方案描述這個算法轉變?yōu)橐粋€清晰的指令的集合（程序設計語言描述）第4章計算學科中基本概念計算機技術別用于復雜問題（大型軟件系

59、統(tǒng)）不僅僅包括實現(xiàn)任務的單個算法的開發(fā)還要求對組件之間的交互進行設計軟件工程：借鑒了工程領域、項目管理領域、人力資源管理以及程序語言設計領域的經(jīng)驗第4章計算學科中基本概念執(zhí)行算法的機器的設計和實現(xiàn)數(shù)據(jù)的存儲數(shù)據(jù)的操作體系結構中涵蓋了對現(xiàn)今技術的討論我們的目標不是去熟知類似當今體系結構是如何用電路來實現(xiàn)這樣的細節(jié)問題，那將會導致過分陷入電子工程學科正如昨天的齒輪驅(qū)動的計算機讓位于電子設備一樣，今天的電子技術也許很快也被其它的技術所取代第4章計算學科中基本概念理想情況下希望計算機的體系結構是我們的有關算法過程知識的延續(xù)，并且不應該被技術能力酸限制使我們的算法知識在當代機器體系結構的發(fā)展背后起推動作

60、用，而不僅僅是從技術的要求觸發(fā)來解頂機器的設計構建允許使用多個指令序列來代替算法的機器是可能的這些指令被同時執(zhí)行或者作為第4章計算學科中基本概念機器于外部世界的接口的設計于計算機的設計緊密相連算法是如何機器中的？機器是如何被告知執(zhí)行的是哪一個算法？第4章計算學科中基本概念計算理論對解決越來越復雜問題的算法的研究導致了算法過程的最終限制問題如果沒有算法可以解決這個問題，那么算法是不能被機器所解決的，機器僅僅可以解決在算法上可解的問題Godel的不完全定理闡述了在任何傳統(tǒng)算術領域的數(shù)學理論中，有些是既不能證明有不能被推翻的任何對算術系統(tǒng)的徹底研究都超出了算法的能力對算法的限制的研究欲望似的數(shù)學家們設計抽象