Wiskundemeisjes

Ionica & Jeanine
 
Slik Internetbureau Rotterdam Internetbureau Rotterdam



Categorieën

Archief

Ode aan Dijkstra


In Geschiedenis,Quotes, door Ionica

Zoals onlangs beloofd: iets meer over Edsger W. Dijkstra. Deze column verscheen eerder in Technisch Weekblad, vakblad voor hogeropgeleide technici en bèta's.

Vijftig jaar geleden publiceerde Edsger Dijkstra zijn kortstepadalgoritme. Daarom een kleine ode aan de in 2002 overleden Dijkstra, iemand waar we als Nederlanders best wat trotser op mogen zijn. Dijkstra was een van de eerste programmeurs van Nederland. Toen hij in 1957 trouwde, werd het beroep computerprogrammeur door de burgerlijke stand nog niet erkend en uiteindelijk gaf hij maar `theoretische natuurkundige’ op.

Zijn beroemdste resultaat is het kortstepadalgoritme, dat de kortste verbinding vindt tussen twee knopen in een graaf (een verzameling punten waarvan sommigen verbonden zijn). Denk bijvoorbeeld aan het vinden van de kortste route tussen twee steden. Het slimme van Dijkstra’s algoritme is dat het niet alle mogelijke routes met elkaar vergelijkt, maar dat het stap voor stap de kortst mogelijke afstanden tot elk punt opbouwt. In de eerste stap kijk je naar alle punten die vanaf het beginpunt te bereiken zijn en markeer je al die punten met de afstand tot het beginpunt. Daarna kijk je steeds vanaf het punt dat op dat moment de kortste afstand heeft tot het beginpunt naar alle punten die je vanaf daar kunt bereiken. Als je een buurpunt via een nieuwe verbinding op een snellere manier kunt bereiken, schrijf je de nieuwe, kortere afstand tot het beginpunt bij zo’n punt. Zo ga je steeds een stukje verder tot je alle punten hebt gehad en je de kortste route tot het eindpunt hebt gevonden.

dijkstra

Als je het algoritme even op een servetje probeert, dan is is het zo eenvoudig dat je je afvraagt waarom je het niet zelf hebt bedacht. Dijkstra vond het zelf ook een beetje gek dat zijn naam en faam voor een groot deel gebaseerd waren op een algoritme dat hij bedacht als demonstratie voor een computer. Hij bedacht het kortstepadalgoritme zonder pen of papier op een zonnig terras terwijl hij met zijn vrouw een kopje koffie dronk.


dijkstra

Dijkstra verzon nog veel meer dan dit algoritme en hij had ook sterke visie op wat informatica zou moeten zijn. Honderden brieven, essays en andere handgeschreven teksten van Dijkstra staan op internet (E. W. Dijkstra Archive). Elke tekst heeft de code EWD (van Edsger W. Dijkstra) en een nummer, EWD1213 is bijvoorbeeld een inleiding bij een cursus analyse. De manier waarop hij zijn studenten daarin toespreekt, is prachtig:

It is not my purpose to "transfer knowledge" to you that, subsequently, you can forget again. My purpose is no less than to effectuate in each of you a noticeable, irreversable change. [...] I mean, if 10 years from now, when you are doing something quick and dirty, you suddenly visualize that I am looking over your shoulders and say to yourself “Dijkstra would not have liked this.”, well, that would be enough immortality for me.

Zou het hem ooit gelukt zijn dit te bereiken bij zijn studenten? De komende weken zal ik in elk geval schuldbewust aan Dijkstra denken als ik een lompe brute-force-oplossing gebruik.

8 reacties op “Ode aan Dijkstra”

  1. Bart:

    Leuke documantaire over deze man en zijn werkwijze: http://noorderlicht.vpro.nl/afleveringen/3502225/ (vooral leuk voor informatici waarschijnlijk).

  2. Christian:

    Na het lezen van zijn tirade tegen goto's heb ik inderdaad een obsessie voor 'nette' programmacode ontwikkeld...

  3. jan van rongen:

    Ja, ik had een leerling van hem kunnen zijn (als ik in Eindhoven in plaats van in Leiden was gaan studeren). Maar ook van een afstand was zijn invloed op mijn generatie van informatici toen groot. Aantonen dat een algoritme correct is, dat is wat ik van hem heb geleerd (zie o.a. "A Discipline of Programming"). En dat is veel meer dan alleen maar "nette code zonder goto's".

    In dat licht is het kortstepadalgoritme een speelgoedalgoritme vergeleken met de algoritmen voor samenwerkende processen (P en V semaphoren) en voor garbage collectie die hij ook heeft ontwikkeld.

  4. johan volkers:

    Eind jaren zestig werkte ik bij Electrologica, de firma die de EL X8 fabriceerde waarop prof. Dijkstra het fameuze THE-systeem ontwikkeld heeft (met de P en V semaphoren).
    Omdat hij toen als adviseur bij Electrologica betrokken was, heb ik het genoegen gehad (en dat is geen beleefheidsfrase) een paar keer een lezing van hem bij te mogen wonen.
    Wat mij vooral bijgebleven is zijn de sprekende voorbeelden die hij gebruikte: twee koks in één keuken om het principe van het vermijden van dodelijke omarmingen te illustreren en een kapsalon voor samenwerkende producer/consumerprocessen.

  5. Wim:

    @Christian Heb je een linkje naar Dijkstra's tirade tegen het GoTo-statement?

  6. Speicus:

    "A case against the GO TO statement" staat op:
    http://www.cs.utexas.edu/users/EWD/ewd02xx/EWD215.PDF

    Maar lees vooral ook:
    "On a somewhat disappointing correspondence"
    http://www.cs.utexas.edu/users/EWD/ewd10xx/EWD1009.PDF

    De transcripties staan op
    http://www.cs.utexas.edu/users/EWD/transcriptions/EWD02xx/EWD215.html
    en
    http://www.cs.utexas.edu/users/EWD/transcriptions/EWD10xx/EWD1009.html

  7. EJee:

    Mooi ook hoe zijn invloed verspreid werd. Het document NN832 "inleiding programmeren" heb ik in vrijwel dezelfde periode in vrijwel dezelfde vorm op college in Groningen gehad als "klein en correct programmeren". Ongetwijfeld zal onze versie een aangepaste versie geweest zijn maar in essentie is de inhoud gelijk. Zelfs na meer dan 25 jaar herken ik het meteen aan notatie, layout en verwijzingen.

    Zelfs zijn handschrift was door mijn docenten overgenomen. (Dit is nog uit de tijd van voor de tekstverwerker.) En ik herken er ook mijn eigen handschrift uit die periode in terug.

  8. Het zit er weer op | Frank's Persoonlijke Grid:

    […] vlak voor de Kerst zijn stressvol: wie doet het met wie, wanneer en waarom. We hebben welhaast Edsger Dijkstra met zijn kortste pad algoritme nodig om mijn reis door die binaire jungle succesvol te […]

Plaats een reactie


Je kunt LaTeX gebruiken in je reactie.
Gelieve antwoorden op puzzels tussen [SPOILER] en [/SPOILER] te plaatsen.