设置网站域名解析和网站主机绑定,ps做网站 大小,邹平建设网站,要建设网站文章目录 [toc]第〇章#xff1a;绪论0.1|自动机、可计算性与复杂性计算复杂性理论可计算性理论自动机理论 0.2|数学概念和术语集合关系等价关系 图简单路径连通图圈强连通图 字符串和语言字母表上的字符串空串 w w w的反转#xff08;倒序#xff09; x x x和 y y y的连接字… 文章目录 [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,i1}∣0≤i≤n−2}∪{{n−1,0}}∪{{i,in/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} 2n2m2由于 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 m2k 2 n 2 ( 2 k ) 2 4 k 2 2 n^{2} (2k)^{2} 4 k^{2} 2n2(2k)24k2 n 2 2 k 2 n^{2} 2 k^{2} n22k2故 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 I0为贷款的年利率 I 0.06 I 0.06 I0.06表示年利率为 6 % 6 \% 6% Y Y Y为月付款数 M 1 I / 12 M 1 I / 12 M1I/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) PtPMt−Y(M−1Mt−1)
证明
归纳基础 当 t 0 t 0 t0时 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 P0PM0−Y(M−1M0−1)P成立 归纳步骤 对于每一个 k ≥ 0 k \geq 0 k≥0假设当 t k t k tk时公式成立 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) PkPMk−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} Pk1PkM−Y[PMk−Y(M−1Mk−1)]M−YPMk1−Y(M−1Mk1−M)−Y(M−1M−1)PMk1−Y(M−1Mk1−1)于是当 t k 1 t k 1 tk1时公式成立
