艾兹赫尔·戴克斯特拉

艾兹赫尔·戴克斯特拉（Edsger Wybe Dijkstra，1930—2002）出生于荷兰鹿特丹，原先学习数学与物理，1952年进入阿姆斯特丹数学中心从事编程。他在早期计算机上面对的，不只是机器速度与存储容量，还有如何精确协调硬件、程序和运行过程。

他与 J. A. Zonneveld 合作实现 ALGOL 60 编译器，后来在埃因霍温组织研究团队，并于1972年获得图灵奖。将这些经历只写成个人算法传奇，会遗漏合作的重要性：语言实现和 THE 多道程序系统，都是在具体工程与研究群体中形成的成果。

参考：[1]

1959年的《图论中两个问题的说明》同时讨论最小生成树与最短路径，两者目标不同：前者连接全部顶点且总边长最小，后者寻找指定顶点之间总长度最小的路线。最短路径方法把已确定距离的顶点与候选顶点分开，每次选择从起点出发的暂定总距离最小者，再用它更新邻接顶点的距离。

这里比较的是整条已知路径的长度，而不是孤立地选择最短的一条边。非负边权保证已选定的最小距离不会再被经过未处理顶点的绕行缩短；允许负权时，这个保证就可能失效。算法思想与某种优先队列实现也应区别开来，后来的数据结构改进不能直接当成1959年论文已有的全部细节。

参考：[2] [1]

在《协作顺序进程》中，戴克斯特拉讨论多个进程访问共同状态的困难，并用信号量及 P、V 操作表达协调。P 在允许时把信号量减一，条件不满足时等待；V 将其加一。判断与修改必须作为不可分割的动作，否则两个进程可能都以为自己获得了同一个资源。

把二元信号量初值设为一，可以用进入前的 P 与退出后的 V 限制临界区同时只由一个进程执行。原文还讨论生产者与消费者，并明确认可 C. S. Scholten 对一般信号量应用范围的贡献。同步原语解决特定协调问题，并不意味着任意组合都会自动免于死锁或等待问题。

参考：[3]

《结构化程序设计札记》强调，人能理解的细节数量有限，程序变大后不能只把小程序的写法机械放大。抽象、分解和循环不变式，可以把推理限制在较清楚的层次；优化也应以程序仍可理解、可管理为前提。这比“去掉某个语句就有好程序”更接近他的论点。

他指出普通测试能够发现错误，却不能凭若干成功样例证明所有可能执行都正确。这不是否定测试的工程作用，而是区分举例检查与一般性论证。理解戴克斯特拉的影响，应看到算法、操作系统和证明方法共享的要求：明确问题、说明假设，并让推理过程能够被他人检查。

参考：[4]