第2章計算機科學的基本概念和基本知識ppt課件

.,1,第二章計算機科學的基本概念和基本知識2.1計算模型與二進制數(shù)學不等于計算，但數(shù)學確實起源于對計算的研究。數(shù)學、計算模型（計算方法、數(shù)學機器）、形式化與形式化方法我們說，形式是事物的內容存在的外在方式、形狀和結構的總和。所謂形式化是將事物的內容與形式相分離，用事物的某種形式來表示事物。形式化方法是在對事物描述形式化的基礎上，通過研究事物的形式變化規(guī)律來研究事物變化規(guī)律的全體方法的總稱。1.1.1計算模型與圖靈機所謂計算模型是刻劃計算這一概念的一種抽象的形式系統(tǒng)或數(shù)學系統(tǒng)，而算法是對計算過程步驟（或狀態(tài)的一種刻,.,2,劃，是計算方法的一種能行實現(xiàn)方式。在計算機科學中，我們通常所說的計算模型，并不是指在其靜態(tài)或動態(tài)數(shù)學描述基礎上建立求解某一(類)問題計算方法的數(shù)學模型，而是指具有狀態(tài)轉換特征，能夠對所處理的對象的數(shù)據(jù)或信息進行表示、加工、變換、輸出的數(shù)學機器。由于觀察計算的角度不同，產(chǎn)生了各種不同的計算模型。遞歸函數(shù)、Turing機等(1)s(x)x1（后繼函數(shù)）(2)o(x)0（零函數(shù)）(3)Uj(n)(x1，x2，xn)xj（射影函數(shù)）由初始函數(shù)和有限次使用算子可以構造各種復雜的遞歸函數(shù)，或者可計算函數(shù)。圖靈機的示意圖,.,3,控制器的命令可表示為：（狀態(tài)，符號）（寫符號，移動，狀態(tài)）；控制器一旦圖靈機在運行中進入了一個狀態(tài)，而且這個狀態(tài)是一個結束狀態(tài)，那么，圖靈機就停機，計算任務宣告完成，此時帶上的內容就是計算的輸出結果。,.,4,例1M的字母表A0，1，b，b表示空格。狀態(tài)集Qq1，q2，q3，其中，指定q1是開始狀態(tài)，q3是終止狀態(tài)。M的程序（控制器的命令）如下：q101Rq1；q110Rq1；q1bbRq2；q2bbLq3；q200Hq1；q211Hq1；對圖靈機的工作過程從不同的角度考察，可以給予不同的解釋。第一，把圖靈機看作識別器，即判斷帶子上最初的內,.,5,容能否被圖靈機所接受。假定圖靈機從左向右掃描完帶子上的內容后停機則為接受，否則為不接受。例2一臺圖靈機可以設計成識別下面的序列：1000110,10011101,010101011。第二，把圖靈機看作生成器，對給定的輸入集合，考察輸出集合，并研究輸入輸出集合性質之間的關系，這就研究了圖靈機的生成能力。例3設一臺圖靈機的輸入集合為In1n0nnN，可設計一臺圖靈機，對給定的輸入集合In，得到輸出集合Out0n1nnN。其中，N是全體自然數(shù)的集合。第三，把圖靈機看作計算器，相當于一個函數(shù)。圖靈機的輸入是函數(shù)的自變量的值，圖靈機的輸出是函數(shù)的值。例4圖靈機可以計算下列函數(shù)：,.,6,(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)。第一和第二個函數(shù)讀者不難從圖靈機的定義出發(fā)感悟到它們是圖靈機可以計算的函數(shù)，而第三個函數(shù)就比較復雜，一時難于判斷。順便提一下，第三個函數(shù)叫做阿克曼函數(shù)，它是阿克曼（W.Ackermann）在研究原始遞歸函數(shù)和遞歸函數(shù)的關系時給出的。這個函數(shù)在計算理論中具有重要價值。事實上，圖靈機還可以計算形式上比第三個函數(shù)更復雜的函數(shù)。沿著這樣一種思路，圖靈機被證明具有很強的計算能力，它與30年代發(fā)展的遞歸函數(shù)論（一種能行可計算性理,.,7,論）中一類最一般的可計算函數(shù)（部分遞歸函數(shù)或部分可計算函數(shù)）在計算表達能力上是等價的。然而，圖靈機簡潔的構造和運行原理隱含了存儲程序的原始思想，深刻地揭示了現(xiàn)代通用電子數(shù)字計算機最核心的內容。圖靈獎2.1.2二進制也許是圖靈機讀寫帶上只出現(xiàn)兩個符號啟發(fā)了研究者，在當時的技術條件下，從便于元器件的設計和制造考慮，計算機的研制很自然地選擇了二進制。后來的實踐也證明了這種選擇具有極大的優(yōu)點。十進制數(shù)的表示例如，1997.630這個數(shù)可以寫成：1997.6301103910291017100610-1310-2010-3,.,8,一般地，任何一個十進制數(shù)S都可以表示為：Sknkn-1k0.k-mkn10nkn-110n-1k0100k-m10-m-mki10iin其中，10稱為十進制的基數(shù),ki0,1,2,3,4,5,6,7,8,9，m，n為正整數(shù)。小數(shù)點的位置不言自明。二進制和十進制一樣，是一種數(shù)制，它用于表示數(shù)的符號（數(shù)字）由于在書寫中的位置不同而具有不同的值。二進制表示數(shù)的符號只有兩個，即0和1，其數(shù)值與十進制中的0和1相同。此外，與十進制不同之處在于二進制數(shù)是逢二進一。,.,9,例如，十進制數(shù)與二進制數(shù)中的一些可作如下對應：十進制二進制(0)(0)(1)(1)(2)(10)(3)(11)(4)(100)(5)(101)(9)(1001)(10)(1010)一般地，任何一個二進制數(shù)S都可以表示為：,.,10,Sknkn-1k0.k-mkn2nkn-12n-1k020k-m2-m-mki2iin其中，2稱為二進制的基數(shù)，ki0,1,m,n為正整數(shù)。進一步，讀者可從十進制數(shù)和二進制數(shù)的一般表示公式得到啟發(fā)，將這種表示推廣到更一般的任意進制，不同之處只是基數(shù)不一樣。二進制的運算規(guī)則比十進制的運算規(guī)則簡單得多。只要建立兩種進制的數(shù)據(jù)之間的轉換方法，那么，二進制將具有更多的優(yōu)勢。計算機的理論基礎是邏輯和代數(shù)。當二進制與同樣只使用“真”和“假”兩個值的邏輯代數(shù)建立了聯(lián)系后，這就為計算機的邏輯設計提供了便利的工具。,.,11,2.2存儲程序式計算機的基本結構與工作原理圖靈機的出現(xiàn)為現(xiàn)代計算機的發(fā)明提供了重要的思想。圖靈機的帶子可以看成是計算機的存儲設備，數(shù)據(jù)可以存儲在上面，也可以根據(jù)需要擦去。圖靈機的命令相當于一組事先設計、存儲好了的程序，它們在控制器安排下，決定讀寫頭的每一步操作。這樣一種數(shù)學機器，如果不考慮它的實用性，就思想和原理而言，確實包含了存儲程序的重要思想。程序與存儲程序式計算機圖靈機誕生后不到十年，在以馮諾依曼為代表的一批科學家的努力下，現(xiàn)代存儲程序式電子數(shù)字計算機的基本結構與工作原理被確定下來。它主要由如下的五部分組成（見P8圖）：存儲器，運算器，控制器，輸入設備，輸出設備,.,12,在學科的發(fā)展歷程中，習慣上，人們將不帶有軟件系統(tǒng)的存儲程序式電子數(shù)字計算機系統(tǒng)稱為硬件裸機，將硬件裸機，參與構成硬件裸機的各類部件及其研究范疇統(tǒng)稱為硬件（方向）。2.3數(shù)字邏輯與集成電路數(shù)字邏輯是數(shù)字電路邏輯設計的簡稱，其內容是應用數(shù)字電路進行數(shù)字系統(tǒng)邏輯設計。電子數(shù)字計算機是由具有各種邏輯功能的邏輯部件組成的，這些邏輯部件按其結構可分為組合邏輯電路和時序邏輯電路。組合邏輯電路是由與門、或門和非門等門電路組合形成的邏輯電路；時序邏輯電路是由觸發(fā)器和門電路組成的具有記憶能力的邏輯電路。有了組合邏輯電路和時序邏輯電路，再進行合理的設計和安排，就可以表示和實現(xiàn)布爾代數(shù)的基本運算。而布爾代數(shù)只使用1（真）和0（假）兩個數(shù)，這樣，當二進,.,13,制的加法、乘法等運算與布爾代數(shù)的運算建立了對應關系后，就可以用邏輯部件來實現(xiàn)二進制數(shù)據(jù)的加法、乘法等各種運算。例5基本的“與”、“或”、“非”門電路?！芭c”門電路一般有兩個以上的輸入和一個輸出。圖(a)表示了一個“與”門電路，其輸出P和輸入A、B、C之間的邏輯關系可用下面的式子表示：PABC電路設計中，用高電平信號表示1，低電平信號表示0，那么，“與”門電路只有當輸入A、B、C同時為1時，輸出P才為1，否則，P為0?！盎颉遍T電路可以用圖(b)表示。一般地說，“或”門電路是一種具有邏輯加法功能的電路，它有兩個以上的輸入和,.,14,一個輸出，其輸出P和輸入A、B、C之間的邏輯關系可用下面的式子表示：PABC在具體的電路設計中，如果我們用高電平信號表示1，低電平信號表示0，那么，“或”門電路僅當輸入A、B、C中有一個為1時，輸出P就為1，否則，P為0?！胺恰遍T電路可以用圖(c)表示。一般地說，“非”門電路是一種具有邏輯取反功能的電路，它只有一個輸入和一個輸出，其輸出P和輸入A之間的邏輯關系可用下面的式子表示：PA在具體的電路設計中，如果我們用高電平信號表示1，低電平信號表示0，那么，“非”門電路當輸入A為0時，輸出P就為1，否則，當輸入A為1時，輸出P為0。,.,15,“與”、“或”、“非”三種門電路示意圖PPPABCABCA（a）（b）（c）將布爾代數(shù)和前面談到的二進制聯(lián)系起來，我們可以看出，“與”、“或”、“非”門電路的作用與集合運算“交”、“并”、“補”是一致的。一旦門電路中僅使用兩個電平信號0和1，引入二進制及其運算規(guī)則，那么，用門電路及其組,.,16,合就可以實現(xiàn)二進制的各種運算，而對復雜電路的計算，如電路的化簡就有可能通過布爾代數(shù)的方法進行。事實上也正是如此。由此可見，真正構成計算機科學基本的、核心的內容是圍繞計算而展開的大量帶有規(guī)律性的知識，而不是具體的實現(xiàn)技術。因為，在將來，我們完全可能發(fā)展一種能表示二進制數(shù)及其運算的新技術，它比今天的微電子技術精度更高、生產(chǎn)價格更便宜。如果真是那樣，這種技術就可能取代微電子技術在計算科學中的地位。近年來科學研究的發(fā)展已顯現(xiàn)出一些很有希望但尚不成熟的技術，如光電子技術，金屬表面處理技術等。當然，程序技術在可預見的將來尚不太可能被別的技術所代替，原因是它與各種應用相聯(lián)系，而且在形式上易于反映能行性這一本質的計算特征，在表達形式上與通常算法的描述較為接近,設計和生產(chǎn)的成本也比較低，又不存在工業(yè)污染的問題，所以不,.,17,易被取代。因此，我們常說，從這個意義上講，軟件技術比微電子技術對計算科學更重要一些。2.4機器指令與匯編語言用計算機求解一個問題，必須事先編制好程序。程序是由指令組成的。每一臺計算機都設計規(guī)定了一組指令集合，稱為機器指令系統(tǒng)。機器指令的格式一般分為兩部分，如下所示：指令格式：操作碼地址部分其中，操作碼指出運算的種類，如，跳轉等，地址部分用來指示參與運算的數(shù)據(jù)保存在什么地方，如存儲器的某個地址或某個寄存器等。操作碼和地址部分都用二進制代碼表示。,.,18,機器指令一般可根據(jù)其功能劃分為以下幾類：(1)控制指令；(2)算術運算指令；(3)邏輯運算指令；(4)移位操作指令；(5)傳送操作指令；(6)輸入/輸出指令。應當注意的是，不同的機器，其指令系統(tǒng)是不同的。指令系統(tǒng)的日漸增大雖然給用戶的程序設計帶來了方便，但也帶來了硬件設計復雜性的增加和因譯碼、存儲、尋址等開銷的增大而使運算速度下降。研究發(fā)現(xiàn)，指令系統(tǒng)存在著改進的必要和可能。真正使研究人員對指令系統(tǒng)進行較大改進的原因是超大規(guī)模集成電路（VLSI）技術的發(fā)展和采用微程序技術實現(xiàn)體系結構設計思想的過程中硬件復雜性的不斷增長帶來的技術上的困難，使人們開始認識到在進行計算機系統(tǒng)設計時，應,.,19,公平對待硬件與軟件的地位，使兩者平衡負擔整個系統(tǒng)的復雜性。這一認識的轉變直接導致了精簡指令系統(tǒng)計算機（RISC）的誕生。所謂RISC是根據(jù)指令系統(tǒng)中各種指令應用的規(guī)律，將最常用的指令，以及一些控制較為簡單的寄存器寄存器的操作與寄存器等一起直接做在VLSI芯片上，靠減少譯碼、存儲、尋址方式和次數(shù)等開銷而大大增加運算速度。實際上，RISC主要是一種體系結構設計的思想，而不只是一種計算機產(chǎn)品。RISC技術由于極大地提高了計算機的運算速度，因而它的問世被認為是計算機體系結構發(fā)展史上的一個里程碑。匯編語言匯編語言實際上是由一組匯編指令構成的語言。每一條匯編指令用某個西文字符串的縮寫來表示其所代表的操作，用符號來代表數(shù)據(jù)的二進制、八進制和十進制數(shù)字序列。大多數(shù)情況下，一條匯編指令對應一條機器指令，少數(shù)對應幾,.,20,條機器指令。例如，下面是幾條匯編指令的操作符，右邊中文是名稱。add加法idiv有符號除法mul無符號乘法neg求補xchg交換test邏輯比較jmp無條件轉移有了匯編語言，就得編寫和設計匯編語言翻譯程序（簡稱匯編程序），專門負責把使用匯編語言書寫的程序翻譯成可直接執(zhí)行的機器指令程序。一般說來，匯編程序被看成是系統(tǒng)軟件的一部分。當然，匯編語言在可讀性和編寫程序時仍然是不能令人滿意的，這導致進一步發(fā)展了高級程序設計語言。不過，由于高級語言在使用時通常還是要通過編譯程序逐步將高級語言寫的程序翻譯成機器指令的程序，而這種翻譯的結果往往不如機器指令或匯編語言寫的程序效率高，所以，直到今天，不少工程師在系統(tǒng)軟件的開發(fā)中還在使用機器指令和匯編語言。,.,21,2.5算法、過程與程序求解一個給定的問題，不同的人常編寫出不同的然而都是正確的程序，這是為什么呢？這里存在兩個層面的問題，一個是與計算方法密切相關的算法問題，另一個是程序設計的技術問題。例6給定兩個整數(shù)，求它們的最大公因數(shù)。不失一般性，設有不全為0的整數(shù)x、y，記gcd(x，y)為它們的最大公因數(shù)，即同時能整除x、y的公因數(shù)中的最大者。顯然，gcd(x，y)可表示為gcd(x，y)maxzz|x，z|y這個問題許多中學生都會解，最常見的有著名的歐幾里德輾轉相除計算方法。當然，還有許多種解法。我們首先從函數(shù)gcd(x，y)的性質出發(fā)來求解。函數(shù)gcd(x，y)具有如下性質：(1)gcd(a，b)gcd(b，a),.,22,(2)gcd(a，b)gcd(a，b)(3)gcd(a，0)|a|(4)gcd(a，b)gcd(b，amodb)，0amodbb（歐幾里德輾轉相除計算方法）根據(jù)以上性質，我們可以設計如下算法：算法A（計算函數(shù)gcd(x，y)）A1.輸入x，y；z是輔助變量；A2.重復執(zhí)行如下操作步驟：(1)若y0，則輸出|x|，算法停止(2)若y0，則zxmody，xy，yz；有了計算函數(shù)gcd(x，y)的算法，用程序設計語言很容易寫出可在計算機上執(zhí)行的程序。算法A的核心是利用了函數(shù)gcd(x，y)的上述第四條性質。倘若我們使用的不是第四,.,23,條性質，那么，算法就會發(fā)生改變。不難想象，不同的求解方法將產(chǎn)生出不同的算法，不同的算法將使我們設計出不同的程序，而決定這個程序功能的本質是計算方法及其算法。一般地說，對不同計算方法過程的抽象描述就產(chǎn)生了相應的不同算法，但同一算法由不同的人來寫程序則完全可能設計出差別很大的程序。憑直覺想象給出的算法往往不是最好的算法。例7用程序變換技術設計的計算函數(shù)gcd(x,y)的程序利用一種叫做程序變換技術的程序設計方法，可以產(chǎn)生計算函數(shù)gcd(x,y)的如下遞歸過程性程序：Proceduregcd(x，y:int，varz:int)；beginifx0thenz:y；xy&x0thengcd(x，yx，z)；,.,24,xy&x0thengcd(y，x，z)endifend；顯然，這個程序要一眼看出其功能是困難的。實際上，這個反映輾轉相除計算方法程序經(jīng)過程序變換，形式上已發(fā)生了很大變化。這兩個例子進一步引發(fā)我們的一些思考：如何確保算法和程序的正確性？既然求解同一個問題可以有不同的方法，不同的算法，不同的程序，那么，怎么來判斷算法和程序的好壞呢？程序變換是否改變算法呢？上面兩個例子初步表明算法、程序與數(shù)學之間存在著密切的聯(lián)系。要解決上面的問題，沒有數(shù)學和計算科學理論的支持恐怕不行。多年來大學計算機科學本科教學的實踐已反復證明，實際情況正是如此。在計算機科學研究中，事實上存在一條規(guī)律：一個問,.,25,題，當它的描述及其求解方法或求解過程可以用構造性數(shù)學描述，而且該問題所涉及的論域為有窮，或雖為無窮但存在有窮表示時，那么，這個問題一定能用計算機來求解；反過來，凡是能用計算機求解的問題，也一定能對該問題的求解過程數(shù)學化，而且這種數(shù)學化是構造性的。當一個問題的求解獲得了計算方法和算法時，并不等于萬事大吉了。在許多情況下，找到求解一個問題的算法只是走完了第一步。至于現(xiàn)實是否可以計算，則取決于算法的存在性和計算的復雜性，即取決于該問題是否存在求解算法，算法所需要的時間和空間在數(shù)量級上能否被接受。要注意的是，有的問題雖然存在求解問題的計算方法，但是，不存在算法。原因有兩種可能：一是計算方法可能不是構造性的；二是雖為構造性的，但計算方法不能保證計算過程在任何初值的情況下都能結束。,.,26,算法復雜性什么是算法的復雜性呢？使用計算機計算各種問題，需要存儲空間、計算時間。不同的算法計算所需要的時間和空間是不同的。所謂算法的復雜性就是對算法計算所需要的時間和空間的一種度量。由于不同的計算機千差萬別，運算速度和字長可以相差很大，因此，不可能用算法在某一臺計算機上計算所需要的實際的時間和存儲單元（空間）去衡量這個算法的復雜性。那么，怎樣才能準確刻劃算法的計算復雜性呢？引入漸近增長率的概念來刻劃算法的計算復雜性。漸進增長率用復雜性度量函數(shù)表示，該函數(shù)表示了算法隨問題規(guī)模大小變化引起的算法中抽象的基本運算執(zhí)行的次數(shù)或存儲空間量的變化規(guī)律。如某個計算問題當輸入規(guī)模分別為1，2，3，n時，經(jīng)分析算法中抽象的基本運算次數(shù)分別為1，4，9，n2，那么，就可以用函數(shù)n2來刻劃這個算法的時間復雜性，并稱這個算法的時間復雜性度量為(n2)級。,.,27,有了復雜性度量函數(shù)，一旦選定具體計算機，可以根據(jù)這臺計算機對某個n值的實際運算速度比較準確地估算出對其他的n值完成計算所需要的時間。于是，對各種算法的復雜性進行分析的關鍵是要設法去找出這樣的函數(shù)，它涉及到與數(shù)學密切相關的算法的設計原理、思想和方法，算法分析是具有智力挑戰(zhàn)性的研究課題。證比求易算法（本書上的三個中國人算法）在算法計算復雜性的研究中，一個算法如果存在圖靈機可計算的多項式時間計算復雜性算法，就將這個算法歸入P類，如果存在非確定性圖靈機可計算的多項式時間計算復雜性算法，就將其歸入NP類。對大多數(shù)實際問題來說，找到一個解可能很難，檢驗一個解常常比較容易，所以都屬于NP類?，F(xiàn)在，計算科學研究中一個懸而未決的重要問題是：PNP？。,.,28,PNP？這個問題不僅具有理論上的價值，而且具有重大實用價值。因為到目前為止，已經(jīng)發(fā)現(xiàn)了一批可計算但有相當難度的問題是屬于NP類的，并且常通過證明一個問題與已知屬于NP類中的某個問題（如可滿足性問題，簡稱SAT問題）等價將其歸入NP類。不過，該問題是否屬于P類，即是否能找到多項式時間計算復雜性算法求解該問題，或證明該問題不存在多項式時間計算復雜性算法求解，至今尚未解決?，F(xiàn)在，很多人都猜測秋碧貞楠的看法是對的：求解一個問題總是比驗證一個問題的解要難，用公式表示也就是PNP。70年代初，庫克（S.A.Cook）和卡爾普（R.M.Karp）指出，NP類中有一小類問題具有以下性質：迄今為止，這些問題多數(shù)經(jīng)過深思熟慮還沒有人找到多項式時間計算復雜性算法。但是，一旦其中的一個問題找到了多項式時間計算復雜性算法，這個類中的其它問題也能找到多項式時間計算復雜性算法，那么就可以斷定PNP。換句話說，如果確屬這個,.,29,類中的某個問題被證明不存在多項式時間計算復雜性算法，那么，就等于證明了PNP。通常，將這類問題稱為NP完全性問題。正是由于這些原因，算法被認為是計算科學的核心問題之一。定義1（算法）給定問題和設備，一個算法是用該設備可理解的語言表示的，解決這個問題的一種方法的精確刻劃。特別，算法具有下列特征屬性：(1)算法應用于一個具體的輸入集合或問題描述將在有窮步動作序列之后得到結果；(2)該序列有一個唯一的初始動作；(3)該序列中的每一個動作有一個唯一的后繼動作；(4)該序列終止時或者得到這個問題的解，或者因該問題不可解而獲得不可解說明。,.,30,定義1是一種百科全書式的定義，在專業(yè)上似乎不夠嚴謹，而且也不適應于不確定性算法和分布式、并行算法。Knuth的算法定義定義2（Knuth算法定義）一個算法，就是一個有窮規(guī)則的集合，其中之規(guī)則確定了一個解決某一特定類型問題的運算序列。此外，算法的規(guī)則序列須滿足如下五個重要條件（特性）：(1)有窮性。算法必須總是在執(zhí)行有窮步之后結束；(2)確定性。算法的每一個步驟必須是確切地定義的；(3)輸入。算法有零個或多個輸入；(4)輸出。算法有一個或多個輸出，即與輸入有某個特定關系的量；(5)能行性。算法中有待執(zhí)行的運算和操作必須是相當基本的，即是說，它們原則上都是能夠精確地進行的，而且用筆和紙做有窮次就可以完成。,.,31,有窮性和能行性是算法最重要的兩個特征。對有些問題來說，如果我們給出了一個類似于算法的有窮運算序列，而它對某些輸入可能不停機，那么，我們就稱這樣的運算序列為一個過程。算法和過程都滿足能行性和確定性，唯一的本質區(qū)別是算法的執(zhí)行必須終止，而過程則不然，它可以永不停止。需要指出的是，高級程序設計語言中也有過程的概念，但與這里所講的過程不同，那里實際上指的是一種子程序。1960年代，克努特把計算機科學定義為是研究算法的學問。不過，由于1980年代計算機科學中并行與分布式算法的發(fā)展與計算機體系結構密切相關，以及學科研究中發(fā)展多種不同層面計算模型的需要，包括發(fā)展非圖靈馮諾依曼型計算模型，使許多人認識到研究計算模型與體系結構具有與研究算法同等的重要性，從而使今天學術界對計算科學下的定義變得比過去更為準確。（見第二章）,.,32,一般地說，對任何一個問題，如果有了解決該問題的算法，就可以編制相應的程序。所謂程序，是一種事先編制好了具有特殊功能的指令序列。其中，指令既可以是機器指令，匯編語言指令，也可以是高級語言的語句命令，甚至還可以是用自然語言描述的運算、操作命令。當然，用自然語言編寫程序是計算機科學進入非常高級的階段的標志之一，有賴于自然語言理解取得重大突破，目前看來還是一個十分遙遠的設想。程序這一概念的出現(xiàn)，得益于人類長期的生活實踐，程序設計也不神秘。但是，程序設計是一種高智力的活動，不同的人對同一事物的處理可以設計出完全不同的程序。我們每一個人的生活經(jīng)歷已經(jīng)告訴自己，知識和閱歷（經(jīng)驗）是處事（設計程序）的基礎。正因為如此，在計算機發(fā)展的早期，程序設計被認為是一個與個人經(jīng)歷、思想和技藝相聯(lián)系的一種技藝和技巧。后來，軟件開發(fā)規(guī)模的擴大和開發(fā)方式,.,33,的變化，程序設計才開始被當成一門科學來對待。既然程序如此重要，又為人類經(jīng)常使用，就有必要對程序及其運行的規(guī)律進行深入的研究。于是，對程序各種性質如程序的結構、程序的正確性、程序的運行效率等的研究產(chǎn)生了計算機科學十分重要的一個方向程序理論。有一種程序的定義，用公式給出：程序數(shù)據(jù)結構算法；定義初看起來有新意，它從程序的特征入手，高度抽象和概括。然而，僅有學術上的輔助參考價值，不能作為科學的定義。因為，按照定義，一旦數(shù)據(jù)結構和算法的定義被確定下來，程序的概念應該被隨之確定，而實際上，程序的概念比數(shù)據(jù)結構加算法的涵義更廣。考慮到我們前面給出的算法定義都明確要求滿足終止性的屬性，而程序可以不停機，甚至采用非常高級的程序設計語言設計的程序可以沒有任何,.,34,數(shù)據(jù)結構，有的程序中看不到算法（如Prolog程序中一些推理計算的過程）。所以，我們還是只取前一種程序的定義更合適一些。2.6高級語言與程序設計技術和方法所謂高級程序設計語言（簡稱高級語言）是指用于描述計算機程序的類自然語言。這種語言只是自然語言的一個很小的子集，在語法結構上比較簡單而且規(guī)范，在語義上較少二義性，能夠以比較準確、易讀的形式描述各種計算機程序。例如，人們常見的Fortran語言、Pascal語言、C語言，LISP語言，Ada語言，Prolog語言，等等。高級程序設計語言是程序設計發(fā)展的產(chǎn)物。1950年代:Fortran語言、Basic、Algol；1960年代：PL/1、APL、COBOL、SNOBOL、Algol-68、Pascal、SIMULA、LISP、C、1970年代:Prolog、Smalltalk、Ada、XYZ、Beta、,.,35,隨著計算機應用領域的不斷拓展，針對各個應用領域的不同特點和程序設計的經(jīng)驗，科研人員設計和發(fā)展了一批高級程序設計語言。對于一個已經(jīng)有了計算該問題算法的待解問題，不同的人根據(jù)同一算法可能編出完全不同然而都是正確的程序。這種不同除了程序的書寫形式有區(qū)別外，重要的是這些程序的結構反映在程序設計的構思和易讀性方面有差別，程序運行的效率（主要指速度）不一樣，有時相去甚遠。這是為什么呢？程序設計語言是一門科學對程序結構本質的深入研究促進了對程序質量的認識開發(fā)程序的效率和質量取決于程序設計方法和技術多年的研究發(fā)展了許多程序設計方法和技術。如自頂向下逐步求精的程序設計方法、自底向上的程序設計方法、程,.,36,序推導的設計方法、程序變換的設計方法、函數(shù)式程序設計技術、邏輯程序設計技術、面向對象的程序設計技術、程序驗證技術、約束程序設計技術、并發(fā)程序設計技術等。例如，對于許多問題的計算，可以用類似于計算函數(shù)的方法來進行，也可以用表（一種數(shù)據(jù)結構）處理的方法來進行，甚至還可以用邏輯公式演繹推導的方法進行，在實現(xiàn)技術上，既可以用遞歸技術計算，也可以用迭代技術或其它技術進行計算。作為一門科學，高級語言和程序設計確實對學科的發(fā)展產(chǎn)生了巨大的影響。程序設計方法和技術在各個時期的發(fā)展不僅直接導致了一大批風格各異的高級語言的誕生，而且許多新思想、新概念、新方法和新技術不僅在語言中得到體現(xiàn)，同時滲透到了計算機科學的各個方向，從理論、硬件、軟件到應用等多方面深刻影響了學科的發(fā)展。對高級語言和程序設計的掌握是計算機科學專業(yè)的基本功之一。,.,37,2.7系統(tǒng)軟件與應用軟件從計算機（硬件裸機）到計算機系統(tǒng)從計算機系統(tǒng)到計算機體系結構軟件是一個發(fā)展的概念，早期軟件和程序幾乎是同義詞。后來，軟件的概念在程序的基礎上得到了延伸。1983年，IEEE對軟件給出了一個較為新穎的定義，指出：軟件是計算機程序、方法、規(guī)范及其相應的文稿以及在計算機上運行時所必須的數(shù)據(jù)。在軟件的發(fā)展過程中，人們將各種軟件分成兩大類。一類稱為系統(tǒng)軟件，一類叫做應用軟件。所謂系統(tǒng)軟件是指那些參與構成計算機系統(tǒng)，提供給計算機用戶使用，用于擴展計算機硬件功能、維護整個計算機硬件和軟件系統(tǒng)，平滑用戶思維方式、操作習慣與計算機硬件設備之間溝坎的軟件。應用軟件是相對于系統(tǒng)軟件而言的，它是對用戶在計算機系統(tǒng)上針對各種具體的應用問題開發(fā)的一類專用程序或軟件的,.,38,總稱。一般地說，操作系統(tǒng)、匯編程序、編譯系統(tǒng)、數(shù)據(jù)庫管理系統(tǒng)、軟硬件故障診斷程序、子程序庫、各種軟件開發(fā)工具和軟件包及其說明文件等屬于系統(tǒng)軟件，其它由用戶開發(fā)的各種形形色色的應用程序及其說明文件或應用軟件系統(tǒng)被稱為應用軟件。操作系統(tǒng)-一種系統(tǒng)軟件，它負責管理計算機系統(tǒng)中的各種資源并控制各類程序的運行。它通過接受來自用戶的操作命令，按照用戶的要求對計算機的工作進行控制。計算機配上操作系統(tǒng)之后，能夠提高效率，便于使用。系統(tǒng)軟件和應用軟件迄今并沒有嚴格的定義。2.8計算機組織與體系結構從計算機系統(tǒng)的逐個設計、制造到計算機的系列化和軟件的兼容性,.,39,IBM360系統(tǒng)標志著計算機體系結構（Architecture）研究的開端（1964年）。計算機體系結構是使用機器語言編寫程序的用戶可以看到的一個機器的抽象結構，而對這一結構實現(xiàn)的硬件組成屬于計算機組成原理研究的范疇。隨著大規(guī)模和超大規(guī)模集成電路（LSI/VLSI）技術的成熟，一方面器件速度和可靠性在不斷提高，目前已逼近極限，另一方面器件的體積和價格在持續(xù)下降，這極大地增強了計算機的性能。然而，高質量的器件不是產(chǎn)生高性能計算機的唯一因素。雖然，今日大多數(shù)計算機都是圖靈馮諾依曼型存儲程序式電子數(shù)字計算機，但人們早已認識到計算機不僅僅是一個硬件組織的問題。一個現(xiàn)代的計算機系統(tǒng)一般被認為是由存儲器、處理器、功能部件、互聯(lián)網(wǎng)絡、匯編程序、編譯程序、操作系統(tǒng)、外部設備、通信通道等內容組合而成的。,.,40,早期計算機系統(tǒng)研究與開發(fā)的兩個基本特點：（1）硬件和軟件的研究與開發(fā)基本上是獨立進行的；（2）硬件的研究與開發(fā)更多的是從計算機組成原理上去關心各部件中分離元器件及其相互之間的聯(lián)接關系，關心各部件的內部構造和外部特性；集成電路的發(fā)展改變了專業(yè)人員的認識。計算機CPU的速度和存儲器的容量成倍增長，各種多功能部件不斷引入，如何設計和配置計算機系統(tǒng)使其具有更高的性能價格比，適應不同用戶的要求，成為亟待解決的問題。集成電路的發(fā)展也使許多專業(yè)人員可以不再關心各部件的內部細節(jié)，而只須考慮如何以一種統(tǒng)一的觀點從硬件器件和一些軟件系統(tǒng)出發(fā)，通過組合配置，設計功能更強、性能價格比更高、更可靠的計算機系統(tǒng)。于是，計算機體系結構應運而生。,.,41,典型的、有助于常人理解計算機體系結構的方向是所謂的網(wǎng)絡計算機系統(tǒng)。用戶面對網(wǎng)絡計算機系統(tǒng)進行開發(fā)是十分困難的，因為，他不可能熟悉網(wǎng)上每一種通信資源）的配置情況，而且也不了解每一種通信資源的基本操作方法，更不可能考慮通信出錯的情況以及如何糾錯。顯然，對于用戶來說，需要有一種能夠屏蔽計算機硬件系統(tǒng)技術細節(jié)，僅對用戶提供功能透明的系統(tǒng)層，使用戶看到的和實際使用的是一個與使用者思想方式、使用習慣比較接近，無須具體關心網(wǎng)絡計算機通信時一些十分繁瑣的技術細節(jié)的分布式計算機系統(tǒng)。硬件的互聯(lián)結構和軟件結構及相互關系形成的計算機系統(tǒng)的總體結構，支持這種結構的基本算法，還有以總體結構為基礎的面向用戶的程序設計語言等內容構成了計算機體系結構的技術范疇。,.,42,29并行計算機、通道與并行計算單CPU計算機多功能部件多寄存器計算機流水線向量計算機陣列式計算機多處理器并行計算機多處理機并行計算機多計算機網(wǎng)絡并行計算機系統(tǒng)并行處理要求在計算機上并行地運行許多程序。根據(jù)使用的計算機系統(tǒng)的不同，我們可以在四個程序的級別上提出并行處理的問題：作業(yè)或程序級并行任務或過程級并行指令級并行指令內部級并行不同的并行處理思想和技術，產(chǎn)生了不同的并行計算機系統(tǒng)。從使用方便的角度考慮，用戶更希望看到的是系統(tǒng)提供作業(yè)或程序級并行，這樣用戶可以不必考慮實現(xiàn)并行的細,.,43,節(jié)。而從實際計算提高效率的角度考慮，用戶更希望系統(tǒng)已經(jīng)實現(xiàn)了指令級并行或指令內部級并行。那么，面對眾多的并行計算機系統(tǒng)，我們應該怎么來認識和區(qū)別它們的系統(tǒng)結構呢？注意到了程序在計算機上的執(zhí)行實際上是指令在數(shù)據(jù)集上的一個操作序列這樣一個基本的事實，M.J.Flynn在1966年提出了一種著名的、也是現(xiàn)今比較常用的系統(tǒng)結構分類方法。他將計算機系統(tǒng)的系統(tǒng)結構分為四類，分別是：單指令流單數(shù)據(jù)流計算機（SISD）、單指令流多數(shù)據(jù)流計算機（SIMD）、多指令流單數(shù)據(jù)流計算機（MISD）、多指令流多數(shù)據(jù)流計算機（MIMD）。由多機系統(tǒng)技術的擴展及網(wǎng)絡互連與通信技術的引入，發(fā)展了分布式網(wǎng)絡計算機系統(tǒng)，提出了分布式計算機體系結構、分布式算法與分布式并行處理的概念等。,.,44,并行計算機系統(tǒng)的出現(xiàn)，帶來了信息并行化處理的概念。并行處理是信息處理的一種有效形式，它著重于發(fā)掘計算過程中的并發(fā)事件。并發(fā)性包含宏觀上的并行性，包含同時性以及微觀上的流水線處理。并行事件可在同一時間間隔內在多個資源（如多個處理器）里發(fā)生；同時事件可在同一時刻上發(fā)生，流水線事件可在部分重疊的時間內于一個（或多個）資源里出現(xiàn)。并發(fā)通常是指宏觀上一個資源里并行發(fā)生了兩個或兩個以上的事件，但在微觀上是順序發(fā)生的，而并行通常是指多個資源里微觀上同時發(fā)生了兩個或兩個以上事件。顯然，一組事件是并行的也是并發(fā)的，但一組事件是并發(fā)的卻不一定是并行的。通道-通道是數(shù)據(jù)或信息傳送的通路利用并行計算機系統(tǒng)進行數(shù)據(jù)與信息的并行處理稱為并行計算。從處理對象的角度劃分，并行計算分為數(shù)值并行計算和非數(shù)值并行計算。與順序計算類似，并行計算也,.,45,分成幾個步驟：研究并行計算方法，研究并行算法，設計并行程序，調試與運行，分析結果。由于許多問題的計算已經(jīng)有了計算方法，而這些計算方法中隱含了大量的并行性，稍作變化就可支持并行算法和并行程序設計，而且，由于各種并行計算機的系統(tǒng)結構不同，各處理器和各多功能部件之間在體現(xiàn)算法時的相互作用不同，算法不能通用。因此，除了并行計算機體系結構的研究外，當前和今后相當長的一個時期內并行處理的一個工作重點將是研究各種并行與分布式計算機系統(tǒng)上的并行算法或分布式算法。2.10計算機網(wǎng)絡與通信隨著計算科學及其應用的高速發(fā)展，用戶對軟硬件和信息資源共享的需求和一大類問題本身具有地域上分布的特點，促進了計算機網(wǎng)絡的發(fā)展。,.,46,所謂計算機網(wǎng)絡是使用通信設備和通信線路將一組地理上分布的相同（稱為同質）或不同（稱為異質）的計算機、終端及其附屬設備按照某種方式互聯(lián)起來得到的一個計算機硬件系統(tǒng)，也叫網(wǎng)絡計算機。在這種計算機硬件系統(tǒng)的基礎上，通過開發(fā)能協(xié)調各臺計算機系統(tǒng)工作的通信系統(tǒng)或更進一步的網(wǎng)絡操作系統(tǒng)，就能使一組計算機實現(xiàn)軟硬件資源共享、協(xié)同計算，合作求解一個問題。由這種通信系統(tǒng)或網(wǎng)絡操作系統(tǒng)連同網(wǎng)絡計算機一起，就形成了網(wǎng)絡計算機系統(tǒng)。按照數(shù)據(jù)傳輸范圍和實現(xiàn)技術的不同，計算機網(wǎng)絡存在局域計算機網(wǎng)絡和廣域計算機網(wǎng)絡之分。局域計算機網(wǎng)絡是一個數(shù)據(jù)通信系統(tǒng)，其傳輸范圍在中等地理區(qū)域，使用中等或高速數(shù)據(jù)傳輸速率，使用專用數(shù)據(jù)通信線或總線進行通信，可聯(lián)接大量獨立設備，在物理通信通道上互相