教學(xué)課件-計算機(jī)科學(xué)導(dǎo)論-董榮勝

計算機(jī)科學(xué)導(dǎo)論—思想與方法第一章緒論本章首先簡單介紹計算學(xué)科命名的背景、計算學(xué)科的定義，以及計算學(xué)科的根本問題，并闡述了計算學(xué)科專業(yè)名稱的演變、分支學(xué)科及其培養(yǎng)側(cè)重點。然后，介紹計算機(jī)科學(xué)、計算機(jī)工程、軟件工程和信息技術(shù)等4個主要分支學(xué)科的知識體和核心課程。最后，提出“計算機(jī)導(dǎo)論”課程的構(gòu)建問題，介紹課程的結(jié)構(gòu)設(shè)計，以及結(jié)構(gòu)設(shè)計的基礎(chǔ)，即計算學(xué)科認(rèn)知模型——計算學(xué)科二維定義矩陣的概念。1.1引言本節(jié)的目的在于，讓學(xué)生了解計算學(xué)科的定義，學(xué)科的根本問題，為后繼章節(jié)的學(xué)習(xí)做個簡單鋪墊。

1.1.1計算學(xué)科命名的背景如何認(rèn)知計算學(xué)科，有著不少爭論。1984年7月，美國計算機(jī)科學(xué)與工程博士單位評審部的領(lǐng)導(dǎo)們，在猶他州召開的會議上對計算認(rèn)知問題進(jìn)行了討論。這一討論以及其他類似討論促使（美國）計算機(jī)協(xié)會（ACM）與（美國）電氣和電子工程師學(xué)會計算機(jī)分會（IEEE/CS）于1985年春聯(lián)手組成任務(wù)組，經(jīng)過近4年的工作，任務(wù)組提交了在計算教育史上具有里程碑意義的“計算作為一門學(xué)科”（ComputingasaDiscipline）報告，報告論證了計算作為一門學(xué)科的事實，回答了計算學(xué)科中長期以來一直爭論的一些問題，并將當(dāng)時的計算機(jī)科學(xué)、計算機(jī)工程、計算機(jī)科學(xué)和工程、計算機(jī)信息學(xué)以及其他類似名稱的專業(yè)及其研究范疇統(tǒng)稱為計算學(xué)科。1.1.2計算學(xué)科的定義計算學(xué)科是對描述和變換信息的算法過程進(jìn)行的系統(tǒng)研究，包括理論、分析、設(shè)計、效率、實現(xiàn)和應(yīng)用等。計算學(xué)科包括對計算過程的分析以及計算機(jī)的設(shè)計和使用。該學(xué)科的廣泛性在下面一段來自美國計算科學(xué)鑒定委員會發(fā)布的報告摘錄中得到強(qiáng)調(diào)：計算學(xué)科的研究包括從算法與可計算性的研究到根據(jù)可計算硬件和軟件的實際實現(xiàn)問題的研究。這樣，計算學(xué)科不但包括從總體上對算法和信息處理過程進(jìn)行研究的內(nèi)容，也包括滿足給定規(guī)格要求的有效而可靠的軟硬件設(shè)計—它包括所有科目的理論研究、實驗方法和工程設(shè)計。1.1.3計算學(xué)科的根本問題學(xué)科的根本問題是：什么能被（有效地）自動進(jìn)行。計算學(xué)科來源于對算法理論、數(shù)理邏輯、計算模型、自動計算機(jī)器的研究，并與存儲式電子計算機(jī)的發(fā)明一起形成于20世紀(jì)40年代初期。1.2專業(yè)名稱的演變，學(xué)科描述及培養(yǎng)側(cè)重點計算學(xué)科現(xiàn)已成為一個龐大的學(xué)科，無論是教師，學(xué)校，還是學(xué)生和家長都希望有一份權(quán)威性的報告來了解學(xué)科的相關(guān)情況。為此，IEEE/CS和ACM任務(wù)組作了大量的工作，并于2001至2005年，分別提交了計算機(jī)科學(xué)（ComputerScience，簡稱CS），信息系統(tǒng)（InformationSystem，簡稱IS），軟件工程（SoftwareEngineering，簡稱SE），計算機(jī)工程（ComputerEngineering，簡稱CE），信息技術(shù)（InformationTechnology，簡稱IT）等5個分支學(xué)科（專業(yè)）的教程以及相應(yīng)的總報告（圖1-1），給出了5個分支學(xué)科的知識體以及相應(yīng)的核心課程，為各專業(yè)教學(xué)計劃的設(shè)計奠定了基礎(chǔ)，同時也為公眾認(rèn)知和選擇這些專業(yè)提供幫助。CC2005OverviewCC2001(CS2001)計算機(jī)科學(xué)IS2002信息系統(tǒng)SE2004軟件工程CE2005計算機(jī)工程IT2005信息技術(shù)其它教程新增專業(yè)根據(jù)我國高校的情況，我國教育部高等學(xué)校計算機(jī)科學(xué)與技術(shù)教學(xué)指導(dǎo)委員會（簡稱“計算機(jī)教指委”）制訂的《高等學(xué)校計算機(jī)科學(xué)與技術(shù)發(fā)展戰(zhàn)略研究報告暨專業(yè)規(guī)范（試行）》（高等教育出版社出版2006年9月出版，簡稱“計算機(jī)專業(yè)規(guī)范”）采納了CC2005報告中的四個分支學(xué)科，并以專業(yè)方向的形式進(jìn)行規(guī)范，它們是：計算機(jī)科學(xué)，計算機(jī)工程，軟件工程，信息技術(shù)。本節(jié)，僅介紹學(xué)科專業(yè)名稱的演變，學(xué)科的描述以及培養(yǎng)的側(cè)重點等內(nèi)容。下一節(jié)，再介紹學(xué)科的知識體和核心課程。1.2.1演變中的學(xué)科專業(yè)名稱1962年，美國普渡大學(xué)開設(shè)了最早的計算機(jī)科學(xué)學(xué)位課程。當(dāng)時，在美國的一些高校還開設(shè)有與計算相關(guān)的兩給學(xué)位課程：電子工程和信息系統(tǒng)。而在我國，早在1956年，就開設(shè)了“計算裝置與儀器”專業(yè)。20世紀(jì)60年代，隨著問題復(fù)雜性的增加，制造可靠軟件的困難越來越大，出現(xiàn)了“軟件危機(jī)”。為了擺脫“軟件危機(jī)”，1968年秋，北大西洋公約組織（NATO）在當(dāng)時的聯(lián)邦德國召開了一次會議，提出了軟件工程的概念。20世紀(jì)70年代，在美國，計算機(jī)工程（也被稱為“計算機(jī)系統(tǒng)工程”）從電子工程學(xué)科中脫離出來，成為一個獨立的二級學(xué)科，并被人們所接受。20世紀(jì)70年代未、80年代初，在一些計算機(jī)科學(xué)專業(yè)的學(xué)位課程中，引入了“軟件工程”的內(nèi)容，然而，這些內(nèi)容，只能讓學(xué)生了解“軟件工程”，卻不能使學(xué)生明白“如何成為一名軟件工程師”。于是，人們開始構(gòu)建單獨的軟件工程學(xué)位課程。20世紀(jì)80年代，英國和澳大利亞，最早開設(shè)了軟件工程這樣的學(xué)位課程。20世紀(jì)90年代，計算機(jī)已成為公司各級人員使用的基本工具，而計算機(jī)網(wǎng)絡(luò)則成為公司信息的中樞，人們相信它有助于提高生產(chǎn)力，而原有的學(xué)術(shù)學(xué)位課程并不能滿足社會的需求，于是，在美國等西方國家，不少大學(xué)，相繼開設(shè)了信息系統(tǒng)和信息技術(shù)等學(xué)位課程。在這里，需要指出的是，即使在美國，5個分支學(xué)科（專業(yè)）同時在一所大學(xué)開設(shè)的情況也是不多的，更多的高校仍然是以傳統(tǒng)的“計算機(jī)科學(xué)”為主；在我國，則是以“計算機(jī)科學(xué)與技術(shù)”為主。1.2.2分支學(xué)科（專業(yè)）描述及培養(yǎng)側(cè)重點計算為個人的職業(yè)生涯提供了廣泛的選擇，進(jìn)入計算職業(yè)的人員應(yīng)重視他們的職業(yè)化訓(xùn)練，并通過計算學(xué)科相應(yīng)學(xué)位課程的嚴(yán)格要求。下面，分別介紹各分支學(xué)科（專業(yè)）及其培養(yǎng)側(cè)重點。（1）計算機(jī)科學(xué)，涉及很寬的范圍，包括了計算的理論、算法和實現(xiàn)，以及機(jī)器人技術(shù)、計算機(jī)視覺、智能系統(tǒng)、生物信息學(xué)和其他新興的有前途的領(lǐng)域。計算機(jī)科學(xué)是計算各學(xué)科的基礎(chǔ)，計算機(jī)科學(xué)專業(yè)培養(yǎng)的學(xué)生，更關(guān)注計算的理論基礎(chǔ)和算法，并能從事軟件開發(fā)及其相關(guān)的理論研究。（2）計算機(jī)工程，是對現(xiàn)代計算系統(tǒng)和由計算機(jī)控制的有關(guān)設(shè)備上的軟件與硬件的設(shè)計、構(gòu)造、實施和維護(hù)進(jìn)行研究的學(xué)科。計算機(jī)工程專業(yè)培養(yǎng)的學(xué)生，更關(guān)注設(shè)計并實施集軟件和硬件設(shè)備為一體的系統(tǒng)，如嵌入式系統(tǒng)。（3）軟件工程，是指以系統(tǒng)、學(xué)科、定量的方法，把工程應(yīng)用于軟件的開發(fā)、運(yùn)行和維護(hù)；同時，展開對上述過程中各種方法和途徑進(jìn)行研究的學(xué)科。軟件工程專業(yè)培養(yǎng)的學(xué)生，更關(guān)注以工程規(guī)范進(jìn)行的大規(guī)模軟件系統(tǒng)開發(fā)與維護(hù)的原則，并盡可能避免軟件系統(tǒng)潛在的風(fēng)險。（4）信息系統(tǒng)，是指如何將信息技術(shù)的方法與企業(yè)生產(chǎn)和商業(yè)流通結(jié)合起來，以滿足這些行業(yè)需求的學(xué)科。信息系統(tǒng)培養(yǎng)的學(xué)生，更關(guān)注信息資源的獲取、部署、管理及使用，并能分析信息的需求和相關(guān)的商業(yè)過程，能詳細(xì)描述并設(shè)計那些與目標(biāo)相一致的系統(tǒng)。（5）信息技術(shù)，從廣義上來說，它包括了所有計算技術(shù)的各個方面，在此專指作為一門學(xué)科的信息技術(shù)。它側(cè)重在一定組織及社會環(huán)境下，通過選擇、創(chuàng)造、應(yīng)用、集成和管理的計算技術(shù)來滿足用戶的需求。與信息系統(tǒng)相比，信息技術(shù)更關(guān)注于“信息技術(shù)”的技術(shù)層面，而信息系統(tǒng)則重于“信息技術(shù)”的“信息”層面。信息技術(shù)專業(yè)培養(yǎng)的學(xué)生，更關(guān)注基于計算機(jī)的新產(chǎn)品及其正常的運(yùn)行和維護(hù)，并能使用相關(guān)的信息技術(shù)來計劃、實施和配置計算機(jī)系統(tǒng)。1.3學(xué)科知識體和核心課程CC2001報告給出了計算機(jī)科學(xué)知識體的概念，為其他分支學(xué)科知識體的建立提供了模式。學(xué)科知識體由以下3個層次構(gòu)成，下面以計算機(jī)科學(xué)為例進(jìn)行介紹：（1）最高層是分支領(lǐng)域（area），它代表一個特定的學(xué)科子領(lǐng)域。每個分支領(lǐng)域由兩個字母的縮寫詞表示，比如OS代表操作系統(tǒng)，PL代表程序設(shè)計語言。（2）分支領(lǐng)域之下又分為更小的知識單元（unit），它代表該領(lǐng)域中的主題模塊。每個知識單元都用一個領(lǐng)域名加一個數(shù)字后綴表示，比如OS3是操作系統(tǒng)領(lǐng)域中關(guān)于并發(fā)的單元。為便于教學(xué)，報告還給出了所有知識單元的最小核心學(xué)時和學(xué)習(xí)目標(biāo)，供教師參考。（3）知識單元又被細(xì)分為眾多的知識點（topic），這些知識點構(gòu)成了知識體結(jié)構(gòu)的最底層。比如，在DS領(lǐng)域（離散結(jié)構(gòu)）的第1個知識單元DS1（函數(shù)、關(guān)系、集合）中，相應(yīng)的知識點有：函數(shù)(滿射，到內(nèi)的映射，逆函數(shù)，復(fù)合函數(shù))，關(guān)系(自反，對稱，傳遞，等價關(guān)系)，集合(文氏圖,補(bǔ)集，笛卡爾積，冪集)，鴿籠原理，基數(shù)性和可數(shù)性等。結(jié)合我國的實際情況，計算機(jī)教指委根據(jù)IEEE/CS和ACM任務(wù)組給出的計算機(jī)科學(xué)、計算機(jī)工程、軟件工程和信息技術(shù)等4個分支學(xué)科知識體和核心課程描述，組織編制了計算機(jī)專業(yè)規(guī)范。下面，簡要介紹構(gòu)成計算機(jī)專業(yè)規(guī)范的4個分支學(xué)科的知識體和核心課程。1.3.1計算機(jī)科學(xué)知識體和核心課程

