文章目录

• 一、计算理论内容概览
• 二、计算问题的 有效性
• 三、语言 与 算法模型
• 四、可计算性 与 可判定性
• 五、可判定性 与 有效性
• 六、语言分类

一、计算理论内容概览

---

计算理论分为 形式语言与自动机 , 可计算部分 , 计算复杂性部分 ;

形式语言与自动机 内容 : 自动机 , 确定性有限自动机 , 非确定性有限自动机 , 正则语言 , 泵引理 , 上下文无关语法 , 下推自动机 , 都属于 形式语言 与 自动机 部分 ;

可计算 内容 : 图灵机 , 确定性图灵机 , 非确定性图灵机 , 丘奇-图灵命题 , 可判定性 , 可计算性 等问题 ;

计算复杂性 内容 : 时间复杂性 , 模型间的时间复杂性关系 , $\mathrm{P}$ 类 , $\mathrm{N}\mathrm{P}$ 类 ;

二、计算问题的 有效性

---

可计算性 包含 可判定性 , 可判定性 包含 有效性 ;

可计算性 > 可判定性 > 有效性 ;

计算问题 对应的算法中 , 有些算法是 有效的 , 有些算法是 无效的 ,

如 : 穷举算法 , 蛮力搜索之类的算法 , 没有有效性可言 , 肯定不是有效算法 ; 贪心算法 , 欧几里得算法 是有效算法 ;

这里希望可以区分 有效算法 与 无效算法 ;

在上一篇博客 【计算理论】计算复杂性 ( 多项式等价 | P 类 | 丘奇-图灵论题延伸 ) 中给出了有效算法的严格的数学定义 ;

有效算法 : 就是在 多项式时间 内 , 可以执行完毕 , 得到一个确定的结果的算法 ;

三、语言 与 算法模型

---

语言 与 算法模型 :

① 正则语言 ( 自动机 ) : ${\mathrm{L}}_{\mathrm{r}}=\mathrm{L}({\mathrm{a}}^{\ast }{\mathrm{b}}^{\ast })$ , 该语言是正则表达式语言 ; $\mathrm{r}$ 下标含义是 regular 正则 ;

正则语言参考 : 【计算理论】正则语言 ( 正则表达式原子定义 | 正则表达式递归定义 | 正则表达式语言原子定义 | 正则表达式语言结构归纳 | 正则表达式语言示例 | 根据正则表达式构造自动机 )

② 上下文无关语言 ( 下推自动机 ) : ${\mathrm{L}}_{\mathrm{C}\mathrm{F}\mathrm{L}}=\{{\mathrm{a}}^{\mathrm{n}}{\mathrm{b}}^{\mathrm{n}}:\mathrm{n}\ge 0\}$ , 该语言不是正则表达式语言 , 是上下文无关语言 ; 下标 $\mathrm{C}\mathrm{F}\mathrm{L}$ 含义是 Context-Free Grammer , 上下文无关语法 ;

上下文无关语法参考 : 【计算理论】上下文无关语法 ( 语法组成 | 规则 | 语法 | 语法示例 | 约定的简写形式 | 语法分析树 )

③ 可判定语言 ( 判定机 ) : ${\mathrm{L}}_{\mathrm{d}}=\{{\mathrm{a}}^{\mathrm{n}}{\mathrm{b}}^{\mathrm{n}}{\mathrm{c}}^{\mathrm{n}}:\mathrm{n}\ge 0\}$ , 该语言不是上下文无关语言 , 是可判定语言 ; 下标 $\mathrm{d}$ 含义是 Decidability 可判定 ;

可判定语言参考 : 【计算理论】可判定性 ( 丘奇-图灵论题 | 可判定性引入 | 图灵机语言 | 图灵机结果 | 判定机 | 部分函数与全部函数 | 可判定性定义 )

