【计算理论】【《计算理论导引（原书第3版）》笔记】第〇章：绪论

第〇章：绪论

0.1|自动机、可计算性与复杂性

计算复杂性理论

• 某些问题很难计算，某些问题容易计算

可计算性理论

• 一些基本问题是不能用计算机解决的，例如确定一个数学命题是真或是假

自动机理论

• 自动机理论阐述了计算的数学模型的定义和性质

0.2|数学概念和术语

集合

• 如果集合要考虑元素出现的次数，则称作多重集合

关系

等价关系

• 一种特殊类型的二元关系，满足$3$个条件
  • $R$是自反的，即对每一个$x$，$xRx$
  • $R$是对称的，即对每一个$x$和$y$，$xRy$则$yRx$
  • $R$是传递的，即对每一个$x$，$y$和$z$，$xRy$，$yRz$则$xRz$

图

简单路径

• 没有顶点重复的路径

连通图

• 每一对顶点之间都有一条路径的图

圈

• 一条起点和终点相同的路径

强连通图

• 每一个顶点到另一个顶点都有一条有向路径的图

字符串和语言

字母表上的字符串

• 字母表中符号的有穷序列

空串

• 记为$\epsilon$

$w$的反转（倒序）

• 按照相反的顺序写$w$所得到的字符串，记作$w^R$

$x$和$y$的连接

• 把$y$附加在$x$后面得到的字符串

字符串顺序

• 在字典序基础上将短的字符串排在长的字符串前面

语言

• 字符串的集合

• 无前缀语言：如果语言中任何一个成员都不是其他成员的真前缀，那么该语言是无前缀的

0.3|定义、定理和证明

定理

• 定理：被证明为真的数学命题

证明

$P$仅当$Q$

• 若$P$为真，则$Q$为真

$P$当$Q$

• 若$Q$为真，则$P$为真

0.4|证明的类型

构造性证明

示例

定理

• 如果图中每一个顶点的度数都为$k$，则称这个图是$k$正则的
• 对于每一个大于$2$的偶数$n$，存在一个有$n$个顶点的$3$正则图

证明

• 设$n$是大于$2$的偶数，现构造有$n$个顶点的图$G=(V,E)$，$G$的顶点集为 V = {   0 , 1 , ⋯   , n − 1   } V = \set{0 , 1 , \cdots , n - 1} V={0,1,⋯,n−1}，边集为 E = {   {   i , i + 1   } ∣ 0 ≤ i ≤ n − 2   } ∪ {   {   n − 1 , 0   }   } ∪ {   {   i , i + n / 2   } ∣ 0 ≤ i ≤ n / 2 − 1   } E = \set{\set{i , i + 1} \mid 0 \leq i \leq n - 2} \cup \set{\set{n - 1 , 0}} \cup \set{\set{i , i + n / 2} \mid 0 \leq i \leq n / 2 - 1} E={{i,i+1}∣0≤i≤n−2}∪{{n−1,0}}∪{{i,i+n/2}∣0≤i≤n/2−1}

反证法

• 假设定理为假，证明这个假设会导致一个明显的错误结论，故而相矛盾

示例

定理

• $\sqrt{2}$是无理数

证明

• 假设$\sqrt{2}$是有理数，$\sqrt{2}=\frac{m}{n}$，$m$和$n$都是整数且互质

• $n\sqrt{2}=m$

• $2n^2=m^2$，由于$m^2$是整数$n^2$的$2$倍，故$m^2$是偶数，所以$m$是偶数，对于某个整数$k$，$m=2k$

• $2n^2=(2k{)}^2=4k^2$

• $n^2=2k^2$，故$n^2$是偶数，所以$n$是偶数，于是$m$和$n$都是偶数，与$m$和$n$互质矛盾

• 所以$\sqrt{2}$是无理数

归纳法

示例

定理

• 设$P$为贷款原始数额，$I>0$为贷款的年利率，$I=0.06$表示年利率为$6\%$，$Y$为月付款数，$M=1+I/12$为月倍增系数，$P_t$为在$t$个月后未偿还清的贷款余额，对于每一个$t\ge 0$，$P_t=P{M}^t-Y\left(\frac{M^t-1}{M-1}\right)$

证明

• 归纳基础
  • 当$t=0$时，$P_0=P{M}^0-Y\left(\frac{M^0-1}{M-1}\right)=P$，成立
• 归纳步骤
  • 对于每一个$k\ge 0$，假设当$t=k$时公式成立，$P_k=P{M}^k-Y\left(\frac{M^k-1}{M-1}\right)$
  • $\begin{array}{rl}{P}_{k+1}=P_{k}M-Y=\left[P{M}^k-Y\left(\frac{M^k-1}{M-1}\right)\right]M-Y& =P{M}^{k+1}-Y\left(\frac{M^{k+1}-M}{M-1}\right)-Y\left(\frac{M-1}{M-1}\right)\\ & =P{M}^{k+1}-Y\left(\frac{M^{k+1}-1}{M-1}\right)\end{array}$
  • 于是，当$t=k+1$时公式成立