每个计算机专业学生应有的知识（翻译自：What every computer science major should know?）

2022年 11月 9日 1603点热度 3人点赞 0条评论

前言

在学习陈皓老师的极客专栏《左耳听风》时，看到了他推荐的一篇文章《What every computer science major should know》，即《每个计算机专业人员应有的知识》，觉得很适合于当作一个学习路径来了解整个计算机科学技术，自己英文水平还不够，看英文还是看的不太下去，于是想着边翻译边学习，也当作一个记录，有兴趣的同学可以阅读英文原文。

原文作者马修·迈特（Matthew Might）是美国犹他大学计算机学院的副教授，2007年于佐治亚理工学院取得博士学位。作者认为计算机专业的课程繁多，而且随着时代的变化，科目的课程组成也在不断变化。考虑到该领域的迅速发展，规划现代计算机科学学位的课程内容变得颇具挑战性。作者的老师也参与了这场讨论，最后作者把这些想法结合起来，来回答一个问题：“每个计算机科学专业的学生应该知道什么？”。为此，马修力求从四个方面来总结，得出这篇文章的内容。

要获得一份好工作，学生需要知道什么？
为了一辈子都有工作干，学生需要知道什么？
学生需要知道什么，才能进入研究生院？
学生需要知道什么，才能对社会有益？

原文作者以技术简介，具体建议，推荐阅读的形式对一些计算机科学技术进行描述。

作品集VS简历

从工程和数学领域发展而来的计算机科学专业，采用基于简历的方式招聘毕业生，但简历并不能说明程序员的能力。每个计算机科学专业的学生都应该建立一个作品集。作品集可以像个人博客一样简单，每个项目或成就都有一篇文章。一个更好的投资组合应该包括每个项目的页面，和可公开浏览的代码(可能托管在github或谷歌代码上)。对开源的贡献应该被链接和记录。代码组合可以让雇主直接判断能力。GPA和简历则不然。教授设计的课程项目应该在作品集上下功夫，而学生在每门课程结束时，应该花时间更新作品集。

作品集例子

技术交流

计算机科学领域的孤狼是濒临灭绝的物种。现代计算机科学家必须练习如何具备说服力，以及如何清晰地与非程序员交流他们的想法。在较小的公司中，程序员是否能与管理层交流自己的想法可能会决定公司的成败。不幸的是，这并不是一门课程就能解决的问题（尽管一门扎实的技术沟通课程没有坏处）。设计课程的时候需要为学生提供机会来展示他们的工作，并通过口头陈述来坚定他们的想法。

具体建议

我建议学生掌握演示工具，如PowerPoint或Keynote。（基于Latex的演示工具太静态了，不建议用来演示。）

但是在生成精美的数学文档方面，LaTeX无可匹敌。所有技术课程的书面作业都应在LaTeX中提交。

推荐阅读

Writing for Computer Science by Zobel.
Even a Geek Can Speak by Asher.
The LaTeX Companion.
The TeXbook by Knuth. (Warning: Experts only.)
Notes on Mathematical Writing.
Simon Peyton-Jones's advice on How to Give a Good Research Talk.
My advice on how to send and reply to email.

工程核心

计算机科学不完全是工程学。但是，它已经足够接近了。计算机科学家将与工程师一起工作。计算机科学家和传统工程师需要使用同一种语言——一种源于真实分析、线性代数、概率和物理学的语言。计算机科学家应该通过电磁学来研究物理学。但是，要做到这一点，他们需要学习多元微积分（还有微分方程）。在构建合理的模拟时，掌握概率和线性代数总是是非常重要的。在解释结果时，没有什么可以替代统计这个工具。

推荐阅读

Calculus by Spivak.
All of Statistics: A Concise Course in Statistical Inference by Wasserman.

Unix哲学

