計算機科學各主領域及其基本問題

1、計算機科學各主領域及其基本問題本節(jié)綜合CC2013和CC2001報告，給出計算機科學各領域的簡介，以及計算機科學中各領域的基本問題。以下學科領域按字母先后順序排列，不分輕重。1. 算法與復雜性（Algorithms and Complexity，AL）算法是計算機科學和軟件工程的基礎?，F(xiàn)實世界中任何軟件系統(tǒng)的性能僅依賴于兩個 方面：一方面是所選擇的算法；另一方面是在各不同層次實現(xiàn)的效率。 對所有軟件系統(tǒng)的性能而言，好的算法設計都是至關重要的。此外，算法研究能夠深刻理解問題的本質(zhì)和可能的求解技術，而不依賴于具體的程序設計語言、程序設計模式、計算機硬件或其他任何與實現(xiàn)有關的內(nèi)容。計算的一個重要內(nèi)容

2、就是根據(jù)特定目的選擇適當?shù)乃惴ú⒓右赃\用，同時認識到可能存在不合適的算法。這依賴于對那些具有良好定義的重要問題求解算法的理解，以及認識到這些算法的優(yōu)缺點和它們在特定環(huán)境中的適宜性。效率是貫穿該領域的一個核心概念。下面，給出算法與復雜性領域的基本問題。（1）對于給定的問題類，最好的算法是什么？要求的存儲空間和計算時間有多少？空間和時間如何折中？（2）訪問數(shù)據(jù)的最好方法是什么？（3）算法最好和最壞的情況是什么？（4）算法的平均性能如何？（5）算法的通用性如何？2體系結(jié)構（Architecture and Organization，AR）計算機在計算技術中處于核心地位。如果沒有計算機，計算學科將只是

3、理論數(shù)學的一個 分支。作為計算專業(yè)的學生，都應該對計算機系統(tǒng)的功能部件、功能特點、性能和相互作用有一定的理解，而不應該只將計算機看作是一個執(zhí)行程序的黑盒子。了解計算機體系結(jié)構和組織還有一定的實際意義。為了構造程序，需要理解計算機體系結(jié)構，從而使該程序在一臺真正的機器上能更有效地運行。在選擇用于應用的系統(tǒng)時，應該理解各種部件之間的折中，如CPU、時鐘頻率與內(nèi)存大小的折中。下面，給出體系結(jié)構領域的基本問題。（1）實現(xiàn)處理器、內(nèi)存和機內(nèi)通信的方法是什么？（2）如何設計和控制大型計算系統(tǒng)，而且使其令人相信，盡管存在錯誤和失敗，但它仍然是按照我們的意圖工作的？（3）哪種類型的體系結(jié)構能有效地包含許多在一

4、個計算中能并行工作的處理元素？（4）如何度量性能？3計算科學（Computational Science，CN）從該學科誕生之日起，科學計算的數(shù)值方法和技術就構成了計算機科學研究的一個主要領域。隨著計算機問題求解能力的增強，該領域（正如該學科一樣）已經(jīng)在廣度和深度兩方面得到了發(fā)展?，F(xiàn)在，科學計算本身就代表了一個學科，一個與計算機科學密切相關的學科。為此，CC2001任務組只是將它劃為計算機科學的一個主領域，但不確定任何核心知識單元，也就是說，盡管它是計算機科學的一個組成部分，但不要求每個教學大綱都必須包含這些內(nèi)容。對于希望學習這部分知識的人，該領域提供了許多有價值的思想和技術，包括數(shù)值表示的精

