第五章計算機科學

1、,第五章信息管理的技術基礎：計算機科學,本章學習目的,了解計算機科學的知識體系初步了解計算機的硬件知識初步了解計算機的軟件知識了解數據組織的基本知識,本章內容,計算機學科的簡介 機器體系結構 軟件數據組織,5.1 計算機學科的簡介,學科的發(fā)展學科的方法論學科的知識體系,,學科的發(fā)展,計算學科的劃分計算機學科稱為計算學科（Computing Discipline，CD）或計算科學（Computing Science，C

2、C），其包括：計算機科學（Computer Science，CS）、計算機工程（Computer Engineering，CE）、軟件工程（Software Engineering，SE）和信息系統（Information Systems，IS）四大分支。發(fā)展的代表階段奠基年代、機器年代、算法年代、獨立系統年代、分布式年代、應用年代、以人為本年代。知識體系與發(fā)展 支撐專業(yè)基礎 ：數學、電子學、高級語言和程序設計 主要專業(yè)基礎

3、：數據結構與算法、計算機原理、基本邏輯、編譯技術、操作系統、高級語言與程序設計、數據庫原理 最新發(fā)展前沿：并行技術、分布計算、網絡技術、軟件工程,,,學科的方法論,理論 主要要素為定義和公理、定理、證明、結果的解釋。抽象（模型化） 源于實驗科學，主要要素為數據采集方法和假設的形式說明、模型的構造與預測、實驗分析、結果分析。設計 源于工程學，用來開發(fā)求解給定問題的系統和設備。主要要素為需求說明、規(guī)格說明、設計和實現方法、測試和

4、分析。用來開發(fā)求解給定問題的系統。,,學科的形態(tài)與科學實踐的關系,,,學科的認識與實踐的關系,,,,學科的知識體系-1,知識體系組成-1離散結構（Discrete Structure，DS）由函數、關系和集合、基本邏輯、證明技巧、計數基礎、圖與樹構成。程序設計基礎（Programming Foundation，PF）由程序設計基本結構、算法與問題求解、基本數據結構、遞歸、事件驅動程序設計組成。,,學科的知識體系-2,知識體系組成

5、-2算法與復雜性（Algorithm and complexity，AL）有算法分析基礎、算法策略、基本算法、分布式算法、可計算性理論基礎、復雜性類（P類和NP類）、自動機理論、高級算法分析、加密算法、幾何算法、并行算法。計算機組織與體系結構（computer framework and system ARchitecture，AR）包括數字邏輯與數字系統、數據的機器級表示、匯編級機器組織、存儲系統組織和結構、接口和通信、功能組

6、織、多處理和其它系統結構、性能提高技術、網絡與分布式系統結構。,,學科的知識體系-3,知識體系組成-3操作系統（Operating System，OS）操作系統概述、操作系統原理、并發(fā)性、調度與分派、內存管理、設備管理、安全與保護、文件系統、實時和嵌入式系統、容錯、系統性能評價、腳本。網絡及其計算（Network and its Computing，NC）網絡及其計算介紹、通信與網絡、網絡安全、客戶-服務器計算舉例、構建Web應

7、用、網絡管理、壓縮與解壓縮、多媒體數據技術、無線和移動計算。,,學科的知識體系-4,知識體系組成-4程序設計語言（Programming Language，PL）程序設計語言概論、虛擬機、語言翻譯簡介、聲明和類型、抽象機制、面向對象程序設計、函數程序設計、語言翻譯系統、類型系統、程序設計語言的語義、程序設計語言的設計。人機交互（Human-Computer Interaction，HCI）人機交互基礎、簡單圖形用戶界面的創(chuàng)建、以

8、人為本的軟件評估、以人為本的軟件開發(fā)、圖形用戶界面的設計、圖形用戶界面的編程、多媒體系統的人機交互、協作和通信的人機交互。,,學科的知識體系-5,知識體系組成-5圖形學和可視化計算（Graphic and Visual computing，GV）圖形學的基本技術、圖形系統、圖形通信、幾何建模、基本圖形繪制方法、高級圖形繪制方法、先進技術、計算機動畫、可視化、虛擬現實、計算機視覺。智能系統（Intelligent System，IS

