Domein B: Grondslagen

Algoritmen en complexiteit#

Basisexamenblad-nl

Groei van complexiteitsklassen

Afb. 1Afb. 1 — Hoe het aantal stappen groeit met de invoergrootte n. Hoe hoger de klasse in de rangorde, hoe steiler de kromme stijgt.

Een algoritme is een eindige, ondubbelzinnige en uitvoerbare beschrijving van de stappen die een probleem oplossen. 'Eindig' betekent dat het na een begrensd aantal stappen stopt met een antwoord; 'ondubbelzinnig' dat elke stap maar op één manier gelezen kan worden, zodat twee mensen (of computers) precies hetzelfde doen; en 'uitvoerbaar' dat elke stap concreet genoeg is om echt uit te voeren. In de informatica formuleren we ze los van een programmeertaal — vaak in pseudocode of een stroomdiagram — zodat we eerst over de méthode kunnen nadenken en pas daarna over de code. Een goed algoritme is bovendien correct (het geeft altijd het juiste antwoord) en het liefst efficiënt (het doet dat met zo min mogelijk werk).

Zoeken is het schoolvoorbeeld waaraan je efficiëntie leert. Lineair zoeken loopt de rij van voor naar achter af en vergelijkt elk element met de gezochte waarde; in het slechtste geval — het element staat achteraan of ontbreekt — kost dat n vergelijkingen bij n elementen. We noteren dat als

O(n)

: het werk groeit evenredig met de invoergrootte. Binair zoeken is veel slimmer, maar stelt één eis: de rij moet gesorteerd zijn. Je kijkt naar het middelste element; is dat te groot, dan ligt de gezochte waarde links en gooi je de hele rechterhelft weg, en omgekeerd. Elke vergelijking halveert zo het aantal overgebleven kandidaten. Dat halveren kun je hooguit

\log_2 n

keer doen, dus binair zoeken is

O(\log n)

.

Om algoritmen eerlijk te vergelijken tellen we niet de seconden — die hangen van de computer af — maar het aantal elementaire stappen als functie van de invoergrootte n. De grote-O-notatie vat die groei samen en gooit bewust details weg: constanten en langzamere termen tellen niet mee, want bij grote n bepaalt de snelst groeiende term het plaatje. Een algoritme dat

3n + 50

stappen doet is gewoon

O(n)

, en

2n^2 + 100n

is

O(n^2)

, omdat

n^2

uiteindelijk over

100n

heen groeit. Grote-O zegt dus iets over de vórm van de groei, niet over de precieze snelheid: het is een bovengrens die beschrijft hoe hard het werk oploopt als je probleem groter wordt. Juist dat maakt het zo bruikbaar om te voorspellen of een aanpak bij grote invoer nog werkbaar blijft.

De belangrijkste complexiteitsklassen vormen een vaste rangorde, van zuinig naar onbetaalbaar:

O(1)

(constant — even veel werk, ongeacht n, zoals het opvragen van een array-element via zijn index),

O(\log n)

(logaritmisch — halveren, zoals binair zoeken),

O(n)

(lineair — alles één keer langslopen),

O(n \log n)

(de snelheid van goede sorteeralgoritmen),

O(n^2)

(kwadratisch — geneste lussen, zoals eenvoudige sorteringen) en

O(2^n)

(exponentieel — bijvoorbeeld alle deelverzamelingen proberen). Afbeelding 1 laat zien hoe dramatisch die klassen uiteenlopen; Afbeelding 2 zet er getallen bij. Het verschil is enorm: bij

n = 1000

doet een

O(n)

-aanpak duizend stappen,

O(n^2)

er een miljoen, en

O(2^n)

zoveel dat geen computer ter wereld het ooit afmaakt.

Ten slotte moet je altijd zeggen wélk geval je bedoelt. Het best-case is het gunstigste scenario (bij lineair zoeken: het element staat vooraan, één stap), het worst-case het ongunstigste (het staat achteraan of ontbreekt, n stappen) en het average-case het gemiddelde over alle mogelijke invoeren. In de praktijk en bij het schoolexamen kijken we meestal naar het worst-case, omdat dat een gegarandeerde bovengrens geeft: je weet dan zeker dat het nooit erger wordt. Voor binair zoeken is het worst-case

O(\log n)

, voor lineair zoeken

O(n)

— en juist omdat het worst-case telt, loont het om je gegevens eerst te sorteren als je er daarna vaak in gaat zoeken.

T(n) = O\bigl(f(n)\bigr)

Grote-O-notatie

$T(n)$ is het aantal stappen bij invoergrootte $n$ ; $O(f(n))$ geeft een bovengrens op de groei, waarbij constanten en lagere termen wegvallen.

O(1) < O(\log n) < O(n) < O(n \log n) < O(n^2) < O(2^n)

Rangorde van de complexiteitsklassen

Voor grote $n$ groeit elke klasse sneller dan de vorige; deze volgorde bepaalt welke aanpak bij grote invoer nog haalbaar is.

\lceil \log_2 1000 \rceil = 10

Binair zoeken in 1000 elementen

Je kunt 1000 elementen hooguit tien keer halveren, dus binair zoeken doet maximaal 10 vergelijkingen.

Big-O in getallen

Afb. 2Afb. 2 — Dezelfde klassen in getallen: bij n = 1000 loopt O(n^2) al in de miljoenen en is O(2^n) onhaalbaar.

