计算理论 · 修读回执档案

课程内容： - 自动机理论：正则语言与有限状态机，上下文无关语言与下推自动机 - 可计算理论：图灵机，可识别性与不可识别性，可判定性与不可判定性，归约 - 复杂性理论：时间复杂度（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。

## 期末直接改成50%的占比了，还在犹豫什么！这简直是期末占比界的跳楼大甩卖！ 讲课好，作业少，给分高，大学完美的课莫过于此吧，属于是选课系统的亲儿子。

课程内容：略 上课自由度：完全不来上课也没关系 考核标准：今年好像是为了捞人，把比例从作业40考试60调成了作业50考试50。作业不接受补交，但只要交了就分数很高，本人作业分是99.52/100 授课质量：高 虽然在讲一些比较绕的东西的时候会犯迷糊，但整体逻辑很清晰，讲得也算清楚，slides的信息量非常适中，复习知识点翻ppt很舒服 今年考试题目出得有点怪，一些比较重点的东西完全没考，考了一些怪不拉几的东西，不过考试巨捞，渔网抡冒烟的那种，只要把卷子填满，老师就会帮你想办法

不会的全跳，跳着跳着竟然跳完了试卷，回头一看卷面白得像太平间，问题只会留下一个个reject。 什么语言可判定不可判定我不知道，我只知道我会的题是decidable的，而且能在常数时间内判定，因为它是空集，来一题reject一题🥹 更新：最后期末很捞，占比也下调到50%，作业认真做平时分接近给满。龙环我女神！

血泪实践证明，靠考前一两天极限速通纯属做梦，各位平时记得老老实实学！期末考试我觉得难度很高，就看老师发不发力了，大佬请随意。

这是一档本学期的期末地狱难度真人投票节目，脚趾头觉得难的点个赞，觉得不过尔尔的点个踩，点赞即受苦，点踩即渡劫。 --------------------------------------------------------------------------------------- 更新：成绩出来了，悬念揭晓。

课程内容：全是硬货，纯的 - 正则语言（RL）与有穷自动机（DFA/NFA） - 上下文无关语言（CFL）与下推自动机（PDA） - DPDA（不考） - 图灵机（recognizable/decidable） - 图灵机可判定性 - GoedelNumber（不考） - 图灵机规约 - 时间复杂度，NP/P - NPC问题 - 空间复杂度，NPSPACE/PSPACE - 对数空间复杂度，L/NL - Intractability（不考） 上课自由度：自由度拉满，来不来全看你良心，点名？不存在的，这课上到现在可能都不知道有考勤这功能 考核标准：作业（40%）+期末考试（60%） - 作业：有点东西的，个别题能让你从晚饭坐到宵夜，不会就上网扒答案偷师，反正考试没这么狠 - 期末考试： - 难度：今年卷子挺接地气的，主打一个课内知识你吃没吃透，那种逼你在草稿纸上原地飞升的证明题没几道 - 分数：龙老师的捞人水平不需要我多说了，字写满，把自己会的东西摆出来，哪怕只证出一半也能捞你不少分（纯写证明思路也能给你塞不少分，属于是下水捞人带救生圈的那种） 授课质量： - 讲得还行，就是速度比较佛系，一个知识点能给你来回解释，认真听基本不存在掉队的可能（但每周五下午连坐三个小时，确实是精神与臀部的双重修行）

课程内容： 不多赘述，下文自带解说～ 上课自由度： 高到下辈子，不签到，课可以不去当背景板，但作业每次死线君亲自蹲守，想补交？门都没有。 考核标准： 作业40％ 期末60％ 作业每周甩几道题，Github上能捞到答案，但别跟饿狼似的一键扒光，最好自己硬啃证明一下，不然等着期末复习怀疑人生。 期末考试是5道证明题，每题20分，每题还带两小问。基本围绕对应章节的重点证明及其变型跳舞，书上重要定理会证＋作业全整明白就基本安全 （可是本人做不到完全整明白哈哈哈，因为作业没怎么讲，网上答案又抽象得像加密通话） 但老师很有耐心，不懂直接课间把人逮住问，服务到位。 这考试还考了一道作业原题的Rice定理（默写＋证明），拿到卷子那一下直接懵成雕塑… 分还没出，但听老师语气应该会调一下分（也可能是我在幻觉hh） 补充：作业没交的同学当次直接0分大礼包（本人少交了一次，平时分少了10％左右🥹）全交了的话平时成绩基本管饱。 授课质量： 龙老师语速属于开了倍速，说是中文班，但ppt和教材是英文的，考试题目中英双语双拼。听跟不上就自己去搜北京大学刘田老师的课看，讲得比较清晰，属于官方外挂。 对了，学过编译原理的同学自带buff，能捞点优势 总体还行吧，一学期下来任务量还算下得去嘴

调查下本次难度，感觉难的可以给我点赞，不难的点踩。谢谢大家！点赞和点踩你们随意，反正我的手指已经悬在屏幕上了。

老师上课是真的认真，人也随和，可惜我一看理论就犯困，全程没听过课。 对理论不来电或者没有计算理论底子的慎选，本人平时是坚决一点时间都不肯多花，到期末复习那叫一个吃不消，什么可判定性根本证不出来。这学期考的也没有lh嘴上说的那么简单，以前据说考过画复杂度韦恩图这类送分题，但这次连最简单的都得背下课上那串证明步骤，考卷从头到尾全是证明大题。唉，这门课就此跻身鼠鼠有史以来分数最低的几门课之一，令人感叹。当然如果你是真爱理论的人，龙老师非常棒。

