某島

… : "…アッカリ~ン . .. . " .. .
November 29, 2010

哈爾濱工業大學《計算機導論》課程複習提綱 …

任課教師:戰德臣,聶蘭順
1.1 基本概念清單 1. 計算思維

第 1 章 引論

計算思維是計算機的思維和利用計算機的思維的統稱,計算機的思維是關於「計算機是 如何工作的? 計算機的功能是如何越來越強大的?」的思維,利用計算機的思維是關於「現 實世界的各種事物如何利用計算機來進行控制和處理?」的思維。 2. 集成電路
集成電路是指將基本的元器件封裝與集成在一起的晶元,它實現了數量眾多元器件的封 裝與集成,可有效地縮小電子電路的體積、提高電子電路的可靠性。 3. 主頻與字長
主頻是指 CPU 每秒鐘所能完成操作的次數,以 MHz 或 GHz 為單位來度量, 1GHz=210MHz。字長是指 CPU 每一次操作所能處理數據的位數。 4. 典型的計算機術語
馮.諾依曼計算機、巨型機、小型機、微型機、個人計算機、兼容機等; 微處理器、硬體、軟體、輸入設備、輸出設備、磁芯/磁鼓、內存與外存 操作系統、計算機網路、區域網、廣域網、網際網路、WWW
5. 典型的計算機語言與典型的操作系統 典型的計算機語言:FORTRAN、COBOL、BASIC、Pascal、C、C++、Visual C++、Visual
BASIC、Java。 典型的操作系統:Unix、MS DOS、Netware、Windows、Liunx。
1.2 基本思想與基本過程 1. 自動計算首先要解決的幾個問題?
自動計算首先要解決的幾個問題是數的表示及其存儲、計算規則及執行和數及規則的輸 入輸出。
2. 算盤與機械計算機的異同點? 典型的機械計算機及其思想和意義; 算盤與機械計算機的異同點是:相同點是:二者都能實現數的表示及存儲,也都有一套
計算規則;差異是:前者是人執行計算規則,後者是機械自動執行計算規則。 典型的機械計算機用純機械裝置來代替人的思維(規則及執行)和記憶(存儲),開闢了自
動計算的道路。 3. 輸入手段的變遷;輸出手段的變遷;存儲手段的變遷。
輸入手段的變遷:打孔卡鍵盤滑鼠掃描儀數碼產品;
輸出手段的變遷:陰極射線管向量式模擬顯示器字元發生器基於內存的數字光 柵掃描顯示器
存儲手段的變遷:磁芯、磁鼓半導體存儲器(內存)軟盤硬碟光碟 4. 從元器件看計算機的發展過程與特點
電子管(真空二極體)晶體管集成電路大規模集成電路 體積越來越小、可靠性越來越高、規模越來越大、性能越來越高。

5. 微處理器的發展過程;微處理器的性能指標。 字長:8 位16 位32 位64 位 主頻:幾 MHz幾十 MHZ幾百 MHz幾 GHz幾十 GHz 晶體管數量:幾萬幾十萬幾百萬幾千萬幾億顆 功能:微處理器微處理器+協處理器(浮點運算)微處理器+多媒體處理器微處理器
+3D 多媒體處理器多微處理器 6. Unix、DOS、Netware、Windows、Linux 等操作系統引發的計算技術的變化
Unix—-操作系統,硬體功能的擴展 DOS—-微機操作系統,個人計算機的普及 NetWare—-網路操作系統,計算機網路應用的普及 Windows—-圖形界面操作系統,多媒體應用的普及 Linux—-開放源代碼運動
7.計算機網路的發展過程與特點;分組交換網、乙太網、互聯網等引發的計算技術的變化 遠距離控制的實現分組交換技術與廣域網乙太網技術與區域網個人微機的網卡
WWW 與 Internet。 區域網(LAN)是指在一個有限地理範圍內的各種計算機及外部設備通過高速傳輸媒介
連接起來的通信網路,可以包含一個或多個子網,通常局限在幾千米的範圍之內。典型的局 域網為乙太網(Ethernet)。
廣域網(WAN)是指由相距較遠的計算機通過公共通信線路互聯而成的網路,範圍可覆蓋 整個城市、國家,甚至整個世界,廣域網有時也稱為遠程網,通常除了計算機設備以外,還 要使用電信部門提供的傳輸裝置和媒介進行連接。常見的廣域網如。
互聯網(internet)是通過專用設備而連接在一起的若干個網路的集合。通過專用互聯設 備,可以進行區域網與區域網之間的互聯、區域網與廣域網之間的互聯以及若干區域網通過 廣域網的互聯。
網際網路(Internet), 又稱國際互聯網,是世界最大的互聯網,是由廣域網連接的區域網 的最大集合。Internet不是一種新的物理網路,而是把多個物理網路互聯起來的一種方法和 使用網路的一套規則。
8.典型的計算機應用—利用計算機的思維 科學計算:數值計算,如求解複雜高階方程、工程分析與模擬模擬等 CAx:如過程式控制制、數字控制、機器人 信息管理:非數值計算,如資料庫、管理與協同等 人工智慧:智能化,使機器具有人的智能 嵌入式系統:使各種電器內嵌入計算機晶元接受自動控制
9.典型的計算機發展趨勢: 高性能計算–無所不能的思維; 移動計算–無處不在的思維; 服務計算(Software As A Service)–提供軟體轉為提供服務,未來互聯網的思維; 生物計算–生物器件與生物晶元及生物信息處理;
智能計算–智能化的思維; 全球信息化–信息技術與信息系統等。

