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

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