計算學科中的基本概念

1、 b b 1 0 1 0 0 0 1 0 b b b 讀 寫 頭 控 制 器 狀 態(tài) ql b b 1 0 1 0 0 0 1 0 b b b 讀 寫 頭 控 制 器 狀 態(tài) ql 計算結果是10100011，即對給定的數(shù)加1。 b b 1 0 1 0 0 0 1 0 b b b 讀 寫 頭 控 制 器 狀 態(tài) ql 以上命令計算的是這樣一個函數(shù)：S(x)x1。當沒有輸入時，即初始狀態(tài)所指的方格為空格（b）時，不改變空格符，讀寫頭不動并停機。 o 第一第一，把圖靈機看作識別器，即判斷帶子上最，把圖靈機看作識別器，即判斷帶子上最初的內(nèi)容能否被圖靈機所接受。假定圖靈機從初的內(nèi)容能否被圖靈機所接受。

2、假定圖靈機從左向右掃描完帶子上的內(nèi)容后停機則為接受，左向右掃描完帶子上的內(nèi)容后停機則為接受，否則為不接受。否則為不接受。o 例例2 一臺圖靈機可以設計成識別下面的序列：一臺圖靈機可以設計成識別下面的序列： 1000110, 10011101, 010101011。o 第二，第二，把圖靈機看作生成器，對給定的輸入集把圖靈機看作生成器，對給定的輸入集合，考察輸出集合，并研究輸入輸出集合性質(zhì)合，考察輸出集合，并研究輸入輸出集合性質(zhì)之間的關系，這就研究了圖靈機的生成能力。之間的關系，這就研究了圖靈機的生成能力。o 例例3 設一臺圖靈機的輸入集合為設一臺圖靈機的輸入集合為In1n0nnN，可設計一臺圖靈

3、機，對給定的，可設計一臺圖靈機，對給定的輸入集合輸入集合In，得到輸出集合，得到輸出集合Out0n1nnN。其中，。其中，N是全體自然數(shù)的集合。是全體自然數(shù)的集合。o 第三第三，把圖靈機看作計算器，相當于一個函數(shù)。，把圖靈機看作計算器，相當于一個函數(shù)。圖靈機的輸入是函數(shù)的自變量的值，圖靈機的圖靈機的輸入是函數(shù)的自變量的值，圖靈機的輸出是函數(shù)的值。輸出是函數(shù)的值。 例例4 圖靈機可以計算下列函數(shù)：圖靈機可以計算下列函數(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)。o 第一和第二個函數(shù)讀者不難從圖

4、靈機的定義出第一和第二個函數(shù)讀者不難從圖靈機的定義出發(fā)感悟到它們是圖靈機可以計算的函數(shù)，而第發(fā)感悟到它們是圖靈機可以計算的函數(shù)，而第三個函數(shù)就比較復雜，一時難于判斷。順便提三個函數(shù)就比較復雜，一時難于判斷。順便提一下，第三個函數(shù)叫做一下，第三個函數(shù)叫做阿克曼函數(shù)阿克曼函數(shù)，它是阿克，它是阿克曼（曼（W.Ackermann）在研究原始遞歸函數(shù)和）在研究原始遞歸函數(shù)和遞歸函數(shù)的關系時給出的。這個函數(shù)在計算理遞歸函數(shù)的關系時給出的。這個函數(shù)在計算理論中具有重要價值。論中具有重要價值。o 事實上，圖靈機還可以計算形式上比第三個函事實上，圖靈機還可以計算形式上比第三個函數(shù)更復雜的函數(shù)。數(shù)更復雜的函數(shù)。

5、nn-110-1-m+1-m其中，其中，10稱為十進制的基數(shù)稱為十進制的基數(shù),ki0,1,2,3,4,5,6,7,8 9，m，n為正整數(shù)。小數(shù)點的位置不言自明。為正整數(shù)。小數(shù)點的位置不言自明。 Sknkn-1 k0. k-m kn2nkn-12n-1k020k-m2-m -m ki2i in 其中，其中，2稱為二進制的基數(shù)，稱為二進制的基數(shù)，ki0,1,m,n為正整數(shù)。為正整數(shù)。 進一步，讀者可從十進制數(shù)和二進制數(shù)的一般表示進一步，讀者可從十進制數(shù)和二進制數(shù)的一般表示公式得到啟發(fā)，將這種表示推廣到更一般的任意進制，公式得到啟發(fā)，將這種表示推廣到更一般的任意進制，不同之處只是基數(shù)不一樣。不同之處