Uitgewerkt voorbeeld

Hoeveel stappen doet binair zoeken in 1000 elementen?

Een gesorteerde lijst bevat 1000 elementen. Bepaal het maximale aantal vergelijkingen dat binair zoeken nodig heeft en vergelijk dat met lineair zoeken.

Wat doet één stap?
Binair zoeken vergelijkt de gezochte waarde met het middelste element en gooit daarna de helft van de kandidaten weg. Elke vergelijking halveert dus het zoekgebied.
Tel de halveringen
Van 1000 blijven achtereenvolgens over: 500, 250, 125, 63, 32, 16, 8, 4, 2, 1. Na tien halveringen is er nog één element over.
$1000 \to 500 \to 250 \to \dots \to 1$
Reken met de logaritme
Het aantal halveringen is naar boven afgerond de tweelog van 1000.
$\lceil \log_2 1000 \rceil = \lceil 9{,}97 \rceil = 10$
Vergelijk met lineair zoeken
Lineair zoeken doet in het slechtste geval 1000 vergelijkingen ( $O(n)$ ); binair zoeken maar 10 ( $O(\log n)$ ) — honderd keer minder werk, mits de lijst gesorteerd is.

Resultaat: Binair zoeken heeft maximaal 10 vergelijkingen nodig, tegen 1000 voor lineair zoeken.

Veelgemaakte fouten

Binair zoeken toepassen op een ongesorteerde rij — dan klopt het halveren niet en mis je de waarde.
Constanten en lagere-orde termen laten meetellen in de grote-O ( $3n^2$ is gewoon $O(n^2)$ ).
$O(\log n)$ en $O(n \log n)$ door elkaar halen, of denken dat 'sneller' altijd 'minder code' betekent.

Actieve herhaling

Een gesorteerde lijst bevat 1.000.000 namen. Bepaal hoeveel vergelijkingen lineair zoeken en binair zoeken in het slechtste geval nodig hebben, en leg met de grote-O-notatie uit waarom het verschil zo groot is.

Actief ophalen

Haal de kernpunten op — onthul ze daarna.

Bronnen: Examenprogramma informatica (HAVO) (CvTE / Examenblad)

Sorteeralgoritmen#

Standaardexamenblad-nl

Bubble sort, pass voor pass

Afb. 3Afb. 3 — Bubble sort op [5, 1, 4, 2, 8]: na elke pass staat het volgende grootste element vast (de gemarkeerde 5 is in pass 1 al bijna naar achteren geborreld). Na pass 3 verandert er niets meer.

Sorteren — een rij op volgorde zetten — is misschien wel de meest bestudeerde taak in de informatica, omdat het overal opduikt (denk aan zoekresultaten, ranglijsten en het feit dat binair zoeken een gesorteerde rij nodig heeft). De drie klassieke 'eenvoudige' sorteeralgoritmen die je op de HAVO moet kunnen naspelen zijn bubble sort, insertion sort en selection sort. Ze zijn niet de snelste, maar wel makkelijk te begrijpen en juist daardoor ideaal om te leren hoe je een algoritme stap voor stap analyseert. Alle drie werken met geneste herhaling: een buitenste lus die meerdere keren over de rij gaat en een binnenste lus die telkens paren of posities vergelijkt.

Bubble sort ('bellen sorteren') vergelijkt telkens twee buurelementen en verwisselt ze als ze in de verkeerde volgorde staan. In één pass loop je zo van links naar rechts; het grootste element 'borrelt' daarbij vanzelf naar de laatste plaats. Daarna herhaal je het spel op het overgebleven, één korter stuk. Neem de rij [5, 2, 4, 1]. Eerste pass: 5 en 2 wisselen → [2,5,4,1]; 5 en 4 wisselen → [2,4,5,1]; 5 en 1 wisselen → [2,4,1,5]. De 5 staat nu goed. Tweede pass op [2,4,1]: 2 en 4 blijven, 4 en 1 wisselen → [2,1,4,5]. Derde pass: 2 en 1 wisselen → [1,2,4,5]. Klaar. Slim detail: eindigt een pass zónder enkele wissel, dan is de rij al gesorteerd en mag je stoppen.

Insertion sort ('invoegen') bouwt links een gesorteerd deel op en schuift elk volgend element net zo lang naar links tot het op de goede plek zit — precies zoals je speelkaarten in je hand ordent. Selection sort ('selecteren') doet het andersom: het zoekt in het onsorteerde deel telkens het kleinste element en zet dat vooraan, waardoor het gesorteerde deel vanaf links groeit. Voor [5,2,4,1] pikt selection sort eerst de 1 (kleinste) en verwisselt die met de 5 → [1,2,4,5] (hier meteen bijna klaar); insertion sort neemt de 2 en schuift die vóór de 5, dan de 4 tussen 2 en 5, en ten slotte de 1 helemaal naar voren. De drie algoritmen komen bij dezelfde rij op hetzelfde eindresultaat uit, maar verschillen in het aantal wissels en vergelijkingen dat ze onderweg doen.

Waarom zijn deze drie

O(n^2)

? Bekijk selection sort: voor het eerste vak vergelijk je met alle overige n − 1 elementen om de kleinste te vinden, voor het tweede met n − 2, dan n − 3, enzovoort. In totaal

(n-1)+(n-2)+\dots+1 = \tfrac{n(n-1)}{2}

