计算机能做什么与不能做什么计算机能做什么与不能做什么计算机是二十世纪人类最伟大的发明，它极大地推动了科学技术的进步，强烈地影响着人类社会生活的各个方面，并且对人类精神与智力的至尊地位提出了巨大的挑战。近年来，计算机“深蓝”战胜了国际象棋天才霸主卡斯帕罗夫，三、四十年前人工智能前辈们的预言终于成为现实，从任何意义上将这都是极具震撼力的事件。这既是人类的胜利，也是计算机的胜利。 计算机之所以有力量，硬件的高速发展是一个重要原因，但还不是最主要的原因。计算机的力量主要来自其软件，软件的核心是算法。算法是计算机的灵魂，算法的改进所产生的作用要比单纯提高硬件速度有效得多。算法的历史比计算机长得多，例如求两个整数的最大公约数的欧几里德算法距今已有两千多年的历史了。算法的理论也极为深奥，它不仅已是数学的一部分，而且有些内容可以说是元数学的一部分，例如交互式证明理论。因此，算法的研究一直是计算机研究与应用中最具挑战性的工作。 计算机算法的研究有两条截然不同的路线：一条路线研究计算机不能做什么，另一条路线研究计算机能做什么。 研究计算机不能做什么早在计算机诞生之前就已经开始并有了明确的结论。1936 年，图林(Turing)提出了图林机模型，用这个抽象的计算机模型定义了算法、计算、可计算等概念，证明了存在计算机不可计算的问题，从而给出了计算机能力的界限。 70 年代初期，Cook、Karp 定义了 NP 完全的复杂性类，证明了相当多的现实问题是 NP 完全问题。NP 完全问题用现有的算法求解均需要指数长的时间，因此，在现有计算资源下实际上不大可能求解。这是人类对计算机能力的局限性又一次深刻的揭示。由此诞生的计算复杂性理论成为理论计算机科学的中心内容。计算复杂性既是对计算机能力的一大限制，又是对人类认识能力的一大限制。今天，计算机已成为人类认识自然、改造自然必不可少的最有力的武器，因此，计算机不能做什么就意味着许多事人类同样也不能办到。 研究连续问题计算复杂性的著名学者 Traub 认为，或许有可能从形式上证明某些科学问题是无法解答的，因为宇宙中不存在能够解答这类问题的计算资源(时间，存储器，能量等)。 计算复杂性理论也使我们对什么是数学中的美有了新的认识。例如，图论中一个著名定理是平面图判定的 Kuratowski 定理，这个定理说一个图可平面化当且仅当图中不含两种类型的子图。从数学上讲，这是个优美的定理。但是，直接按这个定理设计计算机程序即算法，复杂度极高！真正有效的计算机算法选择的完全是另外一条路，其中主要是深度优先搜索。 这从数学上看似乎不太优美，但是此算法的复杂度是线性的，因而是极其有效的。因此我们说，计算复杂性使我们对美与效率有了新的认识，没有效率的美至少是不完美的。 但是，以 NP 完全性理论为代表的计算复杂性理论也逐渐暴露出它的局限性。NP 完全性理论指出，NP 完全问题的求解可能存在本质困难。但是，NP 完全问题在科学研究和生产实践中广泛存在，而且迫切需要解决。无论多么困难，这些问题是不会消失的。因此，仅仅指出问题的难解性是不够的，更重要的是给出求解方法。而 NP 完全性理论最大的不足就是它不提供正面的解决方法。NP 完全性理论的所有结论基本上是否定性的，非常容易使人在面对真实问题时持一种悲观、消极的态度。 NP 完全性理论的第二个缺陷是它仅指出用一个算法求解一个问题的所有实例时在最坏情况下可能是指数复杂度的，而我们在真实世界遇到的问题并不一定正好是最坏实例。即使对每一个算法均存在最坏实例，也并不意味着某一个实例对所有算法均是最坏的。换句话说，NP 完全性理论只是指出以不变的算法对付万变的问题是存在困难的，而以万变的算法对付万变的问题则就不受 NP 完全性理论的限制了！ 可见，NP 完全性理论给我们带来对计算机能力局限性的深刻认识的同时，它的非正面的、非构造性的研究方法和研究结论也有很大的局限性。在当前大量现实问题迫切需要解决的形势下，自然应当更加重视正面的、构造性的算法研究方向，这个方向的主要内容就是算法的设计与分析。 算法设计与分析的目的是探讨计算机能做什么。1995 年，一批优秀的理论计算机科学家代表理论计算机科学界总结了理论计算机科学在通讯网络、并行计算机体系结构、软件系统、超大规模集成电路设计、学习理论、生物学、数学、制造、天文学等领域做出的贡献，所有的贡献都是算法的形式。可以说计算机对人类社会所做的贡献必须通过算法才能被接受，而计算机不能做什么的研究对大多数人来说是不必关心的问题。那么，从学术角度，算法复杂性理论与算法设计与分析理论是什么样的关系呢？ 算法复杂性理论是算法设计与分析理论的元理论。元理论分析这个理论本身，例如对这个理论的基本概念给予精确的定义，并研究这个理论的局限性。一般而言，理论确立有用的正面结果，而元理论则多半由反面结果组成，它限定这种理论的研究范围。因此，算法复杂性理论常给出消极结果，算法设计与分析理论常给出积极结果，这分别是它们的本质特点，我们不必过多指责算法复杂性理论。 算法复杂性理论的反面结果对算法设计与分析的方向具有很大影响。最初，人们追求的是问题的最优解。NP 完全性理论诞生后，人们意识到追求最优解是不太现实的，转而寻找问题的近似解，但希望能有一定的性能保证，比如比最优解差不超过 5%。NP 理论的进一步研究表明，对相当多的一些问题，要使近似解具有任意的性能保证，也不大可能在多项式时间内完成。这样，算法设计的目标开始转向启发式算法，即直观合理，但在数学上不再具有性能保证的算法。在算法设计目标逐渐现实化的过程中，NP 完全性理论提供了重要的理论依据。 但是，算法设计与分析理论从 NP 完全性理论中得到的启发毕竟太少、太抽象、太不具体了，特别是在技巧上得不到任何帮助，因此，算法设计与分析虽然在计算复杂性理论限定的范围内发展，但却基本上走着一条相对独立的道路。吴文俊先生在总结我国古代数学发展的特点时说:“我国的古代数学基本上遵循了一条从生产实践中提炼出数学问题，经过分析综合，形成概念与方法，并上升到理论阶段，精练成极少数一般性原理，进一步应用于多种多样的问题。从问题而不是从公理出发，以解决问题而不是以推理论证为主旨，这与西方之以欧几里德几何为代表的所谓演绎体系旨趣迥异，途径亦殊。” 这一段话实际上也是对算法设计与分析理论的发展道路的最好描述。 【相关知识】 1. NP 问题 2. 算法复杂性 【技术学习】微软对联系统 微软对联系统是由微软亚洲研究院自然语言计算组研发的计算机自动对联系统。该系统采用人工智能技术对自然语言进行识别。当用户给定上联，它能够自动提供若干下联供用户选择； 并且当用户确定一副对联后，它还能够生成若干四字横批供用户参考。除此以外，微软对联系统还有如下功能： （1）下联定字：用户在下联任意位置输入想要的字词，系统将自动补全空缺处字词并生成完整的下联候选。 （2）用字推敲：系统除了生成完整的下联候选外，还能提供上联中所含字词的单独的可对字词候选，方便用户根据自己的爱好创作对联。 （3）机巧对联：系统支持复字联、拆字联和同音异字联。 （4）嵌名对联：系统还能识别人名，比如在上联中嵌入了人名，下联也会对人名。 （5）图片装裱：对联完成后，系统提供了将对联装裱成一张图片的功能，用户还可以将生成的图片发到手机上。