, 可计算性 等问题 ;
计算复杂性 内容 : 时间复杂性 , 模型间的时间复杂性关系 ,
\rm P
类 ,
\rm NP
类 ;
计算理论 知识点很枯燥 , 但是 在进行理论研究时 , 或者大的计算机工程实践时...确定性有限自动机 的计算问题 , 都是可判定的 ;
③ 关于 下推自动机 的计算问题 , 有些可判定 , 有些不可判定 ;
三、计算问题的 有效性
----
可计算性 包含 可判定性 , 可判定性 包含...有效性 ;
可计算性 > 可判定性 > 有效性 ;
计算问题 对应的算法中 , 有些算法是 有效的 , 有些算法是 无效的 ,
如 : 穷举算法 , 蛮力搜索之类的算法 , 没有有效性可言 , 肯定不是有效算法...;
五、算法有效性 数学定义需求
----
有效性 与 无效性 区分时 , 将 贪心算法 分到有效性算法中 , 将蛮力穷举的算法 分到无效性算法中 ;
需要定一个区分原则 , 区分算法的有效性 , 将一个算法分为...\rm M
为什么必须是判定机 :
假设
\rm M
是图灵机 , 在某些输入上是不停机的 , 如输入字符串为
\rm aab
;
图灵机
\rm M
在
\rm aab
字符串上进行计算时