第十章. 计算机科学（约翰·霍普克罗夫特班）— 面试备考指南

核心培养特色

• 理论导向：强调算法理论、计算理论、随机/近似算法、组合优化，而非纯工程编码
• 全英文教学环境：核心课程以英文授课、英文教材、英文讨论，国际化程度为全校之最
• AI 交叉：与机器学习、人工智能前沿紧密结合，鼓励理论服务于数据驱动科学
• 科研早进实验室：依托 IJCC 与各实验室，本科生即可参与前沿科研（论文/项目）
• 全球网络：Hopcroft 教授的国际学术资源带来海外研修、联合培养与顶尖学者讲座

模板一：学术导向型（适合有理论/科研兴趣的同学）

适用：有理论兴趣、自学过算法/ML 公开课、想走科研路线的同学。重点用"问题驱动"体现学术好奇心。

模板二：跨专业转方向型（适合从其他专业/方向转入计算机的同学）

适用：非计算机科班、跨专业申请的同学。坦诚短板 + 展示已做的弥补行动 + 强调跨学科价值，比掩饰更可信。

模板三：英文版（Research-Oriented，全英文自我介绍）

适用：所有申请 Hopcroft 班的同学必须准备全英文自我介绍。面试官极可能全程英文，建议背诵并练到自然，重点展示 research curiosity 与理论兴趣。

自我介绍要点总结

• 时长 1.5–2 分钟（英文约 180–220 词）；Hopcroft 班建议优先练英文版
• 结构：我是谁 → 理论/科研兴趣（用具体问题钩子，如 P vs NP / 近似算法） → 为什么是 Hopcroft 班 → 未来规划 → 致谢
• 多抛"研究型钩子"，引导面试官就你擅长的话题深入，而非被工程编码问题考倒
• 英文表达重在清晰与学术词汇（reduction / approximation ratio / tractable），不要求口音完美

考察对"理论 CS"的定位是否清晰，以及能否把抽象理论与工程实践联系起来。这是 Hopcroft 班最看重的"研究品味"题。

理论计算机科学研究"计算的本质与边界"，大致分三层：① 计算理论/可计算性——什么问题原则上能被计算（图灵机、停机问题）；② 复杂性理论——什么问题能被高效计算（P/NP、空间/时间层级）；③ 算法与数据结构设计——在可高效计算的范畴内如何做得更好（随机/近似/组合优化）。

与日常软件工程的关系——理论是工程的"地基与指南"：

• 复杂度意识：工程师选 HashMap 还是 TreeMap，本质是理论给出的 O(1) vs O(log n) 权衡。
• 不可行性警示：知道某问题是 NP 难，工程上就别傻等精确解，转而用启发式/近似——这是理论对实践的"止损"价值。
• 算法即生产力：编译器优化、数据库查询计划、分布式一致性协议，背后都是理论算法。
• 随机与近似的工程化：现代大数据/ML 系统大量用随机算法（如 HyperLogLog 估算基数、SGD 训练），理论给它们正确性/收敛性保证。

简言之：软件工程是"把能算的算好"，理论计算机是"先问能不能算、怎么算才最优"。Hopcroft 班要培养的是既懂前者、更能驾驭后者的人。

图着色问题：给定无向图 G=(V,E)，用最少的颜色给每个顶点染色，使任意相邻两顶点颜色不同。这个最小颜色数称为色数 χ(G)。判定"能否用 k 种颜色着色"是经典的 NP 完全问题。

为什么难：即使 k=3（3-着色）也已 NP 完全；只有二部图（无奇环）可 2-着色、平面图可由四色定理保证 4-着色。一般图求 χ(G) 没有已知多项式算法。

现实应用：

• 课程排课 / 考试安排：把"互不冲突（无公共学生）"的考试放进同一时段 → 顶点是考试，边表示有共同学生，最少颜色=最少时段。
• 寄存器分配：编译器把"生命周期不重叠"的变量放进同一寄存器，经典的图着色应用（Chaitin 算法）。
• 频率分配：无线基站/蓝牙设备若互相干扰（相邻）就不能同频，频率即颜色。
• 地图着色 / 调度：任务依赖图、带宽分配等。