1.計算機(jī)科學(xué)知識體為便于學(xué)習(xí)，下面列出計算機(jī)科學(xué)知識體中的14個領(lǐng)域，以及132個知識單元（表1-1，表中單元后的數(shù)字表示學(xué)習(xí)所需的最小核心學(xué)時，該學(xué)時為一個相對值，一般要求有3倍以上的課外學(xué)時與之配套）。DS離散結(jié)構(gòu)（43）

DS1函數(shù)、關(guān)系、集合（6）DS2基本邏輯（10）DS3證明方法（12）DS4計算基礎(chǔ)（5）DS5圖和樹（4）DS6離散概率（6）PF程序設(shè)計基礎(chǔ)（38）PF1基本程序設(shè)計結(jié)構(gòu)（9）PF2算法和問題求解（6）PF3基本的數(shù)據(jù)結(jié)構(gòu)（14）PF4遞歸（5）PF5事件驅(qū)動的程序設(shè)計（4）AL算法和復(fù)雜性（31）AL1算法分析基礎(chǔ)(4)AL2算法策略(6)AL3基本的計算算法(12)AL4分布式算法(3)AL5可計算性基礎(chǔ)(6)AL6P和NP復(fù)雜類AL7自動機(jī)理論AL8高級算法分析AL9加密算法AL10幾何算法AL11并行算法AR體系結(jié)構(gòu)和組織（36）AR1數(shù)字邏輯和數(shù)字系統(tǒng)(6)AR2數(shù)據(jù)的機(jī)器級表示(3)AR3匯編級機(jī)器組織(9)AR4存儲系統(tǒng)組織和體系結(jié)構(gòu)(5)AR5接口和通信(3)AR6功能組織(7)AR7多處理和其他體系結(jié)構(gòu)(3)AR8性能提高技術(shù)AR9網(wǎng)絡(luò)與分布式系統(tǒng)的體系結(jié)構(gòu)OS操作系統(tǒng)(18)OS1操作系統(tǒng)概述(2)OS2操作系統(tǒng)原理(2)OS3并發(fā)(6)OS4調(diào)度和分派(3)OS5存儲管理(5)OS6設(shè)備管理OS7安全和保護(hù)OS8文件系統(tǒng)OS9實時和嵌入式系統(tǒng)OS10容錯OS11系統(tǒng)性能評價OS12腳本NC網(wǎng)絡(luò)計算(15個核心小時)NC1網(wǎng)絡(luò)計算引導(dǎo)(2)NC2通信與組網(wǎng)(7)NC3網(wǎng)絡(luò)安全(3)NC4顧客-服務(wù)器計算的實例：Web(3)NC5建立Web應(yīng)用NC6網(wǎng)絡(luò)管理NC7壓縮和解壓縮NC8多媒體數(shù)據(jù)技術(shù)NC9無線和移動計算PL程序設(shè)計語言（21）PL1程序設(shè)計語言概述(2)PL2虛擬機(jī)(1)PL3語言翻譯導(dǎo)引(2)PL4聲明和類型(3)PL5抽象機(jī)制(3)PL6面向?qū)ο蟪绦蛟O(shè)計(10)PL7函數(shù)式程序設(shè)計PL8語言翻譯系統(tǒng)PL9類型系統(tǒng)PL10程序設(shè)計語言的語義PL11程序設(shè)計語言的設(shè)計HC人機(jī)交互(8)HC1人機(jī)交互基礎(chǔ)(6)HC2創(chuàng)建簡單的圖形用戶界面(2)HC3以人為中心的軟件評估HC4以人為中心的軟件開發(fā)HC5圖形用戶界面設(shè)計HC6圖形用戶界面的程序設(shè)計HC7多媒體系統(tǒng)的人機(jī)交互HC8協(xié)作和通信的人機(jī)交互GV圖形學(xué)和可視化計算（5）GV1圖形學(xué)的基本技術(shù)(2)GV2圖形系統(tǒng)(1)GV3圖形通信(2)GV4幾何模型GV5基本繪制GV6高級繪制GV7高級技術(shù)GV8計算機(jī)動畫GV9可視化GV10虛擬現(xiàn)實GV11計算機(jī)視覺IS智能系統(tǒng)（10）IS1智能系統(tǒng)的基本問題(1)IS2搜索和約束滿足(5)IS3知識表示與推理(4)IS4高級搜索IS5高級知識表示與推理IS6代理IS7自然語言處理IS8機(jī)器學(xué)習(xí)與神經(jīng)網(wǎng)絡(luò)IS9人工智能規(guī)劃系統(tǒng)IS10機(jī)器人學(xué)IM信息系統(tǒng)（10）IM1信息模型與信息系統(tǒng)(3)IM2數(shù)據(jù)庫系統(tǒng)(3)IM3數(shù)據(jù)建模(4)IM4關(guān)系型數(shù)據(jù)庫IM5數(shù)據(jù)庫查詢語言IM6關(guān)系數(shù)據(jù)庫設(shè)計IM7事務(wù)處理IM8分布式數(shù)據(jù)庫IM9物理數(shù)據(jù)庫設(shè)計IM10數(shù)據(jù)挖掘IM11信息存儲和檢索IM12超文本和超媒體IM13多媒體信息與多媒體系統(tǒng)IM14數(shù)字圖書館SP社會與職業(yè)問題（16）SP1計算的歷史(1)SP2計算的社會背景(3)SP3分析方法和工具(2)SP4職業(yè)和道德責(zé)任(3)SP5基于計算機(jī)的系統(tǒng)的風(fēng)險與責(zé)任(2)SP6知識產(chǎn)權(quán)(3)SP7隱私與公民自由(2)SP8計算機(jī)犯罪SP9計算中的經(jīng)濟(jì)問題SP10哲學(xué)框架SE軟件工程（31）SE1軟件設(shè)計（8）SE2使用API（5）SE3軟件工具和環(huán)境（3）SE4軟件過程（2）SE5軟件需求與規(guī)約（4）SE6軟件驗證（3）SE7軟件演化（3）SE8軟件項目管理（3）SE9基于構(gòu)件的計算SE10形式化方法SE11軟件可靠性SE12專用系統(tǒng)開發(fā)CN計算科學(xué)和數(shù)值計算方法CN1數(shù)值分析CN2運(yùn)籌學(xué)CN3建模與模擬CN4高性能計算2.計算機(jī)科學(xué)專業(yè)核心課程在對計算機(jī)科學(xué)知識體和CS2001核心課程進(jìn)行研究的基礎(chǔ)上，結(jié)合我國的情況，計算機(jī)專業(yè)規(guī)范研究小組確定了我國計算機(jī)科學(xué)專業(yè)的15門核心課程，給出了相應(yīng)的理論學(xué)習(xí)學(xué)時和實踐學(xué)時，供高校參考。計算機(jī)科學(xué)專業(yè)15門核心課程計算機(jī)導(dǎo)論程序設(shè)計基礎(chǔ)離散結(jié)構(gòu)算法與數(shù)據(jù)結(jié)構(gòu)計算機(jī)組成基礎(chǔ)計算機(jī)體系結(jié)構(gòu)操作系統(tǒng)數(shù)據(jù)庫系統(tǒng)原理編譯原理軟件工程計算機(jī)圖形學(xué)計算機(jī)網(wǎng)絡(luò)人工智能數(shù)字邏輯社會與職業(yè)道德1.3.2計算機(jī)工程的知識體和核心課程

