Edsger Dijkstra

El Vikipedio, la libera enciklopedio
Saltu al: navigado, serĉo
Edsger Dijkstra

Edsger Wybe DIJKSTRA (naskiĝis la 11-an de majo 1930 en Roterdamo – mortis la 6-an de aŭgusto 2002 en Nuenen (Nederlando); IPA: [ˈɛtˌŝər ˈdɛɪkˌstra]) estis influhava nederlanda komputosciencisto. En 1972 li ricevis la premion Turing por fundamentaj kontribuoj kampe de programlingvoj.

Dijkstra estis filo de kemiisto kaj matematikistino. Li studis matematikon kaj teorian fizikon je la universitato en Leiden. De 1952 ĝis 1962 li laboris en la matematika centro (hodiaŭ Centrum voor Wiskunde en Informatica) en Amsterdamo. Poste li estis matematika profesoro je la teknika universitato en Eindhoven. En 1984 li ŝanĝis al la Schlumberger Centennial Chair in Computer Sciences je la Universitato de Teksaso ĉe Aŭstino. De 1973 ĝis 1984 li estis ankaŭ studisto de la Burroughs Corporation. En 1999 Dijkstra emeritiĝis. Li mortis en 2002 pro kancero.

Dijkstra interalie kontribuis al komputiko per la algoritmo de Dijkstra por la kalkulado de la plej mallonga vojo en grafeo, la unua uzo de semaforoj, kaj traktato pri la GOTO-ordono kaj kial oni ne uzu ĝin. Li enkondukis la terminon strukturema programado en la komputikon.

Scienca Kontribuo[redakti | redakti fonton]

Algoritma Verko[redakti | redakti fonton]

Algoritmaj verkoj de Dijkstra (interalie grafeaj algoritmoj, kunkura kaj disaj algoritmoj) rolas grave en diversaj fakoj en komputoscienco. Laŭ Leslie Lamport (2002), Dijkstra "fondis la kampon de kunkuraj kaj disaj algoritmoj" per sia CACM publikaĵo en 1965 "Solution of a Problem in Concurrent Programming Control" (Solvo al problemo en kunkura programa regado), en kiu li unue difinis kaj solvis la problemo de inter-ekskluzivigo.

En 1959 Dijkstra publikigis tri-paĝan artikolon, "Noto pri du problemoj de grafeoj" ("A note on two problems in connexion with graphs"), kiu donis algoritmon por kalkuli la plej mallongan vojon en grafeo inter ĉiuj du verticoj Nun oni nomas ĝin la algoritmo de Dijkstra. Dijkstra ekpripensi la problemon dum li laboris ĉe la matematika centro en Amsterdamo en 1956 kiel programisto, cele montri la kapablon de nova komputilo, ARMAC. Li volis elekti problemon kune kun solvon (kalkulotan de la komputilo), kiun nefakulo ankaŭ povus kompreni. Li inventis la algoritmon en ĉirkaŭ 20 minutoj sen skribi kaj poste plenumis ĝin je ARMAC por ete simpligita grafeo kun 64 nederlandaj urboj (por ke 6 bitoj sufiĉus reprezenti ĉiujn urbojn en la problemo).

Post unu jaro, aparato-inĝeniero donis al li problemon dum labori pri la sekva komputilo de la instituto: minimumigi nombron da ligilon ligitajn najlojn sur la malantaŭa surfaco de la komputilo. Li re-malkovris la algoritmon de Prim kiel solvo al la problemo. La algoritmon unue malkovris en 1930 ĉeĥa matematikisto Vojtěch Jarník[1] kaj poste sendepende re-malkovris kaj re-publikigis en 1957 Robert C. Prim[2] kaj en 1959 Dijkstra[3]. Tial, oni ankaŭ nomas ĝin la DJP-algoritmo.[4]

En 1961 Dijkstra unue priskribis la ekspedista algoritmo, metodo por analizi matematikan formalon skribitan per intermeta operaciskribo. Ĝi povas eldoni rezulton en inversa pola notaciosintakso-arbo. La algoritmon oni nomas la "ekspedista algoritmo" ĉar ĝia operacio similas al ekspedisto por fervojo.

En 1962 aŭ 1963 Dijkstra proponis uzon de semaforoj por ekskluzivigi inter n ruloj (kiel ĝeneraligo de algoritmo de Dekker). Li ankaŭ malkovris mortoblokadon kaj proponis la bankistan algoritmon kiel solvo.

