1、第3章 計算學科中的3個學科形態(tài),3.1 一個關于“學生選課”的例 子,對“學生選課”例子的感性認識,現(xiàn)給出“學生”和“課程”兩個實體,它們的聯(lián)系為： 一個學生可以選修若干門課程 每門課程可以被任一學生所選修 請建立一個信息管理系統(tǒng)，以實現(xiàn)對“學生選課”這一信息的管理。,概念模型,用于信息世界的建模，是客觀世界到信息世界的抽象。 概念模型中的主要概念有：實體、屬性、碼、域、聯(lián)系等。 實體：客觀存在并可相互區(qū)別的事物。 屬性：實體所具有的某一種特性。 碼：能惟一標識實體的屬性集。 域：屬性的取值范圍。 聯(lián)系：指不同實體集之間的聯(lián)系。兩個實體之間的聯(lián)系分為：一對一（1:1）、一對多（1:N）、多對

2、多（N:M）3類。,E-R模型（Entity-Relationship）,1976年，美籍華人陳平山（Peter Pingshan Chen）提出的 用E-R模型來描述客觀世界并建立概念模型的抽象方法。 實體用矩形表示，屬性用橢圓形表示，聯(lián)系用菱形表示，實體間的聯(lián)系有一對一（1:1）、一對多（1:N）和多對多（N:M）3種情況。 要實現(xiàn)對客觀事物的感性認識，必須將客觀世界（在例中客觀世界就是“學生選課”）抽象為信息世界。,圖3.1 學生選課E-R圖,關系模型,概念模型不是機器世界所支持的數(shù)據(jù)模型，而是客觀世界到機器世界的一個中間層次 概念模型還需要轉(zhuǎn)換成機器世界能支持的數(shù)據(jù)模型。 在數(shù)據(jù)庫領域

3、中，數(shù)據(jù)庫管理系統(tǒng)（DBMS）能支持的數(shù)據(jù)模型有：層次、網(wǎng)狀、關系以及面向?qū)ο蟮葦?shù)據(jù)模型。 關系模型支持的是一種二維表結(jié)構的數(shù)據(jù)模型，它由關系數(shù)據(jù)結(jié)構、關系數(shù)據(jù)操作和關系數(shù)據(jù)的完整性約束條件三部分組成。 其中關系就是一張二維表。,概念模型（E-R圖）關系模型,轉(zhuǎn)換： 學生（學號，姓名，年齡，性別）； 課程（課程號，課程名）； 學生選課（學號，課程號，成績） 概念模型是對現(xiàn)實原形的理想化，因此，將概念模型直接轉(zhuǎn)換成關系模型，還不能說完全達到了對“學生選課”這一客觀世界的理性認識，換言之，就是所轉(zhuǎn)換的關系模型有可能還存在問題。,感性認識中存在的問題,在學生（學號，姓名，年齡，性別）關系中增加系名、

4、系主任等屬性時，即學生關系變?yōu)椋▽W號，姓名，年齡，性別，系名，系主任）時，便開始出現(xiàn)以下問題。 插入異常一個系剛成立，系主任已確定，但還未招學生時，則無法將系名和系主任的名字插入到數(shù)據(jù)庫中（學生實體中學號為碼，碼不能缺） 刪除異常當一個系的學生全部畢業(yè)，刪除所有畢業(yè)生時，系名和系主任的名字也就刪除了 冗余太大由于一個學生對應一個系名和系主任的名字，則該系系名和系主任的名字要重復。,關系模式的形式化定義,關系模式（R）是一個四元組，即 R= 其中： （1）U表示關系中所有屬性的集合； （2）D表示屬性集合U中屬性所來自的域； （3）dom是屬性到域的映射； （4）F是屬性集合U上的一組數(shù)據(jù)依賴。

5、,關系模式的形式化定義,由于D、dom與模式設計關系不大，可將關系模式簡單地表示為一個二元組 R= 1NF的定義：作為一張二維表的關系，每一個分量必須是不可再分的數(shù)據(jù)項，滿足這個條件的關系模式就屬于1NF。 2NF的定義：若R1NF，且每一個非主屬性不存在對碼的部分函數(shù)依賴，則 R2NF。在定義中，非主屬性為不屬于碼的那些屬性。 3NF的定義：若R2NF，且每一個非主屬性不存在對碼的傳遞函數(shù)依賴，則 R3NF。,對“例子”問題的理性認識,例子最初是屬于1NF、2NF、3NF，但是當在學生屬性集U中增加系名和系主任后，就出現(xiàn)了這樣的傳遞函數(shù)依賴：學號（碼）系名，系名系主任。因此，它就不屬于3NF

