Algoritme

Een algoritme is een stappenplan bestaande uit een set regels in vaste volgorde om tot een oplossing te komen en het einddoel te bereiken. Het wordt ingezet als een handig hulpmiddel bij eenvoudige tot complexe problemen of situaties van het dagelijks leven en de digitale vraagstukken. Een voorbeeld is het monetair algoritme.

Algoritme om een willekeurig veelvlak in driehoeken op te delen (in het algemeen heeft dit probleem meerdere oplossingen, de bereikte oplossing hangt dus af van het gebruikte algoritme)

Het algoritme werd vroeger alleen gebruikt door wiskundigen, maar sinds de opkomst van computers wordt het vooral gerelateerd aan automatisering, terwijl het algoritme een ruimer begrip kent. Dit kreeg verhaal in 1935 door de Britse wiskundige Alan Turing met zijn bekende uitdaging en beslissingsprobleem "bestaat er een algoritme waarmee kan bewezen worden of een wiskundige bewering waar is of niet?" Vanaf toen werden de mogelijkheden en onmogelijkheden besproken tussen wiskundigen en computerprogrammeurs.

Geschiedenis

Algorismi

Blad uit een Latijnse vertaling (Cambridge manuscript), beginnend met "Dixit algorizmi"

De grondlegger van het algoritme is de Perzische wetenschapper Mohammad ibn Moesa al-Chwarizmi. Hij introduceerde in 813 het gebruik van Hindu-numerieke getallen van 0 tot 9 en ontwikkelde hiermee algebra: de systematische methodes om lineaire en kwadratische vergelijkingen op te lossen. Hierdoor wordt hij "de vader van de moderne wiskunde" genoemd en werd zijn naam gelatiniseerd naar "Algorismi", waarvan het woord algoritme is afgeleid.

Analytische machine

In 1833 kwam Charles Babbage met een concept waarbij hij een mechanische programmeerbare computer bedenkt. In 1842 zag Augusta Ada Byron King, Lady Lovelace potentieel in zijn bevinding en noteerde in haar notitieboekje een algoritme om een analytische machine wiskundige reeksen te laten maken. Dit werd nooit fysiek gebouwd maar Ada Byrons beschrijving wordt wereldwijd als het allereerste computerprogramma beschouwd. Dit is ruim honderd jaar voordat de eerste computer werd gefabriceerd.

Turingmachine

Het ontbreken van wiskundige strengheid in de definitie van een "goed gedefinieerde procedure" voor een algoritme vormde een probleem bij wiskundigen en logici van de 19e en begin 20e eeuw. Dit probleem werd grotendeels opgelost met de beschrijving van de turingmachine. Turing ontwikkelde dit apparaat omdat hij een machine wilde maken die in theorie elke mogelijke berekening kon uitvoeren met een eenvoudig model. Het was bedoeld om gegevens te lezen van een lang stuk band, waarbij gebruikt gemaakt werd van een tabel om de volgorde van gevraagde bewerkingen te bepalen. Een turingmachine wordt hedendaags gezien als de voorloper van de moderne computer met algoritmische bewerkingen.

Kunstmatige intelligentie

Alan Turing is ook een van de grondleggers van de kunstmatige intelligentie. Hij bedacht in 1936 een methode met een algoritme om te toetsen wanneer computerintelligentie niet meer te onderscheiden is van de menselijke intelligentie.

Dagelijks gebruik

Een algoritme kan in het dagelijks leven ook ingezet worden om een bepaald doel te bereiken. Voorbeeld: de vereiste stappen om een lineaire vergelijking op te lossen is een algoritme, maar de nodige stappen volgen van een recept is ook een algoritme.

Wanneer een diner wordt voorbereid is er ook een culinair algoritme nodig om dit tot een goed einde te brengen:

1. Eerst beslissen wat het eten wordt
2. boodschappen doen
3. Groenten snijden en stoven
4. Kruiden toevoegen
5. Oven aanzetten en vlees braden
6. Tafel klaarzetten
7. Het diner verorberen

Enkele abstracte voorbeelden wanneer bovenstaande algoritme niet resulteert in het gewenste resultaat:

Bij dit algoritme zal de eerste stap een bijkomende set regels invoegen voor de tweede stap. Zijn er 5 groenten gekocht dan bevat de volgende stap 5 handelingen. In deze stap hebben alle 5 groenten dezelfde set regels, dus de volgorde van snijden is niet van groot belang. Als de volgende stap een set regels is die drie soorten kruiden toevoegt, mogen de twee set regels niet met elkaar verwisseld worden. Gebeurt dit toch, dan worden er maar drie soorten groenten toegevoegd en resulteert dit in een ongewenst resultaat.

