1.1.1.1. 先修课程¶

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

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

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

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

• 集合论与关系。

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

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

• 基本的数据结构与算法，包括线性表、二叉搜索树（BST）等查找结构、排序算法、堆、哈希，以及基本的图算法。

1.1.1.2. 我们将做什么¶

在本课程中，我们将讨论一些对你来说可能是新问题的题目和算法。但这并不是本课程真正的重点。大部分时间里，我们都在努力学习用以分析算法和问题的新技术。因此，我们会遇到很多这样的情形：看到一个"显而易见"的算法，然后费尽力气去证明它是最"优"的。所选的许多题目和算法都是刻意挑选出来的，目的是展现做分析的新途径。

本课程的主要论题和目标包括：

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

• 下界证明。

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

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

• 一些图算法。