6、只是基數(shù)不一樣。 二進制的運算規(guī)則比十進制的運算規(guī)則簡二進制的運算規(guī)則比十進制的運算規(guī)則簡單得多。單得多。只要建立兩種進制的數(shù)據(jù)之間的轉換只要建立兩種進制的數(shù)據(jù)之間的轉換方法，那么，二進制將具有更多的優(yōu)勢。方法，那么，二進制將具有更多的優(yōu)勢。計算計算機的理論基礎是邏輯和代數(shù)。當二進制與同樣機的理論基礎是邏輯和代數(shù)。當二進制與同樣只使用只使用“真真”和和“假假”兩個值的邏輯代數(shù)建立兩個值的邏輯代數(shù)建立了聯(lián)系后，這就為計算機的邏輯設計提供了便了聯(lián)系后，這就為計算機的邏輯設計提供了便利的工具。利的工具。 圖靈機的出現(xiàn)為現(xiàn)代計算機的發(fā)明提供了圖靈機的出現(xiàn)為現(xiàn)代計算機的發(fā)明提供了重要的思想。圖靈機的帶子

7、可以看成是計算機重要的思想。圖靈機的帶子可以看成是計算機的存儲設備，數(shù)據(jù)可以存儲在上面，也可以根的存儲設備，數(shù)據(jù)可以存儲在上面，也可以根據(jù)需要擦去。圖靈機的命令相當于一組事先設據(jù)需要擦去。圖靈機的命令相當于一組事先設計、存儲好了的程序，它們在控制器安排下，計、存儲好了的程序，它們在控制器安排下，決定讀寫頭的每一步操作。這樣一種數(shù)學機器，決定讀寫頭的每一步操作。這樣一種數(shù)學機器，如果不考慮它的實用性，就思想和原理而言，如果不考慮它的實用性，就思想和原理而言，確實包含了確實包含了存儲程序存儲程序的重要思想。的重要思想。 存 儲 器 運 算 器 控 制 器 輸入/輸出設備 命令寄存器 “與與”、“或

8、或”、“非非”三種門電路示意圖三種門電路示意圖 P P P A B C A B C A （a） （b） （c） o 用計算機求解一個問題，必須事先編制好程序。程用計算機求解一個問題，必須事先編制好程序。程序是由指令組成的。每一臺計算機都設計規(guī)定了一序是由指令組成的。每一臺計算機都設計規(guī)定了一組指令集合，稱為機器指令系統(tǒng)。組指令集合，稱為機器指令系統(tǒng)。o 機器指令的格式一般分為兩部分，如下所示：機器指令的格式一般分為兩部分，如下所示： 指令格式：指令格式： 操作碼操作碼 地址部分地址部分 其中，操作碼指出運算的種類，如，其中，操作碼指出運算的種類，如，跳轉等，地址部分用來指示參與運算的數(shù)據(jù)保，跳

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

10、其指令系統(tǒng)是不同的。不同的。o 指令系統(tǒng)的日漸增大雖然給用戶的程序設計指令系統(tǒng)的日漸增大雖然給用戶的程序設計帶來了方便，但也帶來了硬件設計復雜性的帶來了方便，但也帶來了硬件設計復雜性的增加和因譯碼、存儲、尋址等開銷的增大而增加和因譯碼、存儲、尋址等開銷的增大而使運算速度下降。研究發(fā)現(xiàn)，使運算速度下降。研究發(fā)現(xiàn)，指令系統(tǒng)存在指令系統(tǒng)存在著改進的必要和可能。著改進的必要和可能。 RISCo 思路主要是通過減少指令總數(shù)和簡化指令的思路主要是通過減少指令總數(shù)和簡化指令的功能來降低硬件設計的復雜度，從而提高指功能來降低硬件設計的復雜度，從而提高指令的執(zhí)行速度。令的執(zhí)行速度。o 優(yōu)點優(yōu)點:與與CISC技術

11、相比技術相比n 簡化了指令系統(tǒng)，適合超大規(guī)模集成電路簡化了指令系統(tǒng)，適合超大規(guī)模集成電路的實現(xiàn)；的實現(xiàn)；n 提高了機器執(zhí)行的速度和效率；提高了機器執(zhí)行的速度和效率；n 降低了設計成本，提高了系統(tǒng)的可靠性；降低了設計成本，提高了系統(tǒng)的可靠性；n 提供了直接支持高級語言的能力，簡化了提供了直接支持高級語言的能力，簡化了編譯程序的設計。編譯程序的設計。機器指令o 機器指令系統(tǒng)每臺數(shù)字電子計算機在設計中，都規(guī)定了一組指令。o 機器語言用機器指令形式編寫的程序。o 在裸機級，計算機語言關于算法的描述采用的是實際機器的機器指令，它的符號集是0，1，n 支撐實際機器的理論是圖靈機等計算模型；n 在圖靈機等計

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