哈爾濱工業大學《計算機導論》課程複習提綱 任課教師:戰德臣,聶蘭順
2.1 基本概念清單 1. 語義符號化
第2章 計算原理
語義符號化是指將現實世界的語義用符號表達,進而進行基於符號的計算的一種思維, 將符號賦予不同語義,則能計算不同的問題。 2. 基本邏輯運算
基本邏輯運算有「與」運算、「或」運算、「非」運算、「異或」運算和「同或」運算等。 用1表示「真」,0表示「假」,則: 「與」運算為「有0則0,全1則1」(語義是:參與運算的兩個命題如有一個為假,
則結果為假;否則為真。下略)。 「或」運算為「有1則1,全0則0」;「非」運算為「0 的非則1,1的非則0」;「異或」運算為「相同則0,不同則1」。 3. 進位制、編碼、ASCII 碼、BCD 碼
進位制是用數碼和帶有權值的數位來表示有大小關係的數值型信息的表示方法。常用的 進位製為十進位、二進位和十六進位。
編碼是以若干位數碼或符號的不同組合來表示非數值性信息的方法,編碼是人為地將若 干位數碼或符號的每一種組合均指定一種唯一的含義。編碼的三個特徵是唯一性、公共性和 易於記憶/便於識別性。常用的編碼有 ASCII 碼、BCD 碼等。
ASCII碼是計算機領域普遍應用的英文字母符號的編碼方法,是用7位0和1的不同組 合來表示 10 個數字、26 個英文大寫字母、26 個英文小寫字母及其一些特殊符號的編碼方法, 是信息交換的標準編碼。
BCD 碼,二-十進位編碼,是用4位0和1的不同組合,按照與進位制保持一致的關 系,來表示 10 個十進位數字的方法。 4. 基本門電路
與門電路:是實現邏輯與運算的集成電路,即:只有當兩個輸入端為高電平(1)時,則 輸出端為高電平(1);否則,輸出端為低電平(0)。
或門電路:是實現邏輯或運算的集成電路,即:只有當兩個輸入端為低電平(0)時,則 輸出端為低電平(0);否則,輸出端為高電平(1)。
非門電路:是實現邏輯非運算的集成電路,即:當輸入端為高電平(1)時,則輸出端為 低電平(0);輸入端為低電平(0)時,則輸出端為高電平(1)。
異或門電路:是實現邏輯異或運算的集成電路,即:當兩個輸入端同為高電平(1)或同 為低電平(0)時,則輸出端為低電平(0);否則,輸出端為高電平(1)。 5. 存儲單元:存儲地址和存儲內容
存儲器由若干存儲單元組成,每一存儲單元存儲有一定字長的存儲內容,且有一唯一的 地址,可按存儲單元的地址讀寫存儲單元的內容。存儲地址和存儲內容都可用0和1編碼表 示,例如一 16 位的存儲地址,可表示 1-216 個存儲單元,而一 8 位字長的存儲內容可表示 1-28 大小的存儲內容。存儲單元好比賓館的房間,而存儲地址則是房間編號,存儲內容則是 住在房間的人員,字長好比房間的床位數,房間編號不變,而房間內的人員可以不斷變化。 即存儲單元的內容可變化,而存儲單元的地址通常是確定的。
2-1
哈爾濱工業大學《計算機導論》課程複習提綱 任課教師:戰德臣,聶蘭順
6. 機器指令 機器指令是 CPU 可以直接分析並執行的指令,一般由 0 和1的編碼表示。通常情況下,
一條指令被區分為兩部分:操作碼和地址碼;操作碼告訴 CPU 所要進行的操作類別,如取 數、存數、計算等,而地址碼告訴 CPU 所要操作的數據在哪裡。機器指令有不同的操作數 讀取機制,詳細內容可學習彙編語言課程。
用機器指令編寫的程序即機器語言程序,是可以被 CPU 直接解釋和執行的。 7. 馮.諾依曼計算機:五大部件結構及其功能
馮.諾依曼計算機的五大基本部件:運算器、控制器、存儲器、輸入設備和輸出設備。 其中運算器負責執行邏輯運算和算術運算,控制器負責讀取指令、分析指令並執行指令,以 調度運算器進行計算,存儲器負責存儲數據和指令,輸入設備負責將程序和指令輸入到計算 機中,輸出設備是將計算機處理結果顯示或列印出來。
8. 微處理器、CPU、存儲器、主存/內存、輸入、輸出 將運算器和控制器封裝集成在一塊晶元上,該晶元稱為中央處理單元(CPU:Central
Process Unit),又稱為微處理器。 廣義存儲器是指內存和外存的統稱,內存通常是指使用半導體材料製作的、通常按地址
訪問的、由若干存儲單元構成的存儲晶元,具有速度快、容量有限、和 CPU 按存儲字/存儲 單元交換信息、電信息易失性。由於其電信息易失性,適合於臨時存儲,又稱為主存,在操 作系統、應用軟體中等又被作為緩存使用。外存是指用磁性材料製作的、通常連續順序存儲 信息並具有信息存儲永久性的存儲器,適合於永久存儲設備。
輸入是指將外界信息輸入到計算機內,而輸出則是指將計算機內的信息傳送到外界(顯 示或列印)。
9. 現代計算機系統的構成 現代計算機系統由硬體和軟體構成。硬體由主機和外部設備構成;主機由主電路板(簡稱
主板)、介面電路板(簡稱介面卡)、電源及軟盤驅動器(軟盤和軟盤驅動器是分離的)、硬碟(含 硬碟驅動器,硬碟和硬碟驅動器是做在一起的)等部件構成。主板由 CPU、內存、匯流排等部 件構成。匯流排是主板上連接各部件的符合標準的電路連線和插槽,通常包括數據匯流排、控制 匯流排和地址匯流排三部分,外部設備可通過使其介面卡插入主板的插槽而與 CPU 和內存等相 連接。現代計算機也有將硬碟驅動電路直接做在主板上,此時硬碟可直接連接到匯流排上即可。 外部設備由顯示器、鍵盤、滑鼠以及硬碟、軟盤驅動器等部件構成。所有部件通過匯流排與主 電路板相連接,也即和 CPU 與內存相連接.
10. 硬體、軟體;系統軟體、應用軟體;ROM、RAM; 硬體:硬體是指構成計算機的物理實體,是指看得見摸得著的實物部分。 軟體:軟體則是控制硬體按指定要求進行工作的由有序命令構成的程序集合。現代軟體
通常包括可執行的程序文件及若干附件的程序要使用的數據文件等。 系統軟體是用於對計算機進行管理、控制、維護,或者編輯、製作、加工用戶程序的一
類軟體。常見系統軟體包括操作系統、xx 語言編譯器及其程序開發環境、資料庫管理系統 軟體及各類管理工具軟體等。
應用軟體則是用於解決各種實際問題、進行業務工作的軟體。
ROM 和 RAM 統稱內存,但二者有些差別。ROM:只讀存儲器 Read Only Memory,ROM 採用特殊工藝製作,存儲信息不會丟失(即只讀不寫,信息永久不變),其他特性同內存,通 常容量特別小,僅能存放少量的信息。一般情況,ROM 存放機器接通電源即開機時所必須 的一些指令代碼。
2-2
哈爾濱工業大學《計算機導論》課程複習提綱 任課教師:戰德臣,聶蘭順
RAM:隨機訪問存儲器 Random Access Memory,即常說的內存,通常是指使用半導體 材料製作的、按地址訪問的、由若干存儲單元構成的存儲晶元,具有速度快、容量有限、和 CPU 按存儲字/存儲單元交換信息、電信息易失性。一般情況下,作為與 CPU 交換信息的部 件而存在:所有的程序和數據,如需要 CPU 處理,則其首先要裝載到內存中。
11. 文件、目錄、FAT 文件是操作系統管理信息的基本單位。用戶不必關心文件在磁碟上是如何存取的,而只
需關注文件名及文件內容即可,操作系統通過文件名管理存儲在磁碟上的各種文件及其信 息。
扇區是磁碟的基本操作單位。文件分配表(FAT)是磁碟上記錄文件存儲的簇塊之間銜接 關係的信息區域。所謂簇塊是指倍數且連續的扇區構成的存儲區域。
目錄是磁碟上記錄文件屬性、文件第一簇塊號等相關信息的由文件名構成的文件清單。 12. 操作系統及其主要功能
操作系統(Operating System)是控制和管理計算機系統各種資源(硬體資源、軟體資源和 信息資源)、合理組織計算機系統工作流程、提供用戶與計算機之間介面以解釋用戶對機器 的各種操作需求並完成這些操作的一組程序集合,是最基本、最重要的系統軟體。
操作系統的主要功能包括:處理機管理、存儲管理、文件管理、設備管理和程序與作業 管理。
13. 演算法、程序與計算機語言 演算法是為解決一個特定問題而採取的確定的有限的步驟。 程序是計算機能夠理解與執行的解決問題的步驟,是用計算機語言描述的解決問題的算
法。
計算機語言是人們設計的專用於人與計算機交互、進而計算機能夠自動識別的語言,是
書寫計算機程序的語言,是問題求解步驟的書寫規範、語法規則、相關標準等的集合。 14.指令系統、機器語言、彙編語言、高級語言、源程序、彙編程序、編譯程序
指令系統是 CPU 可以執行的由二進位編碼的指令集合。 機器語言是用機器指令編寫程序的語言。 彙編語言是用助記符號編寫程序的語言。 高級語言是用類自然語言的語句為單位編寫程序的語言。 源程序是用某一種語言編寫的程序。 彙編程序是將用彙編語言編寫的源程序轉換成機器語言程序的程序。 編譯程序是將用高級語言編寫的源程序翻譯成機器語言程序的程序。
15.漢字內碼與漢字外碼 漢字外碼是用鍵盤可識別符號組合來編碼每一個漢字的編碼,是用來進行漢字輸入的編
碼。漢字內碼是用兩位元組且最高位均為 1 的 0,1 型編碼來編碼每一個漢字的編碼,是漢字在 計算機內部存儲所使用的編碼。 16. (圖像/視頻/音頻的)採樣、量化與編碼;模擬信號與數字信號
所謂模擬信號是指隨時間連續不間斷產生的信號。而數字信號則是離散時間點產生的離 散數字信號。
模擬信號,需經採樣、量化和編碼形成數字信號後進行數字信號處理。所謂採樣是指按 一定的採樣頻率對連續信號做時間上的離散化,即對連續信號隔一定周期獲取一個信號點的 過程。量化是將所採集的信號點的數值區分成不同位數的離散數值的過程。編碼則是將採集 到的離散時間點的信號的離散數值按一定編碼規則編碼並存儲的過程。
2-3
哈爾濱工業大學《計算機導論》課程複習提綱 任課教師:戰德臣,聶蘭順
2.2 基本思想與基本過程 1. 語義符號化思想
語義符號化是指將現實世界的語義用符號表達,進而進行基於符號的計算的一種思維, 將符號賦予不同語義,則能計算不同的問題。
例如,《易經》將現實世界分為陰和陽,陰即0,陽即1,進一步用陰陽的組合與變化, 即0,1 的組合與變化來反映大千世界的變化規律,例如八卦,用三位0,1 碼的組合,每一種 組合抽象於一種自然現象,如「乾卦」抽象於天,表達具有天的特性的事物,則天為乾卦的 本體語義,而如果將乾卦放在「家庭空間」中,則表徵「父」,而如果放在「身體空間」中, 則表徵「首」,因此,符號可以被綁定不同的語義。由此符號化,則二十四節氣的演變、生 命規律的演變等都可以用 0 和1,即陰和陽的變化來反映了。 2. 計算的實現:電子電路級的實現,即基於 0 和 1 的電子實現;
現實世界的各種信息可表示成0和1,可基於0和1進行算術運算和邏輯運算,在實現 過程中,能夠表示0和1的元器件有很多,典型的如繼電器開關:開(表示1)、關(表示0), 電路中的電信號:低電平(表示0)、高電平(表示1),二極體、三極體等不僅實現表示,還 實現控制。
利用基本元器件,如二極體、三極體可封裝集成後製造「與」門、「或」門、「非」門等 門電路,並能確認這些基本門電路的正確性。
再將「與」門、「或」門、「非」門等門電路進行組合,形成更為複雜的組合電路。布爾 代數與數字邏輯是判斷組合電路正確性的工具。
微處理器、內存儲器等就是不斷組合已有的門電路、組合電路,並將其集成在一塊晶元 上所形成的。
3. 計算的實現:程序級的實現,即圖靈機 圖靈認為:所謂計算就是計算者(人或機器)對一條兩端可無限延長的紙帶上的一串 0 或
1,執行指令一步一步地改變紙帶上的 0 或 1,經過有限步驟最後得到一個滿足預先規定的 符號串的變換過程。基本思想:「基本動作」就是機器將輸入轉變為輸出,「指令」是對基本 動作的控制,「程序」是有先後次序關係的指令串即控制規則,「自動執行」是依控制規則自 動將輸入處理為輸出,「輸入/輸出」及「程序」均用符號表達及最終由 0 和 1 表達。
上述思想可用形式化模型表達。圖靈機是一個七元組 P = (Q, , , , q0, B, F ),其中 Q 是有窮狀態集,是有窮輸入字符集, 是有窮輸入帶字符集,=是狀 態轉移函數,表示:在當前狀態 q 下,將字元 X 轉換為字元 Y,同時,控制紙帶向左、向右 移動或不動,然後將狀態改為p。q0是初始狀態,B 是空格符,F 是有窮終結狀態集。
圖靈機模型被認為是計算機的基本理論模型,即計算機是使用相應的程序來完成任何設 定好的任務,是一種離散的、有窮的、構造性的問題求解思路,一個問題的求解可以通過構 造其圖靈機(即程序)來解決。圖靈認為:凡是能用演算法方法解決的問題也一定能用圖靈機解 決; 凡是圖靈機解決不了的問題任何演算法也解決不了,此即圖靈可計算性問題。
4. 馮.諾依曼計算機和存儲程序思想 馮.諾依曼計算機的五大基本部件:運算器、控制器、存儲器、輸入設備和輸出設備。
其中運算器負責執行邏輯運算和算術運算,控制器負責讀取指令、分析指令並執行指令,以 調度運算器進行計算,存儲器負責存儲數據和指令,輸入設備負責將程序和指令輸入到計算 機中,輸出設備是將計算機處理結果顯示或列印出來。
馮.諾依曼計算機的基本思想是存儲程序的思想,即程序在執行之前事先存儲在存儲器 中,這樣機器就可連續地從存儲器中讀取指令執行指令,實現連續自動的計算。
2-4
哈爾濱工業大學《計算機導論》課程複習提綱 任課教師:戰德臣,聶蘭順
馮.諾依曼計算機又分為以運算器為中心的結構和以存儲器為中心的結構。以運算器為 中心的結構,則使輸入輸出與計算都要經過運算器,而以存儲器為中心的結構,則使輸入輸 出獨立於運算器,因此後者的結構可使程序/數據的輸入輸出與程序中的各種計算相互獨立, 從而做到並行執行,即一方面輸入輸出程序和數據的,另一方面可同時執行另外的程序進行 計算。
5. 計算機硬體執行過程;計算機系統執行過程 計算機硬體執行過程:機器提供了其可以執行的指令的集合,這些指令被稱為機器指令;
用機器指令編寫問題求解的程序,即機器指令序列;將機器指令序列及相關的數據存儲於存 儲器中;啟動控制器工作;控制器發送第 1 條指令的存儲地址給存儲器;存儲器取出指令返 給控制器;控制器分析指令並執行指令:發送操作數 x 所在地址給存儲器;存儲器取出操作 數 x 給運算器;控制器發送下一指令的存儲地址給存儲器;存儲器取出指令返給控制器;控 制器分析指令並執行指令:發送操作數y所在地址給存儲器;存儲器取出操作數y給運算器; 控制器執行指令:通知運算器進行運算,如此循環往複,一條接一條地取指令、分析指令、 執行指令,直到程序終止!
計算機系統執行過程:計算機初始啟動指令是放置在 ROM 中的,而大量的程序是放置 在磁碟上的。當計算機電源接通時,CPU 首先從 ROM 中讀取啟動指令,按照啟動指令,到 磁碟上尋找操作系統,當找到操作系統後,則將其從磁碟上裝載到內存中,CPU 就可從內 存中讀取操作系統的程序指令並執行之。當操作系統裝載成功後,CPU 就處於操作系統的 監控之下。當用戶在操作系統下運行某一應用程序時,操作系統會到相應磁碟位置尋找應用 程序文件,如找到則將其裝載到內存,同時使 CPU 執行該應用程序,應用程序進行工作, 當應用程序執行完畢,則操作系統會使釋放應用程序所佔用的內存,同時收回 CPU 的控制 權,如此執行。
6. 現代計算機的存儲體系 現代計算機的存儲體系由內存和外存等構成。內存是用半導體材料製作,具有速度較快、
容量有限、電信息易失性等特點;外存是用磁性材料製作,具有速度較慢、容量可無限擴展、 信息永久保存等特點。
現代計算機通常將內存和外存整合成一個存儲體系:使使用者感到容量象外存的容量, 而速度象內存的速度,內存與外存的調度和處理由操作系統來實現而對使用者透明化;CPU 和內存按存儲字/存儲單元交換信息,而外存不與 CPU 直接交換信息,外存的信息首先按塊 (Block, 也有稱頁 Page,一頁約 512 位元組或其倍數)裝載到內存,然後再由 CPU 訪問.即因 外存速度慢,則以批量交換信息,內存速度快,則以存儲單元交換信息,以批量換速度,行 程存儲體系。
內存又分為 ROM(只讀存儲器 Read Only Memory)和 RAM(隨機訪問存儲器 Random Access Memory)。ROM採用特殊工藝製作,存儲信息不會丟失,通常存放機器啟動時所必 須的一些指令代碼。RAM 即前述的內存。
磁碟又分為硬碟(Hard Disk)和軟盤(Floppy Disk)。所謂硬碟通常是固定在計算機裡面的、 具有大容量高速度的磁碟,而軟盤通常是指可靈活更換碟片的磁碟,軟盤雖然容量小,但因 可更換碟片,相當於具有無限容量。 7. 操作系統管理磁碟及文件的基本思想
磁碟被劃分成一個個扇區,以扇區或扇區的倍數(被稱為簇塊)為單位和內存交換信息。 文件也被劃分成一個個扇區或簇塊存儲於磁碟上,為記住構成文件的每一簇塊之間的先後順 序聯繫,操作系統在磁碟上建立了一張表,即 FAT 表(文件分配表)。磁碟上有多少個簇塊,
2-5
哈爾濱工業大學《計算機導論》課程複習提綱 任課教師:戰德臣,聶蘭順
FAT 表就有多少項,FAT 表項的編號與磁碟簇塊編號有一一對應的關係。FAT 表項的內容指 出了該簇塊的下一簇塊的編號。例如 13 號表項內容為 24 說明 13 號簇塊後面是 24 號簇塊, 而由 24 號表項內容 26 可知,24 號簇塊後面是 26 號簇塊,依此類推,一直到表項為 End 的 簇塊為止。這樣構成文件的各簇塊就由 FAT 表形成一個簇塊指針鏈,前一個簇塊指向後一 個簇塊,一直到結束為止。
那麼文件簇塊指針鏈的第一個簇塊編號存在哪呢?它與文件的文件名、文件的屬性等信 息一起存放於磁碟的目錄中。
因此,每張磁碟在使用之前要進行格式化。所謂格式化就是要給磁碟劃分扇區、建立
FAT 表以及建立目錄表(此目錄稱為根目錄),以便於文件存儲。磁碟目錄、文件分配表是磁 盤上的重要數據保存地。 8. 操作系統管理外部設備的基本思想
操作系統管理外部設備像管理文件一樣,使用戶只需關心與設備的數據交換即可,而不 必關心設備的具體控制細節。
主板上是通過匯流排連接的 CPU、內存等。介面電路板與外部設備連接,同時通過插入 主板的匯流排插槽與 CPU 相連接。介面電路板也即所謂的 IO 控制器。操作系統通過設備無關 管理層、設備相關管理層的分層管理調用設備驅動程序。設備驅動程序進一步調用設備自身 的操作指令,控制設備的光機電動作。
其中,設備無關管理層:面嚮應用程序,處理外部設備就像處理文件一樣,以打開、關 閉、讀寫數據等通用的方式描述對設備的操作;
設備相關管理層:面向設備驅動程序,它將前述的設備無關命令翻譯成設備驅動程序所 能識別的命令,並調用設備驅動程序完成對設備的控制操作。
設備驅動程序層:負責將操作系統對設備的操作指令轉換成設備操作指令。
設備操作指令層:設備自身的驅動光機電動作的指令。 9. 操作系統的啟動與關閉過程
操作系統一般由以下幾個部分組成:引導程序、基本輸入輸出程序、磁碟文件管理程序、 命令監控與解釋執行程序和若干命令程序文件構成。每次機器接通電源後,首先由計算機的 ROM 裡面讀取指令開始,然後到磁碟中找引導程序,由引導程序引導載入操作系統的基本 輸入輸出程序。所說載入是指將其裝入內存中處於可用狀態,當引導程序完成基本輸入輸出 程序的載入後即執行之,控制權由此交給了基本輸入輸出程序。基本輸入輸出程序由兩部分 組成。一部分固化在 ROM 中,稱為 ROM BIOS,它包括常用輸入/輸出設備(顯示器、鍵盤、 磁碟驅動器、行式印表機、非同步通信適配器、日期和時間等)的驅動程序,是控制硬體工作 的程序。另一部分則存放在磁碟上,是 ROM BIOS 的擴充。執行基本輸入/輸出程序即是在 內存中設置好各種設備的驅動程序,進行各種初始化工作,然後讀取磁碟文件管理程序,建 立操作系統的運行環境,隨後將命令監控與解釋執行程序載入內存,並執行命令監控與解釋 執行器,控制權移交給命令解釋器。命令解釋器是用戶和操作系統的直接界面。它負責監控、 接收、識別並執行用戶通過鍵盤或滑鼠輸入的命令並執行之。
操作系統啟動通常完成以下工作:初始化系統環境、載入設備驅動程序、載入服務程序 等、載入系統程序, 如程序管理器/命令解釋器等。
操作系統關閉通常完成以下工作:保存用戶設置、關閉服務程序、通知其他聯機用戶、 保存系統運行狀態、將內存內容寫回外存中、正確關閉相關設備等。 10. 計算機語言的發展軌跡
基本軌跡:機器語言彙編語言高級語言面向對象的程序設計語言可視化構造 2-6
哈爾濱工業大學《計算機導論》課程複習提綱 任課教師:戰德臣,聶蘭順
語言。 CPU 可以執行二進位編碼的機器指令,CPU 提供的機器指令集合被稱為指令系統。用
機器指令編寫程序的語言稱為機器語言。所有程序均需轉換成機器語言程序,計算機才能夠 執行。由於二進位編碼的機器指令難於識認和書寫的不便性,人們提出了用助記符號編寫程 序並進行自動翻譯的思想。用助記符號編寫程序的語言被稱為彙編語言。將用彙編語言編寫 的程序自動轉換成機器語言的程序被稱為彙編程序。由於彙編語言和機器指令的密切相關 性,程序編寫仍相當複雜。於是,人們設計了各種高級語言。高級語言的表示形式近似於人
們的自然語言,以語句為單位編寫程序,一條語句的功能往往相當於十幾條甚至上百條彙編 語言的指令,且無需考慮機器指令系統。將用高級語言編寫的程序翻譯成機器語言程序的程 序被稱為編譯程序。 進一步,人們又提出了面向對象的程序設計語言,使程序員可以構造 積木塊,然後就可以用積木塊編寫程序,進一步又提出了可視化的構造語言,像堆積木一樣 編寫程序。如此程序編寫越來越容易,而編寫的程序規模也越來越大! 11.漢字在計算機中的處理過程
漢字首先通過漢字外碼進行輸入,漢字外碼是用鍵盤可識別符號組合來編碼每一個漢字 的編碼。漢字在計算機內部採用漢字內碼進行存儲,漢字內碼是用兩位元組 0,1 編碼每一個漢 字的編碼。漢字的輸出是通過漢字字形碼,漢字字形碼是用點陣形式表示漢字形狀的編碼, 漢字點陣中有筆畫的點為 1 而無筆畫的點為 0,可構成漢字的字形信息。由外碼輸入、轉換 成內碼存儲、再映射到漢字字形碼進行輸出。
12.信息表示與處理的一般性思維 一般性思維是:首先研究信息或符號綁定語義的方法;進一步形成協議、標準或語言(被
稱為廣義的語言),然後基於所形成的廣義語言,開發相應的解析器/編譯器/執行器等(被稱 為廣義的編譯器),實現自動處理。信息處理即是不斷提出新的廣義語言,同時提供廣義編 譯器來解析和執行用所提出的廣義語言編寫的信息,提高計算機的信息處理能力。 13.「分離」與「分層」思想
分離與分層是複雜問題求解的基本思維模式。分離是將共性的內容分離出來以單獨的軟 件或系統來管理,通過逐漸剝離共性內容使複雜問題的可解決內容越來越多,進而到最終求 解的思想;分層是將一個複雜問題分為不同層面,比如從宏觀到微觀的若干層,從概念到實 現的若干層等,每一層相對來講比較簡單,可清晰定義每一層的協議/標準並編製相應的處 理程序。然後再建立高層向低層的轉換關係,從而實現複雜問題求解的一種思想。
附:計算機語言發展路線圖
2-7
哈爾濱工業大學《計算機導論》課程複習提綱 任課教師:戰德臣,聶蘭順
2-8