计算机科学家应该熟悉并实践Unix的计算哲学。Unix哲学（与Unix本身相反）强调语言抽象和组合，以影响计算。实际上，这意味着熟悉命令行计算、文本文件配置和无IDE软件开发的概念。

具体建议

鉴于Unix系统的普及，今天的计算机科学家应该精通基本的Unix，包括以下能力:

浏览和操作文件系统；
用管道组合流程；
使用emacs和vim轻松地编辑文件；
为软件项目创建、修改和执行Makefile；
编写简单的shell脚本。

除非他们了解Unix哲学，否则他们将拒绝Unix哲学。因此，最好挑战学生完成Unix具有相对优势的有用任务，例如：

查找给定目录中占用空间最多的五个文件夹。
报告计算机上重复的MP3（按文件内容而不是文件名）。
列出名字和姓氏均小写的名字列表，并适当地对其进行大写。
查找英语中所有以x为第二个字母，以n为倒数第二个单词的单词。
通过网络将您的麦克风输入直接路由到另一台计算机的扬声器。
将文件名中的所有空格替换为给定目录的下划线。
报告从特定IP地址对Web服务器的最后十次错误访问。

推荐阅读

The Unix Programming Environment by Kernighan and Pike.
The Linux Programming Interface: A Linux and UNIX System Programming Handbook by Kerrisk.
Unix Power Tools by Powers, Peek, O'Reilly and Loukides.
commandlinefu.
Linux Server Hacks.
The single Unix specification.

系统管理

一些计算机科学家嘲笑系统管理是一项“IT”任务。这种想法是，计算机科学家可以教自己如何做技术人员可以做的任何事情。这是真的。(在理论上)。然而这种态度是错误的：计算机科学家必须能够胜任并且安全地管理他们自己的系统和网络。软件开发中的许多任务无需经过系统管理员就可以最有效地执行。

具体建议

每个现代计算机科学家都应该能够:

安装和管理Linux发行版。
配置和编译Linux内核。
排除与dig, ping和traceroute连接的问题。
编译和配置web服务器，如apache。
编译和配置一个DNS守护进程，比如bind。
用文本编辑器维护一个网站。
切断和压接网络电缆。

推荐阅读

UNIX and Linux System Administration Handbook by Nemeth, Synder, Hein and Whaley.

编程语言

编程语言随着太阳周期的变化而起起落落。程序员的职业生涯不应该如此。虽然教授与雇主相关的语言很重要，但学生学习如何自学新语言也同样重要。学习编程语言的最好方法是学习多种编程语言和编程范式。学习第n种语言的困难是学习第n-1种语言的困难的一半。然而，要真正理解编程语言，就必须实现一种语言。理想情况下，每个计算机科学专业的学生都应该参加编译器课程。至少，每个计算机科学专业的学生都应该实现一个解释器。

具体语言

以下语言提供了范例和实际应用的合理混合:

Racket;
C;
JavaScript;
Squeak;
Java;
Standard ML;
Prolog;
Scala;
Haskell;
C++; and
Assembly.

Racket

Racket，作为Lisp的一种全功能语言，语法非常简单。对于一小部分学生来说，这种语法是一种障碍。直截了当地说，如果这些学生在接受一个外来的句法体系时有一个根本的心理障碍，即使是暂时的，他们也缺乏在计算机科学领域生存的智力。Racket强大的宏系统和高阶编程工具彻底消除了数据和代码之间的界限。如果教得正确，Lisp是自由度很高的语言。

推荐阅读

How to Design Programs by Felleisen, Findler, Flatt and Krishnamurthi.
The Racket Docs.

ANSI C

C是Silicon的简洁抽象。在嵌入式系统编程方面，C语言仍然没有对手。学习C语言可以加深对冯·诺依曼体系结构的理解，这是其他语言无法做到的。鉴于不良C编程会直接导致缓冲区溢出安全漏洞，程序员学习如何正确地编写C语言是至关重要的。

推荐阅读

ANSI C by Kernighan and Ritchie.

