计算机科学：算法、理论与机器
这门课学什么
这是 COS 126 的后半部分。内容先讲排序、查找和符号表，再讲图灵机、可计算性和难解性，最后讲机器语言、逻辑电路，并搭出一个完整 CPU。
内容摘要
这门课是普林斯顿 COS 126 的后半部分，接着 Programming with a Purpose 的第 1–10 讲，讲第 11–20 讲。它回答 3 个问题：怎样高效地解决计算问题，哪些问题根本无法用计算机解决，以及计算机硬件到底怎样工作。课程对应教材《计算机科学：跨学科方法》的后半部分。
全课分 3 个阶段。第 1 阶段是第 11–13 讲，讲算法和数据结构：二分查找、归并排序、栈、队列和用二叉搜索树实现的符号表。第 2 阶段是第 14–16 讲，讲计算理论：正则表达式与有限自动机、图灵机与可计算性、P 与 NP 和难解性。第 3 阶段是第 17–20 讲，讲计算机器：先用虚构的 TOY 机器写机器语言程序，再从开关和导线出发搭出组合电路，最后拼出一个完整的 CPU。
每讲配 1 个测验，全课共 10 个，没有编程作业。每讲另有可选的延伸材料。学生可以用教材书站上的代码和 TOY 模拟器自己动手实验。
学完以后，学生能解释从 Java 程序到机器指令再到逻辑电路的完整链条，能说明停机问题为什么不可解，能看懂 NP 完全性的基本论证，并能用常见数据结构写出高效程序。
讲课穿插大量历史背景，介绍图灵、香农和冯·诺依曼的贡献。这门课比前半部分轻：Coursera 估计每周 2–5 小时，重点在理解概念，不在编程量。
为什么值得学
一门短课就从算法讲到计算理论再讲到硬件。课程还讲图灵、香农、冯·诺依曼的历史贡献。
课程信息
- 学校
- 普林斯顿（Princeton）
- 课程号
- COS 126
- 讲师
- 罗伯特·塞奇威克（Robert Sedgewick）、凯文·韦恩（Kevin Wayne）
- 学期
- self-paced
- 平台
- Coursera
- 费用
- 免费
- 难度
- 中级
- 学时
- 10 讲，Coursera 估计约 2 周 × 每周 10 小时
- 先修
- 需要学过 Programming with a Purpose 或会基础 Java。
- 材料
- 视频、幻灯片、作业、教材
- 许可证
- 未注明
课程大纲 · 共 10 节
大纲依据：Coursera 模块列表（Lecture 11–20，每讲一个模块；结构取自 api.coursera.org onDemandCourseMaterials.v2 与课程页）（查看原始页面 ↗）
- 11排序与查找Sorting and Searching
讲二分查找、插入排序和归并排序，并用排序求一段文本的最长重复子串。
- 12栈与队列Stacks and Queues
讲栈和队列的 API 与典型用例，比较几种朴素实现，再用链表实现。
- 13符号表Symbol Tables
讲符号表 API 和用例，用二叉搜索树实现符号表并分析性能。
- 14计算理论导论Introduction to the Theory of Computing
讲正则表达式和确定有限自动机（DFA），以及它们的应用和能力上限。
- 15图灵机Turing Machines
介绍图灵机这一计算模型，讲通用图灵机和可计算性，以及不可计算问题带来的启示。
- 16难解性Intractability
讲 P 与 NP、多项式时间归约和 NP 完全性，以及实践中怎样应对难解问题。
- 17一台计算机器A Computing Machine
介绍 TOY 机器的数据类型、指令和操作方式，并用机器语言编程。
- 18冯·诺依曼机von Neumann Machines
讲程序和数据共用内存这一设计的历史背景、风险和实际影响，并用程序模拟 TOY 机器。
- 19组合电路Combinational Circuits
从开关和导线出发，讲布尔代数、数字电路、加法器和算术逻辑单元。
- 20中央处理器Central Processing Unit
讲寄存器、内存、程序计数器和各部件的连接，搭出 TOY 的完整处理器电路。
普林斯顿的其他经典课
- 算法（上） · Algorithms, Part I
- 算法（下） · Algorithms, Part II
- 计算机科学：有目的的编程 · Computer Science: Programming with a Purpose
- 解析组合学 · Analytic Combinatorics
- 算法分析 · Analysis of Algorithms
- 比特币与加密货币技术 · Bitcoin and Cryptocurrency Technologies