声明：本文转自中大逸仙时空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]