文章目录

一、计算理论内容概览

二、计算问题的有效性

三、语言与算法模型

四、可估算性与可断定性

五、可断定性与有效性

六、语言分类

一、计算理论内容概览

估算理论分为方式语言与自动机,可估算部份,估算复杂性部份;

方式语言与自动机内容:自动机,确定性有限自动机,非确定性有限自动机,正则语言,泵引理,上下文无关句型巴伐利亚算法,下推自动机,都属于方式语言与自动机部份;

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

估算复杂性内容:时间复杂性,模型间的时间复杂性关系,PrmPP类,NPrmNPNP类;

二、计算问题的有效性

可估算性包含可断定性,可断定性包含有效性;

可估算性>可断定性>有效性;

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

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

这儿希望可以分辨有效算法与无效算法;

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

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

三、语言与算法模型

语言与算法模型:

①正则语言(自动机):Lr=L(a∗b∗)rmL_r=L(a^*b^*)L

=L(a

∗

∗

),该语言是正则表达式语言;rrmrr下标涵义是正则;

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

②上下文无关语言(下推自动机):LCFL={anbn:n≥0}rmL_{CFL}={a^nb^n:ngeq0}L

CFL

={a

:n≥0},该语言不是正则表达式语言,是上下文无关语言;下标CFLrm涵义是-Free,上下文无关句型;

上下文无关句型参考:【计算理论】上下文无关句型(句型组成|规则|句型|句型示例|约定的缩写方式|句型剖析树)

③可判断语言(判断机):Ld={anbncn:n≥0}rmL_{d}={a^nb^nc^n:ngeq0}L

={a

:n≥0},该语言不是上下文无关语言,是可判断语言;下标drmdd含意是可判断;

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

④可估算语言(图灵机):LTr=ATMrmL_{Tr}=A_{TM}L

Tr

=A

TM

,该语言是可估算的,不是图灵可判断的;下标TrrmTrTr含意是-(图灵机可辨识)即可估算的;

⑤不可估算语言(没有对应算法模型):LnTr=A‾TMrmL_{nTr}={A}_{TM}L

nTr

TM

,图灵机不辨识语言,不可估算语言;

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

四、可估算性与可判断性

可判断性与可估算性

①可判断性():估算模型是图灵机中的判断机;

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

可估算性包含可判断性;

可估算性与可判断性之间的互相关系:

补集可估算:假如一个语言的补集()是可估算的(-),这么称该语言是补集可估算的(co--);

判断=可估算+补集可估算:假如一个语言是可判断的(),这么这个语言是可估算的(-),同时这个语言又是补集是可估算的(co--);

可估算:-

补集可估算:co--

之前提到过通用图灵机语言ATMrmA_{TM}A

TM

是可估算的,对应的估算模型是图灵机,但ATMrmA_{TM}A

TM

是不可判断的;

可判断=可估算+补集可估算

通用图灵机语言ATMrmA_{TM}A

TM

是不可判断的,可估算的,其补集肯定是不可估算的;

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

五、可判断性与有效性

可判断性与有效性:

①可判断性():估算模型是图灵机中的判断机;

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

六、语言分类

语言分类:

①可估算语言:下推自动机等价问题算法EQPDArmEQ_{PDA}EQ

PDA

,通用图灵机语言ATMrmA_{TM}A

TM

②可判断语言:无效算法语言巴伐利亚算法,有效算法语言;

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

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

右图中,分为可估算,可判断,无效算法,有效算法;

①可估算:黑色部份之外的是可估算语言,对应的估算模型是图灵机;

②可判断:黑色圆框之内的是可判断语言,对应的估算模型是判断机;

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

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