绪论

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

  • 计算复杂性理论

  • 可计算性理论

  • 自动机理论

数学概念和术语

集合

序列和多元组

序列 是某些元素或成员按某种顺序排成的一个列表。

与集合一样，序列也可以是有穷序列或者无穷序列。通常把有穷序列称为 多元组 。k个元素的序列称为 k元组。例如，（7,21,57)为一个3元组。

2元组也称为 有序对。

A的 幂集 为A的所有子集的集合。设A为集合{0,1}，则A的幂集为集合{∅，{0}，{1}，{0,1}}。

设A和B为两个集合，A和B的 笛卡儿积 或 叉积 为这样一个集合，它是第一个元素为A的元素、第二个元索为B的元素的所有有序对组成的集合，记作A × B 。

当函数ƒ的定义域为A1×A2×···Ak时，ƒ的输人是k元组（a1,a2,···ak）为ƒ的自变量。k个自变量的函数称为k元函数，走称为函数的 元数。当k等于1时，ƒ有一个自变量，称为 一元函数。当k等于2时，ƒ为 二元函数。

谓词 或 性质 是一种函数，它的值域为{TRUE,FALSE}。例如，设even为一个谓词，当输入为偶数时该函数的输出为TRUE;当输入为奇数时该函数的输出为FALSE。

定义域为Ak的谓词称为关系，或称为 k元关系，也称为A上的k元关系。通常用的是 二元关系 。

等价关系 是一种特殊类型的二元关系，它利用了用某种特征把两个对象等同起来的想法。
如果二元关系R满足以下3个条件：

  • R是自反的，即对每一个x有xRx
  • R是对称的，即对每一个x和y，xRy意味着yRx
  • R是传递的，即对每一个x,y和z，xRy和yRz意味着xRz
    则称R为一个等价关系。

函数和关系

函数的所有可能的输入组成的集合称为函数的定义域。函数的输出也来自于另一个集合，这个集合称为函数的值域。记为 ƒ:D→R 它表示函数的定义域为 D ,值域为 R 。

图

无向图 简称为 图，是由一个点的集合以及连接其中某些点的线段组成的。这些点称为 结点 或 顶点 ，线段称为 边

顶点的 度数 是以这个顶点为端点的边的数目。

路径 是由边连接的顶点序列。简单路径 是没有顶点重复的路径。

如果每一对顶点之间都有一条路径，则称这个图为 连通图 。

如果一条路径的起点和终点相同，则称这个图为一个 圈 。

如果一个圈除起点和终点之外没有顶点里复，则称它是一个 简单圈 。

树 是连通且没有简单圈的图。 有时专门指定树的一个顶点，把它称为这棵树的 根 。

一棵树中度数为1的顶点称为这棵树的 树叶 。

如果在图中用箭头代替线段，则得到 有向图。从一个顶点引出的箭头数为这个顶点的 出度，指向一个顶点的箭头数为这个顶点的 入度。

所有箭头的方向都与其前进的方向一致的路径称为 有向路径 。如果从每一个顶点到另一个顶点都有一条有向路径，则称这个有向图为 强连通图 。

字符串和语言

字符串是计算机科学中的基本构建块。根据应用的要求可以在各种各样的宇母表上定义这样的字符串。按照要求，定义 字母表 为任意一个非空有穷集合。字母表的成员为该字母表的 符号 。

字母表上的 字符串 为该字母表中符号的有穷序列。

字符串的 字典序 和大家熟悉的字典顺序一样，只是短的字符串排在长的字符串的前面。

布尔逻辑

布尔逻辑 是建立在两个值TRUE和FALSE上的代数系统。

非 或 NOT 运算，用符号﹁表示

合取 或 AND 运算，用符号∧表示

析取 或 OR 运算，用符号∨表示

异或 或 XOR 运算，用符号⊕表示

定义、定理和证明

证明的类型

  • 构造性证明

  • 反证法

  • 归纳法

转载请注明：转载自srzyhead的博客(https://srzyhead.github.io)

本文链接地址: 计算理论导引 (1-绪论)