13、制、八進制和十進制數(shù)字序列。大據(jù)的二進制、八進制和十進制數(shù)字序列。大多數(shù)情況下，一條匯編指令對應一條機器指多數(shù)情況下，一條匯編指令對應一條機器指令，少數(shù)對應幾條機器指令。例如，下面是令，少數(shù)對應幾條機器指令。例如，下面是幾條匯編指令的操作符，右邊中文是名稱。幾條匯編指令的操作符，右邊中文是名稱。 addadd 加法加法 idividiv 有符號除法有符號除法 mulmul 無符無符號乘法號乘法 negneg 求補求補 xchgxchg 交換交換 testtest 邏輯比較邏輯比較 jmpjmp 無條件轉移無條件轉移匯編語言o 當然，匯編語言在可讀性和編寫程序時仍然當然，匯編語言在可讀性和編寫程

14、序時仍然是不能令人滿意的，這導致進一步發(fā)展了高是不能令人滿意的，這導致進一步發(fā)展了高級程序設計語言。不過，由于高級語言在使級程序設計語言。不過，由于高級語言在使用時通常還是要通過編譯程序逐步將高級語用時通常還是要通過編譯程序逐步將高級語言寫的程序翻譯成機器指令的程序，而這種言寫的程序翻譯成機器指令的程序，而這種翻譯的結果往往不如機器指令或匯編語言寫翻譯的結果往往不如機器指令或匯編語言寫的程序效率高，所以，直到今天，不少工程的程序效率高，所以，直到今天，不少工程師在系統(tǒng)軟件的開發(fā)中還在使用機器指令和師在系統(tǒng)軟件的開發(fā)中還在使用機器指令和匯編語言。匯編語言。 求解一個給定的問題，不同的人常編寫求解

15、一個給定的問題，不同的人常編寫出不同的然而都是正確的程序，這是為什么出不同的然而都是正確的程序，這是為什么呢？呢？ 這里存在兩個層面的問題，一個是與計這里存在兩個層面的問題，一個是與計算方法密切相關的算法問題，另一個是程序算方法密切相關的算法問題，另一個是程序設計的技術問題。設計的技術問題。o 不難想象，不同的求解方法將產(chǎn)生出不同的不難想象，不同的求解方法將產(chǎn)生出不同的算法，不同的算法將使我們設計出不同的程算法，不同的算法將使我們設計出不同的程序，而決定這個程序功能的本質(zhì)是計算方法序，而決定這個程序功能的本質(zhì)是計算方法及其算法。一般地說，對不同計算方法過程及其算法。一般地說，對不同計算方法過程

16、的抽象描述就產(chǎn)生了相應的不同算法，但同的抽象描述就產(chǎn)生了相應的不同算法，但同一算法由不同的人來寫程序則完全可能設計一算法由不同的人來寫程序則完全可能設計出差別很大的程序。出差別很大的程序。o 憑直覺想象給出的算法往往不是最好的算法。憑直覺想象給出的算法往往不是最好的算法。 算法算法被認為是計算科學的核心問題之一。被認為是計算科學的核心問題之一。 o 定風定風1 1：給定問題和設備，一個算法是用該設備可：給定問題和設備，一個算法是用該設備可理解的語言表示的，解決這個問題的一種方法的精理解的語言表示的，解決這個問題的一種方法的精確刻劃。特別，算法具有下列特征屬性：確刻劃。特別，算法具有下列特征屬性

17、： (1) (1) 算法應用于一個具體的輸入集合或問題描述算法應用于一個具體的輸入集合或問題描述將在有窮步動作序列之后得到結果；將在有窮步動作序列之后得到結果； (2) (2) 該序列有一個唯一的初始動作；該序列有一個唯一的初始動作； (3) (3) 該序列中的每一個動作有一個唯一的后繼動該序列中的每一個動作有一個唯一的后繼動作；作； (4) (4) 該序列終止時或者得到這個問題的解，或者該序列終止時或者得到這個問題的解，或者因該問題不可解而獲得不可解說明。因該問題不可解而獲得不可解說明。o 定風定風1 1：給定問題和設備，一個算法是用該設備可：給定問題和設備，一個算法是用該設備可理解的語言表

