1.1.1. 先修课程¶

本课程假定你已经具备若干计算机科学主题的充分背景知识。

你应该已经修读过离散数学课程，至少涵盖以下内容：

• 基本证明技巧，如反证法和归纳法。

• 求和与递推关系的基本求解技巧。

• 集合论与关系。

你应该已经修读过数据结构课程，至少涵盖以下内容：

• 基本算法分析，包括 big-oh、big-Omega 和 \(\Theta\) 记法。

• 基本数据结构和算法，包括线性表、BST 等查找结构、 排序算法、堆、散列以及基本图算法。

1.1.2. 我们将会做什么¶

在本课程中，我们将会讨论一些可能是你从未见过的问题和算法。 但这并不是本课程真正关注的焦点。 我们会花很多时间理解分析算法和问题的新技巧。 所以我们经常会看到这样的情形：我们见到了一个"显而易见"的算法， 并且努力证明它"最优"。 这里选取的许多待研究的问题和算法都被有意地用来展现新的分析途径。

本课程的主要议题与目标包括：

• 深入理解一个算法或问题的上界和（尤其是）下界。

• 下界证明。

• 分析技巧，包括求解大量求和与递推关系。

• 归约，最重要的是 NP 完全性理论。

• 作为一点额外奖励，还有少量可计算性理论。

1.1.3. 过程¶

本课程的主要工作来自每周的作业题。 它们通常由两到三个问题构成。 你应该预料到其中很多问题相当难。

布置这些作业的假设是你会与同伴合作完成（但不要求你一定要 与同伴合作）。 理解本课程的内容是很难的。 搞清楚问题的解法也被刻意设计得很难。 如果你能与人切磋、活跃地共同合作得出最终答案，效果最好。 无论如何，作为同伴所提解法的一名持怀疑态度的审查者， 是一项关键贡献，尤其是当你（正确地）指出错误或验证答案 是否合理时。 认识到一个答案不好或是不完整，对在这门课中取得成功至关重要。