哈爾濱工業大學《計算機導論》課程複習提綱 任課教師:戰德臣,聶蘭順
3.1 基本概念清單 1. 演算法
第3章 問題求解
演算法是一個有窮規則的集合,它用規則規定了解決某一特定類型問題的運算序列,或者 規定了任務執行或問題求解的一系列步驟,其基本特徵為有窮性、確定性、有輸入和輸出以 及能行性。 2. 數學模型與數學建模
數學建模就是建立數學模型,就是用數學語言描述實際現象的過程。
數學模型就是對實際問題的一種數學表述,是關於部分現實世界為某種目的的一個抽象 的簡化的數學結構,數學結構可以使數學公式、圖表和框圖等。 3. 數據結構
數據結構是數據的邏輯結構、存儲結構及其操作的總稱,它提供了問題求解/演算法的數 據操縱機制,其中的邏輯結構反映了數據之間的關係,而存儲結構是在反映數據邏輯關係的 原則下,數據在存儲器中的存儲方式。 4. 變數
變數是演算法或程序運行過程中可發生改變的量。通常由符號表示,一個變數由變數名和 變數值構成,變數值可以不斷發生變化。
本質上講,變數是一系列存儲單元,該存儲單元的地址用符號來表示即變數名,即變數 名是用符號表示的存儲單元地址,而變數值則是存儲單元的內容。一個變數佔用多少存儲單 元,則是由變數類型決定的,變數名通常對應這一系列存儲單元的起始地址。 5. 向量和表
向量是一有序數據的集合型變數,向量中的每一個元素都屬於同一個數據類型,用一個 統一的向量名和下標來唯一的確定向量中的元素。在程序設計語言中,又稱為數組。
表是按行按列組織數據的集合型變數,通常是一個二維向量。 6. 控制結構與典型的控制結構
控制結構是指演算法或程序的步驟或規則的執行關係,它提供了問題求解/演算法的過程式控制 制機制。
典型的控制結構有三種:順序結構、分支結構和循環結構。 順序結構是按順序執行一條條規則的一種結構,即「執行 A,然後執行 B」 分支結構是按條件判斷結果決定執行哪些規則的一種結構「,即如果 Q 成立,那麼執
行 A,否則執行 B」 ,Q 是某些邏輯條件。 循環結構:控制指令/規則的多次執行的一種結構—迭代(iteration)。
7. 流程圖 流程圖是圖形方式表示演算法的一種方法,它用矩形框表示一組順序執行的規則或者程序
語句,用菱形框表示條件判斷及根據判斷結果執行不同的分支,用圓形框表示演算法或程序的 開始或結束,用箭頭線表示演算法或程序的走向。 8. 程序設計語言的基本語法要素
程序設計語言的基本語法要素有:常量和變數、表達式、程序語句和函數。
3-1
哈爾濱工業大學《計算機導論》課程複習提綱 任課教師:戰德臣,聶蘭順
所謂常量是程序運行過程中始終不變的量,變數是程序運行過程中可發生改變的量。表 達式為用算術運算符、邏輯運算符、比較運算符將變數、常量連接起來所形成的計算公式。 程序語句為一條條計算機可識別的計算規則的完整表示,是程序的基本構成單位,通常按行 書寫,一行為一條語句,但也有在一行書寫多條語句的,而多條語句之間通過分隔符予以區 分。所謂函數是系統已編製好並可直接在程序編寫中使用的完成特定功能的程序,我們可直 接像表達式或變數一樣使用它,它通常存儲於隨語言環境提供給我們的公用函數庫中。 9.時間複雜性
如果一個問題的規模是 n,解這一問題的某一演算法所需要的時間為 T(n),它是 n 的某一 函數,T(n)稱為這一演算法的「時間複雜性」 10. 「系統」與「系統」的特性
系統是指由相互聯繫、相互作用的若干元素構成且具有特定結構和功能的統一整體。
系統的基本特徵:環境特徵、功能與過程特徵、構件與結構特徵及整體性、層次性和動 態性特徵。
11. 環境、功能與過程、構件與結構 所謂系統的環境是指和系統相關的外部因素的總稱,系統與系統外各元素(或者環境)之
間是相互作用的。 所謂構件是構成系統的一個個可相互獨立的元素,又可稱為模塊、單元等;所謂結構是
指構件(或模塊或單元)之間的相互連接方式與相互作用方式的框架。 所謂功能是指系統所表現出來的,具有並能夠提供的特性、功效、作用和能力等,所謂
過程是各項功能在系統運行過程中的次序及約束關係。 12. 系統的整體性、層次性和動態性
整體性是指系統的非還原性和非加和性。所謂非還原性是指系統的整體具有但還原為部 分便不存在的特性,即「湧現性」。所謂非加和性是指整體不能完全等於各部分之和,即「貝 塔朗菲定律」
層次性是指系統的一個功能或構件仍然可以作為一個系統來看待。即系統由子系統構 成,而子系統作為系統,又是由其子系統構成的,體現為層次性。
動態性是指系統運行過程中隨環境隨時間空間而變化的特性。 13.系統科學方法的三原則:整體優化、動態優化和模型化
系統科學方法的三原則:整體優化、動態優化和模型化原則 14.現代程序的典型構成要素
程序的基本要素有:常量和變數、表達式、程序語句和函數。
而現代程序的典型構成要素,除包含程序的基本要素外,還有類、對象與方法。所謂類 是將不同類型的數據和與這些數據相關的操作封裝在一起的集合體,類的結構是用來確定一 類對象的行為的,而這些行為是通過類的內部數據結構和相關的操作來確定的。所謂對象是 指該類的一個個的程序執行個體或稱實例,對象是用類創建的,同一「類」的所有對象具有 相同形式的函數和變數,但處理各自的數據(變數名相同,但變數值是不同的)。所謂方法是 能執行特定功能的程序語句塊。也稱為「過程」或「函數」。
15.結構框架 結構框架是按照某一種體系結構(Architecture)實現的,用於連接、裝配各種構件形成系
統的一套程序。 16. 軟體體系結構;軟體模式
軟體模式是被前人發現,經過總結形成的一套解決某一類問題的可以重複利用的一般性
3-2
哈爾濱工業大學《計算機導論》課程複習提綱 任課教師:戰德臣,聶蘭順
解決方案。其本質性特徵:把若干類相似問題中的不變部分和變化部分分離出來,其不變的 部分形成了模式,而變化部分留給用戶去解決該類問題中的某一個具體問題。
軟體體系結構(Software Architecture)是為軟體系統提供的一個結構(Structure)、行為和屬 性的高級抽象,它從一個較高的層次來考慮組成系統的構件、構件之間的連接,以及由構件 與構件交互形成的拓撲結構。簡單而言:體系結構 = 構件(或稱組件) + 連接件 + 約束。 17. 系統的可靠性與安全性、軟體系統的可靠性與安全性
可靠性(Reliability):產品或系統在規定的條件下和規定的時間內完成規定功能的能力, 它的概率度量稱為可靠度。
軟體可靠性:軟體可靠性是軟體系統在規定的時間內及規定的環境條件下,完成規定功 能的能力,是在規定的條件下,在規定的時間內,軟體不引起系統失效的概率;
安全性(Safety):安全性是指使傷害或損害的危險限制在可以接受的水平內。
軟體安全性是指軟體系統遭受傷害或損害的危險程度,所謂的傷害是指數據被破壞或被 非授權修改、隱秘數據被公開、數據和系統不能正確為用戶服務等現象。這種危險發生的概 率,可用於評估安全性:概率越小、安全性越高。
3.2 基本思想與基本過程 1. 演算法類問題的求解框架
演算法類問題的求解框架可以描述為:
(1)問題抽象及數學建模:首先要理解問題,將問題抽象為一個數學問題,並給出求解 該數學問題的演算法模型。
(2)演算法的數據結構和控制結構設計:將數學模型轉換為可由計算機自動計算的演算法, 其中涉及的數據要選擇合適的數據結構進行表示和存儲,要用流程圖或規範的自然語言將算 法的步驟或基本思想表達出來。
(3)演算法的實現:用程序設計語言編寫演算法實現的源程序,並經過編譯、鏈接形成可執 行的程序。
(4)演算法的分析:演算法設計和實現後,需要分析演算法的正確性和複雜性,判斷能行性! 所謂能行性就是是否在現有資源可承受能力下完成的。 2. 程序設計過程
程序設計過程一般經過編輯源程序  編譯  鏈接  執行。所謂編輯源程序是利用程序編 輯器,按照計算機語言的規範書寫程序的過程;所謂編譯是將編製好的源程序翻譯成機器可 以執行的機器代碼程序(又稱為目標代碼)的過程。所謂鏈接是將目標代碼與公用函數庫中的 函數實現代碼集成起來形成最終可執行程序的過程。所謂執行就是程序的運行過程。
3. 演算法的描述方法:流程圖法和步驟描述法 參見講義,自己舉例掌握演算法的描述方法。
4. 基本結構程序的編寫訓練、基本結構程序的識讀訓練 提示:要求能夠編寫基本結構的程序,並且能夠模擬計算機執行基本結構的程序。基本
結構即:循環結構、分支結構、順序結構、及其簡單的混合結構(略,參見講義); 5. 關於演算法設計與演算法分析的基本思想;典型演算法策略。
演算法設計與分析就是針對具體的問題,選擇合適的演算法策略,設計求解該問題的具體算 法。典型演算法策略如貪心演算法,它的基本思想是「今朝有酒今朝醉」,即把求解一個問題分 成若干步,每一步一定要做當前情況下的最好選擇,否則將來可能會後悔,故名「貪心」。
求解 TSP 問題的貪心演算法:從某一個城市開始,每次選擇一個城市,直到所有城市都 3-3
哈爾濱工業大學《計算機導論》課程複習提綱 任課教師:戰德臣,聶蘭順
被走完。每次在選擇下一個城市的時候,只考慮當前情況,保證迄今為止經過的路徑總距離 最短。
其他演算法策略還有遍歷與搜索演算法、分治演算法等等。
6. 演算法的正確性與複雜性分析基本思想 演算法設計和實現後,應採用證明方法或模擬分析方法,分析演算法的正確性和複雜性。算
法的正確性分析是分析演算法的輸出是最優解還是可行解,如果是可行解,與最優解的偏差有 多大。演算法的複雜性分析是分析演算法的效率:時間效率和空間效率。空間複雜度是分析演算法 在執行過程中所佔存儲空間的大小;時間複雜性是:如果一個問題的規模是 n,解這一問題 的某一演算法所需要的時間為 T(n),它是 n 的某一函數,T(n)稱為這一演算法的「時間複雜性」。 通常採用大 O 記法,如Ο(n2) 、Ο(2n)等表示複雜性的量級。
當演算法的時間複雜度的表示函數是一個多項式時,如 O(n2)時,則計算機對於大規模問 題是可以處理的。當演算法的時間複雜度是用指數函數表示時,如O(2n),當n很大(如10000) 時計算機是無法處理的,在計算複雜性中將這一類問題被稱為難解性問題。
所有可以在多項式時間內求解的問題稱為 P 類問題,所有在多項式時間內可以驗證的問 題稱為 NP 類問題。 7. 從哪幾個方面描述 「系統」?
主要應從三個方面描述「系統」:
(1)從環境角度描述系統。所謂系統的環境是指和系統相關的外部因素的總稱。系統與 系統外各元素(或者環境)之間是相互作用的。
(2)從外特性或者說目的和作用角度描述系統。描述系統的功能與過程。所謂功能是指 系統所表現出來的,具有並能夠提供的特性、功效、作用和能力等,所謂過程是各項功能在 系統運行過程中的次序及約束關係。
(3)從內特性或者說構成、構造角度描述系統。描述系統的構件與結構。系統是由若干 構件,按照一定的結構(Structure)構成的。所謂構件是構成系統的一個個可相互獨立的元素, 又可稱為模塊、單元等;所謂結構是指構件(或模塊或單元)之間的相互連接方式與相互作用 方式的框架。
8. 系統類問題的求解框架 系統類問題的求解框架可以描述為: (1)建立問題域模型:先建立不考慮計算系統的計算模型,即問題域模型,儘管目的是
刻畫計算系統。若要建立計算系統,首先需理解計算系統,理解:如果由人來做,應如何計 算呢?
(2)建立軟體域模型:建立計算系統的構建模型,即軟體域模型,說清楚軟體系統應怎 樣?
(3)模塊與系統的實現:用程序實現模塊與系統。 (4)系統的部署與運行:將系統部署到應用環境中,利用系統進行業務工作。 (5)系統的結構與性能:設計系統時應關注系統結構的選擇和可靠性、安全性問題。選
擇合適的結構,保證系統的可靠性和安全性。 9. 整體優化、動態優化和模型化原則
整體優化原則:注意系統的非還原性和非加和性,系統整體優化,或者說全局優化是非 常重要的。
動態優化原則:注意系統總是動態的,永遠處於運動變化之中。隨時間、空間和環境而 變化的。例如:飛機造好了,但要考慮(1)適應各類天氣的情況;(2)材料隨使用的磨損等;
3-4
哈爾濱工業大學《計算機導論》課程複習提綱 任課教師:戰德臣,聶蘭順
軟體系統也是一樣,當內存調度出現混亂時,當軟體受到病毒的侵擾時,怎樣回到正確狀態? 當系統裝載的內容越來越多,使用時間越來越長,系統會不會越來越慢?
模型化原則: 以模型代替真實系統。進行分析、設計、模擬和實驗,達到認識真實系 統特性和規律性的方法。 10.問題域建模與軟體域建模的基本思想
問題域建模主要是從功能/過程角度,即使用和作用的角度對系統進行模型化表達以達 到理解系統的目的,可從功能、過程、業務計算邏輯、信息、組織等視角建立模型。典型的 建模過程:(1)基本概念的澄清和相關信息的表示;(2)用少量典型數據模擬計算過程;(3)計 算模型的表達;(4)系統功能的識別、理解與定位;(5)其他方面的建模。
軟體域建模則主要是從構件/結構角度,即構造系統的角度對系統進行模型化表達以達 到理解系統的目的。可從信息(對象)、功能與模塊劃分、程序類設計、功能/函數調用關係、 處理邏輯等視角建立模型。問題域信息模型強調信息要素,但更強調信息要素之間的整體集 成關係,是從信息的使用和分析角度看信息,而軟體域信息模型則強調信息的存儲結構,強 調信息存儲和信息自動處理的有效性。問題域功能模型強調使用功能,而軟體域功能模型則 強調模塊劃分,強調如何系統的製造與構造,強調構件與結構。 11.建模的主要目的是什麼?
建模的主要目的是理解系統與表達思想,而不是繪製圖形,儘管繪製模型圖形是建模的 必要手段。建模是「思維的過程」,模型反映的是「思維的結果」。因此衡量模型優劣的標準 首先是檢查其是否清晰地表達了思想、表達了關於一個系統(被建模對象)的思想,其次才是 其表達方式的規範性和一致性問題。
12. 軟體系統的構成關係 軟體系統(設計)  模塊的集合 + 結構 + 資料庫 模塊  程序類的集合 + 各程序類對象間函數調用關係的集合 (程序)類  程序變數集合 + 函數(子程序) 的集合 函數  完成一個具體功能的程序 變數  函數處理與保存的數據 對象/實例  程序類的一個執行實體 資料庫  永久保存的數據表的集合 數據表  資料庫的基本控制單位
13. 軟體系統的實現過程 模塊的實現:將由軟體模型劃分出的一個個模塊轉換成正確的程序代碼。 模塊測試:模塊實現程序必須進行測試,以保證正確性。 系統的部署:將開發的模塊安裝、部署到擬應用的環境中,並與其所處的環境形成一有
機的整體,即將所有模塊統一管理並使用統一的數據和流程等。 系統測試:重點是各模塊間衝突檢查及系統 Bug 的發現與糾正。 系統應用:包括裝載用戶的數據和過程,用戶利用系統進行業務工作。用戶依賴系統的
程度即是系統應用的程度。 14. 從實現層面看什麼是一軟體系統
一個軟體系統的實現要有一個運行支撐環境(即結構框架)、一批以目錄形式組織的文件 (即部署管理的內容) 、一套配置文件(記錄了客戶對系統所做的個性化配置參數)、一套功能 菜單(即系統對功能的組織)、若干個過程(即各個功能的次序關係)、一套許可權控制數據(角色 /許可權/用戶等) 和一套數據(用戶產生的由系統使用和管理的數據)等。
3-5
哈爾濱工業大學《計算機導論》課程複習提綱 任課教師:戰德臣,聶蘭順
15. 三種軟體環境 三種軟體環境是指開發環境、測試環境和應用環境。 開發環境:是為程序員開發應用程序所建立的環境。程序員在此環境中可開發實現一個
個模塊,並用自己建立的菜單、過程和數據進行模塊運行正確性的檢驗。核心構成:基礎設 施;結構框架(運行支撐環境);各種編程工具。關注點:模塊及系統的實現,重點是模塊的 實現及模塊 Bug 的發現與糾正。
測試環境:是為系統的統一測試所建立的環境。測試員站在系統角度建立統一的菜單、 過程和數據,並部署程序員實現的模塊以進行系統正確性的檢驗。核心構成:基礎設施;結 構框架(運行支撐環境);測試用資料庫、過程、許可權控制數據;測試用菜單。關注點:系統 及系統的正確性,重點是各模塊間衝突及系統 Bug 的發現與糾正。
應用環境:是為客戶運行系統所建立的環境,需要為客戶建立可進行正常業務工作的環 境。核心構成:基礎設施;結構框架(運行支撐環境);正式用資料庫、過程、許可權控制數據; 正式用菜單。關注點:關注系統,更關注數據、過程及許可權控制等與客戶業務密切相關的內 容。
3-6

