计算复杂性 · 修读回执档案

课程内容：讲到教材的第四章，较难，第四就像把前面几章叠起来再乘个系数。 上课自由度：高，课程后半段时间开了签到，属于是飞多了终于有个降落伞警告。 考核标准：作业是教材上面的习题，做对5道题目可以得到满分，一共四次作业，颇有买五送零的感觉。考核难度还好，是单独安排的时间，前一天告知了60%的内容，这是考试预告片提前泄露大纲级别的好心。 授课质量：高，没得黑。

课程内容： 本节学期点评里已经另有一位同学开过铺了，此处我就闭麦不重复播报。 上课自由度： 挺高，教室会原地生出来一个课前签到自动挂机，官方最后应该没把它塞进总评里，但这课内容是硬骨头，脑袋最好还是按时人到场。 考核标准： 考试作业各掰一半各占50%：（1）作业内容为那本《计算复杂性理论》前四章的作业题；（2）考前就给你放期中判决书一样的货——公布期末考试60分的题目。 授课质量： 高，傅老师在课上提着头般地引导同学自己想，反过来拿学生反馈给自己的教案打补丁。

课程内容： 图灵机来打个照面，时间复杂性、空间复杂性（Savitch定理这种选手）轮番上阵，难解性这块Cook-Levin是重头戏中的重头戏，几种不同归约方式排着队来，Oracle TM和相对化壁垒也来凑热闹，电路复杂性直接把Hastad Switching Lemma强行讲完，随机计算复杂性类（RP、coRP、PP）登场，计数复杂性收尾于Valiant-Vazirani定理。一学期走完这套流程，脑子相当于被TCS思维按在地上摩擦了一遍。 上课自由度： 高，今年有签到，但真想把这门课嚼明白，最好还是少开小差——签到能救出勤，救不了你听不懂时的灵魂出窍。 考核标准： 作业50%，考试50%。 四次作业是傅老师书上前四章的习题，每次做对五道当次作业就是满分。 考试是非正式的，不进考期。今年改为考前一天公布卷子中60分的题目，公布的部分不难——相当于开卷送温暖，但那60分之外的荒野还请自求多福。 授课质量： 高。作为纯理论的课程，讲的内容是计算复杂性中的基础，但需要能适应TCS的思维方式，如果不适应的话可能会比较痛苦——适应的叫醍醐灌顶，不适应的叫当场超度。

课程内容：基本计算理论上的定理（停机问题）、基本的时间复杂性上的定理（线性加速、确定/非确定时间谱系，Cook-Levin规约）、对角化技术（确定/非确定时间谱系定理、Ladner、GBS）、基本的空间复杂性、更多的时间复杂性——多项式谱系（几种等价的描述方式）、布尔电路（一致、非一致；并行计算NC，AC类）、随机计算、计数复杂性，看着像报菜名，实则是数学版的复仇者联盟集结。 上课自由度：非常高，不点到签名，本人喜欢线上上课，线下只去过2节课，其他时间跟教室属于网友关系。 考核标准： 3次作业50% + 考试50% 这次用的讲义后面的作业，作业找不到答案，但是不是很难，理解课上的讲的各种技术的话就还好，属于略磨人但不致命。 这次考的Cook-Levin规约的诸多性质和在证明中的应用，考得挺容易的，容易到让你怀疑自己是不是被优待了。 授课质量：挺高的，但是如果你没学过理论计算机（TCS）相关的话，最开始有点痛苦（老师证明讲得挺快的，有很多细节需要自己思考补全），不过后面就好了，基本的套路方法思想还是很清晰的，喜欢理论课的同学听起来应该会很舒服，就像听一场逻辑的交响乐，刚开始跟丢，后来能跟拍。 强烈建议每个对TCS感兴趣的本科生选择这个作为第一门课，没有任何前置知识，但是需要适应这个思考方式，可以学到很多，很多到你可能需要建个文件夹存笔记的那种。

课程内容：计算复杂性 现代方法，光听名字比看烧脑片还下头。 · 考核章节：1~4+6，落单的那个6像从考纲里拐来的孩子。 · 不考核章节：5，7，17，这三章在课上学完后大概率是你的收藏品。 上课自由度：自由，不签到——自由的尽头是不管你，也是一种温柔。 考核标准：作业若干15%+5道闭卷测试题75%。作业量不多，但难度非常大，而且找不到答案——作业像无人区的路标，抬头全是荒芜；不过作业应该不太影响给分，这种存在感约等空气的配比还挺玄幻。课程本身非常难，但是考核相对容易——典型的前途尽头是考场温柔模式，一个唱黑脸一个唱白脸。5道测试题第一天就告诉你题目，是后面上课会讲的证明，你只需要理解并背诵即可——考试题干里自带答案胚胎，你喂它一口就能听到全绩点的老铁刷个火箭。不过这些题本身都是能撑起一篇学术论文的级别，别妄想自己凭空做出来，凭一条小学奥数水平的手臂挑战抽象代数的墙除非你有水泥血统。个人比较推荐，拉高GPA不错的课。不过有个预警：老师写了一本导读，据说之后的课要做导读上的作业，量和难度都比较大——注意这里是据说，是对未来不明的预言镜头。因此本评价仅供参考，我只能把听说放到这，动手摸底得靠你自己。 授课质量：讲得不错，也有Q&A。理论计算机领域，领略各种精妙的构造和思想，个人觉得非常有趣。偏数学——偏数学这条小字，懂的人懂，不懂的人下课已经擦好眼泪站在打印店偏数学这个怪坑面前。