课程介绍
参考书：
J. E. Hopcroft, R. Motivani, and J. D. Ullman. Introduction to Automata Theory, Languages, and Computation (3rd Edition), 2006.
自动机理论、语言和计算导论（第3版），机械工业出版社，2007.
参考课程视频：
考核方式
- 平时成绩：50%
- 平时作业：40%
- 研讨交流：20%
- 期中考试：40%，闭卷
- 期末考试：50% 闭卷
学习建议
- 课前预习（自主学习单）
- 阅读书的章节
- 预习课件（可选）
- 观看视频（可选）
- 课上研讨：出勤很重要！
- 课后练习
- 独立自主完成作业
- 可先和同学、助教或大语言模型讨论之后再独立完成作业；给出和大语言模型讨论的全过程。
介绍计算理论
他是在算法一层往上的抽象
研究内容：计算机的基本能力和局限性是什么
- 什么是计算机 即计算模型
- 什么可以/不可以被计算 即可计算性 halting problem就无法被计算
- 一个问题能够被多快的计算出来 即复杂性 许多问题很可能没有高效的算法 NP问题
计算模型（什么是计算机）
- 图灵机 真实的计算机
- finite state automata
- push-down
数学符号
- 集合
subset子集union并集intersection交集complement补集power set所有子集的集合 幂集
- sequences and tuples
sequence元素的有序列表 序列tuple长度固定的有序列表- 笛卡尔积
- 函数和k元函数
- 关系 关系就是集合
- 等价关系（equivalence relation）自反对称传递
- 闭包 $R^+$表示传递闭包 $R^*$表示自反传递闭包
- 图$G = (V, E)$其中$V$是点集，$E$是边集
- 连通图（connected graph）
- 树 （tree）
- 有向图（directed graph）
- string
- symbol 符号
- 长度 $|010101|=6$
- 空字符串 $|\epsilon|=0$
- substring 100 is a substring of 011001
- connection
- lexicographic order: dictionary order
- string order: 先比长短，然后再按照lexicographic order
- lanaguage
- alphabet 有限字符集合（字母表）
- lanaguage 来自alphabet的字符组成的string组成的集合
- proofs
- 构造证明 construction
- 反证法 contradiction
- 归纳法 induction
- if and only if proof 证明两边
