免费教材分享-《理论计算机科学导论》-Boaz Barak

深度学习与NLP

推荐一本不错的理论计算机课程导论的入门教材。

文末附本教材免费pdf下载地址。

课程内容概述

这是一本关于理论计算机科学的本科入门教材。本教材主要希望表露以下主旨:

这种计算出现在各种自然和人工系统中，而不仅仅出现在现代硅基计算机中。

同样，除了作为一个极其重要的工具，计算也是描述自然、物理、数学甚至社会概念的有用工具。

许多不同计算模型的普遍性概念，以及代码和数据之间的二元性的相关概念。

一个人可以精确定义计算的数学模型，然后用它来证明(或者有时只是猜测)下界和不可能的结果的想法。

现代理论计算机科学中的一些令人惊讶的结果和发现，包括流行的NP完全性、交互作用的力量、随机性的力量和去随机化的可能性、密码学中使用“for good”的能力，以及量子计算的迷人可能性。

我希望通过本课程，学生能够认识到计算的威力和缺陷，因为它出现在各种环境中，包括看似“静态”的内容或“受限”的形式，如宏和脚本。他们应该能够理解关于计算的证明逻辑，包括归约的中心概念，并且理解“self-referential”证明(例如基于对角化的证明，它涉及给定自己代码作为输入的程序)。学生应该明白有些问题本来就很难解决，当他们面临新的问题时，能够认识到潜在的难以解决的问题。虽然本课程仅涉及密码学，但学生应该理解我们如何将计算难度用于密码学目的的基本思想。然而，本课程比任何具体技能都更旨在向学生介绍一种新的计算思维方式，并说明这种新的思维方式如何产生深远的见解和应用。

教材开源地址

https://introtcs.org/public/

教材目录