vergelijkingen — een uitdrukking waarin de

n^2

-term domineert, dus

O(n^2)

. Bubble en insertion sort tellen in het slechtste geval evenveel: bij n elementen ongeveer

n^2/2

vergelijkingen. Dat betekent dat het werk vierkant oploopt: verdubbel je de rij, dan wordt het ongeveer vier keer zo veel werk. Voor een handjevol getallen is dat prima, maar voor een miljoen elementen zijn deze algoritmen hopeloos traag vergeleken met de

O(n \log n)

-sorteringen (zoals merge sort en quicksort) die je later tegenkomt.

Twee begrippen scheiden de algoritmen verder. Het aantal vergelijkingen en het aantal wissels zijn aparte maten: selection sort doet weinig wissels (hooguit n − 1) maar altijd veel vergelijkingen, terwijl bubble sort juist veel kan wisselen. Stabiliteit betekent dat gelijke elementen hun onderlinge volgorde behouden — handig als je bijvoorbeeld eerst op voornaam en dan op achternaam sorteert. Bubble sort en insertion sort zijn van nature stabiel (ze wisselen nooit twee gelijke elementen), selection sort is dat in zijn eenvoudige vorm niet. Bij het schoolexamen wordt vooral gevraagd of je een algoritme correct kunt naspelen, het aantal wissels of vergelijkingen kunt tellen, en kunt uitleggen waarom de complexiteit

O(n^2)

is.

(n-1) + (n-2) + \dots + 1 = \frac{n(n-1)}{2}

Aantal vergelijkingen bij selection sort

De som van de vergelijkingen per ronde; de $n^2$ -term overheerst, dus de complexiteit is $O(n^2)$ .

O(n^2)

Complexiteit van bubble, insertion en selection sort

Twee geneste lussen over $n$ elementen geven een kwadratisch aantal stappen: bij dubbele invoer ongeveer vier keer zo veel werk.

Uitgewerkt voorbeeld

Bubble sort naspelen en de wissels tellen

Speel bubble sort volledig na op de rij [5, 1, 4, 2, 8] en tel het totale aantal wissels.

Pass 1
Vergelijk steeds twee buren: (5,1) wissel → [1,5,4,2,8]; (5,4) wissel → [1,4,5,2,8]; (5,2) wissel → [1,4,2,5,8]; (5,8) geen wissel. Drie wissels; de 8 stond al achteraan.
$[5,\,1,\,4,\,2,\,8] \to [1,\,4,\,2,\,5,\,8]$
Pass 2
(1,4) geen wissel; (4,2) wissel → [1,2,4,5,8]; (4,5) geen wissel. Eén wissel deze ronde.
$[1,\,4,\,2,\,5,\,8] \to [1,\,2,\,4,\,5,\,8]$
Pass 3
(1,2) en (2,4) geven geen wissel. Nul wissels: dat is het teken dat de rij gesorteerd is, dus we stoppen.
Tel de wissels
Tel de wissels van alle passes op. Dat komt overeen met het aantal 'inversies' (paren die verkeerd om staan) in de beginrij.
$3 + 1 + 0 = 4$

Resultaat: De gesorteerde rij is [1, 2, 4, 5, 8], bereikt met 4 wissels.

Veelgemaakte fouten

Bij bubble sort vergeten dat na elke pass het achterste (grootste) element al vaststaat, en dat deel toch opnieuw vergelijken.
Wissels en vergelijkingen door elkaar halen bij het tellen.
Denken dat korte, 'nette' code automatisch snel is — deze algoritmen ogen simpel maar zijn $O(n^2)$ .

Actieve herhaling

Speel bubble sort volledig na op de rij [3, 6, 1, 5, 2]. Schrijf de rij na elke pass op en tel het totale aantal wissels.

Actief ophalen

Haal de kernpunten op — onthul ze daarna.

Bronnen: Examenprogramma informatica (HAVO) (CvTE / Examenblad)

Datastructuren#

Standaardexamenblad-nl

Binaire zoekboom

Afb. 4Afb. 4 — De zoekboom uit het uitgewerkte voorbeeld. De gemarkeerde weg 8 → 3 → 6 → 7 laat zien hoe je naar de waarde 7 zoekt: bij elke knoop kies je links (kleiner) of rechts (groter).

Een datastructuur is een afgesproken manier om gegevens in het geheugen te ordenen, zó gekozen dat de bewerkingen die je vaak doet snel gaan. De eenvoudigste is de lijst of array: een rij vakjes met een vaste index 0, 1, 2, … Omdat de computer weet waar de rij begint en elk vakje even groot is, kan hij element i direct berekenen en ophalen — dat is

O(1)

, ongeacht de lengte. Zoeken naar een wáárde (in plaats van een index) kost in een ongesorteerde lijst wél

O(n)

, en iets ertussen invoegen is duur omdat alles moet opschuiven. Een array is dus ideaal als je vooral via de index werkt en de grootte redelijk vast is.

Twee structuren beperken bewust hóé je erbij mag: de stack en de queue. Een stack (stapel) werkt volgens LIFO — last in, first out, als een stapel borden: je legt er bovenop (push) en pakt er bovenaf (pop), dus wie het laatst kwam, gaat het eerst weg. Stacks zitten achter 'ongedaan maken'-knoppen en achter het terugkeren uit functies in een programma. Een queue (wachtrij) werkt volgens FIFO — first in, first out, als de rij bij de kassa: achteraan erbij (enqueue), vooraan eraf (dequeue), dus wie het eerst kwam, is het eerst aan de beurt. Queues gebruik je voor printtaken, netwerkpakketten en alles wat 'eerlijk op volgorde' afgehandeld moet worden. Beide bewerkingen kosten

