相关资源

-《计算理论导引》第三版 pdf

链接：https://pan.baidu.com/s/1G94BC9U3ZMoRLQ1phGl07Q
提取码：qycz

第 0 章 绪论

该课是计算机科学的理论课。

  • 计算理论
    • 研究理论计算机的科学
    • 研究计算机的理论模型，研究计算机的本质，也就是把计算机看成一个数学系统。（因为计算机科学的基本思想和模型在本质上是数学——离散的。）

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

0.1.3 自动机理论

How to define a computer?

​ Automata theory

  • 形式语言与自动机理论——阐述了计算的数学模型的定义和性质
    • 正规文法与有限自动机（正则语言）（第 1 章）
    • 上下文无关文法与下推自动机（上下文无关语言）（第 2 章）
    • 图灵机（递归可枚举语言）（第 3 章）

0.1.2 可计算性理论

Are there problems that a computer cannot solve?

​ Computability theory

  • 可计算性理论——把问题分成容易计算与难计算的
    • 什么是可计算？（第 4-6 章）

0.1.1 计算复杂性理论

If so, can we find one such problem?

​ Complexity theory

  • 计算复杂性理论——把问题分解成可解的和不可解的
    • 时间复杂性（第 7 章）
    • 空间复杂性（第 8 章）
      -（第 9-10 章）

0.2 数学概念和术语

Unlike other CS courses, this course is a MATH course…

We will look at a lot of definitions, theorems and proofs

  • 基本数学概念与术语回顾

    • Set 集合
    • Sequence 序列
    • Function 函数
    • Graph 图表
    • String 串
    • …

  • 证明技术

    • construction 构造法
    • contradiction 反证法
    • induction 数学归纳法

  • 数学 Mathematics Review

    • 离散数学
    • 数理逻辑
    • 集合论
    • 图论

0.2.1 集合（Set）

Python3 集合 | 菜鸟教程 (runoob.com)

0.2.2 序列（Sequence）和多元组（tuples）

值可变化：

值不可变化：

序列：

​ A sequence of items is a list of these items in some order.

  • (5,12,24)≠(12,5,24)(5, 12, 24)\ne(12,5, 24)

  • (5,12,24)≠(5,12,12,24)(5,12,24)\ne(5,12,12,24)

元组

​ Finite sequences are also called tuples

  • (5,12,24)(5,12,24) is a 3-tuple

  • (5,12,12,24)(5,12,12,24) is a 4-tuple

集合与序列可以作为其他集合或序列的元素。

幂集：

所谓幂集（Power Set），就是原集合中所有的子集（包括全集和空集）构成的集族。

设有集合 A，由 A 的所有子集组成的集合，称为 A 的幂集，记作2A2^A，即：2A=S∣S⊆A2^A={S|S\subseteq A}。

如 A={0,1}A = \{ 0, 1\}

则2A={{},{0},{1},{0,1}}2^A=\{ \{\},\{0\},\{1\},\{0,1\} \}

笛卡尔积：

如 A={1,2},B={x,y,z}A=\{1, 2\}, B=\{x,y,z\}

则A×B={(1,x),(1,y),(2,x),(2,y),(2,z)}A\times B=\{(1,x),(1,y),(2,x),(2,y),(2,z)\}

A×B×A={(1,x,1),(1,x,2),(1,y,1),(1,y,2),(1,z,1),(1,z,2),(2,x,1),(2,x,2),(2,y,1),(2,y,2),(2,z,1),(2,z,2)}A\times B \times A =\{(1,x,1),(1,x,2),(1,y,1),(1,y,2),(1,z,1),(1,z,2),(2,x,1),(2,x,2),(2,y,1),(2,y,2),(2,z,1),(2,z,2)\}

集合自身的笛卡尔积可以写成：

\overset{k}{\overbrace{A\times A\times ...\times A}} = A^k

笛卡尔积运算的性质:

  • 若 AA、BB 中有一个空集，则 ϕ×A=A×ϕ=ϕ\phi \times A = A \times \phi = \phi
  • 当 A≠BA \ne B 且 AA、BB 都不是空集时，有 A×B≠B×AA\times B\ne B\times A
  • 当 AA、BB、CC 都不是空集时，有 (A×B)×C≠A×(B×C)(A\times B)\times C \ne A\times(B\times C)
  • 笛卡尔积满足交和并的分配律:
    • A×(B∪C)=(A×B)∪(A×C)A\times (B\cup C)=(A\times B)\cup(A\times C)
    • A×(B∩C)=(A×B)∩(A×C)A\times (B\cap C)=(A\times B)\cap(A\times C)
    • (A∪B)×C=(A×C)∪(B×C)(A\cup B)\times C=(A\times C)\cup(B\times C)
    • (A∩B)×C=(A×C)∩(B×C)(A\cap B)\times C=(A\times C)\cap(B\times C)