5、度、誤差分析、數(shù)值技術、建模和仿真。 同時，學習過該領域課程的學生有機會在寬闊的應用領域中應用這些技術，例如下面這些領域：（1）分子力學。（2）流體力學。（3）天體力學。（4）經(jīng)濟預測。（5）優(yōu)化問題。（6）材料的結(jié)構化分析。（7）生物信息學。（8）計算生物學。（9）地質(zhì)建模。（10）X斷層攝影術的計算機化。下面，給出科學計算領域的基本問題。（1）如何精確地以有限的離散過程近似表示連續(xù)和無限的離散過程？（2）如何處理這種近似所產(chǎn)生的錯誤？（3）給定某一類方程在某精確度水平上能以多快的速度求解？（4）如何實現(xiàn)方程的符號操作，如積分、微分以及到最小項的歸約？（5）如何把這些問題的答案包含到一個有效

6、的、可靠的、高質(zhì)量的數(shù)學軟件包中？4離散結(jié)構（Discrete Structures，DS）離散結(jié)構是計算機科學的基礎內(nèi)容。盡管很少有計算機科學家專門從事離散結(jié)構的研究，但計算機科學許多領域的工作都要用到離散結(jié)構的概念。離散結(jié)構包括集合論、數(shù)理邏輯、代數(shù)系統(tǒng)、圖論和組合數(shù)學等重要內(nèi)容。離散結(jié)構的內(nèi)容在數(shù)據(jù)結(jié)構、算法以及其他計算機科學領域都有廣泛的運用。例如，在形式規(guī)格、驗證以及密碼學的研究和學習中，需要有生成并理解形式證明的能力；在計算機網(wǎng)絡、操作系統(tǒng)、編譯系統(tǒng)等領域要用到圖論的概念；在軟件工程和數(shù)據(jù)庫等領域需要使用集合論的概念。隨著計算機科學與技術的日益成熟，越來越完美的分析技術被用于解決實

7、際問題。為理解將來的計算技術，需要有堅實的離散結(jié)構基礎。計算學科的根本問題是“能行性”的問題。而凡是與“能行性”有關的討論，都是處理離散對象的。因為非離散對象，即所謂的連續(xù)對象，是很難進行能行處理的。因此，“能行性”這個計算學科的根本問題決定了計算機本身的結(jié)構和它處理的對象都是離散型的，甚至許多連續(xù)型的問題也必須在轉(zhuǎn)化為離散型問題以后才能被計算機處理。例如，計算定積分就是把它變成離散量，再用分段求和的方法來處理的。正是源于計算學科的根本問題，以離散型變量為研究對象的離散數(shù)學對計算技術的發(fā)展起著十分重要的作用。同時，又因為計算技術的迅猛發(fā)展，離散數(shù)學越來越受到重視。為此，CC2001特意將它從C

8、C1991的預備知識中抽取出來，列為計算機科學知識體的第一個主領域，命名為“離散結(jié)構”，以強調(diào)它的重要性。CS2013繼續(xù)強調(diào)該領域的重要作用，在新增了4個領域，在總的核心學時基本保持不變的情況下，僅該領域的核心學時減少了2個，維持在較高的41個核心學時上。5圖形學與可視化（Graphics and Visualization，GV）圖形學與可視化領域可以劃分成以下4個相互關聯(lián)的子領域。（1）計算機圖形學計算機圖形學是研究怎樣用計算機生成、處理和顯示圖形的一個學科分支領域。在計算機圖形學的研究過程中，有以下具體要求： 要求表示信息和構造應有助于圖像的產(chǎn)生和觀察。 要求方便用戶，使之能夠通過精心

9、設計的設備和技術與模型進行交互。 要求提供繪制模型的技術。 要求設計有助于圖像保存的技術。計算機圖形學的目標是對人的視覺中心及其他認知中心有進一步深入的了解。（2）可視化可視化是指使用計算機圖形學和圖像處理技術，將數(shù)據(jù)轉(zhuǎn)換成圖形或圖像在屏幕上顯示，并進行交互處理的理論、方法和技術。當前的可視化技術主要是探索人類的視覺能力以及聲音和觸覺（觸摸）。其目的在于通過它們進一步發(fā)現(xiàn)人類信息的處理過程。（3）虛擬現(xiàn)實虛擬現(xiàn)實是綜合利用計算機三維圖形技術、仿真技術、傳感技術、顯示技術、網(wǎng)絡技術等合成的一種虛擬環(huán)境，這種環(huán)境是計算機生成的一個以視覺感受為主，也包括視覺、觸覺的綜合可感知的人工環(huán)境，是計算機與用

