||
从第1台电子计算机问世到现在已经60年了,尽管计算机科学和技术继续保持高速发展的态势,但是计算机科学与技术不能再采用以往一样的方式发展,需要革命性的突破。如果一直顺着过去形成的惯性发展,计算机科学的路子可能会越走越窄。我们需要静下心来,认真进行反思,总结经验和教训,以便将来更快更好地发展。
计算机科学的迷途
1.计算机科学不应以把解决方案搞复杂为荣
普遍认为,计算机科学是“算法的科学”。美国计算机学会(ACM)对计算机科学有如下的定义:Computer Science as the "systematic study of algorithmic processes that describe and transform information: their theory, analysis, design, efficiency, implementation and application"。算法研究应该是计算机科学的重要内容,但是从某些意义上讲,计算机科学“成也算法,败也算法”。
计算机科学有两个基础:可计算性和计算复杂性。可惜,目前学习可计算性的主要兴趣在证明某些问题不可计算;学习计算复杂性的主要兴趣在证明NP困难问题。在其他学科中很少见到科学家对不可解或实际上几乎不可解的问题有这么大的兴趣。电子工程科学真正帮助了电路设计,如芯片设计的EDA工具在集成电路产业发展中功不可没。但计算机科学并没有大大减轻编软件的困难,软件设计理论的确需要革命性的突破。
上世纪70年代有一本书《计算机和不可解性(Computers and Intractability)》,作者是M. R. Garey和D. S. Johnson,很多学校都采用作为本科高年级或研究生教材,影响很大。这本书的扉页上有一张漫画,漫画中一个人说:这个问题我不能解决,但是你也不能解决,因为它是NP完全问题。说话那个人表现出十分得意的样子。这幅漫画影响了计算机界几十年,从事计算机科学研究的人对解决不了实际需要攻克的困难问题一般不会有任何内疚,因为这是大家都解决不了的NP问题。这种导向对计算机科学已产生了不好的影响。我们真正需要的不是发现一些理论上复杂的问题,而是要在用户满意的前提下尽可能有效地解决实际存在的复杂问题。计算机科学不应以把解决方案搞复杂为荣,尽可能用简单方法处理复杂问题是信息技术的生存之道。
2.应当重视确定可有效求解的问题边界
我们做的研究工作多数是改进前人的算法或理论模型,至于沿着已开辟的方向究竟还有多大改进的余地却很少考虑,很可能这一方向已到了可有效求解的问题边界,而另一方向有很广阔的改进空间我们反而没有触及。
15年前,美国纽约大学的施瓦茨(Schwartz)教授在智能中心做过一个报告。他说,数学上已知的(knowable)问题边界极不规则(如图1所示)。就像油田开采一样,在某个位置钻井有油,偏离一点就没有油。问题的可解性也很类似,某个问题在某些条件下是易解的,但是如果条件稍微改变一点点就很难解甚至不可解了。确定可有效求解的问题边界,应该是计算机科学的重要内容。