计算理论

课程内容： - 自动机理论：正则语言与有限状态机，上下文无关语言与下推自动机 - 可计算理论：图灵机，可识别性与不可识别性，可判定性与不可判定性，归约 - 复杂性理论：时间复杂度（P与NP），空间复杂度（PSPACE与NPSPACE，L与NL） - 不考的内容：不可解决性，P=NP研究过程中部分方法的局限性，逻辑电路复杂性 上课自由度： - 爆高，点名考勤一概没有，人不到场完全没毛病 - 而且这门课没有小测、实验、大作业这种磨人的小妖精（毕竟内容也确实难为设计者），一整个学期的节奏就是1周1次作业，平稳得像心电图直线，~不会出现什么bug调不出来开始怀疑人生这种事~本专业五选三绝对可以带上这门课 考核标准： - 50%平时成绩，大概是作业成绩等比转化，但作业必须按时交，补交通道直接焊死 - 作业就是教材习题，可以在Github上搜书名挖到答案，但我挖到的那份写得跟天书似的 - 50%期末成绩，期末考试是5大题×20 - 计算理论这玩意儿本身就抽象得像哲学，平时还得老老实实跟车，不然考试动不了笔，作业也写不出来 - 龙老师这学期出的期末卷子属于是彻底脱离地心引力了，不过如果平时跟着学+作业认真写（这学期助教批改作业反馈非常负责，在这门课除了内容有点抽象外其他都好的基础上，属于是锦上添花了）+及时看反馈，复习也不用压力山大，只要尽可能把学的东西全摆出来，环神会的，会捞的 授课质量： - 高，虽然照旧难啃，但多半是课程内核本身就硬，老师已经把那点唾沫星子榨干了 - 如果上过CS2304计算机科学中的数学基础的话，应该已经领悟了，此处省略一万字

课程内容： Automata: FA, PDA——对，先跟有限自动机和下推自动机拜个早年 Computability: Decidability, Reducibility——可判定性、可归约性，听着像在给你的人生做判定 Complexity: Time, NPC, Space, LogNLog——时间、NPC、空间，还有那个 LogNLog，读出来像嘴里含了颗糖 教材是 Sipser 的那本——Sipser 那本，江湖人称“上课带它等于带了个翻译” 上课自由度：高——高到你在课堂上飘着走都没人管 考核标准：50 + 50 期末考了好多 NLC（——期末一翻开卷子，满眼都是 NLC，人当场变成自动机，状态疯狂跳转 授课质量： 高，能把一个辅修的教懂大部分👍虽然最后的 PSACE 和 Log 那里有点吃力（——高，真的高，高到一个辅修的都能听懂大半，直接给龙老师磕一个👍就是最后那个 PSACE 跟 Log 一出来，脑子里的栈瞬间溢出，多少有点吃力（

课程内容：FDA、PDA、TM、P、NP、NPSPACE这些玩意儿；期末速通的时候居然还觉得挺有意思的。 上课自由度：神中神，无签到 考核标准：50+50 平时作业和期末，平时作业一定一定得按时交 授课质量：其实我没怎么听，靠slides+gemini复习的；学期刚开始还试着听了一小阵，有点啃不动，跟不上； 考试五道题只会完整做两道，其余全指望我龙神捞啊，太仁义了😭😭😭

课程内容：计算理论，大致撕成FA、CFL、TM（含可判定问题和规约问题）以及计算复杂度理论（时间空间）。 上课自由度：高，可以不来，不签到，平时分基本给满。 考核标准：这学期题目没以前那么白给，调成了50+50，听说一般是40+60。 授课质量：高。认真听课+认真做作业=考试必满绩。

速通失败了，但老师是仁慈的活菩萨，平时期末从四六改成五五开。 讲课质量虽然没之前数学基础那么丝滑，但起码讲得明白，中间卡壳后面也会补讲清楚。 每节课前还会回顾上节内容，比较nice。