計算機方法論chapter4計算學科中的三個學科形態(tài)課件

1、計算學科中的三個學科形態(tài)fuhao_zoufoxmail計算機科學中的問題求解初探計算學科中的三個學科形態(tài) 抽象理論設計（三種形態(tài)）：計算學科中的基本內(nèi)容，基本概念；同時反映了人們的認識是從感性認識（抽象）到理性認識（理論），再由理性認識（理論）回到實踐（設計）中來的一般科學思維方法。21、抽象形態(tài) 科學抽象是指在思維中對同類事物去除其現(xiàn)象的、次要的方面，抽取其共同的、主要的方面，從而做到從個別中把握一般，從現(xiàn)象中把握本質(zhì)的認知過程和思維方法。 學科中的抽象形態(tài)包含著具體的內(nèi)容，它們是學科中所具有的科學概念、科學符號和思想模型。一、三個形態(tài)的主要內(nèi)容3 抽象形態(tài)源于現(xiàn)實世界（建立對客觀事物 進

2、行抽象描述的方法，建立概念模型） 形成假設 建造模型并作出預測 設計實驗并收集數(shù)據(jù) 對結(jié)果進行分析 4 科學認識由感性階段上升為理性階段，就形成了科學理論?？茖W理論是經(jīng)過實踐檢驗的系統(tǒng)化了的科學知識體系，它是由科學概念、科學原理以及對這些概念、原理的理論論證所組成的體系。 理論源于數(shù)學，是從抽象到抽象的升華，它們已經(jīng)完全脫離現(xiàn)實事物，不受現(xiàn)實事物的限制，具有精確的、優(yōu)美的特征，因而更能把握事物的本質(zhì)。2、理論形態(tài)5 表述研究對象的特征（定義和公理） 假設對象之間的基本性質(zhì)和對象之間可能存在的關系（定理） 確定這些關系是否為真（證明） 結(jié)論 理論形態(tài)源于數(shù)學（建立理論體系，建立 數(shù)學模型）63、

3、設計形態(tài)設計形態(tài)與抽象、理論兩個形態(tài)存在的聯(lián)系：設計源于工程，用于系統(tǒng)或設備的開發(fā)，實現(xiàn)給定的任務設計形態(tài)和抽象、理論兩個形態(tài)都須以對自然規(guī)律的認識為前提設計必須創(chuàng)造出相應的人工系統(tǒng)和人工條件，還必須認識自然規(guī)律的具體表現(xiàn)形式設計形態(tài)的主要特征與抽象、理論兩個形態(tài)的主要區(qū)別：設計形態(tài)具有較強的實踐性、社會性、綜合性7 需求分析 建立規(guī)格說明 設計并實現(xiàn)該系統(tǒng) 對系統(tǒng)進行測試與分析 設計形態(tài)源于工程（完成一個具體任務， 總結(jié)與升華）8三個學科形態(tài)的內(nèi)在聯(lián)系在計算學科的原始命題中，蘊含著人類認識過程的兩次飛躍第一次飛躍是從物質(zhì)到精神，從實踐到認識的飛躍。這次飛躍包括兩個決定性的環(huán)節(jié)：一個是科學抽象

4、，另一個是科學理論。第二次飛躍是從精神到物質(zhì)，從認識到實踐的飛躍。這次飛躍的實質(zhì)對技術學科（計算學科就是一門技術學科）而言，其實就是要在理論的指導下，以抽象的成果為工具來完成各種設計工作。 9抽象源于現(xiàn)實世界。建立對客觀事物進行抽象描述的方法，建立具體問題的概念模型，實現(xiàn)對客觀世界的感性認識。 理論源于數(shù)學。建立完整的理論體系，建立具體問題的數(shù)學模型，從而實現(xiàn)對客觀世界的理性認識。設計源于工程。對客觀世界的感性認識和理性認識的基礎上，完成一個具體的任務；對工程設計中所遇到的問題進行總結(jié)，提出問題，由理論界去解決它。三個學科形態(tài)的內(nèi)在聯(lián)系 10二、程序設計語言三種形態(tài)實例自然語言應用語言（4GL