6、了。 不屬于3NF的所有關系模型都會出現(xiàn)插入異常、刪除異常和冗余的問題。 還必須依靠分解算法對模式進行分解，并滿足3NF的要求。 在數(shù)據(jù)依賴理論的指導下，可完成模式的分解任務。 就例子而言，可以再劃分一個關系，即系（系號，系名，系主任名），從而滿足了關系模式規(guī)范化的要求，實現(xiàn)了對例子的理性認識。,從概念模型向滿足規(guī)范化要求的關系模型的轉(zhuǎn)換，其實質(zhì)是認識過程由感性認識（抽象）上升到理性認識（理論）的過程，這個過程包含兩方面的內(nèi)容： 一方面是有關理論的建立； 另一方面是如何在理論的指導下，在具體的設計中，實現(xiàn)對客觀世界的理性認識。 前者是對科學研究而言的，而后者是對工程設計而言的。,“學生選課”系

7、統(tǒng)的工程設計,建立起正確的關系模型后，還要根據(jù)具體的關系數(shù)據(jù)庫管理系統(tǒng)對該模型進行定義，下面，給出定義該模型的SQL語句： CREATE TABLE STUDENT ( SNO CHAR(9) NOT NULL， SN CHAR(16)， SAGE INT， SEX CHAR(1) )；,“學生選課”系統(tǒng)的工程設計,CREATE TABLE COURSE ( CNO CHAR(6) NOT NULL， CN CHAR(22) )； CREATE TABLE SC ( SNO CHAR(9) NOT NULL， CNO CHAR(6)， GRADE INT )； CREATE TABLE DEP