9、）智能系統基本問題、搜索和約束滿足、知識表示和知識推理、高級搜索、高級知識表示和知識推理、主體、自然語言處理技術、機器學習和神經網絡、人工智能規(guī)劃系統、機器人。信息系統（Information System，IS）信息模型和信息系統、數據庫系統、數據模型化、關系數據庫、數據庫查詢語言、關系數據庫設計、事務處理、分布式數據庫、物理數據庫設計、數據挖掘、信息存儲和信息檢索、超文本和超媒體、多媒體信息和系統、數字圖書館。,,學科的知識體

10、系-6,知識體系組成-6軟件工程（Software Engineering，SE）軟件設計、使用API、軟件工具和環(huán)境、軟件過程、軟件需求和規(guī)約（也稱規(guī)格說明書）、軟件確認、軟件演化、軟件項目管理、基于構件的計算、形式化方法、軟件可靠性、特定系統開發(fā)。數值計算科學（Computing of Numerical value，CN）數值分析、運籌學、建模與模擬、高性能計算。社會與職業(yè)問題（Societal and professi

11、onal Problems，SP）包括：信息技術史、信息技術的社會環(huán)境、分析方法和分析工具、職業(yè)責任和道德責任、基于計算機的系統的風險和責任。,,,5.2 機器體系結構,數據儲存數據處理,,比特與觸發(fā)器,比特（bit）的概念一個比特（bit），也稱二進制數（binary digit）是兩個數字符號0和1中的任意一個，在這里0和1沒有任何數字上的意義，而僅僅是兩個符號。門電路的概念 門電路是具有實現邏輯運算的器件，其在給定兩個（

12、或一個）輸入值時，產生一個邏輯運算的輸出。有四種門電路來實現四種邏輯運算或邏輯操作，它們是“與”門、“或”門、“異或”門和“非”門。觸發(fā)器的概念觸發(fā)器是一種特殊的電路，其產生0或1的輸出值，并保持其輸出值不變，一直到另外的電路來的信號使它從當前的輸出值改變到另一個輸出值。 （例圖）,主存儲器中數據的存儲,主儲存器計算機主機（主板）上的存儲設備被稱為計算機的主儲存器 比特（bit）的存儲在計算機內往往利用觸發(fā)器的狀態(tài)來表示或

13、儲存一個比特。 字節(jié)（byte）的概念 計算機的主存儲器被分成成一個個可以管理的存儲單元，其容量用字節(jié)來代表。1字節(jié)（byte）=8比特（bit）。存儲單元的組織 存儲單元是按照地址來組織（例圖）；存儲單元內是按位來組織（例圖）。,海量數據儲存設備-1,海量存儲設備計算機的磁盤、磁帶和CD（光盤）被稱為海量儲存系統的儲存設備，海量儲存系統相對于主儲存器的優(yōu)點是非易失性、大的儲存容量和可以移動。 硬盤（例圖）工作原理：是

14、通過電磁轉換原理來存儲比特（數據）盤片結構：是一個薄的旋轉盤片，上面覆蓋一層磁性材料來存儲數據。軟盤僅有一張盤片，而硬盤有多張盤片。工作過程：是讀/寫磁頭被放在盤片的上面和/或下面，因此隨著盤片的旋轉，每個磁頭在盤片的上或下表面上的圓圈，也叫磁道（track）上來回移動。通過讀/寫磁頭的位置，不同的同心磁道被訪問。衡量磁盤系統性能的參數有：尋道時間（seek time）、旋轉延遲（rotation delay or latency

15、 time）、存取時間（access time）、傳輸速率（transfer rate）。,海量數據儲存設備-2,光盤（例圖）工作原理：是通過光電轉換原理來存儲比特（數據）盤片結構：光盤是一個直徑為12厘米的盤片，由反射材料和上面的塑料保護層組成。工作過程：通過在盤的反射層產生變化來存儲信息，這種信息能利用激光束監(jiān)視光盤旋轉時反射表面上的不規(guī)則來進行讀取。磁帶（例圖）工作原理：信息被存儲在一條覆蓋有磁性材料的薄塑料上工作過程

