计算机学科规范CS2013 —— 系统能力的培养 抛砖引玉研讨稿

Survey of CC2001/CS2008 Usage Developed survey to gather data for CS2013 Reviews usage of CC2001 and CS2008 Rating of importance of existing knowledge areas Rating of principles (e.g., importance of stylized classes) Suggestions for new topics of import/knowledge areas Survey released in December, 2010 ~1500 US department chairs/directors of UG education ~2000 International department chairs Received 201 responses

Importance of Topics

Suggested Topics (% of Suggestions)

Bounding Size of Curriculum CC2001 CS2008 CS2013 Tier 1 Tier 2 AL. Algorithms and Complexity 31 20 8 AR. Architecture and Organization 36 16 CN. Computational Science 1 DS. Discrete Structures 43 38 3 GV. Graphics and Visual Computing 2 HC. Human-Computer Interaction 4 IAS. Security and Information Assurance 6 IM. Information Management 10 11 5 IS. Intelligent Systems NC. Networking and Communication 15 OS. Operating Systems 18 PBD. Platform-based Development PD. Parallel and Distributed Computing 5.5 8.5 PL. Programming Languages 21 SDF. Software Development Fundamentals 47 41 SE. Software Engineering 19 SF. System Fundamentals 9 SP. Social and Professional Issues TOTAL 280 290 172.5 130.5 Tier1 + 100% Tier2: 303 Tier1 + 90% Tier2: 290 Tier1 + 80% Tier2: 277

Body of Knowledge Update (1) Addition of new Knowledge Areas Parallel and Distributed Computing Most important area to add as indicated by previous feedback Will include additional core hours Information Assurance and Security Second most important area to add Systems Fundamentals Cross-cutting systems concepts E.g., caching, locality, latency, parallelism Avoid tying these to any one topic (e.g. Operating Systems, Architecture) to foster broader thinking and new pedagogy Platform-based Development E.g., web, mobile devices, game consoles, robots, etc.

Body of Knowledge Update (2) Reorganization of topics in many Knowledge Areas Net-Centric Computing  Networking and Communications Sharpen focus on networking Web development moves to “Platform-based Development” Notably, includes a reworking of topics in Programming Fundamentals, Programming Languages, and Algorithms Move paradigm-specific concepts (e.g., OOP, Functional) to Programming Languages Programming Fundamentals + some Software Engineering = “Software Development Fundamentals” Seek to broaden thinking away from equating “Programming Fundamentals” with “Introductory Programming Courses” Introductory programming course includes: platform + language/paradigm + software development

CMU Computer Science Core: 15-122 Principles of Imperative Computation 15-150 Principles of Functional Programming 15-210 Parallel and Sequential Data Structures and Algorithms 15-213 Introduction to Computer Systems 15-251 Great Theoretical Ideas in Computer Science 15-451 Algorithm Design and Analysis 8

One Algorithms & Complexity elective: CMU计算机本科教学 One Algorithms & Complexity elective: 15-354 Computational Discrete Mathematics 15-355 Modern Computer Algebra 15-453 Formal Languages and Automata 21-301 Combinatorics 21-484 Graph Theory 9

CMU计算机本科教学 One Applications elective: 05-391 Designing Human-Centered Software 05-431 Software Structures for User Interfaces 10-601 Machine Learning 11-411 Natural Language Processing 15-313 Foundations of Software Engineering 15-322/15-323 Intro to Computer Music 15-381 Artificial Intelligence: Representation and Problem Solving 15-384 Robotic Manipulation 15-385 Computer Vision 15-415 Database Applications 15-462 Computer Graphics 10

CMU计算机本科教学 One Logics and Languages elective: 15-312 Foundations of Programming Languages 15-317 Constructive Logic 15-414 Bug Catching: Automated Program Verification and Testing 21-300 Basic Logic 80-311 Computability and Incompleteness 11

CMU计算机本科教学 One Software Systems elective: 15-410 Operating System Design and Implementation 15-411 Compiler Design 15-418 Parallel Computer Architecture and Programming 15-440 Distributed Systems 15-441 Computer Networks 12

计算机系统基础 1998年在CMU开设 2002年正式出版教材 2010年第2版发行 涵盖了计算机系统领域的广泛内容 但仅从程序员的角度介绍，不与后续课程抢内容

计算机系统基础 汇编 组成与体系结构 操作系统 I/O与网络编程 二进制，汇编，link/loader 流水线，超标量，memory hierarchy 操作系统 Fork/execve/wait/signal (shell), 虚存 I/O与网络编程 I/O, 网络程序设计, 并发程序设计

计算机系统基础 可接触的概念、做中学 设计了8个labs Bit operation Bombing (tracker) Buffer overflow attack (hacker) Pipeline design (using HCL) Code optimization Shell Malloc Proxy

Great Theoretical Ideas in Computer Science How to use theoretical ideas to formulate and solve problems in computer science Integrate mathematical material with general problem solving techniques and computer science applications Examples are drawn from Algorithms, Complexity Theory, Automata Theory, Game Theory, Probability Theory, Graph Theory, Algebra, Cryptography, and Combinatorics Assignments involve both mathematical proofs and programming

