狄克斯特拉

狄克斯特拉1930年5月11日生於荷蘭鹿特丹的一個知識分子家庭，在兄弟姊妹4人中排行第三。他的父親是一名化學家和發明家，曾擔任荷蘭化學會主席。他母親則是一位數學家。他成功地設計並實現了在有障礙物的兩個地點之間找出一條最短路徑的高效算法，這個算法被命名為“狄克斯特拉算法”，解決了機器人學中的一個十分關鍵的問題，即運動路徑規劃問題，至今仍被廣泛套用，被認為是利用“貪心法”(greedy method，也稱greedy algorithm)設計算法的一個成功範例。

基本介紹

• 中文名：埃德斯加·狄克斯特拉
• 外文名：Edsger Wybe Dijkstra
• 國籍：荷蘭
• 出生地：荷蘭鹿特丹
• 出生日期：1930年5月11日
• 逝世日期：2002年8月6日
• 職業：計算機科學家
• 畢業院校：萊頓大學 劍橋大學
• 主要成就：設計了狄克斯特拉算法
• 代表作品：《Algol 60程式設計入門》《程式設計方法》

簡介

埃德斯加·狄克斯特拉

——最先察覺“goto有害”的計算機科學大師

首屆計算機先驅獎獲得者中有一位荷蘭的計算機科學家埃德斯加·狄克斯特拉(Edsgar Wybe Dijkstra)。狄克斯特拉因最早指出“goto是有害的”以及首創結構化程式設計而聞名於世。事實上，他對計算機科學的貢獻並不僅僅限於程式設計技術。在算法和算法理論、編譯器、作業系統諸多方面，狄克斯特拉都有許多創造，作出了傑出貢獻。1983年，ACM為紀念Communications of ACM創刊25周年，評選出從1958—1982年的四分之一個世紀中在該雜誌上發表的25篇有里程碑意義的論文，每年一篇，狄克斯特拉一人就有兩篇入選，是僅有的這樣的兩位學者之一(另一位是英國學者C．A．R．Hoare，也是計算機先驅獎獲得者)。

人生成就

狄克斯特拉1930年5月11日生於荷蘭鹿特丹的一個知識分子家庭，在兄弟姊妹4人中排行第三。他的父親是一名化學家和發明家，曾擔任荷蘭化學會主席。他母親則是一位數學家。

狄克斯特拉的少年時代是在德國法西斯占領軍的鐵蹄下度過的。由於食物短缺，他被送到鄉下他父親的一個朋友那裡去。納粹德國投降後，1945年7月，十分虛弱的狄克斯特拉才和家人重新團聚。狄克斯特拉原打算學法律，畢業後到聯合國工作，為維護世界和平服務。但他中學畢業時，數理化成績都特別好，因此他父親說服了他，1948年進萊頓大學學習數學與物理。在學習理論物理的過程中，狄克斯特拉發現這個領域中的許多問題都需要進行大量複雜的計算，於是決定學習計算機編程。1951年，他自費赴英國參加了劍橋大學舉辦的一個程式設計培訓班，學習在EDSAC(Electronic Delay Storage Automatic Calculator，這是由另一位首屆計算機先驅獎獲得者威爾克斯主持設計與開發的世界上第一台存儲程式式電子計算機)上的編程方法，這使他成為世界上第一批程式設計師之一。第二年，阿姆斯特丹數學中心了解到這一情況，擬聘他為兼職程式設計師。狄克斯特拉開始時有些猶豫，因為世界上當時還沒有“程式設計師”這一職業。數學中心的計算部主任、Algol語言的設計者之一、荷蘭的計算技術先驅維京格爾藤(A．van Wijingaarden，1916—1987，因在設計Algol 68時，為解決上下文有關性這一難題而提出了一種具有很強描述能力的新的文法，稱做二級文法又稱W文法而聞名。他是1986年計算機先驅獎獲得者之一，也曾對另一位首屆計算機先驅獎獲得者N．Wirth的研究產生過影響)對他說，目前程式設計雖然還沒有成為學科，不被重視，但既然計算機已經有了，正處於開創階段，你未來就有可能使程式設計成為一個受人尊敬的學科。這段話說動了狄克斯特拉，使他接受了這個職位，而且越乾越有興趣，這樣，他在第二年就結束了在萊頓大學的學業，成為數學中心全日制的工作人員，從此進入計算機領域，並且正如維京格爾藤所預言的那樣，逐漸成為該領域的知名專家，創造出了許許多多的“第一”。

