形式语言与自动机 - 卜磊,李宣东¶
基本信息¶
- 课程号:
22011120 - 任课教师: 卜磊,李宣东
- 上课专业: 信计,匡计,计拔,计科
评价 1¶
评价者信息¶
Tag：保研；Rank 5%；2024 Fall修课
Score：93
关于老师¶
由软件学院的卜磊老师授课，上课很有精神，时常会使用一些生动有趣的例子解释比较抽象的理论概念，思维跳跃但逻辑严谨。
前置知识¶
集合论
课程内容¶
参见民间课程网站：形式语言与自动机 - cuijiacai
课程包含了有关形式语言和自动机的基础内容，和计算方法类似，是一门偏向于概念介绍的“讲座课”；主要包含了：
- 有穷自动机
- 上下文无关语言
- 下推自动机
- 图灵机
- 判定性与复杂度
- （略讲）迁移系统、Petri 网、时间自动机
算是 NJU CS 里偏简单的一门理论课。
作业、考试与得分¶
作业偏向于理论，有一定难度，可能需要一定的灵感乍现才能做出来（有一些题也根本不是一般人能想出来的，可以适当搜索）。
考试题量非常之大，但难度平平，所以题目都有在现场做出来的可能。最终得分差距主要体现在期末考试。
实验是使用 C++14 模拟一个 PDA 和一个 TM，需要支持读取一个给定格式的 PDA 或 TM 文件，并按文件所描述的自动机在给定的输入上运行。主要难度在于读取文件并正确解析，真正模拟的部分很快就能写完。
工作量¶
作业：共有 6 次作业，平均每次耗时 4 小时。
实验：若设计得当，总体码量约为 1k 行，耗时 10 小时左右。
考试：有民间网站的帮助，复习起来非常方便；完整过一遍需要约 3 小时。
学习指南¶
民间网站：形式语言与自动机 - cuijiacai
课程网站：（每年用完即删）FLA - 25
笔者认为，这门课里最有用的部分还是概念：诚然，很多地方都会用到自动机的概念（TCP 自动机、文法分析等），但并不需要我们使用很复杂的建模技巧和规约证明。因此笔者认为，在这门课上搞懂每一个自动机的概念、每一种自动机的能力边界即可，不需要过于深究那些规约技巧。
评价 2¶
评价者信息¶
Tag：保研；Rank 10%；2024 Fall修课
Score：97
课程内容¶
课程内容只要看崔家才学长的笔记就好了（崔学长大爹！）。主要涵盖了计算理论的基础知识。我是上完了姚鹏晖老师的计算复杂性课再上这门课的，受益匪浅。课程质量很高，推荐所有有志于计算机理论/程序设计语言/编译系统等方向的同学选修。
但我不同意评价 1 的观点，这门课的内容绝对不算简单，尤其是对数学不好的同学。
作业、考试与得分¶
作业题很多非常 ad hoc，打过程序设计竞赛的同学可能会很喜欢。但对大部分同学来说，作业的难度应该非常大。建议多在 stack exchange 上搜索，多思考，多抱大腿。这门课的作业需要的时间很多。
考试则是没有那么 ad hoc 的，但需要你具备一定的熟练度。
实验很简单。
如何贡献¶
请查看评价指南了解如何评价课程！