Samenvattingen · InformaticaNL · VWO

Domein B: Grondslagen

Domein B legt het theoretische fundament onder de informatica: algoritmen (opgebouwd uit sequentie, selectie en iteratie, met standaardalgoritmen voor zoeken en sorteren), datastructuren (array, lijst, stapel, wachtrij, boom en graaf), eindige automaten met hun toestandsdiagrammen, en formele talen met hun grammatica’s. Deze begrippen zijn taalonafhankelijk: ze beschrijven wat een berekening is, los van welke programmeertaal je later kiest.

4 Onderdelen~15 min leestijd4 VaardighedenNiveau Basis 1 · Standaard 1 · Verdieping 2

T·0333 / 18

Examenprofiel

B · Algoritmen ontwerpen en analyseren met sequentie, selectie en iteratie; standaardalgoritmen voor zoeken en sorterenB · Datastructuren kiezen en gebruiken: array, lijst, stapel, wachtrij, boom en graafB · Eindige automaten en toestandsdiagrammen ontwerpen en interpreterenB · Formele talen en grammatica’s lezen; een parseerboom opstellen

Operatoren:ontwerpspeel naleg uitbepaaltoon aananalyseer

basisniveau

Sequentie, selectie, iteratie en de standaardalgoritmen voor zoeken en sorteren vormen de kern; ze keren terug in domein D (programmeren).

verhoogd niveau

Bij verdieping (keuze G) analyseer je de complexiteit van deze algoritmen met O-notatie en verbind je automaten met formele talen.

Diepte

Tekst

Inhoud · 4 onderdelen

Domein B: Grondslagen

Algoritmen en controlestructuren#

Basisexamenblad-informatica-B

Een algoritme is een eindige, ondubbelzinnige reeks stappen die een probleem oplost voor elke geldige invoer. Elk algoritme, hoe complex ook, is opgebouwd uit slechts drie controlestructuren: sequentie (stappen na elkaar), selectie (een keuze op grond van een voorwaarde: als … dan … anders …) en iteratie (herhaling: zolang … of voor elke …). Afb. 1 toont deze structuren in een stroomdiagram van het lineair zoeken: de ruit is de selectie, de pijl die terugloopt naar de voorwaarde is de iteratie, en de rechte opeenvolging van blokken is de sequentie. Dat élk algoritme met deze drie bouwstenen te schrijven is, is een fundamenteel resultaat (de structuurstelling van Böhm-Jacopini).

Stroomdiagram van het lineair zoeken

Afb. 1Afb. 1 — Lineair zoeken: de ruit is de selectie, de teruglopende pijl de iteratie, de opeenvolging de sequentie.

Lineair zoeken doorloopt een rij element voor element tot het gezochte gevonden is of de rij op is. Het werkt op elke rij, ook een ongesorteerde, maar moet in het slechtste geval alle

n

elementen bekijken. Binair zoeken is veel sneller, maar stelt een eis: de rij moet gesorteerd zijn. Het vergelijkt met het middelste element en gooit telkens de helft van de rij weg — links of rechts, afhankelijk van de vergelijking. Waar lineair zoeken in het slechtste geval

n

stappen kost, doet binair zoeken er ongeveer

\log_2 n

: bij een miljoen elementen is dat het verschil tussen een miljoen en twintig vergelijkingen.

Sorteren brengt een rij in volgorde en is een voorwaarde voor binair zoeken. Eenvoudige sorteeralgoritmen zoals bubble sort en selection sort vergelijken telkens paren en verwisselen ze; ze zijn makkelijk te begrijpen maar kosten in de orde van

n^2

stappen. Slimmere algoritmen (zoals merge sort, dat het verdeel-en-heers-principe gebruikt) halen

n\log_2 n

. Bij het kiezen van een algoritme weeg je niet alleen de snelheid, maar ook of de invoer al bijna gesorteerd is, hoeveel geheugen je hebt en of gelijke elementen hun volgorde moeten houden (stabiliteit).

Een algoritme is pas bruikbaar als het correct is (voor elke geldige invoer het juiste resultaat) én termineert (altijd stopt). Bij iteratie let je daarom op de stopvoorwaarde: een lus die zijn voorwaarde nooit onwaar maakt, blijft eeuwig draaien (een oneindige lus). Naast correctheid beoordeel je de efficiëntie: hoeveel stappen (tijd) en hoeveel geheugen (ruimte) het algoritme nodig heeft als functie van de invoergrootte

