《计算机世界》最近报道了计算机科学先驱Dijkstra于8月上旬逝世的消息。Dijkstra被西方学术界称为“结构程序设计之父”和“先知先觉”(Oracle),他一生致力于把程序设计发展成一门科学。科学研究的帅才最重要的素质是洞察力(Vision和Insight),能够发现有前景的新领域或在新领域内发现和解决最关键的问题。下面仅举几例说明Dijkstra的洞察力。
解决编译系统中的关键问题
FORTRAN是最早得到一定程度推广的高级语言,但FORTRAN的编译系统并未科学地解决一些主要的难题。最早提出用堆栈(stack)来编译复杂公式的是德国的Bauer和Samelson,他们的著名论文“顺序公式的翻译”(Sequential Formula Translation)是编译方面的经典论文。最近有些报道说Dijkstra是堆栈的发明人,这恐怕不符事实。Dijkstra发展了堆栈的概念,使之用于整个编译,以及目标代码运行时的动态存储分配,并在此基础上和Jenson完成了世界上第一个ALGOL60编译系统,采用了他首创的优先数编译算法。其中递归调用子程序时的环境维护是Dijkstra的重要贡献,Display这一术语就是当时他发明的,这是用来维护动态环境的一组寄存器(软件),其结构清晰并能适应任何复杂情况。我于20世纪60年代初看完他的文章后马上想到,假如计算机硬件中有对应的设备将极大地提高软件的运行效率。
Dijkstra是ALGOL 60报告的主要起草者之一,1972年Dijkstra在他获得ACM图灵奖的讲演中,仍对这一报告给予高度评价:“只有极少极少几个像ALGOL60报告这样短的文件能给计算机界带来如此深远的影响。”
同步进程的协调和操作系统的结构
Dijkstra在1950~1952年期间曾当过三年程序员,在从事硬件中断处理程序的研制中,他发现一些程序错误在多个中断同时出现的情况下无法再现,很容易被当作硬件的瞬间故障,这一现象使Dijkstra毛骨悚然,促使他后来钻研用科学方法从事软件研制。操作系统是当时最复杂的软件,1965年Dijkstra在ACM通讯上发表了仅一页长的短文“并行程序的控制”,这是他在操作系统领域的第一个重要贡献。该文提出了并行程序互锁问题的一个解决方案。“死锁”(Deadly embrace)这一术语是Dijkstra发明的。1967年在首届操作系统原理研讨会上,Dijkstra介绍了他和几个博士生研制的THE多道程序系统。THE系统的目的是验证Dijkstra关于操作系统原理、结构、同步进程通信机制等方面的一系列新想法。今天已经普遍采用的系统的多层结构、抽象、上层不需了解下层的详细细节等科学原则就是当时Dijkstra提出的,引起了强烈反响;同步进程通信的信号量Semaphore这一术语也是Dijkstra当时创造的。
同步进程协调方面的程序错误是很难发现的,为此我曾吃过大苦头。1979年我开始设计Ⅱ型照排系统,用了两台双极型高速微处理器平行工作实现轮廓字形的复原和控制激光扫描,两台微处理器通过信号量彼此协调。设计和编程均无错误,但在把微程序翻译成二进制代码时错了一位,结果造成了无法再现的随机故障:激光打印机输出的汉字有时拖尾巴。这一故障持续了一年多,引起用户不满,后由潍坊计算机公司的一位协作人员挖空心思地发现了错误的原因,即二进制码错误,问题才得以解决。
上世纪六十年代操作系统的研制经受了一系列重大挫折,典型的例子是OS 360。而Dijkstra为首的一批科学家的努力,使操作系统走上了健康发展的道路。
Go To语句有害和结构程序设计
结构程序设计被称为软件发展中的第三个里程碑(第一、二个里程碑是子程序和高级语言)。早在1965年召开的IFIP会议上,Dijkstra就提出“Go To语句可以从高级语言中取消”,“一个程序的质量与程序中所含的Go To语句的数量成反比”。但是,Dijkstra讲话的影响很小,当时人们正忙于IBM 360系列的使用;而IBM 360的主要语言之一是FORTRAN,Go To语句则是FORTRAN的支柱。
1968年Dijkstra给ACM通讯写了一篇短文,该文后改成信件形式刊登,以便早日发表,这就是具有历史意义的、著名的“Go To Letter”。Dijkstra在信中建议:“Go To语句太容易把程序弄乱,应从一切高级语言中去掉;只用三种基本控制结构就可以写各种程序,而这样的程序可以由上而下阅读而不会返回”。这封信引起了激烈的讨论。人们逐渐认识到:不是一个简单地去掉Go To的问题,而是促进一种新的程序设计观念、方法和风格,以期显著提高软件生产率和降低软件维护代价。当时采用结构程序设计方法的两个最著名项目是:
1. 纽约时报信息库管理系统,含8.3万行源代码,只化了11人年,第一年使用过程中,只发生过一次使系统失效的软件故障;
2. 美国宇航局空间实验室操作的模拟系统,含40万行源代码,只用两年时间就全部完成。
上个世纪六十年代末到七十年代初,上述这两个系统可以算得上是大型软件了。
结构程序设计概念影响了后来的高级语言,也影响了一代程序员的风格和习惯。
坚持真理,不惜反对恩师
ALGOL 68语言是Van Wijingaarden为主设计的,得到了IFIP下属的工作小组的多数票通过。Wirth、Dijkstra和Hoare等工作小组成员发表了“少数派报告”,强烈反对这一语言及其表达方式。ALGOL 68的表达方式独特而严格,但不易理解,是Wijingaarden的发明。事实证明,少数派是正确的,ALGOL 68很快就夭折了。
要知道,Wijingaarden是Dijkstra的恩师。上世纪五十年代初Dijkstra在阿姆斯特丹数学中心编程序时Wijingaarden是他的领导。Dijkstra当时正在攻读理论物理学位,他发现理论物理课程和程序设计在精力上越来越冲突,他又拿不定主意,到底成为一个理论物理学家还是选择程序设计作为自己的职业,而他当时又担心程序设计能否成为被尊敬的学科。充满不安心情的Dijkstra于1952年春的一个早晨敲开了Wijingaarden办公室的门。几个小时的谈话,使Dijkstra变了另外一个人,因为Wijingaarden向他指明了程序设计这门学科正处在起步阶段,因而有重大的机会,Dijkstra可以努力使程序设计变成一个受人尊敬的学科。Dijkstra把这次谈话称为他一生中的转折点,于是决定尽快结束理论物理研究,全身心地投入程序设计。Dijkstra说,为此他应该终生感谢Wijingaarden。但是Dijkstra还是强烈地反对其恩师的得意之作ALGOL 68,少数派报告虽被IFIP压制,但真理终究得到了证明,后来的成功语言都是背离ALGOL 68方向的。
Dijkstra的名言今天仍有现实意义
Dijkstra的主要贡献是在上个世纪五十年代末到七十年代初,也就是他二十多岁到四十岁出头这段时间完成的。回忆这些过去的成就是想强调:洞察力对一个科学家是何等的重要! Dijkstra获图灵奖以后,软件领域又涌现出图形用户界面、面向对象技术等一系列新的里程碑,因特网更是带来一个全新的时代。但是三十年前Dijkstra关于程序可靠性的一些名言至今仍有意义:
“有效的程序员不应该浪费很多时间用于程序调试,他们应该一开始就不要把故障引入。”
“程序测试是表明存在故障的非常有效的方法,但对于证明没有故障,调试是很无能为力的。”
Dijkstra大力鼓吹程序正确性证明,但这一方法离实用还有相当距离,因为一段源程序的正确性证明的文字往往比源代码还要长,所以充分的软件测试今天仍不可或缺。但是程序员的科学训练是十分重要的,有人曾做过一个试验:一个题目由一批印度程序员编程,其结果惊人地相似;而由一批中国程序员来做,编出的程序五花八门。中国的软件人员有时把创造性放在不恰当的地方。只有规范的科学的编程,一个大项目才能得到有效的管理,其质量才有保证。
中国软件产业的发展需要有洞察力的帅才,也需要一大批训练有素的程序设计人员和既懂技术又懂管理的项目领导人。
分享到:
相关推荐
Dijkstra算法,由荷兰计算机科学家艾兹格·迪科斯彻于1956年提出,是一种用于在加权图中寻找单源最短路径的算法。它保证了找到的路径是最优的,即从起点到每个顶点的路径长度都是最小的。在这个程序中,我们看到有两...
Dijkstra算法的特点是它保证了每次选取的都是当前未处理节点中距离源点最近的一个,所以最终得到的是从源点到所有其他节点的最短路径。但要注意,这个算法不适用于负权边,因为可能会漏掉更短的路径。 在压缩包中的...
Dijkstra算法的基本原理是使用邻接矩阵来存储图的信息,然后使用Dijkstra算法来计算从源节点到其他节点的最短路径。该算法的步骤如下: 1. 初始化:将所有节点的距离初始化为无穷大,除了源节点的距离为0。 2. 选择...
最短路径算法Dijkstra是图论中的一个经典算法,由荷兰计算机科学家艾兹格·迪科斯彻在1956年提出。该算法主要用于寻找带权重的有向或无向图中,从一个特定顶点到其他所有顶点的最短路径。Dijkstra算法的核心思想是...
在实际运行中,`DijkstraSP`类的实例会读取`tinyEWD.txt`中的数据,构建`EdgeWeightedDigraph`,然后执行Dijkstra's算法,找到从特定起点到所有顶点的最短路径。 **应用场景** 在IT领域,Dijkstra's算法的应用非常...
Dijkstra算法是一种常用的图算法,用于寻找从起点到其他顶点的最短路径。下面是一个使用Dijkstra算法的应用举例,展示了如何使用该算法来解决实际问题。 从给定的代码中,我们可以看到,这个应用举例是为了解决一个...
在地图导航系统中,它帮助计算从出发点到目的地的最快或最短路线;在社交网络分析中,它可以帮助找出两个用户之间的最短联系路径。 MATLAB实现的Dijkstra算法不仅可以帮助理解算法本身,而且可以作为原型快速验证和...
Dijkstra算法的基本思想是从起点开始,按照距离递增的顺序依次将各个顶点加入到已知最短路径集合中,直到终点被加入或者所有顶点都被加入。具体步骤如下: 1. **初始化**:设置起点的距离为0,其他所有顶点的距离为...
迪杰斯特拉(Dijkstra)算法是图论中一种经典的最短路径算法,由荷兰计算机科学家艾兹格·迪杰斯特拉在1956年提出。这个算法主要用于寻找有向或无向图中从一个特定源节点到其余所有节点的最短路径。在MATLAB环境中...
### 堆优化的Dijkstra算法(Dijkstra+邻接表+Heap) #### 算法概述 Dijkstra算法是一种用于解决单源最短路径问题的著名算法,它能够找到图中某一点到其他所有点的最短路径。在处理大规模数据时,原始的Dijkstra...
Dijkstra算法算是贪⼼思想实现的,⾸先把起点到所有点的距离存下来找个最短的,然后松弛⼀次再找出最短的,所谓的松弛操作就是,遍历⼀遍看通过刚刚找到的距离最短的点作为中转站会不会更近,如果更近了就更新距离,...
经典的dijkstra's algorithm实现,很好的例子
代码 基于最短路dijkstra算法离散优化问题代码代码 基于最短路dijkstra算法离散优化问题代码代码 基于最短路dijkstra算法离散优化问题代码代码 基于最短路dijkstra算法离散优化问题代码代码 基于最短路dijkstra算法...
dijkstra算法:什么是dijkstra算法,Java和Python如何实现dijkstra算法 dijkstra算法:什么是dijkstra算法,Java和Python如何实现dijkstra算法 dijkstra算法:什么是dijkstra算法,Java和Python如何实现dijkstra算法...
Dijkstra 算法的基本原理是:从一个节点出发,遍历所有相邻节点,计算到达每个节点的最短路径,然后选择最短的路径。Dijkstra 算法的步骤是: 1. 选择起点节点 2. 遍历所有相邻节点,计算到达每个节点的最短路径 3....
在Dijkstra算法中,首先需要构造有向图的邻接矩阵,然后使用Dijkstra算法来计算从源点到所有可达顶点的最短路径。Dijkstra算法的时间复杂度为O(n^2),其中n为图中的顶点数。 Dijkstra算法的主要步骤可以分为以下几...
dijkstra算法C++实现的程序代码