O(1)

.

Een boom ordent gegevens hiërarchisch. Hij begint bij één wortel (root); elke knoop (node) kan kinderen hebben, en knopen zonder kinderen heten bladeren (leaves). In een binaire boom heeft elke knoop hoogstens twee kinderen. Een binaire zóékboom (BST) legt daar een handige regel bovenop: in de linkerdeelboom van een knoop staan alleen kleinere waarden, in de rechter alleen grotere. Daardoor kun je zoeken zoals bij binair zoeken — bij elke knoop links of rechts af — wat in een gebalanceerde boom

O(\log n)

kost. Afbeelding 4 toont de zoekboom die je krijgt door de getallen uit het uitgewerkte voorbeeld in te voegen. Bomen zitten onder andere in bestandsmappen, beslisbomen en de manier waarop databases hun gegevens indexeren.

Een graaf is de meest algemene structuur: een verzameling knopen (nodes) verbonden door kanten (edges). Bij een ongerichte graaf werkt een kant beide kanten op (zoals een weg tussen twee steden of een vriendschap); bij een gerichte graaf heeft elke kant een richting (zoals 'volgt op sociale media' of een eenrichtingsstraat). Grafen modelleren netwerken van elke soort: wegennetten, het internet, sociale netwerken en de afhankelijkheden tussen taken in een project. Afbeelding 5 laat zo'n kleine gerichte graaf zien. Anders dan een boom mag een graaf lussen (cykels) bevatten en hoeft er geen wortel te zijn; een boom is eigenlijk een bijzonder, lus-vrij geval van een graaf.

De hashtabel ten slotte combineert snelheid met flexibiliteit. Een hashfunctie rekent een sleutel (bijvoorbeeld een naam) om naar een getal, de index van een 'emmer' (bucket) waarin de bijbehorende waarde wordt bewaard. Omdat je zo direct naar de juiste plek springt, zijn opzoeken, toevoegen en verwijderen gemiddeld

O(1)

— daarom zitten hashtabellen achter woordenboeken, verzamelingen en databases. Botsingen (twee sleutels met dezelfde uitkomst) worden apart opgevangen, en in het slechtste geval zakt de prestatie naar

O(n)

. De kunst is de juiste structuur bij je probleem te kiezen: een array voor snelle index-toegang, een stack of queue voor een strikte volgorde, een boom voor gesorteerd zoeken, een graaf voor netwerken en een hashtabel voor bliksemsnel opzoeken op sleutel.

O(1)

Array-index en hashtabel (gemiddeld)

Toegang tot element $i$ van een array en opzoeken in een hashtabel kosten gemiddeld constante tijd, ongeacht de grootte.

O(\log n)

Zoeken in een gebalanceerde binaire zoekboom

Bij elke knoop kies je links of rechts, waardoor je het aantal kandidaten telkens ongeveer halveert.

Gerichte graaf

Afb. 5Afb. 5 — Een gerichte graaf (knopen + gerichte kanten) die de afhankelijkheden tussen projecttaken weergeeft: 'Opleveren' kan pas als Testen én Documentatie klaar zijn.

Uitgewerkt voorbeeld

Getallen invoegen in een binaire zoekboom

Voeg de getallen 8, 3, 10, 1, 6, 14, 4, 7, 13 in die volgorde in een lege binaire zoekboom in en beschrijf de ontstane structuur.

Wortel
De eerste 8 wordt de wortel. Voor elk volgend getal geldt: kleiner → naar links, groter → naar rechts, net zo lang tot je een lege plek vindt.
3 en 10
3 < 8 → linkerkind van 8. 10 > 8 → rechterkind van 8.
1 en 6
1 < 8 (links), 1 < 3 (links) → linkerkind van 3. 6 < 8 (links), 6 > 3 (rechts) → rechterkind van 3.
14, 4 en 7
14 > 8, 14 > 10 → rechterkind van 10. 4 < 8, 4 > 3, 4 < 6 → linkerkind van 6. 7 < 8, 7 > 3, 7 > 6 → rechterkind van 6.
13
13 > 8, 13 > 10, 13 < 14 → linkerkind van 14.

Resultaat: Je krijgt de boom van Afbeelding 4: wortel 8, met bladeren 1, 4, 7 en 13. Zoeken naar 7 volgt kort de weg 8 → 3 → 6 → 7.

Veelgemaakte fouten

Stack en queue verwisselen — LIFO (bovenop) versus FIFO (achteraan aansluiten).
In een binaire zoekboom kleinere waarden rechts of grotere links plaatsen.
Denken dat een hashtabel altijd $O(1)$ is; bij veel botsingen kan het naar $O(n)$ zakken.

Actieve herhaling

Voeg de getallen 6, 2, 8, 1, 4, 7, 9 in die volgorde in een lege binaire zoekboom in. Teken de boom en geef aan welke knopen bladeren zijn.

Actief ophalen

Haal de kernpunten op — onthul ze daarna.

Bronnen: Examenprogramma informatica (HAVO) (CvTE / Examenblad)