18、示的，解決這個問題的一種方法的精理解的語言表示的，解決這個問題的一種方法的精確刻劃。特別，算法具有下列特征屬性：確刻劃。特別，算法具有下列特征屬性： (1) (1) 算法應用于一個具體的輸入集合或問題描述算法應用于一個具體的輸入集合或問題描述將在有窮步動作序列之后得到結果；將在有窮步動作序列之后得到結果； (2) (2) 該序列有一個唯一的初始動作；該序列有一個唯一的初始動作； (3) (3) 該序列中的每一個動作有一個唯一的后繼動該序列中的每一個動作有一個唯一的后繼動作；作； (4) (4) 該序列終止時或者得到這個問題的解，或者該序列終止時或者得到這個問題的解，或者因該問題不可解而獲得不可

19、解說明。因該問題不可解而獲得不可解說明。定義定義2（Knuth算法定義）算法定義） 一個算法，就是一個有窮規(guī)則的集合，其中之規(guī)則一個算法，就是一個有窮規(guī)則的集合，其中之規(guī)則確定了一個解決某一特定類型問題的運算序列。此外，確定了一個解決某一特定類型問題的運算序列。此外，算法的規(guī)則序列須滿足如下五個重要條件（特性）：算法的規(guī)則序列須滿足如下五個重要條件（特性）： (1) (1) 有窮性。算法必須總是在執(zhí)行有窮步之后結束；有窮性。算法必須總是在執(zhí)行有窮步之后結束； (2) (2) 確定性。算法的每一個步驟必須是確切地定義確定性。算法的每一個步驟必須是確切地定義的；的； (3) (3) 輸入。算法有零

20、個或多個輸入；輸入。算法有零個或多個輸入； (4) (4) 輸出。算法有一個或多個輸出，即與輸入有某輸出。算法有一個或多個輸出，即與輸入有某個特定關系的量；個特定關系的量； (5) (5) 能行性。算法中有待執(zhí)行的運算和操作必須是能行性。算法中有待執(zhí)行的運算和操作必須是相當基本的，即是說，它們原則上都是能夠精確地進行相當基本的，即是說，它們原則上都是能夠精確地進行的，而且用筆和紙做有窮次就可以完成。的，而且用筆和紙做有窮次就可以完成。nHn1312111 X=1 Y=2 X=X+Y Y=Y+1 Y100 結 束 開 始 Y N 開 始 X=0 I=1 X=X+1/I I=I+1 I=N 結 束

21、 N Y 開 始 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 在梵天塔問題中，需要移動的盤子次數(shù)為在梵天塔問題中，需要移動的盤子次數(shù)為h(n)=2n-1，則該問題的算法時間復雜度表示則該問題的算法時間復雜度表示為為 (2n)；例例4.4的算法時間復雜度表示為的算法時間復雜度表示為 (1)；例例4.5的算法時間復雜度表示為的算法時間復雜度表示為 (n)；例例4.6的的算法時間復雜度表示為算法時間復雜度表示為 (n)

22、等等。等等。 一般而言，對于較復雜的算法，應將它分一般而言，對于較復雜的算法，應將它分成容易估算的幾個部分，然后用成容易估算的幾個部分，然后用 的求解原則的求解原則計算整個算法的時間復雜度，最好不要采用計算整個算法的時間復雜度，最好不要采用指數(shù)級和階乘級的算法，而應盡可能選用多指數(shù)級和階乘級的算法，而應盡可能選用多項式級或線性級等時間復雜度較小的算法。項式級或線性級等時間復雜度較小的算法。另外，還要在算法最好、平均和最壞的情況另外，還要在算法最好、平均和最壞的情況下區(qū)別執(zhí)行效率的不同。下區(qū)別執(zhí)行效率的不同。 在階乘級的算法中，如果問題規(guī)模在階乘級的算法中，如果問題規(guī)模n為為10，則算法時間復雜

23、度為則算法時間復雜度為10?。ǎ。?，628，800）。）。若要檢驗若要檢驗10！種情況，設每種情況需要！種情況，設每種情況需要1毫秒毫秒的計算時間，則整個計算將需的計算時間，則整個計算將需1小時左右。一小時左右。一般來說，如果選用了階乘級的算法，則當問般來說，如果選用了階乘級的算法，則當問題規(guī)模等于或者大于題規(guī)模等于或者大于10時，就要認真考慮算時，就要認真考慮算法的適用性問題。法的適用性問題。 C A B D E F G H I J K L C A B D 一個程序具有一個單一的、不可分的結構，它規(guī)定了某個數(shù)據(jù)結構上的一個算法。瑞士著名計算機科學家尼可萊沃思（Nikiklaus Wirth