Stel dat men eerst eet, dan alle groenten gaat stoven, om daarna boodschappen te doen. Dan zal dit algoritme leiden tot een ongewenst resultaat omdat de set regels niet werd gerespecteerd.

Computer en software

Het begrip 'algoritme' wordt vaak gebruikt als deze door systemen worden uitgevoerd. doel van een computeralgoritme is een probleem op te lossen. De instructies kunnen in het algemeen omgaan met eventualiteiten (fouten, datakwaliteitsproblemen, inconsistenties, randeffecten) die bij het uitvoeren kunnen optreden. Algoritmen hebben in het algemeen stappen (sequentie) die zich kunnen herhalen (iteratie) of die beslissingen (logica of vergelijkingen) vereisen om de taak te voltooien.

Eenzelfde taak kan gewoonlijk op verschillende manieren worden opgelost. Het verschil ligt dan meestal in de hoeveelheid tijd, ruimte of inspanning die het algoritme vergt; dit kan een indicatie zijn voor de complexiteit of de efficiëntie van het algoritme. Bij het correct uitvoeren van een computerprogramma is het belangrijk dat het algoritme inderdaad de beoogde functie uitvoert en dat het algoritme goed door het computerprogramma wordt uitgevoerd. Eventuele fouten of problemen moeten hierbij worden gerapporteerd.

Formeel algoritme

Algoritmen in formele systemen zijn essentieel voor bijvoorbeeld de manier waarop computers informatie verwerken. Dit is omdat een computerprogramma een formeel algoritme is dat de computer vertelt welke specifieke stappen in een specifieke volgorde uitgevoerd moeten worden om een bepaald eindresultaat te bereiken. Een groter probleem wordt opgesplitst in meerdere deelproblemen.

In het algemeen wordt bij algoritmen informatie verwerkt; de informatie (data) wordt gelezen van een invoerapparaat en weggeschreven naar een uitvoerapparaat; de informatie kan ook bewaard worden voor later. Opgeslagen data worden bij het analyseren van algoritmen gezien als de "interne toestand" van het apparaat dat het algoritme uitvoert.

Voor elk rekenkundig proces moet een algoritme nauwkeurig gedefinieerd worden: het specificeert namelijk hoe het apparaat zal reageren op elke mogelijke invoer en interne toestand. Omdat een algoritme een exacte lijst is met exacte stappen, is de volgorde waarin de berekening gebeurt vaak (maar niet altijd) kritisch voor het correct functioneren van het algoritme. Uniek aan het concept van formele algoritmen is de toewijzing van een waarde aan een variabele. Dit komt voort uit de notie van het geheugen als werkruimte.

Computerprogramma's

Waar een algoritme de beschrijving is van een oplossing van een probleem, is een computerprogramma (in een of andere programmeertaal) de implementatie van dat algoritme. Een algoritme voor een berekening met reële getallen kan bijvoorbeeld uitgaan van exacte berekeningen, terwijl de implementatie bepaalt hoe groot de afrondfouten kunnen zijn. De nauwkeurigheid van het eindresultaat kan (bij gelijkwaardige wijze van afronden van tussenresultaten) wel van het algoritme afhangen, dus bij het ontwerp van het algoritme moet er vaak al rekening mee worden gehouden dat er in de implementatie niet exact gerekend wordt. Dit geldt overigens niet alleen bij computergebruik, maar ook bij een handberekening met tussentijdse afrondingen.

Grotere systemen en algoritmen worden opgesplitst in deelsystemen, modules, functies en statements, waarbij het ontwerp top-down of bottom-up wordt verwezenlijkt. In principe is het algoritme onafhankelijk van de fysieke implementatie op een bepaald computersysteem. Toch kan er in het ontwerp rekening (moeten) worden gehouden met een bepaalde architectuur. In dat geval worden de specifieke functies in een afzonderlijke module ondergebracht. Als het systeem moet worden vervangen blijven de wijzigingen beperkt tot een enkele module.

De verschillende manieren om tegen een probleem aan te kijken en het te beschrijven hebben in de loop van de jaren ook verschillende vormen van programmeren opgeleverd: imperatief programmeren, objectgeoriënteerd programmeren, aspectgeoriënteerd programmeren, logisch programmeren, symbolisch programmeren, functioneel programmeren.

