Wiskundemeisjes

Ode aan Dijkstra

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.

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 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.