工程上常用贪心着色（按度降序 Welsh–Powell）或 DSATUR 求可行解，配合回溯求精确解；这是"NP 难→用启发式"的典型范例，正契合 Hopcroft 班重视的近似/权衡思维。

解释 P vs NP 问题，以及为什么它被认为是计算机科学最重要的开放问题之一。

P is the class of decision problems solvable in polynomial time on a deterministic Turing machine — problems we can both find a solution to and verify it efficiently (e.g., shortest path, sorting).

NP (nondeterministic polynomial) is the class where a proposed solution can be verified in polynomial time, even if finding it may be hard (e.g., Boolean satisfiability SAT). Importantly, P ⊆ NP, because any problem we can solve quickly we can also verify quickly.

The question "P = NP?" asks whether every problem whose solution is easy to check is also easy to solve. Most theorists believe P ≠ NP, but no proof exists.

Why it matters so much:

• Foundational: it sits at the heart of computational complexity, distinguishing "search/solve" from "verify".
• Practical stakes: if P = NP, countless hard problems (optimization, scheduling, cryptography) would become efficiently solvable, revolutionizing medicine, logistics, and AI — but it would also break most modern cryptography, which relies on certain problems being hard.
• Millennium Prize: it is one of the seven Clay Mathematics Institute Millennium Problems, carrying a US$1,000,000 prize.
• NP-completeness: Cook–Levin showed SAT is NP-complete, meaning if any NPC problem is in P, then P = NP. This gives a concrete battleground for the question.

In short, P vs NP probes the very limits of what computation can achieve — which is exactly the kind of question theoretical computer science, and this class, cares about.

TSP：给定 n 个城市与两两距离，求访问每个城市恰好一次并回到起点的最短回路。它是经典的 NP 难问题（其决策版本属于 NP 完全）——暴力枚举 (n−1)!/2 条回路在 n 稍大时即不可行。

为什么难：解空间随 n 阶乘增长，且局部最优≠全局最优（"贪心走最近城市"极易陷入坏解）。它属于 强 NP 难，除非 P=NP，否则不存在多项式时间的精确算法能保证最优。

应对大规模实例的方法：

• 近似算法（有理论保证）：对满足三角不等式的度量 TSP，最小生成树 2-近似（走 MST 的 DFS 前序，再 shortcut）保证解 ≤ 2×最优；更好的 Christofides 算法可达 1.5-近似（MST + 奇度点最小完美匹配）。注意一般 TSP 不存在常数近似（除非 P=NP）。
• 启发式 / 元启发式：2-opt / 3-opt 局部搜索、模拟退火、遗传算法、蚁群优化——不求最优但实践中效果好。
• 精确法（中小规模）：分支定界、整数线性规划（ILP）求解器。

TSP 完美体现了 Hopcroft 班重视的"当精确不可得，如何用近似比/启发式换取可行"的权衡哲学。

图灵机（Turing Machine, TM）：一种抽象计算模型，由以下几部分组成：一条无限长的纸带（分格，每格写一个符号）、一个读写头（可读/写当前格并左右移动）、一个有限状态控制器（含状态转移规则 δ）。转移规则形如"在状态 q、读到符号 a 时，写 b、移动方向（L/R）、进入状态 q'"。从初始状态、纸带含输入开始运行，停机时输出结果。

Church–Turing 论题：一个函数"可有效计算"（算法可解）当且仅当它能被某个图灵机计算。换言之，所有合理的"算法"概念（λ演算、递归函数、 postnatal 机等）在计算能力上都与图灵机等价。注意这是一个论题（thesis）而非定理——无法严格证明，因为"有效计算"本身是非形式概念，但至今所有被提出的计算模型都未超越 TM 的能力。

为什么重要：① 它定义了"算法"的黄金标准，使"可计算性"成为严谨学科；② 由此推出存在不可判定问题——图灵机无法判定的事（如停机问题），任何等价模型也都无法判定；③ 它是现代计算机体系结构的理论原型（冯·诺依曼架构即 TM 的物理实现）。

随机算法在算法中引入随机源，用"概率上的大概率正确/高效"换取确定算法难以达到的简洁或突破最坏情况。