24、）在1976年曾提出這樣一個公式： 算法算法+數(shù)據(jù)結構數(shù)據(jù)結構=程序程序 這一公式僅可以作為一種參考，不能作這一公式僅可以作為一種參考，不能作為教學中的定義。為教學中的定義。 由此看來，我們前面提到的算法和數(shù)據(jù)結構是計算機程序的兩個最基本的概念。算法是程序的核心，它在程序編制、軟件開發(fā)，乃至在整個計算機科學中都占據(jù)重要地位。數(shù)據(jù)結構是加工的對象，一個程序要進行計算或處理總是以某些數(shù)據(jù)為對象的，而要設計一個好的程序就需將這些松散的數(shù)據(jù)按某種要求組成一種數(shù)據(jù)結構。然而，隨著計算機科學的發(fā)展，人們現(xiàn)在已經(jīng)意識到程序除了以上兩個主要要素外，還應包括程序的設計方法以及相應的語言工具和計算環(huán)境。 抽象理論

25、設計常用的符號：數(shù)字(09)，大小寫字母(AZ、az)，括號，運算符(+，*，/)等;用高級語言對算法進行的描述；語言的分類方法；各種數(shù)據(jù)類型的抽象實現(xiàn)模型；詞法分析、編譯、解釋和代碼優(yōu)化的方法；詞法分析器、掃描器、編譯器組件和編譯器的自動生成方法形式語言和自動機理論；形式語義學：操作、指稱、公理、代數(shù)、并發(fā)和分布式程序的形式語義特定語言：過程式的COBOL，F(xiàn)ORTURN，ALGOL，Pascal，Ada，C），函數(shù)式的（LISP），數(shù)據(jù)流的（SISAL，VAL），面向?qū)ο蟮模⊿malltalk，C+），邏輯的（Prolog），字符串（SNOBOL），和并發(fā)（Concurrent Pasca

26、l，Modula 2）等語言；詞法分析器和掃描器的產(chǎn)生器（如YACC，LEX），編譯器產(chǎn)生器；語法和語義檢查，成型、調(diào)試和追蹤程序o 對程序結構本質(zhì)的深入研究促進了對程序質(zhì)對程序結構本質(zhì)的深入研究促進了對程序質(zhì)量的認識量的認識o 開發(fā)程序的效率和質(zhì)量取決于程序設計方法開發(fā)程序的效率和質(zhì)量取決于程序設計方法和技術和技術o 多年的研究發(fā)展了許多程序設計方法和技術。多年的研究發(fā)展了許多程序設計方法和技術。如自頂向下逐步求精的程序設計方法、自底如自頂向下逐步求精的程序設計方法、自底向上的程序設計方法、程序推導的設計方法、向上的程序設計方法、程序推導的設計方法、程序變換的設計方法、函數(shù)式程序設計技術、程

27、序變換的設計方法、函數(shù)式程序設計技術、邏輯程序設計技術、面向?qū)ο蟮某绦蛟O計技邏輯程序設計技術、面向?qū)ο蟮某绦蛟O計技術、程序驗證技術、約束程序設計技術、并術、程序驗證技術、約束程序設計技術、并發(fā)程序設計技術等。發(fā)程序設計技術等。o 例如，對于許多問題的計算，可以用類似于例如，對于許多問題的計算，可以用類似于計算函數(shù)的方法來進行，也可以用表（一種計算函數(shù)的方法來進行，也可以用表（一種數(shù)據(jù)結構）處理的方法進行，甚至還可以用數(shù)據(jù)結構）處理的方法進行，甚至還可以用邏輯公式演繹推導的方法進行，在實現(xiàn)技術邏輯公式演繹推導的方法進行，在實現(xiàn)技術上，既可以用遞歸技術計算，也可以用迭代上，既可以用遞歸技術計算，也