8、ARTMENT ( DNO CHAR(9) NOT NULL， DN CHAR(16)， DEAN CHAR(8)；,“學生選課”系統(tǒng)的工程設計,接下來，便可以進行數(shù)據(jù)的輸入、修改和查詢，從而完成對“學生選課”的管理。 一個簡單的查詢：查詢選修了“數(shù)據(jù)庫”課程，并且成績在90分以上的所有學生的學號和姓名。 SELECT SNO,SN FROM STUDENT,SC,COURSE WHERE CN=數(shù)據(jù)庫 AND GRADE90; 系統(tǒng)運行以上語句后，即可在屏幕上顯示所求的結(jié)果。,3.2.1 抽象形態(tài),3.2 計算學科的3個學科形態(tài),一般科學技術方法論中有關抽象形態(tài)的論述,科學抽象是指在思維中對

9、同類事物去除其現(xiàn)象的、次要的方面，抽取其共同的、主要的方面，從而做到從個別中把握一般，從現(xiàn)象中把握本質(zhì)的認知過程和思維方法。 學科中的抽象形態(tài)包含著具體的內(nèi)容，它們是學科中所具有的科學概念、科學符號和思想模型。,計算學科中有關抽象形態(tài)的論述,計算作為一門學科報告認為：理論、抽象和設計是我們從事本領域工作的3種主要形態(tài)按人們對客觀事物認識的先后次序，我們將報告中的抽象列為第一個學科形態(tài)，理論列為第二個學科形態(tài)。抽象源于實驗科學。按客觀現(xiàn)象的研究過程，抽象形態(tài)包括以下4個步驟的內(nèi)容： （1）形成假設； （2）建造模型并作出預測； （3）設計實驗并收集數(shù)據(jù)； （4）對結(jié)果進行分析。,例子中有關抽象形

10、態(tài)的主要內(nèi)容及其簡要分析,在“學生選課”例子中，有關抽象形態(tài)的內(nèi)容可以用集合的方式表示為： A=學生，屬性，碼，關系，學號，姓名，年齡，性別，課程，課程號，課程名，成績，E-R圖，“學生選課”E-R圖，關系模型，“學生選課”關系模型， 對“學生選課”問題的抽象（感性認識）就是通過建立“學生選課”的E-R模型和關系模型來實現(xiàn)的，這一步是實現(xiàn)“學生選課”系統(tǒng)的關鍵。,3.2.2 理論形態(tài),3.2 計算學科的3個學科形態(tài),一般科學技術方法論中有關理論形態(tài)的論述,科學認識由感性階段上升為理性階段，就形成了科學理論?？茖W理論是經(jīng)過實踐檢驗的系統(tǒng)化了的科學知識體系，它是由科學概念、科學原理以及對這些概念、

11、原理的理論論證所組成的體系。 理論源于數(shù)學，是從抽象到抽象的升華，它們已經(jīng)完全脫離現(xiàn)實事物，不受現(xiàn)實事物的限制，具有精確的、優(yōu)美的特征，因而更能把握事物的本質(zhì)。,計算學科中有關理論形態(tài)的論述,在計算學科中，從統(tǒng)一合理的理論發(fā)展過程來看，理論形態(tài)包括以下4個步驟的內(nèi)容： （1）表述研究對象的特征（定義和公理）； （2）假設對象之間的基本性質(zhì)和對象之間可能存在的關系（定理）； （3）確定這些關系是否為真（證明）； （4）結(jié)論。,例子中有關理論形態(tài)的主要內(nèi)容及簡要分析,在與“學生選課”例子有關的關系數(shù)據(jù)庫領域中，理論形態(tài)的主要內(nèi)容可以用集合的方式表示為： T=關系代數(shù)，關系演算，數(shù)據(jù)依賴理論， 在數(shù)

12、據(jù)庫理論的指導下，我們就可以在“學生選課”關系模型（感性認識）的基礎上，建立對“學生選課”問題的理性認識，從而為“學生選課”管理系統(tǒng)的設計奠定基礎。,3.2.3 設計形態(tài),3.2 計算學科的3個學科形態(tài),一般科學技術方法論中有關設計形態(tài)的論述,設計形態(tài)與抽象、理論兩個形態(tài)存在的聯(lián)系 設計源于工程，并用于系統(tǒng)或設備的開發(fā)，以實現(xiàn)給定的任務。 設計形態(tài)和抽象、理論兩個形態(tài)具有許多共同的特點。設計必須以對自然規(guī)律的認識為前提。 設計必須創(chuàng)造出相應的人工系統(tǒng)和人工條件，還必須認識自然規(guī)律在這些人工系統(tǒng)中和人工條件下的具體表現(xiàn)形式 設計形態(tài)的主要特征與抽象、理論兩個形態(tài)的主要區(qū)別： 設計形態(tài)具有較強的實

13、踐性、社會性、綜合性。,計算學科中有關設計形態(tài)的論述,在計算學科中，從為解決某個問題而實現(xiàn)系統(tǒng)或裝置的過程來看，設計形態(tài)包括以下4個步驟的內(nèi)容： （1）需求分析； （2）建立規(guī)格說明； （3）設計并實現(xiàn)該系統(tǒng)； （4）對系統(tǒng)進行測試與分析。,例子中有關設計形態(tài)的主要內(nèi)容及簡要分析,“學生選課”一例中，有關設計形態(tài)的內(nèi)容是指：在數(shù)據(jù)庫理論的指導下，運用E-R圖和關系模型，實現(xiàn)對例子的感性認識和理性認識，最后借助某種關系DBMS（如Oracle等），實現(xiàn)“學生選課”應用軟件的編制。最終成果是“學生選課”應用軟件以及相關資料（如需求說明書）。 就例子而言，其內(nèi)容可以用集合的方式表示為： D=“學生選

14、課”應用軟件，“學生選課”需求說明，,3.2.4 3個學科形態(tài)的內(nèi)在聯(lián)系,3.2 計算學科的3個學科形態(tài),一般科學技術方法論中有關3個學科形態(tài)內(nèi)在聯(lián)系的簡要論述,在計算機科學與技術方法論的原始命題中，蘊含著人類認識過程的兩次飛躍，第一次飛躍是從物質(zhì)到精神，從實踐到認識的飛躍。這次飛躍包括兩個決定性的環(huán)節(jié)：一個是科學抽象，另一個是科學理論。 第二次飛躍是從精神到物質(zhì)，從認識到實踐的飛躍。這次飛躍的實質(zhì)對技術學科（計算學科就是一門技術學科）而言，其實就是要在理論的指導下，以抽象的成果為工具來完成各種設計工作。,計算學科中有關3個學科形態(tài)內(nèi)在聯(lián)系 的論述,3個學科形態(tài)的內(nèi)在聯(lián)系 抽象源于現(xiàn)實世界。建

15、立對客觀事物進行抽象描述的方法 建立具體問題的概念模型，實現(xiàn)對客觀世界的感性認識。 理論源于數(shù)學。建立完整的理論體系 建立具體問題的數(shù)學模型，從而實現(xiàn)對客觀世界的理性認識。 設計源于工程 。對客觀世界的感性認識和理性認識的基礎上，完成一個具體的任務；對工程設計中所遇到的問題進行總結(jié)，提出問題，由理論界去解決它。,3.7 計算機語言的發(fā)展及其 3個學科形態(tài)的內(nèi)在聯(lián)系,計算機語言在計算學科中占有特殊的地位，它是計算學科中最富有智慧的成果之一，它深刻地影響著計算學科各個領域的發(fā)展。不僅如此，計算機語言還是程序員與計算機交流的主要工具。因此，可以說如果不了解計算機語言，就談不上對計算學科的真正了解。,

16、現(xiàn)在，我們從自然語言與形式化語言、圖靈機和馮諾依曼型計算機、機器指令與匯編語言、計算機的層次結(jié)構、虛擬機的意義和作用、高級語言、應用語言和自然語言的形式化問題等方面，介紹計算機語言的發(fā)展歷程及其在抽象、理論和設計3個學科形態(tài)取得的主要成果，從而揭示計算機語言發(fā)展過程中3個學科形態(tài)的內(nèi)在聯(lián)系。,3.7.1 自然語言與形式語言,自然語言的定義 人類的語言（文字）是人類最普遍使用的符號系統(tǒng)。 其最基本、最普遍的形式是自然語言符號系統(tǒng) 自然語言是某一社會發(fā)展中形成的一種民族語言。例如，漢語、英語、法語和俄語等。,自然語言符號系統(tǒng)的基本特征,歧義性； 不夠嚴格和不夠統(tǒng)一的語法結(jié)構。 例3.2 他的發(fā)理得

17、好。 他的理發(fā)水平高； 理發(fā)師理他的發(fā)理得好。 例3.3 他的小說看不完。 他寫的小說看不完； 他收藏的小說看不完； 他是個小說迷。,高級語言的歧義性問題,高級程序設計語言其實也有語義的歧義性問題,高級程序設計語言存在較少的歧義性而已 例3.4 IF (表達式1) THEN IF (表達式2) THEN 語句1 ELSE 語句2。 IF (表達式1) THEN (IF (表達式2) THEN 語句1 ELSE 語句2)； IF (表達式1) THEN (IF (表達式2) THEN 語句1) ELSE 語句2。,形式語言,人們在自然語言符號系統(tǒng)的基礎上，逐步建立起了人工語言符號系統(tǒng)（也稱科學語

18、言系統(tǒng)），即各學科的專門科學術語（符號），使語言符號保持其單一性、無歧義性和明確性。 人工語言符號系統(tǒng)發(fā)展的第二階段叫形式化語言，簡稱形式語言。 形式語言是進行形式化工作的元語言，它是以數(shù)學和數(shù)理邏輯為基礎的科學語言。,形式語言的基本特點,有一組初始的、專門的符號集； 有一組精確定義的，由初始的、專門的符號組成的符號串轉(zhuǎn)換成另一個符號串的規(guī)則。 在形式語言中，不允許出現(xiàn)根據(jù)形成規(guī)則無法確定的符號串。,形式語言的語法,形式語言的語法：形式語言中的轉(zhuǎn)換規(guī)則。 語法不包含語義。 在一個給定的形式語言中，可以根據(jù)需要，通過賦值或模型對其進行嚴格的語義解釋，從而構成形式語言的語義。 語法和語義要作嚴格的

19、區(qū)分。,例3.5,語言W定義為： 初始符號集：a，b，c，d，e。 形成規(guī)則：上述符號組成的有限符號串中，能組成一英語單詞的為一公式；否則不是。 問：W是否為一形式語言？ 答：不是。 因為，根據(jù)形成規(guī)則，無法精確地定義轉(zhuǎn)換規(guī)則。 原因：形成規(guī)則（語法）中包含了語義。,例3.6,語言X定義為： 初始符號集：a，b，c，d，e，(，)，。 形成規(guī)則：上述符號組成的有限符號串中，構成表達式的為一公式，否則不是。 問：X是否為一形式語言？ 答：不是。 原因：與例3.5相同。,例3.7,語言Y定義為： 初始符號集：a，b，c，d，e，(，)，。 形成規(guī)則：上述符號組成的有限符號串中，凡以符號“(”開頭且

20、以“)”結(jié)尾的符號串，為一公式。 問：Y是否為一形式語言？ 答：不是。 因為，根據(jù)形成規(guī)則，無法對不是以符號“(”開頭且以“)”結(jié)尾的符號串進行判定。例如，(a+b)c。,例3.8,語言Z定義為： 初始符號集：a，b，c，d，e，(，)，。 形成規(guī)則：上述符號組成的有限符號串中，凡以符號“（”開頭且以“）”結(jié)尾的符號串，為一公式，否則不是。 問：Z是否為一形式語言？ 答：是。,形式化的產(chǎn)物,由于技術科學（計算學科主要是一門技術科學）的語言從類型上說基本上是描述性、斷定性而非評論性的，在描述性語言中又以分析陳述為主。 技術科學就更有可能充分運用形式語言來表達自己深刻而復雜的內(nèi)容，并進行演算化的推

21、理。 計算機語言是一種形式化語言。 計算機的誕生又與形式化研究的進程息息相關。 不論是計算機語言還是數(shù)字計算機，它們都是形式化的產(chǎn)物。,3.3.2 圖靈機與馮諾依曼型計算機,3.3 計算機語言的發(fā)展及其3個 學科形態(tài)的內(nèi)在聯(lián)系,圖靈機及其他計算模型,圖靈的觀點及結(jié)論： 凡是能用算法方法解決的問題，也一定能用圖靈機解決；凡是圖靈機解決不了的問題，任何算法也解決不了。 與圖靈機等價的計算模型： 遞歸函數(shù) -演算 POST規(guī)范系統(tǒng) 圖靈機是從過程這一角度來刻畫計算的本質(zhì)，其結(jié)構簡單、操作運算規(guī)則也較少，從而為更多的人所理解。,圖靈機,圖靈機由一條兩端可無限延長的帶子、一個讀寫頭以及一組控制讀寫頭工作

22、的命令組成，,圖靈機,寫在帶子上的符號為一個有窮字母表：S0，S1，S2，Sp。 可以認為這個有窮字母表僅有S0、S1兩個字符， 其中S0可以看作是“0”，S1可以看作是“1”， 由 “0”和“1”組成的字母表可以表示任何一個數(shù)。,由于“0”和“1”只有形式的意義，因此，也可以將S0改稱為“白”，S1改稱為“黑”，甚至，還可以改稱為“桌子”和“老虎”，這樣改稱的目的在于割斷與直覺的聯(lián)系，并加深對布爾域中的值真，假，以及二進制機器本質(zhì)的理解。機器的控制狀態(tài)表為：q1，q2，qm。 將一個圖靈機的初始狀態(tài)設為q1，在每一個具體的圖靈機中還要確定一個結(jié)束狀態(tài)qw。,一個給定機器的“程序”,機器內(nèi)的五

23、元組（qiSjSkR（或L或N）ql）形式的指令集，五元組定義了機器在一個特定狀態(tài)下讀入一個特定字符時所采取的動作。5個元素的含義如下： qi表示機器目前所處的狀態(tài)； Sj表示機器從方格中讀入的符號； Sk表示機器用來代替Sj寫入方格中的符號； R、L、N分別表示向右移一格、向左移一格、不移動； ql表示下一步機器的狀態(tài)。,一個機器計算的結(jié)果是從機器停止時帶子上的信息得到的。容易看出，q1S2S2Rq3指令和q3S3S3Lq1指令如果同時出現(xiàn)在機器中，當機器處于狀態(tài)q1，第一條指令讀入的是S2，第二條指令讀入的是S3，那么機器會在兩個方塊之間無休止地工作。 另外，如果q3S2S2Rq4和q3S

24、2S4Lq6指令同時出現(xiàn)在機器中，當機器處于狀態(tài)q3并在帶子上掃描到符號S2時，就產(chǎn)生了二義性的問題，機器就無法判定。,例子：,b表示空格，q1表示機器的初始狀態(tài)， q4表示機器的結(jié)束狀態(tài)，設帶子上的輸入信息是10100010，讀入頭位對準最右邊第一個為0的方格，狀態(tài)為初始狀態(tài)q1。規(guī)則如下： q1 0 1 L q2 q1 1 0 L q3 q1 b b N q4 q2 0 0 L q2 q2 1 1 L q2 q2 b b N q4 q3 0 1 L q2 q3 1 0 L q3 q3 b b N q4,計算結(jié)果是10100011，即對給定的數(shù)加1。,以上命令計算的是這樣一個函數(shù)：S(x)x

25、1。當沒有輸入時，即初始狀態(tài)所指的方格為空格（b）時，不改變空格符，讀寫頭不動并停機。,圖靈機的計算能力,圖靈機可以計算 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ù)都是圖靈機可計算的。,馮諾依曼型計算機,ENIAC的結(jié)構在很大程度上是依照機電系統(tǒng)設計的，還存在重大的線路結(jié)構等問題。 在圖靈等人工作的影響下，1946年6月，美國杰出的數(shù)學家馮