例一：随机化快速排序。普通快排最坏 O(n²)（坏 pivot）。随机选 pivot 后，期望复杂度 O(n log n)，且对任意输入分布都成立——无需对数据做任何假设。这是"用随机性消除最坏情况"的典范。

例二：蒙特卡洛算法（Monte Carlo）。以一定概率给出正确解，错误概率可通过重复降到任意小。典型：

• 素数测试 Miller–Rabin：确定性测试大数极慢，Miller–Rabin 用随机数做费马式检验，错误概率每轮减半，重复 k 轮后错误率 < 2⁻ᵏ，密码学广泛用。
• 用随机采样估计大规模图的性质（如连通性、三角形计数）：不遍历全图，抽样近似。

例三：拉斯维加斯算法（Las Vegas）。与蒙特卡洛互补——总是给出正确解，但运行时间随机。如随机化快速排序（结果必对，时间随机）、随机化最小割 Karger 算法。

价值总结：随机化常能把"最坏情况不可控"变成"期望可控"，或把"指数精确"变成"多项式高概率"。现代密码学、机器学习（SGD 随机梯度）、大数据 sketching 都建立在随机算法之上。

最坏情况复杂度（Worst-case）：对所有长度为 n 的输入，算法运行时间的上界。如快排最坏 O(n²)、归并最坏 O(n log n)。它给出绝对保证——无论什么输入都不会更差。

平均情况复杂度（Average-case）：在某种输入分布假设下，运行时间的期望值。如随机化快排平均 O(n log n)。它反映"典型表现"，但依赖分布假设。

何时关心哪个：

• 最坏情况优先：实时系统、安全/密码学、生命关键系统——必须保证"再坏也不会崩"。也用于复杂度下界证明。
• 平均情况优先：搜索引擎、推荐系统、通用库——典型输入占绝大多数，平均性能决定真实体验（如哈希表平均 O(1) 虽最坏 O(n) 仍被广泛使用）。
• 均摊分析（Amortized）介于二者：不单看一次，而看"一系列操作的总时间 ÷ 次数"，如动态数组扩容、并查集 O(α(n)) 均摊——很多情况下比最坏更有意义。

理论研究中最常用最坏情况（因为它不依赖分布假设、最稳健）；工程中常结合平均与均摊来选算法。

什么是近似算法？给出一个经典例子并说明其近似比。

An approximation algorithm is a polynomial-time algorithm for an NP-hard optimization problem that guarantees a solution within a bounded factor of the optimal. The approximation ratio ρ is the worst-case ratio between the algorithm's cost and the optimal cost: ALG / OPT ≤ ρ (for minimization). Unlike plain heuristics, approximation algorithms come with a provable performance guarantee.

Classic example — Vertex Cover 2-approximation: given a graph, find the smallest set of vertices touching every edge. Vertex Cover is NP-hard. The greedy approximation:

• Repeatedly pick an arbitrary edge, add both its endpoints to the cover, and remove all edges incident to them.
• The edges picked are disjoint, so the optimal cover must contain at least one endpoint of each → OPT ≥ k where k is the number of picked edges.
• Our cover has size 2k ≤ 2·OPT. Hence the algorithm is a 2-approximation (ratio ≤ 2).

Another famous one: Metric TSP (satisfying triangle inequality) has Christofides' 1.5-approximation, and a simple MST-based tour gives a 2-approximation. These ratios are exactly what theoretical CS studies — how close to optimal we can stay when exact optimum is infeasible.

两者都支持高效的插入/删除/查找，但语义与性能特征不同：

哈希表：平均 O(1) 查找/插入，依赖好的哈希函数与负载因子。优势是极快的点查询；劣势是不支持有序遍历、最坏 O(n)（冲突退化）、需要重哈希。

平衡树（红黑树/AVL）：保证 O(log n)，且天然有序——支持范围查询、前驱/后继、按序遍历。劣势是常数略大、实现复杂。

取舍原则：

• 只需要"按键取数"、不需要顺序 → 哈希表（如缓存、字典、对象存储的索引）。
• 需要有序性 / 范围查询 / 最近邻 → 平衡树（如 std::map、数据库索引的 B+ 树、定时器管理、优先级调度）。
• 对最坏延迟敏感（不能接受哈希退化 O(n)）→ 平衡树或带良好哈希的实现。
• 现代融合：C++ 无序容器用哈希、有序容器用红黑树；一些语言（如 Go）map 用哈希开放寻址；Redis 用哈希表 + 跳表（zset）兼顾点查与有序。