28、可以用迭代技術或其它技術進行計算。技術或其它技術進行計算。o 作為一門科學，高級語言和程序設計確實對作為一門科學，高級語言和程序設計確實對學科的發(fā)展產(chǎn)生了巨大的影響。程序設計方學科的發(fā)展產(chǎn)生了巨大的影響。程序設計方法和技術在各個時期的發(fā)展不僅直接導致了法和技術在各個時期的發(fā)展不僅直接導致了一大批風格各異的高級語言的誕生，而且許一大批風格各異的高級語言的誕生，而且許多新思想、新概念、新方法和新技術不僅在多新思想、新概念、新方法和新技術不僅在語言中得到體現(xiàn)，同時滲透到了計算機科學語言中得到體現(xiàn)，同時滲透到了計算機科學的各個方向，從理論、硬件、軟件到應用等的各個方向，從理論、硬件、軟件到應用等多方面

29、深刻影響了學科的發(fā)展。多方面深刻影響了學科的發(fā)展。o 對高級語言和程序設計的掌握是計算機科學對高級語言和程序設計的掌握是計算機科學專業(yè)的基本功之一。專業(yè)的基本功之一。o 從計算機（硬件裸機）到計算機系統(tǒng)從計算機（硬件裸機）到計算機系統(tǒng)o 從計算機系統(tǒng)到計算機體系結構從計算機系統(tǒng)到計算機體系結構o 軟件是一個發(fā)展的概念，早期軟件和程序幾軟件是一個發(fā)展的概念，早期軟件和程序幾乎是同義詞。后來，軟件的概念在程序的基乎是同義詞。后來，軟件的概念在程序的基礎上得到了延伸。礎上得到了延伸。1983年，年，IEEE對軟件給出對軟件給出了一個較為新穎的定義，指出：了一個較為新穎的定義，指出：軟件是計算軟件是計

30、算機程序、方法、規(guī)范及其相應的文稿以及在機程序、方法、規(guī)范及其相應的文稿以及在計算機上運行時所必須的數(shù)據(jù)。計算機上運行時所必須的數(shù)據(jù)。o 系統(tǒng)軟件和應用軟件迄今并沒有嚴格的定系統(tǒng)軟件和應用軟件迄今并沒有嚴格的定義。義。圖像處理圖像處理計計算算機機圖圖形形學學模模式式識識別別圖圖 像像計算幾何計算幾何特特 征征 數(shù)數(shù) 據(jù)據(jù)幾幾 何何 模模 型型CAD/CAM計算機藝術計算機藝術計算機動畫計算機動畫計算機視覺計算機視覺o 隨著計算科學及其應用的高速發(fā)展，用戶對軟硬件和隨著計算科學及其應用的高速發(fā)展，用戶對軟硬件和信息資源共享的需求和一大類問題本身具有地域上分信息資源共享的需求和一大類問題本身具有地

31、域上分布的特點，促進了計算機網(wǎng)絡的發(fā)展。布的特點，促進了計算機網(wǎng)絡的發(fā)展。o 所謂所謂計算機網(wǎng)絡是使用通信設備和通信線路將一組地計算機網(wǎng)絡是使用通信設備和通信線路將一組地理上分布的相同（稱為同質(zhì)）或不同（稱為異質(zhì)）的理上分布的相同（稱為同質(zhì)）或不同（稱為異質(zhì)）的計算機、終端及其附屬設備按照某種方式互聯(lián)起來得計算機、終端及其附屬設備按照某種方式互聯(lián)起來得到的一個計算機硬件系統(tǒng)到的一個計算機硬件系統(tǒng)，也叫網(wǎng)絡計算機。在這種，也叫網(wǎng)絡計算機。在這種計算機硬件系統(tǒng)的基礎上，通過開發(fā)能協(xié)調(diào)各臺計算計算機硬件系統(tǒng)的基礎上，通過開發(fā)能協(xié)調(diào)各臺計算機系統(tǒng)工作的通信系統(tǒng)或更進一步的網(wǎng)絡操作系統(tǒng)，機系統(tǒng)工作的通信

32、系統(tǒng)或更進一步的網(wǎng)絡操作系統(tǒng)，就能使一組計算機實現(xiàn)軟硬件資源共享、協(xié)同計算，就能使一組計算機實現(xiàn)軟硬件資源共享、協(xié)同計算，合作求解一個問題。由這種通信系統(tǒng)或網(wǎng)絡操作系統(tǒng)合作求解一個問題。由這種通信系統(tǒng)或網(wǎng)絡操作系統(tǒng)連同網(wǎng)絡計算機一起，就形成了網(wǎng)絡計算機系統(tǒng)。連同網(wǎng)絡計算機一起，就形成了網(wǎng)絡計算機系統(tǒng)。o 按照數(shù)據(jù)傳輸范圍和實現(xiàn)技術的不同，計算機網(wǎng)按照數(shù)據(jù)傳輸范圍和實現(xiàn)技術的不同，計算機網(wǎng)絡存在絡存在局域計算機網(wǎng)絡局域計算機網(wǎng)絡和和廣域計算機網(wǎng)絡廣域計算機網(wǎng)絡之分。之分。局域計算機網(wǎng)絡是一個數(shù)據(jù)通信系統(tǒng)，其傳輸范局域計算機網(wǎng)絡是一個數(shù)據(jù)通信系統(tǒng)，其傳輸范圍在中等地理區(qū)域，使用中等或高速數(shù)據(jù)傳輸速

