Articles

Hoe zijn we hier gekomen? Het verhaal van algoritmen.

Tot voor kort waren algoritmen het domein van computerwetenschappers. Maar nu zijn ze ons leven binnengedrongen en worden ze alomtegenwoordig. Algoritme is geen vreemd woord meer. Algoritmische handel, algoritmische vooringenomenheid, het Facebook-algoritme, zelfs algoritmische oorlogsvoering – al deze termen zijn de afgelopen jaren deel gaan uitmaken van ons vocabulaire. Sommige mensen gaan zelfs zover te beweren dat we in een nieuw tijdperk leven: het tijdperk van het algoritme. Maar zo nieuw zijn de algoritmen niet. We gebruiken ze, bewust of onbewust, al honderden en duizenden jaren. Algoritmen zijn niet meer dan specifieke beschrijvingen van stapsgewijze handelingen die moeten gebeuren om een bepaald resultaat te bereiken. Ze zijn een van de meest gebruikte instrumenten om kennis te delen.

Praktisch gezien maakt elk proces om iemand te leren hoe hij iets moet doen gebruik van algoritmen.

Een aantal aspecten van algoritmen is de afgelopen decennia echter veranderd. Met name de introductie van computers heeft ertoe geleid dat veel algoritmen tegenwoordig veel complexer zijn dan we ons in het verleden ooit hadden kunnen voorstellen. Hoe zijn de algoritmen geëvolueerd zodat ze vandaag zo veel gesofisticeerder zijn dan in het verleden? Laten we eens kort naar hun geschiedenis kijken.

Algoritmen die menselijke handelingen begeleiden

Een postzegel uitgegeven op 6 september 1983 in de Sovjet-Unie, ter herdenking van de (bij benadering) 1200ste geboortedag van al-Khwārizmī; via Wikimedia Commons

De term algoritme is afgeleid van de naam van Muhammad ibn Mūsā al’Khwārizmī, een negende-eeuwse Perzische wiskundige. Zijn gelatiniseerde naam, Algoritmi, betekende “het decimale getallenstelsel” en werd eeuwenlang in deze betekenis gebruikt. Het moderne begrip algoritme ontstond in het Engels in de negentiende eeuw, en werd meer algemeen gebruikt sinds de jaren 1950, naar aanleiding van de opkomst van de eerste commercieel verkrijgbare computers.

Lang voordat algoritmen hun moderne naam kregen, werden ze echter al algemeen gemaakt en gebruikt.

De eerste algoritmen werden in het Oude Griekenland op papier vastgelegd. Geleerden als Nicomachus van Gerasa of Euclides creëerden toen de bouwstenen van de moderne wiskunde. Om het begrip en de toepasbaarheid van hun ideeën te vergemakkelijken, drukten zij veel ervan uit als stap-voor-stap handelingen.

Nicomachus van Gerasa introduceerde de Zeef van Eratosthenes. De Zeef wordt tot op de dag van vandaag gebruikt door studenten die leren efficiënte computercode te schrijven. Hij hielp het proces van het identificeren van priemgetallen te vereenvoudigen. Priemgetallen zijn natuurlijke getallen, groter dan één, die niet kunnen worden gevormd door vermenigvuldiging van twee kleinere natuurlijke getallen. Vier is bijvoorbeeld geen priemgetal omdat het kan worden gevormd door vermenigvuldiging van twee met twee. Vijf daarentegen is een priemgetal, omdat geen enkel natuurlijk getal kleiner dan vijf kan worden vermenigvuldigd om vijf te vormen. Hoewel het niet al te moeilijk is om de eerste paar priemgetallen te identificeren (bijvoorbeeld 2, 3, 5, 7, 11, 13, 17, 19, 23 en 29), kost het vinden van grote priemgetallen veel tijd. En grote priemgetallen zijn essentieel in de cryptografie. De Zeef van Eratosthenes geeft stap voor stap instructies om snel alle niet-priemgetallen uit een gedefinieerde verzameling getallen (bijvoorbeeld tussen 1 en 10.000) te verwijderen tot alleen nog priemgetallen overblijven. Vandaag zijn er talrijke algoritmen beschikbaar die de taak om dergelijke getallen te identificeren vereenvoudigen. De Zeef van Eratosthenes heeft een hele familie algoritmen op gang gebracht die hetzelfde doel hebben en steeds beter worden (sneller, of minder stappen vereisen) in het opsporen van priemgetallen.

Zeef van Eratosthenes door SKopp op de Duitse Wikipedia