本质上：哈希表换"有序性"换取"点查速度"；平衡树用"稍慢的 log n"换取"有序与稳定最坏情况"。这是理论复杂度向工程权衡落地的典型案例。

证明问题 L 是 NP 完全，需两步：

第一步：证明 L ∈ NP。即给一个候选解，能在多项式时间验证其正确性（写验证器）。

第二步：证明 NP-hardness——找一个已知 NPC 问题 R，构造多项式时间归约 R ≤ₚ L。即：设计一个多项式时间的变换 f，把 R 的任意实例 x 映射成 L 的实例 f(x)，使得 x ∈ R ⟺ f(x) ∈ L。若 L 有多项式算法，则 R 也有（先变换再解 L），与 R 是 NPC 矛盾——故 L 也 NP 难。

归约的作用：它是"难度传递"的工具。Cook–Levin 定理已证明 SAT 是第一个 NPC；之后所有 NPC 问题都通过"从 SAT（或另一个 NPC）归约"链式证明。归约方向很关键：必须是从已知难问题归约到待证问题，表示"待证问题至少和已知难问题一样难"。

例子——证明 3-SAT 是 NPC：Cook–Levin 证明 SAT∈NPC；再把任意 SAT 公式变换为等价的 3-CNF（每个子句恰 3 字面）形式，多项式时间内完成且可满足性不变，即得 3-SAT ≤ₚ SAT 的反向链，证明 3-SAT 也是 NPC。另一个经典：把 3-SAT 归约到图着色（3-着色）、到团问题（Clique）、到顶点覆盖，从而证明它们皆 NPC。

过拟合（Overfitting）：模型在训练集上误差很小，但在未见过的测试集上误差大——它"记住了噪声"而非学到规律。本质是用过高复杂度去拟合有限数据。

正则化：在损失函数中加入惩罚项，限制模型复杂度。

• L2 正则（Ridge）：加 λ·‖w‖²，使权重整体变小、平滑，抑制某些特征被过度放大。
• L1 正则（Lasso）：加 λ·‖w‖₁，倾向产生稀疏权重（特征选择）。
• Dropout / 早停（Early Stopping）/ 数据增强：神经网络中常用，防止记住训练样本。

正则化项前的超参 λ 控制"拟合数据"与"控制复杂度"的权衡。

偏差-方差权衡（Bias–Variance Tradeoff）：总期望误差 ≈ 偏差² + 方差 + 不可约噪声。

• 高偏差 = 模型太简单/欠拟合（如用直线拟合曲线），训练测试都差。
• 高方差 = 模型太复杂/过拟合，对训练数据扰动敏感。

增加模型复杂度降偏差但升方差；正则化通过牺牲一点偏差、显著降低方差，使测试误差整体下降。这是 ML 理论的核心直觉，也体现了 Hopcroft 班倡导的"理论指导实践"。

解释监督学习与无监督学习的区别，并各举具体例子。

The key difference is whether the training data carries labels.

Supervised learning learns a mapping from inputs x to outputs y using labeled examples {(xᵢ, yᵢ)}. It is split into:

• Classification (discrete y): e.g., email spam detection (spam / not spam), image recognition (cat vs dog), medical diagnosis.
• Regression (continuous y): e.g., predicting house prices from size and location, or temperature forecasting.

Unsupervised learning finds structure in unlabeled data — no target output is given. Common tasks:

• Clustering: e.g., customer segmentation (K-means grouping buyers by behavior), document grouping.
• Dimensionality reduction: PCA or t-SNE to compress high-dimensional data for visualization or denoising.
• Density estimation / anomaly detection: flagging unusual transactions in fraud detection.

Why it matters: supervised learning needs costly labels but targets a known goal; unsupervised learning explores hidden patterns when labels are absent. There is also a middle ground — semi-supervised and self-supervised learning (e.g., large language models pretraining on unlabeled text), which are central to modern AI. For a theoretical CS student, the fascinating questions are the sample complexity and generalization bounds behind both paradigms.