1.計算機(jī)工程知識體計算機(jī)工程知識體由18個知識領(lǐng)域（其中有2個與數(shù)學(xué)有關(guān)），175個知識單元組成。知識領(lǐng)域和知識單元如下所示。ALG算法與復(fù)雜度（30）ALG1歷史和概述（1）ALG2基本算法分析（4）ALG3算法策略（8）ALG4計算算法（12）ALG5分布式算法（3）ALG6算法復(fù)雜度（2）ALG7基本可計算性理論CAO計算機(jī)體系結(jié)構(gòu)和組織（63）CAO1歷史和概述（1）CAO2計算機(jī)體系結(jié)構(gòu)基礎(chǔ)（10）CAO3計算機(jī)的運(yùn)算（3）CAO4存儲系統(tǒng)組織和體系結(jié)構(gòu)（8）CAO5接口和通信（10）CAO6設(shè)備子系統(tǒng)（5）CAO7處理器系統(tǒng)設(shè)計（10）CAO8CPU的組織（10）CAO9性能（3）CAO10分布式系統(tǒng)模型（3）CAO11性能改進(jìn)CSE計算機(jī)系統(tǒng)工程（18）CSE1歷史和概述（1）CSE2生命周期（2）CSE3需求分析和獲?。?）CSE4規(guī)格說明（2）CSE5體系結(jié)構(gòu)設(shè)計（3）CSE6測試（2）CSE7維護(hù)（2）CSE8項目管理（2）CSE9并發(fā)(硬件/軟件)設(shè)計（2）CSE10實現(xiàn)CSE11專用系統(tǒng)CSE12可靠性和容錯性CSG電路和信號（43）CSG1歷史和概述（1）CSG2電量（3）CSG3電阻性電路和網(wǎng)絡(luò)（9）CSG4電抗性電路和網(wǎng)絡(luò)（12）CSG5頻率響應(yīng)（9）CSG6正弦分析（6）CSG7卷積（3）CSG8傅立葉分析CSG9濾波器CSG10拉普拉斯變換DBS數(shù)據(jù)庫系統(tǒng)（5）DBS1歷史和概述（1）DBS2數(shù)據(jù)庫系統(tǒng)（2）DBS3數(shù)據(jù)建模（2）DBS4關(guān)系數(shù)據(jù)庫DBS5數(shù)據(jù)查詢語言DBS6關(guān)系型數(shù)據(jù)庫設(shè)計DBS7事務(wù)處理DBS8分布式數(shù)據(jù)庫DBS9物理數(shù)據(jù)庫設(shè)計DIG數(shù)字邏輯（57）DIG1歷史和概述（1）DIG2開關(guān)理論（6）DIG3組合邏輯電路（4）DIG4組合邏輯電路的模塊設(shè)計（6）DIG5存儲單元（3）DIG6時序邏輯電路（10）DIG7數(shù)字系統(tǒng)設(shè)計（12）DIG8建模和仿真（5）DIG9形式化驗證（5）DIG10故障模型和測試（5）DIG11可測試性設(shè)計DSP數(shù)字信號處理（17）DSP1歷史和概述（1）DSP2理論和概念（1）DSP3數(shù)字頻譜分析（1）DSP4離散傅立葉變換（7）DSP5采樣（2）DSP6變換（2）DSP7數(shù)字濾波器（1）DSP8離散時間信號DSP9窗口函數(shù)DSP10卷積DSP11音頻處理DSP12圖像處理ELE電子學(xué)（40）ELE1歷史和概述（1）ELE2材料的電子特性（3）ELE3二極管和二極管電路（5）ELE4MOS傳感器和偏置（3）ELE5MOS邏輯（7）ELE6雙極型晶體管和邏輯（4）ELE7參數(shù)設(shè)計及相關(guān)問題（4）ELE8存儲單元（3）ELE9接口邏輯和標(biāo)準(zhǔn)總線（3）ELE10運(yùn)算放大器（4）ELE11電路建模和仿真（3）ELE12數(shù)據(jù)轉(zhuǎn)換電路ELE13電壓源和電流源ELE14放大器設(shè)計ELE15集成電路組成模塊ESY嵌入式系統(tǒng)（20）ESY1歷史和概述（1）ESY2嵌入式微控制器（6）ESY3嵌入式程序（3）ESY4實時操作系統(tǒng)（3）ESY5低功耗計算（2）ESY6可靠系統(tǒng)設(shè)計（2）ESY7設(shè)計方法（3）ESY8工具支持ESY9嵌入式多處理器ESY10網(wǎng)絡(luò)嵌入式系統(tǒng)ESY11接口和混合信號系統(tǒng)HCI人機(jī)交互（8）HCI1歷史和概述（1）HCI2人機(jī)交互基礎(chǔ)（2）HCI3圖形用戶接口（2）HCI4輸入/輸出技術(shù)（1）HCI5智能系統(tǒng)（2）HCI6人性化軟件評價HCI7人性化軟件開發(fā)HCI8交互式圖形用戶接口設(shè)計HCI9圖形用戶接口編程HCI10圖形和可視化HCI11多媒體系統(tǒng)NWK計算機(jī)網(wǎng)絡(luò)（21）NWK1歷史和概述（1）NWK2通訊網(wǎng)絡(luò)體系結(jié)構(gòu)（3）NWK3通訊網(wǎng)絡(luò)協(xié)議（4）NWK4局域網(wǎng)和廣域網(wǎng)（4）NWK5客戶—服務(wù)器計算（3）NWK6數(shù)據(jù)安全性和完整性（4）NWK7無線和移動計算（2）NWK8性能評價NWK9數(shù)據(jù)通信NWK10網(wǎng)絡(luò)管理NWK11壓縮和解壓縮OPS操作系統(tǒng)（20）OPS1歷史和概述（1）OPS2設(shè)計原則（5）OPS3并發(fā)（6）OPS4調(diào)度和分派（3）OPS5內(nèi)存管理（5）OPS6設(shè)備管理OPS7安全和保護(hù)OPS8文件系統(tǒng)OPS9系統(tǒng)性能評價PRF程序設(shè)計基礎(chǔ)（39）PRF1歷史和概述（1）PRF2程序設(shè)計范例（5）PRF3程序設(shè)計結(jié)構(gòu)（7）PRF4算法和問題求解（8）PRF5數(shù)據(jù)結(jié)構(gòu)（13）PRF6遞歸（5）PRF7面向?qū)ο蟪绦蛟O(shè)計PRF8事件驅(qū)動和并發(fā)程序設(shè)計PRF9使用APIsSPR社會與職業(yè)問題（16）SPR1歷史和概述（1）SPR2公共政策（2）SPR3分析方法和工具（2）SPR4職業(yè)和倫理責(zé)任（2）SPR5風(fēng)險和責(zé)任（2）SPR6知識產(chǎn)權(quán)（2）SPR7隱私和公民自由（2）SPR8計算機(jī)犯罪（1）SPR9計算中的經(jīng)濟(jì)問題（2）SPR10哲學(xué)框架SWE軟件工程（13）SWE1歷史和概述（1）SWE2軟件過程（2）SWE3軟件需求和規(guī)約（2）SWE4軟件設(shè)計（2）SWE5軟件測試和驗證（2）SWE6軟件演化（2）SWE7軟件工具和環(huán)境（2）SWE8語言翻譯SWE9軟件工程管理SWE10軟件容錯性VLSVLSI設(shè)計和構(gòu)造（10）VLS1歷史和概述（1）VLS2材料的電子特性（2）VLS3基本反向器結(jié)構(gòu)的功能（3）VLS4組合邏輯結(jié)構(gòu)（1）VLS5時序邏輯結(jié)構(gòu)（1）VLS6半導(dǎo)體存儲器和陣列結(jié)構(gòu)（2）VLS7芯片輸入/輸出電路VLS8工藝過程和布局VLS9電路特性和性能VLS10可選電路結(jié)構(gòu)/低功耗設(shè)計VLS11半定制技術(shù)VLS12ASIC設(shè)計方法與數(shù)學(xué)有關(guān)的兩個知識領(lǐng)域及其知識單元DSC離散結(jié)構(gòu)（33）DSC1歷史和概述（1）DSC2函數(shù)、關(guān)系和集合（6）DSC3基本邏輯（10）DSC4證明方法（6）DSC5計數(shù)基礎(chǔ)（4）DSC6圖和樹（4）DSC7遞歸（2）PRS概率和統(tǒng)計學(xué)（33）PRS1歷史和概述（1）PRS2離散概率（6）PRS3連續(xù)概率（6）PRS4期望（4）PRS5隨機(jī)過程（6）PRS6樣本分布（4）PRS7估計（4）PRS8假設(shè)檢驗（2）PRS9相關(guān)性和回歸2.計算機(jī)工程16門專業(yè)核心課程計算機(jī)導(dǎo)論程序設(shè)計基礎(chǔ)離散結(jié)構(gòu)算法與數(shù)據(jù)結(jié)構(gòu)電路與系統(tǒng)模擬與數(shù)字電子技術(shù)數(shù)字信息處理數(shù)字邏輯計算機(jī)組成結(jié)構(gòu)計算機(jī)體系結(jié)構(gòu)操作系統(tǒng)計算機(jī)網(wǎng)絡(luò)嵌入式系統(tǒng)軟件工程數(shù)據(jù)庫系統(tǒng)原理社會與職業(yè)道德1.3.3軟件工程知識體及所支撐的核心課程1.軟件工程知識體軟件工程知識體由11個知識領(lǐng)域（其中1個是應(yīng)用知識領(lǐng)域），以及相應(yīng)的57個知識單元構(gòu)成。CMP計算基礎(chǔ)（172）CMP1計算機(jī)科學(xué)基礎(chǔ)（140）CMP2代碼開發(fā)技術(shù)（20）CMP3代碼開發(fā)工具（4）CMP4形式化開發(fā)方法（8）FND數(shù)學(xué)和工程基礎(chǔ)（89）FND1數(shù)學(xué)基礎(chǔ)（56）FND2軟件的工程基礎(chǔ)（23）FND3軟件的工程經(jīng)濟(jì)學(xué)（10）PRF職業(yè)實踐（35）PRF1團(tuán)隊激勵/心理學(xué)（5）PRF2交流溝通技能（10）PRF3專業(yè)精神（20）MAA軟件建模與分析（53）MAA1建?；A(chǔ)（19）MAA2模型分類（12）MAA3分析基礎(chǔ)（6）MAA4需求基礎(chǔ)（3）MAA5需求獲取（4）MAA6需求規(guī)約與文檔（6）MAA7需求確認(rèn)（3）DES軟件設(shè)計（45）DES1設(shè)計概念（3）DES2設(shè)計策略（6）DES3體系結(jié)構(gòu)設(shè)計（9）DES4人機(jī)界面設(shè)計（12）DES5詳細(xì)設(shè)計（12）DES6設(shè)計工具與設(shè)計評價（3）VAV軟件驗證與確認(rèn)（42）VAV1基本知識（5）VAV2評審（6）VAV3測試（21）VAV4人機(jī)用戶界面測試和評價（6）VAV5問題分析報告（4）EVO軟件演化（10）；PRO軟件過程（13）EVO1演化過程（6）EVO2演化活動（4）PRO1軟件過程的概念（3）PRO2軟件過程的實現(xiàn)（10）QUA軟件質(zhì)量（16）QUA1軟件質(zhì)量概念與文化（2）QUA2軟件質(zhì)量標(biāo)準(zhǔn)（2）QUA3軟件質(zhì)量過程（4）QUA4過程保證（4）QUA5產(chǎn)品保證（4）MGT軟件管理（19）MGT1管理概念（2）MGT2項目計劃（6）MGT3項目人員和組織（2）MGT4項目控制（4）MGT5軟件配置管理（5）SE-SAS特定系統(tǒng)和應(yīng)用（應(yīng)用知識領(lǐng)域）SAS1以網(wǎng)絡(luò)為中心的系統(tǒng)SAS2信息系統(tǒng)和數(shù)據(jù)處理SAS3金融和電子商務(wù)系統(tǒng)SAS4容錯和可存活系統(tǒng)SAS5高安全系統(tǒng)SAS6安全攸關(guān)系統(tǒng)SAS7嵌入式和實時系統(tǒng)SAS8生物學(xué)系統(tǒng)SAS9科學(xué)系統(tǒng)SAS10電信系統(tǒng)SAS11航空和交通系統(tǒng)SAS12工業(yè)過程控制系統(tǒng)SAS13多媒體、游戲和娛樂系統(tǒng)SAS14小型移動平臺系統(tǒng)SAS15基于Agent的系統(tǒng)SAS16中文信息處理系統(tǒng)