26、諾依曼（Von Neumann）及其同事完成了關于“電子計算裝置邏輯結(jié)構設計”的研究報告， 具體介紹了制造電子計算機和程序設計的新思想 至今為止，大多數(shù)計算機采用的仍然是馮諾依曼型計算機的組織結(jié)構，只是作了一些改進而已。因此，馮諾依曼被人們譽為“計算機器之父”。,馮諾依曼型計算機的組織結(jié)構,輸入設備和輸出設備,輸入設備和輸出設備,作用：是將信息輸入計算機和輸出計算機。 常用的文字輸入設備是鍵盤（還有掃描儀、穿孔卡片讀入機和鼠標等專用輸入設備） 當在鍵盤上按下一個鍵時，按下的鍵通過編碼變換成機器可讀的數(shù)據(jù)形式， 如字符“A”變換成ASCII碼“1000001”，該編碼數(shù)據(jù)隨即存入存儲器等待處理，

27、 通過與“1000001”對應的字符點陣數(shù)據(jù)在屏幕上顯示一個字符“A”。 輸出設備有打印機、顯示器、繪圖儀、磁記錄設備等。,存儲器,存儲器是一種數(shù)據(jù)或信息的存儲部件，它分成很多存儲單元，并按照一定的方式進行排列。每個單元都編了號，稱為存儲地址。指令和數(shù)據(jù)存放在存儲器中,而且對指令和數(shù)據(jù)同等對待，都不加區(qū)別地送到運算器中運算。指令在存儲器中基本上是按執(zhí)行順序存儲的，由指令計數(shù)器指明要執(zhí)行的指令在存儲器中的地址。 存儲器一般分為內(nèi)存儲器與外存儲器兩大類。內(nèi)存一般安裝在主機板上，根據(jù)材料和工作原理的不同，內(nèi)存可分為隨機存儲器（RAM）和只讀存儲器（ROM）兩種?？刂破骱瓦\算器只能接受在內(nèi)存中存放的指

