聲明：本文轉自中大逸仙時空CS版。--Michael
-------------------------------------------------------------------
發信人: newer (討厭考試), 信區: CS
標? 題: 關于計算機科學與技術的知識體系
發信站: 逸仙時空 Yat-sen Channel (Mon Jun? 6 11:53:51 2005), 站內信件
因為感覺到人們對計算機科學有著太多的誤區,在這里給出美國CC2001(關于計算機科學
的教學大綱),看看計算機科學究竟應該學些什么.
CC2001把計算學科分成14個主要領域:
一.DS. Discrete Structures
DS1. Functions, relations, and sets
DS2. Basic logic
DS3. Proof techniques
DS4. Basics of counting
DS5. Graphs and trees
DS6. Discrete probability
介紹:
主要內容包括集合論,數理邏輯,近世代數,圖論以及組合數學等.該領域與計算學科各主領域有著緊密的聯系,CC2001為了強調它的重要性,特意將它列為計算學科的第一個主領域.該主領域以"抽象"和"理論"兩個學科形態出現在計算學科中,它為計算學科各分支領域解決其基本問題提供了強有力的數學工具.
二.PF. Programming Fundamentals
PF1. Fundamental programming constructs
PF2. Algorithms and problem-solving
PF3. Object-oriented programming
PF4. Fundamental data structures
PF5. Recursion
PF6. Event-driven and concurrent programming
PF7. Using APIs
介紹:
主要內容包括程序設計結構,算法,問題求解和數據結構等.它考慮的是如何對問題進行抽象.它屬于學科抽象形態方面的內容,并為計算學科各分支領域基本問題的感性認識(抽象)提供方法.基本問題主要包括:
1.對給定的問題如何進行有效的描述并給出算法?
2.如何正確選擇數據結構?
3.如何進行設計,編碼,測試和調試程序?
三.AL. Algorithms and Complexity
AL1. Basic algorithmic analysis
AL2. Algorithmic strategies
AL3. Fundamental computing algorithms
AL4. Distributed algorithms
AL5. Basic computability theory
AL6. The complexity classes P and NP
AL7. Automata theory
AL8. Advanced algorithmic analysis
AL9. Cryptographic algorithms
AL10. Geometric algorithms
AL11. Parallel algorithms
介紹:
主要內容包括算法的復雜度分析,典型的算法策略,分布式算法,并行算法,可計算理論,P類和NP類問題,自動機理論,密碼算法以及幾何算法等.1.抽象形態的主要內容:包括算法分析,算法策略(如蠻干算法,貪婪算法,啟發式算法,分治法等),并行和分布式算法等.
2.理論形態的主要內容:包括可計算性理論,計算復雜性理論,P和NP類問題,并行計算理論,密碼學等.
3.設計形態的主要內容:包括對重要問題類的算法的選擇,實現和測試,對通用算法的實現和測試,(如哈希表,圖和樹的實現與測試),對并行和分布式算法的實現和測試,對組合問題啟發式算法的大量實驗測試,密碼協議等.
基本問題主要包括:
1.對于給定的問題類,最好的算法是什么?要求的存儲空間和計算時間有多少?空間和時間如何折衷?
2.訪問數據的最好方法是什么?
3.算法最好和最壞的情況是什么?
4.算法的平均性能如何?
5.算法的通用性如何?
四.PL. Programming Languages
PL1. Overview of programming languages
PL2. Fundamental issues in language design
PL3. Virtual machines
PL4. Introduction to language translation
PL5. Language translation systems
PL6. 無效 systems
PL7. Models of 執行ution control
PL8. Declaration, modularity, and storage management
PL9. Programming language semantics
PL10. Programming paradigms
PL11. Language-based constructs for parallelism
介紹:
主要內容包括程序設計模式,虛擬機,類型系統,執行控制模型,語言翻譯系統,程序設計語言的語義學,基于語言的并行構件等.抽象形態的主要內容:包括基于語法和動態語義模型的語言分類(如靜態型,動態型,函數式,過程式,面向對象的,邏輯,規格說明,報文傳遞和數據流),按照目標應用領域的語言分類(如商業數據處理,仿真,表處理和圖形),程序結構的主要語法和語義模型的分類(如過程分層,函數合成,抽象數據類型和通信的并行處理),語言的每一種主要類型的抽象實現模型,詞法分析,編譯,解釋和代碼優化的方法,詞法分析器,掃描器,編譯器組件和編譯器的自動生成方法等.
理論形態的主要內容:包括形式語言和自動機,圖靈機(過程式語言的基礎),POST系統(字符串處理語言的基礎),lamda-演算(函數式語言的基礎),形式語義學,謂詞邏輯,時態邏輯,近世代數等.
設計形態的主要內容:包括把一個特殊的抽象機器(語法)和語義結合在一起形成的統一的可實現的整體特定語言(如過程式的(COBOL,FORTURN,ALGOL,Pascal,Ada,C),函數式的(LISP),數據流的(SISAL,VAL),面向對象的(Smalltalk,CLU,C++),邏輯的(Prolog),字符串(SNOBOL)和并發(CSP,Concurrent Pascal,Modula 2)),特定類型語言的指定實現方法,程序設計環境,詞法分析器和掃描器的產生器(如YACC,LEX),編譯器產生器,語法和語義檢查,成型,調試和追蹤程序,程序設計語言方法在文件處理方面的應用(如制表,圖,化學
公式),統計處理等.
基本問題主要包括:
1.語言(數據類型,操作,控制結構,引進新類型和操作的機制)表示的虛擬機的可能組織結構是什么?
2.語言如何定義機器?機器如何定義語言?
3.什么樣的表示法(語義)可以有效地用于描述計算機應該做什么?
五.AR. Architecture and Organization
AR1. Digital logic and digital systems
AR2. Machine level representation of data
AR3. Assembly level machine organization
AR4. Memory system organization and architecture
AR5. Interfacing and communication
AR6. Functional organization
AR7. Multiprocessing and alternative architectures
AR8. Performance enhancements
AR9. Architecture for networks and distributed systems
介紹:
主要內容包括數字邏輯,數據的機器表示,匯編級機器組織,存儲技術,接口和通信,多道處理和預備體系結構,性能優化,網絡和分布式系統的體系結構等.
抽象形態的主要內容:包括布爾代數模型,基本組件合成系統的通用方法,電路模型和在有限領域內計算算術函數的有限狀態機,數據路徑和控制結構模型,不同的模型和工作負載的優化指令集,硬件可靠性(如冗余,錯誤檢測,恢復與測試),VLSI裝置設計中的空間,時間和組織的折衷,不同的計算模型的機器組織(如時序的,數據流,表處理,陣列處理,向量處理和報文傳遞),分級設計的確定,即系統級,程序級,指令級,寄存器級和門級等.
理論形態的主要內容:包括布爾代數,開關理論,編碼理論,有限自動機理論等.
設計形態的主要內容:包括快速計算的硬件單元(如算術功能單元,高速緩沖存儲器),馮·諾依曼機(單指令順序存儲程序式計算機),RISC和CISC的實現,存儲和記錄信息,以及檢測與糾正錯誤的有效方法,對差錯處理的具體方法(如恢復,診斷,重構和備份過程
),為VLSI電路設計的計算機輔助設計(CAD)系統和邏輯模擬,故障診斷,硅編譯器等,在不同計算模型上的機器實現(如數據流,樹,LISP,超立方結構,向量和多處理器),超級計算機等.
基本問題主要包括:
1.實現處理器內存和機內通信的方法是什么?
2.如何設計和控制大型計算系統,而且使其令人相信,盡管存在錯誤和失敗,但它仍然是按照我們的意圖工作的?
3.哪種類型的體系結構能夠有效地包含許多在一個計算中能夠并行工作的處理元素?
4.如何度量性能?
六.OS. Operating Systems
OS1. Overview of operating systems
OS2. Operating system principles
OS3. Concurrency
OS4. Scheduling and dispatch
OS5. Memory management
OS6. Device management
OS7. Security and protection
OS8. File systems
OS9. Real-time and embedded systems
OS10. Fault tolerance
OS11. System performance 執行uation
OS12. 腳本ing
介紹:
主要內容包括操作系統的邏輯結構,并發處理,資源分配與調度,存儲管理,設備管理,文件系統等 .抽象形態的主要內容:包括不考慮物理細節(如面向進程而不是處理器,面向文件而不是磁盤)而對同一類資源上進行操作的抽象原則,用戶接口可以察覺的對象與內部計算機結構的綁定(Binding),重要的子問題模型(如進程管理,內存管理,作業調度,兩級存儲管理,和性能分析),安全計算模型(如訪問控制和驗證)等.
理論形態的主要內容:包括并發理論,調度理論(特別是處理機調度),程序行為和存儲管理的理論,(如存儲分配的優化策略),性能模型化與分析等
設計形態的主要內容:包括分時系統,自動存儲分配器,多級調度器,內存管理器,分層文件系統和其他作為商業系統基礎的重要系統組件,構建操作系統(如UNIX,DOS,Windows)的技術,建立實用程序庫的技術(如編輯器,文件形式程序,編譯器,連接器和設備驅動器),文件和文件系統等內容.
基本問題主要包括:
1.在計算機系統操作的每一個級別上,可見的對象和允許進行的操作各是什么?
2.對于每一類資源,能夠對其進行有效利用的最小操作集是什么?
3.如何組織接口才能使得用戶只需與抽象的資源而非硬件的物理細節打交道?
4.作業調度,內存管理,通信,軟件資源訪問,并發任務間的通信以及可靠性與安全的控制策略是什么?
5.通過少數構造規則的重復使用進行系統功能擴展的原則是什么?
七.NC. Net-Centric Computing
NC1. Introduction to net-centric computing
NC2. Communication and networking
NC3. Network security
NC4. The web as an example of client-server computing
NC5. Building web applications
NC6. Network management
NC7. Compression and decompression
NC8. Multimedia data technologies
NC9. Wireless and mobile computing
介紹:
主要內容包括計算機網絡的體系結構,網絡安全,網絡管理,無線和移動計算以及多媒體數據技術等.
抽象形態的主要內容:包括分布式計算模型(如C/S模式,合作時序進程,消息傳遞和遠方過程調用),組網(分層協議.命名.遠程資源利用,幫助服務和局域網協議),網絡安全模型(如通信,訪問控制和驗證)等.
理論形態的主要內容:包括數據通信理論,排隊理論,密碼學,協議的形式化驗證等.
設計形態的主要內容:包括排隊網絡建模和實際系統性能評估的模擬程序包,網絡體系結構(如以太網.FDDI.令牌網),包含在TCP/IP中的協議技術,虛擬電路協議,Internet,實時會議等.
基本問題主要包括:
1.網絡中的數據如何進行交換?
2.網絡協議如何驗證?
3.如何保證網絡的安全?
4.分布式計算的性能如何評價?
5.分布式計算如何組織才能夠使通過通信網連接在一起的自主計算機參加到一項計算中,而網絡協議,主機地址,帶寬和資源則具有透明性?
八.HC. Human-Computer Interaction
HC1. Foundations of human-computer interaction
HC2. Human-centered software 執行uation
HC3. Human-centered software development
HC4. Graphical user-interface design
HC5. Graphical user-interface programming
HC6. HCI aspects of multimedia systems
HC7. HCI aspects of collaboration and communication
介紹:
主要內容包括以人為中心的軟件開發和評價,圖形用戶接口設計,多媒體系統的人機接口等.
抽象形態的主要內容:包括人的表現模型(如理解,運動,認知,文件,通信和組織),原型化,
交互對象的描述,人機通信(含減少人為錯誤和提高人的生產力的交互模式心理學研究)等.
理論形態的主要內容:包括認知心理學,社會交互科學等.
設計形態的主要內容:交互設備(如鍵盤,語音識別器),有關人機交互的常用子程序庫,圖形專用語言,原形工具,用戶接口的主要形式(如子程序庫,專用語言和交互命令),交互技術(如選擇,定位,定向,拖動等技術),圖形拾取技術,以"人為中心"的人機交互軟件
的評價標準等.
基本問題主要包括:
1.表示物體和自動產生供閱覽的照片的有效方法是什么?
2.接受輸入和給出輸出的有效方法是什么?
3.怎樣才能減小產生誤解和由此產生的人為錯誤的風險?
4.圖表和其他工具怎樣才能通過存儲在數據集中的信息去理解物理現象?
九.GV. Graphics and Visual Computing
GV1. Fundamental techniques in graphics
GV2. Graphic systems
GV3. Graphic communication
GV4. Geometric modeling
GV5. Basic rendering
GV6. Advanced rendering
GV7. Advanced techniques
GV8. Computer animation
GV9. Visualization
GV10. Virtual reality
GV11. Computer vision
介紹:
主要內容包括計算機圖形學,可視化,虛擬現實,計算機視覺等4個學科子領域的研究內容.
抽象形態的主要內容:包括顯示圖像的算法,計算機輔助設計(CAD)模型,實體對象的計算機表示,圖像處理和加強的方法.
理論形態的主要內容:包括二維和高維幾何(包括解析,投影,仿射和計算幾何),顏色理論,認知心理學,傅立葉分析,線性代數,圖論等
設計形態的主要內容:包括不同的圖形設備上圖形算法的實現,不斷增多的模型和現象的實驗性圖形算法的設計與實現,在顯示中彩色圖的恰當使用,在顯示器和硬拷貝設備上彩色的精確再現,圖形標準圖形語言和特殊的圖形包,不同用戶接口技術的實現(含位圖設備上的直接操作和字符設備的屏幕技術),用于不同的系統和機器之間信息轉換的各種標準文件互換格式的實現,CAD系統,圖像增強系統等.
基本問題主要包括:
1.支撐圖像產生以及信息瀏覽的更好模型?
2.如何提取科學的(計算和醫學)和更抽象的相關數據?
3.圖像形成過程的解釋和分析方法?
十.IS. Intelligent Systems
IS1. Fundamental issues in intelligent systems
IS2. Search and constraint satisfaction
IS3. Knowledge representation and reasoning
IS4. Advanced search
IS5. Advanced knowledge representation and reasoning
IS6. Agents
IS7. Natural language processing
IS8. Machine learning and neural networks
IS9. AI planning systems
IS10. Robotics
介紹:
主要內容包括約束可滿足性問題,知識表示和推理,Agent,自然語言處理,機器學習和神經網絡,人工智能規劃系統和機器人學等.
抽象形態的主要內容:包括知識表示(如規則,框架和邏輯)以及處理知識的方法(如演繹,推理),自然語言理解和自然語言表示的模型(包括音素表示和機器翻譯),語音識別與合成,從文本到語音的翻譯,推理與學習模型(如不確定,非單調邏輯,Bayesian推理),啟發式搜索方法,分支界限法,控制搜索,模仿生物系統的機器體系結構(如神經網絡),人類的記憶模型以及自動學習和機器人系統的其他元素等.
理論形態的主要內容:包括邏輯(如單調,非單調和模糊邏輯),概念依賴性,認知,自然語言理解的語法和語義模型,機器人動作和機器人使用的外部世界模型的運動學和力學原理,以及相關支持領域(如結構力學,圖論,形式語法,語言學哲學與心理學)等.
設計形態的主要內容:包括邏輯程序設計軟件系統的設計技巧,定理證明,規則評估,在小范圍領域中使用專家系統的技術,專家系統外殼程序,邏輯程序設計的實現(如PROLOG),自然語言理解系統,神經網絡的實現,國際象棋和其他策略性游戲的程序,語音合成器,識別器,機器人等.
基本問題主要有:
1.基本的行為模型是什么?如何建造模擬它們的機器?
2.規則評估,推理,演繹和模式計算在多大程度上描述了智能?
3.通過這些方法模擬行為的機器的最終性能如何?
4.傳感數據如何編碼才使得相似的模式有相似的代碼?
5.電機編碼如何與傳感編碼相關聯?
6.學習系統的體系結構怎樣?
7.這些系統是如何表示它們對這個世界的理解的?
十一.IM. Information Management
IM1. Information models and systems
IM2. Database systems
IM3. Data modeling
IM4. Relational databases
IM5. Database query languages
IM6. Relational database design
IM7. Transaction processing
IM8. Distributed databases
IM9. Physical database design
IM10. Data mining
IM11. Information storage and retri執行
IM12. Hypertext and hypermedia
IM13. Multimedia information and systems
IM14. Digital libraries
介紹:
主要內容包括信息模型與信息系統,數據庫系統,數據建模,關系數據庫,數據庫查詢語言,關系數據庫設計,事務處理,分布式數據庫,數據挖掘,信息存儲與檢索,超文本和超媒體,多媒體信息與多媒體系統,數字圖書館等.
抽象形態的主要內容:包括表示數據的邏輯結構和數據元素之間關系的模型(如E-R模型,關系模型,面向對象的模型),為快速檢索的文件表示(如索引),保證更新時數據庫完整性(一致性)的方法,防止非授權泄露或更改數據的方法,對不同類信息檢索系統和數據庫(如超文本,文本,空間的,圖像,規則集)進行查詢的語言,允許文檔在多個層次上包含文本,視頻,圖像和聲音的模型(如超文本),人的因素和接口問題等 .
理論形態的主要內容:包括關系代數,關系演算,數據依賴理論,并發理論,統計推理,排序與搜索,性能分析以及支持理論的密碼學.
設計形態的主要內容:包括關系,層次,網絡,分布式和并行數據庫的設計技術,信息檢索系統的設計技術,安全數據庫系統的設計技術,超文本系統的設計技術,把大型數據庫映射到磁盤存儲器的技術,把大型的只讀數據庫映射到光存儲介質上的技術等.
基本問題主要包括:
1.使用什么樣的建模概念來表示數據元素及其相互關系?
2.怎樣把基本操作(如存儲,定位,匹配和恢復)組合成有效的事務?
3.這些事務怎樣才能與用戶有效地進行交互?
4.高級查詢如何翻譯成高質量的程序?
5.哪種機器體系結構能夠進行有效的恢復和更新?
6.怎樣保護數據,以避免非授權訪問,泄露和破壞?
7.如何保護大型的數據庫,以避免由于同時更新引起的不一致性?
8.當數據分布在許多機器上時如何保護數據,保證性能?
9.文本如何索引和分類才能夠進行有效的恢復?
十二.SE. Software Engineering
SE1. Software processes
SE2. Software requirements and specifications
SE3. Software design
SE4. Software validation
SE5. Software evolution
SE6. Software project management
SE7. Software tools and environments
SE8. Component-based computing
SE9. Formal methods
SE10. Software reliability
SE11. Specialized systems development
介紹:
主要內容包括軟件過程,軟件需求與規格說明,軟件設計,軟件驗證,軟件演化,軟件項目管理,軟件開發工具與環境,基于構件的計算,形式化方法,軟件可靠性,專用系統開發等.
抽象形態的主要內容:包括規約方法(如謂詞轉換器,程序設計演算,抽象數據類型和Floyd-Hoare 公理化思想),方法學(如逐步求精法,模塊化設計),程序開發自動化方法(如文本編輯器,面向語法的編輯器和屏幕編輯器),可靠計算的方法學(如容錯,安全,可靠性,恢復,多路冗余),軟件工具與程序設計環境,程序和系統的測度與評價,軟件系統到特定機器的相匹配問題域,軟件研制的生命周期模型等.
理論形態的主要內容:包括程序驗證與證明,時態邏輯,可靠性理論以及支持領域:謂詞演算,公理語義學和認知心理學等.
設計形態的主要內容:包括歸約語言,配置管理系統,版本修改系統,面向語法的編輯器,行編輯器,屏幕編輯器和字處理系統,實際使用并受到支持的特定軟件開發方法(如HDM,Dijkstra,Jockson,Mills和Yourdon倡導的方法),測試的過程與實踐(如遍歷,手工仿真,模塊間接口的檢查),質量保證與工程管理,程序開發和調試,成型,文本格式化和數據庫操作的軟件工具,安全計算系統的標準等級與確認過程的描述,用戶接口設計,可靠容錯的大型系統的設計方法,以"公眾利益為中心的"軟件從業人員認證體系.
基本問題主要包括:
1.程序和程序設計系統發展背后的原理是什么?
2.如何證明一個程序或系統滿足其規格說明?
3.如何編寫不忽略重要情況且能用于安全分析的規格說明?
4.軟件系統是如何歷經不同的各代進行演化的?
5.如何從可理解性和易修改性著手設計軟件?
十三.SP. Social and Professional Issues
SP1. History of computing
SP2. Social context of computing
SP3. Methods and tools of analysis
SP4. Professional and ethical responsibilities
SP5. Risks and liabilities of computer-based systems
SP6. Intellectual property
SP7. Privacy and civil liberties
SP8. Computer crime
SP9. Economic issues in computing
SP10. Philosophical frameworks
介紹:
主要內容包括計算的歷史,計算的社會背景,分析方法和工具,專業和道德責任,基于計算機系統的風險與責任,知識產權,隱私與公民的自由,計算機犯罪,與計算有關的經濟問題,哲學框架等.
該主領域屬于學科設計形態方面的內容.根據一般科學技術方法論的劃分,該領域中的價值觀,道德觀屬于設計形態中技術評估方面的內容.知識產權屬于設計形態中技術保護方面的內容.
而CC1991報告提到的美學問題則屬于設計形態中技術美學方面的內容.
基本問題主要包括:
1.計算學科本身的文化,社會法律和道德的問題.
2.有關計算的社會影響問題,以及如何評價可能的一些答案的問題.
3.哲學問題.
4.技術問題以及美學問題.
十四.CN. Computational Science
CN1. Numerical analysis
CN2. Operations research
CN3. Modeling and simulation
CN4. High-performance computing
介紹:
主要內容包括數值分析,運籌學,模擬和仿真,高性能計算.
抽象形態的主要內容:包括物理問題的數學模型(連續或離散)的形式化表示,連續問題的離散化技術,有限元模型等.
理論形態的主要內容:數論,線性代數,數值分析,以及支持領域,包括微積分,實數分析,復數分析和代數等.
設計形態的主要內容:用于線性代數的函數庫與函數包,常微分方程,統計,非線性方程和優化的函數庫與函數包,把有限元算法映射到特定結構上的方法等.
基本問題主要包括:
1.如何精確地以有限的離散過程近似表示連續和無限的離散過程?
2.如何處理這種近似產生的錯誤?
3.給定某一類方程在某精確度水平上能以多快的速度求解?
4.如何實現方程的符號操作,如積分,微分以及到最小項的歸約?
5.如何把這些問題的答案包含到一個有效的,可靠的,高質量的數學軟件包中?
--
※ 來源:．逸仙時空 Yat-sen Channel bbs.zsu.edu.cn．[FROM: 202.116.77.48]