算法(第 4 版)
Robert Sedgewick, Kevin Wayne
ACM Fellow, ACM 杰出教育家
2178 人已学习
立即订阅
登录后,你可以任选4讲全文学习
推荐试读
换一换
时长 04:02
时长 01:33:37
课程目录
已完结/共 41 讲
时长 00:58
时长 03:10
时长 05:29
时长 04:02
时长 01:24:35
时长 01:33:37
时长 01:16:16
时长 01:26:27
时长 30:28
时长 36:09
时长 48:57
时长 47:59
时长 54:43
时长 46:00
时长 56:31
时长 56:13
时长 53:55
时长 01:12:09
时长 51:36
时长 55:01
时长 01:35:07
时长 04:45
时长 04:08
时长 47:52
时长 45:42
时长 37:58
时长 01:13:26
时长 15:16
时长 17:22
时长 25:55
时长 14:40
时长 28:01
时长 04:15
时长 03:41
时长 03:52
算法(第 4 版)
15
15
1.0x
00:00/00:00
登录|注册

6.0.6 不可解性

本书中讨论的算法一般都是用来解决实际问题的,因此它们消耗的资源都是有限的。大多数算法的实用性是显而易见的,而且对于许多问题,我们还很幸运地能够在几种不同的算法之间进行选择。但不幸的是,现实生活中还有许多其他问题并没有如此有效的解决方法。更糟糕的是,对于许多类问题,人们甚至不知道是否存在有效解决它们的方法。这种情况让程序员和算法的设计者都极度沮丧,因为他们无法为许多实际问题找到有效的算法。对于理论学者而言,沮丧来自于他们无法证明这些问题到底有多难。在这个领域,人们已经进行了大量的研究,并发展出了一种方法来判断一个新问题从技术的角度来说是否能够归于“难以解决”这个类别。尽管这方面的研究大多数都超出了本书的范畴,但是理解它们的核心思想并不困难。我们将在这里介绍它们,因为当面对一个新问题时,每个程序员都应该了解不存在解决它的高效算法的可能性。

6.0.6.1 准备工作

20 世纪最漂亮和有趣的智力发明之一,就是阿兰·图灵在 20 世纪 30 年代发明的“图灵机”。它是一个简单而又非常通用的计算模型,足以描述任意计算机程序和设备。一台图灵机就是一台能够读取输入、变换状态和打印输出的有限状态机。图灵机是理论计算机科学的基础。它来自于下面两个重要的思想。
确认放弃笔记?
放弃后所记笔记将不保留。
新功能上线,你的历史笔记已初始化为私密笔记,是否一键批量公开?
批量公开的笔记不会为你同步至部落
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线
笔记
复制
AI
  • 深入了解
  • 翻译
    • 英语
    • 中文简体
    • 中文繁体
    • 法语
    • 德语
    • 日语
    • 韩语
    • 俄语
    • 西班牙语
    • 阿拉伯语
  • 解释
  • 总结

本文深入探讨了算法的不可解性问题,围绕图灵机的普遍性、可计算性和扩展的丘奇—图灵论题展开讨论。文章指出存在一些问题没有有效的解决方法,甚至无法确定是否存在有效解决方法,给程序员和算法设计者带来沮丧。此外,文章介绍了指数级别的运行时间和搜索问题,以及NP问题的集合。通过讨论线性等式可满足性和线性不等式可满足性等问题,阐述了NP问题的重要性。文章以深入浅出的方式解释了这些概念,使读者能够快速了解不可解性问题及其在计算机科学领域的重要性。此外,文章还介绍了P集合中的问题,强调了多项式时间算法的重要性。整体而言,本文通过对算法不可解性问题的深入剖析,为读者呈现了一个全面而清晰的技术视角。文章还探讨了非确定性的强大和P=NP问题的重要性,以及多项式时间问题的相互归约和NP-完全性,为读者呈现了算法领域的前沿研究和挑战。文章通过深入讨论NP-完全性问题和P=NP问题,展现了算法领域的复杂性和挑战,为读者呈现了一个全面而清晰的技术视角。

仅可试看部分内容,如需阅读全部内容,请付费购买文章所属专栏
《算法(第 4 版)》
立即购买
登录 后留言

精选留言

由作者筛选后的优质留言将会公开显示,欢迎踊跃留言。
收起评论
显示
设置
留言
收藏
沉浸
阅读
分享
手机端
快捷键
回顶部