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

文章目录

• • @[toc]
  • 第〇章：绪论
  • • 0.1|自动机、可计算性与复杂性
    • • 计算复杂性理论
      • 可计算性理论
      • 自动机理论
    • 0.2|数学概念和术语
    • • 集合
      • 关系
      • • 等价关系
      • 图
      • • 简单路径
        • 连通图
        • 圈
        • 强连通图
      • 字符串和语言
      • • 字母表上的字符串
        • 空串
        • w w w的反转（倒序）
        • x x x和 y y y的连接
        • 字符串顺序
        • 语言
    • 0.3|定义、定理和证明
    • • 定理
      • 证明
      • • P P P仅当 Q Q Q
        • P P P当 Q Q Q
    • 0.4|证明的类型
    • • 构造性证明
      • • 示例
        • • 定理
          • 证明
      • 反证法
      • • 示例
        • • 定理
          • 证明
      • 归纳法
      • • 示例
        • • 定理
          • 证明

第〇章：绪论

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

计算复杂性理论

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

可计算性理论

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

自动机理论

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

0.2|数学概念和术语

集合

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

关系

等价关系

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

图

简单路径

• 没有顶点重复的路径

连通图

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

圈

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

强连通图

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

字符串和语言

字母表上的字符串

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

空串

• 记为 ε \varepsilon ε

w w w的反转（倒序）

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

x x x和 y y y的连接

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

字符串顺序

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

语言

• 字符串的集合

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

0.3|定义、定理和证明

定理

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

证明

P P P仅当 Q Q Q

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

P P P当 Q Q Q

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

0.4|证明的类型

构造性证明

示例

定理

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

证明

• 设 n n n是大于 2 2 2的偶数，现构造有 n n n个顶点的图 G = ( V , E ) G = (V , E) G=(V,E)， G G 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}

反证法

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

示例

定理

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

证明

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

• n 2 = m n \sqrt{2} = m n2 ​=m

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

• 2 n 2 = ( 2 k ) 2 = 4 k 2 2 n^{2} = (2k)^{2} = 4 k^{2} 2n2=(2k)2=4k2

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

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

归纳法

示例

定理

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

证明

• 归纳基础
  • 当 t = 0 t = 0 t=0时， P 0 = P M 0 − Y ( M 0 − 1 M − 1 ) = P P_{0} = P M^{0} - Y \left(\cfrac{M^{0} - 1}{M - 1}\right) = P P0​=PM0−Y(M−1M0−1​)=P，成立
• 归纳步骤
  • 对于每一个 k ≥ 0 k \geq 0 k≥0，假设当 t = k t = k t=k时公式成立， P k = P M k − Y ( M k − 1 M − 1 ) P_{k} = P M^{k} - Y \left(\cfrac{M^{k} - 1}{M - 1}\right) Pk​=PMk−Y(M−1Mk−1​)
  • P k + 1 = P k M − Y = [ P M k − Y ( M k − 1 M − 1 ) ] M − Y = P M k + 1 − Y ( M k + 1 − M M − 1 ) − Y ( M − 1 M − 1 ) = P M k + 1 − Y ( M k + 1 − 1 M − 1 ) \begin{aligned} P_{k + 1} = P_{k} M - Y = \left[P M^{k} - Y \left(\cfrac{M^{k} - 1}{M - 1}\right)\right] M - Y &= P M^{k + 1} - Y \left(\cfrac{M^{k + 1} - M}{M - 1}\right) - Y \left(\cfrac{M - 1}{M - 1}\right) \\ &= P M^{k + 1} - Y \left(\cfrac{M^{k + 1} - 1}{M - 1}\right) \end{aligned} Pk+1​=Pk​M−Y=[PMk−Y(M−1Mk−1​)]M−Y​=PMk+1−Y(M−1Mk+1−M​)−Y(M−1M−1​)=PMk+1−Y(M−1Mk+1−1​)​
  • 于是，当 t = k + 1 t = k + 1 t=k+1时公式成立