10、戶之間的一種更為理想化的人機界面形式。（4）計算機視覺計算機視覺是研究怎樣利用計算機實現(xiàn)人的視覺功能（包括對客觀世界的三維場景的感知、識別和理解）的一個分支領域。對計算機視覺的理解和實踐取決于計算學科中的核心概念，但也和物理、數(shù)學和心理學等密切相關。下面，給出圖形學和可視化計算領域的基本問題。（1）如何選擇支撐圖像產(chǎn)生以及信息瀏覽的更好模型？（2）如何提取科學的（計算和醫(yī)學）和更抽象的相關數(shù)據(jù)？（3）圖像形成過程的解釋和分析方法。6人機交互（Human-Computer Interaction，HC）人機交互的重點在于理解作為交互式對象的人的行為，知道怎樣使用以人為中心的方法來開發(fā)和評價交互式

11、軟件系統(tǒng)。單元HC1（人機交互基礎）和單元HC2（建立簡單的圖形用戶界面）是最基本的內(nèi)容，需要學生掌握。剩余單元的內(nèi)容可作為高年級的選修課程。下面，給出人機交互領域的基本問題。（1）表示物體和自動產(chǎn)生供閱覽的照片的有效方法是什么？（2）接收輸入和給出輸出的有效方法是什么？（3）怎樣才能減小產(chǎn)生誤解和由此產(chǎn)生的人為錯誤的風險？（4）圖表和其他工具怎樣才能通過存儲在數(shù)據(jù)集中的信息去理解物理現(xiàn)象？7信息保障與安全（Information Assurance and Security，IAS）信息保障與安全是CS2013劃分的一個新領域，是世界公認的信息技術與計算的重要依靠，也是信息控制與處理過程的集

12、合，該集合即包括技術方面的內(nèi)容也包括政策方面的內(nèi)容，其目的在于通過保證其可用性、完整性、可認證性與機密性，用不可否認性來保護和定義信息和信息系統(tǒng)。保障包括了認證，使得當前的與過去的過程和數(shù)據(jù)都是有效的，保障與安全的共同作用使信息變得更加可靠和完整。下面，給出信息保障與安全領域的基本問題。（1）如何定義信息的不可否認性？（2）如何保證信息的可用性、完整性、可認證性與機密性？（3）安全規(guī)則與監(jiān)管的有效策略是什么，如何評估？8信息管理（Information Management，IM）信息管理幾乎在所有使用計算機的場合都發(fā)揮著重要的作用。它包括信息獲取、信息數(shù)字化、信息表示、組織、轉(zhuǎn)化和信息的表現(xiàn)

13、；有效地訪問和更新存儲信息的算法、數(shù)據(jù)建模和數(shù)據(jù)抽象以及物理文件的存儲技術、共享數(shù)據(jù)的信息安全、隱私性、完備性和保護。要求學生能夠建立概念和物理上的數(shù)據(jù)模型，對于給定的問題，能夠選擇和實現(xiàn)合適的信息管理解決方案。下面，給出信息管理領域的基本問題。（1）使用什么樣的建模概念來表示數(shù)據(jù)元素及其相互關系？（2）怎樣把基本操作（如存儲、定位、匹配和恢復）組合成有效的事務？（3）這些事務怎樣才能與用戶有效地進行交互？（4）高級查詢?nèi)绾畏g成高質(zhì)量的程序？（5）哪種機器體系結(jié)構能夠進行有效的恢復和更新？（6）怎樣保護數(shù)據(jù)，以避免非授權訪問、泄露和破壞？（7）如何保護大型的數(shù)據(jù)庫，以避免由于同時更新引起的不