Eindige automaten en toestandsmachines#

Verdiepingexamenblad-nl

Deterministische eindige automaat

Afb. 6Afb. 6 — Een DFA die binaire strings accepteert die eindigen op 01. Vanuit elke toestand vertrekt voor elk symbool precies één pijl; de string wordt geaccepteerd als je na het laatste symbool in de gemarkeerde toestand q2 eindigt.

Een eindige automaat (finite automaton) is een heel eenvoudig, abstract 'machientje' dat een rij invoersymbolen leest en op grond daarvan van toestand naar toestand springt. Je kunt het je voorstellen als een landkaart met bolletjes (toestanden) en pijlen (overgangen). Op elk moment ben je in precies één toestand; lees je een symbool, dan volg je de pijl met dat symbool naar de volgende toestand. Er is één begintoestand (waar je start) en één of meer eindtoestanden ofwel accepterende toestanden. De automaat 'onthoudt' niets meer dan zijn huidige toestand — er is geen geheugen dat bijhoudt hoe vaak of wat je precies zag — en juist die beperking maakt hem zo goed te analyseren.

De variant die je op de HAVO tegenkomt is de deterministische eindige automaat (DFA). 'Deterministisch' betekent dat er vanuit elke toestand voor elk invoersymbool precies één pijl vertrekt: gegeven de toestand en het symbool ligt de volgende toestand volledig vast, zonder keuze of toeval. Formeel beschrijf je zo'n automaat als een vijftal

M = (Q, \Sigma, \delta, q_0, F)

: de verzameling toestanden

Q

, het invoeralfabet

\Sigma

, de overgangsfunctie

\delta

die bij (toestand, symbool) de volgende toestand geeft, de begintoestand

q_0

en de verzameling accepterende toestanden

F

. Dat oogt wiskundig, maar het is niets meer dan een nette samenvatting van het plaatje met bolletjes en pijlen.

Een string 'draai je door' de automaat om te bepalen of hij geaccepteerd of verworpen wordt. Je begint in

q_0

, leest de symbolen één voor één van links naar rechts en volgt telkens de bijbehorende pijl. Is de string op, dan kijk je in welke toestand je bent geëindigd: staat die in

F

(accepterend), dan is de string geaccepteerd; zo niet, dan is hij verworpen. De verzameling van álle strings die een automaat accepteert heet de taal van die automaat. Afbeelding 6 toont een DFA die precies de binaire strings accepteert die eindigen op '01'. Merk op dat sommige toestanden een pijl naar zichzelf hebben (een zelf-lus): daarmee 'blijf je' in dezelfde toestand als een symbool niets verandert aan wat je moet onthouden.

Volg als voorbeeld de string '1101' door die automaat. Je start in

q_0

; de eerste 1 houdt je in

q_0

, de tweede 1 ook. De 0 brengt je naar

q_1

(je hebt net een 0 gezien, een mogelijk begin van '01'), en de laatste 1 brengt je van

q_1

naar de accepterende toestand

q_2

(je zag '01' aan het eind). De string eindigt in

q_2

en wordt dus geaccepteerd — terecht, want '1101' eindigt op '01'. De string '1010' daarentegen eindigt in

q_1

(laatste symbool 0) en wordt verworpen. Zo herken je met een handjevol toestanden een oneindig grote taal, zonder ook maar één string vooraf te hoeven opslaan.

Eindige automaten zijn niet alleen theorie: ze zitten in gereedschap dat je dagelijks gebruikt. Invoervalidatie — controleren of een postcode, e-mailadres of wachtwoord de juiste vorm heeft — is precies de vraag 'accepteert deze automaat de string?'. Reguliere expressies, waarmee programmeurs patronen in tekst beschrijven, worden intern omgezet in eindige automaten. En de lexer of scanner van een compiler, die broncode in stukjes (tokens) knipt zoals getallen, namen en operatoren, is één grote eindige automaat. Toestandsmachines sturen daarnaast verkeerslichten, liften en de menu's van apparaten aan. Overal waar een systeem 'zich in een bepaalde stand bevindt' en op gebeurtenissen reageert, is een toestandsmachine een natuurlijk model.

M = (Q, \Sigma, \delta, q_0, F)

Een DFA als vijftal

$Q$ = toestanden, $\Sigma$ = invoeralfabet, $\delta$ = overgangsfunctie, $q_0$ = begintoestand, $F$ = accepterende toestanden.

\delta(q_1, 1) = q_2

Een overgang lezen

In toestand $q_1$ brengt het symbool 1 je naar $q_2$ ; zo legt de overgangsfunctie elke pijl vast.

Uitgewerkt voorbeeld

Accepteert de automaat de string 1101?

Bepaal met de DFA uit Afbeelding 6 of de string '1101' wordt geaccepteerd. Schrijf alle doorlopen toestanden op.

Start
Je begint in de begintoestand q0. De string is 1-1-0-1.
Lees de eerste 1
In q0 gaat een 1 via de zelf-lus terug naar q0.
Lees de tweede 1
Opnieuw houdt de 1 je in q0.
Lees de 0
Nu brengt de 0 je van q0 naar q1: je hebt net een 0 gezien, mogelijk het begin van '01'.
Lees de laatste 1
In q1 brengt de 1 je naar q2, de accepterende toestand — je zag '01' aan het eind.
$q_0 \to q_0 \to q_0 \to q_1 \to q_2$
Controleer de eindtoestand
De string is op en je bent in q2, dat in F zit. Dus geaccepteerd.

