CMSC 515 -计算理论

2021年秋季学期

讲座
  1. 介绍
  2. 不确定有限自动机
  3. 常规的语言
  4. 正则语言的抽运引理
  5. 上下文无关语法
  6. 下推自动机
  7. pda和CFGs的等效性
  8. 节能灯的抽运引理
  9. 图灵机简介
  10. 模拟其他机器
  11. 用图灵机解决难题
  12. 使用还原来证明不可判定性
  13. 其他削减的例子
  14. 自省和递归定理
  15. 数理逻辑中的不可判定问题
  16. NP完全语言
  17. 关于第七章的最后一句话
  18. 自底向上解析算法
  19. 自顶向下解析算法
作业
  1. 问题1.6aj, 1.16b, 1.18j, 1.46a, 1.49, 9月24日星期五交
  2. 习题2.4ce, 2.5ce, 2.44, 2.47: 10月1日星期五交
  3. 习题2.31、2.48、3.8b: 10月8日星期五交
  4. 问题3.13、3.14、3.15b、3.19、4.3、4.11,10月18日星期一交
  5. 习题5.9,5.14,5.23:10月27日星期三交
  6. 习题6.6,6.13,11月5日星期五交
  7. 习题7.9 7.12 7.26 7.27 7.31 11月17日周三交
考试

第一次期中考试将在10月13日星期三举行。以下是进一步的细节。

第二次期中考试将在11月3日星期三举行。以下是进一步的细节。

期末考试将于11月23日星期二举行。以下是进一步的细节。

这是期末考试。

资源

教学大纲

这门课的教学大纲在这里。

DirectMath

我强烈建议你使用DirectMath软件来写这门课的习题集。DirectMath可以在www.directmath.com上免费下载。