0.2.3 函数和关系

函数又称为映射，若f(a)=bf(a)=b，则称 ff 把 aa 映射为 bb。

f:D→Rf:D\to R

D：domain（定义域）：函数所有可能的输入组成的集合。

R：range（值域）：函数所有可能的输出组成的集合。

如对于整数的加法函数：add:Z×Z→Zadd:\mathbf{Z} \times \mathbf{Z} \to\mathbf{Z}

定义域 Z×Z\mathbf{Z} \times \mathbf{Z} 是二元的，值域 Z\mathbf{Z} 是一元的。

将某些大家熟悉的二元函数写为特殊的中缀表示法的形式，如 a+ba+b，代替采用前缀表示法add(a,b)add(a,b)。

AA 到 BB 有多少个不同的关系？

如果 A=∣m∣,∣B∣=nA=|m|,|B|=n，则 ∣A×B∣=m×n|A\times B|=m\times n，而关系是 A×BA\times B 的子集，A×BA\times B 的子集共有 2m×n2^{m\times n} 个，所以，AA 到 BB 的关系共有 2m×n2^{m\times n} 个。

设 RR 是集合 XX 上的二元关系，RR 的性质有以下 5 种：

  • 自反性：对于每个 x∈Xx\in X，有 <x,x>∈R<x,x>\in R。关系矩阵主对角线上全为 1，关系图中每个顶点都有环。如实数集合上 ≤\le 关系，集合之间 $\subseteq $ 关系。
  • 反自反性：对于每个 x∈Xx\in X，有 <x,x>∉R<x,x>\notin R。关系矩阵主对角线上全为 0，关系图中每个顶点都没有环。如实数集合上 << 关系，集合之间 ⊂\subset 关系。

结论：

RR 是 XX 上的二元关系，则（IXI^X 表示恒等关系，关系矩阵主对角线上全为 1）：

  1. RR 是自反关系的充要条件是 IX⊆RI^X\subseteq R。
  2. RR 是反自反关系的充要条件是 R∩IX=ϕR\cap I^X=\phi。
  • 对称性：若 <x,y>∈R<x,y>\in R，有 <y,x>∈R<y,x>\in R。关系矩阵是对称矩阵，在关系图中，若两个顶点之间有边，则一定是一对相反关系的边。例如同学关系，兄弟关系。
  • 反对称性：若<x,y>∈R<x,y>\in R，且 x≠yx\ne y，有<y,x>∉R<y,x>\notin R。在关系矩阵中，如果 r_{ij}=1,且 i\ne j, 则 r_{ji}=0。关系图中，如果两个顶点之间有边，一定是一条有向边。例如父子关系，上下级关系。

R1={<1,1>,<2,3>,<3,2>}R_1=\{<1,1>,<2,3>,<3,2>\} 是对称的。

R2={<1,1>,<3,3>}R_2=\{<1,1>,<3,3>\} 是对称的也是反对称的。

R3={<2,2>,<2,3>,<3,2>,<3,1>}R_3=\{<2,2>,<2,3>,<3,2>,<3,1>\} 不是对称的也不是反对称的。

R4={<2,2>,<2,3>,<3,1>}R_4=\{<2,2>,<2,3>,<3,1>\} 是反对称的。

​ 存在关系既不是对称的，也不是反对称的（关系图中两个顶点之间的边既有有相反关系的边，也有有向边）。也存在关系既是对称的，也是反对称的（关系图中两个顶点之间没有边）。

  • 传递性：若 <x,y>∈R<x,y>\in R 且 <y,z>∈R<y,z>\in R，则有 <x,z>∈R<x,z>\in R。关系图中，如果顶点 xix_i 到 xjx_j 有边，xjx_j 到 xkx_k 有边，则从 xix_i 到 xkx_k 有边。例如上下级关系，祖先关系，实数集合上 << 关系，集合之间的 \sub 关系。

等价关系:

  • 自反性
  • 对称性
  • 传递性