n

. Deze inschatting maak je grof met de groeiorde; de precieze notatie (

O(n)

O(\log n)

O(n^2)

) hoort bij keuzethema G, maar het idee — hoe snel groeit het werk als de invoer groeit? — hoort al bij de grondslagen.

T_{\text{lineair}}(n) \approx n \quad\text{versus}\quad T_{\text{binair}}(n) \approx \log_2 n

Aantal vergelijkingen (slechtste geval)

Binair zoeken halveert de zoekruimte elke stap, lineair zoeken loopt alles langs.

Uitgewerkt voorbeeld

Binair zoeken naspelen

Zoek met binair zoeken het getal 25 in de gesorteerde rij [3, 7, 12, 19, 25, 31, 42] (indices 0 t/m 6).

Stap 1 — hele rij
Ondergrens 0, bovengrens 6, midden = (0+6)/2 = 3. rij[3] = 19. Omdat 25 > 19, zoek verder rechts (indices 4..6).
Stap 2 — rechterhelft
Ondergrens 4, bovengrens 6, midden = (4+6)/2 = 5. rij[5] = 31. Omdat 25 < 31, zoek verder links (index 4..4).
Stap 3 — één element
Ondergrens 4, bovengrens 4, midden = 4. rij[4] = 25. Gevonden!

Resultaat: 25 staat op index 4, gevonden in 3 vergelijkingen; lineair zoeken had er 5 gekost.

Veelgemaakte fouten

Binair zoeken toepassen op een ongesorteerde rij; zonder sortering werkt het niet, omdat je dan niet weet in welke helft je verder moet zoeken.
Bij iteratie de stopvoorwaarde vergeten of verkeerd formuleren, waardoor de lus nooit stopt (oneindige lus) of één element te vroeg of te laat afbreekt.

Actieve herhaling

Gegeven de gesorteerde rij [3, 7, 12, 19, 25, 31, 42]. Speel binair zoeken na voor het element 12 en noteer bij elke stap welk middelste element je vergelijkt en welke helft je overhoudt.

Actief ophalen

Haal de kernpunten op — onthul ze daarna.

Bronnen: Examenprogramma informatica vwo — domein B (algoritmen) (CvTE / Examenblad)

Datastructuren#

Standaardexamenblad-informatica-B

Binaire zoekboom

Afb. 3Afb. 2 — In een binaire zoekboom is links altijd kleiner en rechts altijd groter; zoeken daalt telkens één kant af.

Een datastructuur bepaalt hoe je gegevens in het geheugen organiseert, en die keuze bepaalt welke bewerkingen goedkoop of duur zijn. De eenvoudigste is de array (rij): een blok elementen op opeenvolgende plaatsen, elk direct bereikbaar via zijn index — opzoeken op index kost één stap, maar invoegen midden in de rij dwingt je alle volgende elementen op te schuiven. Een gelinkte lijst rijgt elementen aan elkaar met verwijzingen; invoegen en verwijderen is dan goedkoop, maar het

k

-de element vinden vergt het aflopen van de keten. De les: er is geen ‘beste’ datastructuur, alleen een beste bij een bepaald gebruikspatroon.

Twee bijzondere lijsten worden gedefinieerd door de manier waarop je ze in- en uitlaadt. Een stapel (stack) werkt volgens LIFO — last in, first out: je legt bovenop en neemt bovenaf, zoals een stapel borden. Stacks liggen onder het terugkeren uit functieaanroepen en het ‘ongedaan maken’ (undo). Een wachtrij (queue) werkt volgens FIFO — first in, first out: wie het eerst komt, gaat het eerst — zoals een rij bij de kassa. Queues modelleren printtaken, netwerkbuffers en processen die op de CPU wachten. Afb. 1 vat de kenmerken van deze vier structuren samen.

De boom (tree) organiseert gegevens hiërarchisch: een wortel met vertakkende knopen, elk met kinderen, eindigend in bladeren. Een veelgebruikte vorm is de binaire zoekboom, waarin voor elke knoop geldt dat álle waarden in de linker deelboom kleiner zijn en alle in de rechter groter. Afb. 2 toont zo’n boom; daarin zoek je een waarde door bij de wortel te beginnen en telkens links of rechts af te dalen. Is de boom mooi in balans, dan kost dat ongeveer