1956年，他成功地設計並實現了在有障礙物的兩個地點之間找出一條最短路徑的高效算法，這個算法被命名為“狄克斯特拉算法”，解決了機器人學中的一個十分關鍵的問題，即運動路徑規劃問題，至今仍被廣泛套用，被認為是利用“貪心法”(greedy method)設計算法的一個成功範例。

1959年，在數學中心將他們原先的ARMAC計算機進行升級的過程中，狄克斯特拉設計了一種處理程式，成功地解決了“實時中斷”（real-time interrupt)問題。狄克斯特拉的博士論文就是以此為課題完成的，並在阿姆斯特丹大學通過論文答辯而獲得博士學位。

1960年8月，Algol 60文本推出剛剛半年多，狄克斯特拉和他在數學中心的同事仲納凡爾特(J．A．Zonneveld)一起就率先實現了世界上第一個Algol 60編譯器，比歐美其他各國學者實現Algol 60早一年還多。這一成就引起各國計算機學者的驚嘆，並因此奠定了狄克斯特拉作為世界一流計算機學者在科學界的地位。

1962年，狄克斯特拉離開數學中心進入位於荷蘭南部的艾恩德大學(Eindhoven Technical University)任數學教授。在這裡，X8計算機的開發，設計與實現了具有多道程式運行能力統——THE Multiprogramming System。THE是艾恩德霍芬技荷蘭文Technische Hoogeschool Eindhoven的詞頭縮寫。狄克THE這個系統中所提出的一系列方法和技術奠定了計算作系統的基礎，尤其是關於多層體系結構、順序進程之間的斥機制這樣一些重要的思想和概念都是狄克斯特拉在THE中首先提出並為以後的作業系統如UNIX等所採用的。為了在單處理機的情況下確定進程(process)能否占有處理機，狄克斯特拉將每個進程分為“就緒”(ready)、“運行”(running)和“阻塞”(blocking)三個工作狀態。由於在任一時刻最多只有一個進程可以使用處理機，正占用著處理機的進程稱為“運行”進程。當某進程已具備了使用處理機的條件，而當前又沒有處理機供其使用，則使該進程處於“就緒”狀態，當運行進程由於某種原因無法繼續運行下去時，就停止其占用處理機，使之進入“阻塞’’狀態，待造成其退出運行的條件解除，再進入“就緒”狀態。而對系統中所有同時運行的進程之間所存在的相互制約的同步(synchronization，指為了避免錯誤，在一個進程訪問共享數據時，另一個進程不訪問該數據)和互斥(mutually-exclusive，指兩個進程不能同時在一個臨界區中使用同一個可重複使用的資源，諸如讀寫緩衝區)兩個關係，狄克斯特拉巧妙地利用火車運行控制系統中的“信號燈”(semaphore，或叫“信號量”)概念加以解決。所謂信號燈，實際上就是用來控制進程狀態的一個代表某一資源的存儲單元。例如，P1和P2是分別將數據送入緩衝B和從緩衝B讀出數據的兩個進程，為了防止這兩個進程並發時產生錯誤，狄克斯特拉設計了一種同步機制叫"PV操作”，P操作和V操作是執行時不被打斷的兩個作業系統原語。執行P操作P(S)時信號量S的值減1，若結果不為負則P(S)執行完畢，否則執行P操作的進程暫停以等待釋放。執行V操作V(S)時，S的值加1，若結果不大於0則釋放一個因執行P(S)而等待的進程。對P1和凹可定義兩個信號量S1和S2，初值分別為1和0。進程P1在向緩衝B送人數據前執行P操作P(S1)，在送人數據後執行V操作V(S2)。進程P2在從緩衝B讀取數據前先執行P操作P(S2)，在讀出數據後執行V操作V(S1)。當P1往緩衝B送入一數據後信號量S1之值變為0，在該數據讀出後S1之值才又變為1，因此在前驅數未讀出前後續數不會送入，從而保證了P1和P2之間的同步。我國讀者常常不明白這一同步機制為什麼稱做PV操作，原來這是狄克斯特拉用荷蘭文定義的，因為在荷蘭文中，通過叫passeren，釋放叫，VRIJGEVEN，PV操作因此得名。這是在計算機術語中不用英語表達的極少數的例子之一。