28、令和數(shù)據(jù)。 外存一般安裝在主機板之外，例如磁盤就是一種常用的外存。外存上面的信息可長久保存，但這些信息必須讀入內(nèi)存之后才能被控制器和運算器所利用。磁盤按其材料的不同，又可分為軟盤和硬盤兩種。,存儲器,存儲器是一種數(shù)據(jù)或信息的存儲部件，它分成很多存儲單元，并按照一定的方式進行排列。每個單元都編了號，稱為存儲地址。指令和數(shù)據(jù)存放在存儲器中,而且對指令和數(shù)據(jù)同等對待，都不加區(qū)別地送到運算器中運算。指令在存儲器中基本上是按執(zhí)行順序存儲的，由指令計數(shù)器指明要執(zhí)行的指令在存儲器中的地址。 存儲器一般分為內(nèi)存儲器與外存儲器兩大類。內(nèi)存一般安裝在主機板上，根據(jù)材料和工作原理的不同，內(nèi)存可分為隨機存儲器（RAM

29、）和只讀存儲器（ROM）兩種。控制器和運算器只能接受在內(nèi)存中存放的指令和數(shù)據(jù)。,存儲器,外存一般安裝在主機板之外，例如磁盤就是一種常用的外存。外存上面的信息可長久保存，但這些信息必須讀入內(nèi)存之后才能被控制器和運算器所利用。磁盤按其材料的不同，又可分為軟盤和硬盤兩種。,CPU(運算器和控制器 ),central processing unit,Register、控制單元,計算機中控制數(shù)據(jù)操作的電路并不與主存直接相連 這些電路被封裝在一起，即CPU CPU含有自己的存儲單元（register） Register作為臨時空間來存儲CPU所操作的數(shù)，保存算術邏輯單元的輸入與輸出數(shù)據(jù) 控制單元負責將主存