5、）高級語言匯編語言機器語言抽象 理論 設計t11計算機語言在裸機級所取得的主要成果計算機語言抽象理論設計裸機級（機器語言）的主要內(nèi)容和成果語言的符號集為：0，1；用機器指令對算法進行描述圖靈機(過程語言的基礎)；波斯特系統(tǒng)（字符串處理語言的基礎）；-演算（函數(shù)式語言的基礎）等計算模型馮諾依曼型計算機等實現(xiàn)技術；數(shù)字電子計算機產(chǎn)品BACK121、自然語言與形式語言歧義性；不夠嚴格和不夠統(tǒng)一的語法結(jié)構(gòu)。 他的發(fā)理得好。他的理發(fā)水平高；理發(fā)師理他的發(fā)理得好。 他的小說看不完。 他寫的小說看不完；他收藏的小說看不完；他是個小說迷。 人類的語言（文字）是人類最普遍使用的符號系統(tǒng)。其最基本、最普遍的形式是

6、自然語言符號系統(tǒng)自然語言是某一社會發(fā)展中形成的一種民族語言。例如，漢語、英語、法語和俄語等。13高級語言的歧義性問題 高級程序設計語言也有語義的歧義性問題，只是存在的歧義性較少而已例 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。 14形式語言有一組初始的、專門的符號集；有一組精確定義的，由初始的、專門的符號組成的符號串轉(zhuǎn)換成另一個符號串的規(guī)則。在形式語言中，不允許出現(xiàn)根據(jù)形成

7、規(guī)則無法確定的符號串。人工語言符號系統(tǒng)發(fā)展的第二階段叫形式化語言，簡稱形式語言。形式語言是進行形式化工作的元語言，它是以數(shù)學和數(shù)理邏輯為基礎的科學語言。15形式語言的語法形式語言的語法：形式語言中的轉(zhuǎn)換規(guī)則。語法不包含語義。在一個給定的形式語言中，可以根據(jù)需要，通過賦值或模型對其進行嚴格的語義解釋，從而構(gòu)成形式語言的語義。語法（Syntax）和語義（Semantics）要作嚴格的區(qū)分。16例1：形式語言語法示例語言W定義為：初始符號集：a，b，c，d，e。形成規(guī)則：上述符號組成的有限符號串中，能組成一英語單詞的為一公式；否則不是。問：W是否為一形式語言？答：不是。因為，根據(jù)形成規(guī)則，無法精確地

8、定義轉(zhuǎn)換規(guī)則。原因：形成規(guī)則（語法）中包含了語義。17例2：形式語言語法示例語言X定義為：初始符號集：a，b，c，d，e，(，)，。形成規(guī)則：上述符號組成的有限符號串中，構(gòu)成表達式的為一公式，否則不是。問：X是否為一形式語言？答：不是。原因：與例1相同。 18例3：形式語言語法示例語言Y定義為：初始符號集：a，b，c，d，e，(，)，。形成規(guī)則：上述符號組成的有限符號串中，凡以符號“(”開頭且以“)”結(jié)尾的符號串，為一公式。問：Y是否為一形式語言？答：不是。因為，根據(jù)形成規(guī)則，無法對不是以符號“(”開頭且以“)”結(jié)尾的符號串進行判定。例如，(a+b)c。 19例4：形式語言語法示例語言Z定義為

9、：初始符號集：a，b，c，d，e，(，)，。形成規(guī)則：上述符號組成的有限符號串中，凡以符號“（”開頭且以“）”結(jié)尾的符號串，為一公式，否則不是。問：Z是否為一形式語言？答：是。20圖靈機與馮諾依曼型計算機 圖靈機計算模型（理論） 圖靈計算機科學之父馮諾依曼型計算機計算機組織結(jié)構(gòu)（設計） 馮諾依曼計算機器之父212. 圖靈機圖靈的觀點及結(jié)論：凡是能用算法方法解決的問題，也一定能用圖靈機解決；凡是圖靈機解決不了的問題，任何算法也解決不了。與圖靈機等價的計算模型：遞歸函數(shù)-演算POST規(guī)范系統(tǒng)圖靈機是從過程這一角度來刻畫計算的本質(zhì)，其結(jié)構(gòu)簡單、操作運算規(guī)則也較少，從而為更多的人所理解。22圖靈機圖靈