案例之一

通過基於Dijkstra算法思想上提出一套快速評估車間動態生產能力的方法,該方法在確保訂單不延遲的情況下,能夠有效合理地安排生產過程。通過對車間工序建立數學模型,套用改進的算法對所有訂單進行評估,確定所有訂單每道工序的最早完成時間和最遲發生時間,從而實現對生產能力動態評估。本算法適用於嚴格按訂單組織生產的企業,企業可以利用該算法對訂單進行評估,確定是否可以接受訂單。

狄克斯特拉

論著及著作

狄克斯特拉所提出的最弱前置條件的概念及相應的程式設計演算，使得程式的設計和程式的驗證可同時進行，具有十分重要的理論意義和實際價值，極大地促進了程式設計作為科學的進程。

狄克斯特拉於1984年結束了寶來公司自由研究員的生活，應邀出任位於奧斯汀的德克薩斯大學計算機科學系名譽主任。

狄克斯特拉論著極多，主要有：

《Algol 60程式設計入門》(A Primer of Algol 60 Programming, Academic Pr.，1962)

《程式設計的訓練方法》(ADiscipline of Programming, Prentice-Hall，1976)

《程式設計的教學就是思維方法的教學》(TheTeaching of Programming i. e. the Teaching of Thinking，Springer，1976)

《關於計算的論著選集：個人的觀點》(SelectedWriting on Computing：A Personal Perspective，Springer，1982。本書是從他發給寶來公司的大量通信中選出最重要、最有意義的60餘件通信材料編纂而成的，集中反映了他那個時期的觀點和研究成果)

《程式設計方法》(A Method ofProgramming，Addison- Wesley，1988)

《程式與證明的形式開發》(FormalDevelopment of Programs and Proofs，Addison-Wesley，1990)

《謂詞演算與程式語義》(PredicateCalculus and Program Semantics，Springer，1990)

除了獲得圖靈獎外，狄克斯特拉還在1974年獲得AFIPS的HarryGoode獎。

狄克斯特拉是在1972年8月14日于波士頓召開的ACM年會上接受圖靈獎的。他發表了題為“智力低下的程式設計師”(The Humble Programmer)的圖靈獎演說，刊於Communications of ACM ，1973年10月，859-866頁。也可見《前20年的ACM圖靈獎演說集》(ACM Turing Award Lectutes——TheFirst 20 Years：1966-1985，ACM Pr. ),17-32頁。演說中他肯定了Fortran ,Algol, LISP等語言，而對於PL/I，他認為是失敗的。演說的重點是如何建立可靠的軟體，如何在編程時就盡力避免引入錯誤，而不是以後再去消除錯誤，這不單具有技術上的意義，而且在經濟上是十分重要的。狄克斯特拉的上述觀點贏得了愈來愈多的人的理解與支持。

1994年在講課

1989年，為了慶祝狄克斯特拉60壽辰，由著名計算機學者、狄克斯特拉的長期合作者費京 (W. H. J. Feijin)等聯合編纂了一本紀念性文集，書名引用了狄克斯特拉的另一句名言：《完美是我們的追求》（Beauty is Our Business，Springer，1990）。書中包括他的同事、朋友、學生們寫的53篇文章，其中有4點陣圖靈獎獲得者，即霍爾(C. A. R. Hoare，1980)、克努特（D. Knuth，1974）、沃思（N. Wirth，1984）和伯努利（A. Pnueli，1996）。有趣的是，克努特在1966年曾經對狄克斯特拉“並發程式控制中一個問題的解決”一文中所提出的方案進行批評，認為該方案有可能使特定進程“餓死”，即永遠被阻塞而無法獲得所需資源。他提出了一種“不會餓死”的方案。但有評論指出，克努特的方案比狄克斯特拉的方案更加複雜而未見得更加可靠。顯然，學術上的爭論並不妨礙這兩位大師級的計算機科學家成為好朋友。

在與癌症進行了多年的鬥爭之後，狄克斯特拉於2002年8月6日在荷蘭Nuenen自己的家中逝世。

2002年的照片