Great Theoretical Ideas in Computer Science Number Pancakes with a Problem! Choose Your Representation! Unary, Binary, and Beyond One Step at a Time: Induction On Raising a Number to a Power Euclid's Great Recursive Algorithm for GCD Fibonacci Numbers: An Unexpected Formula Modular Arithmetic and the RSA Cryptosystem

Great Theoretical Ideas in Computer Science Counting: Counting I: One To One Correspondence and Choice Tree Representation Counting II: Recurring Problems and Correspondences Counting III: Polynomials Count! Pascal's Triangle

Great Theoretical Ideas in Computer Science Computation: The One Minute to Learn Programming Language: Finite Automata Playing Symbol Games: Logic, Language, and Meaning On Time versus Input Size Problem Solving: The Method behind the AHA! Grade School Revisited: How to Add and Multiply Grade School Again: A Parallel Perspective

Great Theoretical Ideas in Computer Science Probability Methods Probability I: Counting in Terms of Proportions Probability II: Probability Pitfalls and Paradoxes Counting, Naming, and Worst-Case Compression Dating Theory: Who Wins the Battle of the Sexes? Probability III: Random Variables and Great Expectations! Probability IV: Event Space in an Infinite Choice Tree Probability V: Random Walks.

Great Theoretical Ideas in Computer Science Computational Theory Thales's Legacy: What is a Proof? Cantor's Legacy: Infinity and Diagonalization. Turing's Legacy: The Limits of Computation Godel's Legacy: The Limits of the Symbol Game Ancient Paradoxes with an Incompressible Resolution

M I T 的 核心 课程

计算机系统工程 互联网成为主流以及多核的出现 如何控制计算机系统的设计复杂性 其它系统设计的主要问题 2011年开始授课 Strong modularity using client-service design Naming Virtualization 其它系统设计的主要问题 Performance Networks Fault Tolerance Atomicity and Consistency Security 2011年开始授课

计算机系统工程 大量的经典论文阅读 Worse is Better A Fast File System for UNIX The X Window System The Evolution of an x86 Virtual Machine Monitor End-to-end Arguments in System Design MapReduce The Design and Implementation of a Log-Structured File System RAID: A Case for Redundant Arrays of Inexpensive Disks Hints of Computer System Design

计算机系统工程 设计类 project Lab tagged file system 设计类google-doc系统 The UNIX File System (practice file system related commands) The UNIX Time-Sharing System (practice other shell commands) Internet Routes and Measuring Round Trip Times (traceroute) MapReduce

Stanford计算机本科核心课程 Systems cs106B Programming Abstractions cs107 Computer Organization and Systems Computer Systems: A Programmer‘s Perspective by Bryant and O’Hallaron(CMU) . C Programming Language by Kernighan cs110 Principles of Computer Systems 课本：Principles of Computer System Design by Jerome H. Saltzer and M. Frans Kaashoek (MIT) Theory cs103 Mathematical Foundations of Computing cs109 Intro to Probability for Computer Scientists cs161 Data Structures and Algorithms 26

Berkeley计算机本科核心课程 Core CS 61A Structure and Interpretation of Computer Programs CS61B Data Structures CS61C Machine Structures EECS42 Digital Electronics Upper Division Required CS 170 Algorithms CS 162 Operating systems 27

Berkeley计算机本科核心课程 Breadth courses choose two from the following: CS 150 Digital Systems CS 152 Computer Architecture CS 160 User Interfaces CS 161 Computer Security CS 164 Languages and Compilers CS 169 Software Engineering CS 184 Computer Graphics CS 186 Databases CS 188 Artificial Intelligence 28

Utexas的《计算机系统概念》 Yale Patt， Introduction to Computing Systems: from bits and gates to C and beyond. 美国计算机界的卓越泰斗，与Knuth齐名 第1章 欢迎阅读本书 1.1 我们的目标 1.2 怎么才能做到 1.3 两个反复出现的理念 1.4 计算机系统简述 1.5 两个非常重要的思想 1.6 计算机：通用计算设备 1.7 从问题描述到电子运转 1.8 习题 第2章 bit、数据类型及其运算 2.1 bit和数据类型 2.2 整数数据类型 2.3 补码 2.4 二进制数与十进制数之间的转换 2.5 bit运算之一：算术运算 2.6 bit运算之二：逻辑运算 2.7 其他类型 2.8 习题 第3章 数字逻辑 3.1 MOS晶体管 3.2 逻辑门 3.3 组合逻辑 3.4 存储单元 3.5 内存的概念 3.6 时序电路 3.7 LC-3计算机的数据通路 3.8 习题 第4章 冯·诺伊曼模型 4.1 基本部件 4.2 LC-3：一台冯·诺伊曼机器 4.3 指令处理 4.4 改变执行顺序 4.5 停机操作 4.6 习题 第5章 LC-3结构 5.1 ISA概述 5.2 操作指令 5.3 数据搬移指令 5.4 控制指令 5.5 例子：字符数统计 5.6 总结：数据通路(LC-3) 5.7 习题 第6章 编程 第7章 汇编语言 第8章 输入/输出 第9章 TRAP程序和子程序 第10章 栈 第11章 C语言编程概述 第12章 变量和运算符 第13章 控制结构 第14章 函数 第15章 测试与调试技术 第16章 指针和数组 第17章 递归 笫18章 C语言中的I/O 第19章 数据结构

