計(jì)算機(jī)導(dǎo)論第4 章 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)科知識(shí)體系

第4章計(jì)算機(jī)科學(xué)與技術(shù)學(xué)科知識(shí)體系

本章介紹計(jì)算機(jī)科學(xué)與技術(shù)學(xué)科的知識(shí)結(jié)構(gòu)體系，并對(duì)其中的有關(guān)問(wèn)題進(jìn)行簡(jiǎn)要說(shuō)明。

4.1知識(shí)體系結(jié)構(gòu)

我們用14個(gè)知識(shí)領(lǐng)域(area)、若干個(gè)知識(shí)單元(unit)和一系列知識(shí)點(diǎn)(topic)來(lái)描述計(jì)算機(jī)

學(xué)科的知識(shí)體系。

知識(shí)體系結(jié)構(gòu)組織成如下三個(gè)層次：知識(shí)領(lǐng)域(area)、知識(shí)單元(unit)和知識(shí)點(diǎn)(topic)。一

個(gè)知識(shí)領(lǐng)域可以分解成若干個(gè)知識(shí)單元，一個(gè)知識(shí)單元又包含若干個(gè)知識(shí)點(diǎn)。知識(shí)體系結(jié)構(gòu)

的最高層是知識(shí)領(lǐng)域，表示特定的學(xué)科子域。每個(gè)知識(shí)領(lǐng)域用兩個(gè)英文字母的縮寫(xiě)表示，例

如，OS表示操作系統(tǒng)，PL表示程序設(shè)計(jì)語(yǔ)言等。知識(shí)體系結(jié)構(gòu)的中間層是知識(shí)單元，表示

知識(shí)領(lǐng)域中獨(dú)立的主題(thematic)模塊。每一知識(shí)單元用知識(shí)領(lǐng)域名后加一個(gè)數(shù)字后綴表示，

例如，0S3是操作系統(tǒng)中有關(guān)并發(fā)性的知識(shí)單元。知識(shí)體系結(jié)構(gòu)的最底層是知識(shí)點(diǎn)。

表4-1是對(duì)計(jì)算機(jī)科學(xué)與技術(shù)知識(shí)體系的概要總結(jié)，它展示了知識(shí)領(lǐng)域、知識(shí)單元、核

心知識(shí)單元及各自所需的最少時(shí)間。

表4-1計(jì)算機(jī)科學(xué)與技術(shù)學(xué)科知識(shí)體系

代號(hào)知識(shí)領(lǐng)域知識(shí)單元最少學(xué)時(shí)

DS離散結(jié)構(gòu)DSI函數(shù)、關(guān)系和集合；DS2基本邏輯；DS3證明技巧；72核心學(xué)時(shí)

DS4計(jì)數(shù)基礎(chǔ)；DS5圖與樹(shù)

PF程序設(shè)計(jì)基礎(chǔ)PFI程序設(shè)計(jì)基本結(jié)構(gòu)；PF2算法與問(wèn)題求解；PF3基本69核心學(xué)時(shí)

數(shù)據(jù)結(jié)構(gòu)；PF4遞歸；

PF5事件驅(qū)動(dòng)程序設(shè)計(jì)

AL算法與復(fù)雜性AL1算法分析基礎(chǔ)；AL2算法策略：AL3基本算法：AL454核心學(xué)時(shí)

分布式算法；AL5可計(jì)算性理論基礎(chǔ)；

AR計(jì)算機(jī)組織與AR1數(shù)字邏輯與數(shù)字系統(tǒng)；AR2數(shù)據(jù)的機(jī)器級(jí)表示；82核心學(xué)時(shí)

體系結(jié)構(gòu)AR3匯編級(jí)機(jī)器組織；

AR4存儲(chǔ)系統(tǒng)組織和結(jié)構(gòu)：AR5接口和通信；

AR6功能組織；AR7多處理和其他系統(tǒng)結(jié)構(gòu)；AR8性能

提高技術(shù)；AR9網(wǎng)絡(luò)與分布式系統(tǒng)結(jié)構(gòu)

OS操作系統(tǒng)0S1操作系統(tǒng)概述；0S2操作系統(tǒng)原理；0S3并發(fā)性；40核心學(xué)時(shí)

0S4調(diào)度與分派；0S5內(nèi)存管理；0S6設(shè)備管理；0S7

安全與保護(hù)；0S8文件系統(tǒng)；0S9系統(tǒng)性能評(píng)價(jià)

PL程序設(shè)計(jì)語(yǔ)言PL1程序設(shè)計(jì)語(yǔ)言概論；PL2虛擬機(jī)；PL3語(yǔ)言翻譯簡(jiǎn)介；54核心學(xué)時(shí)

PL4聲明和類(lèi)型；PL5抽象機(jī)制;PL6面向?qū)ο蟪绦蛟O(shè)計(jì);

PL7函數(shù)程序設(shè)計(jì)：PL8語(yǔ)言翻譯系統(tǒng)；PL9類(lèi)型系統(tǒng)；

PL10程序設(shè)計(jì)語(yǔ)言的語(yǔ)義；PL11程序設(shè)計(jì)語(yǔ)言的設(shè)計(jì)

HC人機(jī)交互HC1人機(jī)交互基礎(chǔ)：HC2簡(jiǎn)單圖形用戶(hù)界面的創(chuàng)建：HC312核心學(xué)時(shí)

以人為本的軟件評(píng)估；HC4以人為本的軟件開(kāi)發(fā)；HC5

圖形用戶(hù)界面的設(shè)計(jì)；HC6圖形用戶(hù)界面的編程；HC7

多媒體系統(tǒng)的人機(jī)交互；HC8協(xié)作和通信的人機(jī)交互

NC網(wǎng)絡(luò)及其計(jì)算NC1網(wǎng)絡(luò)及其計(jì)算介紹；NC2通信與網(wǎng)絡(luò)；NC3網(wǎng)絡(luò)安48核心學(xué)時(shí)

全；NC4客戶(hù)/服務(wù)器計(jì)算舉例；NC5構(gòu)建Web應(yīng)用；

NC6網(wǎng)絡(luò)管理；NC7壓縮與解壓縮；NC8多媒體數(shù)據(jù)技

術(shù)；NC9無(wú)線(xiàn)和移動(dòng)計(jì)算

GV圖形學(xué)和可視GV1圖形學(xué)的基本技術(shù)；GV2圖形系統(tǒng)；GV3圖形通信；8核心學(xué)時(shí)

化計(jì)算GV4兒何建模；GV5基本的圖形繪制方法；GV6高級(jí)的

圖形繪制方法；GV7先進(jìn)技術(shù)；GV8計(jì)算機(jī)動(dòng)畫(huà)：GV9

可視化：GV10虛擬現(xiàn)實(shí)；GVH計(jì)算機(jī)視覺(jué)

IS智能系統(tǒng)IS1智能系統(tǒng)基本問(wèn)題；1S2搜索和約束滿(mǎn)足：IS3知識(shí)表22核心學(xué)時(shí)

示和知識(shí)推理；1S4高級(jí)搜索；IS5高級(jí)知識(shí)表示和知識(shí)