Euclides, de andere hierboven genoemde geleerde, tegenwoordig veel bekender dan Nicomachus, introduceerde een algoritme voor het bepalen van de grootste gemene deler van twee getallen. Nogmaals, niet altijd een gemakkelijke taak, maar essentieel in veel situaties. Het algoritme van Euclides hielp om deze berekening gemakkelijk te maken. Waarom is het algoritme van Euclides nuttig? Stel je voor dat je een kamer hebt met de exacte afmetingen van 612 bij 2006 centimeter die een nieuwe vloer nodig heeft. Het algoritme van Euclides helpt je om de grootte van de grootste vierkante tegels te vinden die de vloer netjes zouden bedekken. Het antwoord, gegeven door het algoritme, is 34 cm bij 34 cm, wat resulteert in een indeling van 18 bij 59 tegels. Natuurlijk zal elke tegelzetter u vertellen dat het antwoord fout is en dat u geen idee hebt waar u mee bezig bent omdat het algoritme geen rekening houdt met de voegbreedte en daar geen ruimte voor laat. Vrees niet: ook dit kan worden berekend, en netjes uitgedrukt als een algoritme.

Algoritmen die machinehandelingen begeleiden

In de honderden jaren die volgden, werden nog veel meer algoritmen bedacht en op papier vastgelegd. Ze werden vervolgens door individuen gebruikt en stap voor stap gevolgd. Het eerste algoritme dat bedoeld was om op een machine te worden uitgevoerd, werd gemaakt door Ada Lovelace (geboren Byron) en gepubliceerd in 1843.

Ada Byron, vier jaar oud. Binnenkort zal ze ’s werelds eerste computerprogrammeur worden. Door artiest: Alfred, Comte d’Orsay. Digitale afbeelding; Somerville College, Oxford – Somerville College, Oxford, Publiek Domein, https://commons.wikimedia.org/w/index.php?curid=44246375

Ada was een intrigerend personage. Ze werd in 1815 geboren als enig wettig kind van de dichter Lord Byron. Ze ontwikkelde grote talenten in wiskunde. En aangezien de liefde voor poëzie duidelijk in haar genen zat, slaagde zij er op de een of andere manier in om zowel de liefde voor wetenschap als voor poëzie te ontwikkelen en in evenwicht te brengen. Ada omschreef haar denkwijze zelf als “poëtische wetenschap”. Als bekwaam wiskundige leerde ze Charles Babbage kennen, die vaak “de vader van de computers” wordt genoemd, dankzij zijn uitvindingen. Beiden ontwikkelden een werkrelatie en een vriendschap. Ada was zeer geïnteresseerd in een van Charles’ ontwerpen – de Analytical Engine.

Een schema voor de Analytical Engine. Door ArnoldReinhold – Eigen werk, CC BY 4.0, https://commons.wikimedia.org/w/index.php?curid=69497631

De Analytical Engine was een mechanische computer – een machine die berekeningen automatiseerde. Het was de Analytical Engine waarvoor zij het eerste algoritme schreef. Haar werk was een formule die liet zien hoe de Engine geconfigureerd kon worden om een bepaalde complexe reeks getallen, Bernoulli getallen genoemd, te berekenen. De formule wordt nu algemeen erkend als het eerste computeralgoritme in de geschiedenis.

Ada beperkte zich niet alleen tot zuiver wiskundige berekeningen. Aangezien ze in de negentiende eeuw leefde, was ze een echte visionair.

Terwijl veel van haar tijdgenoten de eerste mechanische computers in de eerste plaats zagen als cijferaars, vroeg zij zich af wat er verder ging dan het uitvoeren van berekeningen. Ze was nieuwsgierig naar het bredere potentieel van mechanische computers als hulpmiddelen om samen te werken. Ze hoopte computers te zien die mensen veel meer mogelijkheden zouden geven dan alleen door het automatiseren van berekeningen.

Lovelace’s diagram uit “note G”, het eerste gepubliceerde computeralgoritme, door Ada Lovelace – http://www.sophiararebooks.com/pictures/3544a.jpg, Publiek domein, https://commons.wikimedia.org/w/index.php?curid=37285970

Helaas was de constructie van de Analytical Engine niet voltooid voor Ada’s dood, en heeft zij haar algoritme dus nooit in actie kunnen zien. Helaas is de Analytical Engine tot op de dag van vandaag niet gebouwd. Een ander ontwerp van Charles Babbage, de Difference Engine №2, werd pas in 1991 door het London Science Museum gebouwd. Aangetoond werd dat de machine functioneel was, gebruik makend van materialen en technologieën die Charles Babbage tot zijn beschikking had. Het lijkt erop dat Babbage gewoon pech had om zijn ontwerpen gebouwd te krijgen. Elders bestaan andere gedeeltelijke implementaties van Charles’ werk, maar helaas kunnen we Ada Byrons algoritme niet op een echte Analytical Engine uitvoeren.

De negentiende eeuw werd een tijdperk van “in machines ingebedde algoritmen”.