30、中的數(shù)據(jù)移到register，然后通知算術邏輯單元所需要的數(shù)據(jù)在哪個register,總線,總線：CPU與主存之間用總線連接，利用總線 CPU通過提供存儲單元目標地址以及讀信號來選擇、讀取數(shù)據(jù) CPU通過提供存儲單元目標地址以及寫信號來放置、寫入信號 誰發(fā)明了什么 程序存儲的概念：由賓西法尼亞大學Moore電子工程學院的J.P.Echert提出，John von Neumann只是先發(fā)表了程序存儲的概念,CPU和主存儲器通過總線相連,3.3.3 機器指令與匯編語言,3.3 計算機語言的發(fā)展及其3個 學科形態(tài)的內(nèi)在聯(lián)系,機器指令與匯編語言,為了實現(xiàn)程序存儲的概念，CPU要能識別二進制編碼的指令

31、機器語言指令集合以及編碼系統(tǒng),指令系統(tǒng),CPU必須能夠解碼并執(zhí)行的機器指令很少 一旦計算機可以執(zhí)行一些基本的而且是精選的操作，加入額外的操作理論上是不會改變計算機的能力的 是否充分利用這種特性導致了兩種不同的計算機設計： CISC(complex instruction set computer) RISC(reduced instruction set computer),CISC,最初人們采用的是進一步增強原有指令的功能，并設置更為復雜的指令的方法 采用這種設計思路的計算機被稱為復雜指令系統(tǒng)計算機（CISC）。 CISC的思路是由IBM公司提出的，并以1964年IBM研制的IBM 360系