16、：磁帶在寫數據時是將數據轉變成數字信號（脈沖電流），通過讀/寫磁頭使磁帶的磁性發(fā)生變化，在讀取數據時，通過讀/寫磁頭感應磁帶上的磁場變化，并將其轉換成數字信號，從而獲得數據。,信息的存儲與表示,文本信息的表示文本信息通常用編碼的形式表示，文本的不同的字符（字母表、標點符號或漢字字符）被賦予唯一的比特(bit)模式。數值信息的表示用不同的數制編碼系統表示，如二進制系統是用數字0和1，進位規(guī)則是“逢二進一”，而不是傳統的十進制來表示數

17、值。圖象信息的表示位圖（bit map）技術 在位圖技術中，一幅圖像被看作是點的集合，而將每一個點叫做像素（pixel）；用1或是0，用來表示相應的像素是黑還是白，或者用1和0的組合來表示像素的不同顏色。矢量技術 一幅圖像被表示成直線和曲線的集合；用1和0的組合來表示圖形的位置，幾何圖形的參數。,二進制系統,二進制加法兩個二進制數加法同十進制加法類似，所不同的是逢二進一，而不是逢十進一。二進制的小數表示形式同十進制一

18、樣，我們小數點來將二進制數的小數和整數分開，在小數點左邊的是整數，在小數點右邊的是小數。整數的存儲 用比特模式來表示數值的方法，即數值表示系統不是唯一的，除了二進制系統，到目前有許多其它的數值表示系統，其中許多被用于數字電路的設計中。,數據壓縮,數據壓縮的定義為了數據儲存和傳輸的目的，減小數據的尺寸往往是非常有用的，用于實現減小數據量的技術被稱為數據壓縮（data compression）。數據壓縮技術實際上是研究數據壓縮的算法。

19、 圖形壓縮的格式GIF：CompuServe公司發(fā)明的圖形交換格式（Graphic Interchange Format），其通過將一個像素所賦予的顏色減少到256來實現圖像壓縮。 JPEG：由ISO的聯合圖形專家組（Joint Photographic Experts Group）制訂的，是一種彩色圖像的壓縮系統。MPEG：ISO的運動圖像專家組（Motion Picture Experts Group）制訂的，用于對視頻的

20、編碼（壓縮）。,,一種觸發(fā)器的組成,,,存儲單元的組織,,,字節(jié)的組織,,,磁盤儲存系統,,磁盤工作過程示意,,,光盤劃分的示意,,,光盤工作過程示意,,磁帶工作過程示意,,現代磁帶系統,,,,文字表示-ASCII,,,,二進制加法,,,,中央處理單元（CPU）,CPU計算機內執(zhí)行對數據的運算（如加法和減法）的電路不是直接連接到機器的主儲存器的內存單元而是一個獨立的計算機組成部件，稱為中央處理單元（Central Processing

21、 Unit，CPU） 。CPU的組成一部分是算術/邏輯單元（Arithmetic/Logic Unit，ALU），其由執(zhí)行數據處理的電路組成；另一部分是控制單元，其協調機器的活動。CPU的工作要素寄存器：為了臨時存儲信息，CPU包含類似于主儲存器的儲存單元，稱為寄存器?？偩€（bus）：為了在計算機的CPU和主內存之間傳遞比特模式，這些單元被一個稱為總線（bus）的線集合所連接。機器指令：CPU必須執(zhí)行指令才能工作，CUP能夠

22、直接識別并執(zhí)行的指令稱為機器指令。,程序儲存與執(zhí)行-1,儲存程序的概念 程序可以象數據一樣，被編碼和存儲在主內存中；控制單元設計成從內存中提取程序，解碼指令，然后執(zhí)行它們；計算機的程序能改變僅僅通過改變計算機內存的內容，這使得通用計算機成為可能。 機器語言(Machine-language) 計算機被設計來識別確定的比特模式作為確定的指令，這種同編碼系統一起的指令的集合被稱為機器語言。機器指令的編碼通常由兩部分組成：操作碼和

23、操作數（例圖）。在操作碼中的比特模式表示指令要求的基本操作，在操作數中的比特模式提供操作碼規(guī)定的操作的更詳細的細節(jié)。,程序儲存與執(zhí)行-2,程序執(zhí)行 計算機執(zhí)行存儲的程序是通過需要時將指令從內存拷貝到控制單元來實現的，一旦在控制單元，指令被解碼并執(zhí)行。指令從內存中取出的順序是同指令存放在內存中的順序是一致的，除非由一個JUMP指令重新指定?？刂茊卧ㄟ^連續(xù)執(zhí)行一個稱為機器周期（machine cycle）的算法來完成它的任務。機器