10、機由一條兩端可無限延長的帶子、一個讀寫頭以及一組控制讀寫頭工作的命令組成。23圖靈機寫在帶子上的符號為一個有窮字母表： S0，S1，S2，Sp可以認為這個有窮字母表僅有S0、S1兩個字符其中S0可以看作是“0”，S1可以看作是“1”由 “0”和“1”組成的字母表可以表示任何一個數(shù)24一個給定機器的“程序”機器內(nèi)的五元組（qiSjSkR（或L或N）ql）形式的指令集，五元組定義了機器在一個特定狀態(tài)下讀入一個特定字符時所采取的動作。5個元素的含義如下： qi表示機器目前所處的狀態(tài)； Sj表示機器從方格中讀入的符號； Sk表示機器用來代替Sj寫入方格中的符號； R、L、N分別表示向右移一格、向左移一

11、格、不移動；ql表示下一步機器的狀態(tài)。 25一個機器計算的結(jié)果是從機器停止時帶子上的信息得到的。如果q1S2S2Rq3指令和q3S3S3Lq1指令同時出現(xiàn)在機器中，當機器處于狀態(tài)q1，第一條指令讀入的是S2，第二條指令讀入的是S3，那么機器會在兩個方塊之間無休止地工作。-死循環(huán)如果q3S2S2Rq4和q3S2S4Lq6指令同時出現(xiàn)在機器中，當機器處于狀態(tài)q3并在帶子上掃描到符號S2時，就產(chǎn)生了二義性的問題，機器就無法判定。-歧義26例5：圖靈機示例b表示空格，q1表示機器的初始狀態(tài)， q4表示機器的結(jié)束狀態(tài)，設帶子上的輸入信息是10100010，讀入頭位對準最右邊第一個為0的方格，狀態(tài)為初始狀

12、態(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 q427計算過程如下：(1) q1 0 1 L q2 (2) q1 1 0 L q3 (3) q1 b b N q4(4) q2 0 0 L q2 (5) q2 1 1 L q2 (6) q2 b b N q4(7) q3 0 1 L q2 (8) q3 1 0 L q3 (9) q3 b b N q428計算結(jié)果是10100011，即對給定的數(shù)加1。以上命令計算的是這樣一

13、個函數(shù)：S(x)x1。當沒有輸入時，即初始狀態(tài)所指的方格為空格（b）時，不改變空格符，讀寫頭不動并停機。 29圖靈機的計算能力圖靈機可以計算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ù)都是圖靈機可計算的。 303、預備知識馮諾依曼計算機 P641946年2月14日，世界上第一臺數(shù)字電子計算機ENIAC在美國賓夕法尼亞大學研制成功。ENIAC的結(jié)構(gòu)在很大程

14、度上是依照機電系統(tǒng)設計的，還存在重大的線路結(jié)構(gòu)等問題。在圖靈等人工作的影響下，1946年6月，美國杰出的數(shù)學家馮諾依曼（Von Neumann）及其同事完成了關于“電子計算裝置邏輯結(jié)構(gòu)設計”的研究報告，具體介紹了制造電子計算機和程序設計的新思想至今為止，大多數(shù)計算機采用的仍然是馮諾依曼型計算機的組織結(jié)構(gòu)，只是作了一些改進而已。因此，馮諾依曼被人們譽為“計算機器之父”。31馮諾依曼型計算機的組織結(jié)構(gòu) 32 馮諾依曼計算機的體系結(jié)構(gòu)33基于總線的計算機系統(tǒng)的硬件組成34輸入設備和輸出設備作用：是將信息輸入計算機和輸出計算機。常用的文字輸入設備是鍵盤（還有掃描儀、穿孔卡片讀入機和鼠標等專用輸入設備）

15、。當在鍵盤上按下一個鍵時，按下的鍵通過編碼變換成機器可讀的數(shù)據(jù)形式，如字符“A”變換成ASCII碼“1000001”，該編碼數(shù)據(jù)隨即存入存儲器等待處理，通過與“1000001”對應的字符點陣數(shù)據(jù)在屏幕上顯示一個字符“A”。輸出設備有打印機、顯示器、繪圖儀、磁記錄設備等。 35存儲器存儲器是一種數(shù)據(jù)或信息的存儲部件分為兩大類： 內(nèi)存儲器（內(nèi)存） 外存儲器（外存）36存儲器內(nèi)存隨機存儲器（RAM）只讀存儲器（ROM）：一般用于BIOS外存硬盤軟盤光盤磁帶優(yōu)盤（USB盤）固態(tài)硬盤（SSD）相變存儲（PCM）37運算器和控制器Central Processing Unit（中央處理單元，CPU）38寄