\log_2 n

stappen — hetzelfde halveringsprincipe als binair zoeken, maar nu in een structuur die ook snel invoegen en verwijderen toelaat.

Vier datastructuren vergeleken

Afb. 2Afb. 1 — Elke datastructuur maakt bepaalde bewerkingen goedkoop en andere duur.

De graaf (graph) is de meest algemene structuur: knopen (vertices) verbonden door kanten (edges), eventueel gericht en/of gewogen. Waar een boom een hiërarchie zonder cykels is, mag een graaf willekeurige verbindingen en kringen bevatten. Grafen modelleren netwerken van elke soort: wegen tussen steden, vriendschappen in een sociaal netwerk, links tussen webpagina’s, afhankelijkheden tussen taken. Veel klassieke problemen — de kortste route, de goedkoopste verbinding van alles, het opsporen van kringen — zijn grafenproblemen. De keuze voor een datastructuur is dus in de kern een modelleerkeuze: je kiest de structuur die de relaties in je probleem het natuurlijkst weergeeft.

Uitgewerkt voorbeeld

Bewerkingen op een stapel en een wachtrij

Voer op een lege stapel én een lege wachtrij dezelfde invoervolgorde uit: voeg 1, 2, 3 toe en neem daarna twee elementen af. Welke elementen verdwijnen bij elk?

Toevoegen
Beide bevatten na het toevoegen 1, 2, 3 (1 als eerste toegevoegd, 3 als laatste).
Stapel (LIFO)
Afnemen geeft eerst 3, dan 2 — het laatst toegevoegde vertrekt als eerste. Rest: [1].
Wachtrij (FIFO)
Afnemen geeft eerst 1, dan 2 — het eerst toegevoegde vertrekt als eerste. Rest: [3].

Resultaat: Dezelfde invoer, tegengesteld resultaat: de stapel laat 3 en 2 vertrekken (rest 1), de wachtrij 1 en 2 (rest 3).

Veelgemaakte fouten

Stapel (LIFO) en wachtrij (FIFO) verwisselen; bij een stapel verlaat het láátst toegevoegde element als eerste, bij een wachtrij juist het éérst toegevoegde.
Denken dat een array altijd de beste keuze is; midden in een array invoegen kost het opschuiven van alle volgende elementen, wat een lijst goedkoper doet.

Actieve herhaling

Op een lege stapel voer je uit: push(A), push(B), push(C), pop, push(D), pop. Geef de inhoud van de stapel na elke bewerking en het element dat bij elke pop verdwijnt.

Actief ophalen

Haal de kernpunten op — onthul ze daarna.

Bronnen: Examenprogramma informatica vwo — domein B (datastructuren) (CvTE / Examenblad)

Eindige automaten en toestandsdiagrammen#

Verdiepingexamenblad-informatica-B

Toestandsdiagram: reeksen die op 1 eindigen

Afb. 4Afb. 1 — Deze DFA aanvaardt precies de binaire reeksen die op een 1 eindigen; q1 is de eindtoestand.

Een eindige automaat (finite state machine) is een abstract machientje met een eindig aantal toestanden, dat symbool voor symbool een invoer verwerkt en bij elk symbool volgens vaste overgangsregels naar een volgende toestand springt. Je tekent hem als een toestandsdiagram: cirkels zijn toestanden, pijlen zijn overgangen met het symbool erbij. Afb. 1 toont een automaat die binaire reeksen leest. Eén toestand is de begintoestand (waar je start) en één of meer zijn eindtoestanden (accepterend, meestal met een dubbele cirkel). Een invoerreeks wordt aanvaard als je na het lezen van het laatste symbool in een eindtoestand belandt.

De automaat in Afb. 1 herkent binaire reeksen die op een 1 eindigen. Vanuit

q_0

(begin, niet-accepterend) blijf je bij een 0 in

q_0

(de lus), en bij een 1 ga je naar

q_1

(accepterend). In

q_1

blijf je bij een 1 (lus), maar een 0 stuurt je terug naar

q_0