14、一致性？（8）當數(shù)據(jù)分布在許多機器上時如何保護數(shù)據(jù)、保證性能？（9）文本如何索引和分類才能夠進行有效的恢復？9智能系統(tǒng)（Intelligent Systems，IS）人工智能關注的是自主系統(tǒng)的設計和分析。這些系統(tǒng)有些是軟件系統(tǒng)，而有些系統(tǒng)還配有傳感器和傳送器（如機器人或航天器），一個智能系統(tǒng)要有感知環(huán)境、執(zhí)行既定任務以及與其他代理進行交流的能力。這些能力包括計算機視覺、規(guī)劃和動作、機器人學、多代理系統(tǒng)、語音識別和自然語言理解等。智能系統(tǒng)依賴于一整套關于問題求解、搜索算法以及機器學習技術的專門知識表示機制和推理機制。人工智能為求解其他方法難以解決或者不太現(xiàn)實的問題提供了一些技術，包括啟發(fā)式搜索和

15、規(guī)劃算法、知識表示的形式化機制、機器學習技術以及語言理解、計算機視覺、機器人學等領域中所包含的感知和動作問題的方法。要求學生能夠針對特定的問題選擇合適的方法解決問題。下面，給出智能系統(tǒng)領域的基本問題。（1）基本的行為模型是什么？如何建造模擬它們的機器？（2）規(guī)則評估、推理、演繹和模式計算在多大程度上描述了智能？（3）通過這些方法模擬行為的機器的最終性能如何？（4）傳感數(shù)據(jù)如何編碼才使得相似的模式有相似的代碼？（5）電機編碼如何與傳感編碼相關聯(lián)？（6）怎樣學習系統(tǒng)的體系結(jié)構？（7）這些系統(tǒng)是如何表示它們對這個世界的理解的？10網(wǎng)絡與通信（Networking and Communication，

16、NC）計算機與通信網(wǎng)絡的發(fā)展，尤其是基于TCP/IP的網(wǎng)絡的發(fā)展，使得網(wǎng)絡技術在計算學科中變得更為重要。在CC2001報告中，該領域包括有計算機通信網(wǎng)絡的基本概念和協(xié)議、多媒體系統(tǒng)、Web標準和技術、網(wǎng)絡安全、移動計算以及分布式系統(tǒng)等傳統(tǒng)網(wǎng)絡的內(nèi)容。CS2013認為，這些內(nèi)容已得到發(fā)展和分化，因此對該領域進行了重組，將主要的關注放在該領域的網(wǎng)絡與通信方面，將網(wǎng)站應用和移動設備開發(fā)的內(nèi)容放在基于平臺的開發(fā)（PBD）領域中，將安全部分的內(nèi)容放入新的信息保障和安全（IAS）領域中。該領域的知識單元包括：網(wǎng)絡應用；可靠數(shù)據(jù)傳輸；路由與轉(zhuǎn)發(fā)；局域網(wǎng)；資源分配；移動網(wǎng)絡；社會網(wǎng)絡等。CC2001特別強調(diào)了

17、在該領域進行實踐教學的重要性，認為實踐教學能夠大大地加強學生對該領域基本概念的理解。在CC2001的基礎上，CS2013繼續(xù)強調(diào)了該領域的重要性，報告認為，現(xiàn)在許多計算的應用脫離網(wǎng)絡是無法繼續(xù)工作的，這些應用對底層網(wǎng)絡的依賴在未來將會得到加強，報告認為，網(wǎng)絡的設計依賴實際的約束條件，要求通過使用網(wǎng)絡工具、編寫網(wǎng)絡軟件等方式，向?qū)W生展示這些實際的約束條件。網(wǎng)絡課程有很多不同的組織方式。一些教育者傾向于“自頂向下”的教學方式：課程起始于應用程序，然后講授可靠數(shù)據(jù)傳輸、路由和轉(zhuǎn)發(fā)等。另外一些傾向于“自底向上”的教學方式：課程起始于網(wǎng)絡體系底層，然后講授數(shù)據(jù)傳輸、應用層等概念。無論那種方式，實驗都是該