推理；IS6主體；IS7自然語(yǔ)言處理技術(shù)；IS8機(jī)器學(xué)習(xí)和

神經(jīng)網(wǎng)絡(luò)；IS9人工智能規(guī)劃系統(tǒng)；IS10機(jī)器人

IM信息系統(tǒng)IM1信息模型和信息系統(tǒng)；IM2數(shù)據(jù)庫(kù)系統(tǒng)：IM3數(shù)據(jù)模34核心學(xué)時(shí)

型化；IM4關(guān)系數(shù)據(jù)庫(kù)；IM5數(shù)據(jù)庫(kù)查詢(xún)語(yǔ)言；IM6關(guān)系

數(shù)據(jù)庫(kù)設(shè)計(jì)；IM7事務(wù)處理；IM8分布式數(shù)據(jù)庫(kù)；IM9

物理數(shù)據(jù)庫(kù)設(shè)計(jì)；IM10數(shù)據(jù)挖掘；IM11信息存儲(chǔ)和信息

檢索；IM12超文本和超媒體；IM13多媒體信息和系統(tǒng)；

IM14數(shù)字圖書(shū)館

SE軟件工程SE1軟件設(shè)計(jì)；SE2使用API；SE3軟件工具和環(huán)境；SE454核心學(xué)時(shí)

軟件過(guò)程；SE5軟件需求與規(guī)約（規(guī)格說(shuō)明）；SE6軟件

確認(rèn)；SE7軟件演化；SE8軟件項(xiàng)目管理；SE9基于構(gòu)件

的計(jì)算；SE10形式化方法；SE1I軟件可靠性；SE12特定

系統(tǒng)開(kāi)發(fā)

SP社會(huì)與職業(yè)問(wèn)SP1信息技術(shù)史；SP2信息技術(shù)的社會(huì)環(huán)境：SP3分析方11核心學(xué)時(shí)

題法和分析工具；SP4職業(yè)責(zé)任和道德責(zé)任；SP5基于計(jì)算

機(jī)的系統(tǒng)的系統(tǒng)風(fēng)險(xiǎn)和責(zé)任；SP6知識(shí)產(chǎn)權(quán)；SP7隱私和

公民自由；SP8計(jì)算機(jī)犯罪；SP9與信息技術(shù)相關(guān)的經(jīng)濟(jì)

問(wèn)題

CN數(shù)值計(jì)算科學(xué)CN1數(shù)值分析：CN2運(yùn)籌學(xué)：CN3建模與模擬：CN4高

性能計(jì)算

4.2知識(shí)體系結(jié)構(gòu)簡(jiǎn)介

本節(jié)描述計(jì)算機(jī)科學(xué)與技術(shù)專(zhuān)業(yè)本科階段課程所包含的知識(shí)領(lǐng)域。下面是14個(gè)知識(shí)領(lǐng)域

（area）及其中的知識(shí)單元（units）和知識(shí)點(diǎn)（topics）的描述。在知識(shí)單元級(jí)，我們根據(jù)學(xué)科的現(xiàn)狀

及未來(lái)發(fā)展的需要，區(qū)分出核心內(nèi)容和選修內(nèi)容。凡被列入核心內(nèi)容的是本學(xué)科每個(gè)學(xué)生所

必須掌握的。它們包含了計(jì)算學(xué)科的四大分支學(xué)科的一些最基礎(chǔ)的內(nèi)容。所列的選修內(nèi)容可

以由各校根據(jù)自己的特點(diǎn)、畢'也生的就業(yè)主要面向等因素來(lái)選擇。當(dāng)然，根據(jù)特殊的需要，

各校在實(shí)施中甚至還可以強(qiáng)化一些內(nèi)容、補(bǔ)充一些內(nèi)容：如通信、商務(wù)、經(jīng)濟(jì)、信息安全等。

4.2.1離散結(jié)構(gòu)（DS）

1.內(nèi)容摘要

離散結(jié)構(gòu)是計(jì)算機(jī)科學(xué)的基礎(chǔ)內(nèi)容。之所以這樣說(shuō)，是因?yàn)楹苌儆袑?zhuān)家專(zhuān)門(mén)從事離散結(jié)

構(gòu)的研究。但計(jì)算機(jī)的許多領(lǐng)域都要用到離散結(jié)構(gòu)中的概念。離散結(jié)構(gòu)包括集合論、邏輯學(xué)、

圖論和組合學(xué)等重要內(nèi)容。

數(shù)據(jù)結(jié)構(gòu)和算法分析與設(shè)計(jì)中含有大量離散結(jié)構(gòu)的內(nèi)容。例如：在形式證明、驗(yàn)證、密

碼學(xué)的研究與學(xué)習(xí)中要有理解形式證明的能力。圖論中的概念被用于計(jì)算機(jī)網(wǎng)絡(luò)、操作系統(tǒng)

和編譯系統(tǒng)等領(lǐng)域。集合論的概念被用在軟件工程和數(shù)據(jù)庫(kù)中。

隨著計(jì)算機(jī)科學(xué)與技術(shù)的日益成熟，越來(lái)越完善的分析技術(shù)被用于實(shí)踐，為了理解將來(lái)

的計(jì)算機(jī)科學(xué)技術(shù)，學(xué)生需要對(duì)離散結(jié)構(gòu)有深入的理解。

2.知識(shí)單元描述

DS1函數(shù)、關(guān)系和集合（核心）

知識(shí)點(diǎn)學(xué)習(xí)目標(biāo)

函數(shù)（滿(mǎn)射，到內(nèi)的映射，逆函數(shù)，復(fù)合函數(shù)）①舉例解釋集合、關(guān)系和函數(shù)的基本術(shù)語(yǔ)

關(guān)系（自反，對(duì)稱(chēng)，傳遞，等價(jià)關(guān)系）②舉例說(shuō)明與集合、關(guān)系和函數(shù)的有關(guān)運(yùn)算

集合（文氏圖，補(bǔ)集，笛k兒集，鼎集）③將實(shí)例與合適的集合、函數(shù)和關(guān)系模型關(guān)聯(lián)，并解釋有

鴿籠原理關(guān)的運(yùn)算和術(shù)語(yǔ)

基數(shù)性和可數(shù)性④舉例說(shuō)明：基本計(jì)數(shù)原理，包括對(duì)角線(xiàn)原理和鴿籠原理

的用法

DS2基本邏輯（核心）

知識(shí)點(diǎn)學(xué)習(xí)目標(biāo)

命題邏輯①使用命題邏輯與謂詞邏輯的形式化方法

邏輯連接詞②說(shuō)明符號(hào)邏輯的形式化工具如何給算法和實(shí)際問(wèn)題建模

真值表③用形式邏輯證明和邏輯推理法解決問(wèn)題

范式（合取式和析取式）④說(shuō)明謂詞邏輯的重要性和局限性

永真性

謂詞邏輯

全稱(chēng)量詞和存在量詞

假言推理、否定式推理

謂詞邏輯的局限性

DS3證明技巧（核心）

知識(shí)點(diǎn)學(xué)習(xí)目標(biāo)

