1正则的能力边界
为什么数不了？
计算机基础 · 小纸条
选一章打印。双面打印（按长边翻页）后沿虚线剪开，每张卡片正面题目、背面答案。
第 1 页 · 正面（题目）
2泵引理
它是什么类型的证明工具？
3为什么正则匹配不了括号
那用什么才行？
4上下文无关文法
写出描述配对括号的文法。
5下推自动机
它和上下文无关文法什么关系？
6文法的二义性
算式文法怎么消除二义性？
7乔姆斯基层级
这四层各对应什么机器？
8图灵机
为什么这么简单的模型这么强？
9丘奇－图灵论题
为什么它不能被证明？
10通用图灵机
这对应现实中的什么？
第 1 页 · 背面（答案）
参考答案（家长）：反证法，先假设正则再推出矛盾。
参考答案（家长）：状态有限，记不住任意大的计数。
参考答案（家长）：S 可以是空、可以是左括号 S 右括号、可以是 SS。
参考答案（家长）：下推自动机，也就是带栈的自动机。
参考答案（家长）：分层写规则，让优先级和结合性体现在文法结构里。
参考答案（家长）：等价，能识别的语言完全一样。
参考答案（家长）：无限的纸带提供了无限的存储和状态组合。
参考答案（家长）：有限自动机、下推自动机、线性有界自动机、图灵机。
参考答案（家长）：CPU 读取并执行程序，程序就是被模拟的机器。
参考答案（家长）："直觉上能计算"本身不是精确的数学概念。
第 2 页 · 正面（题目）
11停机问题
这个证明用了什么方法？
12停机问题的证明
矛盾说明了什么？
13不可判定的影响
那杀毒软件怎么工作的？
14莱斯定理
这意味着什么？
15可计算与可行
这对应哪两门学问？
16计算理论小结
用一句话概括这门课的结论。
17信息论：信息是什么
"明天太阳升起"信息量大吗？
18信息的度量
概率二分之一的事件信息量是多少？
19熵
均匀分布和极不均匀分布，哪个熵大？
20熵与压缩
这说明什么？
第 2 页 · 背面（答案）
参考答案（家长）：假设错了，H 不可能存在。
参考答案（家长）：对角线法，构造一个自我矛盾的程序。
参考答案（家长）：静态分析工具永远只能给近似答案。
参考答案（家长）：用特征匹配和行为启发，做不到完美但足够实用。
参考答案（家长）：计算很强大，但有明确且已被证明的极限。
参考答案（家长）：可计算性理论和计算复杂性理论。
参考答案（家长）：1 比特。
参考答案（家长）：极小，因为几乎确定。
参考答案（家长）：压缩不是无限的，有数学上的硬极限。
参考答案（家长）：均匀分布熵最大，最难猜。
第 3 页 · 正面（题目）
21哈夫曼编码
为什么要求前缀码？
22哈夫曼的最优性
贪心策略是什么？
23有损压缩
什么数据绝不能有损压缩？
24信道容量
超过上限会怎样？
25纠错码
最简单的纠错思路是什么？
26校验和与哈希校验
它能纠错吗？
27海明码
纠一位错需要多少校验位？
28冗余的代价
什么场景值得高冗余？
29信息论小结
用熵解释"为什么随机数据压不动"。
30密码学要解决什么
这四样各举一个生活例子。
第 3 页 · 背面（答案）
参考答案（家长）：每次合并当前频率最小的两个。
参考答案（家长）：保证解码没有歧义，不需要分隔符。
参考答案（家长）：错误率无法通过任何编码降到可接受范围。
参考答案（家长）：程序、文本、财务数据，改一个字节就错。
参考答案（家长）：不能，只能发现，纠错需要更多冗余。
参考答案（家长）：重复发三遍，取多数。
参考答案（家长）：深空通信、存储介质，重传代价极高或不可能。
参考答案（家长）：k 个校验位能定位 2 的 k 次方减 1 个位置。
参考答案（家长）：如密码、封条、身份证、签名。
参考答案（家长）：随机数据熵最大，没有可利用的规律。