Wat een algoritme is

De methode om de grootste gemeenschappelijke deler te vinden uit Boek VII van de Elementen van Euclides, ongeveer 2300 jaar geleden geschreven, werkt nog steeds in computers.

Een methode die altijd werkt

Stel dat je het grootste getal nodig hebt dat zowel 1071 als 462 deelt. Je kunt elk getal van 462 terug tot 1 proberen en stoppen bij het eerste dat beide deelt. Dat werkt, maar kan honderden pogingen kosten. Er is een kortere weg. Deel 1071 door 462 en bewaar de rest, 147. Deel nu 462 door 147 en bewaar de rest, 21. Deel 147 door 21: de rest is 0, dus het antwoord is 21. Drie delingen in plaats van enkele honderden.

Die kortere weg is een algoritme: een eindige lijst nauwkeurige stappen die invoer krijgt en de juiste uitvoer oplevert. Dit is het algoritme van Euclides voor de grootste gemeenschappelijke deler, uit Boek VII van de Elementen, geschreven rond 300 v.Chr. Euclides beschreef het met herhaald aftrekken van lengten in plaats van delen, maar het idee is hetzelfde. Programma's gebruiken tegenwoordig de versie met resten.

function gcd(a, b) {
  while (b !== 0) {
    const r = a % b;   // remainder
    a = b;
    b = r;
  }
  return a;
}
console.log(gcd(1071, 462)); // 21

Wat een lijst stappen tot algoritme maakt

Leerboeken zoals dat van Cormen, Leiserson, Rivest en Stein beschrijven een algoritme als een goed gedefinieerde procedure die invoer omzet in uitvoer. In die beschrijving zitten drie dingen, die elk van belang zijn wanneer je code schrijft.

• Nauwkeurig. Elke stap betekent één ding. ‘Deel a door b en bewaar de rest’ is nauwkeurig; ‘maak de getallen op de een of andere manier kleiner’ niet.
• Eindig. Het moet stoppen. In het algoritme van Euclides is de rest altijd kleiner dan het getal waardoor je deelde, dus hij krimpt elke ronde en moet 0 bereiken.
• Correct. Voor elke toegestane invoer is de uitvoer het juiste antwoord, niet alleen voor de voorbeelden die je probeerde.

Een recept wordt vaak als alledaags voorbeeld gegeven en dat is terecht: ingrediënten zijn de invoer, het gerecht is de uitvoer en de stappen staan op volgorde. Het verschil is hoeveel de lezer zelf invult. Een kok beslist wat ‘een snufje’ betekent. Een computer beslist niets, en daarom worden algoritmen voor computers met elke stap uitgeschreven.

Hetzelfde probleem, verschillende algoritmen

Voor één probleem bestaan meestal veel correcte algoritmen, die enorm kunnen verschillen in de hoeveelheid werk. Voor de grootste gemeenschappelijke deler van 1071 en 462 kost elk getal vanaf 462 omlaag proberen 442 pogingen tot je 21 bereikt, terwijl de methode van Euclides 3 delingen nodig heeft. Beide zijn correct. Slechts één is snel. In een groot deel van deze cursus bekijk je die tweede vraag: als een methode correct is, hoeveel stappen kost zij en hoe groeit dat aantal als de invoer groter wordt?

Om dat te beantwoorden tellen informatici basisstappen (een vergelijking, een verwisseling, een deling) in plaats van seconden. Seconden hangen af van de machine. Het aantal stappen hangt alleen af van het algoritme en de invoer, zodat je twee methoden eerlijk kunt vergelijken. In het lab hieronder tel je vergelijkingen terwijl je een rij balken sorteert. Probeer dezelfde beginvolgorde met twee verschillende methoden en bekijk de tellers.

Invoer, uitvoer en de stappen ertussen

Schrijf vóór het algoritme precies op wat erin gaat en wat eruit moet komen. Voor de grootste gemeenschappelijke deler: de invoer is twee positieve gehele getallen en de uitvoer één geheel getal dat beide deelt, zonder dat een groter getal dat ook doet. Die beschrijving vertelt hoe je het resultaat test en geeft vaak aanwijzingen voor de stappen. Ze onthult ook randgevallen: wat als één getal 0 is? (De lus hierboven geeft het andere getal terug, het juiste antwoord.) Wat als beide getallen gelijk zijn? Door vóór de uitvoering over randgevallen na te denken vind je veel fouten.