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

文章目录

• • @[toc]
  • 第〇章：绪论
  • • 0.1|自动机、可计算性与复杂性
    • • 计算复杂性理论
      • 可计算性理论
      • 自动机理论
    • 0.2|数学概念和术语
    • • 集合
      • 关系
      • • 等价关系
      • 图
      • • 简单路径
        • 连通图
        • 圈
        • 强连通图
      • 字符串和语言
      • • 字母表上的字符串
        • 空串
        • $w$的反转（倒序）
        • $x$和$y$的连接
        • 字符串顺序
        • 语言
    • 0.3|定义、定理和证明
    • • 定理
      • 证明
      • • $P$仅当$Q$
        • $P$当$Q$
    • 0.4|证明的类型
    • • 构造性证明
      • • 示例
        • • 定理
          • 证明
      • 反证法
      • • 示例
        • • 定理
          • 证明
      • 归纳法
      • • 示例
        • • 定理
          • 证明
    • 后继
    • • 【计算理论】【《计算理论导引（原书第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$时公式成立

---

后继

【计算理论】【《计算理论导引（原书第3版）》笔记】第一章：正则语言

---