JavaScript

JavaScript是动态、高级语言（例如Python，Ruby和Perl）中流行的语义模型的良好代表。作为网络的母语，它的语言优势是独一无二的。

推荐阅读

JavaScript: The Definitive Guide by Flanagan.
JavaScript: The Good Parts by Crockford.
Effective JavaScript: 68 Specific Ways to Harness the Power of JavaScript by Herman.

Squeak

Squeak是Smalltalk的现代方言，是最纯粹的面向对象语言。它赋予了“面向对象”的精髓。

推荐阅读

Introductions to Squeak

Java

Java将会继续流行很长时间，不容忽视。

推荐阅读

Effective Java by Bloch.

Standard ML

Standard ML是Hindley-Milner（辛德雷-米尔纳）系统的清晰体现。Hindley-Milner系统是现代计算机领域最伟大（但最不为人知）的成就之一。尽管Hindley-Milner的类型推理具有指数级的复杂性，但对于人类感兴趣的程序来说，它总是快速的。类型系统足够丰富，可以表达复杂的结构不变量。它是如此丰富，事实上，类型良好的程序通常没有bug。

推荐阅读

ML for the Working Programmer by Paulson.
The Definition of Standard ML by Milner, Harper, MacQueen and Tofte.

Prolog

逻辑编程是计算思维的另一种范式，尽管它在应用上很小众。对于那些程序员可能需要在另一个范式中模拟逻辑编程的实例，理解逻辑编程是值得的。另一种值得学习的逻辑语言是miniKanren。miniKanren强调纯粹（不允许切割）的逻辑编程。这种约束演化出了一种被称为关系编程的逻辑编程风格，它授予Prolog程序通常不具有的属性。

推荐阅读

Scala

Scala是函数式编程语言和面向对象编程语言的完美融合。Scala就是Java应该有的样子。它构建在Java虚拟机之上，与现有的Java代码库兼容，因此，它是Java最有可能的继承者。

推荐阅读

Programming in Scala by Odersky, Spoon and Venners.
Programming Scala by Wampler and Payne.

Haskell

Haskell语言是Hindley-Milner语言家族皇冠上的明珠。Haskell充分利用了惰性，是所有主要编程语言中最接近纯数学编程的语言。

推荐阅读

Learn You a Haskell by Lipovaca.
Real World Haskell by O'Sullivan, Goerzen and Stewart.

ISO C++

C++是一个不可避免的恶魔。但是，既然一定要教，就一定要全教。特别是，计算机科学专业的学生甚至应该掌握模板元编程。

推荐阅读

The C++ Programming Language by Stroustrup.
C++ Templates: The Complete Guide by Vandevoorde and Josuttis.
Programming Pearls by Bentley.

Assembly 汇编

任何汇编语言都可以。既然x86很流行，它也可能是这样。学习编译器是学习汇编的最好方法，因为它使计算机科学家直观地了解高级代码将如何转换。

具体建议

计算机科学家应该了解生成式编程（宏）；词汇（还有动态）范围；闭包；延续；高阶函数；动态调度；子类型化；模块和函子；单子作为语义概念区别于任何特定的语法。

推荐阅读

Structure and Interpretation of Computer Programs by Abelson, Sussman and Sussman.
Lisp in Small Pieces by Queinnec.

离散数学

计算机科学家必须牢牢掌握形式逻辑和证明。通过代数运算和自然演绎的证明涉及到常规编程任务中常见的推理。归纳证明涉及递归函数构造中使用的推理。

计算机科学家必须精通正式的数学表示法，并能严格推理基本的离散结构：集、元组、序列、函数和幂集。

具体建议

对于计算机科学家来说，重要的是要涵盖以下方面的推理：

树；
图；
正式的语言；
自动机。

学生应该学习足够的数论来研究和实现常见的密码协议。

推荐阅读

How to Prove It: A Structured Approach by Velleman.
How To Solve It by Polya.