蘊(yùn)涵、逆、逆反、置換、非、永假等概念①以實(shí)例概述本單元所述的每種證明技巧的基本結(jié)構(gòu)

形式證明結(jié)構(gòu)②論述對(duì)給定的問(wèn)題哪一種證明是最好的

直接證明③將數(shù)學(xué)歸納法思想與遞歸及遞歸定義結(jié)構(gòu)相聯(lián)系

反例證法④指出數(shù)學(xué)歸納法與強(qiáng)歸納法的差異，并給出相應(yīng)的應(yīng)用

逆反式證明法實(shí)例

反證法

數(shù)學(xué)歸納法

強(qiáng)歸納法

遞歸數(shù)學(xué)定義

良序

DS4計(jì)數(shù)基礎(chǔ)（核心）

知識(shí)點(diǎn)學(xué)習(xí)目標(biāo)

計(jì)數(shù)變?cè)儆?jì)算一個(gè)集合的排列和組合，并解釋在特定應(yīng)用中的意

求和與相乘的規(guī)則義

包含排斥②敘述Master原理的定義

算術(shù)和幾何級(jí)數(shù)③給出各種遞歸方程的解法

斐波那契（Fibonacci）數(shù)列④分析問(wèn)題以建立相關(guān)的遞歸方程，或指出重要的計(jì)數(shù)問(wèn)

排列組合題

基本定義

恒等式

二項(xiàng)式定理

遞歸關(guān)系

實(shí)例

Master原理

DS5圖與樹(shù)（核心）

知識(shí)點(diǎn)學(xué)習(xí)目標(biāo)

樹(shù)①用實(shí)例解釋圖論基本術(shù)語(yǔ)、特性和每種特殊情況

無(wú)向圖②用實(shí)例說(shuō)明樹(shù)和圖遍歷方法的差異

有向圖③用圖和樹(shù)給計(jì)算機(jī)科學(xué)中的問(wèn)題建模

生成樹(shù)④圖和樹(shù)與數(shù)據(jù)結(jié)構(gòu)、算法和計(jì)數(shù)之間的關(guān)系

遍歷策略

DS6離散概率（這部分內(nèi)容由基礎(chǔ)課“概率統(tǒng)計(jì)”完成）

知識(shí)點(diǎn)學(xué)習(xí)目標(biāo)

有限概率空間①對(duì)于如偶然性游戲的基本問(wèn)題計(jì)算事件概率和隨機(jī)變量

概率度量的期望值

事件②依賴(lài)事件與獨(dú)立事件的差異

條件概率③二項(xiàng)式定理應(yīng)用于獨(dú)立事件和貝葉斯規(guī)則應(yīng)用于依賴(lài)事

獨(dú)立性件

貝葉斯規(guī)則④將概率工具應(yīng)用于問(wèn)題的求解，包括如MonteCarlo隨

整型隨機(jī)變量機(jī)方法、算法平均情況分析和散列法

期望

4.2.2程序設(shè)計(jì)基礎(chǔ)（PF）

1.內(nèi)容摘要

熟練掌握程序設(shè)計(jì)語(yǔ)言是學(xué)習(xí)計(jì)算機(jī)科學(xué)與技術(shù)大多數(shù)內(nèi)容的前提，教學(xué)大綱應(yīng)要求學(xué)

生掌握如何使用一種程序設(shè)計(jì)語(yǔ)言。建議學(xué)生至少應(yīng)熟練掌握兩種程序設(shè)計(jì)范例。

程序設(shè)計(jì)基礎(chǔ)領(lǐng)域的知識(shí)由程序設(shè)計(jì)基本概念和程序設(shè)計(jì)技巧組成，這些概念和技巧對(duì)

于獨(dú)立于基本范例的程序設(shè)計(jì)實(shí)踐是重要的。這一領(lǐng)域包括的知識(shí)單元有程序設(shè)計(jì)基本概念、

基本數(shù)據(jù)結(jié)構(gòu)和算法等，這些內(nèi)容很好地覆蓋了計(jì)算機(jī)科學(xué)與技術(shù)專(zhuān)業(yè)的本科生必須了解和

掌握的整個(gè)程序設(shè)計(jì)的知識(shí)范圍。其他知識(shí)領(lǐng)域如程序設(shè)計(jì)語(yǔ)言（PL）和軟件工程（SE）一—也

包含有和程序設(shè)計(jì)相關(guān)的知識(shí)單元，這些知識(shí)單元也是計(jì)算機(jī)科學(xué)與技術(shù)專(zhuān)業(yè)本科教學(xué)大綱

中的核心課程。一般來(lái)說(shuō)，這些知識(shí)單元可以劃歸程序設(shè)計(jì)基礎(chǔ)，也可以劃歸其他的知識(shí)領(lǐng)

域。

2.知識(shí)單元描述

PF1程序設(shè)計(jì)基本結(jié)構(gòu)（核心）

知識(shí)點(diǎn)學(xué)習(xí)目標(biāo)

變量、類(lèi)型、表達(dá)式和語(yǔ)句①分析解釋由基本程序結(jié)構(gòu)組成的簡(jiǎn)單程序（含基本計(jì)算、

高級(jí)語(yǔ)言的基本語(yǔ)法和語(yǔ)義簡(jiǎn)單輸入輸出、條件與重復(fù)結(jié)構(gòu)和函數(shù)）

輸入和輸出基礎(chǔ)②修改和擴(kuò)充簡(jiǎn)單程序

順序、條件和循環(huán)控制結(jié)構(gòu)③設(shè)計(jì)、實(shí)現(xiàn)、測(cè)試和查錯(cuò)

函數(shù)定義、函數(shù)調(diào)用和參數(shù)傳遞④按給定的程序設(shè)計(jì)任務(wù)，選擇相應(yīng)的條件和重復(fù)結(jié)構(gòu)

程序結(jié)構(gòu)分解基礎(chǔ)⑤應(yīng)用結(jié)構(gòu)化技術(shù)分解程序

⑥掌握參數(shù)的傳遞過(guò)程

PF2算法與問(wèn)題求解（核心）

知識(shí)點(diǎn)學(xué)習(xí)目標(biāo)

問(wèn)題求解策略①了解算法在問(wèn)題求解中的重要性

問(wèn)題求解算法②了解一個(gè)好算法的必要特性

算法實(shí)現(xiàn)策略③給簡(jiǎn)單問(wèn)題設(shè)計(jì)算法

調(diào)試策略④解決簡(jiǎn)單問(wèn)題，能用偽代碼或程序設(shè)計(jì)語(yǔ)言實(shí)現(xiàn)算法，

算法的概念和特性并對(duì)該算法作測(cè)試和查錯(cuò)

⑤掌握查錯(cuò)策略

PF3基本數(shù)據(jù)結(jié)構(gòu)（核心）

知識(shí)點(diǎn)學(xué)習(xí)目標(biāo)

基本類(lèi)型①了解基本數(shù)據(jù)和復(fù)合數(shù)據(jù)的表示和用法

數(shù)組②了解數(shù)據(jù)結(jié)構(gòu)在存儲(chǔ)器中的分配和使用