32、統(tǒng)為代表。,CISC缺點,80%的指令只在20%的運行時間里用到； 一些指令非常繁雜，而執(zhí)行效率甚至比用幾條簡單的基本指令組合的實現(xiàn)還要慢。 龐雜的指令系統(tǒng)也給超大規(guī)模集成電路（VLSI）的設計帶來了困難， 它不但不利于設計自動化技術的應用，延長了設計周期，增加了成本， 容易增加設計中出現(xiàn)錯誤的機會，從而降低了系統(tǒng)的可靠性。,RISC,思路主要是通過減少指令總數(shù)和簡化指令的功能來降低硬件設計的復雜度，從而提高指令的執(zhí)行速度。 優(yōu)點:與CISC技術相比 簡化了指令系統(tǒng)，適合超大規(guī)模集成電路的實現(xiàn)； 提高了機器執(zhí)行的速度和效率； 降低了設計成本，提高了系統(tǒng)的可靠性； 提供了直接支持高級語言的能力，

33、簡化了編譯程序的設計。,機器指令,機器指令系統(tǒng)每臺數(shù)字電子計算機在設計中，都規(guī)定了一組指令。 機器語言用機器指令形式編寫的程序。 在裸機級，計算機語言關于算法的描述采用的是實際機器的機器指令，它的符號集是0，1， 支撐實際機器的理論是圖靈機等計算模型； 在圖靈機等計算模型理論的指導下，有關設計形態(tài)的主要成果有馮諾依曼型計算機等具體實現(xiàn)思想和技術，以及各類數(shù)字電子計算機產(chǎn)品。,計算機語言在裸機級所取得的主要成果,匯編語言,采用字符和十進制數(shù)來代替二進制代碼的思想。 例3.10 對2+6進行計算的算法描述 用機器指令對“2+6”進行計算的算法描述： 1011000000000110 0000010

34、000000010 101000100101000000000000 匯編語言對“2+6”進行計算的算法描述： MOV AL，6 ADD AL，2 MOV VC，AL,匯編語言語句與特定的機器指令有一一對應的關系，但是它畢竟不同于由二進制組成的機器指令，它還需要經(jīng)匯編程序翻譯為機器指令后才能運行。 匯編語言源程序經(jīng)匯編程序翻譯成機器指令，再在實際的機器中執(zhí)行。 就匯編語言的用戶而言，該機器是可以直接識別匯編語言的，從而產(chǎn)生了一個屬于抽象形態(tài)的重要概念，即虛擬機的概念。,3.3.4 高級語言,3.3 計算機語言的發(fā)展及其3個 學科形態(tài)的內(nèi)在聯(lián)系,高級語言,雖然與機器語言相比，匯編語言的產(chǎn)生是一個