哈爾濱工業大學《計算機導論》課程複習提綱 任課教師:戰德臣,聶蘭順
第 4 章 計算機科學與技術學科介紹
4.1 基本概念清單 1. 計算學科的五個分支學科
計算學科目前被分為計算機科學、計算機工程、軟體工程、信息系統和信息技術五個分 支學科。
計算機科學側重計算與計算系統相關的理論研究,計算機工程側重用硬體實現計算系統 的技術研究,軟體工程側重以軟體的開發、管理與應用為對象進行計算系統的技術研究,信 息系統則以信息的組織、管理與應用為對象進行信息工程研究,信息技術則側重於信息處理 手段、及處理手段的選擇、組合與集成技術研究。
2. 計算學科的三種形態/過程 計算學科的三種形態/過程是抽象形態、理論形態與設計形態。 抽象形態是指由具體事物中發現其本質性特徵和方法的過程,是「理解區分命名
 表達」,是「尋找相同形式,處理可變內容」的過程,是感性認識世界的手段。 理論形態是對規律進行嚴密化描述及論證的過程,通常由定義、公理、性質、定理和證
明等內容構成,是發現現實世界規律的手段。 設計形態是構建計算系統的過程,是技術、原理在計算系統中實現的過程,是構造計算
系統來改造世界的手段。 3. 抽象形態的結果與兩種類型的抽象
簡單而言,兩種類型的抽象一是方法論層面的抽象,研究一般性的抽象方法;另一是方 法論應用層面的抽象,用一般性方法做指導進行具體任務的抽象。
或者如下敘述:一方面是建立對客觀事物進行抽象描述的方法,另一方面是要採用現有 的抽象方法建立具體問題的概念模型,從而實現對客觀世界的感性認識。
抽象的結果是關於系統要素的概念模型,通常以可視化非數學模型、形式化模型來表達。 也可以表達為數學模型,如果必要的話。 4. 典型的學科方法及特徵
典型的學科方法有: 形式化方法、遞歸方法、結構化方法和面向對象方法。
形式化方法是一種嚴密化(演算法類和系統類)問題求解的方法,其典型特徵是符號化、抽 象化、邏輯嚴格化。
遞歸方法是一種典型的演算法和系統設計方法,是計算學科核心的構造性方法的典型代 表,其典型特徵是自身調用自身、高階調用低階來實現求解!
結構化方法是一種分析系統、設計系統的思維方法,其典型特徵是以功能為中心,自頂 向下分解。
面向對象方法是另一種分析系統、設計系統的思維,其典型特徵是以對象為中心,逐一 地獨立地分析每一對象的各種特性。 5. 形式化方法
形式化方法是用符號化,基於數學思維,嚴密描述被研究對象的一種方法,是在對事物 描述形式化的基礎上,通過研究事物的形式化變化規律來研究事物變化規律的全體方法的總 稱,形式化方法得到的是形式系統。
4-1
哈爾濱工業大學《計算機導論》課程複習提綱 任課教師:戰德臣,聶蘭順
形式化是將事物的內容和形式相分離,用事物的某種形式(符號)來表示事物,以便尋找 相同的形式,處理可變的內容。 6. 形式系統的四個組成部分
形式系統的四個組成部分是初始符號、形式規則、公理、變形規則(或稱定理)。 初始符號:是無需定義的符號集; 形式規則:它規定一種程序,藉以判定哪些符號串是本系統中的公式,哪些不是。 公理: 即在本系統的公式中確定不加推導就可以斷定的公式集。
變形規則: 變形規則亦稱演繹規則或推導規則。變形規則規定從已被斷定的公式如何得 出新的被斷定公式。被斷定的公式又稱為系統中的定理。
在以上 4 個組成部分中,前兩個部分定義了一個形式語言,後兩個部分在該形式語言上 定義了一個演繹結構。形式系統是由形式語言和定義於其上的演繹結構組成的。 7. 計算技術中與遞歸有關的概念
與遞歸有關的概念有:遞歸關係、遞歸數列、遞歸過程、遞歸演算法、遞歸程序、遞歸方 法等。
遞歸關係指的是一個數列的若干連續項之間的關係; 遞歸數列指的是由遞歸關係所確定的數列; 遞歸過程指的是調用自身過程的過程; 遞歸演算法指的是包含遞歸過程的演算法; 遞歸程序指的是直接或間接調用自身程序的程序; 遞歸方法也稱遞推法,是一種在有限步驟內,根據特定的法則或公式,對一個或多個前
面的元素進行運算得到後續元素,以確定一系列元素如數或函數的方法。 8.結構化方法與面向對象方法
結構化方法是計算學科的一種典型的分析系統、設計系統的思維方法,它採用了系統科 學的思想方法,依據層次分解思維,自頂向下地分析和設計系統。
面向對象方法是計算學科的一種典型的分析系統、設計系統的思維方法,它以對象為中 心,逐一地獨立地分析或設計系統每一對象的各種特性,達到系統分析與設計的目的。 9. 對象、類、消息、事件
對象是現實世界中的一個個個體,具有以下特性:有唯一的標識,有自己的狀態和數據, 對象自己執行自身的工作而無需其他對象干預,對象可為其他對象服務,或接受其他對象服 務,對象之間交互的唯一手段是消息。
消息是對象之間傳遞的內容,如指示、打聽、請求等,本質是數據;
事件是一種能夠激活對象功能的特殊的消息。當發生事件後將給所涉及對象發送一個消 息,對象便可執行相應的功能。
類是設計形態的概念,對象是運行形態的概念,一個類對應了形式上相同但內容不同的 若干對象。例如「學生」是一個類,它對應了「張三」、「李四」、「王五」等所有的是學生的對象。 類是一種「型」,而對象則是該型的一個個「值」,或者說,對象是類的一個個實例(Instance)。
4.2 基本思想與基本過程 1. 計算學科的各分支學科的研究內容
「計算機科學」是研究計算機和可計算系統的理論方面的學科。它主要研究(1)為硬體、 軟體、網路方面的計算問題求解提供有效的解決方式和方法;(2)提出新的問題求解策略、 新的問題求解演算法,在硬體、軟體、互聯網方面;(3)發現並設計使用計算機的新方式和新
4-2
哈爾濱工業大學《計算機導論》課程複習提綱 任課教師:戰德臣,聶蘭順
方法, 尤其是互聯網方面。 「計算機工程」是研究計算機的設計、建造和應用的偏工程性的學科。它主要研究(1)
設計和建造計算機及基於計算機的系統,涉及硬體、軟體、通訊及其之間的介面;(2)構建 和建造計算機系統、通訊系統和嵌入式系統。
「軟體工程」是研究軟體的開發、測試、運行和維護的偏工程性的學科。它以「軟體」 為研究對象,「軟體」的無形性和軟體操作的非連續性使得大型軟體系統在開發、運行和維 護方面都有不同於其他有形產品的問題需要解決,例如如何準確地理解客戶對軟體的期望? (需求工程);如何開發軟體使得能滿足客戶不斷變化的需求? (軟體復用與演化);如何檢驗 軟體是一個可靠的、安全的、無 Bug、可自我修復的軟體? (軟體的正確性可信性)等。
「信息系統」是以信息的組織、管理與應用為對象進行信息工程研究,研究信息技術解 決方案與企業業務整合,為企業提供信息服務的,偏工程性與管理性的學科。
「信息技術」是研究信息處理手段、及處理手段的選擇、組合與集成技術,通常而言研 究軟體硬體網路產品的選型、安裝、客戶化、維護、集成等技術,偏應用性的學科。 2. 計算學科各分支學科的典型特點,其對人才要求的知識結構特徵
典型特點:計算機科學偏重基礎理論性的研究;計算機工程和軟體工程均偏重工程性的 研究,前者偏重硬體技術,而後者偏重軟體技術;信息系統和信息技術則均偏重於應用性的 研究,前者偏重信息,而後者偏重信息處理手段,二者又被廣義的稱為信息技術。
知識結構特徵: 首先他們都要求有很好的計算思維基礎和問題求解基礎。在此基礎上, 計算機科學強調數學理論基礎和演算法分析基礎; 計算機工程強調系統工程基礎和計算機硬體基礎; 軟體工程強調系統工程基礎和計算機軟體基礎; 信息系統強調信息技術基礎和業務基礎,強調計算與業務相結合的複合型知識結構; 信息技術強調信息技術基礎,強調通用性知識與典型產品相結合的專門型知識結構;
3. 抽象、理論與設計之間的關係 設計是指構造計算系統來改造世界的手段,是工程的主要內容,只有設計才能造福於人
類(設計的價值)。理論是發現世界規律的手段,理論,如果不能指導設計,則是反映不出其 價值的;設計,如果沒有理論指導,則設計的嚴密性、可靠性、正確性是沒有保證的(理論 的價值);抽象是感性認識世界的手段,理論和設計的前提都需要抽象,沒有抽象二者都是 沒有辦法達成目標的(抽象的價值)。
區分並命名現實世界問題的每一個形式要素是抽象。理論指導下的抽象將更為嚴密,而 在很好的抽象基礎上的理論是認識深入化的標誌。理論的目的是數學化邏輯嚴密化各種概念 及規律的描述,抽象是理論研究的前提和保證。設計的目的是設計和實現計算系統。先抽象 再設計,深入認識形式系統,則可在更高層面實現計算系統。理論支持下的設計可使設計具 有正確性、完備性等特性。
4. 遞歸和迭代的本質區別 遞歸和迭代都是構造方法的典型案例。遞歸是自身調用自身、高階調用低階的方法;而
迭代則是通過循環來實現由低階到高階的運算。迭代不調用自身程序,是通過循環來實現的。 迭代程序都可以轉換為與它等價的遞歸程序,反之,則不然。遞歸程序的實現要比迭代程序 的實現耗費更多的時間和空間,因此能用迭代程序的地方盡量少用遞歸程序實現。 5. 結構化方法的思維基礎
系統論基礎:系統是有目標的(作用性);系統是有邊界的(外特性);系統是有組成要素 4-3
哈爾濱工業大學《計算機導論》課程複習提綱 任課教師:戰德臣,聶蘭順
的且各組成要素之間是有關聯的(內特性)。組成要素很多,可以僅描述與系統相關的組成要 素即可(複雜度)。
控制論基礎:系統被區分為物理系統和控制系統。控制系統通常是計算系統,它接受來 自物理系統的數據及狀態,進行決策並下達指令控制物理系統的運行(控制與被控)。
分解論基礎:系統是複雜的,化解複雜為簡單的辦法就是分解,將系統分解為不同的部 分,各個擊破。分解、再分解,直到清楚為止。 6.結構化方法的基本思想
結構化方法的基本思想是系統的外特性和內特性分離描述,首先刻畫外特性,即系統的 邊界和環境。外特性刻畫清楚後,再刻畫內特性,即系統的構成。
外特性的刻畫方法如下,以功能或活動為中心,刻畫功能的輸入、輸出、目標與控制和 支撐等;輸入:從外界傳到系統中的信息;輸出:從系統中傳到外界的信息;功能或活動: 被認為是將輸入轉換為輸出的一種變換過程。一般,宏觀層面稱功能,而微觀層面稱活動。 目標與控制:功能應達到的目標,或者說,功能是在目標與控制的控制下執行。支撐:執行 功能或活動所需要的必要的支撐條件。外特性刻畫中將系統內部構成封裝起來,以屏蔽內部 細節對外特性描述的干擾。
內特性以單獨的圖來描述,描述其功能分解、每一子功能在該功能內的外特性及各個子 功能關係的描述。功能分解:上級功能被分解為若干個下級功能(被稱為子功能),從邏輯上 這些子功能的集合應等價於該上級功能。子功能外特性的描述:描述每一個子功能的外特性。 子功能關係的描述:建立子功能之間的關係。可以認為:功能(內部構成)=子功能的集合+ 子功能外特性集合+子功能之間關係的集合。
如此自頂向下,逐級分解,便可由粗至細將一個複雜系統刻畫清楚。 7. 結構化方法的基本原則
抽象原則:抽象原則是一切系統科學方法都必須遵循的基本原則,它注重把握系統的本 質內容而忽略與系統當前目標無關的內容,即:既能夠理解細節,同時又能從細節中跳出來。
模型化原則:抽象的結果需要通過模型來表達,儘可能採用非數學化模型(圖示化模型) 和形式化模型來表達(後者要比前者嚴格) 。必要情況下,也可以數學化模型來表達。典型 的模型包括:
分解原則:分解原則是結構化方法中最基本的原則,它是一種先總體後局部的思想原則, 在構造信息系統模型時,它採用自頂向下分層解決的方法。
模塊化原則:模塊化是結構化方法最基本分解原則的具體應用,它主要出現在結構化設 計階段中,其目標是將系統分解成具有特定功能的若干模塊從而完成系統指定的各項功能。
等價性原則:上級功能和下級子功能在邊界範圍內的宏觀意義上的等價性原則。 8.面向對象方法的基本思想
面向對象方法的基本思想: (1)確定系統的範圍,識別出系統可能涉及的對象(類); (2)對每一個對象做如下的工作:識別該對象的所有狀態;識別對象的狀態轉換及轉換
條件和動作;識別該對象的所有可能的活動;識別該對象的數據存儲與顯示;識別該對象的 其他特性。
(3)對所有對象,按識別的內容建立相關的模型。 簡單而言,以對象為中心, 逐一地獨立地分析或設計每一對象的各種特性。
4-4