記錄③掌握各種數(shù)據(jù)結(jié)構(gòu)的常見(jiàn)應(yīng)用

字符串和字符串處理④掌握高級(jí)語(yǔ)言實(shí)現(xiàn)用戶(hù)定義數(shù)據(jù)結(jié)構(gòu)的方法

數(shù)據(jù)在存儲(chǔ)器中的表示⑤了解數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)方法的差異

靜態(tài)分配、棧式分配和堆式分配⑥能用數(shù)組、記錄、字符串、鏈表、棧、隊(duì)列和哈希表等

運(yùn)行時(shí)的存儲(chǔ)器管理數(shù)據(jù)結(jié)構(gòu)編寫(xiě)程序

指針和引用⑦了解動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)和靜態(tài)數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)的差異

鏈?zhǔn)浇Y(jié)構(gòu)⑧數(shù)據(jù)結(jié)構(gòu)在問(wèn)題建模中的應(yīng)用

棧、隊(duì)列和哈希表的實(shí)現(xiàn)策略

樹(shù)和圖的實(shí)現(xiàn)策略

數(shù)據(jù)結(jié)構(gòu)的應(yīng)用和選擇策略

PF4遞歸(核心)

知識(shí)點(diǎn)學(xué)習(xí)目標(biāo)

遞歸的概念①解釋遞歸的概念和遞歸應(yīng)用實(shí)例

遞歸數(shù)學(xué)函數(shù)②識(shí)別遞歸定義問(wèn)題的基本情況和?般情況

遞歸過(guò)程③以類(lèi)似階乘問(wèn)題為例，比較循環(huán)和遞歸求解方法的差異

分治法④解釋分治法

回溯法⑤編寫(xiě)、測(cè)試、調(diào)試簡(jiǎn)單的遞歸函數(shù)和遞歸過(guò)程

遞歸的實(shí)現(xiàn)⑥解釋如何利用棧實(shí)現(xiàn)遞歸

⑦通過(guò)實(shí)例解釋回溯法的求解過(guò)程

⑧能確定何時(shí)用遞歸求解

PF5事件驅(qū)動(dòng)程序設(shè)計(jì)(核心)

知識(shí)點(diǎn)學(xué)習(xí)目標(biāo)

事件處理方法編寫(xiě)能響應(yīng)執(zhí)行中異常情況的代碼

事件傳播

異常處理

4.2.3算法與復(fù)雜性(AL)

1.內(nèi)容摘要

對(duì)計(jì)算機(jī)科學(xué)來(lái)說(shuō)，算法(Algorithm)的概念和應(yīng)用是至關(guān)重要的，計(jì)算機(jī)程序的核心

是算法。算法是描述求解問(wèn)題方法的操作步驟或過(guò)程集合，從計(jì)算機(jī)程序的角度來(lái)講，算法

是由若干條指令組成的有窮序列，且滿(mǎn)足下述兒條性質(zhì)：

①輸入：有零個(gè)或多個(gè)由外部提供的量作為算法的輸入；

②輸出：算法產(chǎn)生至少一個(gè)量作為輸出；

③確定性：組成算法的每條指令的操作功能是唯一的：

④有限性：算法中每條指令的執(zhí)行次數(shù)和時(shí)間是有限的。

早在計(jì)算機(jī)發(fā)明之前，算法就是數(shù)學(xué)家求解問(wèn)題的工具。數(shù)學(xué)家用算法來(lái)描述特定問(wèn)題

的求解方法，例如，數(shù)學(xué)家給出求解兩個(gè)整數(shù)的最大公約數(shù)的具體算法如下：

①令M為兩個(gè)整數(shù)中的較大者，N為兩個(gè)整數(shù)中的較小者；

②用M除以N,令R為余數(shù)；

③若R不等于0,則令M等于N,N等于R,返回步驟②繼續(xù)；若R等于0,則N中的

數(shù)值就是兩個(gè)整數(shù)的最大公約數(shù)。

算法給出了對(duì)求解特定問(wèn)題方法的指導(dǎo)，人們可以按照算法描述的求解步驟一步一步得

到正確的結(jié)果。算法可以在人類(lèi)之間傳遞智能，如果我們把人類(lèi)求解問(wèn)題的方法設(shè)計(jì)成計(jì)算

機(jī)能夠理解的算法，然后把這樣的算法傳遞給計(jì)算機(jī)，并讓計(jì)算機(jī)執(zhí)行這樣的算法，那么，

計(jì)算機(jī)就繼承了人類(lèi)計(jì)算智能而求解出問(wèn)題的結(jié)果，計(jì)算機(jī)執(zhí)行的這個(gè)算法就是程序。

算法不等于程序，程序是算法用某種程序設(shè)計(jì)語(yǔ)言的具體實(shí)現(xiàn)。因此，在計(jì)算機(jī)硬件基

礎(chǔ)上，開(kāi)發(fā)程序的第一步就是學(xué)習(xí)求解特定問(wèn)題的算法。

2.知識(shí)單元描述

AL1算法分析基礎(chǔ)（核心）

知識(shí)點(diǎn)學(xué)習(xí)目標(biāo)

復(fù)雜性上界和平均復(fù)雜性的漸近分析①解釋記號(hào)大0,小0,Q和9的用法，以描述算法所做

最佳、最差和平均情況下的復(fù)雜性差異的工作量

大o,小o,Q和e符號(hào)②用大o,。和e記號(hào)表示算法的時(shí)間和空間復(fù)雜性的漸

標(biāo)準(zhǔn)復(fù)雜性類(lèi)近上界、下界和嚴(yán)格界

性能的經(jīng)驗(yàn)度量③確定簡(jiǎn)單算法的時(shí)間和空間復(fù)雜性

算法時(shí)間、空間復(fù)雜性的權(quán)衡④推導(dǎo)遞歸關(guān)系以描述由遞歸定義的算法的時(shí)間復(fù)雜性

用遞歸關(guān)系分析遞歸算法⑤解決簡(jiǎn)單的遞歸關(guān)系

AL2算法策略（核心）

知識(shí)點(diǎn)學(xué)習(xí)目標(biāo)

窮舉算法①描述窮舉法的缺點(diǎn)

貪心算法②對(duì)各種算法（窮舉算法，貪心算法，分治算法，回溯法，

分治算法分支界限法和試探法），用人們?nèi)粘Ｐ袨榈睦觼?lái)加以說(shuō)明

回溯法.③實(shí)現(xiàn)解決一個(gè)合適問(wèn)題的貪心算法

分支界限法④實(shí)現(xiàn)解決?個(gè)合適問(wèn)題的分治算法

試探法⑤用回溯法解決諸如走迷宮這樣的問(wèn)題

模式匹配和字符串/文本匹配算法⑥描述各種試探法的解題方法

數(shù)值逼近算法⑦用模式匹配算法分析子字符串

⑧用數(shù)值逼近方法解決如求解多項(xiàng)式的根這樣的數(shù)學(xué)問(wèn)題

AL3基本算法（核心）

知識(shí)點(diǎn)學(xué)習(xí)目標(biāo)