如关系 R：x x 与 y 年龄相同 ;

自反 : x 与 x 年龄相同 ; 自反 成立 ;
对称 : x 与 y 年龄相同 , y 与 x 年龄相同 ; 对称 成立 ;
传递 : x 与 y 年龄相同 , y 与 z 年龄相同 , x 与 z 年龄相同 ; 传递 成立 ;
等价关系 : 该关系是 自反 , 对称 , 传递 的 , 因此该关系 是等价关系 ;

复合关系：设 RR 为 XX 到 YY 上的关系，SS 为 YY 到 ZZ 上的关系，则 R∘SR\circ S 称为 RR 和 SS 的符合关系，表示为：

R∘S={<x,z>∣∃y(<x,y>∈R∧<y,z>∈S)}R\circ S=\{<x,z>|\exists y(<x,y>\in R \wedge <y,z>\in S)\}

例如若 xx 是 yy 的母亲，yy 是 zz 的妻子，则 xx 是 zz 的岳母。

关系的复合不满足交换律，但是满足结合律。

关系的 nn 次幂：设 RR 是 XX 上的二元关系，n∈Nn\in N，则关系的 nn 次幂 R(n)R^{(n)} 定义为：

  1. R(0)=IXR^{(0)}=I_X
  2. R(n+1)=R(n)∘RR^{(n+1)}=R^{(n)}\circ R

说明：如果 RR 是 XX 到 YY 的关系，且 X≠YX\ne Y，则 R2R^2 是无意义的，因为 R∘RR\circ R 是无法复合的。

定理：设 RR 是集合 XX 上的二元关系，mm，n∈Nn\in N，则

  1. R(m)∘R(n)=R(m+n)R^{(m)}\circ R^{(n)}=R^{(m+n)}（称第一指数律）
  2. (R(m))(n)=R(mn)(R^{(m)})^{(n)}=R^{(mn)}（称第二指数律）

此定理证明可以用数学归纳法加以证明。

第三指数律(R∘S)(n)=R(n)∘S(n)(R\circ S)^{(n)}=R^{(n)}\circ S^{(n)} 一般是不成立的（只要交换律不成立，第三指数律不成立）

  • 相当于关系矩阵作矩阵乘法

逆关系：设 RR 为 XX 到 YY 的二元关系，RR 的逆关系记为 RCR^C (或 R−1R^{-1})，即：

RC={<y,x>∣<x,y>∈R}R^C=\{<y,x>|<x,y>\in R\}（把序偶对颠倒一下顺序，关系中的元素与逆关系中的元素一一对应）

显然，若 R⊆A×BR\subseteq A \times B，则 RC⊆B×AR^C\subseteq B\times A

如 >> 关系的逆关系为 <<。若 2<32<3 则 3>23>2。

  • (T∘S)C=SC∘TC(T\circ S)^C=S^C\circ T^C
  • RR 是对称的，当且仅当 R=RCR=R^C
  • RR 是反对称的，当且仅当 R∩RC⊆IAR\cap R^C\subseteq I_A

关系 RCR^C 的关系图，是将关系 RR 的关系图中的箭头方向反向即可。

关系 RCR^C 的关系矩阵 MRCM_{RC} 是 RR 的关系矩阵 MRM_R 的转置矩阵。