Resultaat: De doorlopen weg is q0 → q0 → q0 → q1 → q2; je eindigt in de accepterende toestand q2, dus '1101' wordt geaccepteerd.

Veelgemaakte fouten

Bij een accepterende eindtoestand alleen kijken of je die onderweg passeerde, in plaats van of je er ná het laatste symbool in eindigt.
Een zelf-lus vergeten te volgen, waardoor je bij een herhaald symbool denkt 'vast te lopen'.
Denken dat een automaat de héle string moet onthouden; hij kent alleen zijn huidige toestand.

Actieve herhaling

Gegeven de DFA uit Afbeelding 6 (accepteert binaire strings die eindigen op '01'). Bepaal voor de strings '0101', '110' en '001' of ze worden geaccepteerd, door telkens de doorlopen toestanden op te schrijven.

Actief ophalen

Haal de kernpunten op — onthul ze daarna.

Bronnen: Examenprogramma informatica (HAVO) (CvTE / Examenblad)

Formele talen en grammatica's#

Verdiepingexamenblad-nl

Parseboom van 3 + 4 * 5

Afb. 7Afb. 7 — De parseboom van 3 + 4 5. Omdat 4 5 samen één gemarkeerde term (T) vormt, staat vast dat eerst 4 * 5 = 20 wordt berekend en pas daarna 3 + 20 = 23.

Een formele taal is wiskundig veel strikter dan een gewone taal. Je begint met een alfabet

\Sigma

: een eindige verzameling symbolen, bijvoorbeeld {0, 1} of alle letters en cijfers. Een string is een eindige rij van die symbolen, en een taal is simpelweg een (vaak oneindige) verzameling van toegestane strings. Twee begrippen die je scherp moet houden zijn syntax en semantiek. Syntax gaat over de vorm: is de string volgens de regels correct opgebouwd? Semantiek gaat over de betekenis: wat stelt de string voor, wat is de waarde? '3 + + 4' is syntactisch fout; '3 + 4' is syntactisch goed en betekent semantisch 7. Een programmeertaal heeft precies zulke regels: de compiler controleert eerst de syntax en bepaalt daarna de betekenis.

Welke strings tot een taal behoren, leg je vast met een grammatica: een verzameling productieregels die beschrijven hoe je geldige strings 'maakt'. Daarin komen twee soorten symbolen voor. Terminals zijn de echte symbolen uit het alfabet die uiteindelijk in de string blijven staan (zoals cijfers, + en *). Nonterminals zijn hulpsymbolen (vaak met een hoofdletter, zoals

E

,

T

,

F

) die nog verder 'uitgewerkt' moeten worden. Een regel als

E \rightarrow E + T

zegt: een expressie

E

mag bestaan uit een expressie, een plusteken en een term. Deze schrijfwijze heet BNF (Backus-Naur-vorm), waarmee je de syntax van programmeertalen en dataformaten precies vastlegt. Het streepje

\mid

betekent 'of':

F \rightarrow 0 \mid 1 \mid \dots \mid 9

zegt dat een factor precies één cijfer is.

Een afleiding (derivation) laat zien dát een string tot de taal hoort, door vanuit het startsymbool net zo lang regels toe te passen tot er alleen nog terminals staan. Elke stap vervangt één nonterminal door de rechterkant van een van zijn regels; we schrijven de stap met een dubbele pijl

\Rightarrow

. Voor de rij '3 + 4 * 5' begin je bij

E

en werk je die stap voor stap uit tot precies die symbolen overblijven (zie het uitgewerkte voorbeeld). Slaagt dat, dan is de string syntactisch geldig. Lukt het met geen enkele regelvolgorde, dan hoort de string niet tot de taal — precies wat een compiler bedoelt met een 'syntaxfout'.

Een afleiding als platte regel is lastig te lezen; daarom tekenen we hem als een parseboom of ontleedboom. De wortel is het startsymbool, elke interne knoop is een nonterminal, en de bladeren zijn — van links naar rechts gelezen — precies de terminals van de string. De boomstructuur maakt bovendien de betekenis zichtbaar: hij groepeert wat bij elkaar hoort. In Afbeelding 7 zie je de parseboom van '3 + 4 5'. Omdat de grammatica de vermenigvuldiging 'dieper' in de boom plaatst dan de optelling, staat vast dat eerst 4 5 wordt uitgerekend en pas daarna 3 erbij: de boom codeert dus de rekenvolgorde (4 5 = 20, dan 3 + 20 = 23), en niet (3 + 4) 5 = 35.

Deze theorie is het fundament onder elke programmeertaal en elk dataformaat. Wie een taal ontwerpt, geeft eerst het alfabet en de grammatica; wie een compiler of interpreter bouwt, laat een parser met die grammatica de broncode ontleden tot een boom (de abstracte syntaxboom), waarna de betekenis wordt bepaald. Dezelfde ideeën zitten achter het lezen van HTML, JSON en XML, achter reguliere expressies, en achter de manier waarop een rekenmachine '3 + 4 * 5' correct interpreteert. Grammatica's en eindige automaten hangen bovendien samen: de eenvoudigste talen (de 'reguliere' talen) kun je zowel met een automaat herkennen als met een simpele grammatica beschrijven — twee kanten van dezelfde medaille.