2．軟件工程專業(yè)24門核心課程程序設(shè)計基礎(chǔ)面向?qū)ο蠓椒▽W(xué)數(shù)據(jù)結(jié)構(gòu)和算法離散結(jié)構(gòu)計算機(jī)體系結(jié)構(gòu)操作系統(tǒng)和網(wǎng)絡(luò)數(shù)據(jù)庫工程經(jīng)濟(jì)學(xué)團(tuán)隊激勵和溝通軟件工程職業(yè)實踐軟件工程與計算軟件工程導(dǎo)論軟件代碼開發(fā)技術(shù)人機(jī)交互的軟件工程方法大型軟件系統(tǒng)設(shè)計與軟件體系結(jié)構(gòu)軟件測試軟件設(shè)計與體系結(jié)構(gòu)軟件詳細(xì)設(shè)計軟件工程的形式化方法軟件質(zhì)量保證與測試軟件需求分析軟件項目管理軟件過程與管理軟件工程綜合實習(xí)（含畢業(yè)設(shè)計）在制定具體的教學(xué)計劃時，又可將核心課程可以分為兩組，取其中一組即可。第一組課程是：軟件代碼開發(fā)技術(shù)，軟件設(shè)計與體系結(jié)構(gòu)，軟件質(zhì)量保證與測試，軟件需求分析，軟件項目管理。第二組課程是：大型軟件系統(tǒng)設(shè)計與軟件體系結(jié)構(gòu)，軟件測試，軟件詳細(xì)設(shè)計，軟件工程的形式化方法，軟件過程與管理。1.3.4信息技術(shù)知識體及所支撐的核心課程1.信息技術(shù)知識體信息技術(shù)知識體由12個知識領(lǐng)域，以及相應(yīng)的81個知識單元構(gòu)成。ITF信息技術(shù)基礎(chǔ)(33)ITF1IT中的基本主題(17)ITF2組織問題(6)ITF3IT的歷史(3)ITF4IT及其信息原則(3)ITF5應(yīng)用領(lǐng)域(2)ITF6數(shù)學(xué)與統(tǒng)計學(xué)在IT中的應(yīng)用(2)HCI人機(jī)交互(20)HCI1人的因素(6)HCI2HCI方面的應(yīng)用(3)HCI3以人為中心的評估(3)HCI4有效接口的開發(fā)(3)HCI5訪問性(2)HCI6新出現(xiàn)的技術(shù)(2)HCI7以人為中心的軟件開發(fā)(1)IAS信息保障與安全(23)IAS1基礎(chǔ)知識(3)IAS2安全機(jī)制(抵御方法)(5)IAS3操作性問題(3)IAS4策略(3)IAS5攻擊(2)IAS6安全領(lǐng)域(2)IAS7說明(1)IAS8信息狀態(tài)(1)IAS9安全服務(wù)(1)IAS10威脅分析模型(1)IAS11易受傷性(1)IM信息管理(34)IM1IM概念及基礎(chǔ)(8)IM2數(shù)據(jù)庫查詢語言(9)IM3數(shù)據(jù)組織體系結(jié)構(gòu)(7)IM4數(shù)據(jù)建模(6)IM5數(shù)據(jù)庫環(huán)境管理(3)IM6特定目的數(shù)據(jù)庫(1)IPT綜合編程和技術(shù)(23)IPT1系統(tǒng)間通信(5)IPT2數(shù)據(jù)映射與交換(4)IPT3集成代碼(4)IPT4腳本技術(shù)(4)IPT5軟件安全實踐(4)IPT6混雜問題(1)IPT7編程語言概述(1)NET網(wǎng)絡(luò)(20)NET1網(wǎng)絡(luò)基礎(chǔ)(3)NET2路由與交換(8)NET3物理層(6)NET4安全性(2)NET5應(yīng)用領(lǐng)域(1)NET6網(wǎng)絡(luò)管理PF編程基礎(chǔ)(38)PF1數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)(10)PF2編程構(gòu)造基礎(chǔ)(9)PF3面向?qū)ο缶幊?9)PF4算法與問題解決(6)PF5事件驅(qū)動編程(3)PF6遞歸(1)PT平臺技術(shù)(14)PT1操作系統(tǒng)(10)PT2體系結(jié)構(gòu)與組織(3)PT3計算基礎(chǔ)設(shè)施(1)PT4企業(yè)配置軟件PT5固件PT6硬件SA系統(tǒng)管理和維護(hù)(11)SA1操作系統(tǒng)(4)SA2應(yīng)用(3)SA3管理性活動(2)SA4管理性領(lǐng)域(2)SIA系統(tǒng)集成和體系結(jié)構(gòu)(21)SIA1需求(6)SIA2先決條件/資源(4)SIA3集成(3)SIA4項目管理(3)SIA5測試和QA(3)SIA6組織性環(huán)境(1)SIA7體系結(jié)構(gòu)(1)SP社會與職業(yè)問題(23)SP1職業(yè)交流(5)SP2計算的歷史(3)SP3計算的社會環(huán)境(3)SP4團(tuán)隊工作概念和問題(3)SP5知識產(chǎn)權(quán)(2)SP6計算的合法性問題(2)SP7組織機(jī)構(gòu)環(huán)境(2)SP8職業(yè)道德問題和責(zé)任(2)SP9個人隱私和個人自由(1)WSWeb系統(tǒng)和技術(shù)(21)WS1Web技術(shù)(10)WS2信息體系結(jié)構(gòu)(4)WS3數(shù)字化媒體(3)WS4Web的發(fā)展(3)WS5脆弱性(1)WS6社會性軟件