18、領域課程教學中最重要的內(nèi)容，包括數(shù)據(jù)收集和綜合、建模、源代碼級的協(xié)議分析、網(wǎng)絡數(shù)據(jù)包的監(jiān)控、軟件構造以及對備選設計模型的評估等。下面，給出網(wǎng)絡與通信領域的基本問題。（1）網(wǎng)絡中的數(shù)據(jù)如何進行交換？（2）網(wǎng)絡性能如何評估？（3）網(wǎng)絡協(xié)議如何驗證？（4）網(wǎng)絡安全如何保證？（5）網(wǎng)絡構建與操作背后的網(wǎng)絡行為和關鍵原則是什么？11操作系統(tǒng)（Operating Systems，OS）操作系統(tǒng)是對計算機硬件行為的抽象，程序員用它來對硬件進行控制。操作系統(tǒng)還負責管理計算機用戶間的共享資源（如文件等）。本領域的主題解釋了影響現(xiàn)代操作系統(tǒng)設計的各種問題。相應的課程還應該包括一個實驗部分。近年來，操作系統(tǒng)及其抽象

19、機制相對于應用軟件變得更加復雜，這就要求在系統(tǒng)學習操作系統(tǒng)內(nèi)部算法實現(xiàn)和數(shù)據(jù)結(jié)構之前，對操作系統(tǒng)有深入的理解。因此操作系統(tǒng)的課程不僅要強調(diào)操作系統(tǒng)的使用（外部特性），還要強調(diào)它的設計和實現(xiàn)（內(nèi)部特性）。操作系統(tǒng)中的許多思想在其他計算機科學領域也有相當廣泛的應用，例如并行程序設計、算法設計與實現(xiàn)、虛擬環(huán)境的創(chuàng)建、網(wǎng)絡高速緩存、安全系統(tǒng)的創(chuàng)建、網(wǎng)絡管理等。下面，給出操作系統(tǒng)領域的基本問題。（1）在計算機系統(tǒng)操作的每一個級別上，可見的對象和允許進行的操作各是什么？（2）對于每一類資源，能夠?qū)ζ溥M行有效利用的最小操作集是什么？（3）如何組織接口才能使得用戶只需與抽象的資源而非硬件的物理細節(jié)打交道？（4

20、）作業(yè)調(diào)度、內(nèi)存管理、通信、軟件資源訪問、并發(fā)任務間的通信以及可靠性與安全的控制策略是什么？（5）通過少數(shù)構造規(guī)則的重復使用進行系統(tǒng)功能擴展的原則是什么？12基于平臺的開發(fā)（Platform-based Development，PBD）該部分的內(nèi)容不構成嚴格意義上的學科分支，它的劃分是為了教學上的需要，將軟件開發(fā)基礎（SDF)分支領域中基于指定平臺的內(nèi)容抽取出來，對它進行強調(diào)而劃分的，其基本的知識單元已在第一章中列出。它的基本問題與軟件開發(fā)基礎分支領域的基本問題相同，本書不再重新給出。13并行與分布式計算（Parallel and Distributed Computing，PD）CC2001

21、將并行性的內(nèi)容作為選修內(nèi)容分別穿插在不同的學科領域。CS2013考慮到并行與分布式計算越來越突出的作用，劃分了這個新的領域。該領域包括程序設計模板，編程語言，算法，性能，體系結(jié)構和分布式系統(tǒng)等內(nèi)容。并行和分布式計算建立在學科許多分支領域的基礎上，包括對基礎系統(tǒng)概念的理解，如并發(fā)和并行執(zhí)行、一致性狀態(tài)、內(nèi)存操作和延遲。由于進程間的通信和協(xié)作根植于消息傳遞和共享內(nèi)存模型的計算中，也存在于算法之中，如原子性、一致性以及條件等。因此，要想在實踐中提高對該領域的把握，需要先對并發(fā)算法、問題分解策略、系統(tǒng)架構、實施策略與性能分析等內(nèi)容有一個較深入的認知。下面，給出并行和分布式計算領域的基本問題。（1）機器