哈爾濱工業大學《計算機導論》課程複習提綱 任課教師:戰德臣,聶蘭順
6.1 基本概念清單 1. Linux 的誕生
第 6 章 Linux 操作系統的使用
Linux 誕生於 1991 年,是一種類 UNIX 操作系統,Linux 誕生的主要基礎有 UNIX、 MINIX、GUN、POSIX 和 Internet。 2. Linux 發行版
Linux 免費的內核,以及用戶或廠商自行搭配的其他應用程序,構成了「Linux Distribution」(內核+應用軟體包),Linux 發行版有很多種,包括 Ubuntu、openSUSE、Debian 等。 3. Linux 的特點
開放性、多用戶、多任務、良好的用戶界面、設備獨立性、豐富的網路功能、可靠地系
統安全、良好的可移植性。
4. 開源軟體 開放源代碼(Open Source)軟體:在開放源代碼許可證下發布的軟體,保障軟體用戶
自由使用及接觸源代碼的權利,也保障了用戶自行修改、複製以及再分發的權利。典型的軟 件有 Eclipse、GNU Emacs、Apache、GCC 等。 5. Linux 需要掌握的基本命令
ls, date, cal, who, man, cat, head, tail, more, less, od, cp, mv, rm, ln, pwd, cd, mkdir, rmdir, find, useradd, usermod, userdel, passwd, groupadd, groupdel, gpasswd, id, su, groups, finger, chown, chgrp, chmod, vi, grep, tar, gzip, dpkg, apt-get install, apt-get update。 6. Linux 的基本目錄及其內容
Linux 文件系統包括的目錄有 bin, sbin, root, mnt, boot, lost+found, lib, dev, etc, var, usr, proc, initrd, tmp, home, opt。
具體內容參見講義。 7. 在本科學習中能提供支撐的 GNU/Linux 軟體
Linux, Gcc,gdb, Lex, YaCC, Eclipse, Apache, mySQL, Emacs, …。
6.2 基本思想與基本過程 1. Linux 的文件與存儲管理
Unix/Linux 中,任何軟硬體都被視為文件,文件是位元組序列,分為常規文件、目錄、設 備文件、符號鏈接文件、字元文件、套接字文件等。
Linux 文件沒有「擴展名」的概念,文件的名稱與類型無直接關係。
存儲設備或存儲設備的分區格式化為文件系統後,分為兩部分,Block 用來存儲數據, Inode 用來存儲這些數據的信息,包括文件大小、屬主、歸屬的用戶組、讀寫許可權等。操作 系統通過 inode 管理文件。
可以對文件創造硬鏈接和軟鏈接(符號鏈接)。
文件系統採用分層樹狀目錄結構管理文件,有根目錄、home 目錄和工作目錄的概念, 有絕對路徑和相對路徑的概念。
6-1
哈爾濱工業大學《計算機導論》課程複習提綱 任課教師:戰德臣,聶蘭順
2. Linux 的用戶管理 Linux 是典型的多用戶、多任務操作系統,用戶在系統中分角色,不同角色具有不同權
限,能夠完成不同的任務,典型的角色包括 root、虛擬用戶和普通真實用戶。 Linux 使用用戶和用戶組的概念管理用戶和角色,用戶與用戶組之間的關係可以是一對
一、一對多、多對一等。 用戶可以通過 su 命令改變角色。
3. Linux 的文件/目錄的歸屬及許可權控制 文件/目錄的屬性記錄/控制著文件/目錄的歸屬和許可權,歸屬主要包括歸屬於哪個用戶和
歸屬於哪個用戶組兩個方面,許可權通過 9 個許可權控制位定義,許可權分為讀、寫、執行三種, 許可權分為三部分,即文件屬主、所屬用戶組和其他用戶的許可權。 4. Linux 下的 Shell 編程
Shell 是介於用戶和 Linux 操作系統的內核(kernel)間的一個介面程序,能夠作為解釋 性的程序設計語言,支持 Shell 編程。
Shell 編程的基本過程是:(1) 編輯一個利用 Linux 命令和 Shell 腳本寫成的程序文件; (2) 設置該文件的可執行許可權;(3) 執行 Shell 程序。 5. Linux 的 I/O 重定向
Linux 命令執行時的 I/O(輸入/輸出)為,調用標準輸出(stdout)進程–屏幕用於顯示信 息,調用標準錯誤(stderr)進程–屏幕顯示任何錯誤信息,調用標準輸入(stdin) –鍵盤得到用 戶輸入的信息。
I/O 重定向是指更改系統的輸入/輸出,如將命令的輸出重定向到一個文件,則命令的執 行結果將寫入某一文件中而不是顯示到屏幕上。
6-2

