1正则的能力边界
为什么数不了？
计算机基础 · 小纸条
选一章打印。双面打印（按长边翻页）后沿虚线剪开，每张卡片正面题目、背面答案。
第 1 页 · 正面（题目）
2泵引理
它是什么类型的证明工具？
3为什么正则匹配不了括号
那用什么才行？
4上下文无关文法
写出描述配对括号的文法。
5下推自动机
它和上下文无关文法什么关系？
6文法的二义性
算式文法怎么消除二义性？
7乔姆斯基层级
这四层各对应什么机器？
8图灵机
为什么这么简单的模型这么强？
9丘奇－图灵论题
为什么它不能被证明？
10通用图灵机
这对应现实中的什么？
第 2 页 · 正面（题目）
11停机问题
这个证明用了什么方法？
12停机问题的证明
矛盾说明了什么？
13不可判定的影响
那杀毒软件怎么工作的？
14莱斯定理
这意味着什么？
15可计算与可行
这对应哪两门学问？
16计算理论小结
用一句话概括这门课的结论。
17信息论：信息是什么
"明天太阳升起"信息量大吗？
18信息的度量
概率二分之一的事件信息量是多少？
19熵
均匀分布和极不均匀分布，哪个熵大？
20熵与压缩
这说明什么？
第 3 页 · 正面（题目）
21哈夫曼编码
为什么要求前缀码？
22哈夫曼的最优性
贪心策略是什么？
23有损压缩
什么数据绝不能有损压缩？
24信道容量
超过上限会怎样？
25纠错码
最简单的纠错思路是什么？
26校验和与哈希校验
它能纠错吗？
27海明码
纠一位错需要多少校验位？
28冗余的代价
什么场景值得高冗余？
29信息论小结
用熵解释"为什么随机数据压不动"。
30密码学要解决什么
这四样各举一个生活例子。