2.信息技術(shù)專業(yè)15門核心課程信息技術(shù)導(dǎo)論信息技術(shù)應(yīng)用數(shù)學(xué)入門程序設(shè)計與問題求解數(shù)據(jù)結(jié)構(gòu)與算法計算機(jī)系統(tǒng)平臺應(yīng)用集成原理與工具Web系統(tǒng)與技術(shù)計算機(jī)網(wǎng)絡(luò)與互聯(lián)網(wǎng)數(shù)據(jù)庫與信息管理技術(shù)人機(jī)交互面向?qū)ο蠓椒ㄐ畔⒈Ｕ吓c安全社會信息學(xué)信息系統(tǒng)工程與實踐系統(tǒng)管理與維護(hù)1.4如何構(gòu)建“計算機(jī)導(dǎo)論”課程1.4.1“計算機(jī)導(dǎo)論”課程的構(gòu)建是計算教育面臨的一個重大問題正如前幾節(jié)介紹的那樣，計算已成為一個龐大的學(xué)科，它涉及了數(shù)學(xué)、科學(xué)、工程和商業(yè)等領(lǐng)域，并包括了專業(yè)實踐所需要的大量基礎(chǔ)知識。學(xué)科知識體，以及核心知識單元等內(nèi)容的給出，為學(xué)科專業(yè)教學(xué)計劃的制定奠定了基礎(chǔ)。然而，由于知識單元，特別是知識點的大量羅列，也為計算學(xué)科的教學(xué)帶來了挑戰(zhàn)。要知道，19世紀(jì)，隨著63個化學(xué)元素的發(fā)現(xiàn)，化學(xué)教學(xué)史上曾遇到過前所未有的危機(jī)，面對雜亂無章的63個化學(xué)元素，當(dāng)時的人們很難進(jìn)行教與學(xué)。針對這個問題，門捷列夫發(fā)明了“元素周期表”，揭示了化學(xué)元素之間的規(guī)律，使問題的復(fù)雜性大大下降，促進(jìn)了化學(xué)學(xué)科的發(fā)展。今天的計算學(xué)科，不說具體的內(nèi)容，僅就其重要的思想、方法和核心概念而言，早就超過了63個。因此，要解決計算學(xué)科內(nèi)容大量羅列而產(chǎn)生的問題，就不得不先解決計算教育面臨的另一個重要問題，即“計算機(jī)導(dǎo)論”課程的構(gòu)建問題。

“計算作為一門學(xué)科”報告認(rèn)為，“計算機(jī)導(dǎo)論”課程的構(gòu)建問題是計算教育面臨的一個重大問題。報告認(rèn)為，該課程要培養(yǎng)學(xué)生面向?qū)W科的思維能力，使學(xué)生領(lǐng)會學(xué)科的力量，以及從事本學(xué)科工作的價值之所在。報告希望該課程能用類似于數(shù)學(xué)那樣嚴(yán)密的方式將學(xué)生引入到計算學(xué)科各個富有挑戰(zhàn)性的領(lǐng)域之中。CC2001報告介紹了該課程的構(gòu)建問題，并認(rèn)為這是一個引起類似宗教戰(zhàn)爭那樣激烈爭論的問題。報告認(rèn)為，不管怎樣設(shè)計，這門課都應(yīng)該講授學(xué)科中那些富有智慧的核心思想。CC2004和CC2005則進(jìn)一步指出，該課程的關(guān)鍵是課程的結(jié)構(gòu)設(shè)計問題，現(xiàn)有的濃縮版結(jié)構(gòu)顯然不是一種好的課程結(jié)構(gòu)，報告期待人們在該課程的結(jié)構(gòu)設(shè)計上有所突破。1.4.2計算學(xué)科二維定義矩陣計算學(xué)科二維定義矩陣是對學(xué)科一個高度的概括，于是，可以將計算學(xué)科的認(rèn)知問題具體為計算學(xué)科二維定義矩陣的認(rèn)知問題。在定義矩陣中，不變的是3個過程（也稱為3個學(xué)科形態(tài)）；變化的是3個過程的具體內(nèi)容（值），這一維的取名可以是學(xué)科知識領(lǐng)域（或?qū)W科主領(lǐng)域），也可以為分支學(xué)科等。1.4.3“計算機(jī)導(dǎo)論”課程的結(jié)構(gòu)設(shè)計上一小節(jié)，我們將學(xué)科的認(rèn)知問題具體為學(xué)科二維定義矩陣的認(rèn)知問題，從而使學(xué)科的認(rèn)知具體化。認(rèn)知學(xué)科終究是通過概念來完成的，而學(xué)科中所有的概念都蘊(yùn)含在定義矩陣中。于是，可以從定義矩陣出發(fā)介紹學(xué)科，并在學(xué)科思想、方法這個較高的層面講授“計算機(jī)導(dǎo)論”課程，為學(xué)生后續(xù)專業(yè)課程的學(xué)習(xí)提供必要的認(rèn)知基礎(chǔ)?，F(xiàn)在，可以將焦點放在定義矩陣，將把握學(xué)科的本質(zhì)問題歸約為把握定義矩陣的本質(zhì)問題，即對定義矩陣的“橫向”和“縱向”關(guān)系的把握。

“橫向”關(guān)系，即抽象、理論和設(shè)計3個過程的關(guān)系，是定義矩陣中最為重要的內(nèi)容。它反映的是，人們在計算領(lǐng)域的認(rèn)識規(guī)律，即是從感性認(rèn)識（抽象）到理性認(rèn)識（理論），再由理性認(rèn)識（理論）回到實踐（設(shè)計）的過程。

“橫向”關(guān)系還蘊(yùn)含著學(xué)科中的基本問題。由于人們對客觀世界的認(rèn)識過程就是一個不斷提出問題和解決問題的過程，這種過程反映的正是抽象、理論和設(shè)計3個過程之間的相互作用，它與3個過程在本質(zhì)上是一致的。因此，在“計算機(jī)導(dǎo)論”課程的設(shè)計上，有必要將它與3個過程一起列入最重要的內(nèi)容。

“縱向”關(guān)系，即各分支領(lǐng)域中具有共性的核心概念、數(shù)學(xué)方法、系統(tǒng)科學(xué)方法、社會與職業(yè)問題等內(nèi)容的關(guān)系。這些內(nèi)容蘊(yùn)含在學(xué)科3個過程中，并將學(xué)科各分支領(lǐng)域結(jié)合成一個完整的體系，而不是互不相關(guān)的領(lǐng)域。

