教學課件-計算機科學導論-董榮勝

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

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

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

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

1.計算機工程知識體計算機工程知識體由18個知識領域（其中有2個與數(shù)學有關），175個知識單元組成。知識領域和知識單元如下所示。ALG算法與復雜度（30）ALG1歷史和概述（1）ALG2基本算法分析（4）ALG3算法策略（8）ALG4計算算法（12）ALG5分布式算法（3）ALG6算法復雜度（2）ALG7基本可計算性理論CAO計算機體系結構和組織（63）CAO1歷史和概述（1）CAO2計算機體系結構基礎（10）CAO3計算機的運算（3）CAO4存儲系統(tǒng)組織和體系結構（8）CAO5接口和通信（10）CAO6設備子系統(tǒng)（5）CAO7處理器系統(tǒng)設計（10）CAO8CPU的組織（10）CAO9性能（3）CAO10分布式系統(tǒng)模型（3）CAO11性能改進CSE計算機系統(tǒng)工程（18）CSE1歷史和概述（1）CSE2生命周期（2）CSE3需求分析和獲取（2）CSE4規(guī)格說明（2）CSE5體系結構設計（3）CSE6測試（2）CSE7維護（2）CSE8項目管理（2）CSE9并發(fā)(硬件/軟件)設計（2）CSE10實現(xiàn)CSE11專用系統(tǒng)CSE12可靠性和容錯性CSG電路和信號（43）CSG1歷史和概述（1）CSG2電量（3）CSG3電阻性電路和網(wǎng)絡（9）CSG4電抗性電路和網(wǎng)絡（12）CSG5頻率響應（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關系數(shù)據(jù)庫DBS5數(shù)據(jù)查詢語言DBS6關系型數(shù)據(jù)庫設計DBS7事務處理DBS8分布式數(shù)據(jù)庫DBS9物理數(shù)據(jù)庫設計DIG數(shù)字邏輯（57）DIG1歷史和概述（1）DIG2開關理論（6）DIG3組合邏輯電路（4）DIG4組合邏輯電路的模塊設計（6）DIG5存儲單元（3）DIG6時序邏輯電路（10）DIG7數(shù)字系統(tǒng)設計（12）DIG8建模和仿真（5）DIG9形式化驗證（5）DIG10故障模型和測試（5）DIG11可測試性設計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電子學（40）ELE1歷史和概述（1）ELE2材料的電子特性（3）ELE3二極管和二極管電路（5）ELE4MOS傳感器和偏置（3）ELE5MOS邏輯（7）ELE6雙極型晶體管和邏輯（4）ELE7參數(shù)設計及相關問題（4）ELE8存儲單元（3）ELE9接口邏輯和標準總線（3）ELE10運算放大器（4）ELE11電路建模和仿真（3）ELE12數(shù)據(jù)轉換電路ELE13電壓源和電流源ELE14放大器設計ELE15集成電路組成模塊ESY嵌入式系統(tǒng)（20）ESY1歷史和概述（1）ESY2嵌入式微控制器（6）ESY3嵌入式程序（3）ESY4實時操作系統(tǒng)（3）ESY5低功耗計算（2）ESY6可靠系統(tǒng)設計（2）ESY7設計方法（3）ESY8工具支持ESY9嵌入式多處理器ESY10網(wǎng)絡嵌入式系統(tǒng)ESY11接口和混合信號系統(tǒng)HCI人機交互（8）HCI1歷史和概述（1）HCI2人機交互基礎（2）HCI3圖形用戶接口（2）HCI4輸入/輸出技術（1）HCI5智能系統(tǒng)（2）HCI6人性化軟件評價HCI7人性化軟件開發(fā)HCI8交互式圖形用戶接口設計HCI9圖形用戶接口編程HCI10圖形和可視化HCI11多媒體系統(tǒng)NWK計算機網(wǎng)絡（21）NWK1歷史和概述（1）NWK2通訊網(wǎng)絡體系結構（3）NWK3通訊網(wǎng)絡協(xié)議（4）NWK4局域網(wǎng)和廣域網(wǎng)（4）NWK5客戶—服務器計算（3）NWK6數(shù)據(jù)安全性和完整性（4）NWK7無線和移動計算（2）NWK8性能評價NWK9數(shù)據(jù)通信NWK10網(wǎng)絡管理NWK11壓縮和解壓縮OPS操作系統(tǒng)（20）OPS1歷史和概述（1）OPS2設計原則（5）OPS3并發(fā)（6）OPS4調度和分派（3）OPS5內存管理（5）OPS6設備管理OPS7安全和保護OPS8文件系統(tǒng)OPS9系統(tǒng)性能評價PRF程序設計基礎（39）PRF1歷史和概述（1）PRF2程序設計范例（5）PRF3程序設計結構（7）PRF4算法和問題求解（8）PRF5數(shù)據(jù)結構（13）PRF6遞歸（5）PRF7面向對象程序設計PRF8事件驅動和并發(fā)程序設計PRF9使用APIsSPR社會與職業(yè)問題（16）SPR1歷史和概述（1）SPR2公共政策（2）SPR3分析方法和工具（2）SPR4職業(yè)和倫理責任（2）SPR5風險和責任（2）SPR6知識產(chǎn)權（2）SPR7隱私和公民自由（2）SPR8計算機犯罪（1）SPR9計算中的經(jīng)濟問題（2）SPR10哲學框架SWE軟件工程（13）SWE1歷史和概述（1）SWE2軟件過程（2）SWE3軟件需求和規(guī)約（2）SWE4軟件設計（2）SWE5軟件測試和驗證（2）SWE6軟件演化（2）SWE7軟件工具和環(huán)境（2）SWE8語言翻譯SWE9軟件工程管理SWE10軟件容錯性VLSVLSI設計和構造（10）VLS1歷史和概述（1）VLS2材料的電子特性（2）VLS3基本反向器結構的功能（3）VLS4組合邏輯結構（1）VLS5時序邏輯結構（1）VLS6半導體存儲器和陣列結構（2）VLS7芯片輸入/輸出電路VLS8工藝過程和布局VLS9電路特性和性能VLS10可選電路結構/低功耗設計VLS11半定制技術VLS12ASIC設計方法與數(shù)學有關的兩個知識領域及其知識單元DSC離散結構（33）DSC1歷史和概述（1）DSC2函數(shù)、關系和集合（6）DSC3基本邏輯（10）DSC4證明方法（6）DSC5計數(shù)基礎（4）DSC6圖和樹（4）DSC7遞歸（2）PRS概率和統(tǒng)計學（33）PRS1歷史和概述（1）PRS2離散概率（6）PRS3連續(xù)概率（6）PRS4期望（4）PRS5隨機過程（6）PRS6樣本分布（4）PRS7估計（4）PRS8假設檢驗（2）PRS9相關性和回歸2.計算機工程16門專業(yè)核心課程計算機導論程序設計基礎離散結構算法與數(shù)據(jù)結構電路與系統(tǒng)模擬與數(shù)字電子技術數(shù)字信息處理數(shù)字邏輯計算機組成結構計算機體系結構操作系統(tǒng)計算機網(wǎng)絡嵌入式系統(tǒng)軟件工程數(shù)據(jù)庫系統(tǒng)原理社會與職業(yè)道德1.3.3軟件工程知識體及所支撐的核心課程1.軟件工程知識體軟件工程知識體由11個知識領域（其中1個是應用知識領域），以及相應的57個知識單元構成。CMP計算基礎（172）CMP1計算機科學基礎（140）CMP2代碼開發(fā)技術（20）CMP3代碼開發(fā)工具（4）CMP4形式化開發(fā)方法（8）FND數(shù)學和工程基礎（89）FND1數(shù)學基礎（56）FND2軟件的工程基礎（23）FND3軟件的工程經(jīng)濟學（10）PRF職業(yè)實踐（35）PRF1團隊激勵/心理學（5）PRF2交流溝通技能（10）PRF3專業(yè)精神（20）MAA軟件建模與分析（53）MAA1建模基礎（19）MAA2模型分類（12）MAA3分析基礎（6）MAA4需求基礎（3）MAA5需求獲?。?）MAA6需求規(guī)約與文檔（6）MAA7需求確認（3）DES軟件設計（45）DES1設計概念（3）DES2設計策略（6）DES3體系結構設計（9）DES4人機界面設計（12）DES5詳細設計（12）DES6設計工具與設計評價（3）VAV軟件驗證與確認（42）VAV1基本知識（5）VAV2評審（6）VAV3測試（21）VAV4人機用戶界面測試和評價（6）VAV5問題分析報告（4）EVO軟件演化（10）；PRO軟件過程（13）EVO1演化過程（6）EVO2演化活動（4）PRO1軟件過程的概念（3）PRO2軟件過程的實現(xiàn)（10）QUA軟件質量（16）QUA1軟件質量概念與文化（2）QUA2軟件質量標準（2）QUA3軟件質量過程（4）QUA4過程保證（4）QUA5產(chǎn)品保證（4）MGT軟件管理（19）MGT1管理概念（2）MGT2項目計劃（6）MGT3項目人員和組織（2）MGT4項目控制（4）MGT5軟件配置管理（5）SE-SAS特定系統(tǒng)和應用（應用知識領域）SAS1以網(wǎng)絡為中心的系統(tǒng)SAS2信息系統(tǒng)和數(shù)據(jù)處理SAS3金融和電子商務系統(tǒng)SAS4容錯和可存活系統(tǒng)SAS5高安全系統(tǒng)SAS6安全攸關系統(tǒng)SAS7嵌入式和實時系統(tǒng)SAS8生物學系統(tǒng)SAS9科學系統(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ù)據(jù)結構和算法離散結構計算機體系結構操作系統(tǒng)和網(wǎng)絡數(shù)據(jù)庫工程經(jīng)濟學團隊激勵和溝通軟件工程職業(yè)實踐軟件工程與計算軟件工程導論軟件代碼開發(fā)技術人機交互的軟件工程方法大型軟件系統(tǒng)設計與軟件體系結構軟件測試軟件設計與體系結構軟件詳細設計軟件工程的形式化方法軟件質量保證與測試軟件需求分析軟件項目管理軟件過程與管理軟件工程綜合實習（含畢業(yè)設計）在制定具體的教學計劃時，又可將核心課程可以分為兩組，取其中一組即可。第一組課程是：軟件代碼開發(fā)技術，軟件設計與體系結構，軟件質量保證與測試，軟件需求分析，軟件項目管理。第二組課程是：大型軟件系統(tǒng)設計與軟件體系結構，軟件測試，軟件詳細設計，軟件工程的形式化方法，軟件過程與管理。1.3.4信息技術知識體及所支撐的核心課程1.信息技術知識體信息技術知識體由12個知識領域，以及相應的81個知識單元構成。ITF信息技術基礎(33)ITF1IT中的基本主題(17)ITF2組織問題(6)ITF3IT的歷史(3)ITF4IT及其信息原則(3)ITF5應用領域(2)ITF6數(shù)學與統(tǒng)計學在IT中的應用(2)HCI人機交互(20)HCI1人的因素(6)HCI2HCI方面的應用(3)HCI3以人為中心的評估(3)HCI4有效接口的開發(fā)(3)HCI5訪問性(2)HCI6新出現(xiàn)的技術(2)HCI7以人為中心的軟件開發(fā)(1)IAS信息保障與安全(23)IAS1基礎知識(3)IAS2安全機制(抵御方法)(5)IAS3操作性問題(3)IAS4策略(3)IAS5攻擊(2)IAS6安全領域(2)IAS7說明(1)IAS8信息狀態(tài)(1)IAS9安全服務(1)IAS10威脅分析模型(1)IAS11易受傷性(1)IM信息管理(34)IM1IM概念及基礎(8)IM2數(shù)據(jù)庫查詢語言(9)IM3數(shù)據(jù)組織體系結構(7)IM4數(shù)據(jù)建模(6)IM5數(shù)據(jù)庫環(huán)境管理(3)IM6特定目的數(shù)據(jù)庫(1)IPT綜合編程和技術(23)IPT1系統(tǒng)間通信(5)IPT2數(shù)據(jù)映射與交換(4)IPT3集成代碼(4)IPT4腳本技術(4)IPT5軟件安全實踐(4)IPT6混雜問題(1)IPT7編程語言概述(1)NET網(wǎng)絡(20)NET1網(wǎng)絡基礎(3)NET2路由與交換(8)NET3物理層(6)NET4安全性(2)NET5應用領域(1)NET6網(wǎng)絡管理PF編程基礎(38)PF1數(shù)據(jù)結構基礎(10)PF2編程構造基礎(9)PF3面向對象編程(9)PF4算法與問題解決(6)PF5事件驅動編程(3)PF6遞歸(1)PT平臺技術(14)PT1操作系統(tǒng)(10)PT2體系結構與組織(3)PT3計算基礎設施(1)PT4企業(yè)配置軟件PT5固件PT6硬件SA系統(tǒng)管理和維護(11)SA1操作系統(tǒng)(4)SA2應用(3)SA3管理性活動(2)SA4管理性領域(2)SIA系統(tǒng)集成和體系結構(21)SIA1需求(6)SIA2先決條件/資源(4)SIA3集成(3)SIA4項目管理(3)SIA5測試和QA(3)SIA6組織性環(huán)境(1)SIA7體系結構(1)SP社會與職業(yè)問題(23)SP1職業(yè)交流(5)SP2計算的歷史(3)SP3計算的社會環(huán)境(3)SP4團隊工作概念和問題(3)SP5知識產(chǎn)權(2)SP6計算的合法性問題(2)SP7組織機構環(huán)境(2)SP8職業(yè)道德問題和責任(2)SP9個人隱私和個人自由(1)WSWeb系統(tǒng)和技術(21)WS1Web技術(10)WS2信息體系結構(4)WS3數(shù)字化媒體(3)WS4Web的發(fā)展(3)WS5脆弱性(1)WS6社會性軟件

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

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

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

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

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

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

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

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

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

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

{

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

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

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

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

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

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

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