簡(jiǎn)單數(shù)值算法①實(shí)現(xiàn)最常用的二次排序和0（NlogN）算法

順序查找算法和折半查找算法②對(duì)?個(gè)應(yīng)用問(wèn)題設(shè)計(jì)一個(gè)合適的哈希函數(shù)并加以實(shí)現(xiàn)

二次排序算法（選擇排序，插入排序）③對(duì)哈希表設(shè)計(jì)?個(gè)解決沖突的算法并加以實(shí)現(xiàn)

復(fù)雜度為O（NlogN）排序算法（快速排序，堆排④討論排序、搜索和哈希的主要算法的計(jì)算效率

序，歸并排序）⑤討論那些與計(jì)算效率不同的影響算法選擇的其他因素，

哈希（Hash）表，包括沖突消解策略如編程時(shí)間、維護(hù)和輸人數(shù)據(jù)中的特殊應(yīng)用模式

二叉查找樹(shù)⑥用基本的圖算法解決問(wèn)題，包括深度優(yōu)先遍歷和廣度優(yōu)

圖的表示（鄰接表，鄰接矩陣）先遍歷，單源最短路徑和所有的最近點(diǎn)對(duì)問(wèn)路徑，傳遞閉

深度優(yōu)先遍歷、廣度優(yōu)先遍歷包，拓?fù)渑判蚝椭辽僖环N最小生成樹(shù)算法

最短路徑算法（Dijkstra和Floyd算法）⑦具有算法評(píng)價(jià)、選擇合適的算法且給出理由以及在指定

傳遞閉包（Floyd算法）程序設(shè)計(jì)環(huán)境F實(shí)現(xiàn)算法的能力

最小生成樹(shù)（Prim算法和Kruskal算法）

拓?fù)渑判?/p>

AL4分布式算法（核心）

知識(shí)點(diǎn)學(xué)習(xí)目標(biāo)

一致性和選擇①解釋分布式范例

終止探測(cè)②解釋一個(gè)簡(jiǎn)單分布式算法

容錯(cuò)③確定何時(shí)使用?致性算法或選擇算法

穩(wěn)定性④區(qū)分邏輯時(shí)鐘和物理時(shí)鐘

⑤描述分布式算法中的事件相對(duì)順序

AL5可計(jì)算性理論基礎(chǔ)（核心）

知識(shí)點(diǎn)學(xué)習(xí)目標(biāo)

有限狀態(tài)自動(dòng)機(jī)①討論有限自動(dòng)機(jī)概念

上下文無(wú)關(guān)文法②解釋上下文無(wú)關(guān)文法

易解問(wèn)題和難解問(wèn)題③設(shè)計(jì)?個(gè)確定的有限狀態(tài)自動(dòng)機(jī)接受指定語(yǔ)言

不可計(jì)算函數(shù)④解釋什么叫“?些問(wèn)題算法不可解”

停機(jī)問(wèn)題⑤舉例說(shuō)明不可計(jì)算性的概念

不可計(jì)算性的含義

AL6復(fù)雜性類(lèi)：P類(lèi)和NP類(lèi)（選修）

知識(shí)點(diǎn)學(xué)習(xí)目標(biāo)

P類(lèi)和NP類(lèi)的定義①定義P類(lèi)，NP類(lèi)

NP完全性②解釋NP完全性的意義

基本的NP完全問(wèn)題③通過(guò)把已知的NP完全問(wèn)題歸約成要研究的問(wèn)題來(lái)證明

歸約技術(shù)要研究的問(wèn)題是NP完全的

AL7自動(dòng)機(jī)理論（選修）

知識(shí)點(diǎn)學(xué)習(xí)目標(biāo)

確定的有限自動(dòng)機(jī)（DFA）①確定一個(gè)語(yǔ)言在Chomsky文法分類(lèi)結(jié)構(gòu)中的位置（正則

非確定的有限自動(dòng)機(jī)（NFA）集，上下文無(wú)關(guān)，上下文有關(guān)和遞歸可列枚舉語(yǔ)言）

DFA和NFA的等價(jià)性②證明?個(gè)語(yǔ)言在?個(gè)特定的類(lèi)中并且不能在低層的類(lèi)中

正則表達(dá)式③語(yǔ)言的轉(zhuǎn)換，包括在DFA、NFA和正則表達(dá)式間以及

正則表達(dá)式的泵引理PDA和CFG之間的相互轉(zhuǎn)換

下推自動(dòng)機(jī)（PDA）④解釋自頂向卜.分析和自底向上分析算法（至少各解釋一

PDA和上下文無(wú)關(guān)文法的關(guān)系種）

上下文無(wú)關(guān)文法的特性⑤解釋Church-Hiring論題及其重要性

圖靈機(jī)

非確定的圖靈機(jī)

集合和語(yǔ)言

Chomsky文法分類(lèi)

Church-TUring論題

AL8高級(jí)算法分析（選修）

知識(shí)點(diǎn)學(xué)習(xí)目標(biāo)

退火算法分析①為未定數(shù)據(jù)結(jié)構(gòu)的退火分析算法提供一種方法及其相應(yīng)

聯(lián)機(jī)算法和脫機(jī)算法的函數(shù)

隨機(jī)算法②解釋為何競(jìng)爭(zhēng)分析是聯(lián)機(jī)算法的合適度量標(biāo)準(zhǔn)

動(dòng)態(tài)程序設(shè)計(jì)③解釋隨機(jī)算法在難以用確定算法或確定的算法更難的設(shè)

組合優(yōu)化計(jì)問(wèn)題中的作用

④用動(dòng)態(tài)程序設(shè)計(jì)方法實(shí)現(xiàn)問(wèn)題求解

AL9加密算法（選修）

知識(shí)點(diǎn)學(xué)習(xí)目標(biāo)

密碼學(xué)史回顧①描述有效的基本數(shù)論算法，包括最大公約數(shù)算法，模n

私鑰密碼和密鑰交換問(wèn)題的乘法逆元算法和數(shù)的募次算法

公鑰密碼②描述至少一種公鑰密碼系統(tǒng)，包括對(duì)安全必需的復(fù)雜性

數(shù)字簽名理論的假設(shè)

安全協(xié)議③使用現(xiàn)有的協(xié)議和密碼原語(yǔ)，作密碼協(xié)議的簡(jiǎn)單擴(kuò)充

應(yīng)用（零知識(shí)證明，認(rèn)證系統(tǒng)等等）

AL10幾何算法（選修）

知識(shí)點(diǎn)學(xué)習(xí)目標(biāo)

線(xiàn)段的性質(zhì)和線(xiàn)段相交性①描述和給出至少兩個(gè)求凸包算法的時(shí)間分析

求凸包算法②驗(yàn)證求凸包算法的復(fù)雜度下限是Omega（NlogN）

③描述至少一種其他的有效幾何算法,如找最近點(diǎn)對(duì)算法，

求凸層算法，求最大層算法

AL11并行算法（選修）

知識(shí)點(diǎn)學(xué)習(xí)目標(biāo)