En mez-1970-oj, Dijkstra (kune kun aliaj aŭtoroj) enkondukis utilan abstraktadon por studo de senrubigilo.

En la frua 1980-oj Dijkstra kaj Carel S. Scholten proponis la algoritmo de Dijkstra–Scholten por malkovri finiĝo en disaj sistemoj.

En1981 Dijkstra disvolvigis smoothsort, speco de piramida ordigo, bazita sur komparado.

EWD-oj[redakti | redakti fonton]

Estis fama kutimo de Dijkstra zorge manskribi tekston per sia plumo. La sekvo da manskribaĵoj nomiĝas "EWD"-oj, ĉar Dijkstra mem antaŭmetis iliajn numerojn per sia nomo-mallongigo. Dijkstra distribuis EWD-kopiaĵojn inter siaj kolegoj, kaj poste ili disvastiĝis plusende interne de la sciencista komunumo. Ili enhavis leterojn, raportojn pri vojaĝojn, kaj prelegojn; la temo estis komputado kaj matematiko. Li skribadis dum 40 jaroj. La EWD-teskto estis apenaŭ pli longa ol 15 paĝoj. La lastan EWD-on, la 1318-an, li publikigis je 2002, Aprilo 14-a.

Oni jam skanis kaj publikigis pli ol 1300 EWD-oj ĉe la Arkivejo de E. W. Dijkstra fare de la Universitato de Teksaso ĉe Aŭstino.[5]

Persona vivo[redakti | redakti fonton]

Dijkstra vivis tre modestan, eĉ spartan, vivostilon. Li kaj lia edzino vivis en simpla, malgranda kaj modesta domo en Nuenen. Li ne havis televidilon, videoaparaton, aŭ poŝtelefonon, kaj ne iras kinen[6]. Kontraste, li bone ludis pianon kaj, dum lia profesorado en Aŭstino, ŝatis viziti klasikan koncerton. Lia plej ŝatita muzikisto estis Mozart.[7]

Publikaĵoj[redakti | redakti fonton]

Libroj[redakti | redakti fonton]

  • Dijkstra, Edsger W.: A Primer of ALGOL 60 Programming: Together with Report on the Algorithmic Language ALGOL 60. (New York: Academic Press, 1962)
  • Dijkstra, Edsger W.: A Discipline of Programming. (Prentice Hall, 1976, 217pp)
  • Dijkstra, Edsger W.: Selected Writings on Computing: A Personal Perspective (Monographs in Computer Science). (Springer, 1982, 362pp)
  • Dijkstra, Edsger W.; Feijen, W. H. J.; Sterringa, Joke: A Method of Programming. (Addison-Wesley, 1988, 198pp)
  • Dijkstra, Edsger W.; Scholten, Carel S.: Predicate Calculus and Program Semantics (Texts and Monographs in Computer Science). New York: Springer-Verlag, 1990, 220pp

