3.24

周一

Introduction to the theory of computation theory 收尾

周末一天休息，半天摆烂，半天补作业，算是什么都没干。今天直接跳习题，看了 Chapter 8,9，然后开始读最后一章 Chapter 10: Advanced Topics in Complexity Theory

这章的六节分别是 近似算法、概率算法、交替图灵机、交互证明、并行计算、密码学，这么多内容塞在一章，不可避免地有些浅显。目前看了近似算法，书上只提到了两个算法就草草结束；SJTU CS1212 的讲义不仅讲了四个算法，还都有更细致的分析，此外还提到了不可近似性，PCP 定理。

明天七点要升旗，今天得早睡一回。明天先往下读 Chapter 10，然后看看 PCP 定理的证明能不能 handle