UIUC、Utexas、UMN、UMASS、上海交大、中科大等采用 Patt教授2011年中科大授课的Youku视频 http://www.youku.com/playlist_show/id_6525373.html （密码ustc） 英文(授课时使用,随时更新) http://acsa.ustc.edu.cn/htmls/ics-courses/en/index.html 大一就对计算机系统软件和硬件有整体的理解 Patt教授是美国计算机界的卓越泰斗，与Knuth齐名。他写的关于计算机第一门课的看法： http://users.ece.utexas.edu/~patt/ut.present.1mar06.pdf   国外的UIUC等大学在用Patt的教材。 http://courses.engr.illinois.edu/ece190/info/course_info.htm http://users.ece.utexas.edu/~patt/09f.306/，  www.ece.utexas.edu/~patt/00f.379K/descriptor.pdf http://www.mriedel.ece.umn.edu/wiki/index.php/EE1301  http://www.cis.umassd.edu/~rbalasubrama/CIS272/F07/ 旨在让计算机科学和电子工程专业的学生在刚刚开始本科学习的时候就对计算机系统软件和硬件有一个整体的理解，使得一年级的学生从整体上认识后续专业课程之间的联系，以便学生在学习后续专业课程时，能够较容易地学习更详细和更深入的相关内容，并了解这些课程内容是如何连贯在一起的。

《计算机系统概念》目录 第1章 欢迎阅读本书 1.1 我们的目标 1.2 怎么才能做到 1.3 两个反复出现的理念 1.4 计算机系统简述 1.5 两个非常重要的思想 1.6 计算机：通用计算设备 1.7 从问题描述到电子运转 1.8 习题

第2章 bit、数据类型及其运算 第3章 数字逻辑 第4章 冯·诺伊曼模型 第5章 LC-3结构 第6章 编程 第7章 汇编语言 第8章 输入/输出 第9章 TRAP程序和子程序 第10章 栈

第11章 C语言编程概述 第12章 变量和运算符 第13章 控制结构 第14章 函数 第15章 测试与调试技术 第16章 指针和数组 第17章 递归 笫18章 C语言中的I/O 第19章 数据结构

Programming in C++

Programming in C++ Introduction Programming and “Hello, Word!” Computers, People, and Programming Programming and “Hello, Word!” Objects, Types, and Values Computation Errors Writing a Program Completing a Program Technicalities: Functions, etc Technicalities: Classes, etc

Programming in C++ Input/Output Streams Customizing I/O A Display Model Graphics Classes Graphics Class Design Graphing Functions and Data Graphical User Interfaces

Programming in C++ Vector and Free Store Vectors and Arrays Vector, Template, and Exceptions Containers and Iterators Algorithms and Maps

Programming in C++ 每周一次lab指导 3个projects 国内传统教学方法 分数计算 字符界面游戏（Fox-hounds） 图形界面游戏 国内传统教学方法 以语言为主 课程结束后学生基本不会编程（有基础的除外） 基本上要在数据结构之后才会编程

实验和考试 Marking on the curve 开卷考试、考卷上网 实验 美国学生靠阅读学习 中国学生靠做题学习 每门课的实验占总成绩的30%～50% 基本以个人完成为主 与国际上通常以小组为单位不同 必须有防止抄袭的手段 定期变化实验内容 其它手段

助教 基础课每20名学生一名助教 组织学生讨论 防止抄袭 作业, labs, projects, 考卷 阅读内容（MIT图灵奖得主作助教） 开放课题 设计性实验 防止抄袭 Check-point(阶段性提交) 半自动代码检查抄袭 面试 在线测试

CS vs. EECS 纯CS（CMU, Stanford） EECS（MIT, Berkeley） 没有传统的组成和计算机系统结构课程 相关课程在ECE EECS（MIT, Berkeley） 有组成和系统结构课程 必须有较强的EECS（eg. Signal）基础

Bryant 《深入理解计算机系统》，适合有了程序设计基础以后 复旦大学课程体系（核心课程） 学年 上学期 下学期 一 高等数学(上) 线性代数 程序设计 高等数学(下) 普通物理(上) 计算机系统基础(上) 二 普通物理（下） 计算机系统基础(下) (并行)数据结构与算法 逻辑与可计算性 计算机系统工程 概率论 数据库设计 软件工程 三 (并行)算法设计与分析 Patt 《计算机系统概念》，大一入学可参考，程序部分略浅 Bryant 《深入理解计算机系统》，适合有了程序设计基础以后

课程体系（系统软件方向课程） 学年 上学期 下学期 三 编译系统 操作系统 数字部件设计 计算机体系结构 分布式系统 四

参考文献 Mehran Sahami, Stanford, Computer Science Curricula for the Coming Decade. Nov. 3, Peking University 臧斌宇，复旦大学， “借鉴国际先进经验 构建核心课程体系”. 2011年11月5日。

谢谢