. De toestand onthoudt dus precies één ding: was het laatst gelezen symbool een 1? Dat illustreert de kracht én de grens van een eindige automaat: hij heeft géén onbeperkt geheugen, alleen zijn eindige verzameling toestanden. Elke toestand vat een hele klasse van ‘tot nu toe geziene’ invoeren samen — opnieuw abstractie in actie.

Automaten zijn deterministisch (DFA) als er vanuit elke toestand voor elk invoersymbool precies één overgang is — dan ligt het pad volledig vast. Bij een niet-deterministische automaat (NFA) mag een toestand voor hetzelfde symbool meerdere overgangen (of geen) hebben, en de reeks wordt aanvaard zodra ér een pad naar een eindtoestand bestaat. Een belangrijk resultaat is dat beide precies even krachtig zijn: bij elke NFA bestaat een DFA die exact dezelfde reeksen aanvaardt. De NFA is vaak makkelijker te ontwerpen, de DFA makkelijker uit te voeren.

Eindige automaten zijn geen speelgoed: ze zitten overal in echte systemen. Een verkeerslicht, een kaartjesautomaat, de lexicale ontleder in een compiler, het protocol van een netwerkverbinding en de knopbediening van een apparaat zijn allemaal als toestandsmachine te beschrijven. Ze vormen bovendien de brug naar de volgende sectie: de reeksen die een eindige automaat kan aanvaarden zijn precies de reguliere talen, en die worden ook beschreven door reguliere expressies. Toestandsdiagram en reguliere expressie zijn twee gezichten van dezelfde formele taal.

Uitgewerkt voorbeeld

Wordt de reeks aanvaard?

Loop de reeks 1011 door de automaat uit Afb. 1 en bepaal of ze wordt aanvaard.

Start
Begin in q0. Lees het eerste symbool: 1 → ga naar q1.
Tweede symbool
In q1, lees 0 → terug naar q0.
Derde symbool
In q0, lees 1 → naar q1.
Vierde symbool
In q1, lees 1 → lus, blijf in q1. Invoer op.

Resultaat: Na het laatste symbool sta je in q1 (eindtoestand): 1011 wordt aanvaard — de reeks eindigt inderdaad op een 1.

Veelgemaakte fouten

Een reeks aanvaard noemen omdat je onderweg door een eindtoestand kwam; alleen de toestand ná het láátste symbool telt.
Bij een deterministische automaat een toestand ontwerpen waar voor hetzelfde symbool geen of twee overgangen bestaan; in een DFA hoort er precies één per symbool te zijn.

Actieve herhaling

Gegeven de automaat uit Afb. 1 (aanvaardt binaire reeksen die op 1 eindigen). Bepaal voor 1011, 1100 en 0 of ze worden aanvaard, en noteer het doorlopen toestandenpad.

Actief ophalen

Haal de kernpunten op — onthul ze daarna.

Bronnen: Examenprogramma informatica vwo — domein B (automaten) (CvTE / Examenblad)

Formele talen en grammatica’s#

Verdiepingexamenblad-informatica-B

Parseerboom van 3 + 4 × 2

Afb. 5Afb. 1 — De parseerboom van 3 + 4 × 2: de vermenigvuldiging zit dieper en gebeurt dus eerst.

Een formele taal is een precies afgebakende verzameling ‘woorden’: reeksen symbolen uit een vast alfabet. Anders dan een natuurlijke taal is een formele taal exact gedefinieerd — een reeks hoort er wel of niet bij, zonder grijs gebied. Formele talen zijn onmisbaar in de informatica: een programmeertaal, een bestandsformaat, een url en een rekenkundige expressie zijn allemaal formele talen. Het centrale probleem is: hoort deze reeks bij de taal, en zo ja, wat is haar structuur? Om dat te beantwoorden gebruik je een grammatica.

Een grammatica is een verzameling productieregels die beschrijven hoe je geldige woorden opbouwt. Ze werkt met niet-terminalen (hulpsymbolen, vaak hoofdletters, die nog vervangen moeten worden) en terminalen (de echte symbolen die in het eindwoord staan). Je begint bij het startsymbool en vervangt telkens een niet-terminale volgens een regel, tot er alleen terminalen over zijn. Een eenvoudige grammatica voor rekenkundige expressies is:

E \to E + E

E \to E \times E