数据结构与算法

学生当然应该了解常见（或罕见但不合理有效）的数据结构和算法。

但是，比了解一个特定的算法或数据结构（这通常很容易查到）更重要的是，计算机科学家必须了解如何设计算法（例如，贪婪，动态规划），以及如何跨越算法的理想和实现的实质之间的差距。

具体建议

寻求长期稳定工作的计算机科学家至少应该知道以下所有内容：

哈希表；
链表；
树；
二叉搜索树；
有向图和无向图。

计算机科学家应该准备好实现或扩展对这些数据结构进行操作的算法，包括搜索元素，添加元素和删除元素的能力。为了完整起见，计算机科学家应该知道每个算法的命令式和函数式版本。

推荐阅读

CLRS.
Any of the Art of Computer Programming series by Knuth.

理论知识

掌握理论知识是研究生研究的先决条件。当理论为一个问题提供了硬边界（或者当它提供了一种绕过最初看起来是硬边界的方法）时，它是无价的。

计算复杂性可以说是所有计算机“科学”中为数不多的真正可预测的理论之一。

计算机科学家必须知道可管理性和可计算性的界限在哪里。忽略这些限制会在最好的情况下导致挫败感，而在最坏的情况下会导致失败。

具体建议

在本科阶段，理论至少应该涵盖计算模型和计算复杂性。

计算模型应该包括有限状态自动机、正则语言（和正则表达式）、下推自动机、上下文无关语言、形式语法、图灵机、lambda演算和不可测性。

在本科阶段，学生至少应该学习足够的复杂性，来理解P、NP、NP- hard和NP- complete之间的区别。

为了避免留下错误的印象，学生应该通过简化到SAT和使用现代SAT求解器来解决NP中的一些大问题。

推荐阅读

Introduction to the Theory of Computation by Sipser.
Computational Complexity by Papadimitriou.
Algorithms by Sedgewick and Wayne.
Introduction to Algorithms by Cormen, Leiserson, Rivest and Stein.

计算机体系结构

对计算机体系结构的深刻理解无可替代。计算机科学家应该从晶体管上理解计算机。对体系结构的理解应该包括抽象的标准层次：晶体管、门、加器、MUX、触发器、ALU、控制单元、缓存和RAM。对高性能计算的GPU模型的理解在可预见的未来是很重要的。

具体建议

对缓存、总线和硬件内存管理的良好理解是在现代系统上实现良好性能的必要条件。

为了更好地掌握机器架构，学生应该设计和模拟一个小型CPU。

推荐阅读

nand2tetris, which constructs a computer from the ground up.
Computer Organization and Design by Patterson and Hennessy.
"What every programmer should know about memory" by Drepper.

操作系统

任何足够大的程序最终都成为一个操作系统。因此，计算机科学家应该了解内核如何处理系统调用、分页、调度、上下文切换、文件系统和内部资源管理。

要获得性能，对操作系统的深入理解仅次于对编译器和计算机体系结构的理解。在编写没有运行时系统的嵌入式系统时，理解操作系统（我可以将其解释为包含运行时系统）变得尤为重要。

具体建议

让学生动手操作真正的操作系统是很重要的。

有了Linux和虚拟化，这比以往任何时候都容易。

为了更好地理解内核，学生可以：

在引导过程中打印“hello world”；
设计自己的调度程序；
修改页面处理策略；
并创建自己的文件系统。

推荐阅读

Linux Kernel Development by Love.

网络

鉴于网络的普遍存在，计算机科学家应该深入理解网络堆栈和网络中的路由协议。

在不可靠的传输协议（如IP）之上构建高效、可靠的传输协议（如TCP）的机制对计算机科学家来说不应该是魔法。它应该是核心知识。

计算机科学家必须了解协议设计中涉及的权衡——例如，何时选择TCP，何时选择UDP。（程序员也需要了解大规模使用UDP对拥塞的更大的社会影响。）