PRAM模型①描述PRAM上鏈表的實(shí)現(xiàn)

互斥讀寫(xiě)與并發(fā)讀寫(xiě)②用前置并行操作進(jìn)行簡(jiǎn)單的有效并行計(jì)算

指針跳轉(zhuǎn)③解釋Brent定理和有關(guān)方面

Brent定理和工作效率

4.2.4計(jì)算機(jī)組織與體系結(jié)構(gòu)（AR）

1.內(nèi)容摘要

本課程介紹計(jì)算機(jī)系統(tǒng)的組織結(jié)構(gòu)，以馮?諾依曼模型作為教學(xué)起點(diǎn)，進(jìn)而介紹較新的

計(jì)算機(jī)組織結(jié)構(gòu)體系。作為計(jì)算機(jī)科學(xué)與技術(shù)專(zhuān)業(yè)的本科生，應(yīng)當(dāng)對(duì)計(jì)算機(jī)的內(nèi)部結(jié)構(gòu)、功

能部件、功能特征、性能以及交互方式有所了解，而不應(yīng)當(dāng)把它看作一個(gè)執(zhí)行程序的黑盒子。

學(xué)生還應(yīng)當(dāng)了解計(jì)算機(jī)的系統(tǒng)結(jié)構(gòu)，以便在編寫(xiě)程序時(shí)能根據(jù)計(jì)算機(jī)的特征編寫(xiě)出更加高效

的程序。在選擇計(jì)算機(jī)產(chǎn)品方面，應(yīng)當(dāng)能夠理解各種部件選擇之間的權(quán)衡，如CPU、時(shí)鐘頻

率和存儲(chǔ)器容量等。

2.知識(shí)單元描述

AR1數(shù)字邏輯與數(shù)字系統(tǒng)（核心）

知識(shí)點(diǎn)學(xué)習(xí)目標(biāo)

計(jì)算機(jī)發(fā)展歷史回顧①描述計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)從電子管到超大規(guī)模集成電路的發(fā)

基本的組成元件（邏輯門(mén)，觸發(fā)器，計(jì)數(shù)器，寄展過(guò)程

存器，PLA）②展示計(jì)算機(jī)的基本模塊的工作原理，及其在計(jì)算機(jī)系統(tǒng)

邏輯表達(dá)式，最小化，寄存器傳輸?shù)谋硎?，物發(fā)展中的歷史作用

理特性（門(mén)延遲，扇入，扇出）③使用數(shù)學(xué)表達(dá)式描述簡(jiǎn)單的組合電路和時(shí)序電路的功能

計(jì)算機(jī)的基本組成，硬件結(jié)構(gòu)，軟件的概念，④解釋典型的馮?諾依曼機(jī)器的結(jié)構(gòu)及其主要功能模塊

計(jì)算機(jī)語(yǔ)言及其編譯計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)的概念，⑤用功能模塊設(shè)計(jì)一個(gè)簡(jiǎn)單的電路

性能評(píng)價(jià)

AR2數(shù)據(jù)的機(jī)器級(jí)表示（核心）

知識(shí)點(diǎn)學(xué)習(xí)目標(biāo)

數(shù)值表示和數(shù)制①解釋使用不同數(shù)據(jù)表示方式的理由

定點(diǎn)數(shù)和浮點(diǎn)數(shù)系統(tǒng)②解釋原碼和補(bǔ)碼是如何表示負(fù)數(shù)的

有符號(hào)數(shù)的表示方法和基本運(yùn)算方法③數(shù)制及其轉(zhuǎn)換的原理

非數(shù)值數(shù)據(jù)的表示（如字符代碼和圖象數(shù)據(jù)）④討論定長(zhǎng)數(shù)據(jù)表示如何影響數(shù)據(jù)表示的精度

系統(tǒng)可靠性與糾錯(cuò)碼⑤描述非數(shù)值數(shù)據(jù)在計(jì)算機(jī)內(nèi)部的表示方法

數(shù)據(jù)運(yùn)算器的結(jié)構(gòu)⑥描述字符、字符串、記錄和數(shù)組在計(jì)算機(jī)內(nèi)部的表示方

法

AR3匯編級(jí)機(jī)器組織（核心）

知識(shí)點(diǎn)學(xué)習(xí)目標(biāo)

指令格式①概述機(jī)器指令和匯編指令的表示方式

數(shù)據(jù)的存儲(chǔ)方式與尋址方式②解釋不同的指令格式，如不同的地址碼數(shù)量和不同的指

指令集及其分類(lèi)（數(shù)據(jù)操作，控制，輸入輸出）令的長(zhǎng)度

子程序調(diào)用和返回機(jī)制③編寫(xiě)簡(jiǎn)單的匯編語(yǔ)言程序段

匯編語(yǔ)言和機(jī)器語(yǔ)言編程基礎(chǔ)④解釋高級(jí)語(yǔ)言的結(jié)構(gòu)如何在機(jī)器語(yǔ)言層次上表示

⑤解釋在匯編層次上如何實(shí)現(xiàn)子程序的調(diào)用

AR4存儲(chǔ)系統(tǒng)組織和結(jié)構(gòu)（核心）

知識(shí)點(diǎn)學(xué)習(xí)目標(biāo)

存儲(chǔ)器件類(lèi)型及其工作原理①識(shí)別存儲(chǔ)技術(shù)的主要類(lèi)型

主存儲(chǔ)器的組織和操作②解釋訪(fǎng)問(wèn)存儲(chǔ)的時(shí)間延遲效應(yīng)

存儲(chǔ)器的延遲，工作周期，帶寬提高和交叉存③解釋層次化存儲(chǔ)器在減少實(shí)際訪(fǎng)存延遲上的應(yīng)用

儲(chǔ)技術(shù)④描述存儲(chǔ)管理的原理

層次化存儲(chǔ)系統(tǒng)⑤描述cache和虛擬存儲(chǔ)器的作用

高速緩沖存儲(chǔ)器（地址映射，塊大小，替換和更⑥解釋具有虛擬存儲(chǔ)器管理的系統(tǒng)的工作原理

新機(jī)制）

虛擬存儲(chǔ)器（頁(yè)表，TLB快表）

AR5接口和通信（核心）

知識(shí)點(diǎn)學(xué)習(xí)目標(biāo)

輸入輸出基本原理，信號(hào)交換，緩沖存儲(chǔ)①解釋中斷是如何用于實(shí)現(xiàn)I/O控制和數(shù)據(jù)傳輸?shù)?/p>

程序控制I/O,中斷驅(qū)動(dòng)I/O,DMA②認(rèn)識(shí)計(jì)算機(jī)系統(tǒng)中的各種類(lèi)型的總線(xiàn)

中斷結(jié)構(gòu)，向量化和優(yōu)先級(jí)化，中斷識(shí)別③描述從磁盤(pán)上進(jìn)行數(shù)據(jù)訪(fǎng)問(wèn)的過(guò)程

外部存儲(chǔ)器的物理組織及驅(qū)動(dòng)④描述RAID系統(tǒng)結(jié)構(gòu)的優(yōu)點(diǎn)及其實(shí)現(xiàn)方法