顯然，在定義矩陣中，“橫向”關(guān)系最重要，“縱向”關(guān)系次之。因此，在“計算機(jī)導(dǎo)論”課程的設(shè)計上，可以將本章列為第一章，而將學(xué)科的基本問題，抽象、理論和設(shè)計3個過程，學(xué)科中的核心概念，數(shù)學(xué)方法，系統(tǒng)科學(xué)方法，以及社會與職業(yè)問題分別列為第二至第七章。沿著定義矩陣這個關(guān)于學(xué)科概念的認(rèn)知模型進(jìn)行導(dǎo)引，優(yōu)點在于，對學(xué)科進(jìn)行總結(jié)的系統(tǒng)性。這種總結(jié)是回顧性的總結(jié)，不足在于，對學(xué)科有爭論的問題以及未來探索性的展望作用有限。為此，有必要構(gòu)建最后一章，即“探討與展望”。1.5本章小結(jié)針對“計算機(jī)導(dǎo)論”課程的構(gòu)建問題，本章在介紹了學(xué)科的定義，學(xué)科的根本問題，專業(yè)名稱的演變，以及學(xué)科知識體等內(nèi)容后，將學(xué)科的認(rèn)知問題具體為學(xué)科二維定義矩陣的認(rèn)知問題，從而降低了學(xué)科認(rèn)知問題的復(fù)雜性。接下來的章節(jié)，將分別介紹學(xué)科的基本問題、3個過程（學(xué)科形態(tài)）、核心概念、數(shù)學(xué)方法、系統(tǒng)科學(xué)方法、社會與職業(yè)問題，以及對學(xué)科有關(guān)問題的探討與展望等內(nèi)容。為便于后續(xù)章節(jié)的展開，本書以計算機(jī)科學(xué)的內(nèi)容為背景，從思想與方法這個層面，對計算學(xué)科進(jìn)行導(dǎo)引。第二章計算學(xué)科的基本問題本章首先介紹一個對問題進(jìn)行抽象的典型實例——哥尼斯堡七橋問題。然后，通過“梵天塔”問題和“停機(jī)問題”分別介紹學(xué)科中的可計算問題和不可計算問題。從“梵天塔”問題再引出算法復(fù)雜性中的難解性問題、P類問題和NP類問題，證比求易算法，P＝NP是否成立的問題，旅行商問題與組合爆炸問題，找零問題、背包問題與貪婪算法。要描述和實現(xiàn)算法，就要編寫程序。本章從“GOTO語句”的爭論，介紹程序設(shè)計中的結(jié)構(gòu)問題；以“哲學(xué)家共餐”問題為例，介紹計算機(jī)系統(tǒng)中的軟硬件資源的管理問題；以“兩軍問題”為例介紹計算機(jī)網(wǎng)絡(luò)的有關(guān)問題；以“圖靈測試”和“中文屋子”為例介紹人工智能的有關(guān)問題。最后，給出計算機(jī)科學(xué)各主領(lǐng)域的基本問題。2.1引言科學(xué)研究從問題開始，或者說科學(xué)始于問題而非觀察，盡管通過觀察可以引出問題，但在觀察時必定帶有問題，帶有預(yù)期的設(shè)想，漫無目的的觀察是不存在的。人們對客觀世界的認(rèn)識過程正是一個不斷提出問題和解決問題的過程，這個過程反映的正是抽象、理論和設(shè)計3個過程之間的相互作用，它與3個過程在本質(zhì)上是一致的。針對學(xué)科抽象第一的教學(xué)原則，我們先介紹一個對問題進(jìn)行抽象的典型實例，即哥尼斯堡七橋問題。然后再介紹計算學(xué)科的基本問題。2.2哥尼斯堡七橋問題17世紀(jì)的東普魯士有一座哥尼斯堡城，城中有一座奈佛夫島，普雷格爾河的兩條支流環(huán)繞其旁，并將整個城市分成北區(qū)、東區(qū)、南區(qū)和島區(qū)4個區(qū)域，全城共有7座橋?qū)?個城區(qū)相連起來。通過這7座橋到各城區(qū)游玩，問題：尋找走遍這7座橋的路徑，要求過每座橋只許走一次，最后又回到原出發(fā)點。問題的抽象1736年，大數(shù)學(xué)家列昂納德·歐拉（L.Euler）發(fā)表了關(guān)于“哥尼斯堡七橋問題”的論文。他抽象出問題最本質(zhì)的東西，忽視問題非本質(zhì)的東西（如橋的長度等），從而將哥尼斯堡七橋問題抽象為一個數(shù)學(xué)問題，即經(jīng)過圖中每邊一次且僅一次的回路問題了。歐拉回路歐拉給出了哥尼斯堡七橋問題的證明，還用數(shù)學(xué)方法給出了三條判定規(guī)則(判定每座橋恰好走過一次,不一定回到原點,即對歐拉路徑的判定)：如果通奇數(shù)座橋的地方不止兩個，滿足要求的路線是找不到的。如果只有兩個地方通奇數(shù)座橋，可以從這兩個地方之一出發(fā)，找到所要求的路線。如果沒有一個地方是通奇數(shù)座橋的，則無論從哪里出發(fā)，所要求的路線都能實現(xiàn)。根據(jù)第3點,可以得出,任一連通圖存在歐拉回路的充分必要條件是所有頂點均有偶數(shù)度.哈密爾頓回路問題問題：在某個圖G中，能不能找到這樣的路徑，即從一點出發(fā)不重復(fù)地走過所有的結(jié)點，最后又回到原出發(fā)點?！肮軤栴D回路問題”與“歐拉回路問題”的不同點“哈密爾頓回路問題”是訪問每個結(jié)點一次，而“歐拉回路問題”是訪問每條邊一次。對圖G是否存在“歐拉回路”前面已給出充分必要條件，而對圖G是否存在“哈密爾頓回路”至今仍未找到滿足該問題的充分必要條件。圖論的形成和發(fā)展歐拉的論文為圖論的形成奠定了基礎(chǔ)。圖論已廣泛地應(yīng)用于計算學(xué)科運(yùn)籌學(xué)信息論控制論等學(xué)科圖論已成為我們對現(xiàn)實問題進(jìn)行抽象的一個強(qiáng)有力的數(shù)學(xué)工具。圖論在計算學(xué)科中的作用越來越大，圖論本身也得到了充分的發(fā)展。2.3可計算問題與不可計算問題計算學(xué)科的問題，無非就是計算問題，從大的方面來說，分可計算問題與不可計算問題?？捎嬎銌栴}是存在算法可解的問題，不可計算問題是不存在算法可解的問題。為便于理解，下面，分別以梵天塔（Hanoi，又譯為漢諾）問題和停機(jī)問題來介紹可計算問題與不可計算問題。2.3.1梵天塔問題相傳印度教的天神梵天在創(chuàng)造地球這一世界時，建了一座神廟，神廟里豎有三根寶石柱子，柱子由一個銅座支撐。梵天將64個直徑大小不一的金盤子，按照從大到小的順序依次套放在第一根柱子上，形成一座金塔（如圖2.3所示），即所謂的梵天塔（又稱漢諾塔）。天神讓廟里的僧侶們將第一根柱子上的64個盤子借助第二根柱子全部移到第三根柱子上，即將整個塔遷移，同時定下3條規(guī)則：每次只能移動一個盤子；盤子只能在三根柱子上來回移動，不能放在他處；在移動過程中，三根柱子上的盤子必須始終保持大盤在下，小盤在上。算法：C語言描述hanoi(intn,charleft,charmiddle,charright){if(n==1)move(1,one,_,three);else{hanoi(n-1,left,right,middle);move(1,left,_,right);hanoi(n-1,middle,left,right);}}當(dāng)n=64時，移動次數(shù)=？花費(fèi)時間=？

h(n)=2h(n-1)+1=2(2h(n-2)+1)+1=22h(n-2)+2+1=23h(n-3)+22+2+1……=2nh(0)+2n-1+…+22+2+1=2n-1+…+22+2+1=2n-1需要移動盤子的次數(shù)為：

264-1=18446744073709551615假定每秒移動一次，一年有31536000秒，則僧侶們一刻不停地來回搬動，也需要花費(fèi)大約5849億年的時間。假定計算機(jī)以每秒1000萬個盤子的速度進(jìn)行搬遷，則需要花費(fèi)大約58490年的時間。理論上可以計算的問題，實際上并不一定能行，這屬于算法復(fù)雜性方面的研究內(nèi)容。2.3.2算法復(fù)雜性中的難解性問題、P類問題和NP類問題算法復(fù)雜性包括算法的空間以及時間兩方面的復(fù)雜性問題，梵天塔問題主要講的是算法的時間復(fù)雜性。關(guān)于梵天塔問題算法的時間復(fù)雜度，可以用一個指數(shù)函數(shù)O(2n)來表示，顯然，當(dāng)n很大（如10000）時，計算機(jī)是無法處理的。相反，當(dāng)算法的時間復(fù)雜度的表示函數(shù)是一個多項式，如O(n2)時，則可以處理。因此，一個問題求解算法的時間復(fù)雜度大于多項式（如指數(shù)函數(shù)）時，算法的執(zhí)行時間將隨n的增加而急劇增長，以致即使是中等規(guī)模的問題也不能求解出來，于是在計算復(fù)雜性中，將這一類問題稱為難解性問題。人工智能領(lǐng)域中的狀態(tài)圖搜索問題（解空間的表示或狀態(tài)空間搜索問題）就是一類典型的難解性問題。在計算復(fù)雜性理論中，將所有可以在多項式時間內(nèi)求解的問題稱為P類問題，而將所有在多項式時間內(nèi)可以驗證的問題稱為NP類問題。由于P類問題采用的是確定性算法，NP類問題采用的是非確定性算法，而確定性算法是非確定性算法的一種特例，因此，可以斷定P

NP。2.3.3證比求易算法為了更好地理解計算復(fù)雜性的有關(guān)概念，我國學(xué)者洪加威曾經(jīng)講了一個被人稱為“證比求易算法”的童話，用來幫助讀者理解計算復(fù)雜性的有關(guān)概念，大致內(nèi)容如下。從前，有一個酷愛數(shù)學(xué)的年輕國王艾述向鄰國一位聰明美麗的公主秋碧貞楠求婚。公主出了這樣一道題：求出48770428433377171的一個真因子。若國王能在一天之內(nèi)求出答案，公主便接受他的求婚。國王回去后立即開始逐個數(shù)地進(jìn)行計算，他從早到晚，共算了三萬多個數(shù)，最終還是沒有結(jié)果。國王向公主求情，公主將答案相告：223092827是它的一個真因子。國王很快就驗證了這個數(shù)確能除盡48770428433377171。公主說：“我再給你一次機(jī)會，如果還求不出，將來你只好做我的證婚人了?！眹趿⒓椿貒?，并向時任宰相的大數(shù)學(xué)家孔喚石求教，大數(shù)學(xué)家在仔細(xì)地思考后認(rèn)為這個數(shù)為17位，則最小的一個真因子不會超過9位，他給國王出了一個主意：按自然數(shù)的順序給全國的老百姓每人編一個號發(fā)下去，等公主給出數(shù)目后，立即將它們通報全國，讓每個老百姓用自己的編號去除這個數(shù)，除盡了立即上報，賞金萬兩。順序算法和并行算法國王最先使用的是一種順序算法，其復(fù)雜性表現(xiàn)在時間方面，后面由宰相提出的是一種并行算法，其復(fù)雜性表現(xiàn)在空間方面。直覺上，我們認(rèn)為順序算法解決不了的問題完全可以用并行算法來解決，甚至?xí)?，并行計算機(jī)系統(tǒng)求解問題的速度將隨著處理器數(shù)目的不斷增加而不斷提高，從而解決難解性問題，其實這是一種誤解。當(dāng)將一個問題分解到多個處理器上解決時，由于算法中不可避免地存在必須串行執(zhí)行的操作，從而大大地限制了并行計算機(jī)系統(tǒng)的加速能力。阿達(dá)爾定律設(shè)f為求解某個問題的計算存在的必須串行執(zhí)行的操作占整個計算的百分比，p為處理器的數(shù)目，Sp為并行計算機(jī)系統(tǒng)最大的加速能力，則設(shè)f=1%，p→

，則Sp=100。串行執(zhí)行操作僅占全部操作1%，解題速度最多也只能提高一百倍。對難解性問題而言，提高計算機(jī)系統(tǒng)的速度是遠(yuǎn)遠(yuǎn)不夠的，而降低算法復(fù)雜度的數(shù)量級才是最關(guān)鍵的問題。2.3.4

