理论计算机科学导论 一本免费的开源教科书，涵盖计算机科学的基础理论，被哈佛大学本科生和研究生课程用作教材。你将学到：基础数学、计算模型、算法、可计算性、复杂性理论、密码学、随机化算法、量子计算。

理论计算机科学导论：索引

来源：https://introtcs.org/public/ Boaz Barak

写作中

这是一本正在编写中的教科书，面向理论计算机科学本科入门课程。我使用此文本教授哈佛大学CS 121课程（http://cs121.boazbarak.org/）。它也被用于弗吉尼亚大学CS 3102课程（https://uvatoc.github.io/）和加州大学洛杉矶分校CS181课程（https://hackmd.io/@raghum/introtcs）。

各章节见下文。你也可以下载单一PDF文件版本（https://files.boazbarak.org/introtcs/lnotes_book.pdf）（约600页，10MB）。

如果你有任何评论、建议、错别字修正等，非常感激你将其作为issue（https://github.com/boazbk/tcs/issues）或pull request（https://github.com/boazbk/tcs/pulls）提交到GitHub仓库 boazbk/tcs（https://github.com/boazbk/tcs），我在那里维护这些笔记的源文件。你也可以在下方每个章节的链接中发表评论。

请参见github.com/boazbk/tcscode代码仓库（https://introtcs.org/public/the%20tcscode%20repository）获取包含本书补充代码的jupyter笔记本。

关于本书的先前版本，请参见仓库发布页面（https://github.com/boazbk/tcs/releases）。本书的最新版本始终在此页面。

2023年秋季冻结版本： 我将在秋季期间仅进行少量编辑（错别字、局部修复），以免干扰教学。为保持引用和练习的一致性，教师可以使用以下冻结于2023年7月24日的版本：TCS导论 0.95版（https://github.com/boazbk/tcs/releases/download/v0.95/lnotes_book_fall2023.pdf）

图书章节