33、圍在中等地理區(qū)域，使用中等或高速數(shù)據(jù)傳輸速率，使用專用數(shù)據(jù)通信線或總線進行通信，可聯(lián)率，使用專用數(shù)據(jù)通信線或總線進行通信，可聯(lián)接大量獨立設備，在物理通信通道上互相通信。接大量獨立設備，在物理通信通道上互相通信。o 廣域計算機網(wǎng)絡把不同城市、不同國家中的計算廣域計算機網(wǎng)絡把不同城市、不同國家中的計算機或計算機網(wǎng)絡通過分級互聯(lián)技術聯(lián)接起來，其機或計算機網(wǎng)絡通過分級互聯(lián)技術聯(lián)接起來，其傳輸范圍可達到相當遠的距離。目前最常見的是傳輸范圍可達到相當遠的距離。目前最常見的是使用公用或?qū)Ｓ秒娫捑€通信，主干網(wǎng)和一些局域使用公用或?qū)Ｓ秒娫捑€通信，主干網(wǎng)和一些局域網(wǎng)使用可進行數(shù)字通信的光纖光纜數(shù)據(jù)通信專用網(wǎng)使用可

34、進行數(shù)字通信的光纖光纜數(shù)據(jù)通信專用線。線。o 網(wǎng)絡互聯(lián)的拓撲結構是計算機網(wǎng)絡的重要特性。網(wǎng)絡互聯(lián)的拓撲結構是計算機網(wǎng)絡的重要特性。網(wǎng)絡的拓撲結構是一種抽象的由點和線組成的圖。網(wǎng)絡的拓撲結構是一種抽象的由點和線組成的圖。網(wǎng)絡上的每臺計算機用一個結點表示，機器與機網(wǎng)絡上的每臺計算機用一個結點表示，機器與機器之間的鏈路用線和路徑表示，于是，圖論構成器之間的鏈路用線和路徑表示，于是，圖論構成了網(wǎng)絡計算機體系結構中一些基本算法研究中數(shù)了網(wǎng)絡計算機體系結構中一些基本算法研究中數(shù)學描述的理論基礎。學描述的理論基礎。o 網(wǎng)絡的結構一般有：主從型、環(huán)型、星型、等網(wǎng)絡的結構一般有：主從型、環(huán)型、星型、等o 支持計

35、算機網(wǎng)絡的重要技術是通信，即實現(xiàn)計算支持計算機網(wǎng)絡的重要技術是通信，即實現(xiàn)計算機之間信息傳輸?shù)囊环N技術方式。網(wǎng)絡通信的核機之間信息傳輸?shù)囊环N技術方式。網(wǎng)絡通信的核心內(nèi)容是通信協(xié)議。所謂通信協(xié)議是網(wǎng)絡通信中心內(nèi)容是通信協(xié)議。所謂通信協(xié)議是網(wǎng)絡通信中一組約定的集合，由它確定了經(jīng)由通信網(wǎng)絡傳輸一組約定的集合，由它確定了經(jīng)由通信網(wǎng)絡傳輸?shù)男畔⒒虼鎯υ趫笪暮蛿?shù)據(jù)庫中的信息的格式和的信息或存儲在報文和數(shù)據(jù)庫中的信息的格式和控制方式。研究通信協(xié)議主要是為了在網(wǎng)絡計算控制方式。研究通信協(xié)議主要是為了在網(wǎng)絡計算機系統(tǒng)中實現(xiàn)可靠的、高效的數(shù)據(jù)交換，差錯控機系統(tǒng)中實現(xiàn)可靠的、高效的數(shù)據(jù)交換，差錯控制，信息編碼，線路