P＝NP？P類問題——存在多項式時間的算法的一類問題；NP類問題——非多項式時間算法解的一類問題。像梵塔問題、推銷員旅行問題、（命題表達(dá)式）可滿足問題這類，至今沒有找到多項式時間算法解的一類問題。P＝NP？如果P=NP，則所有在多項式時間內(nèi)可驗證的問題都將是在多項式時間內(nèi)可求解（或可判定）的問題。要證明P≠NP，目前還無法做到這一點。在P＝?NP問題上，庫克（S.A.Cook）等人認(rèn)為NP類中的某些問題的復(fù)雜性與整個類的復(fù)雜性有關(guān)，當(dāng)這些問題中的任何一個存在多項式時間算法時，則所有這些NP問題都是多項式時間可解的，這些問題被稱為NP完全性問題。多達(dá)數(shù)千個的NP完全性問題。有代表性的有：哈密爾頓回路問題、旅行商問題（也稱貨郎擔(dān)問題）、劃分問題、帶優(yōu)先級次序的處理機(jī)調(diào)度問題、頂點覆蓋問題等。2.3.5一個不可計算問題：停機(jī)問題停機(jī)問題（HaltingProblem）是1936年圖靈（A.M.Turing）在其著名論文《論可計算數(shù)及其在判定問題上的應(yīng)用》（OnComputableNumbers,withanApplicationtotheEntscheidungsproblem）中提出，并用形式化方法給予證明的一個不可計算問題。該問題針對任意給定的圖靈機(jī)和輸入，尋找一個一般的算法（或圖靈機(jī)），用于判定給定的圖靈機(jī)在接收了初始輸入后，能否到達(dá)終止?fàn)顟B(tài)，即停機(jī)狀態(tài)。若能找到這樣的算法，我們說停機(jī)問題可解，否則，不可解。換句話講說，就是我們能不能找到這樣一個測試程序，它能判斷出任意的程序在接收了某個輸入并執(zhí)行后，能不能終止。若能，則停機(jī)問題可解，否則，不可解。停機(jī)問題不可解？看起來好像不是的，畢竟有點編程經(jīng)歷的人都會遇到判斷一個程序是否是進(jìn)入死循環(huán)的時候，并且往往能判定該程序是否能在某種情況下終止或不能終止。例如：main()

{

inti=1; while(i<10){i=i+1;}return;}

很明顯，這個程序可以終止。但是將程序中while語句的條件“(i<10)”改為“(i>0)”時，循環(huán)將會一直運(yùn)行下去，無法終止。程序簡單的時候，我們會很容易做出判斷，當(dāng)例子復(fù)雜的時候，則會遇到較大的困難。而在某些情況下，其實是無法預(yù)測的。用計算機(jī)的程序來證明停機(jī)問題的不可解，或許會更有趣，本書不介紹圖靈的嚴(yán)格證明，而采用J.GlennBrookshear在其著作《計算機(jī)科學(xué)概論》（ComputerScience:AnOverview，J.GlennBrookshear著，王保江等譯，人民郵電出版社，2003年9月出版）中，給出的一個證明。在證明之前，我們先介紹一個概念：哥德爾數(shù)。在計算機(jī)理論的研究中，可以將無符號數(shù)分配給任何用特定語言編寫的程序，這樣的無符號數(shù)就稱為哥德爾數(shù)。這種分配使得程序可以作為單一的數(shù)據(jù)項輸入給其他程序。首先，我們將程序中要使用的符號用哥德爾數(shù)進(jìn)行對應(yīng)。int對應(yīng) 1x對應(yīng)2＋對應(yīng)3－對應(yīng)4……while對應(yīng)Aif對應(yīng)B

……語句則根據(jù)以上符號的對應(yīng)關(guān)系來確定。比如語句intx，int對應(yīng)1，x對應(yīng)2，所以intx對應(yīng)12（十六進(jìn)制），這樣intx的歌德爾數(shù)為18（十進(jìn)制）。同理，可以用這樣的方法表示其它的語句和程序段，這樣就可以將程序轉(zhuǎn)化為歌德爾數(shù)并作為單一的數(shù)據(jù)項輸入給其他程序。接下來進(jìn)行證明。停機(jī)問題的關(guān)鍵在于，能否找到這樣一個測試程序，這個測試程序能判定任何一個程序在給定的輸入下能否終止。用數(shù)學(xué)反證法證明，先假設(shè)存在這樣的測試程序，然后再構(gòu)造一個程序，該測試程序測試不了第一步假設(shè)存在一個測試程序T，它能接受任何輸入，如圖2.4（a）所示。輸入程序P（用哥德爾數(shù)來代替），若它能終止，輸出1，若不能終止，輸出0。第二步構(gòu)造一個程序S，該程序由兩部分構(gòu)成，一部分為測試程序T，另一部分為一個空循環(huán)，如圖2.4（b）所示?？昭h(huán)表示為：While(x){}輸入P，若P終止，程序T輸出1，把1送到循環(huán)體，很明顯S不會終止；若P不終止，程序T輸出0，把0送入循環(huán)體，程序S終止。第三步將S自身作為輸入，會是什么情況呢？由于沒有對P作任何特殊的規(guī)定，因此也可能將S替換P作為輸入，如圖2.4（c）所示。若S終止，測試程序T輸出1，把1送到循環(huán)體，很明顯它不會終止；若S不終止，T輸出0，把0送入循環(huán)體，程序終止。結(jié)論是：若S終止，則S不終止；若S不終止，則S終止。結(jié)論矛盾，故可以確定這樣的測試程序是不存在的，從而證明停機(jī)問題的不可解。現(xiàn)在我們知道，對于問題而言，并不都是可以計算的，即使是可以計算的問題，也存在是多項式時間內(nèi)可以計算的，還是非多項式時間可以計算的，當(dāng)然，還存在著神秘的NP問題。2.3.6旅行商問題與組合爆炸問題旅行商問題與組合爆炸問題旅行商問題與組合爆炸問題如果有3個城市A，B和C，互相之間都有往返的飛機(jī)，而且起始城市是任意的，則有6種訪問每個城市的次序：ABC,ACB,,BAC,BCA,CAB,CBA。如果有4個城市，則有24種次序，可以用階乘來表示：4！=4×3！=4×3×2×1=24；若有5個城市，則有5！=5×4！=120，類似的有6！=720等等。即使用計算機(jī)來計算，這種急劇增長的可能性的數(shù)目也遠(yuǎn)遠(yuǎn)超過計算資源的處理能力，