24、周期由三個步驟組成：（例圖）,程序儲存與執(zhí)行-2,同其它設備通訊主內存和CUP構成了計算機的核心，但它們要同外部設備一起工作才能完成計算機的功能。 通過控制器通訊計算機同其它設備之間的通訊是通過一個中間設備實現的，這個中間設備被稱為控制器。每種控制器處理一種特殊類型的設備的通訊，如監(jiān)視器、硬盤驅動器、光盤驅動器等（例圖）。 通訊形式 并行通訊：若干比特被同時傳輸，每一個比特通過并排的分別的線路，這種技術能迅速地傳送數據，但需

25、要相對復雜的通訊通道。串行通訊：是一次傳送一個比特。這種技術傳輸速率慢，但要求簡單的傳輸通道，因為所有的比特都通過同一根線傳輸。,,機器指令組成,,,機器周期,,外設控制器,,,5.3 軟件,操作系統算法編程語言軟件工程,,操作系統-1,操作系統的定義 操作系統（Operating System，OS）是一組控制和管理計算機軟件和硬件資源，為用戶提供便捷使用計算機的程序的集合。 操作系統的發(fā)展批處理（batch proce

26、ssing）系統：批處理指通過將任務收集起來形成批量，然后執(zhí)行它們，而不需要用戶的進一步交互（例圖） 交互處理（interactive processing）：交互處理系統允許程序在執(zhí)行時，用戶通過遠程終端或工作站，利用對話程序同計算機交換信息（例圖）。軟件的分類 軟件按其功能可以劃分為應用軟件和系統軟件。依次系統軟件又可以分成工具軟件和操作系統；操作系統又可分為內核與外殼（例圖）。,操作系統-2,操作系統的內核設備管理器：其

27、功能是根據確定的設備分配原則對設備進行分配，使設備與主機能夠并行地工作，為用戶提供良好的設備使用界面。存儲器管理器：由于多道程序共享內存資源，所以其主要任務是對存儲器進行分配、保護和擴充。進程管理器：其主要任務是對CPU的時間進行合理地分配，對CPU的運行實施有效地管理。文件管理器：有效地管理文件的存儲空間，合理地組織和管理文件系統，為文件訪問和文件保護提供更有效的方法及手段。操作系統的外殼操作系統的外殼是指操作系統同用戶之間

28、的界面。外殼的作用是提供用戶與機器之間的通訊（例圖）。窗口管理器是外殼的主要部件。,,批處理系統,,,交互處理系統,,,軟件分類,,,操作系統外殼的作用,,,算法的概念-1,算法的定義 算法是一組有序的、無二義性的、可執(zhí)行的步驟，定義了一個可以結束的過程。 算法的特征有序（ordered）：算法的有序性表現在算法中的步驟必須有一個利用次序來精心確定的結構，算法的步驟根據這個次序執(zhí)行。可執(zhí)行的（executable）：算法中的步驟

29、必須是可執(zhí)行的。無二義性（unambiguous)：無二義性指在一個算法的執(zhí)行過程中，在過程中的狀態(tài)信息必須足以唯一地、完整地確定每一步驟所執(zhí)行的活動。可終止性（terminating）：可終止性意味著算法必須定義一個可終止的過程，隨著算法的執(zhí)行，過程必須導向一個終點。,算法的概念-2,算法的表示 算法和算法的表示是有區(qū)別的，這如同故事和記載故事的書之間的區(qū)別。一個算法能用多種方式來表示。原語和偽碼可以建立一個算法的表示系統。

30、 算法的發(fā)現程序的開發(fā)有兩個活動組成，首先發(fā)現內在的算法，然后再將算法表示成程序。實際上，算法的發(fā)現是軟件開發(fā)過程中更具有挑戰(zhàn)性的工作。發(fā)現算法是找到解決問題的方法，而該問題的解答是算法所要計算的。,,編程語言-1,編程語言的作用 編程語言允許我們以既方便人類的理解，又便于轉換成機器語言指令的形式來表示算法。編程語言在程序開發(fā)過程中將人們從處理寄存器、內存地址和機器周期等錯綜復雜的細節(jié)中解脫出來，從而能將注意力集中在要解決的問