④ 可计算语言 ( 图灵机 ) : ${\mathrm{L}}_{\mathrm{T}\mathrm{r}}={\mathrm{A}}_{\mathrm{T}\mathrm{M}}$ , 该语言是可计算的 , 不是图灵可判定的 ; 下标 $\mathrm{T}\mathrm{r}$ 含义是 Turing-recognizable ( 图灵机可识别 ) 即可计算的 ;

⑤ 不可计算语言 ( 没有对应算法模型 ) : ${\mathrm{L}}_{\mathrm{n}\mathrm{T}\mathrm{r}}={\overline{\mathrm{A}}}_{\mathrm{T}\mathrm{M}}$ , 图灵机不识别语言 , 不可计算语言 ;

参考博客 : 【计算理论】可判定性 ( 通用图灵机和停机问题 | 可判定性 与 可计算性 | 语言 与 算法模型 )

四、可计算性 与 可判定性

---

可判定性 与 可计算性

① 可判定性 ( Decidability ) : 计算模型是 图灵机中的 判定机 ;

② 可计算性 ( Turing-recognizable 图灵机可接受的 ) : 计算模型是 图灵机 ;

可计算性 包含 可判定性 ;

可计算性 与 可判定性 之间的相互关系 :

补集可计算 : 如果一个语言的 补集 ( Complement ) 是可计算的 ( Turing-recognizable ) , 那么称该语言是 补集可计算的 ( co-Turing-recognizable ) ;

判定 = 可计算 + 补集可计算 : 如果一个语言是 可判定的 ( Decidable ) , 那么这个语言是 可计算的 ( Turing-recognizable ) , 同时这个语言又是 补集是可计算的 ( co-Turing-recognizable ) ;

可计算 : Turing-recognizable

补集可计算 : co-Turing-recognizable

之前提到过 通用图灵机语言 ${\mathrm{A}}_{\mathrm{T}\mathrm{M}}$ 是 可计算的 , 对应的计算模型是 图灵机 , 但 ${\mathrm{A}}_{\mathrm{T}\mathrm{M}}$ 是 不可判定的 ;

可判定 = 可计算 + 补集可计算

通用图灵机语言 ${\mathrm{A}}_{\mathrm{T}\mathrm{M}}$ 是 不可判定的 , 可计算的 , 其补集肯定是不可计算的 ;

参考博客 : 【计算理论】可判定性 ( 通用图灵机和停机问题 | 可判定性 与 可计算性 | 语言 与 算法模型 )

五、可判定性 与 有效性

---

可判定性 与 有效性 :

① 可判定性 ( Decidability ) : 计算模型是 图灵机中的 判定机 ;

② 有效性 : 在 多项式时间 内 , 可以执行完毕 , 得到一个确定的结果的算法 ;

六、语言分类

---

语言分类 :

① 可计算语言 : 下推自动机等价问题算法 $\mathrm{E}{\mathrm{Q}}_{\mathrm{P}\mathrm{D}\mathrm{A}}$ , 通用图灵机语言 ${\mathrm{A}}_{\mathrm{T}\mathrm{M}}$ ;

② 可判定语言 : 无效算法语言 , 有效算法语言 ;

③ 无效算法语言 : 蛮力穷举算法 ;

④ 有效算法语言 : 正则表达式 , 上下文无关语言 , 动态规划算法 , 贪心算法 ;

下图中 , 分为 可计算 , 可判定 , 无效算法 , 有效算法 ;

① 可计算 : 蓝色部分之外的是 可计算语言 , 对应的计算模型是 图灵机 ;

② 可判定 : 蓝色圆框 之内的是 可判定语言 , 对应的计算模型是 判定机 ;

③ 无效算法 : 蓝色圆框 与 红色圆框 之间的是 无效算法 , 蛮力穷举算法 ;

④ 有效算法 : 红框内的算法是 有效算法 , 可以在 多项式时间 内得到一个结果 ;

总结

以上是生活随笔为你收集整理的【计算理论】计算复杂性 ( 阶段总结 | 计算理论内容概览 | 计算问题的有效性 | 语言与算法模型 | 可计算性与可判定性 | 可判定性与有效性 | 语言分类 ) ★的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。