總線(xiàn)和總線(xiàn)協(xié)議，仲裁機(jī)構(gòu)和直接存儲(chǔ)器存?、菝枋鼋涌谥腥绾沃С侄嗝襟w數(shù)據(jù)的傳輸

（DMA）

多媒體支持

RAID系統(tǒng)結(jié)構(gòu)

AR6功能組織（核心）

知識(shí)點(diǎn)學(xué)習(xí)目標(biāo)

簡(jiǎn)單的數(shù)據(jù)通路實(shí)現(xiàn)①解釋指令在典型的馮?諾依曼計(jì)算機(jī)上的指令過(guò)程

控制單元，硬連線(xiàn)實(shí)現(xiàn)和微程序?qū)崿F(xiàn)②解釋中斷的基本概念

指令讀取、解碼和執(zhí)行③比較各種數(shù)據(jù)通路的構(gòu)成

異常與中斷④討論控制點(diǎn)的概念，以及用硬連線(xiàn)和微程序生成控制信

指令流水技術(shù)，指令級(jí)并行（ILP）技術(shù)與循環(huán)級(jí)號(hào)的方法

并行技術(shù)⑤解釋基本的指令級(jí)并行性，及其數(shù)據(jù)相關(guān)性

AR7多處理和其他系統(tǒng)結(jié)構(gòu)（核心）

知識(shí)點(diǎn)學(xué)習(xí)目標(biāo)

SIMD,MIMD,VLIW和EPIC①討論在傳統(tǒng)的馮?諾依曼上進(jìn)行并行處理的概念

網(wǎng)絡(luò)互聯(lián)（超立方體，混洗交換，網(wǎng)格結(jié)構(gòu)，交②描述其他系統(tǒng)結(jié)構(gòu)，如SIMD、MIMD和超長(zhǎng)指令字

叉開(kāi)關(guān)結(jié)構(gòu)）③解釋互連網(wǎng)絡(luò)的概念以及各種互連網(wǎng)絡(luò)結(jié)構(gòu)的特點(diǎn)

共享存儲(chǔ)系統(tǒng)④討論多處理機(jī)系統(tǒng)的特殊問(wèn)題，包括存儲(chǔ)器管理，描述

cache?致性如何解決這些問(wèn)題

存儲(chǔ)模型和存儲(chǔ)一致性

AR8性能提高技術(shù)（選修）

知識(shí)點(diǎn)學(xué)習(xí)目標(biāo)

超標(biāo)量體系結(jié)構(gòu)①描述超標(biāo)量系統(tǒng)結(jié)構(gòu)及其優(yōu)點(diǎn)

分支預(yù)測(cè)②解釋分支預(yù)測(cè)的概念及其效果

指令預(yù)?、勖枋鲋噶铑A(yù)取的代價(jià)及其好處

推測(cè)執(zhí)行④解釋推測(cè)執(zhí)行的原理

多線(xiàn)程⑤討論多線(xiàn)程系統(tǒng)結(jié)構(gòu)的性能優(yōu)勢(shì)及其實(shí)現(xiàn)上的困難

AR9網(wǎng)絡(luò)與分布式系統(tǒng)結(jié)構(gòu)（選修）

知識(shí)點(diǎn)學(xué)習(xí)目標(biāo)

LAN與WAN①解釋基本的網(wǎng)絡(luò)構(gòu)成原理，以及LAN與WAN的區(qū)別

網(wǎng)絡(luò)的分層協(xié)議②討論網(wǎng)絡(luò)層次化協(xié)議的設(shè)計(jì)問(wèn)題

分布式算法對(duì)系統(tǒng)結(jié)構(gòu)的影響③解釋網(wǎng)絡(luò)系統(tǒng)與分布式系統(tǒng)的區(qū)別

網(wǎng)絡(luò)計(jì)算④討論與網(wǎng)絡(luò)計(jì)算和分布式多媒體有關(guān)的問(wèn)題。

分布式多媒體

4.2.5操作系統(tǒng)（OS）

1.內(nèi)容摘要

操作系統(tǒng)是硬件性能的抽象，人們通過(guò)它來(lái)控制硬件。它也進(jìn)行計(jì)算機(jī)用戶(hù)間的資源分

配工作。這門(mén)課主要講述影響現(xiàn)代操作系統(tǒng)設(shè)計(jì)的各種因素及實(shí)際操作。

近些年來(lái)操作系統(tǒng)和其抽象機(jī)制相對(duì)手應(yīng)用軟件變得更加復(fù)雜，這就要求學(xué)生在系統(tǒng)學(xué)

習(xí)內(nèi)部算法實(shí)現(xiàn)和數(shù)據(jù)結(jié)構(gòu)之前對(duì)操作系統(tǒng)有比較深入的理解。因而課程設(shè)置不僅強(qiáng)調(diào)了操

作系統(tǒng)的使用（外部特性），更強(qiáng)調(diào)它的設(shè)計(jì)和實(shí)現(xiàn)（內(nèi)部特性）。操作系統(tǒng)中的許多思想也可用

于計(jì)算機(jī)的其他領(lǐng)域，如并發(fā)程序設(shè)計(jì)、算法設(shè)計(jì)和實(shí)現(xiàn)、虛擬環(huán)境的創(chuàng)建、安全系統(tǒng)的創(chuàng)

建及網(wǎng)絡(luò)管理等。

2.知識(shí)單元描述

OS1操作系統(tǒng)概述（核心）

知識(shí)點(diǎn)學(xué)習(xí)目標(biāo)

操作系統(tǒng)的作用和目的①闡述現(xiàn)代操作系統(tǒng)的目標(biāo)和功能

操作系統(tǒng)的發(fā)展歷史②介紹操作系統(tǒng)如何從最早的批處理系統(tǒng)發(fā)展成為復(fù)雜的

操作系統(tǒng)的特征和功能多用戶(hù)系統(tǒng)

支持客戶(hù)一服務(wù)器模型和手提設(shè)備的機(jī)制③分析操作系統(tǒng)設(shè)計(jì)中存在的平衡問(wèn)題

有關(guān)有效性、健壯性、靈活性、可移植性、安④介紹最新操作系統(tǒng)在使用方便、運(yùn)算效率、演化能力方

全性、兼容性的設(shè)計(jì)問(wèn)題面的功能

安全性、網(wǎng)絡(luò)化、多媒體、視窗所帶來(lái)的影響⑤分析討論網(wǎng)絡(luò)操作系統(tǒng)、客戶(hù)——服務(wù)器操作系統(tǒng)、分

布式操作系統(tǒng)及它們與單用戶(hù)操作系統(tǒng)的不同之處

⑥充分認(rèn)識(shí)對(duì)操作系統(tǒng)的潛在威脅，以及所需采取的安全

防范措施

⑦介紹公開(kāi)源程序和Internet的廣泛使用等方面對(duì)操作系

統(tǒng)設(shè)計(jì)帶來(lái)的影響

OS2操作系統(tǒng)原理（核心）

知識(shí)點(diǎn)學(xué)習(xí)目標(biāo)