• 第p章： 前言（https://introtcs.org/public/lec_00_0_preface.html）（PDF：最佳排版（https://files.boazbarak.org/introtcs/lec_00_0_preface.pdf），Word：有缺陷（https://files.boazbarak.org/introtcs/lec_00_0_preface.docx））
• 第0章： 引言（https://introtcs.org/public/lec_01_introduction.html）（PDF：最佳排版（https://files.boazbarak.org/introtcs/lec_01_introduction.pdf），Word：有缺陷（https://files.boazbarak.org/introtcs/lec_01_introduction.docx））
• 第1章： 数学基础（https://introtcs.org/public/lec_00_1_math_background.html）（PDF：最佳排版（https://files.boazbarak.org/introtcs/lec_00_1_math_background.pdf），Word：有缺陷（https://files.boazbarak.org/introtcs/lec_00_1_math_background.docx））
• 第2章： 计算与表示（https://introtcs.org/public/lec_02_representation.html）（PDF：最佳排版（https://files.boazbarak.org/introtcs/lec_02_representation.pdf），Word：有缺陷（https://files.boazbarak.org/introtcs/lec_02_representation.docx））
• 第3章： 定义计算（https://introtcs.org/public/lec_03_computation.html）（PDF：最佳排版（https://files.boazbarak.org/introtcs/lec_03_computation.pdf），Word：有缺陷（https://files.boazbarak.org/introtcs/lec_03_computation.docx））
• 第4章： 语法糖与计算任何函数（https://introtcs.org/public/lec_03a_computing_every_function.html）（PDF：最佳排版（https://files.boazbarak.org/introtcs/lec_03a_computing_every_function.pdf），Word：有缺陷（https://files.boazbarak.org/introtcs/lec_03a_computing_every_function.docx））
• 第5章： 代码即数据，数据即代码（https://introtcs.org/public/lec_04_code_and_data.html）（PDF：最佳排版（https://files.boazbarak.org/introtcs/lec_04_code_and_data.pdf），Word：有缺陷（https://files.boazbarak.org/introtcs/lec_04_code_and_data.docx））
• 第6章： 具有无限域的函数、自动机与正则表达式（https://introtcs.org/public/lec_05_infinite.html）（PDF：最佳排版（https://files.boazbarak.org/introtcs/lec_05_infinite.pdf），Word：有缺陷（https://files.boazbarak.org/introtcs/lec_05_infinite.docx））
• 第7章： 循环与无穷（https://introtcs.org/public/lec_06_loops.html）（PDF：最佳排版（https://files.boazbarak.org/introtcs/lec_06_loops.pdf），Word：有缺陷（https://files.boazbarak.org/introtcs/lec_06_loops.docx））
• 第8章： 等价的计算模型（https://introtcs.org/public/lec_07_other_models.html）（PDF：最佳排版（https://files.boazbarak.org/introtcs/lec_07_other_models.pdf），Word：有缺陷（https://files.boazbarak.org/introtcs/lec_07_other_models.docx））
• 第9章： 普遍性与不可计算性（https://introtcs.org/public/lec_08_uncomputability.html）（PDF：最佳排版（https://files.boazbarak.org/introtcs/lec_08_uncomputability.pdf），Word：有缺陷（https://files.boazbarak.org/introtcs/lec_08_uncomputability.docx））
• 第10章： 受限计算模型（https://introtcs.org/public/lec_08a_restricted_models.html）（PDF：最佳排版（https://files.boazbarak.org/introtcs/lec_08a_restricted_models.pdf），Word：有缺陷（https://files.boazbarak.org/introtcs/lec_08a_restricted_models.docx））
• 第11章： 每个定理都可证明吗？（https://introtcs.org/public/lec_09_godel.html）（PDF：最佳排版（https://files.boazbarak.org/introtcs/lec_09_godel.pdf），Word：有缺陷（https://files.boazbarak.org/introtcs/lec_09_godel.docx））
• 第12章： 高效计算：非正式介绍（https://introtcs.org/public/lec_10_efficient_alg.html）（PDF：最佳排版（https://files.boazbarak.org/introtcs/lec_10_efficient_alg.pdf），Word：有缺陷（https://files.boazbarak.org/introtcs/lec_10_efficient_alg.docx））
• 第13章： 运行时间建模（https://introtcs.org/public/lec_11_running_time.html）（PDF：最佳排版（https://files.boazbarak.org/introtcs/lec_11_running_time.pdf），Word：有缺陷（https://files.boazbarak.org/introtcs/lec_11_running_time.docx））
• 第14章： 多项式时间归约（https://introtcs.org/public/lec_12_NP.html）（PDF：最佳排版（https://files.boazbarak.org/introtcs/lec_12_NP.pdf），Word：有缺陷（https://files.boazbarak.org/introtcs/lec_12_NP.docx））
• 第15章： NP、NP完全性与Cook-Levin定理（https://introtcs.org/public/lec_13_Cook_Levin.html）（PDF：最佳排版（https://files.boazbarak.org/introtcs/lec_13_Cook_Levin.pdf），Word：有缺陷（https://files.boazbarak.org/introtcs/lec_13_Cook_Levin.docx））
• 第16章： 如果P等于NP会怎样？（https://introtcs.org/public/lec_14_PvsNP.html）（PDF：最佳排版（https://files.boazbarak.org/introtcs/lec_14_PvsNP.pdf），Word：有缺陷（https://files.boazbarak.org/introtcs/lec_14_PvsNP.docx））
• 第17章： 空间有界计算（https://introtcs.org/public/lec_14a_space_complexity.html）（PDF：最佳排版（https://files.boazbarak.org/introtcs/lec_14a_space_complexity.pdf），Word：有缺陷（https://files.boazbarak.org/introtcs/lec_14a_space_complexity.docx））
• 第18章： 概率论101（https://introtcs.org/public/lec_15_probability.html）（PDF：最佳排版（https://files.boazbarak.org/introtcs/lec_15_probability.pdf），Word：有缺陷（https://files.boazbarak.org/introtcs/lec_15_probability.docx））
• 第19章： 概率计算（https://introtcs.org/public/lec_16_randomized_alg.html）（PDF：最佳排版（https://files.boazbarak.org/introtcs/lec_16_randomized_alg.pdf），Word：有缺陷（https://files.boazbarak.org/introtcs/lec_16_randomized_alg.docx））
• 第20章： 随机化计算建模（https://introtcs.org/public/lec_17_model_rand.html）（PDF：最佳排版（https://files.boazbarak.org/introtcs/lec_17_model_rand.pdf），Word：有缺陷（https://files.boazbarak.org/introtcs/lec_17_model_rand.docx））
• 第21章： 密码学（https://introtcs.org/public/lec_19_cryptography.html）（PDF：最佳排版（https://files.boazbarak.org/introtcs/lec_19_cryptography.pdf），Word：有缺陷（https://files.boazbarak.org/introtcs/lec_19_cryptography.docx））
• 第22章： 证明与算法（https://introtcs.org/public/lec_24_proofs.html）（PDF：最佳排版（https://files.boazbarak.org/introtcs/lec_24_proofs.pdf），Word：有缺陷（https://files.boazbarak.org/introtcs/lec_24_proofs.docx））
• 第23章： 量子计算（https://introtcs.org/public/lec_26_quantum_computing.html）（PDF：最佳排版（https://files.boazbarak.org/introtcs/lec_26_quantum_computing.pdf），Word：有缺陷（https://files.boazbarak.org/introtcs/lec_26_quantum_computing.docx））

编译于2023年12月6日 00:07:51

版权所有 2023, Boaz Barak。Creative Commons License (https://creativecommons.org/licenses/by-nc-nd/4.0/) 本作品采用Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License (https://creativecommons.org/licenses/by-nc-nd/4.0/)进行许可。

使用pandoc (https://pandoc.org/)和panflute (http://scorreia.com/software/panflute/)生成，模板衍生自gitbook (https://www.gitbook.com/)和bookdown (https://bookdown.org/)。