课程内容：计算理论，名字就直接叫这。 上课自由度：高，迟到早退隐身拿捏之。 考核标准：平时+期末，平时比重能让你一整个人升天。 授课质量：较高。课上着感觉还可以，这门课本身也有点意思，考试难度适中，但平时分扣得有点多，扣了5分+，不理解到挠墙，综合下来一颗星星就没了。

课程内容：正则语言、上下文无关语言、图灵机、可判定性、可归约性、时间复杂度、空间复杂度（《计算理论导引》的第0、1、2、3、4、5、7、8章） 上课自由度：高，不点名，作业全程线上交 考核标准：平时30%，期末70%，平时作业是全交了但要命的是每份都有扣分，平均分大概4.6左右，最终平时分就按你扣了多少来直接结算（即平时分扣2分左右） 讲课质量：很高，老师顺着书讲也顺着自己脑子里的逻辑讲，非常自洽。老师人非常好。 一学期一共12次小作业，光前九周就周周有作业，还比较难。每次3到5个题目不等，头铁不看答案的话一次作业耗时2~5小时（这也看各人手速，不过身边大多数人都是这个情况）。期末好好复习吧，但题目很难，不一定有好分数。Dominik Scheder今年跑路了，想选计算理论你也没别的老师了。 目前就出来这一门,核心学积分排名34/105. 今年姐妹花给分都比较一般, 对分数有需求的同学慎选

课程内容：就是上一条评论说的那些，顺便个别章节会参考《计算理论导引》这本书 上课自由度：高，本来选课的人也少，老师也不会点名，教室里常常空旷得能跳广场舞 考核标准：50%作业（小组形式）+50%期末考试（5道大题，可以看电子版资料，但不能上网搜索，我这学期的试卷应该可以在传承交大找到） 讲课质量：全白板英文连击英语播报，讲得还是不错的，但基本上全黑板板书，只有个别章节有slides，相当于给你发了一张地图手册之后就全靠腿走。中间听不懂也可以随时提问，老师会耐心地讲解，大家也会一起互动（教室里一般也就个位数的人，开会规模都比这大） 老师很不错，但我太菜了。因为老师讲课是全英文（毕竟是外籍教授），再碰上纯板书，我经常一个走神就整节课挂机......确实可以提问，但我的口语水平也很难描述出我的问题（不过还是提问了几次）。作业是小组形式，每周做几道题目，感觉很多时候靠组内大佬扛着我过河，有时候甚至看不懂他们写的解答。 总之这门课对大佬来说绝对算精品课程——高水平教授、自由的课堂讨论、高质量的讲授和作业。但如果你英文水平不太行（主要指口语），或者觉得自己比较菜，我建议还是慎重考虑吧.另一位老师也挺好的，水平也很高，讲的也很好，我数学基础课就选的她的课，计算理论就想换个新店试试手。现在回过劲儿来，早知道当初就选她的计算理论了（悲） 班上还有个大佬中期把这门课退掉了，虽然我不知道具体原因，但或许也算给这课的难度盖了一颗手印吧😭 顺便，如果选了这门课的话，awesome-cs上有同学写的课堂笔记，可以去翻一翻。

课程内容：boolean circuits, regular languages, general grammars, primitive recursive functions, Turing machines，一串英文名词砸脸上，像自动售货机把整排饮料全掉下来那种，爱喝不喝，反正这课就这个配方。 上课自由度：人少，老师上课会像雷达一样扫你有没有听懂，没听懂当场打断提问都不带举手蓄力的。打疫苗这种破事直接请假，说一声就行，听说还有几个一直挂网课修仙的。 考核标准：50%作业（小组作业，但本质是做题目，编程较少，逻辑站C位），50%考试。 讲课质量：很好！外教全英文，但认真听是能跟上的，像听英文播客不需要字幕那种。提问、要课件，直接跟老师开口就能解决。上课主打板书，到primitive recursive functions 和Turing machines时才稍微加了点代码，像清汤突然撒了把胡椒。 老师是第一次上这个课，我是交叉选进来的但本身逻辑还凑合，所以听下来不算困难，作业、考试也都还行。极其推荐想体验外教课堂方式的同学，另外老师真的认真负责，是抱着教书的心态来的（懂的都懂，和那种棒读PPT的课一比简直像换了个物种），他很注重和你们的交流，这点我很喜欢。计算机的同学我不知道中文班教得怎么样，反正这个还挺不错，英文也不算难，一堂课可能有一两个实在不懂的地方，也来得及查一下，或者直接提问都行。 交叉的话建议看看有没有认识的同学能组队，不过我上下来班级同学都还挺好的。但这作业量，想划水是不大行的，水面上看着平静，底下全是暗流。

课程内容：正则语言、上下文无关语言、图灵机、可判定性、可归约性、时间复杂度、空间复杂度 （《计算理论导引》的第0、1、2、3、4、5、7、8章） 上课自由度：高，不点名，就是每次记得线下来交作业，别人不到作业也不到。 考核标准：很详细，平时30%，期末70%，平时只要所有作业都交了而且不错得太离谱，都是100分。 讲课质量：很高，老师顺着书讲，但里头又缝着自己的逻辑。老师人非常好，强烈推荐，选龙龙绝对没错~ 这课事少，期末好好复习就能抱个漂亮分数回家，属实是计算机系课程里的一股清流。