35、很大的進步，但是用它來進行程序設計仍然比較困難。于是人們著手對它進行改進。一是發(fā)展宏匯編，即用一條宏指令代替若干條匯編指令，從而提高編程效率?，F(xiàn)在人們使用的匯編語言，大多數(shù)都是宏匯編語言。二是創(chuàng)建高級語言，使編程更加方便。 如用高級語言對例子2+6進行計算的算法描述，其描述與數(shù)學描述一樣，即2+6。,高級語言的分類,按語言的特點，可以將高級語言劃分為： 過程式語言（如Cobol，F(xiàn)orturn，Algol，Pascal，Ada，C） 函數(shù)式語言（如Lisp） 數(shù)據(jù)流語言（如SISAL，VAL） 面向?qū)ο笳Z言（如Smalltalk，CLU，C+） 邏輯語言（如Prolog） 字符串語言（如SNO

36、BOL） 并發(fā)程序設計語言（如Concurrent Pascal，Modula 2）等,高級語言的形式化,20世紀50年代 美國語言學家喬姆斯基（Noam Chomsky）關于語言分層的理論， 巴科斯（Backus）、瑙爾（Naur）的關于“上下文無關方法表示形式”的研究成果推動了語法形式化的研究。 其結(jié)果是，在ALGOL60的文本設計中第一次使用了BNF范式來表示語法，并且第一次在語言文本中明確提出應將語法和語義區(qū)分開來。,高級語言的形式化,20世紀50年代至60年代間，面向語法的編譯自動化理論得到了很大發(fā)展，使語法形式化研究的成果達到實用化的水平。 語法形式化問題基本解決以后，人們逐步把注

37、意力集中到語義形式化的研究方面, 20世紀60年代，相繼誕生了 操作語義學 指稱語義學 公理語義學 代數(shù)語義學等語義學理論,數(shù)據(jù)類型的抽象,相對于匯編語言和機器語言，高級語言的數(shù)據(jù)類型的抽象層次有了很大地提高，出現(xiàn)了 整型 實型 字符型 布爾型 用戶自定義類型 抽象數(shù)據(jù)類型 數(shù)據(jù)類型的抽象極大地方便了用戶對數(shù)據(jù)的抽象描述，為實現(xiàn)軟件設計的工程化奠定了基礎。,高級語言中有關抽象、理論和設計3個形態(tài)的主要內(nèi)容,3.3.5 應用語言,3.3 計算機語言的發(fā)展及其3個 學科形態(tài)的內(nèi)在聯(lián)系,計算機語言的劃分,一般將它劃分為5代： 第一代為機器語言； 第二代為匯編語言； 第三代為高級語言； 第四代為“非過

38、程性語言”； 第五代為自然語言。,4GL,提供了功能強大的非過程化問題定義手段，用戶只需告知系統(tǒng)“做什么”，而無需說明“怎么做” 以數(shù)據(jù)庫管理系統(tǒng)所提供的功能為核心，進一步構造了開發(fā)高層軟件系統(tǒng)的開發(fā)環(huán)境， 報表生成 多窗口表格設計 菜單生成系統(tǒng)等 4GL的代表性軟件系統(tǒng)有：PowerBuilder、Delphi和INFORMOX-4GL等。,應用語言中有關抽象、理論和設計形態(tài)的主要內(nèi)容,3.3.6 自然語言,3.3 計算機語言的發(fā)展及其3個 學科形態(tài)的內(nèi)在聯(lián)系,自然語言計算機處理層次的劃分,四個層次： 第一層次是文字和語音，即基本語言信息的構成； 第二層次是語法，即語言的形態(tài)結(jié)構； 第三層次是語義，即語言與它所指的對象之間的關系； 第四層次是語用，即語言與它的使用者之間的關系。,自然語言的輸入問題,鍵盤（漢字的編碼輸入也是通過鍵盤進行輸入） 掃描 手寫 語音等方式進入計算機 計算機可以對輸入的文字進行各種加工和處理（如放大、變形等），現(xiàn)在大多數(shù)的報紙、雜志、書籍等就是這一處理的產(chǎn)物。,自然語言的形式化問題,要使計算機對自然語言進行處理, 就必須使其形式化。 喬姆斯說：一個說本族語的人具有一種理解他過去從未聽到過的句子的