具体建议

考虑到现代程序员接触网络编程的频率，了解现有标准的协议是有帮助的，例如:

802.3和802.11；
IPv4和IPv6；
DNS、SMTP和HTTP。

计算机科学家应该了解包冲突解决中的指数退缩以及拥塞控制中涉及的累加增减机制。

每个计算机科学家都应该实现以下几点:

HTTP客户端和守护进程；
DNS解析器和服务器；
命令行SMTP邮件。

任何学生都应该学会使用wireshark（抓包工具）嗅探他们老师的Google查询，以此来通过入门网络课程。

要求所有的学生从头开始在IP上实现一个可靠的传输协议可能有点过分，但我可以说，这对作为学生的我个人来说是一次变革性的经历。

推荐阅读

Unix Network Programming by Stevens, Fenner and Rudoff.

安全

关于安全性的一个可悲的事实是，大多数安全性漏洞都来自草率的编程。更悲哀的事实是，许多学校在培训程序员保护代码方面做得很差。

计算机科学家必须知道程序可能被破坏的方法。

他们需要培养一种防御性编程意识-一种思考如何攻击自己的代码的思想。

安全性是最好在整个课程中分配的一种培训：每个学科都应警告学生其本身漏洞。

具体建议

至少，每个计算机科学家都需要明白：

社会工程学；
缓冲区溢出；
整数溢出；
代码注入漏洞；
竞态条件；
权限混乱。

一些读者指出，计算机科学家还需要了解基本的IT安全措施，例如如何选择合理的好密码，以及如何正确配置带有iptables的防火墙。

推荐阅读

Metasploit: The Penetration Tester's Guide by Kennedy, O'Gorman, Kearns and Aharoni.
Security Engineering by Anderson.

密码学

密码学使我们的数字生活成为可能。计算机科学家应该理解并能够实现以下概念，以及这样做的常见陷阱：

对称密钥密码系统；
公钥密码机制；
安全哈希函数；
质询-响应身份验证；
数字签名算法；
门限密码系统。

因为这是密码系统实现中的常见故障，所以每位计算机科学家都应该知道如何为手头的任务获取足够随机的数字。至少，正如几乎每一次数据泄露所显示的那样，计算机科学家需要知道如何对密码进行加密和哈希存储。

具体建议

每个计算机科学家都应该从使用前现代密码系统和手摇统计工具破解密文中获取乐趣。

RSA很容易实现，每个人都应该这样做。

每个学生都应该创建自己的数字证书，并在apache中设置https。（要做到这一点非常困难。）

学生还应该编写一个通过SSL连接的控制台Web客户端。

作为严格的实际问题，计算机科学家应该知道如何使用GPG；如何对SSH使用公钥身份验证；以及如何加密目录或硬盘。

推荐阅读

Cryptography Engineering by Ferguson, Schneier and Kohno.

软件测试

软件测试必须分布在整个课程中。

一门关于软件工程的课程可以涵盖测试的基本风格，但是没有什么可以代替实践这门艺术。

应该给学生上交的测试用例打分。

我使用学生提交的测试用例来对抗所有其他学生。

学生们似乎并不太在意开发防御性测试用例，但是当涉及到给同学打沙包时，他们会释放地狱。

用户体验

程序员经常为其他程序员编写软件，或者更糟的是，为自己编写软件。

用户界面设计（或者更广泛地说，用户体验设计）可能是计算机科学中最不被重视的方面。甚至在教学中也存在一种误解，认为用户体验是一种无法传授的“软”技能。在现实中，现代用户体验设计是基于人为因素工程和工业设计的经验原则。如果没有其他事情，计算机科学家应该知道接口需要使执行任何任务的难易程度与任务的频率乘以其重要性成正比。实际上，每个程序员都应该熟悉用HTML，CSS和JavaScript设计可用的Web界面。

推荐阅读