ITOC chapter0 读书笔记

0 Introduction 导引

0.1 Automata, Computability, and Complexity 自动机、可计算性与复杂性

计算理论的三个核心领域:自动机、可计算性、复杂性

计算机的基本能力和限制是什么?

计算复杂性理论:按照计算难度给问题分类的体系(容易–困难)

可计算理论:一些基本问题不能用计算机解决,如“确定一个数学问题是真还是假“(可解–不可解)

自动机理论:自动机理论论述计算的数学模型的定义和性质。(有穷自动机、上下文无关文法)

0.2 Mathematical Notions and Terminology 数学概念和术语

一大波数学概念(都在离散数学上见过0.0)

  1. 集合
  2. 序列和多元组
  3. 函数和关系
  4. 字符串和语言
  5. 布尔逻辑

0.3 Definitions, Theorems, and Proofs 定义,定理和证明

定义:描述我们使用的对象和概念

定理:被证明为真且关键的数学命题
(不关键的,一般是证明来去证明更大(关键)的命题,一般叫引理)
(关键的定理推导出相关命题为真,一般叫推论)

证明:确定数学命题的真假
(尝试去构造证明时的技巧:有耐心,回头做,条理清晰,表述简洁)

0.4 Types of Proofs 证明的方法类型

构造法:

定理:存在/如果xxx(特定类型对象),使得/那么就xxxxxxx。
证明方法:构造这样的对象
如:对于每一个大于2的偶数n,存在n个顶点的3正则图

反证法:

证明方法:假设这个定理为假,然后证明这个假设导致一个错误结论,与假设矛盾,故定理为真。
如:证明2的平方根是无理数。

归纳法:

归纳基础:P(1)为真
归纳步骤:若P(i)为真,则P(i+1)也为真
由归纳步骤与归纳基础则:对于任意i>=1,P(i)为真。

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注