31、題的本質上。 編程語言的分類從時間上劃分 第一代：機器語言第二代：匯編語言第三代：結構化語言第四代：…從思維邏輯劃分（例圖）,編程語言-2,傳統編程概念在傳統編程語言中，語句是程序的基本組成。一般，語句劃分為三大類：聲明語句、命令語句和注釋語句。聲明語句聲明語句是定義用戶化的術語，這些術語將要在程序中使用，如引用數據項的名稱。命令語句命令語句描述算法中的步驟。其包括賦值語句、控制語句和過程調用語句。控制語句一般包

32、括：分支語句，如if-then-else語句，switch-case語句；循環(huán)語句，如for語句、while語句等。注釋語句注釋語句通過用人們熟悉的形式來解釋程序深奧的特性來增強程序的可讀性。,編程語言-3,語言執(zhí)行語言執(zhí)行是將用高級語言所寫的程序轉換成機器可以執(zhí)行的形式。翻譯過程將程序從一種語言轉換成另一種語言的過程被稱為翻譯（translation）。程序在其原始的形式就源程序（source program）；轉換后的版本

33、叫目標程序（object program）。翻譯過程由三個活動組成：詞法分析、語法分析和代碼生成，分別由翻譯器中稱為詞法分析程序、語法分析程序和代碼生成器來完成（例圖）。,,程序分類,,,翻譯過程,,,軟件工程-1,軟件工程概念 軟件工程涉及軟件生產的各個方面，從早期的系統定義到軟件投入使用后的系統維護，之所以稱之為軟件工程，是因為我們將軟件的開發(fā)看作一個工程過程。 工程領域是一個已經非常成熟的領域，軟件工程初衷就是要借鑒工程領域

34、的成熟管理技術來管理復雜的大型軟件系統的開發(fā)過程。軟件工程與傳統工程的區(qū)別構件的重用性系統的容錯性質量的可度量性,軟件工程-2,軟件工程的基本思想用科學的知識和技術原理來定義、開發(fā)、維護軟件；用工程科學的觀點進行費用估算、制定進度、制定計劃和方案；用管理科學的方法和原理進行生產的管理；用數學的方法建立軟件開發(fā)過程中的各種模型和算法。軟件工程的目標付出較低開發(fā)成本，達到要求的功能，取得較好的性能；按時完成開發(fā)任務，及時交付使

35、用；軟件易于移植，可靠性高，維修費用低。,軟件工程-3,軟件工程的研究內容研究內容包括開發(fā)技術和管理技術兩個方面。開發(fā)技術主要研究軟件開發(fā)方法、開發(fā)過程、開發(fā)工具和開發(fā)環(huán)境。開發(fā)管理主要研究軟件管理、軟件經濟和軟件心理。軟件工程所解決的問題包括軟件的費用、可靠性、可維護性、軟件生產效率和軟件的重用問題。軟件工程的實施內容軟件工程規(guī)定了獲取、供應、開發(fā)、操作和維護軟件時，要實施的過程、活動和任務。,軟件工程-4,軟件生命周期軟

36、件生命周期（例圖）表示了這樣一個事實，即一旦軟件被開發(fā)，它就進入使用和修改的循環(huán)，在軟件生命的剩余部分一直繼續(xù)。 軟件開發(fā)工作內容（例圖）分析：軟件生命周期的開發(fā)階段是從分析開始。分析的主要目的是確定計劃的系統的用戶的需求。設計：分析關注的是系統應該做什么，設計關注的是系統將如何完成這些目標。在設計中，軟件系統的結構被確定。實施：實施包括實際地編寫程序，建立數據文件和開發(fā)數據庫。測試：測試是同實施緊密相連的，其目的是盡量減少軟件

37、中存在的錯誤，使軟件能正常、高效地工作。,,軟件生命周期,,,軟件開發(fā)階段的工作內容,,,,5.4 數據組織,數據結構文件結構數據庫結構,,數據結構-1,數據結構的概念數據結構研究在計算機內存中的數據組織數據結構分為靜態(tài)的數據結構和動態(tài)的數據結構，前者的尺寸和形態(tài)是固定的，而后者的尺寸和形態(tài)是不固定的。靜態(tài)數據結構-數組數組是在內存中將數據以稱作同類數組的矩形排列來存儲的，其占據了內存中連續(xù)的、大小不變的內存單元。 一維數

