Skip to Main Content
计算机科学导论:跨学科方法
book

计算机科学导论:跨学科方法

by 罗伯特 塞奇威克, 凯文 韦恩
August 2021
Beginner to intermediate content levelBeginner to intermediate
450 pages
19h
Chinese
Pearson
Content preview from 计算机科学导论:跨学科方法

5.5 难解性

在前面的章节中,我们根据是否能被计算机解决来对问题进行了分类。在本节中,我们将重点放在我们可以解决的问题上,特别是如何确定解决这些问题所需要的计算资源。

在本书中我们研究了很多算法,这些算法普遍用于解决实际问题,而且它们消耗的计算资源的数量是合理的。大多数算法带来的实际效益是显而易见的,对于许多问题,我们都有很多高效的算法可以选择。不幸的是,许多在实践中出现的其他问题不能使用这些有效的解决方案。更糟糕的是,对于一大类这样的问题,我们甚至无法判断是否存在有效的解决方案。对于程序员和算法设计人员来说,这种情况是十分令人沮丧的,因为对于很大一部分的实际问题他们找不到适用的有效算法;理论家们也同样沮丧,因为他们也无法找到有效的方法来证明这些问题确实是很难解决的。

人们在这个领域已经做了大量的工作,这导致一个新的机制的发展。这个机制是将新出现的这些问题在特定的技术意义上归类为“难以解决”的问题。虽然这些工作的大部分都超出了本书的范围,但是中心思想是相通的。我们在这里介绍这些工作是因为对于每个程序员来说,当他们面临一个新问题时,他们应该知道这个问题有可能是那些没人知道任何有效算法的问题,自然也无法保证能找到一个有效的解决方案。

在前面两节中,我们研究了下面两个观点,这两个观点源于20世纪30年代艾伦·图灵的开创性工作:

·普遍性。一个图灵机能够执行任何可以用物理存在的计算设备描述的计算(判定语言或者计算函数)。这个想法被称为邱奇-图灵理论。把这个理论推广到自然世界时是不能被证明的(但它有可能是错的)。支持这个理论的证据是,数学家和计算机科学家已经研究出大量的计算模型,但是它们全部被证明与图灵机一致。

·可计算性。无法通过图灵机来解决(根据普遍性,也可以说是通过任何物理存在的计算设备都无法解决)的问题是存在的。这是一个著名的数学事实。著名的停机问题(没有程序可以保证能够确定一个给定的程序是否会停机)就是这样的一个问题。 ...

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.
Start your free trial

You might also like

数据科学之编程技术:使用R进行数据清理、分析与可视化

数据科学之编程技术:使用R进行数据清理、分析与可视化

迈克尔 弗里曼, 乔尔 罗斯
C语言核心技术(原书第2版)

C语言核心技术(原书第2版)

Peter Prinz, Tony Crawford

Publisher Resources

ISBN: 9787111641414