0.2.4 图（graph）

  • 图
    • 路径（path）：由边连接的顶点序列。
      • 如果每一对顶点之间都有一条路径，则称这个图为连通图。
        • 有一个平凡的结论：连通图 G=<V,E>G=<V,E> 中，任意两个节点之间必是连通的。
      • 如果一条路中所有的边均不相同，则成为迹。
      • 如果一条路中所有的结点均不相同，则称为通路。
        • 迹不一定是通路，但通路一定是迹。
      • 简单路径（simple path）：没有顶点重复的路径。
      • 圈（cycle）：全如果一条路径的起点和终点相同，则称这个图为一个圈。（除了顶点是相同的，其他都不相同）
        • 如果一个圈包含至少 3 个顶点，并且除起点和终点之外没有顶点重复，则称它是一个简单圈。
    • 点割集和割点：
      • 设无向图 G=<V,E>G=<V,E> 为连通的，若有结点集 V1⊆VV_1\subseteq V，使得图 GG 删除了 V1V_1 所有结点后，所得的子图是不连通的，而删除了 V1V_1 的任意真子集后，所得的子图仍然是连通图。则称集合 V1V_1 为图 GG 的点割集。若某一结点就构成点割集，则称该结点为割点。
    • 边割集和割边：
      • 设无向图 G=<V,E>G=<V,E> 为连通的，若有边集 E1⊆EE_1\subseteq E，使得图 GG 删除了 E1E_1 所有边后，所得的子图是不连通的，而删除了 E1E_1 的任意真子集后，所得的子图仍然是连通图。则称集合 E1E_1 为图 GG 的边割集。若某一结点就构成点割集，则称该结点为割边（或桥）。
    • 对于任何一个图 G=<V,E>G=<V,E>，有 k(G)≤λ(G)≤δ(G)k(G)\le \lambda(G)\le \delta(G)（点割集数量 ≤\le 边割集数量 ≤\le 最小的度）
    • 不含有平行边和环的图称为简单图。
      • 简单图 G=<V,E>G=<V,E> 中若每一对结点间都有边相连，则称该图为完全图。
        • 有 nn 个结点的无向完全图记作 KnK_n。
          • nn 个借点的无向完全图 KnK_n 的边数为 \C^2_n=\frac{n(n-1)}{2}。
    • 相对于图 GG 的补图：设图 G′=<V′,E′>G'=<V',E'> 是图 G=<V,E>G=<V,E> 的子图，若给定另外一个图 G′′=<V′′,E′′>G''=<V'',E''> 使得 E′′=E−E′{\color{red}E''=E-E'}，且 V′′V'' 中仅包含 E′′E'' 的边所关联的节点。则称 G′′G'' 是子图 G′G' 的相对于图 GG 的补图。

png

©为(b)相对于(a)的补图，但是(b)不是©相对于(a)的补图（©的补图没有 c 点）。

  • 树（tree）：连通且没有简单圈的图。
    • 有时专门指树的一个顶点，把它称为这棵树的根（root）。
    • 一棵树中度数为 1 的顶点称为这棵树的树叶（leaf）。

png

0.2.5 字符串和语言

Python3 字符串 | 菜鸟教程 (runoob.com)

字母表（alphabet）：任意一个非空有穷集合。字母表的成员为该字母表的符号

字符串（string）是一个 sequence。

语言（language）：字符串的集合（A set of strings is called a language.）。

0.2.6 布尔逻辑

否定、合取、析取、条件、双条件定义及 LaTex 公式_老实人小李的博客-CSDN 博客_latex 条件公式

名称 符号
非（NOT） $ \lnot $
合取（AND） ∧\wedge
析取（OR） $\vee $
异或（XOR） $\oplus $
等值 $\leftrightarrow $
蕴涵 →\to

0.3 定义、定理和证明

0.4.1 构造性证明（proof by construction）

在数学中，构造性证明是证明方法的一种，通过直接或间接构造出具有命题所要求的性质的实例来完成证明。

绝大多数证明都是基础理论问题，都是用构造性证明。

现采用构造性证明方法证明以下定理。我们定义：如果图中每一个顶点的度数都为 k，则称这个图是 k 正则的（k-regular）。

  • 对于每一个大于 2 的偶数 nn，存在一个有 nn 个顶点的 3 正则图。
    • 证明：设 nn 是大于 2 的偶数。现构造有 nn 个顶点的图 G=(V,E)G=(V,E), GG 的顶点集 {0,1,...,n−1}\{0,1,...,n-1\}，边集为png
      • 1：将 nn 个点均匀排列在一个圆上，对每一个顶点，连接其左右邻点各为一条边。
      • 2：第三边与其对点相连。
    • 按照上面的定义，证得该命题为真。

0.4.2 反证法（proof by contradiction）

反证法是“间接证明法”一类，是从反方向证明的证明方法，即：肯定题设而否定结论，经过推理导出矛盾，从而证明原命题。

0.4.3 归纳法（proof by induction）

第一数学归纳法与第二数学归纳法 - 知乎 (zhihu.com)

第一数学归纳法可以概括为以下三步：

  1. 归纳奠基：证明当 n=1 时命题成立；

  2. 归纳假设：假设当 n=k 时命题成立；

  3. 归纳递推：由归纳假设推出当 n=k+1 时命题也成立．

一般我们都是使用第一数学归纳法，但是对于第二数学归纳法，在算法导论中也是经常使用。

Icon
Icon
Icon
Icon
上一篇：Theory-计算理论导引1
下一篇：Diary-冀了以后