38、組是將數組中的每個元素利用它在數組中的位置來引用比較方便，這個位置被稱為叫索引。（例圖）兩維以上數組是被轉換成，按一維數組的形式來存儲的。根據轉換的方式不同，分為以行為主序或以列為主序。（例圖）,數據結構-2,動態(tài)數據結構-表連續(xù)表：將整個表存儲在一個連續(xù)地址的單個內存區(qū)域（圖例），連續(xù)表因為簡單而方便，但有若干缺點，如插入和刪除都不方便。鏈接表：將數據存儲在散布的、用指針聯起來的若干個小的內存單元區(qū)域（例圖）。動態(tài)數據結構-堆

39、棧堆棧是一個特殊的表，其所有數據的插入和刪除都是在結構的尾部。這種限制的結構是最后進入的元素總是最先移出的元素，這導致了堆棧被稱為后進先出（Last-In，First-Out，LIFO）結構。動態(tài)數據結構-隊列隊列是一種特殊的表，在其中所有的數據插入在一端，而所有的數據刪除在另一端。隊列概念的實質是這樣一個系統，對象被處理按照它們到達的次序，即先進先出（First-In，First-Out）。,,一維數組的存儲,,,兩維數組的存儲

40、（行為主序）,,,連續(xù)表數據結構,,,鏈接表數據結構,,,文件結構-1,文件的概念信息以大的單元存儲在海量儲存系統被稱為文件（files）。 海量儲存設備的物理特性決定了這些文件的存儲和提取是以多個字節(jié)單位進行的。 物理記錄（physical record）遵守一個儲存設備的物理特性的數據塊叫做物理記錄，儲存在海量儲存中的文件典型的是由許多物理記錄組成。邏輯記錄（logical record）自然產生的數據塊叫做邏輯記錄邏

41、輯記錄的尺寸通常不匹配海量儲存設備決定的物理記錄，結果是若干個邏輯記錄放置在單個物理記錄中，或者一個邏輯記錄被分割到兩個或多個物理記錄之間（例圖）。緩沖區(qū)（buffer） 緩沖區(qū)是主內存中開辟一個專門的區(qū)域，其大得足以容納若干個物理記錄，用來作為物理記錄與邏輯記錄重新編組的地方。,文件結構-2,順序文件（Sequential Files）順序文件是這樣的一種文件，對其的訪問是從頭到尾，仿佛文件中的信息被排列成一行。順序文件的例

42、子有音頻文件、視頻文件、包含程序的文件、以及包含文本的文件。 文本文件（text files）文本文件，它是一個順序文件，它的每一個記錄由單個的“可打印的”字符組成?！翱纱蛴〉摹北硎疚覀儾粌H包括文字、字母、數字和標點符號，而且包括諸如回車、進行等控制代碼。索引文件（indexed file） 由一個條目表組成，表中的每個條目包含一個記錄的確定特性（也許是一個關鍵域值）和該記錄的位置。這個索引文件通常存儲在同文件相同的海量儲存

43、設備上。為了從文件中讀取一條記錄，索引被首先傳遞到主內存，用于搜索適當的條目。,,物理記錄與邏輯記錄,,,,數據庫結構-1,數據庫的概念數據庫主題是數據結構和文件結構的綜合?，F代數據庫應用兩個方面的技術來獲得一個單獨的、海量的數據系統，其能表現出服務許多應用的多種數據組織。 數據庫結構與文件結構的比較文件結構是一維儲存系統，在系統中，信息是從一個單獨的視角來表示的。 數據庫術語描述多維數據的集合，在這個集合中，數據之間存在著聯系

44、，因此信息能從不同的視角來訪問。 數據庫的優(yōu)點數據集成、共享、統一管理（例圖）提高數據的一致性、減少數據的冗余。數據庫的缺點 對敏感數據的訪問控制問題如數據的收集權限問題、數據濫用問題等等,數據庫結構-2,數據庫系統實現的分層方法為了隱藏數據庫實現的復雜性，數據庫系統是根據抽象的層次來構建的（例圖）。應用軟件對數據庫使用者的數據映像是由應用軟件產生的，應用軟件利用交互的方式和應用領域中的術語同用戶通訊。數據庫管理系統