Sector
  • Havo bovenbouw
  • Vwo bovenbouw
Vakgebied
  • Informatica
Leerplankundig thema
  • Schoolexamen
  • Handreiking

Subdomein B1: Algoritmen

12-2-2018

​​​​​​​​​​​​Een ​​​al​goritme​​ is een serie acties (of instructies) en beslissingen met een bepaald doel. De uitvoerder van deze instructies hoeft geen computer te zijn, maar kan ook een mens zijn. Zo zou je een partituur kunnen zien als algoritme voor een muziekstuk en een recept als een algoritme voor een gerecht. Beide worden uitgevoerd door een mens. Basisbouwstenen voor algoritmen zijn opeenvolging, keuze en herhaling. Als een algoritme zichzelf aanroept, dan he​​et dat​​ recursie.

​ ​

Hieronder staat een voorbeeldalgoritme om te bepalen hoe vaak een bepaald woord in een gegeven tekst voorkomt.

flowchart.png                                 

 

Figuur 1: Voorbeeld van een algoritme dat telt hoe vaak een woord in een tekst voorkomt

Over het voorbeeld:

  • Het algoritme begint met een opeenvolging van instructies, stap 1, 2 en 3. Het algoritme doet hier altijd hetzelfde; onafhankelijk van de omstandigheden.
  • Stap 4a tot en met 4d zijn onderdeel van een herhaling: zij worden meerdere malen uitgevoerd. Het aantal herhalingen hangt in dit voorbeeld af van het aantal woorden in de tekst, maar kan in het algemeen ook een van tevoren bepaald aantal zijn.
  • Zowel stap 4a als 4c zijn keuzen: afhankelijk van de omstandigheden wordt gekozen welke volgende stap wordt doorlopen.
  • ​​​Het algoritme is weergegeven als een flowchart, met instructies in blokken en pijlen tussen de blokken die de opeenvolging aangeven. In dit flowchart komen drie symbolen voor uit de norm ISO 5807:1985. Een algoritme kan ook in pseudocode worden weergegeven: herhalings- en keuzestructuren worden dan in woorden beschreven die doen denken aan een programmeertaal, bijvoorbeeld "ZOLANG voorwaarde geldt, voer instructies uit.
    Uit onderzoek (….) blijkt dat flowcharts didactische voordelen hebben. Bovendien is het in het geval van pseudocode nodig om afspraken te maken over de formulering van instructies, terwijl de blokken in de flowcharts teksten kunnen bevatten op een willekeurig niveau van abstractie (een concrete handeling of een complexere taak). Dit maakt flowcharts ruimer inzetbaar: zowel voor globaal ontwerp als voor weergave van gedetailleerde instructies.
  • In de flowchart worden enkele objecten aangeduid met een gekozen naam (gegeven tekst, aantal voorkomens). Zulke benoemde objecten​ in een algoritme zien we in een programma meestal terug als variabelen.​

Correctheid

Een algoritme​ is correct als bij iedere invoer de 'juiste' uitvoer oplevert. De bedoeling van een algoritme (de beoogde relatie tussen in- en uitvoer) kan worden uitgedrukt door een combinatie van aannamen over de invoer (ook wel precondities genoemd) en eigenschappen van de uitvoer (postconditie). Bijvoorbeeld: "als de invoer een niet-lege rij van gehele getallen is, dan is de uitvoer het gemiddelde van de getallen in die rij."

De correctheid van een algoritme kan op verschillende manieren aannemelijk worden gemaakt of zelfs bewezen. Dat laatste valt buiten het bereik van het examenprogramma. Testen is een veelgebruikte manier om de correctheid te onderzoeken (door fouten op te sporen), maar met testen is ongeschikt om de correctheid van een programma waterdicht aan te tonen. ​

Efficiëntie

Net als programma's kunnen algoritmen onderling vergeleken worden aan de hand van de (verwachte) rekentijd bij gegeven invoer. Meestal heeft een sneller ("efficiënter") algoritme de voorkeur. Een alternatief voor het hierboven beschreven algoritme is om de tekst eerst woord voor woord op te slaan om deze daarna pas te doorzoeken. Alle woorden worden dan twee keer gelezen en het algoritme is dus langer bezig. Dit nieuwe algoritme is nog steeds correct, maar minder efficiënt dan het voorbeeldalgoritme

De rekentijd kan in absolute zin worden beschouwd, maar interessanter is het om te kijken naar de rekentijd in relatie tot de grootte van de invoer, ook wel de complexiteit van een algoritme of programma genoemd. Welk effect heeft een verdubbeling van de invoer op de rekentijd, bijvoorbeeld? Hierop gaat het keuzethema G dieper in.​​