E \rightarrow E + T \mid T

Regel voor een expressie

Een expressie is een expressie plus een term, of gewoon een term; de $\mid$ betekent 'of'.

T \rightarrow T * F \mid F

Regel voor een term

Een term is een term maal een factor, of een factor; hierdoor bindt de vermenigvuldiging sterker dan de optelling.

F \rightarrow 0 \mid 1 \mid \dots \mid 9

Regel voor een factor

Een factor is in deze eenvoudige taal precies één cijfer (een terminal).

Uitgewerkt voorbeeld

3 + 4 * 5 afleiden en ontleden

Leid met de regels $E \rightarrow E + T \mid T$ , $T \rightarrow T * F \mid F$ en $F \rightarrow$ cijfer de string '3 + 4 * 5' af, en leg uit welke rekenvolgorde de parseboom vastlegt.

Begin bij het startsymbool
We starten met E en passen steeds één regel toe tot er alleen cijfers en tekens overblijven. De linker-nonterminal werken we telkens eerst uit.
$E \Rightarrow E + T$
Werk de linker E uit tot 3
Kies E → T, dan T → F, dan F → 3.
$E + T \Rightarrow T + T \Rightarrow F + T \Rightarrow 3 + T$
Werk de rechter term uit tot 4 * 5
De term T rechts van de + wordt 4 5: kies T → T F en werk beide factoren uit tot cijfers.
$T \Rightarrow T * F \Rightarrow F * F \Rightarrow 4 * F \Rightarrow 4 * 5$
Lees de betekenis af
Omdat 4 en 5 samen onder één term T vallen, groepeert de parseboom ze: eerst 4 * 5 = 20, dan 3 + 20 = 23. De grammatica geeft de vermenigvuldiging dus voorrang.

Resultaat: De afleiding vanuit E slaagt en levert 3 + 4 * 5 op, dus de string is geldig; de parseboom (Afb. 7) legt vast dat de uitkomst 23 is, niet 35.

Veelgemaakte fouten

Terminals en nonterminals verwisselen, of vergeten dat een afleiding pas klaar is als er alleen terminals overblijven.
In de parseboom de rekenvolgorde negeren, waardoor 3 + 4 5 als (3 + 4) 5 wordt gelezen.
Syntax (vorm) en semantiek (betekenis) door elkaar halen.

Actieve herhaling

Gebruik de grammatica $E \rightarrow E + T \mid T$ , $T \rightarrow T * F \mid F$ en $F \rightarrow$ cijfer. Leid de string '2 * 3 + 1' af en teken de bijbehorende parseboom.

Actief ophalen

Haal de kernpunten op — onthul ze daarna.

Bronnen: Examenprogramma informatica (HAVO) (CvTE / Examenblad)

Getalstelsels en booleaanse logica#

Standaardexamenblad-nl

Waarheidstabel van AND, OR en XOR

Afb. 8Afb. 8 — AND is alleen waar bij twee enen; OR bij minstens één; XOR alleen als A en B verschillen.

Mensen rekenen in het tientallige (decimale) stelsel, met tien cijfers 0–9 en machten van 10 als plaatswaarde. Een computer werkt met twee toestanden (stroom aan of uit) en gebruikt daarom het binaire (tweetallige) stelsel: alleen 0 en 1, met machten van 2 als plaatswaarde. In het getal

1101_2

staan de posities voor

2^3, 2^2, 2^1, 2^0

, dus voor

8, 4, 2, 1

. Tel de posities met een 1 op en je hebt de decimale waarde:

8 + 4 + 0 + 1 = 13

. Zo werkt élk stelsel — het grondtal bepaalt alleen welke machten je gebruikt. Acht bits vormen samen een byte, die dus

2^8 = 256

verschillende waarden (0 tot en met 255) kan voorstellen; het is de standaardbrok waarin computers geheugen tellen.

Binaire getallen worden al gauw lang en onleesbaar, daarom gebruiken informatici het hexadecimale (zestientallige) stelsel als handige korte schrijfwijze. Het heeft zestien 'cijfers': 0–9 en dan A, B, C, D, E, F voor de waarden 10 tot en met 15. Het mooie is dat vier bits precies één hexcijfer vormen (

2^4 = 16

), zodat je een byte in twee hexcijfers schrijft. Zo is 1111 binair gelijk aan 15, oftewel F, en het bytepatroon 0010 1111 schrijf je als

\text{0x2F}

. Omrekenen van hex naar decimaal gaat weer met plaatswaarden, nu machten van 16:

\text{0x2F} = 2 \cdot 16 + 15 = 47