Gravaj artikoloj[redakti | redakti fonton]

  • Dijkstra, Edsger W. (1962). "Some Meditations on Advanced Programming," Proc. IFIP Congress, North-Holland, Amsterdam, pp. 535–538.
  • Dijkstra, Edsger W. (1965). Cooperating Sequential Processes (Technische Hogeschool Eindhoven). Reprinted in F. Genuys (ed.), Programming Languages, Academic Press, Orlando, Florida, 1968, pp. 43–112
  • Dijkstra, Edsger W. (1965). "Solution of a Problem in Concurrent Programming Control". Communications of the ACM 8 (9): 569.
  • Dijkstra, Edsger W. (1965). "Programming Considered as a Human Activity," Proc. IFIP Congress, pp. 213–217.
  • Dijkstra, Edsger W. (1968). Letters to the editor: Go To Statement Considered Harmful. Commun. ACM 11(3): 147-148
  • Dijkstra, Edsger W. (1968). A Constructive Approach to the Problem of Program Correctness. BIT Numerical Mathematics 8(1968): pp. 174–186.
  • Dijkstra, Edsger W. (1968). "The Structure of the 'THE'-Multiprogramming System," ACM Symp. on Operating Systems, Comm. ACM, Vol. 11, No. 5, May 1968, pp. 341–346.
  • Dijkstra, Edsger W. (1971). A Short Introduction to the Art of Computer Programming. (Technische Hogeschool, Eindhoven)
  • Dijkstra, Edsger W. (1971). Hierarchical Ordering of Sequential Processes. Acta Inf. 1: 115-138
  • Dijkstra, Edsger W. (1972). The Humble Programmer. Communications of the ACM 15(10): pp. 859-866.
  • Dijkstra, Edsger W. (1972). Notes on Structured Programming, in Structured Programming, by O.-J. Dahl, E. W. Dijkstra, and C. A. R. Hoare, New York: Academic Press
  • Dijkstra, Edsger W. (1974). Programming as a Discipline of Mathematical Nature. American Mathematical Monthly 81(JuneJuly): pp. 608-612.
  • Dijkstra, Edsger W. (1974). On the role of scientific thought (EWD447). (E.W. Dijkstra Archive, Center for American History, University of Texas at Austin)
  • Dijkstra, Edsger W. (1974). Self-stabilizing Systems in Spite of Distributed Control. Commun. ACM 17(11): 643-644
  • Dijkstra, Edsger W. (1975). How do we tell truths that might hurt?. In Dijkstra, Edsger W. (1982): "Selected Writings on Computing: A Personal Perspective": pp. 129-131.
  • Dijkstra, Edsger W. (1975). Craftsman or Scientist. ACM Pacific 1975: 217-223
  • Dijkstra, Edsger W. (1975). On the teaching of programming, i. e. on the teaching of thinking. Language Hierarchies and Interfaces 1975: 1-10
  • Dijkstra, Edsger W. (1977). Programming: From Craft to Scientific Discipline. International Computing Symposium 1977: 23-30
  • Dijkstra, Edsger W. (1978). On the Interplay between Mathematics and Programming. Program Construction 1978: 35-46
  • Dijkstra, Edsger W. (1975). Correctness Concerns And, Among Other Things, Why They Are Resented. (ACM) Proceedings of the international conference on Reliable software. April 21–23, 1975, Los Angeles, California, USA: pp. 546-550.
  • Dijkstra, Edsger W. (1975). Guarded Commands, Nondeterminacy and Formal Derivation of Programs. Commun. ACM 18(8): 453-457
  • Dijkstra, Edsger W. (1978). Finding the Correctness Proof of a Concurrent Program. Program Construction 1978: 24-34
  • Dijkstra, Edsger W. (1984). The threats to computing science (EWD898). (E.W. Dijkstra Archive, Center for American History, University of Texas at Austin)
  • Dijkstra, Edsger W. (1986). On a Cultural Gap. The Mathematical Intelligencer 8(1): pp. 48-52.
  • Dijkstra, Edsger W. (1987). Mathematicians and Computing Scientists: The Cultural Gap. Abacus 4(4): pp. 26-31.
  • Dijkstra, Edsger W. (1989). On the Cruelty of Really Teaching Computer Science. Communications of the ACM 32(12): pp.1398-1404.
  • Dijkstra, Edsger W. (1999). Computing Science: Achievements and Challenges. ACM SIGAPP Applied Computing Review 7(2): pp. 2-9.
  • Dijkstra, Edsger W. (2001). The End of Computing Science?. Communications of the ACM 44(3): pp. 92.
  • Dijkstra, Edsger W. (2001). "What led to Notes on Structured Programming". (E.W. Dijkstra Archive, Center for American History, University of Texas at Austin)

Eksteraj ligiloj[redakti | redakti fonton]

Literaturo[redakti | redakti fonton]

  1. Jarník, V. (1930), "O jistém problému minimálním" (in Czech), Práce Moravské Přírodovědecké Společnosti 6: 57–63, http://dml.cz/dmlcz/500726 .
  2. Prim, R. C. (November 1957), "Shortest connection networks And some generalizations", Bell System Technical Journal 36 (6): 1389–1401, doi:10.1002/j.1538-7305.1957.tb01515.x .
  3. Dijkstra, E. W. (1959), "A note on two problems in connexion with graphs", Numerische Mathematik 1: 269–271, doi:10.1007/BF01386390, http://www-m3.ma.tum.de/twiki/pub/MN0506/WebHome/dijkstra.pdf .
  4. Pettie, Seth; Ramachandran, Vijaya (2002), "An optimal minimum spanning tree algorithm", Journal of the ACM 49 (1): 16–34, doi:10.1145/505241.505243 .
  5. Arkivejo de E. W. Dijkstra, Universitato de Teksaso, http://www.cs.utexas.edu/users/EWD/ .
  6. Apt, Krzysztof R. (2002)
  7. Dijkstra biography (July 2008). Arkivita el la originalo je 11 October 2013. Alirita 18 January 2014.