线性规划是一种非常强大的算法工具。从本质上讲，线性规划问题要求你优化一个实变量的线性函数，该函数受到一些线性不等式系统的约束。这是一个用途极为广泛的框架，不仅可以立即概括流量问题，还可以用来讨论从优化生产流程到寻找实现健康饮食的最经济方法等各种其他问题。令人惊讶的是，这个非常通用的框架也承认高效的算法。在本单元中，我们将讨论线性规划问题的一些重要性，以及用于解决这些问题的一些工具。

虽然你迄今为止学到的许多算法在实践中应用得很多，但事实证明，现实世界中的问题大多没有已知的可证明的高效算法。这些问题要么无法用多项式算法解决，要么解决其中任何一个都会让你赢得一百万美元（参见 "千禧奖问题"），并因解决了计算机科学的主要问题 P vs NP 而永垂不朽。在明天的截止日期前尝试解决问题之前，最好先了解这些：)虽然在不久的将来，这些问题不太可能得到有效解决，但人们总能想出各种变通办法。在本模块中，您将学习经典的 NP-完全问题以及它们之间的还原。您还将使用基于 NP-complete（不完全问题）领域大量研究成果的高效专业软件，练习解决其中一些问题的大型实例。

上一模块结束后，您可能会感到悲伤：您刚刚学习了 5 门算法课程，却发现它们并不适用于大多数实际问题。不过，先不要放弃！人是有创造力的，无论如何，他们都需要解决这些问题，所以在实践中，往往有办法应对手头的 NP-完全问题。我们首先证明，NP-complete 问题的某些特例实际上可以在多项式时间内求解。然后，我们考虑精确算法，这些算法找到的解比蛮力算法快得多。最后，我们将介绍能在多项式时间内找到接近最优解的近似算法。

在之前的大多数讲座中，我们都对设计运行时间快（如小多项式）的算法感兴趣，并假设算法可以随机访问加载到内存中的输入。然而，在大数据分析的许多现代应用中，输入量非常大，无法存储在内存中。取而代之的是，输入以更新流的形式呈现，算法在扫描更新流的同时，会对迄今为止看到的更新流进行小结。这正是我们在本讲座中所研究的流式计算模型的背景。流模型非常适合设计和推理小空间算法。它在文献中受到了广泛关注，并且已经设计出了几种强大的算法原语，用于计算该模型中的基本流统计，其中有几种对大数据分析实践产生了影响。在本讲座中，我们将看到这样一种算法（CountSketch），它是一种用于查找数据流中前 k 个最频繁项的小空间算法。