E \to ( E )

E \to \text{getal}

. Hiermee genereer je uitdrukkingen als

3 + 4 \times 2

. De regels zijn recursief:

E

komt in zijn eigen definitie voor, wat oneindig veel geldige woorden mogelijk maakt met een eindig aantal regels.

Parseren (ontleden) is het omgekeerde: gegeven een reeks, reconstrueer je welke regels haar kunnen voortbrengen, en leg je die structuur vast in een parseerboom (syntaxboom). Afb. 1 toont de parseerboom van

3 + 4 \times 2

: de wortel is het startsymbool, de knopen zijn regeltoepassingen en de bladeren zijn de terminalen. De boom maakt de structuur zichtbaar — en dus ook de betekenis. Dat

4 \times 2

dieper in de boom zit dan de optelling, drukt uit dat de vermenigvuldiging eerst gebeurt: de boomstructuur codeert de bewerkingsvolgorde.

Grammatica’s verschillen in kracht. Reguliere grammatica’s beschrijven precies de talen die een eindige automaat aankan (sectie 3) — bruikbaar voor eenvoudige patronen, maar ze kunnen niet ‘tellen’ of onbeperkt geneste haakjes bijhouden. Daarvoor heb je contextvrije grammatica’s nodig, die wél willekeurig diepe nesting aankunnen (zoals haakjes in een expressie) en de ruggengraat vormen van elke programmeertaal. Een reeks kan ambigu zijn als er meer dan één parseerboom bij past; goede grammatica’s worden zo opgesteld dat dat niet gebeurt, want anders zou dezelfde code twee betekenissen kunnen hebben. Compilers gebruiken deze theorie letterlijk: eerst splitst een automaat de tekst in symbolen (lexen), daarna bouwt een parser de syntaxboom (parsen).

E \;\to\; E + E \;\mid\; E \times E \;\mid\; ( E ) \;\mid\; \text{getal}

Contextvrije grammatica voor expressies

Het recursieve niet-terminaal E genereert alle rekenkundige uitdrukkingen.

Uitgewerkt voorbeeld

Behoort de reeks tot de taal?

Toon met de grammatica $E \to E + E \mid E \times E \mid ( E ) \mid \text{getal}$ aan dat $1 + 2$ tot de taal behoort.

Start
Begin bij het startsymbool E.
Pas de optelregel toe
E → E + E.
Vervang de niet-terminalen
Linker E → getal (1), rechter E → getal (2): E + E → 1 + 2.
Controle
Er zijn alleen nog terminalen (1, +, 2) over — de afleiding is compleet.

Resultaat: De afleiding E ⇒ E + E ⇒ 1 + 2 bewijst dat 1 + 2 een geldig woord van de taal is.

Veelgemaakte fouten

Niet-terminalen en terminalen door elkaar halen; alleen terminalen mogen in het uiteindelijke woord blijven staan, niet-terminalen moeten allemaal vervangen zijn.
Bij het parseren de bewerkingsvolgorde negeren en $3 + 4 \times 2$ als $(3+4)\times 2$ opvatten, terwijl de grammaticale structuur $3 + (4\times 2)$ voorschrijft.

Actieve herhaling

Gegeven de grammatica $E \to E + E \mid E \times E \mid ( E ) \mid \text{getal}$ . Geef een afleiding van de reeks $(1 + 2) \times 3$ vanuit $E$ en teken de bijbehorende parseerboom.

Actief ophalen

Haal de kernpunten op — onthul ze daarna.

Bronnen: Examenprogramma informatica vwo — domein B (formele talen en grammatica’s) (CvTE / Examenblad)

Referenties en bronnen

Bronnen

CvTE / Examenblad

Examenprogramma informatica vwo — domein B (algoritmen)

Domein B: Grondslagen

Kernpunten

Binair zoeken naspelen

Kernpunten

Bewerkingen op een stapel en een wachtrij

Kernpunten

Wordt de reeks aanvaard?

Kernpunten

Behoort de reeks tot de taal?

Bronnen

Domein B: Grondslagen

Kernpunten

Binair zoeken naspelen

Kernpunten

Bewerkingen op een stapel en een wachtrij

Kernpunten

Wordt de reeks aanvaard?

Kernpunten

Behoort de reeks tot de taal?

Bronnen