結(jié)構(gòu)化方法（整體的、分層的、模塊化的、微內(nèi)①闡述邏輯層的概念

核模型）②闡述在分層模式下建立抽象層的好處

抽象、進(jìn)程、資源③說(shuō)明應(yīng)用程序接口（API）和中間件的需求

應(yīng)用程序接口（API）的基本概念④解釋計(jì)算資源是如何被應(yīng)用軟件使用，被系統(tǒng)軟件管理

應(yīng)用的需求以及軟、硬件技術(shù)的發(fā)展⑤比較操作系統(tǒng)中的用戶(hù)態(tài)和核心態(tài)

設(shè)備的組織⑥論述使用中斷處理的優(yōu)缺點(diǎn)

中斷的方法和實(shí)現(xiàn)⑦比較幾種構(gòu)造操作系統(tǒng)結(jié)構(gòu)的方法，如：面向?qū)ο蟆⒛?/p>

用戶(hù)系統(tǒng)狀態(tài)及其保護(hù)，以及用戶(hù)/系統(tǒng)狀態(tài)轉(zhuǎn)塊化、微內(nèi)核、分層

換到核心態(tài)的原理⑧論述設(shè)備隊(duì)列和輸入輸出驅(qū)動(dòng)隊(duì)列的用途

OS3并發(fā)性（核心）

知識(shí)點(diǎn)學(xué)習(xí)目標(biāo)

狀態(tài)和狀態(tài)圖①闡述操作系統(tǒng)框架中的并發(fā)需求

就緒隊(duì)列、進(jìn)程控制塊等的結(jié)構(gòu)②演示由于并行處理多個(gè)獨(dú)立任務(wù)而可能引起運(yùn)行問(wèn)題

調(diào)度和狀態(tài)轉(zhuǎn)換③總結(jié)可以使用操作系統(tǒng)去實(shí)現(xiàn)并發(fā)系統(tǒng)的機(jī)制范圍，并

中斷的作用論述它們的優(yōu)點(diǎn)

并發(fā)執(zhí)行的優(yōu)點(diǎn)和缺點(diǎn)④闡述一個(gè)任務(wù)所要經(jīng)過(guò)的各種不同的狀態(tài)和多任務(wù)管理

互斥問(wèn)題和?些解決的方法所需要的數(shù)據(jù)結(jié)構(gòu)

死鎖的產(chǎn)生、條件及其預(yù)防措施⑤總結(jié)操作系統(tǒng)中互斥問(wèn)題的各種解決方法

信號(hào)量、監(jiān)控、條件變量、聚集的模型和機(jī)制⑥解釋在操作系統(tǒng)中為了支持并發(fā)而采用的中斷、分派、

生產(chǎn)者一消費(fèi)者問(wèn)題和同步狀態(tài)轉(zhuǎn)換的理由

多處理器自旋鎖定和重入的問(wèn)題⑦為簡(jiǎn)單問(wèn)題域建立狀態(tài)圖和轉(zhuǎn)換圖

⑧討論在管理并發(fā)過(guò)程中使用的數(shù)據(jù)結(jié)構(gòu)（如：堆棧，隊(duì)列）

⑨論述產(chǎn)生死鎖的條件

OS4調(diào)度與分派（核心）

知識(shí)點(diǎn)學(xué)習(xí)目標(biāo)

搶占和非搶占調(diào)度①比較操作系統(tǒng)中采用的搶占和非搶占的任務(wù)調(diào)度常用算

調(diào)度和策略法，比如：優(yōu)先級(jí)、性能比較、平均分配

進(jìn)程和線(xiàn)程②論述調(diào)度算法和應(yīng)用領(lǐng)域的關(guān)系

里程碑和實(shí)時(shí)問(wèn)題③論述處理器調(diào)度的不同類(lèi)型，如短期、中期、長(zhǎng)期和I/O

④論述進(jìn)程和線(xiàn)程的區(qū)別

⑤比較靜態(tài)和動(dòng)態(tài)實(shí)時(shí)調(diào)度方法

⑥論述搶占調(diào)度和底線(xiàn)調(diào)度的需求

⑦找出邏輯上嵌入在調(diào)度算法中可用于其他與計(jì)算無(wú)關(guān)的

領(lǐng)域（如磁盤(pán)1/0、網(wǎng)絡(luò)調(diào)度、工程項(xiàng)目調(diào)度，以及其他與

計(jì)算無(wú)關(guān)的問(wèn)題等）的方法

OS5內(nèi)存管理（核心）

知識(shí)點(diǎn)學(xué)習(xí)目標(biāo)

物理內(nèi)存和內(nèi)存管理硬件的回顧①闡述內(nèi)存層次和費(fèi)用一性能折衷

覆蓋、交換、分區(qū)②論述虛擬內(nèi)存的原理及如何在硬件和軟件中實(shí)現(xiàn)

內(nèi)存分頁(yè)和分段③總結(jié)適用于高速緩存、內(nèi)存分頁(yè)、分段虛擬內(nèi)存的原理

分配和淘汰策略④評(píng)估內(nèi)存（主存、高速緩存、輔存）的大小和處理器速度

工作集和系統(tǒng)顛簸的權(quán)衡

高速緩存⑤講解分配內(nèi)存的不同方法，并舉例說(shuō)明它們各自的優(yōu)點(diǎn)

⑥論述使用高速緩存的原因

⑦比較內(nèi)存分頁(yè)和分段技術(shù)

⑧論述系統(tǒng)顛簸的原理、產(chǎn)生的原因以及發(fā)現(xiàn)和解決問(wèn)題

的技術(shù)

⑨分析幾種不同的內(nèi)存分配技術(shù)，包括：覆蓋、交換、分

配和淘汰策略

OS6設(shè)備管理（核心）

知識(shí)點(diǎn)學(xué)習(xí)目標(biāo)

串行和并行設(shè)備的特點(diǎn)①闡述串行和并行設(shè)備的主要區(qū)別，并且了解在什么情況

設(shè)備的分類(lèi)卜.用哪種設(shè)備更合適

緩沖策略②掌握操作系統(tǒng)中的物理硬件和虛擬設(shè)備之間的關(guān)系

直接存儲(chǔ)器訪(fǎng)問(wèn)（DMA）③論述緩沖及其實(shí)現(xiàn)方法

故障恢復(fù)④區(qū)分從設(shè)備（包括：手提設(shè)備、網(wǎng)絡(luò)、多媒體）到計(jì)算機(jī)

的接口機(jī)制，并闡述它們與操作系統(tǒng)設(shè)計(jì)相關(guān)的部分

⑤論述直接內(nèi)存訪(fǎng)問(wèn)的優(yōu)點(diǎn)和缺點(diǎn)，并指出其使用的環(huán)境

⑥認(rèn)識(shí)故障恢復(fù)的需求

⑦設(shè)計(jì)一個(gè)簡(jiǎn)單的設(shè)備驅(qū)動(dòng)器程序

OS7安全與保護(hù)（核心）

知識(shí)點(diǎn)學(xué)習(xí)目標(biāo)

系統(tǒng)安全概論①認(rèn)識(shí)安全和保