Cook評論：“如果有100個城市，需要求出100！條路線的費(fèi)用，沒有哪一臺計算機(jī)能夠勝任這一任務(wù)。打個比方，讓太陽系中所有的電子以它旋轉(zhuǎn)的頻率來計算，就算太陽燒盡了也算不完。問題的關(guān)鍵是某些東西在實踐中行不通。1998年，科學(xué)家們成功地解決了美國13509個城市之間的TSP問題，2001年又解決了德國15112個城市之間的TSP問題。但這一工程代價也是巨大的解決15112個城市之間的TSP問題，共使用了美國Rice大學(xué)和普林斯頓大學(xué)之間網(wǎng)絡(luò)互連的、由速度為500MHz的CompaqEV6Alpha處理器組成的110臺計算機(jī)，所有計算機(jī)花費(fèi)的時間之和為22.6年。TSP的應(yīng)用一個典型的例子就是機(jī)器在電路板上鉆孔的調(diào)度問題（注：在該問題中，鉆孔的時間是固定的，只有機(jī)器移動時間的總量是可變的），在這里，電路板上要鉆的孔相當(dāng)于TSP中的“城市”，鉆頭從一個孔移到另一個孔所耗的時間相當(dāng)于TSP中的“旅行費(fèi)用”。運(yùn)輸業(yè)、后勤服務(wù)業(yè)等然而，由于TSP會產(chǎn)生組合爆炸的問題，因此尋找切實可行的簡化求解方法就成為問題的關(guān)鍵。2.3.7找零問題、背包問題與貪婪算法找零問題、背包問題等是一類可以用啟發(fā)式的貪婪算法來處理的典型問題。下面，分別進(jìn)行介紹。1.找零問題設(shè)有不同面值的鈔票，要求用最小數(shù)量的鈔票給顧客找某數(shù)額的零錢，這就是通常說的找零問題。例1：有一個顧客拿一張面值100元的鈔票（人民幣）在超市買了5元錢的商品，收銀員需找給他95元零錢。售貨員在找零錢時可有多種選擇，比如可以找9張10元的、1張5元的，也可以找95張1元的，甚至還可以找950張1角的。但在一般情況下收銀員都會憑直覺選擇1張50元、2張20元和1張5元的，使找的零錢數(shù)目最少。收銀員采用的方法，其實是一種典型的貪婪算法（greedymethod，也可譯為貪心算法）?？梢宰C明，按照這種算法找的零錢數(shù)目的確最少。下面，介紹這種算法的基本思想。貪婪算法貪婪算法是一種傳統(tǒng)的啟發(fā)式算法，它采用逐步構(gòu)造最優(yōu)解的方法，即在算法的每個階段，都作出在當(dāng)時看上去最好的決策，以獲得最大的“好處”，換言之，就是在每一個決策過程中都要盡可能的“貪”，直到算法中的某一步不能繼續(xù)前進(jìn)時，算法才停止。在算法的過程中，“貪”的決策一旦作出，就不可再更改，作出“貪”的決策的依據(jù)稱為貪婪準(zhǔn)則。貪婪算法是從局部的最優(yōu)考慮問題的解決方案，它簡單而又快捷，因此，常被人們所使用。但是，這種從局部，而不是從整體最優(yōu)上考慮問題的算法，并不能保證求得的最后解為最優(yōu)解。下面，再介紹一類典型的背包問題。背包問題給定n種物品和一個背包，設(shè)Wi為物品i的重量，Vi為其價值，C為背包的重量容量，要求在重量容量的限制下，盡可能使裝入的物品總價最大，這就是背包問題。背包問題是一個典型的NP復(fù)雜性問題，也是一個在“算法設(shè)計與分析”教學(xué)中，一般都要提到的一個典型問題。為便于討論，本書所指的是一類物品不可分割的背包問題，即0/1背包問題，在這類問題中，物品只有裝入和不裝入兩種情況。用貪婪算法解決背包問題，有以下3種常用的貪婪準(zhǔn)則。貪婪準(zhǔn)則1：每次都選擇價值最大的物品裝包。例，假設(shè)n=3；W1=100，V1=60；W2=20，V2=40；W3=20，V3=40；C=110。利用價值最大的貪婪準(zhǔn)則時，選物品1，這種方案的總價值為60。而最優(yōu)解選物品為2和3，總價值為80，因此，可以斷定，使用貪婪準(zhǔn)則1，不能保證得到最優(yōu)解。貪婪準(zhǔn)則2：每次都選擇重量最小的物品裝包。使用貪婪準(zhǔn)則2，對于前面的例子能產(chǎn)生最優(yōu)解，但在一般情況下，不一定能得到最優(yōu)解。例，假設(shè)n=2；W1=100,V1=60；W2=20,V2=40；C=110。利用重量最小的貪婪策略時，選擇物品為2，總價值為40。而最優(yōu)解選1，總價值為60。貪婪準(zhǔn)則3：每次都選擇Vi/Wi值（價值密度）最大的物品裝包。例，假設(shè)n=3；W1=100，V1=60；W2=20，V2=40；W3=20，V3=40；C=110。使用價值密度最大的貪婪策略，選擇物品為2和3，總價值為80，結(jié)果為最優(yōu)解。比較3種不同的貪婪準(zhǔn)則，感覺（貪婪算法有直覺的傾向，這種傾向是計算學(xué)科中的一個特例），貪婪準(zhǔn)則3可能是一種更好的啟發(fā)式算法，而據(jù)有關(guān)文獻(xiàn)介紹，的確如此，用貪婪準(zhǔn)則3可以在大多數(shù)時候得到令人滿意的次優(yōu)解，甚至相當(dāng)一部份為最優(yōu)解。綜上所述，在一些應(yīng)用（如找零問題），貪婪算法所產(chǎn)生的方案總是最優(yōu)的解決方案。但對其他的一些應(yīng)用（如0/1背包問題），就不一定能得到最優(yōu)解。而在實際應(yīng)用中，盡管不一定能夠得到最優(yōu)解，然而次優(yōu)解也一樣有效。與找零問題、背包問題等類似的可以用貪婪算法求解的問題還有貨箱裝船問題、拓?fù)渑判騿栴}、二分覆蓋問題、最短路徑問題、最小代價生成樹等。貪婪算法是一種傳統(tǒng)的啟發(fā)式算法，用于求解一類問題的啟發(fā)式算法還有分而治之法、動態(tài)規(guī)劃法、分枝定界法、A*算法、遺傳算法、螞蟻算法，以及演化算法等。就以上找零問題、背包問題而言，以上的啟發(fā)式算法，都可以使用，在以后的學(xué)習(xí)中還會知道，解決這類問題的方法還會有不少。類似的，在現(xiàn)實生活中，可以觀察，解決問題的方式（方法）總比問題多，這時，問題的關(guān)鍵，往往不在于問題的本身，而在于方式（方法）的選擇。2.4“GOTO語句”與程序的結(jié)構(gòu)在計算機(jī)誕生的初期，計算機(jī)主要用于科學(xué)計算，程序的規(guī)模一般都比較小，那時的程序設(shè)計要說有方法的話，也只能說是一種手工式的設(shè)計方法。20世紀(jì)60年代，計算機(jī)軟硬件技術(shù)得到了迅速的發(fā)展，其應(yīng)用領(lǐng)域也急劇擴(kuò)大，這給傳統(tǒng)的手工式程序設(shè)計方法帶來了挑戰(zhàn)。1966年，C.B?hm和G.Jacopini發(fā)表了關(guān)于“程序結(jié)構(gòu)”的重要論文《帶有兩種形成規(guī)則的圖靈機(jī)和語言的流程圖》（FlowDiagrams,TuringMachinesandLanguageswithOnlyTwoFormationRules），給出了任何程序的邏輯結(jié)構(gòu)都可以用3種最基本的結(jié)構(gòu)（如圖2.7所示；A，B分別表示程序段；T，F(xiàn)分別表示謂詞P的真，假），即順序結(jié)構(gòu)、選擇結(jié)構(gòu)和循環(huán)結(jié)構(gòu)來表示的證明。以B?hm和Jacopini的工作為基礎(chǔ)，1968年，戴克斯特拉（E.W.Dijkstra）經(jīng)過深思熟慮后，在給《ACM通訊》（CommunicationsoftheACM）編輯的一封信中，首次提出了“GOTO語句是有害的”（GotoStatementConsideredHarmful）問題，該問題在《ACM通訊》雜志上發(fā)表后，引發(fā)了激烈的爭論，不少著名的學(xué)者參與了討論。經(jīng)過6年的爭論，1974年，著名計算機(jī)科學(xué)家、圖靈獎獲得者克努特（D.E.Knuth）教授在他發(fā)表的有影響力的論文《帶有GOTO語句的結(jié)構(gòu)化程序設(shè)計》（StructuredProgrammingwithGotoStatements）中對這場爭論作了較為全面而公正的論述：濫用GOTO語句是有害的，完全禁止也不明智，在不破壞程序良好結(jié)構(gòu)的前提下，有控制地使用一些GOTO語句，就有可能使程序更清晰，效率也更高，關(guān)于“GOTO語句”的爭論，其焦點應(yīng)當(dāng)放在程序的結(jié)構(gòu)上，好的程序應(yīng)該邏輯正確、結(jié)構(gòu)清晰、樸實無華。關(guān)于“GOTO語句”問題的爭論直接導(dǎo)致了一個新的學(xué)科分支領(lǐng)域，即程序設(shè)計方法學(xué)的產(chǎn)生。程序設(shè)計方法學(xué)是對程序的性質(zhì)及其設(shè)計的理論和方法進(jìn)行研究的學(xué)科，它是計算學(xué)科發(fā)展的必然產(chǎn)物，也是學(xué)科方法論中的重要內(nèi)容。關(guān)于“GOTO語句”問題的爭論直接導(dǎo)致了一個新的學(xué)科分支領(lǐng)域，即程序設(shè)計方法學(xué)的產(chǎn)生。程序設(shè)計方法學(xué)是對程序的性質(zhì)及其設(shè)計的理論和方法進(jìn)行研究的學(xué)科，它是計算學(xué)科發(fā)展的必然產(chǎn)物，也是學(xué)科方法論中的重要內(nèi)容。2.5“哲學(xué)家共餐”問題與計算機(jī)的資源管理計算機(jī)的資源分軟件資源和硬件資源。硬件的資源主要有：CPU、存儲器、以及輸入和輸出設(shè)備等；軟件資源則是指存儲于硬盤等存儲設(shè)備之中的各類文件。在計算機(jī)中，操作系統(tǒng)負(fù)責(zé)對計算機(jī)軟硬資源進(jìn)行控制和管理，要使計算機(jī)系統(tǒng)中的軟硬件資源得到高效的使用，就會遇到由于資源共享而產(chǎn)生的問題。下面，我們通過生產(chǎn)者－消費(fèi)者問題，和“哲學(xué)家共餐”問題來了解這方面的內(nèi)容。生產(chǎn)者－消費(fèi)者問題

一個生產(chǎn)者和一個消費(fèi)者以及一個硬件資源。所謂消費(fèi)者是指使用某一軟硬件資源時的進(jìn)程，而生產(chǎn)者是指提供（或釋放）某一軟硬件資源時的進(jìn)程。一個重要的概念，即信號燈，它借用了火車信號系統(tǒng)中的信號燈來表示進(jìn)程之間的互斥?！罢軐W(xué)家共餐”問題5個哲學(xué)家圍坐在一張圓桌旁，每個人的面前擺有一碗面條，碗的兩旁各擺有一只筷子一個哲學(xué)家的生活進(jìn)程可表示為：（1）思考問題；（2）餓了停止思考，左手拿一只筷子（拿不到就等）；（3）右手拿一只筷子（拿不到就等）；

（4）進(jìn)餐；（5）放右手筷子；（6）放左手筷子；（7）重新回到思考問題狀態(tài)（1）。問題是：如何協(xié)調(diào)5個哲學(xué)家的生活進(jìn)程，使得每一個哲學(xué)家最終都可以進(jìn)餐。按哲學(xué)家的活動進(jìn)程，當(dāng)所有的哲學(xué)家都同時拿起左手筷子時，則所有的哲學(xué)家都將拿不到右手的筷子，并處于等待狀態(tài)，那么哲學(xué)家都將無法進(jìn)餐，最終餓死。將哲學(xué)家的活動進(jìn)程修改一下，變?yōu)楫?dāng)右手的筷子拿不到時，就放下左手的筷子，這種情況是不是就沒有問題？不一定，因為可能在一個瞬間，所有的哲學(xué)家都同時拿起左手的筷子，則自然拿不到右手的筷子，于是都同時放下左手的筷子，等一會，又同時拿起左手的筷子，如此這樣永遠(yuǎn)重復(fù)下去，則所有的哲學(xué)家一樣都吃不到飯。程序并發(fā)執(zhí)行時進(jìn)程同步有關(guān)的經(jīng)典問題還有：讀－寫者問題（Reader－WriterProblem）、理發(fā)師睡眠問題（SleepingBarberProblem）等。2.6“兩軍問題”與計算機(jī)網(wǎng)絡(luò)

20世紀(jì)90年代，計算機(jī)網(wǎng)絡(luò)，特別是因特網(wǎng)（Internet）得到飛速的發(fā)展，新思想、新技術(shù)、新產(chǎn)品和新的應(yīng)用層出不窮，并開始滲透到人們生活的各個方面，若再將它列為操作系統(tǒng)中的一個研究主題就不合適了。為此，CC2001任務(wù)組在CC1991報告的基礎(chǔ)上，將它提取出來，作為計算學(xué)科一個新的主要領(lǐng)域，命名