哈爾濱工業大學《計算機導論》課程複習提綱
任課教師:戰德臣,聶蘭順
第 7 章 引論
7.1 基本概念清單 1.區域網、廣域網、互聯網、Internet 2.集線器、數據機和路由器 3.網路協議、OSI 七層協議、TCP/IP 協議 4. IP 地址,域名,DNS,URL,HTTP,WWW,HTTP,HTML 5.搜索引擎,網頁,超鏈接與超文本,網站
6. 常用排版術語 7.典型的 Internet 服務:Ftp, Telnet, Email, WWW 8.計算機病毒 (概念的具體定義可參閱講義)
7.2 基本思想與基本過程 1. 科技文章的編排要求,科技講演稿的製作要求 2. 文字的相關格式有哪些;段落的相關格式有哪些;版面的相關格式有哪些;什麼情況下 使用什麼樣的格式。 3. 區域網組建方法及設施;廣域網組建方法及設施;互聯網組建方法及設施 4. 連接到 Internet 的方法和過程,發布信息的方法和過程,獲取信息的方法和過程 5. 常見的計算機安全威脅;病毒可能攻擊的計算機部位及其危害 6. 常見的計算機與信息安全防護手段 7. 計算機行業應該遵守的職業道德 8. HTML 語言和 XML 語言的異同點及作用 9.通用搜索引擎的基本功能 (基本思想與基本過程的解釋可參閱講義)
7-1