Hoe vindt Google zo snel de goede internetpagina’s? Hoe sorteer je een lijst namen op alfabet? Hoe vind je alle priemgetallen kleiner dan een bepaald getal? Het antwoord op deze drie vragen is hetzelfde: met een algoritme. Een algoritme is een recept om een probleem stap voor stap op te lossen.
Nu werkt u waarschijnlijk niet voor Google en hoeft u ook niet zo vaak lijsten met namen te sorteren of priemgetallen te zoeken. Toch gebruikt u zelf regelmatig een algoritme. Bijvoorbeeld als u nakijkt of de rekening in een restaurant klopt. U telt de getallen bij elkaar op – in kolommen van rechts naar links. Eerst de eenheden, eventueel onthouden wat er overblijft, dan de tientallen, weer onthouden, verder met de honderdtallen en zo verder (afhankelijk van uw budget).
Getallen optellen is niet zo moeilijk, maar het is een stuk lastiger om met pen en papier uit te rekenen dat Ö5 ≈ 2.236… Ook dit gaat met een algoritme. Bijna 4000 jaar geleden kenden de Babyloniërs al zulke methoden om wortels te berekenen. Ook de Grieken (verder vooral bekend van de stelling van Pythagoras) ontwikkelden rond 200 voor Christus verschillende algoritmen.
Stap voor stap
Een mooi voorbeeld is de zeef van Eratosthenes om priemgetallen te vinden -een priemgetal is een getal dat alleen deelbaar is door 1 en zichzelf. Het is heel eenvoudig om stapsgewijs alle priemgetallen kleiner dan een bepaald getal (neem bijvoorbeeld 1729) te vinden.
1. Maak een lijst van alle gehele getallen tussen 2 en 1729.
2. Omcirkel 2 en streep alle veelvouden van 2 door: 4, 6, 8, enzovoots tot 1728.
3.Zoek het eerste getal op de lijst dat niet omcirkeld of doorgestreept is. Stop als zo’n getal niet bestaat.
4. Omcirkel dit getal en streep alle veelvouden van dit getal op de lijst door. Ga daarna terug naar stap 3.
Als het algoritme stopt, dan zijn alle getallen op de lijst omcirkeld of doorgestreept. De omcirkelde getallen zijn precies alle priemgetallen kleiner dan 1729. Alle getallen die deelbaar zijn door een of ander getal zijn immers stuk voor stuk doorgestreept.
In dit voorbeeld zien we een wonderlijke eigenschap van algoritmes: je hoeft helemaal niet te begrijpen wat je doet. Als je netjes de stappen volgt, dan komt er vanzelf het goede antwoord uit. Een kind dat niet weet wat priemgetallen zijn, maar wel tot 1729 kan tellen en vermenigvuldigen, kan met de bovenstaande methode probleemloos alle priemgetallen kleiner dan 1729 vinden.
Al-gortime
De naam algoritme is een verbastering van de naam Al-Khwarizmi. Deze Arabische wiskundige schreef in de negende eeuw een belangrijk boek over Indische getallen en wat je daar allemaal mee kon doen. Hij introduceerde hiermee ons huidige getallenstelsel in het Midden-Oosten en later Europa. Bij het vertalen van zijn werk naar het Latijn werd door een ijverige vertaler ook de naam Al-Khwarizmi meegenomen en verwesterd tot algoritmi. In de loop der tijd werd het woord algoritme een algemene term voor methoden die stap voor stap beschrijven hoe een probleem moet worden opgelost.
Het is nogal vervelend om al die stappen van een algoritme met pen en papier uit te werken. Computers zijn echter bijzonder goed in dom en mechanisch werk en de opkomst van de computer ging hand in hand met de groeiende toepassingen van algoritmen in de laatste zestig jaar. Het grappige is dat juist het nadenken over algoritmen tot onze huidige computers leidde. Natuurlijk speelden veel meer factoren een rol (denk aan de Tweede Wereldoorlog die zorgde voor een technologische spurt), maar buitengewoon belangrijk waren de ideeën van één man: Alan Turing. Deze Engelsman werd geboren in 1912 en studeerde wiskunde in Cambridge. Op zijn 23ste was hij al gepromoveerd en raakte hij geïnteresseerd in logica. Turing betwijfelde of logica wel de enige manier was om naar wiskunde te kijken en vroeg zich af of er vragen waren, die je niet met logica kon beantwoorden.
Om de grenzen van de logica te onderzoeken, bedacht Turing in 1936 zijn Turing machine, een eenvoudige computer die nog alleen in zijn hoofd bestond. Zijn meest revolutionaire idee was dat je een programma op dezelfde manier kunt opslaan als de gegevens waarmee je rekent. Wij zijn inmiddels helemaal gewend aan dit idee: op onze computers bewaren we gegevens als vakantiefoto’s en favoriete liedjes op dezelfde manier als programma’s als webbrowsers of tekstverwerkers. Alles staat als rijtjes nullen en enen op de harde schijf. Om een computer iets nieuws te laten doen, hoef je alleen nieuwe software te installeren en niet met een schroevendraaier allerlei nieuwe componenten toe te voegen. Dat hebben we aan Alan Turing te danken.
De theoretische Turing machine kan alleen algoritmes uitvoeren die aan bepaalde eisen voldoen. Het algoritme moet bestaan uit een eindig aantal precieze instructies en het moet stoppen na een eindig aantal stappen. Daarnaast moet het algoritme in principe door een persoon met pen, papier en een heleboel tijd uitgevoerd kunnen worden. Hierbij hoeft deze persoon niets te begrijpen van wat hij doet, als hij elke losse stap maar kan uitvoeren.
Onze huidige computerprogramma’s voldoen ook aan deze eisen. Turing bewees dat elke computer die op deze manier werkt precies hetzelfde kan, als hij maar genoeg tijd en geheugen heeft. Een gloednieuwe computer met een supersnelle processor kan in principe niet meer problemen oplossen dan een kamergrote computer uit de jaren vijftig.
To stop or not to stop
Turing gebruikte zijn Turing machine om de grenzen van de logica te onderzoeken: wat kan een algoritme niet? In 1936 ontdekte hij dat het onmogelijk is om een computerprogramma te maken dat van een willekeurig algoritme bepaalt of het zal stoppen. De relevantie van deze vraag is duidelijk: als je computer niet reageert, dan wil je graag weten of je even moet wachten omdat je computer nog ergens mee bezig is, of dat je maar beter opnieuw kan opstarten.
De naïeve methode om te kijken of een algoritme stopt, is om het domweg te laten draaien. Als het na een tijdje stopt, dan weet je het antwoord. Maar wat doe je als het algoritme niet stopt? Je weet nooit zeker of het algoritme over drie minuten of drie dagen of drie jaar niet toch zal stoppen. Turing liet zien dat er algoritmen bestaan waarvoor je met geen enkele slimme truc kunt bepalen of ze stoppen.
Turing maakte de opkomst van de computers trouwens niet meer mee. Hij overleed in 1954 op sprookjesachtige wijze aan een cyanide-vergifting met een half opgegeten appel naast zijn bed. Zijn moeder geloofde dat het een ongeluk was, de rest van de wereld gokte op zelfmoord.
Nog meer problemen
Turing liet zien dat we niet van elk algoritme kunnen bepalen of het stopt. Maar gelukkig zijn er een heleboel algoritmen waarvan we zeker weten dat ze stoppen, omdat er bijvoorbeeld maar een eindig aantal mogelijkheden is om na te gaan. Een logische vraag is nu: zijn deze algoritmen snel genoeg, zijn ze efficiënt? Met efficiënt wordt bedoeld dat de rekentijd niet belachelijk veel groter wordt als het probleem groter wordt.
Het antwoord hierop is een teleurstellend ‘nee’. Er bestaat een grote groep van problemen die heel eenvoudig lijken, maar waar geen efficiënt algoritme voor bestaat. Berucht is het handelsreizigersprobleem. Een handelsreiziger wil naar verschillende steden om zijn handel naar klanten te brengen. Tijd en benzine kosten geld, dus vraagt de handelsreiziger zich af wat de kortste route is waarbij hij langs al deze steden komt. Soortgelijke problemen komen op veel plaatsen voor: een bezorger van de Volkskrant zoekt de kortste route langs zijn bezorgadressen en fabrikanten van printplaten voor computers zoeken de snelste manier om duizenden gaten op de juiste plek te boren.
Het is niet moeilijk om een algoritme te geven dat in een eindig aantal stappen de kortste route vindt: probeer ze gewoon allemaal. Jammer genoeg zijn er nogal veel mogelijkheden.Voor tien steden zijn er al 362.880 mogelijke routes. Bij de gaten in de printplaat gaat het in de praktijk al snel om enorme aantallen en heeft de computer geen dagen, geen jaren, maar eeuwen nodig om de kortste route te vinden. Tegen de tijd dat het probleem opgelost is, heeft niemand de printplaat meer nodig. Voor dit soort problemen gloort er hoop in de toekomst: de quantumcomputer! Die zou ze wél snel kunnen oplossen. Maar dat is iets voor een ander lemma in deze canon.
Tekst: Ionica Smeets (1979)
Links:
De wiskunde achter het Google algoritme (Engels)
http://www.ams.org/featurecolumn/archive/pagerank.html
Artikel over Mohammad ibn Musa Al-Khwarizmi
http://www.kennislink.nl/publicaties?q=Mohammad+ibn+Musa+Al-Khwarizmi&commit=Zoekl
Site over Turing, gemaakt door zijn biograaf (Engels)
http://www.turing.org.uk/turing/
Uitleg over wat je kunt beslissen met Turing machines (Engels)
http://plato.stanford.edu/entries/church-turing/
Optimaal combineren (over het Handelsreizigersprobleem):
http://www.kennislink.nl/web/show?id=141774
Quantumcomputer
Relevante boeken
Worden in de loop van 2020-2021 toegevoegd (3 september 2020)
Homepage Bètacanon
(zaterdag 17 februari 2007)
