7. Algoritmen, moeilijke dingen gemakkelijk maken

Hoe vindt Google zo snel de goede internetpagina’s? Hoe sorteert een computer 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 v5 ˜ 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 natuurlijke getal groter dan 1 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 vanaf 2 tot en met 1729.

2. Omcirkel 2 en streep alle veelvouden van 2 door: 4, 6, 8, enzovoorts 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 ander getal dan 1 of zichzelf 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.

Dit algoritme voor het berekenen van priemgetallen kan nog aanzienlijk verbeterd worden. Zodra de eerste deler groter wordt dan de vierkantswortel van het grensgetal (1729), zal het resultaat van de deling kleiner zijn dan die deler. Alle samengestelde getallen groter dan de vierkantswortel zij dus al afgestreept, en alle niet afgestreepte getallen zijn priem. In het voorbeeld kan het algoritme dus stoppen bij 43

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

Klik voor de hele bus !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. 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. Wel veronderstelt de Turing machine een oneindige hoeveelheid werkgeheugen, waardoor een volledige Turing machine nooit in werkelijkheid kan bestaan.

Turing bewees dat er geen machine bestaat die meer berekeningen uit kan voeren dan zijn Turing machine. Een gloednieuwe computer met een supersnelle processor kan in principe niet meer problemen oplossen dan een kamergrote computer uit de jaren vijftig, al zal de laatste er waarschijnlijk wel veel meer tijd voor nodig hebben.

Een belangrijke variatie op de Turing machine werd bedacht door John von Neumann, een uit Hongarije afkomstige wiskundige en tijdgenoot van Turing. Hij bedacht dat het niet nodig is om onderscheid te maken tussen een programma en het werkgeheugen, maar dat de instructies van het programma in het geheugen gecodeerd kunnen worden. Hierdoor is maar één soort geheugen nodig, dat zowel gegevens als programma's opslaat. Alle moderne computers zijn volgens deze Von Neumann architectuur ontworpen. 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 zoals 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.

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 181.440 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.
Bij het handelsreizigerprobleem voor grotere aantallen steden wordt vaak gebruik gemaakt van benaderingsalgoritmen die wel in korte tijd tot bruikbare resultaten komen. Zelfs als een exacte oplossing nodig is wordt eerst een zo goed mogelijke benadering gemaakt, omdat dan veel eerder kan worden besloten dat een voorgestelde route geen verbetering meer kan opleveren.

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/web/show?id=116543

Optimaal combineren (over het Handelsreizigersprobleem):
http://www.kennislink.nl/web/show?id=141774

Quantumcomputer
http://www.natuurkunde.nl/artikelen/view.do?supportId=692020