36、利用，同步，使通信數(shù)據(jù)具制，信息編碼，線路利用，同步，使通信數(shù)據(jù)具有透明性。有透明性。 網(wǎng)絡上連接著大量的計算機系統(tǒng)，每臺計算機系網(wǎng)絡上連接著大量的計算機系統(tǒng)，每臺計算機系統(tǒng)上可能有多個用戶在同時使用計算機與其它網(wǎng)上用統(tǒng)上可能有多個用戶在同時使用計算機與其它網(wǎng)上用戶進行通信，而網(wǎng)絡通信線路通常設計成公用資源，戶進行通信，而網(wǎng)絡通信線路通常設計成公用資源，這樣，網(wǎng)絡通信為了實現(xiàn)可靠的數(shù)據(jù)交換，因需要做這樣，網(wǎng)絡通信為了實現(xiàn)可靠的數(shù)據(jù)交換，因需要做許多具體的操作運算而變得十分復雜。由于從用戶發(fā)許多具體的操作運算而變得十分復雜。由于從用戶發(fā)送或接收可以識別的符號信息到實際在正確的通信線送或接收可以識

37、別的符號信息到實際在正確的通信線路上傳遞物理信息之間存在轉換、線路利用、分組交路上傳遞物理信息之間存在轉換、線路利用、分組交換、差錯糾正等一系列的操作，為了便于協(xié)議的有效換、差錯糾正等一系列的操作，為了便于協(xié)議的有效實現(xiàn)和對不同的用戶開放，最大限度地實現(xiàn)線路的有實現(xiàn)和對不同的用戶開放，最大限度地實現(xiàn)線路的有效利用，有必要對網(wǎng)絡計算機系統(tǒng)進行通信結構分層。效利用，有必要對網(wǎng)絡計算機系統(tǒng)進行通信結構分層。于是產(chǎn)生了網(wǎng)絡協(xié)議層。每一層包含一組通信功能和于是產(chǎn)生了網(wǎng)絡協(xié)議層。每一層包含一組通信功能和相應的層間通信協(xié)議，支持通信雙方在不同的層間進相應的層間通信協(xié)議，支持通信雙方在不同的層間進行通信，并提

38、供了實現(xiàn)通信的具體思想和方法。行通信，并提供了實現(xiàn)通信的具體思想和方法。 按照按照ISOISO的建議，網(wǎng)絡結構模型是開放系統(tǒng)互連模型的建議，網(wǎng)絡結構模型是開放系統(tǒng)互連模型OSIOSI（七層協(xié)議），包括物理層，數(shù)據(jù)鏈路層，網(wǎng)絡層，七層協(xié)議），包括物理層，數(shù)據(jù)鏈路層，網(wǎng)絡層，傳輸層，會話層，表示層，應用層共七層，產(chǎn)生了七傳輸層，會話層，表示層，應用層共七層，產(chǎn)生了七層協(xié)議。層協(xié)議。 開放系統(tǒng)開放系統(tǒng)A A 開放系統(tǒng)開放系統(tǒng)B B 應用層協(xié)議應用層協(xié)議 應用層應用層 應用層應用層 表示層協(xié)議表示層協(xié)議 表示層表示層 表示層表示層 會話層協(xié)議會話層協(xié)議 會話層會話層 會話層會話層 傳輸層協(xié)議傳輸層協(xié)議 傳輸層傳輸層 傳輸層傳輸層 網(wǎng)絡層協(xié)議網(wǎng)絡層協(xié)議 網(wǎng)絡層網(wǎng)絡層 網(wǎng)絡層網(wǎng)絡層 數(shù)據(jù)鏈路層協(xié)議數(shù)據(jù)鏈路層協(xié)議 數(shù)據(jù)鏈路層數(shù)據(jù)鏈路層數(shù)據(jù)鏈路層數(shù)據(jù)鏈路層 物理層協(xié)議物理層協(xié)議 物理層物理層 物理層物理層 物理傳輸介質(zhì)物理傳輸介質(zhì) o 物理層協(xié)議實現(xiàn)物理上互連系統(tǒng)間位流信息的透物理層協(xié)議實現(xiàn)物理上互連系統(tǒng)間位流信息的透明傳輸，即實現(xiàn)了一位（組）數(shù)據(jù)在兩個通信實明傳輸，即實現(xiàn)了一位（組）數(shù)據(jù)在兩個通信實體之間的可靠傳送通信，它描述了經(jīng)通信介質(zhì)在體之間的可靠傳送通信，它描述了經(jīng)通信介質(zhì)在數(shù)據(jù)鏈路實體之間建立、維護和拆除物理連接。數(shù)據(jù)鏈路實體之間建立、維護和拆除物理連接。o