In imperatief programmeren worden instructies expliciet opgeschreven, waarbij de berekening bovenaan begint en vervolgens stap voor stap naar beneden verloopt. Dit heet de control flow van een algoritme.

Een andere manier om tegen algoritmen aan te kijken is functioneel programmeren. In programma's van dit type worden algoritmen gezien als wiskundige functies die elkaar kunnen aanroepen. Diezelfde functies kunnen ook aan variabelen worden toegewezen en zelfs als parameter in een functieaanroep gebruikt worden.

Voorbeeld

Een voorbeeld van een algoritme is het algoritme van Euclides. Dit bepaalt de grootste gemene deler van twee positieve getallen a en b.

Het programma in pseudocode:

function ggd(a,b)
  a = abs(a);
  b = abs(b);
  if (a == 0 || b == 0) {
     return 0;
  }
  do { 
     res = a % b; 
     a = b;
     b = res;
  } while (b > 0);
return a;

Het algoritme van dit programma gaat als volgt:

• De standaard functie abs zorgt ervoor dat de variabelen a en b altijd een positief getal bevat
• Wanneer a of b de waarde 0 heeft, dan stopt het algoritme en is de uitkomst 0
• Indien a groter blijkt dan b, zal het algoritme de variabelen a en b automatisch wisselen bij de eerste iteratie via modulo
• De iteratie (een do-while-loop) start en stopt pas als de variabele b op 0 staat:
  • % berekent de modulo van deling a en b, dat het getal reduceert (bv.: 23 = 3 × 6 + restwaarde 5)
  • a wordt gelijkgesteld met b
  • b wordt gelijkgesteld met de modulo-uitkomst
  • De iteratie herhaalt zich zolang b groter is dan 0
• Als de iteratie stopt, bevat variabele a altijd de grootste gemene deler

Algoritmen in gebruik bij de overheid

Nederland

De Nederlandse overheid heeft een begin gemaakt met het opbouwen van een register van door haar gebruikte algoritmen.

Een voorbeeld (nog niet opgenomen in het register) is het algoritme om op basis van een aangifte inkomstenbelasting het bedrag van de aanslag te bepalen. Bij de online aangifte wordt dit ook min of meer voorgerekend.

Discussie en privacy

Internationaal

In haar boek Automating Inequality (“Automatisering van de ongelijkheid”) uit 2019 onderzocht Virginia Eubanks de impact van met name beleidsalgoritmen, maar ook datamining en voorspellende risicomodellen op arme mensen en mensen uit de arbeidersklasse in Amerika.

Duitsland

De Duitse ngo AlgorithmWatch publiceerde in mei 2021 richtlijnen om te vermijden dat mensen op de werkvloer het slachtoffer worden van people analytics, complexe computersystemen die met behulp van algoritmen werknemers surveilleren, evalueren, aansturen en zelfs promoten of ontslaan. Met name Amazon was in 2019 hiermee in het nieuws gekomen.

Verenigde Staten

In de Verenigde Staten getuigde Frances Haugen in 2021 voor de Senaat aan de hand van de Facebook files dat de algoritmen van Facebook systematisch berichten tonen die reactie opleveren en polariseren, en dus meer platformtijd en winst opleveren.

Nederland

In Nederland waarschuwden critici al in 2018 voor een "algocratie" in de openbare ruimte, waarbij algoritmen een smart city gaan besturen.

Toepassingen

Sorteren

• Bubblesort
• Insertion sort
• Mergesort
• Quicksort
• Radix sort
• Sorteeralgoritme
• Straight selection sort

Optimalisatie

• Genetische algoritmen
• Optimalisatiealgoritme
• Simulated annealing
• Tabu search

Converteren

• Coderen en decoderen (zie ook: codec)
• Compressie
• Decryptie
• Encryptie

Gerelateerde onderwerpen

• Algoritme van Lamport
• Complexiteitstheorie
• Computer
• Grafentheorie
• Lambdacalculus
• Online-algoritme
• Turingmachine

Bronnen, noten en/of referenties

Bibliografische informatie

• Biblioteca Nacional de España: XX527980
• Bibliothèque nationale de France: cb119358199 (data)
• Gemeinsame Normdatei: 4001183-5
• Library of Congress Control Number: sh85003487
• Nationale Bibliotheek van Letland: 000052282
• Bibliotheek van het Japanse parlement: 00560337
• Nationale Bibliotheek van Tsjechië: ph114026
• Nationale Bibliotheek van Israël: 987007293927505171

Mediabestanden

Zie de categorie Algorithms van Wikimedia Commons voor mediabestanden over dit onderwerp.