. Je ziet hexadecimaal overal waar bits een rol spelen: kleurcodes (zoals #FF8800), geheugenadressen en foutcodes.

Naast getallen rekent een computer met waarheidswaarden: waar (1) en onwaar (0). De booleaanse logica kent drie basisoperatoren. AND (

\land

) is alleen waar als béíde ingangen waar zijn; OR (

\lor

) is waar als mínstens één ingang waar is; NOT (

\overline{A}

) keert een waarde om. Een vierde, veelgebruikte operator is XOR (

\oplus

, de 'exclusieve of'): waar als de ingangen verschíllen. Deze operatoren zitten letterlijk in de hardware als logische poorten, en in software in elke 'als … en/of … dan'-voorwaarde. Afbeelding 8 vat AND, OR en XOR samen in één waarheidstabel. Let op het verschil tussen OR (ook waar als beide waar zijn) en XOR (juist níét waar als beide waar zijn).

Om een samengestelde booleaanse expressie te doorgronden maak je een waarheidstabel: je zet alle mogelijke combinaties van de ingangen in de rijen en rekent de expressie kolom voor kolom uit. Bij

n

ingangen zijn er

2^n

rijen — twee variabelen geven 4 rijen, drie variabelen 8. Handig is om eerst tussenkolommen te maken voor de deeluitdrukkingen. Voor

A \land (\overline{B} \lor C)

bereken je bijvoorbeeld eerst

\overline{B}

, dan

\overline{B} \lor C

, en pas daarna de hele AND. Zo houd je overzicht en maak je minder fouten. Het uitgewerkte voorbeeld en Afbeelding 9 lopen deze tabel helemaal door. Twee expressies zijn logisch gelijkwaardig als hun resultaatkolommen precies gelijk zijn.

Voor booleaanse expressies gelden rekenregels, net als in de gewone algebra. De bekendste zijn de wetten van De Morgan, die vertellen hoe een NOT over een AND of OR 'heen valt' en daarbij de operator omklapt:

\overline{A \land B} = \overline{A} \lor \overline{B}

en

\overline{A \lor B} = \overline{A} \land \overline{B}

. In woorden: 'niet (A én B)' is hetzelfde als 'niet A óf niet B'. Je kunt zulke wetten bewijzen door beide kanten in een waarheidstabel te zetten en te zien dat de resultaatkolommen gelijk zijn. Verder gelden onder meer

A \land 0 = 0

,

A \lor 1 = 1

en

A \land \overline{A} = 0

. Met deze regels vereenvoudig je logische schakelingen en voorwaarden, wat kan schelen in hardware en in de leesbaarheid van code.

1101_2 = 1\cdot 2^3 + 1\cdot 2^2 + 0\cdot 2^1 + 1\cdot 2^0 = 13_{10}

Binair naar decimaal met plaatswaarden

Tel de machten van 2 op de posities met een 1 op: $8 + 4 + 1 = 13$ .

13_{10} = \text{D}_{16}

Decimaal naar hexadecimaal

13 is kleiner dan 16 en komt overeen met het hexcijfer D.

\overline{A \land B} = \overline{A} \lor \overline{B}

Wet van De Morgan

Een NOT over een AND wordt een OR van de losse NOT's — de operator klapt om.

Waarheidstabel van A ∧ (¬B ∨ C)

Afb. 9Afb. 9 — Stap voor stap: eerst ¬B, dan ¬B ∨ C, dan de hele AND. De expressie is alleen waar in de rijen (1,0,0), (1,0,1) en (1,1,1); de eerste daarvan is gemarkeerd.

Uitgewerkt voorbeeld

1101 omrekenen en een waarheidstabel invullen

Reken $1101_2$ om naar decimaal en hexadecimaal, en vul de waarheidstabel van $A \land (\overline{B} \lor C)$ in.

Binair naar decimaal
Schrijf de plaatswaarden 8, 4, 2, 1 onder de bits en tel de posities met een 1 op.
$1101_2 = 8 + 4 + 0 + 1 = 13_{10}$
Decimaal naar hexadecimaal
13 past in één hexcijfer: de waarde 13 heet in hex D. Dus 1101 binair is 0xD.
$13_{10} = \text{D}_{16}$
Zet de tabel op
Drie variabelen geven 2³ = 8 rijen. Maak eerst tussenkolommen voor ¬B en ¬B ∨ C, en reken dan de AND met A uit.
Reken de rijen uit
De expressie is alleen waar als A = 1 én (¬B ∨ C) waar is. Dat gebeurt in de rijen (A,B,C) = (1,0,0), (1,0,1) en (1,1,1); in alle andere rijen is de uitkomst 0.
$A \land (\overline{B} \lor C)$

Resultaat: Er geldt $1101_2 = 13_{10} = \text{0xD}$ ; de expressie $A \land (\overline{B} \lor C)$ is waar in 3 van de 8 rijen (zie Afb. 9).

Veelgemaakte fouten

Bij binair naar decimaal de plaatswaarden verkeerd om zetten (van rechts naar links begint het bij $2^0$ ).
OR ('minstens één') verwarren met XOR ('precies één / verschillend').
Bij De Morgan de operator niet omklappen: $\overline{A \land B}$ wordt $\overline{A} \lor \overline{B}$ , niet $\overline{A} \land \overline{B}$ .

Actieve herhaling

Reken $101101_2$ om naar decimaal en naar hexadecimaal, en stel de volledige waarheidstabel op van de expressie $(A \lor B) \land \overline{C}$ .

Actief ophalen

Haal de kernpunten op — onthul ze daarna.

Bronnen: Examenprogramma informatica (HAVO) (CvTE / Examenblad)

Kernpunten

Hoeveel stappen doet binair zoeken in 1000 elementen?

Kernpunten

Bubble sort naspelen en de wissels tellen

Kernpunten

Getallen invoegen in een binaire zoekboom

Kernpunten

Accepteert de automaat de string 1101?

Kernpunten

3 + 4 * 5 afleiden en ontleden

Kernpunten

1101 omrekenen en een waarheidstabel invullen

Bronnen