Er waren er genoeg, waarmee allerlei menselijke handelingen werden geautomatiseerd. Als u een ingewikkeld patroon op een stuk stof wilde, had Joseph Marie Jacquard, een Franse wever en koopman, een oplossing voor u: het jacquardweefgetouw. Dankzij dit weefgetouw konden stoffenfabrikanten verfijnde patronen vervaardigen met behulp van een reeks geperforeerde kaarten die het weefgetouw instrueerden hoe het moest weven. Op een vergelijkbare manier maakten de vroege telefooncentrales gebruik van geavanceerde mechanische apparaten om telefoongesprekken te verbinden. Zij volgden automatisch stap voor stap instructies om uiteindelijk twee mensen met elkaar te laten praten. Deze machines, of het nu weefgetouwen of telefooncentrales waren, waren baanbrekend in hun tijd, en zijn tot op de dag van vandaag indrukwekkend. Het is moeilijk om het niveau van de ingewikkeldheid van sommige van deze machines niet te bewonderen. Toch waren al deze apparaten nog zuiver mechanisch. Ze bestonden uit hefbomen, schakelaars, assen. Ze maakten veel lawaai. En ze stonden heel ver af van wat we tegenwoordig computers noemen.

Algoritmen op computers voor algemeen gebruik

Pas in de jaren dertig van de vorige eeuw zagen we de eerste vermeldingen van algoritmen in elektronische (niet-mechanische) computers. Alan Turing was een van de eerste wetenschappers die formeel vastlegde hoe individuen berekeningen uitvoerden. Het doel van Turing was om een algemeen proces vast te leggen, in plaats van een specifiek proces voor een bepaalde taak zoals het identificeren van priemgetallen of het berekenen van de grootste gemene deler. Het algemene proces kon dan worden gebruikt om specifieke taken uit te voeren. Turing’s conceptuele werk leidde tot de ontwikkeling van wat nu bekend staat als de Turing Machine. De Turing Machine, op zijn beurt, leidde tot de opkomst van computers voor algemene doeleinden. Het voorvoegsel “algemeen” is hier essentieel. In tegenstelling tot eerdere machines, konden de nieuwe computers willekeurige reeksen instructies uitvoeren. Zij konden worden gebruikt voor doeleinden die zelfs door hun scheppers niet waren voorspeld. Met andere woorden: Turing’s werk leidde tot de ontwikkeling van computers waarop we toepassingen kunnen installeren en uitvoeren.

Geen Flappy Bird op je smartphone zonder het concept van een Turing-machine.

Decennia later zijn algoritmen uiterst verfijnd geworden. Zo geavanceerd zelfs, dat het vaak onmogelijk is uit te leggen hoe ze werken. In de twintigste eeuw dachten velen liever over computeralgoritmen als zwarte dozen. Je hoefde niet te begrijpen hoe ze precies werkten. Het enige waar je om gaf waren de inputs – wat de zwarte doos in ging – en de outputs – wat eruit kwam. Deze vereenvoudiging was een keuze. In de eenentwintigste eeuw is dit voor sommige algoritmen geen keuze meer: mensen kunnen niet precies uitleggen hoe algoritmen tot bepaalde resultaten komen, en dus zijn we gedwongen over deze algoritmen te denken als zwarte, of misschien magische, dozen. Een groep van dergelijke algoritmen zijn sommige van de kunstmatige intelligentie-algoritmen. Wij kunnen hun principes verklaren. Wij kunnen bijvoorbeeld zeggen dat een algoritme gebruik maakt van een kunstmatig neuraal netwerk. We kunnen ook uitleggen hoe het netwerk tot stand is gekomen, en hoe de input tot een bepaalde output heeft geleid. Wat we echter niet kunnen verklaren, is waarom dit specifieke resultaat de output van het algoritme was, afgezien van een zuiver mechanische verklaring. Eric L. Loomis, wiens duur van de opsluiting afhing van een algoritme, probeerde te begrijpen waarom het COMPAS-algoritme hem als een hoog-risico crimineel beoordeelde. Dat was gewoon onmogelijk. De complexiteit van algoritmen is vaak overweldigend. En dit is nog maar het begin.

We leven in een wereld waar algoritmen overal zijn – niet alleen op papier of in onze gedachten, maar ook bij het besturen van machines, computers en robots.

Ze zijn klein, alomtegenwoordig en – althans in sommige gevallen – onverklaarbaar.

Een meer formele definitie van een algoritme is “een ondubbelzinnige specificatie van hoe een klasse van problemen moet worden opgelost” of “een op zichzelf staande stapsgewijze reeks uit te voeren bewerkingen”

www.oed.com/view/Entry/4959

In oktober 2018 is het grootst bekende priemgetal 277.232.917- 1, een getal met 23.249.425 cijfers. Alleen al het controleren of dit ene getal priem is, kostte zes dagen non-stop rekenwerk op een hedendaagse thuiscomputer. (https://www.mersenne.org/primes/press/M77232917.html)