16、存器、控制單元計算機中控制數(shù)據(jù)操作的電路并不與主存直接相連這些電路被封裝在一起，即CPUCPU含有自己的存儲單元（register）寄存器（Register）作為臨時空間來存儲CPU所操作的數(shù)，保存算術邏輯單元的輸入與輸出數(shù)據(jù)控制單元負責將主存中的數(shù)據(jù)移到register，然后通知算術邏輯單元所需要的數(shù)據(jù)在哪個register39總線（Bus）總線：CPU與主存之間用總線連接利用總線CPU通過提供存儲單元目標地址以及讀信號來選擇、讀取數(shù)據(jù)CPU通過提供存儲單元目標地址以及寫信號來放置、寫入信號40CPU和主存儲器通過總線相連41早期計算機設計中的程序執(zhí)行 在早期計算機設計中，人們認為，程序與數(shù)

17、據(jù)是兩種完全不同的實體。自然地將程序與數(shù)據(jù)分離，數(shù)據(jù)存放在存儲器中，程序則作為控制器的一個組成部分（如外插型的程序）。這樣，每執(zhí)行一個程序，都要對控制器進行設置。如在ENIAC中，編制一個解決小規(guī)模問題的程序，就要在40多塊幾英尺長的插接板上，插上幾千個帶導線的插頭。顯然，這樣的機器效率不僅低，且靈活性也很差。 42基于馮諾依曼計算機體系結(jié)構(gòu)的程序執(zhí)行馮諾依曼計算機的體系結(jié)構(gòu)，也即存儲程序式計算機的體系結(jié)構(gòu)，則是將程序與數(shù)據(jù)一樣看待，對程序像數(shù)據(jù)那樣進行適當?shù)木幋a，然后與數(shù)據(jù)一起共同存放在存儲器中。計算機可以通過改變存儲器中的內(nèi)容，對數(shù)據(jù)進行操作。從原來對程序和數(shù)據(jù)的嚴格區(qū)別到一樣看待，這個觀

18、念上的轉(zhuǎn)變是計算機史上的一場革命，它反映的正是計算的本質(zhì)，即符號串的變化。434、機器指令（語言） CISC與RISC 為了實現(xiàn)程序存儲的概念，CPU要能識別二進制編碼的指令44指令系統(tǒng)CPU必須能夠解碼并且執(zhí)行的機器指令很少一旦計算機可以執(zhí)行一些基本的而且是精選的操作，加入額外的操作理論上是不會改變計算機的能力的。是否充分利用這種特性導致了兩種不同的計算機設計：CISC(Complex instruction set computer)RISC(Reduced instruction set computer)45CISC最初人們采用的是進一步增強原有指令的功能，并設置更為復雜的指令的方法。

19、采用這種設計思路的計算機被稱為復雜指令系統(tǒng)計算機（CISC）。CISC的思路是由IBM公司提出的，并以1964年IBM研制的IBM 360系統(tǒng)為代表。46CISC缺點80%的指令只在20%的運行時間里用到。一些指令非常繁雜，而執(zhí)行效率甚至比用幾條簡單的基本指令組合的實現(xiàn)還要慢。龐雜的指令系統(tǒng)也給超大規(guī)模集成電路（VLSI）的設計帶來了困難，它不但不利于設計自動化技術的應用，延長了設計周期，增加了成本，容易增加設計中出現(xiàn)錯誤的機會，從而降低了系統(tǒng)的可靠性。 47RISC思路主要是通過減少指令總數(shù)和簡化指令的功能來降低硬件設計的復雜度，從而提高指令的執(zhí)行速度。優(yōu)點：與CISC技術相比簡化了指令系統(tǒng)，適合超大規(guī)模集成電路的實現(xiàn)； 提高了機器執(zhí)行的速度和效率；降低了設計成本，提高了系統(tǒng)的可靠性； 提供了直接支持高級語言的能力，簡化了編譯程序的設計。48機器指令機器指令系統(tǒng)每臺數(shù)字電子計算機在設計中，都規(guī)定了一組指令。機器語言用機器指令形式編寫的程序。在裸機級，計算機語言關于算法的描述采用的是實際機器的機器指令，它的符號集是0, 1。支撐實際機器的理論是圖靈機等計算模型；在圖靈機等計算