22、的結(jié)構如何保證大量處理單元能夠有效協(xié)同工作最終實現(xiàn)一個計算的并行？（2）任務如何劃分到不同的處理器上執(zhí)行？（3）并行算法與分布式算法的性能如何評價？（4）分布式計算如何組織才能使通過通信網(wǎng)連接在一起的自主計算機參加到一項特定的計算中，如何在計算的過程中保持網(wǎng)絡協(xié)議、主機地址、帶寬和其他使用資源的透明性？14程序設計語言（Programming Languages，PL）程序設計語言是程序員與計算機交流的主要工具。一個程序員不僅要至少掌握一種程序設計語言，更要了解各種程序設計語言的不同風格。在工作中，程序員會使用不同風格的語言，也會遇到許多不同的語言。為了迅速掌握一門新語言，程序員必須理解程序設

23、計語言的語義以及在不同的程序設計范式之間設計上的折中。為了理解程序設計語言實用的一面，還要求具有程序設計語言翻譯和諸如存儲分配等方面的基礎知識。下面給出程序設計語言領域的基本問題。（1）語言（數(shù)據(jù)類型、操作、控制結(jié)構、引進新類型和操作的機制）表示的虛擬機的可能組織結(jié)構是什么？（2）語言如何定義機器？機器如何定義語言？（3）什么樣的表示法（語義）可以有效地描述計算機應該做什么？15軟件開發(fā)基礎（Software Development Fundamentals，SDF）CS2013報告在CC2001的基礎上，對原報告劃分的程序設計基礎（PF）領域進行了重組，將關注的內(nèi)容進一步擴展到整個軟件的開發(fā)

24、過程中，要求學生在大學一年級就系統(tǒng)地掌握軟件開發(fā)的基本概念和技巧，包括算法的設計和簡單分析、基本程序設計的概念、數(shù)據(jù)結(jié)構和基本的軟件開發(fā)方法和工具等。CS2013報告認為，該領域課程的設計可以相當靈活，報告要求在基本的編程中只強調(diào)那些在所有編程范例都常見的基礎概念。報告認為，可以綜合程序設計語言，算法與復雜性，以及軟件工程等多個領域的內(nèi)容，選擇一個或多個編程范例（例如面向?qū)ο缶幊獭⒑瘮?shù)式編程或腳本編程）來說明這些概念。報告建議，將形式化的分析（例如大O、可計算性）與設計方法（如團隊項目、軟件生命周期）融入到系列課程中，以形成一個完整的、連貫一致的第一學年的系列課程。下面，給出軟件開發(fā)基礎領域的

25、基本問題。（1）對給定的問題，如何進行有效的描述并給出算法？（2）如何確定算法的復雜度？（3）如何正確選擇數(shù)據(jù)結(jié)構？（4）如何進行設計、編碼、測試和調(diào)試程序？16軟件工程（Software Engineering，SE）軟件工程是一門關于如何有效構建滿足用戶需求的軟件系統(tǒng)所需的理論、知識和實踐的學科。軟件工程適應各種軟件開發(fā)，它包含需求分析和規(guī)格、設計、構建、測試、運行和維護等軟件系統(tǒng)生存周期的所有階段。軟件工程使用工程化的方法、過程、技術和度量標準。它使用的工具有管理軟件開發(fā)的工具，軟件產(chǎn)品的分析和建模、質(zhì)量評估和控制工具，確保有條不紊且有控制實施軟件進化和復用的工具。軟件可由一個開發(fā)者或者一組開發(fā)者進行開發(fā)，他們需要選擇最適合已知開發(fā)環(huán)境的工具和方法。質(zhì)量、進度、成本等軟