Module: Enigma - Grondslagen

Module: Enigma - Grondslagen

A Inleiding

Vooraf

In de module Grondslagen behandelen we de basisprincipes van informatie en rekenen.
Eigenlijk hoort ook communicatie in dit rijtje, maar dat is uitgewerkt als een apart onderdeel.
Bij rekenen denk je meestal aan het werken met getallen.

In de informatica heeft rekenen een ruimere betekenis:
rekenen is het manipuleren van vormen (“spelen met vormen”), volgens bepaalde regels.

Deze regels schrijven precies voor hoe je met de vormen manipuleert.
Zo’n voorschrift noemen we een algoritme.
Deze vormen kunnen van alles voorstellen: getallen, woorden, tekeningen, foto’s, muziek, enz.

Leerdoelen

Lees de leerdoelen door die van toepassing zijn op deze module.
Na verwerking van deze module:

  • weet ik dat informatie uit vormen bestaat en een manier om die vormen betekenis te geven;
  • weet ik wat het verschil is tussen representeren en interpreteren;
  • weet ik wat wordt verstaan onder een vorm;
  • kan ik voorbeelden geven van fysieke dragers voor verschillende vormen;
  • weet ik dat het verband tussen een vorm en een betekenis een kwestie van afspraak (conventie) is;
  • kan ik uitleggen waarom sommige vormen handiger zijn om mee te werken dan andere vormen;
  • weet ik het verschil tussen een analoge en een digitale vorm;
  • weet ik wat discrete waarden zijn;
  • kan ik uitleggen wat een symbolische vorm is;
  • weet ik wat een elementaire symbolische vorm is;
  • kan ik een definitie geven van informatie;
  • kan ik uitleggen wat wordt bedoeld met “informatie stuurt”;
  • kan ik toelichten wat het verschil is tussen informatie en data;
  • weet ik wat een informatieproces is;
  • weet ik dat een vorm statisch en een informatieproces dynamisch is;
  • weet ik wat bij informatica met een boom bedoeld wordt;
  • kan ik uitleggen wat wordt bedoeld met een recursieve structuur;
  • kan ik de verschillende niveaus in een boom onderscheiden;
  • kan ik voorbeelden geven van boomstructuren;
  • weet ik wat bedoeld wordt met paden in een boom;
  • weet ik wat een binaire zoekboom is;
  • weet ik wat een ontleedboom is;
  • weet ik wat bij informatica met rekenen bedoeld wordt;
  • kan ik uitleggen wat een algoritme is;
  • weet ik wat cellulaire automaten zijn;
  • weet ik wat het verschil is tussen een ééndimensionale – en een tweedimensionale cellulaire automaat;
  • weet ik wat wordt bedoeld met rule 110;
  • kan ik de onderdelen van een eindige automaat benoemen;
  • weet ik wat lineair en binair zoeken is;
  • weet ik wat het verschil tussen map en reduce is;
  • weet ik waarvoor grammatica’s gebruikt worden;
  • weet ik wat herschrijfregels en syntaxdiagrammen zijn.

Bijlagen

Bij deze module horen de volgende bijlagen:

Download de bestanden naar je device en open ze met de bijbehorende programma's die omschreven worden in de opdrachten.

Zo werkt het

Je bent begonnen in de module Grondslagen.
Deze module bestaat uit meerdere onderdelen.
In ieder onderdeel vind je, verdeeld over verschillende pagina's, informatie in de vorm van teksten, afbeeldingen en video's.
Daarnaast ga je zelf aan de slag. Onder het kopje "Aan de slag" vind je steeds toepassingsopdrachten.
Deze opdrachten maak je alleen of met een klasgenoot.

Er zijn ook toetsen. Deze herken je aan de blauwe knop met daarop "Adaptieve Toets".
Een toets bestaat uit meerdere vragen. Dat kunnen gesloten vragen zijn, die door de computer worden nagekeken, of open vragen, die moet je zelf nakijken.
Bij een enkele vraag moet je een bestand uploaden.

Van de toetsen wordt, als je ingelogd bent, de voortgang bijgehouden.
Het resultaat vind je onder de knop "Voortgang". Deze voortgang is ook door je docent te bekijken.

De blauwe knoppen zijn aanklikbaar. Hieronder zie je een voorbeeld van een blauwe knop. 

Oftewel, wanneer je op de blauwe knop drukt, opent hetgeen wat je nodig hebt. Denk aan een toets of jouw voortgang.

Succes met de module Grondslagen.

 

B Grondslagen

Inleiding

Alan Turing

In het onderdeel Grondslagen behandelen we de basisprincipes van informatie en rekenen. Deze basisprincipes zijn onafhankelijk van de technologie. Dat betekent niet dat deze principes puur theoretisch zijn. Je komt ze overal tegen waar er sprake is van informatie, communicatie en rekenen. Overal in de ICT, maar ook overal daarbuiten: in de biologie, in het menselijk brein, in organisaties, enz.

Deze principes geven je ook houvast voor de toekomst: ook de toekomstige technologie en toepassingen gedragen zich volgens deze basisprincipes.

Het onderdeel Grondslagen vormt een eerste kennismaking met deze basisprincipes. Het vakgebied is veel groter dan we in hier kunnen behandelen. In het vervolg komen nog meer fundamentele vragen aan de orde, zoals:

  • wat zijn de fundamentele beperkingen van informatieverwerking (ofwel rekenen)?
  • wat zijn de overeenkomsten en verschillen tussen mens en robot?
  • kunnen machines denken?

Alan Turing heeft een variatie van deze vraag geformuleerd: kun je het verschil tussen mens en robot (computer) zien aan de manier waarop deze vragen beantwoorden? Dit heet de Turing test. De omgekeerde vorm van deze test kom je tegen op het web, in de vorm van een CAPTCHA, waarin je moet aantonen dat je geen robot bent. Turing voorzag, doordat hij bezig was na te denken over de grondslagen, een aantal van de fundamentele vragen die nu nog steeds actueel zijn.

Een voorbeeld hoe je de basisprincipes van rekenen (algoritmen) op verrassende plaatsen tegen kunt komen is The Algorithmic Beauty of Plants.


Dit laat zien hoe je met eenvoudige rekenregels complexe vormen zoals je die in de (levende) natuur tegenkomt, kunt beschrijven. Dit heeft een praktische toepassing in het genereren van landschappen e.d. in computer games. Maar het raakt ook aan de regels die de natuur zelf gebruikt, met dergelijke vormen als resultaat.

Taal is erg menselijk - maar talen spelen ook een belangrijke rol bij “rekenen” (informatieverwerking). Algoritmen drukken we uit in programmeertalen om deze vervolgens door automaten (computers) te laten verwerken. Met behulp van een grammatica beschrijf je de structuur van de zinnen in een taal. Dit principe kun je zowel gebruiken voor programmeertalen als voor natuurlijke talen zoals het Nederlands of het Italiaans. Dit vormt de basis voor het “rekenen met taal” zoals je dat bijvoorbeeld tegenkomt bij Google Translate, maar ook in een compiler (vertaler) voor een programmeertaal.

★ Aan de slag 1

  1. Geef drie voorbeelden van CAPTCHA’s die je op het web tegen kunt komen.
  2. Geef aan welke principes deze CAPTCHA’s gebruiken.
  3. Probeer een voorbeeld van een oude CAPTCHA te vinden die nu niet meer bruikbaar is doordat de “robots” hierin te goed geworden zijn.

★ Aan de slag 2

  1. Zoek op het web naar algoritmisch gegenereerde afbeeldingen van “natuur”, zoals planten of landschappen.
    Mogelijke zoektermen hierbij zijn “algorithmic beauty” en “fractal landscape”.
  2. Kun je deze (als in een Turing test) onderscheiden van natuurlijke planten of landschappen?

★ Aan de slag 3

1. Bedenk in welke van de volgende situaties een programma als Google Translate beter werkt:

  • voor technisch/wetenschappelijke artikelen, gebruikershandleidingen e.d.;
  • voor dagelijks taalgebruik, bijvoorbeeld in krantenartikelen;
  • voor literair taalgebruik, van romans tot gedichten.

2. Geef argumenten voor je antwoord.

3. Ga vervolgens met enkele voorbeelden na of je vermoeden (hypothese) klopt.

Grammatica vormt de basis voor het "rekenen met taal", wat belangrijk is bij toepassingen zoals Google Translate en compilers voor programmeertalen. Google Translate maakt gebruik van geavanceerde algoritmes en taalmodellen om teksten nauwkeurig te vertalen. Hoewel moderne systemen vaak werken met technieken zoals neurale netwerken (een vorm van kunstmatige intelligentie), gaan we daar in deze module niet dieper op in. Zowel natuurlijke talen als programmeertalen kunnen dankzij deze technieken efficiënter en nauwkeuriger worden verwerkt.

Voor verdere verdieping mag je gebruik maken van internet om begrippen zoals 'neurale machinevertaling' zelf op te zoeken.

4. Wat is de rol van grammatica in zowel natuurlijke talen als programmeertalen?

  1. Het optimaliseert de rekensnelheid van algoritmen.
  2. Het vertaalt zinnen direct naar een andere taal.
  3. Het beschrijft de structuur van de zinnen in een taal.
  4. Het vermindert de complexiteit van talen.

5. Welke basis wordt gebruikt voor het "rekenen met taal" in toepassingen zoals Google Translate en compilers?

  1. Grammatica
  2. Handige vertalingen
  3. Neurale netwerken
  4. Algoritmes

 

★ Aan de slag 4 (verdiepen)

  1. In de TED-presentatie van de Amerikaan Kevin Slavin heeft Slavin het over “writing the unreadable”.
    Wat bedoelt hij hiermee?
  2. In dezelfde presentatie gaat Slavin in op de snelheid van een algoritme.
    In welke beroepsgroep is de snelheid van een algoritme van groot belang?
  3. Lees de Wikipedia-pagina over de film “The Imitation Game”.
    Beschrijf in het kort waar de film over gaat
  4. Noem twee onjuistheden die in de film verwerkt zijn.

C Informatie

Vorm en betekenis

Een belangrijk maar ook lastig begrip in de informatica is informatie.
Het woord informatie wordt niet overal in de informatica en ICT op dezelfde manier gebruikt.
Wij hanteren hier de volgende omschrijving:

Informatie bestaat uit vormen, en een manier om die vormen betekenis te geven.
Het bepalen van een vorm voor een betekenis noemen we representeren; het bepalen van de betekenis van een vorm noemen we interpreteren.

Informatie: vorm en betekenis

 

Onder ICT verstaan we de informatie- en communicatietechnologie en de toepassingen daarvan, hardware en software; informatica is de onderliggende wetenschap, waarin de meer fundamentele en tijdloze concepten bestudeerd worden.


“Vorm” betekent hier “uiterlijke verschijning” in de meest brede zin; ook kleuren, geluiden, gebaren, geuren enz. vallen hieronder.
Voor de vorm heb je een fysieke drager nodig - bijvoorbeeld voor een tekst heb je papier en inkt nodig, voor geluid trillende lucht. Deze drager draagt bij aan de vorm, maar niet aan de betekenis.

Voorbeelden:

  • een natuurlijke taal zoals Nederlands of Engels bepaalt een groot aantal vormen, van elementaire tot samengestelde vormen: klanken, woorden, zinnen. De taal geeft bovendien een manier om de betekenis van deze vormen te bepalen.
  • we interpreteren de vorm “13” als het getal “….. ….. …”
  • een bij interpreteert de kleur en vorm van een bloem als: daar is nectar te halen.
  • feromonen zijn geurstoffen die informatie overdragen tussen soortgenoten. Niet-soortgenoten ontvangen deze stoffen ook, maar hebben geen manier om daar betekenis aan te geven.

Als je met computers werkt, is het belangrijk om vorm en betekenis te onderscheiden. Computers werken met vormen, op een erg letterlijke manier. Als mens ben je gewend om een vorm direct betekenis te geven: vaak ben je je er niet eens van bewust dat je de stap van vorm naar betekenis maakt.

★ Aan de slag 5

1. Wat betekent het proces van representeren in de context van informatica?

  1. Het kiezen van een geschikte manier om data te structureren.
  2. Het bepalen van een vorm om een bepaalde betekenis te overbrengen.
  3. Het installeren van software om gegevens te analyseren.
  4. Het testen van een programma op eventuele fouten.

 

2. Wat houdt het interpreteren van informatie in binnen de informatica?

  1. Het vertalen van gecodeerde gegevens naar bruikbare informatie.
  2. Het schrijven van code in een efficiënte programmeertaal.
  3. Het debuggen van software om problemen te vinden en op te lossen.
  4. Het ontwerpen van een interface voor gebruikersinteractie.

 

3. Wat wordt bedoeld met de term "vorm" in de context van informatieverwerking?

  1. De fysieke drager van informatie, zoals papier en inkt of trillende lucht.
  2. De uiterlijke verschijning van informatie, zoals kleuren, geluiden en gebaren.
  3. De fundamentele concepten van informatica en technologie.
  4. De hardware en software die gebruikt worden in informatie- en communicatietechnologie.

 

4. Waarom is het belangrijk om vorm en betekenis te onderscheiden bij het werken met computers?

  1. Omdat computers alleen met vormen werken en geen betekenis kunnen toekennen.
  2. Omdat computers zowel vormen als betekenissen kunnen onderscheiden.
  3. Omdat menselijke interpretatie nodig is om hardware te laten functioneren.  
  4. Omdat fysieke dragers niet relevant zijn voor digitale informatieverwerking.

★ Aan de slag 6

Informatie gaat verloren als de vorm verloren gaat, of als de manier om die vorm betekenis te geven verloren raakt.

  1. Geef drie voorbeelden van verlies van informatie doordat de vorm verloren gaat.
  2. Geef drie voorbeelden van dit laatste. (Enkele hints: Voynich; 5 1/4 inch; WordStar).

★ Aan de slag 7

Niet alle aspecten van een vorm dragen op eenzelfde manier bij aan de betekenis.
Geef aan wat de mogelijke betekenissen zijn van de volgende vorm-keuzes in (gedrukte) tekst:
lettertype (font); cursieve letters; vette letters; hoofdletters; gekleurde letters.

Hello World

Hello World

Hello World

HELLO WORLD

Hello World

 

 

★ Aan de slag 8

Sommige woorden in het Nederlands klinken hetzelfde maar hebben verschillende betekenissen:
dit zijn homoniemen.
Een voorbeeld is vorst: dit kan zowel een heerser zijn als een afleiding van vriezen. (“Vorst aan de grond.”)

  1. Geef 3 voorbeelden van homoniemen.
  2. Hoe weet je welke betekenis je moet kiezen?

★ Aan de slag 9

Welke fysieke dragers heb je nodig voor de onderstaande vormen?

  • stopteken bij een kruispunt
  • kenteken van een auto

Afspraken

Lewis Carroll

Het verband tussen vorm en betekenis is een kwestie van afspraak (conventie). Fysische noodzaak (natuurkundige wetten) of logische noodzaak (wiskunde regels) spelen daarbij geen rol. Je hebt een grote vrijheid bij de keuze van een vorm voor een betekenis; het is vaak de traditie die deze vrijheid inperkt.

“When I use a word,” Humpty Dumpty said, in rather a scornful tone, “it means just what I choose it to mean—neither more nor less.” “The question is,” said Alice, “whether you can make words mean so many different things.” “The question is,” said Humpty Dumpty, “which is to be master—that’s all.”

LEWIS CARROLL (Charles L. Dodgson), Through the Looking-Glass, chapter 6, p. 205 (1934). First published in 1872.

Voorbeelden:

  • met de vorm 12,395 bedoelen we in Nederland een getal tussen 12 en 13. In de VS staat dit voor een getal tussen 12000 en 13000. (In Nederland vertalen we "floating point" met "zwevende komma".)
  • met 3/4/2019 bedoelen we in Nederland: 3 april 2019; in de VS staat dit voor 4 maart. (Vandaar ook 3/14/2019: pi-day; in Nederland kun je dat vorm-grapje niet maken.)
  • in een elektronische schakeling gebruiken we vaak de spanning 0V voor een logische 0, en de spanning 5V voor een logische 1 (“positive logic”). Maar we kunnen ook het omgekeerde gebruiken: 0V voor 1 en 5V voor 0 (negative logic); soms gebruiken we in een schakeling beide afspraken (“mixed logic”). Dit kan tot eenvoudiger schakelingen leiden.

 

★ Aan de slag 10

De notatie 1010 kan verschillende getallen voorstellen:
Wat betekent dit in decimale notatie, in hexadecimale notatie, en in binaire notatie?
Hoe weet je welke betekenis je moet kiezen?

★ Aan de slag 11

Humpty Dumpty

1. In 1872 wordt het boek Through the Looking-Glass van Lewis Caroll gepubliceerd.
Het boek is een vervolg op Alice Adventures in Wonderland.
In Through the Looking-Glass verplaatst Alice zich door een spiegel en komt terecht in een fantasierijk wereld.
In een van de passages in het boek voert Alice een gesprek met het personage Humpty Dumpty.
Humpty Dumpty is een fictief figuur uit een Engelstalig bakerrijm en wordt vaak afgebeeld als een ei.
Alice merkt op dat Humpty Dumpty er precies als een ei uitziet.
Humpty Dumpty ervaart dat als beledigend en zegt “my name means the shape I am”.

Wat wil Humpty Dumpty hier mee zeggen?

 

2. Het Hexadecimaal systeem:
In de informatica wordt vaak het hexadecimale systeem gebruikt als alternatief voor het binaire of decimale systeem. 
a) Leg uit waarom het hexadecimale systeem handig is in de context van computerwetenschappen. 
b) Kun je vier gebieden bedenken waar het hexadecimaal systeem gebruikt wordt in de dagelijkse praktijk.

Handige vormen

Zoals eerder gezegd, hebben we een grote vrijheid in het kiezen van vormen voor het uitdrukken van een bepaalde betekenis. Vaak laten we ons daarbij leiden door de traditie (conventie).
Maar niet alle vormen zijn even “handig”. Zoals we zullen zien, is rekenen het werken met vormen (“schuiven met vormen”). Sommige vormen zijn handiger om mee te werken dan andere.

Voorbeeld: voor het rekenen met getallen is de decimale notatie veel handiger dan de romeinse notatie.
Probeer uit je hoofd eens op te tellen: 123 + 488 of CXXIII + CDLXXXVIII.

Symbool: Waarde:
I 1
V 5
X 10
L 50
C 100
D 500
M 1000

 

Voor een computer is de binaire vorm van getallen weer handiger dan de decimale vorm.

In de informatica en ICT, en in het algemeen bij het oplossen van problemen, speelt het vinden van handige vormen (representaties) een grote rol. Bij het onderdeel Algoritmen en datastructuren komt dit uitgebreider aan bod. Een probleem is soms al half of bijna helemaal opgelost door een keuze van een handige vorm.

Analoge en digitale vormen

Een analoge vorm is gelijkvormig aan het origineel.
Een voorbeeld is een analoog elektrisch geluidssignaal: dit heeft dezelfde trillingen als het oorspronkelijke geluid.
Je kunt geluid eenvoudig omzetten in een analoog elektrisch signaal - met een microfoon; of omgekeerd, met een luidspreker.
Ook de vorm van de groef op een grammofoonplaat (“vinyl”) is analoog aan de oorspronkelijke geluidstrilling.

Een analoge vorm zoals het elektrische geluidssignaal is gewoonlijk continu (aaneensluitend): tussen elk tweetal waarden bestaan er in principe oneindig veel waarden.

Analoog signaal


Digitaal betekent “aftelbaar” (op je vingers), of “uit te drukken in gehele getallen”. De essentie is dat je een eindig aantal afzonderlijke waarden gebruikt. Dit noemen we ook wel discrete waarden. Voordat je een analoge vorm kunt gebruiken in een digitaal systeem moet je dit eerst omzetten in discrete waarden.

Van analoog naar digitaal


Het analoge signaal bemonsteren we op discrete tijdstippen (sampling): discretisatie in de tijd.
Elk monster (sample) zetten we om in een discrete waarde (kwantisatie).
Deze gekwantiseerde waarden benaderen het oorspronkelijke signaal: hoe kleiner de resolutie van de kwantisatie, des te groter zijn de fouten in deze benadering. Het resultaat is een reeks gehele getallen als digitale vorm van het analoge signaal.
Deze reeks getallen kun je ook voorstellen als een reeks bits. In het geval van een CD vind je deze terug in de aan- en afwezigheid van putjes in het oppervlak.

 

★ Aan de slag 12

In de tekst wordt besproken hoe bepaalde notaties handiger zijn voor specifieke toepassingen, zoals het decimale systeem voor rekenen en het binaire systeem voor computers. Het hexadecimaal systeem is vergelijkbaar in zijn handigheid, omdat het een compacte en efficiënte manier biedt om kleuren weer te geven in webdesign.

1. Waarom is het hexadecimaal systeem handig voor het weergeven van kleuren in webdesign?

  1. Omdat het korter is dan het binaire systeem en eenvoudiger te begrijpen voor programmeurs.
  2. Omdat het minder geheugen gebruikt dan het decimale systeem.
  3. Omdat het direct overeenkomt met de RGB-kleurwaarden en compact weergegeven kan worden.
  4. Omdat het door de Romeinen werd gebruikt voor het maken van mozaïeken.

 

Het MAC-adres staat voor Media Access Control Address en betreft een uniek identificatienummer dat helpt bij het volgen van jouw apparaat in een netwerk. Elke netwerkkaart, zoals een ethernet- of wifi-kaart, krijgt vanuit de fabriek een MAC-adres toegewezen.

2. Wat is een voorbeeld van een conventie die wordt gebruikt voor het weergeven van MAC-adressen?

  1. Acht groepen van vier hexadecimale cijfers gescheiden door dubbele punten.
  2. Twee groepen van zes decimale cijfers gescheiden door komma's.
  3. Zes groepen van twee hexadecimale cijfers gescheiden door dubbele punten.
  4. Vier groepen van drie binaire cijfers gescheiden door streepjes.

 

Bestudeer de uitleg over analoog-digitaal omzetting voor bijvoorbeeld muziek.

3. Wat bepaalt de nauwkeurigheid waarmee het oorspronkelijke analoge geluidssignaal wordt benaderd?

4. Wat is het verschil tussen geluid in PCM-formaat en in MP3-formaat?

 

5. Welke van de volgende beweringen is waar over analoge signalen?

  1. Ze gebruiken discrete waarden om informatie weer te geven.
  2. Ze worden alleen gebruikt in moderne technologieën zoals smartphones.
  3. Ze zijn gewoonlijk continu en kunnen oneindig veel waarden tussen twee punten hebben.
  4. Ze kunnen niet worden omgezet naar digitale signalen.

6. Hoe noemen we het proces waarbij een analoog signaal omgezet wordt in discrete waarden?

  1. Kwantisatie
  2. Digitalisatie
  3. Bemonstreren
  4. Continuering

 

Gebruik de onderstaande informatie en gegevens om een analoog geluidssignaal om te zetten in een digitaal signaal. Voer de stappen uit en geef de resultaten weer in een tabel.

Informatie bij de vraag:
Geluidsgolven zijn trillingen in de lucht die door het menselijk oor worden waargenomen als geluid. Elke geluidsgolf heeft een frequentie, golflengte en amplitude, waarbij de amplitude de luidheid van het geluid bepaalt. Geluidsgolven variëren continu, wat betekent dat ze analoog zijn. Computers kunnen echter niet werken met analoge gegevens, dus moeten geluidsgolven worden bemonsterd om in een computer te worden opgeslagen.

Het bemonsteren betekent het meten van de amplitude van de geluidsgolf op regelmatige tijdsintervallen, waarbij gebruik wordt gemaakt van een analoog-naar-digitaal converter (ADC). Bij het omzetten van analoge gegevens naar digitaal worden de geluidsgolven bemonsterd op vaste tijdsintervallen en worden de amplitude-waarden opgeslagen als benaderingen.

Bron data:
De onderstaande tabel toont de amplitudes van een geluidsgolf op verschillende tijdsintervallen. Het amplitude-bereik ligt tussen 0 en 10, en kan worden weergegeven met 4 binaire bits.

Tijdsinterval Amplitude
1 10
2 4
3 7
4 1
5 0
6 1
7 4
8 7
9 10
10 7
11 4
12 1
13 0
14 1
15 4
16 7
17 10
18 7
19 4
20 1
21 0

 

Zet de bovenstaande geluidsgolf om naar een digitaal signaal door de volgende stappen uit te voeren:

 

  • Bemonster de geluidsgolf op 10 tijdsintervallen (1, 3, 5, 7, 9, 11, 13, 15, 17, 19).
  • Geef de benaderde amplitude-waarden weer voor elk tijdsinterval.
  • Zet elke amplitude-waarde om in een binaire waarde met een resolutie van 4 bits.
  • Verklaar kort hoe een hogere bemonsteringsfrequentie of grotere resolutie zou leiden tot een meer nauwkeurige weergave van het oorspronkelijke geluidssignaal.

Voorbeeld:

Tijdsinterval 1: Amplitude 10 -> Binair 1010
Tijdsinterval 3: Amplitude 7 -> Binair 0111

7. Gebruik de data om de amplitude-waarden te bepalen en geef je antwoord in de onderstaande tabel:

Tijdsinterval Amplitude Binair (4 bits)
1 10 1010
3 7 111
5    
7    
9    
11    
13    
15    
17    
19    

 

Analoog-digitaal omzetting

Een ander voorbeeld van omzetting van analoog naar digitaal vind je in een digitale camera: deze zet het oorspronkelijke beeld om in een groot aantal discrete pixels.
Het omgekeerde gebeurt bij een display, waar het beeld gevormd wordt door een groot aantal pixels.

Ook je ogen gebruiken een dergelijke discretisatie: het beeld wordt opgebouwd met behulp van een eindig aantal staafjes en kegeltjes.
Je kunt met een digitale vorm een analoge vorm willekeurig goed benaderen een groot aantal discrete waarden te gebruiken.
Je krijgt een getrouwer beeld door een groter aantal pixels te gebruiken.
Het heeft voor een beeldscherm geen zin om meer pixels te gebruiken dan je oog kan waarnemen.

Je kunt deze discrete waarden ook gebruiken voor symbolische vormen.
Een symbolische vorm staat voor een bepaalde betekenis, maar hoeft er helemaal niet op te lijken.
Zo staat het teken A in het Nederlandse alfabet voor een bepaalde klank, maar dit is puur een kwestie van afspraak.
Het teken P staat in het Nederlandse (Latijnse) alfabet voor een andere klank dan in het Russische (Cyrillische) alfabet.

Computers werken met symbolische vormen. Rekenen, zoals we verderop zullen zien, is “spelen met symbolische vormen”.
Deze symbolen kunnen van alles voorstellen: getallen, geluiden, teksten, kleuren, ideeën, enz..
Dit “spelen met symbolische vormen” kom je niet alleen in digitale computers tegen: in de levende natuur is dit overal te vinden, en in het bijzonder mensen zijn er erg goed in.

Een symbolische vorm is vaak opgebouwd uit elementaire symbolen.
Bijvoorbeeld: een tekst is een reeks lettertekens, een getal schrijven we als een reeks cijfers.
Deze elementaire symbolen noemen we vaak het alfabet van de betreffende vormentaal.

De elementaire symbolen in een alfabet kunnen we nummeren, bijvoorbeeld A=1, B=2, C=3, enzovoorts.
We kunnen een symbolische vorm die opgebouwd is uit elementaire symbolen dan weergeven als een reeks getallen.
De tekst "HELLO" wordt dan (8, 5, 12, 12, 15). Omdat dit soort omzettingen erg eenvoudig is, gebruiken we deze vormen door elkaar, zoals het handig uitkomt.
We beschouwen "HELLO" dan ook als een digitale vorm.

Voorbeelden van symbolische vormen(-talen):

  • DNA, met alfabet A, C, G,T
  • tekst, met alfabet A, B, .. Z (en tegenwoordig ook leestekens)
  • getallen, in decimale notatie, met alfabet 0, 1, .., 9
  • bits, met alfabet 0, 1

Al deze talen zijn in principe gelijkwaardig, en universeel: je kunt deze in elkaar uitdrukken, en je kunt er alles in uitdrukken.

Zie bijvoorbeeld Digital DNA Storage, hoe je DNA kunt gebruiken als opslagmedium voor teksten en andere data. En omgekeerd gebruiken we moderne computers om DNA-structuren in op te slaan.

De huidige digitale computers zijn gemaakt met elektronica met 0 en 1 als alfabet.
Dit is een praktische keuze; in principe zijn andere computers, met andere alfabetten, en met andere technologie (mechanisch, chemisch, …) mogelijk.
Dit verandert niets aan de fundamentele mogelijkheden en beperkingen.

Alle aspecten die we in deze module grondslagen behandelen zijn universeel, en niet gebonden aan digitale elektronica.

★ Aan de slag 13

  1. Geef een aantal voorbeelden van analoge vormen.
  2. Geef aan wat de overeenkomst is tussen de vorm en het origineel.
  3. Wat gebeurt er bij een digitale camera met het originele beeld?
    1. Het beeld wordt omgezet in een analoog signaal.
    2. Het beeld wordt omgezet in een groot aantal discrete pixels.
    3. Het beeld wordt weergegeven met een groter aantal kleuren.
    4. Het beeld wordt direct naar een display gestuurd zonder enige omzetting.
  4. Waarom heeft het geen zin om meer pixels te gebruiken op een beeldscherm dan je oog kan waarnemen?
    1. Omdat het beeld dan wazig wordt.
    2. Omdat de computer de extra pixels niet kan verwerken.
    3. Omdat het geen extra details toevoegt die het oog kan waarnemen.
    4. Omdat de kleuren onnauwkeurig worden weergegeven.

★ Aan de slag 14

Geef een aantal voorbeelden van symbolische vormen die al bestonden voor de komst van de computer.

★ Aan de slag 15

Welke van de onderstaande vormen zijn analoog, welke symbolisch?

  • foto
  • stripboek
  • leesboek
  • draaiorgelboek
  • langspeelplaat (“vinyl”)
  • verkeersbord

★ Aan de slag 16

Computers werken met vormen op een erg letterlijke manier.
Wat wordt hiermee bedoeld?

Informatie stuurt

Een Arduino waarop enkele ledjes
zijn aangesloten

Een mogelijke definitie van informatie zou kunnen zijn:

informatie is wat de levende natuur richting geeft - in afwijking van de wetten van de natuur- en scheikunde.

Deze definitie geeft aan dat sturen een wezenlijk kenmerk van informatie is.
Dit sturen vind je op allerlei niveaus:

  • het aansturen van spieren door zenuwen;
  • het sturen van groeiprocessen door genetische informatie;
  • het besturen van een fiets of een auto;
  • het besturen van een bedrijf of andere organisatie;
  • het besturen van een ledstrip met een Arduino.

Informatie stuurt: op grond van informatie nemen mensen beslissingen die uiteindelijk leiden tot actie.
Deze actie kan pas veel later plaatsvinden - mogelijk zelfs vele eeuwen later:
mensen laten zich nog steeds inspireren door informatie van duizenden jaren geleden.

Dit sturen vinden we ook in computers:

  • het programma in een computer stuurt de manier waarop de invoer verwerkt wordt;
  • de combinatie van invoer en het programma bepaalt de uitvoer van deze verwerking;
  • het operating system bestuurt welke programma's op welk moment actief mogen zijn, en hoe deze het geheugen en de randapparaten mogen gebruiken; enz.

Informatie en data

Uithangbord Post Telegraaf ©Agaath

We hebben hiervoor gezien dat informatie een combinatie is van vormen en een manier om die vormen betekenis te geven.
Als de nadruk ligt op de vormen spreken we over data.
Als de betekenis van belang is, spreken we over informatie.

Communicatietechnologie is gericht op het transporteren van vormen: datatransport.
Hierbij moet de ontvanger de vorm ontvangen zoals de afzender deze verstuurd heeft, zonder vervorming.
Bij dit transport speelt de betekenis van deze vormen geen enkele rol. (Bij de PTT (nu: PostNL) gebruikte men vroeger de leus: wij hebben geen boodschap aan de boodschap.)


Ook bij het reproduceren van vormen speelt de betekenis geen rol.
Een kopieermachine reproduceert zo getrouw mogelijk de vlekjes op het papier, maar de betekenis van die vlekjes is voor het kopieerproces niet van belang.

Bij het opslaan en terugzoeken van informatie gaat het alleen om de vorm: dataopslag en databases.
Bij een database gebruik je een deel van de vorm om een meer complete vorm terug te vinden.

Vergelijk ook het opzoeken van de betekenis van een woord in een woordenboek: je zoekt aan de hand van de vorm van het woord naar een uitgebreidere vorm die de betekenis beschrijft.
Het woordenboek bevat alleen vormen (letters/woorden/zinnen), je moet hier zelf betekenis aan geven.

★ Aan de slag 17

1. Wanneer spreken we van data en wanneer van informatie?

© Dall-E

 

2. Kijk naar de bovenstaande afbeeldingen en kies welke afbeelding het beste illustreert hoe informatie een beslissingsproces stuurt.

  1. Afbeelding 1: Een persoon die een fiets bestuurt op basis van een signaal.
  2. Afbeelding 2: Een Arduino die een LED-strip aanstuurt.
  3. Afbeelding 3: Een persoon die een woord in een woordenboek opzoekt.
  4. Afbeelding 4: Een persoon die informatie opzoekt in een boek met behulp van een vergrootglas.

★ Aan de slag 18

Bij de PTT gebruikte men vroeger de leus: wij hebben geen boodschap aan de boodschap.
De PPT, het Staatsbedrijf der Posterijen, Telegrafie en Telefonie, werd in 1989 verzelfstandigd en ging in dat jaar verder onder de naam KPN.
In 1998 splitste het zich af als TPG, waarna het vanaf 2011 PostNL heet.

1. Wat zou bedoeld worden met de leus “Wij hebben geen boodschap aan de boodschap”?

 

2. Je gaat belangrijke persoonlijke informatie bespreken

  1. Benoem belangrijke persoonlijke informatie:
  2. Gebruik van Gegevens door Andere Partijen:

Informatieprocessen

Bladmuziek

Een vorm is statisch: deze verandert niet in de tijd.
Voorbeelden hiervan zijn: een boek, een vel bladmuziek, een CD (muziekdrager), een videobestand en een programmabestand.

We gebruiken vormen vaak in processen, waarmee we vormen omzetten in andere vormen, of waarmee we fysische processen besturen.
Een proces is dynamisch: dit speelt zich af in de tijd. (Zo mogelijk gebruiken we voor een proces een werkwoord.)

Voorbeelden van statische data en enkele bijbehorende processen:

  • boek - lezen van een boek, schrijven van een boek
  • film - kijken van een film
  • muziekstuk - spelen van een muziekstuk, beluisteren van een muziekstuk
  • programma - uitvoeren van het programma

Enkele voorbeelden van informatieprocessen:

  • opslaan en terugzoeken
  • kopiëren/reproduceren
  • communiceren
  • rekenen
  • leren
  • besturen

★ Aan de slag 19

1. Wat is een voorbeeld van een statische vorm?

  1. Lezen van een wetenschappelijk artikel
  2. Een digitale foto
  3. Kijken van een documentaire
  4. Luisteren naar een podcast

 

2. Welke van de volgende activiteiten is een dynamisch proces?

  1. Een schilderij
  2. Een rekenblad (spreadsheet)
  3. Verzenden van een e-mail
  4. Een software-handleiding

 

3. Welke van de volgende opties is een voorbeeld van een informatieproces?

  1. Een digitale afbeelding
  2. Bewerken van een video
  3. Een muziekbestand
  4. Een geprinte handleiding

 

D Bomen

Voorbeeld: file system

Een belangrijke structuur die je overal in de informatica tegenkomt, is de boom.
Dit is een recursieve structuur: de structuur van de delen is gelijk aan de structuur van het geheel, zoals bij een boom in de natuur: een tak heeft dezelfde structuur als de boom.

Een boom: knoop A is de wortel (de boom is dus op de kop getekend), B, C en D zijn de kindknopen van ouderknoop A.
B heeft 0 kinderen, C heeft er 2, en D 1.


Je kunt in een boom niveaus onderscheiden: de kinderen van een knoop zijn ondergeschikt aan die ouderknoop.
Dit betekent dat je met een boom een hiërarchische structuur kunt weergeven.
Voorbeelden hiervan zijn:
een hiërarchisch bestandssysteem (file system), een tekst (boek met hoofdstukken en secties), een HTML-document en een organisatieschema.

Als je een boom handig organiseert, als zoekboom, dan kun je in een boom ook erg efficiënt zoeken.
Een voorbeeld daarvan is een binaire zoekboom.

Met een ontleedboom maak je de syntactische structuur van een (lineaire) zin duidelijk.
Aan de hand van deze structuur bepaal je de betekenis van deze zin.
Voorbeelden hiervan komen we tegen bij natuurlijke talen en bij formele talen zoals programmeertalen.

Een voorbeeld van een boomstructuur is een hiërarchisch file system, zoals je dat bijvoorbeeld tegenkomt bij operating systems als Windows, OS X, en Linux (Unix).
In zo’n file system is een bestand òf een “normaal” bestand, òf een map met bestanden.
Een bestand in een map kan dan ook zelf weer een map met bestanden zijn (recursie).


Een hiërarchisch file system: a, d en e zijn mappen, b.txt enz. zijn gewone bestanden.


Met behulp van zo’n hiërarchisch file system kun je je bestanden op een logische manier organiseren, bijvoorbeeld in een map per project.
De bestanden van een project kun je weer onderverdelen in documentatie, broncode, projectadministratie, e.d.

★ Aan de slag 20

1. Voor de organisatie van data maken computers gebruik van een file system.
Zoek op internet naar de betekenis van "file system".

© Dall-E

2. Kijk naar de afbeelding van een hiërarchisch bestandssysteem.
Welke van de volgende uitspraken is waar over de structuur van een bestandssysteem?

  1. Elk bestand kan meerdere ouders hebben.
  2. Een Windows map kan zowel bestanden als andere mappen (submappen) bevatten
    Notabene: Deze submappen zijn NIET zichtbaar op de afbeelding.
  3. Alle bestanden moeten direct onder de root-map staan.
  4. Bestanden kunnen niet in mappen worden ondergebracht.

3. Kijk nogmaals naar de bovenstaande afbeelding.
Welke van de volgende kenmerken beschrijft het beste een binaire zoekboom?

  1. Elke knoop heeft exact drie kinderen.
  2. Elke knoop heeft ten minste één kind.
  3. Elke knoop heeft maximaal twee kinderen.
  4. Elke knoop heeft geen kinderen.

4. Kijk nogmaals naar de bovenstaande afbeelding.
Hoe wordt de hiërarchie in een organisatieschema weergegeven?

  1. Elk niveau is onafhankelijk en heeft geen ondergeschikten.
  2. Hogere niveaus geven richting aan de lagere niveaus.
  3. Alle niveaus hebben dezelfde autoriteit en verantwoordelijkheden.
  4. Lagere niveaus geven richting aan de hogere niveaus.

 

★ Aan de slag 21

Een recursieve structuur is een structuur waarbij één of meer delen dezelfde structuur hebben als het geheel. In de informatica zie je bij bomen deze recursieve structuur terug.
Bekijk de onderstaande afbeelding van een voorbeeld van een boom en leg aan de hand van de afbeelding uit wat een recursieve structuur is.

Paden in een boom

Het beginpunt van de boom, bijvoorbeeld de map op het hoogste niveau, noemen we de wortel of root. In Linux spreek je over de root directory, aangegeven als /.

Het kind b.txt van knoop a geef je aan met de padnaam a/b.txt. Meer algemeen kunnen we een bestand in een hiërarchisch filesysteem aanduiden door het pad van de wortel (root directory) naar het bestand. Dit heet de absolute padnaam. Als a een map is in de root directory, dan vormt /a/d/f.txt de absolute padnaam van het bestand f.txt. Een padnaam die niet begint met de wortel is een relatieve padnaam. Voorbeeld: d/f.txt is de relatieve padnaam van f.txt gerekend vanuit a.

             Padnamen kom je ook tegen in URL's in het web.

De bovenliggende map noem je de ouder-knoop: de parent directory. Deze geef je in Linux (of Unix, OS X) aan als “..” . Ook deze kun je in een padnaam gebruiken: vanuit map d geeft ../c.txt het pad naar c.txt. In dit geval is er sprake van een relatieve padnaam.

Een file system als horizontale boom


Een andere manier om een boomstructuur weer te geven is horizontaal: de wortel staat dan links boven, en de kinderen ingesprongen daaronder. Soms is het mogelijk om een subboom in- en uit te klappen.

Merk op dat een map leeg kan zijn: deze bevat dan geen mappen of gewone bestanden.

★ Aan de slag 22

1. Zoek voorbeelden van een horizontale weergave van een boom.
Let bijvoorbeeld op het gebruik van inspringen en in- en uitklappen.

 

2. Welke van de volgende uitspraken zijn juist over padnamen in een hiërarchisch bestandssysteem? (Meerdere antwoorden zijn correct)

  1. Een absolute padnaam begint altijd met de root directory.
  2. Een relatieve padnaam begint altijd met de root directory.
  3. Een absolute padnaam geeft het volledige pad van de root naar het bestand.
  4. Een relatieve padnaam begint altijd met "/".

3. Welke van de volgende kenmerken beschrijven een hiërarchisch bestandssysteem correct? (Meerdere antwoorden zijn correct)

  1. De wortel of root is het beginpunt van de boom.
  2. Een map kan geen andere mappen bevatten, alleen bestanden.
  3. Een map kan zowel bestanden als andere mappen bevatten.

  4. ) Een horizontale weergave van een boomstructuur toont de wortel links boven met de kinderen ingesprongen daaronder.

★ Aan de slag 23

Gegeven is de voorbeeldfiguur met mappen en bestanden hierboven, waarbij de map a bevat is in de root-directory.

  1. Wat zijn de relatieve padnamen van b.txt en g.txt, vanuit a gerekend?
  2. Wat zijn de absolute padnamen van b.txt en g.txt?
  3. De mappen en bestanden worden uitgebreid met a/x/y.txt. Pas de figuur hiervoor aan.
  4. Geef de relatieve padnaam van y.txt vanuit e gerekend.
  5. Er wordt een bestand a/d/g.txt toegevoegd. Geef de relatieve padnaam van dit toegevoegde bestand vanuit e gerekend.

★ Aan de slag 24

  1. Maak in het Operating System op je computer de bestanden aan volgens de structuur van de voorbeeld-figuur.
  2. Maak een schermafdruk waarin je deze structuur weergeeft.

★ Aan de slag 25

  1. Zoek uit wat een outline editor is (voor tekstdocumenten).
  2. Welke mogelijkheden biedt de tekstverwerkingsprogramma’s die je gebruikt om met de outline te werken?

Voorbeeld: HTML

HTML-structuur
HTML (HyperText Markup Language) is de opmaaktaal die wordt gebruikt om webpagina's te maken. Het document wordt georganiseerd in een boomstructuur (DOM - Document Object Model) met elementen als knopen (nodes). Bijvoorbeeld, een eenvoudige HTML-structuur kan er als volgt uitzien:

html
<html>
      <head>
          <title>Mijn webpagina</title>
      </head>
     <body>
             <h1>Welkom</h1>
             <p>Dit is een paragraaf</p>
      </body>
</html>

 

Opmaak en CSS
CSS (Cascading Style Sheets) wordt gebruikt om de opmaak en lay-out van HTML-documenten te beschrijven. De term "cascading" verwijst naar hoe opmaakregels worden toegepast en geërfd door de elementen in de HTML-structuur. Bijvoorbeeld:

body {
   font-family: Arial, sans-serif;
   color: black;
}

h1 {
   color: blue;
}

Wanneer een stijl op een ouderknoop (bijvoorbeeld <body>) wordt toegepast, erven de kindknopen (zoals <h1> en <p>) deze stijl, tenzij er specifiek andere stijlen voor de kindknopen zijn gedefinieerd.

JavaScript en de DOM
DOM (Document Object Model):


De DOM is een programmeerbare object-georiënteerde representatie van de HTML-documenten. Het wordt door de browser gegenereerd en kan gemanipuleerd worden met JavaScript om de inhoud en de structuur van de webpagina dynamisch te veranderen.

In de DOM wordt elk HTML-element als een object (knoop) gerepresenteerd, en de boomstructuur van de HTML wordt nagebootst. Bijvoorbeeld:

html
     <body>
             <h1>Welkom</h1>
             <p>Dit is een paragraaf</p>
      </body>

Wordt in de DOM als een boomstructuur gerepresenteerd:

css

body
├── h1
└── p

JavaScript en de DOM manipulatie:

Met JavaScript kun je de DOM manipuleren door elementen toe te voegen, te verwijderen of te wijzigen. Dit zorgt ervoor dat je webpagina's dynamisch kunt maken. Bijvoorbeeld:

javascript
// Selecteer het h1 element
const heading = document.querySelector('h1');

// Verander de tekst van het h1 element
heading.textContent = 'Hallo Wereld';

// Voeg een nieuwe paragraaf toe
const newParagraph = document.createElement('p');
newParagraph.textContent = 'Dit is een nieuwe paragraaf.';
document.body.appendChild(newParagraph);

Wanneer je deze JavaScript code uitvoert, zal de browser de wijzigingen weergeven door de huidige staat van de DOM te tonen.

Kortom, de structuur van een HTML-document en het "cascading" aspect van CSS zijn essentieel voor de opmaak en weergave van webpagina's. Met JavaScript kun je vervolgens de DOM manipuleren om dynamische en interactieve webpagina's te creëren.

★ Aan de slag 26

Bestudeer hoe in een project voor een website de bestanden georganiseerd zijn (bijvoorbeeld via GitHub). Geef een beschrijving van de gebruikte aanpak.

★ Aan de slag 27

Als een webpagina wordt geladen in een browser, dan maakt de browser een Document Object Model (DOM) van die pagina.
Hieronder zie je een onvolledig DOM van de html-pagina welkom.html.

Neem dit model over en vul de ontbrekende onderdelen aan.

★ Aan de slag 28

Een HTML DOM model wordt opgebouwd als een boom die bestaat uit objecten.
Hoeveel objecten tref je aan in het DOM model dat gemaakt is op basis van de pagina welkom.html?

★ Aan de slag 29

1. Met behulp van de webontwikkelaar-hulpmiddelen van de browser kun je de DOM als “horizontale boomstructuur” te zien krijgen.
Deze vind je in Firefox via het menu Extra → Webontwikkelaar → Inspector.
Vergelijk voor een eenvoudige webpagina deze structuur met de HTML-broncode (Extra → Webontwikkelaar → Paginabron).
Pas via de inspector een tekstelement in de DOM aan, voor een bekende website (bijvoorbeeld van je school), met een onwaarschijnlijke tekst, en maak een schermafdruk van het resultaat.

2. Maak van de volgende HTML code van een nieuwssite een boomstructuur zoals beschreven in de tekst van deze paragraaf:
<!DOCTYPE html>
<html lang="nl">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Krant</title>
</head>
<body>
    <header>
        <h1>Dagelijkse Krant</h1>
        <nav>
            <ul>
                <li><a href="index.html">Home</a></li>
                <li><a href="politiek.html">Politiek</a></li>
                <li><a href="sport.html">Sport</a></li>
                <li><a href="cultuur.html">Cultuur</a></li>
            </ul>
        </nav>
    </header>
    <main>
        <section id="home">
            <h2>Welkom bij de Dagelijkse Krant</h2>
            <p>Lees het laatste nieuws hier.</p>
        </section>
        <section id="politiek">
            <h2>Politiek Nieuws</h2>
            <p>Blijf op de hoogte van de laatste politieke ontwikkelingen.</p>
        </section>
        <section id="sport">
            <h2>Sport Nieuws</h2>
            <p>Het laatste sportnieuws en resultaten.</p>
        </section>
        <section id="cultuur">
            <h2>Cultuur Nieuws</h2>
            <p>Nieuws over kunst en cultuur.</p>
        </section>
    </main>
    <footer>
        <p>&copy; 2024 Dagelijkse Krant</p>
    </footer>
</body>
</html>

★ Aan de slag 30

Voor de structuur van een webpagina wordt HTML gebruikt.
Voor de vormgeving van een webpagina worden stijlbladen gebruikt.
In het HTML-document wordt naar deze stijlbladen verwezen.
In het Engels worden deze stijlbladen Cascading Style Sheets of afgekort CSS genoemd.

Open in een browser het bestand welkom.html. Dit bestand kun je vinden onder de menukeuze Bijlagen.
Je kunt de broncode van dit bestand bekijken door het bestand in een editor te openen. (bijvoorbeeld Notepad++).

<!doctype html>
<html>
      <head>
          <title>Welcome</title>
      </head>
     <body>
             <h1>Welkom op mijn website</h1>
             <p>Dit is mijn eerste website</p>
             <p>Hier moet nog meer tekst komen</p>
      </body>
</html>

In dit bestand staat een verwijzing naar het CSS-bestand layout.css (<link rel="stylesheet" href="layout.css">). Open het CSS-bestand layout.css in bijvoorbeeld Notepad++.

body{
           color: blue;
}
hl {
}
p {
}

In de code van het CSS-bestand zie je tussen de accolades van de body de regel color: blue; staan. Daarmee geef je aan de de kleur van het lettertype blauw is. Voeg nu tussen de accolades bij h1 en p achtereenvolgens color: green; en color: red; toe. Sla het CSS-bestand op onder dezelfde naam.
Ververs in de browser de webpagina welkom.html.

  1. Welke veranderingen in de webpagina neem je waar?
  2. Kun je hier een verklaring voor geven?

 

Binaire zoekbomen

Binaire Zoekboom

Een binaire zoekboom (Binary Search Tree, BST) is een datastructuur die de efficiënte organisatie en toegang tot gegevens mogelijk maakt. Hier is hoe een BST werkt en wat de belangrijkste eigenschappen zijn:

Basisprincipes van een Binaire Zoekboom:

  1. Structuur:
    • Elke knoop in de boom heeft maximaal twee kinderen: een linker en een rechter kind.
    • In een binaire zoekboom is het maximum van de waarden in de linker subboom kleiner dan de waarde in de knoop zelf; het minimum van de waarden in de rechter subboom is ten minste (>=) de waarde in de knoop zelf..
  2. Zoekproces:
    • Stap 1: Begin bij de wortel (root) van de boom.
    • Stap 2: Vergelijk de waarde die je zoekt met de waarde in de wortel.
      • Als de waarde gelijk is, ben je klaar.
      • Als de waarde kleiner is, herhaal het proces in de linker subboom.
      • Als de waarde groter is, herhaal het proces in de rechter subboom.
    • Dit proces herhaalt zich totdat je de gezochte waarde vindt of bij een bladknoop aankomt (een knoop zonder kinderen).
  3. Zoeken en Efficiëntie:
    • Het zoeken in een BST is efficiënt als de boom gebalanceerd is. Dit betekent dat het aantal knopen in de linker en rechter subbomen van elke knoop ongeveer gelijk is.
    • In een gebalanceerde BST is het aantal stappen dat nodig is om een waarde te vinden ongeveer gelijk aan de hoogte van de boom, wat log (N). Hier staat N voor het aantal knopen in de boom.

Uitleg gebalanceerde zoekboom:

Een gebalanceerde binaire zoekboom (of balanced binary search tree, BST) is een datastructuur die ervoor zorgt dat gegevens op zo’n manier worden opgeslagen dat je er efficiënt in kunt zoeken, invoegen en verwijderen. Laten we dat stap voor stap toelichten:

Zoals gezien is een binaire zoekboom een boomstructuur waarin elke knoop (node) maximaal twee kinderen heeft: een linker en een rechter.

  • De linkerkinderen bevatten waarden kleiner dan de ouder.
  • De rechterkinderen bevatten waarden groter dan de ouder.

Bijvoorbeeld, als je 5 in de boom stopt, en daarna 3 en 7:

Wat betekent "gebalanceerd"?

Een binaire zoekboom is gebalanceerd als de hoogte van de boom ongeveer zo klein mogelijk is. Dit betekent dat het verschil in diepte tussen de linker- en rechter-subboom bij elke knoop klein is, meestal maximaal 1 of 2 niveaus verschil (afhankelijk van het type balansregel).

Waarom is dit belangrijk?

  • Omdat de hoogte van de boom bepaalt hoe snel je kunt zoeken.
  • Hoe lager de boom, hoe minder stappen je nodig hebt om een element te vinden (O(log n) tijd in het beste geval).

Voorbeeld van een ongebalanceerde boom

Als je getallen in oplopende volgorde invoegt, krijg je:


 

Dit is niet gebalanceerd – hij lijkt meer op een lijst, en zoeken duurt langer (O(n)).

Voorbeeld van een gebalanceerde boom

Als je dezelfde getallen anders organiseert:

Dan is de boom veel evenwichtiger, en zoekoperaties zijn sneller.

Samengevat

Een gebalanceerde binaire zoekboom is een datastructuur die:
In elke knoop een waarde heeft met een linkerkind (<) en rechterkind (>),
Zichzelf in balans houdt zodat zoeken snel blijft (meestal O(log n)).

Het Concept van 2log (N)

Kleine toelichting op het concept van 2log (N):

Logaritme in Basis 2:

    • Het logaritme in basis 2 (log2​) van een getal N is de macht waartoe je 2 moet verheffen om N te krijgen.
      Bijvoorbeeld, log2(1024) = 10 omdat 210 = 1024.

★ Aan de slag 31

Gegeven is de volgende zoekboom.

Binaire zoekboom


Schrijf het pad op waarmee je de knoop met waarde 73 vindt.
Idem, met waarde 43.

 

Ontleedbomen

Hieronder zie je een ontleedboom.

Ontleedboom van de expressie 3 + 5 * x


Een ontleedboom geeft de structuur van een lineaire zin in een taal weer, als de ontleding van die zin volgens de regels van de grammatica van die taal.
Deze structuur gebruik je vervolgens bij het bepalen van de betekenis van die zin.
In het gedeelte over Talen en grammatica’s gaan we daar verder op in.

 

Andere voorbeelden

Op nog veel meer plaatsen in de informatica kom je bomen tegen.
We noemen enkele voorbeelden:

  • een proces met beslissingen kun je beschrijven als een boom (decision tree): een voorbeeld hiervan zijn de verschillende zetten die je kunt doen in een schaakpartij;
  • domeinnamen in het internet, zoals rijkswaterstaat.nl, ieni.org, en  google.com, vormen een boom; deze boom wordt ook gebruikt bij het zoeken van een IP-adres bij een domeinnaam, via het DNS (Domain Name System).

★ Aan de slag 32

1. Wat is een belangrijk voordeel van het gebruik van een gebalanceerde binaire zoekboom in databases?

  1. Het vermindert de behoefte aan extra hardware.
  2. Het zorgt voor gelijkmatige toegangstijden voor zoekoperaties.
  3. Het maakt de database volledig immuun voor storingen.
  4. Het elimineert de noodzaak voor regelmatige back-ups

2. Welke van de volgende toepassingen maakt expliciet gebruik van een binaire boomstructuur?

  1. Het sorteren van emails in een e-mail inbox.
  2. Het bepalen van de route voor een navigatiesysteem.
  3. Opzoeken IP-adres bij een domeinnaam via DNS.
  4. Het schrijven van tekst in een tekstverwerker.

 

E Rekenen

Rekentechnologie

Bij rekenen denk je meestal aan het werken met getallen.
In de informatica heeft rekenen een ruimere betekenis:
rekenen is het manipuleren van vormen (“spelen met vormen”), volgens bepaalde regels.
Deze regels schrijven precies voor hoe je met de vormen manipuleert.
Zo’n voorschrift noemen we een algoritme.
Deze vormen kunnen van alles voorstellen: getallen, woorden, tekeningen, foto’s, muziek, enz.
Ook het vertalen met een computer van een zin uit het Nederlands in het Engels, of het automatisch verwijderen van rode ogen in een foto noemen we rekenen.

Aan de hand van een aantal voorbeelden proberen we dit begrip van rekenen duidelijker te maken.

Algoritmen in het dagelijks leven

Enkele begrippen rond algoritmen (en programmeren) komen we ook in het dagelijks leven tegen.

Als je een taart wilt bakken, heb je een recept nodig. In het recept staat wat je nodig hebt:
ingrediënten (bijvoorbeeld bloem en boter), en hulpmiddelen (zoals een kom, een mixer, en een oven).
Het recept geeft stap voor stap aan hoe je van de ingrediënten, met deze hulpmiddelen, een taart bakt.

Met een recept alleen gebeurt er nog niets: je hebt een kok nodig - iemand nodig die het recept kan uitvoeren. Deze heeft de bijbehorende hulpmiddelen nodig, en de ingrediënten. Daarna kan hij aan de slag gaan met het bakken van de taart.
Het uitvoeren van de verschillende stappen van het bakken kost tijd. We noemen iets dat in de tijd verloopt een proces.

Als alles goed gaat, heb je als resultaat van het bakproces een taart.
Aan de taart kun je niet meer zien hoe deze gemaakt is: welke stappen er gebruikt zijn, of hoe lang dit geduurd heeft. Maar als je de taart wilt opeten is dat ook niet je eerste vraag.

We hebben in dit voorbeeld te maken met de volgende begrippen:

  • script (algoritme, programma): stappenplan dat precies vastlegt welke stappen uitgevoerd moeten worden;
  • actor (processor): kan een script uitvoeren; dit kan een mens zijn, maar ook een machine (automaat);
  • proces - het uitvoeren van een script door een actor; bij een proces is er meestal sprake van:
  • invoer (input)
  • uitvoer (output, resultaat)
  • hulpmiddelen (resources)

Een algoritme is een handelingsvoorschrift: dit beschrijft precies welke stappen je moet nemen voor het bereiken van het beoogde resultaat.

In het dagelijks leven vinden we meer voorbeelden van scripts, processoren (actoren) en processen:

Script/Programma Proces Processor Resultaat
Recept Bakken Kok Taart
Breipatroon Breien Breimachine Trui
Routebeschrijving Reis Automobilist Bestemming bereikt
Draaiorgelboek Afspelen Draaiorgel Muziek
Optellen Rekenen Boekhouder Totaal

 

De verschillende scripts zijn geschreven voor een bepaald soort actor (processor).
Een recept is geschreven in een taal die door een kok begrepen wordt.
Als je wilt leren koken, dan moet je de receptentaal (of kokstaal) leren begrijpen.

Een algoritme beschrijft precies de stappen die je moet nemen om het gewenste resultaat te bereiken. Als de beschrijving precies genoeg is en voldoende detail bevat, dan kan deze ook automatisch uitgevoerd worden. Denk aan het algoritme voor het optellen van twee getallen in decimale notatie: dit kun je met de hand uitvoeren, zonder erbij na te denken; je kunt het ook automatisch laten uitvoeren, door een rekenmachine.

Weefgetouw van Jacquard

Enkele van de voorlopers van de huidige computers zijn de muziekautomaten, zoals muziekdozen en draaiorgels; en het Jaquard-weefgetouw. Deze machines kunnen een algoritme in een gespecialiseerd domein automatisch uitvoeren. Een verschil met de huidige computers is dat deze laatste universeel zijn: in principe kunnen ze alle mogelijke algoritmen uitvoeren.

Een script of programma voor een computer schrijven we in een programmeertaal. Dit script legt precies en volledig vast welke stappen de computer moet nemen bij het uitvoeren van het proces.

Een programma is een algoritme opgeschreven in een programmeertaal. Je kunt eenzelfde algoritme, bijvoorbeeld voor het vermenigvuldigen van twee getallen, in verschillende programmeertalen noteren: het blijft hetzelfde algoritme.
Vergelijk een algoritme met een recept: hetzelfde recept kun je in verschillende talen opschrijven, maar het blijft hetzelfde recept - of dit in het Frans, in het Engels of in het Nederlands geschreven is.

Een computer voert de opdrachten in het programma heel precies en letterlijk uit. Een computer doet wat je zegt - en dat is misschien niet altijd wat je bedoelt. En omdat computers zo snel zijn, loopt het soms erg snel uit de hand.

 

★ Aan de slag 33

1. Kijk op het web naar de video "peanut butter jelly sandwich instructions".
Wat maakt deze video duidelijk?

2. Wat is een algoritme in de context van programmeren?

  1. Een grafische interface voor softwareontwikkeling
  2. Een set instructies die een computer exact uitvoert
  3. Een taal die computers gebruiken om te communiceren
  4. Een methode om gegevens systematisch te verwerken

3. Waarom blijft een algoritme hetzelfde, ongeacht de programmeertaal waarin het geschreven is?

  1. Omdat alle programmeertalen dezelfde syntaxis gebruiken
  2. Omdat programmeertalen geen invloed hebben op de uitvoeringssnelheid
  3. Omdat een algoritme een concept is dat onafhankelijk is van de taal
  4. Omdat een computer alleen machinecode begrijpt

4. Leg uit waarom het belangrijk is dat een algoritme correct is, en geef een voorbeeld van een situatie waarin een incorrect algoritme bij een bankieren app problemen kan veroorzaken.

5. Beschrijf hoe de technologie waarmee een algoritme wordt uitgevoerd kan variëren, en geef een voorbeeld van een alternatieve technologie (bijvoorbeeld de eerste voor computers zoals bedacht door Charles Babbage) die niet op een traditionele computer gebaseerd is.

Correctheid

Als het algoritme effectief is (of correct) krijg je, als je de stappen precies uitvoert, altijd het beoogde resultaat, voor elke acceptabele waarde van de invoer.

Een correct algoritme kan wel eisen aan de invoer stellen: niet alle invoerwaarden zijn zinvol.
Voor een delingsalgoritme eis je dat de deler verschilt van 0.

Een niet-effectief (incorrect) algoritme heeft niet zoveel zin.
Maar het is niet altijd eenvoudig om in te zien of een algoritme correct is, of om een correct algoritme te ontwikkelen.

Rekentechnologie

Een algoritme is niet afhankelijk van de technologie: je kunt eenzelfde algoritme met verschillende technologieën uitvoeren. Je kunt verschillende programmeertalen gebruiken, en verschillende processoren. Maar je kunt ook een compleet andere technologie gebruiken.

De eerste ideeën voor een computer werden bedacht met mechanische onderdelen (Babbage).
Daarnaast zijn er veel voorbeelden van informatieverwerking met biologische "rekentechnologie" - zoals we in de levende natuur om ons heen zien.

Volgende stappen

In de volgende onderdelen gaan we verder in op algoritmen en automaten.

De regels van een cellulaire automaat beschrijven hoe je uit de huidige toestand (vorm) de volgende toestand bepaalt. De uitvoering van deze regels resulteert in een proces als opeenvolging van deze toestanden.

Een eindige automaat is een processor met een vast algoritme, of anders gezegd:
het algoritme is met de processor geïntegreerd.
Je kunt tekening of een tabel van een eindige automaat daarom ook zien als een beschrijving van een algoritme.

In een spreadsheet vormen de cellen met formules samen een algoritme.
De uitvoer verschijnt in de cellen met formules.

We illustreren een aantal algoritmen met behulp van spreadsheets.
Bij zoeken en sorteren gaat het om de efficiëntie van deze algoritmen:
hoeveel stappen heb je nodig voor het uitvoeren van het algoritme, bij een bepaalde invoer?

★ Aan de slag 34

1. Plaats de volgende termen in het juiste vak:

  • wol, trui, breien, oma, breipatroon
  • brood, bakker, bakken, meel, recept
  • muzieknoten, draaiorgelboek, draaiorgel, muziek, orgeldraaien
Invoer Programma Proces Processor Uitvoer
         
         
         
         
         

 

2. Voeg een regel toe die betrekking heeft op het pinnen van contant geld bij een pinautomaat.

★ Aan de slag 35

Call centra maken vaak gebruik van call scripts.

  1. Zoek een voorbeeld van een call script (dat je in praktijk tegen kunt komen).

  2. Word je wel eens lastig gevallen door een telemarketeer die ook nog lastig gaat doen? Denk je dan niet ik zou de beller wel eens van repliek willen dienen? Hier is je kans! Ontdek op onze website https://web.archive.org/web/20241126001150/https://egbg.home.xs4all.nl/tegenscript.html geniale manieren om terug te slaan. Bezoek onze site en leer hoe je elke telemarketeer met hun eigen wapens kunt verslaan. Laat je inspireren en amuseer je met de leukste tegentactieken!
    PS: deze site is niet meer in de lucht maar wel nog te benaderen via de Waybackmachine, daarom is dit een aangepaste url. De Waybackmachine archiveert websites, dus hier kun je een website die niet meer in de lucht is terughalen.

  3. Geef aan op welke manier daarin de volgende elementen genoteerd worden: (i) opeenvolging, (ii) keuze, (iii) invoer, (iv) uitvoer.

★ Aan de slag 36

Breien als algoritme

  1. Zoek een voorbeeld van een breipatroon, en bestudeer de manier waarop dit genoteerd wordt.
  2. Welke van de volgende elementen kom je daarin tegen: (i) opeenvolging, (ii) keuze,  (iii) herhaling?
  3. Geef argumenten waarom dit wel/niet geautomatiseerd kan worden.

★ Aan de slag 37

Optellen

Beschrijf het algoritme dat je gebruikt voor het optellen van twee getallen in decimale notatie.

  1. Wat zijn de basisstappen van het algoritme?
  2. Moet je nadenken bij het uitvoeren van dit algoritme?
  3. Welke van de volgende elementen heb je hiervoor nodig: (i) opeenvolging, (ii) keuze, (iii) herhaling.

★ Aan de slag 38

Zoekalgoritme

  1. Waaruit bestaat de invoer voor het Google zoekalgoritme dat uitgevoerd wordt als je een zoekopdracht geeft?
  2. Hoe kan ik de Google zoekmachine wijs maken dat ik hele grote interesse heb in wasmachines? Het gevolg van de zoekopdracht moet zijn dat ik voortaan allerlei wasmachine reclames krijg te zien.
  3. Hoe kan ik dit weer oplossen zodat ik geen wasmachine reclames meer krijg te zien?

★ Aan de slag 39

Charles Babbage (1792-1871) is vooral bekend geworden door zijn ontwerpen voor mechanische rekenmachines. In de 17e eeuw hadden Blaise Pascal en Gottfried Wilhelm Leibniz ook al mechanische rekenmachines ontworpen.
Bij de machines van Pascal en Leibniz konden gegevens worden ingesteld door tandwielen in een bepaalde positie te plaatsen. Voordat er een berekening kon worden uitgevoerd, moesten de tandwielen in een beginpositie geplaatst worden. Na de berekeningen kon het resultaat aan de hand van de posities van de tandwielen worden afgelezen.
In 1821 ontwierp Babbage een mechanische rekenmachine die de Difference Engine werd genoemd.

Bekijk de onderstaande video over Charles Babbage en beantwoord dan de bijbehorende vragen:
Video: Charles Babbage

1. Hoe worden bij de Difference Engine van Babbage gegevens ingevoerd?

2. Difference Engine No.2 werd op basis van de originele ontwerpen van Babbage gebouwd in het Science Museum in Londen.
Hoe kunnen de resultaten van berekeningen bij deze machine worden afgelezen?

3. Wat was het belangrijkste doel van de Difference Engine van Charles Babbage?

  1. Het automatisch uitvoeren van complexe algebraïsche berekeningen.
  2. Het mechaniseren van berekeningen om fouten te voorkomen.
  3. Het creëren van een programmeerbare rekenmachine.
  4. Het simuleren van menselijke denkprocessen middels een machine.

4. Waarom werd de Difference Engine No. 2 pas meer dan een eeuw na Babbage’s dood gebouwd?

  1. Babbage’s tekeningen werden pas in de 20e eeuw serieus bestudeerd voor reconstructie.
  2. De bouw ervan was in Babbage’s tijd te duur en te arbeidsintensief.
  3. De Britse regering weigerde destijds de financiering van het project.
  4. Babbage richtte zich op de Analytical Engine en stopte met de Difference Engine.

5. Wat maakte de Analytical Engine revolutionair in vergelijking met de Difference Engine?

  1. Het kon meerdere soorten berekeningen uitvoeren zonder handmatige aanpassingen.
  2. Het gebruikte ponskaarten om instructies te volgen, vergelijkbaar met latere computers.
  3. Het was de eerste machine die op elektriciteit werkte en logische beslissingen kon nemen.
  4. Het werd daadwerkelijk gebouwd en gebruikt door wetenschappers in de 19e eeuw.

6. Wat was een van de belangrijkste kenmerken van de printersectie van de Difference Engine No. 2?

  1. Het kon berekeningen niet alleen afdrukken, maar ook automatisch opslaan in een drukvorm.
  2. Het kon tekst en afbeeldingen in kleur printen naast de berekende cijfers.
  3. Het gebruikte een handmatige schrijfarm om berekeningen op papier te noteren.
  4. Het moest na elke berekening handmatig worden gereset voordat het opnieuw kon printen.

7. Waarom wordt Charles Babbage beschouwd als een pionier van de moderne computer?

  1. Hij bouwde de eerste elektronische computer die werd gebruikt in wetenschappelijk onderzoek.
  2. Hij ontwikkelde een mechanische rekenmachine die volledig autonoom kon rekenen zonder menselijke tussenkomst.
  3. Hij ontwierp een machine die voorgeprogrammeerde instructies kon uitvoeren met behulp van ponskaarten.
  4. Hij maakte als eerste gebruik van binair rekenen voor mechanische berekeningen.

 

Game of life

Het speelveld van Conway’s Game of Life is een oneindig rechthoekig rooster van vierkante cellen.
Elke cel is in één van twee toestanden: wit of zwart.
Elke cel heeft 8 buren: de cellen die deze cel omringen.

Een zet in dit spel geeft alle cellen tegelijk een nieuwe waarde, op basis van de huidige toestand, volgens deze regels:

  1. een zwarte cel met minder dan 2 zwarte buren wordt wit;
  2. een zwarte cel met 2 of 3 zwarte buren blijft zwart;
  3. een zwarte cel met meer dan 3 zwarte buren wordt wit;
  4. een witte cel met 3 zwarte buren wordt zwart.

Vanuit een begintoestand van het speelveld kun je zo steeds een volgende toestand uitrekenen.
Hieronder zie je enkele opeenvolgende stappen (zetten) in dit spel, voor een bepaalde begintoestand.

Life: opeenvolgende toestanden (generaties)


Merk op dat we in de beschrijving alleen vorm-begrippen gebruiken: wit/zwart, en buren in het rechthoekige rooster.
Deze begrippen zijn voldoende om het spel te spelen.

De huidige toestand kun je zien als een samenvatting van de voorgeschiedenis: voor het berekenen van de volgende toestand is alleen de huidige toestand van belang, niet wat daarvoor gebeurd is. Dit begrip toestand speelt bij rekenprocessen een grote rol.

Je kunt de rollen van wit en zwart omwisselen: voor het spel maakt dit geen wezenlijk verschil.
De ontwikkeling van de opeenvolgende toestanden gaat op dezelfde manier.

Het spel Game of Life is een voorbeeld van een twee-dimensionale cellulaire automaat. We zullen later voorbeelden zien van ééndimensionale cellulaire automaten.

Wat betekenen deze vormen?
Zoals je gezien hebt, hoef je om het spel te spelen, geen betekenis aan de vormen te geven.
Maar misschien kun je aan deze vormen toch een betekenis toekennen.

In Conway’s oorspronkelijke formulering (zie bijvoorbeeld Wikipedia) wordt gesproken over “levende” en “dode” cellen, in plaats van over zwarte en witte. Regel 1 kun je dan zien als het sterven van een cel door eenzaamheid; regel 3 als het sterven van een cel door lokale overbevolking; regel 4 als de geboorte van een cel door de juiste combinatie van buren. Opeenvolgende toestanden worden generaties genoemd.

Deze betekenis verandert misschien de manier waarop wij naar het spel kijken, maar het spel zelf, als opeenvolging van vormen, verandert er niet door.

Wat is de relevantie van "Life"?
Life is een voorbeeld van rekenen als “spelen met vormen, volgens bepaalde regels”: alleen de vormen en de regels zijn van belang, de mogelijke betekenis van de vormen speelt bij de berekening geen rol.

Life is ook een voorbeeld van een systeem met emergent behaviour: een systeem met eenvoudige basisregels dat aanleiding geeft tot complex, interessant en verrassend gedrag.
Dergelijke systemen komen in de natuur veel voor: het complexe gedrag van een mierenkolonie of van een zwerm spreeuwen kan beschreven worden met eenvoudige regels.

Links en verdieping
Enkele links waar je meer informatie over Life kunt vinden:

 

★ Aan de slag 40

  1. Open de online-simulator Game of life.
    Met deze simulator kan het Game of Life worden gespeeld.
    Stel de simulator zo dat je start met een lege grid:
  2. Stel daarna het speelveld zo in dat je start met de meest linkse afbeelding.
    Klik daarna telkens op de knop next en controleer of de afbeeldingen overeenkomen met de opeenvolgende stappen:

 

★ Aan de slag 41

Bekijk de onderstaande video:
Video: An Introduction to Conway's The Game of Life

Geef voorbeelden van vormen die:

  1. niet veranderen in opeenvolgende toestanden (generaties);
  2. oscilleren: na een aantal zetten krijg je weer dezelfde vorm, op dezelfde plaats;
  3. zich verplaatsen: na een aantal zetten krijg je weer dezelfde vorm, maar op een andere plaats.

Je kunt dit opzoeken op de wiki over het Game of Life.
Of je probeert dit zelf uit, bijvoorbeeld met één van de online simulatoren.

★ Aan de slag 42

Zoek op het web (YouTube) naar video’s van de Game of Life.
Geef voorbeelden van interessant gedrag dat je op deze video’s tegenkomt.
Je kunt hierbij ook gebruik maken van de Wikipedia-tekst over Life, of van de conwaylife-wiki.

★ Aan de slag 43

Er zijn allerlei varianten op de regels mogelijk, maar niet alle varianten geven aanleiding tot interessant gedrag. Met de online-simulator Game of life kun je verschillende regels uitproberen.

Geef voorbeelden van (niet-triviale) regels die geen interessant gedrag opleveren, bijvoorbeeld doordat je snel een stabiele situatie bereikt.

Cellulaire automaten

De regels van een cellulaire automaat beschrijven hoe je uit de huidige toestand (vorm) de volgende toestand bepaalt. De uitvoering van deze regels resulteert in een proces als opeenvolging van deze toestanden.
Conway’s Game of Life is een voorbeeld van een 2-dimensionale cellulaire automaat. Je hebt dan een vlak met cellen (witte en zwarte hokjes).
Een 1-dimensionale cellulaire automaat bestaat uit een reeks aaneengesloten cellen. Een cel is “levend” (zwart, 1) of “dood” (wit, 0). De toestand van een automaat op een bepaald moment geeft aan welke cellen levend zijn, en welke dood. Dit kun je weergeven als een (horizontale) rij zwart/witte cellen (hokjes).

Gegeven een toestand van een automaat, kun je voor elke cel de volgende toestand bepalen uit de toestand van die cel en die van zijn directe buren. Je kunt de opeenvolging van toestanden weergeven door deze onder elkaar te tekenen, in een plat vlak.

Een voorbeeld van een automaat: (rule 110 = 0110 1110)
 

Regels voor de automaat (rule 110)

Met behulp van deze regels kun je vanuit een begintoestand de volgende toestanden uitrekenen. We tekenen de opeenvolgende toestanden (of generaties) onder elkaar.
In de figuur hieronder is dan gedaan voor een begintoestand met één zwarte cel, met de bovenstaande regels.

1-dimensionale cellualire automaat: de eerste regel is de
begintoestand, de volgende regels zijn de opeenvolgende
toestanden.


In plaats van met de “vormen” zwart en wit kunnen we ook met symbolen werken, bijvoorbeeld 0 en 1. (We kunnen allerlei symbolen gebruiken, als we maar twee waarden kunnen onderscheiden.)

In tabelvorm worden de regels dan:

0 000 0
1 001 1
2 010 1
3 011 1
4 100 0
5 101 1
6 110 1
7 111 0


Dit voorbeeld is uitgewerkt in een spreadsheet. Dit bestand (Cellular Automaton) tref je aan bij Bijlagen.

Weergave van het proces in een spreadsheet
In de spreadsheet staan de opeenvolgende stappen van het proces onder elkaar. Zo kun je de loop van het proces volgen.
Deze aanpak zullen we ook in volgende opdrachten gebruiken. De eerste rij bevat de begintoestand, soms met de invoer.
Elke volgende rij bevat de volgende stap in het algoritme - waarvan het resultaat dan in cellen van de rij zichtbaar wordt.

Voor de spreadsheet met de cellulaire automaat hebben we ook tussenresultaten, namelijk een codering van het patroon van de cel en de buren; voor de overzichtelijkheid hebben we deze in een apart vel (sheet, tab) geplaatst.

Links en verdieping
In het Wikipedia-artikel over Rule 110 vind je een beschrijving van het gedrag van deze cellulaire automaat.
Een bijzondere eigenschap is dat deze automaat Turing-complete is: je kunt daarmee in principe alle mogelijke berekeningen uitvoeren.
Voor zover bekend is dit het eenvoudigste systeem waarmee dit kan.

Meer over cellulaire automaten vind je in het boek van Stephen Wolfram, A New Kind of Science. Dit boek is online beschikbaar. In dit boek vind je veel fraaie figuren die ontstaan uit zulke eenvoudige regels en automaten. Je vindt er ook figuren uit de natuur die soms verrassend sterk lijken op deze figuren, zoals in hoofdstuk 8 (bijv. p. 423, p. 426).

Opdracht voor jezelf:

Formuleer nu zelf een lesdoel voor deze opdracht. Wat heb je door het maken van deze opdracht geleerd?

 

★ Aan de slag 44

De cellulaire automaat hierboven heet “regel 110”. Bedenk waar deze naam vandaan komt. 

★ Aan de slag 45




Maak de figuur van de cellulaire automaat hierboven af, door de toestanden 5 tot en met 8 te berekenen met de gegeven regels.

Controleer je uitwerking met de spreadsheet (Cellular automaton).
Om zelf met deze spreadsheet te werken, moet je eerst een kopie maken.
In deze spreadsheet vul je de begintoestand (eerste regel) in: de volgende toestanden worden dan uitgerekend.

★ Aan de slag 46

Je kunt in de spreadsheet ook experimenteren met andere regels.
In de sheet (tab) “rules” kun je het nummer van een andere regel invoeren, in omgekeerde binaire notatie.
Verander het regelnummer van “110” in “18” (0100 1000).
Welk effect heeft dit op het resultaat?

Eindige automaten

We behandelen hier een ander soort automaten: eindige automaten.
Ook hier weer gaat het om het werken met vormen: een eindige automaat verwerkt een reeks invoersymbolen tot een reeks uitvoersymbolen.
De uitvoersymbolen kunnen verschillen van de invoersymbolen.

Een eindige automaat bestaat uit de volgende onderdelen:

  • een verzameling toestanden; meestal geven we een toestand een naam of een nummer;
  • één van deze toestanden geven we aan als de begintoestand;
  • een verzameling invoersymbolen (het invoeralfabet);
  • een verzameling uitvoersymbolen (het uitvoeralfabet);
  • een verzameling toestandsovergangen; bij een overgang hoort (gewoonlijk) een invoersymbool en (gewoonlijk) een uitvoersymbool.
Voorbeeld van een automaat. A, B, en C zijn de toestanden.
A is de begintoestand. Het invoeralfabet is {M, T}. 
Het uitvoeralfabet is {M+, H+}. Bij sommige overgangen verandert
de toestand niet.


We tekenen een automaat op de volgende manier:

  • een toestand geven we aan met een cirkel (“bolletje”);
  • een toestandsovergang geven we aan met pijl van de ene naar de andere toestand; bij deze pijl schrijven we het bijbehorende invoer- en uitvoersymbool.
  • de begintoestand geven we aan met een dubbele inkomende pijl.

 

★ Aan de slag 47

1. Teken een eindige automaat die de verkeerslichten bij een kruispunt beschrijft.
Bedenk wat de invoer en de uitvoer is.

 

Adaptive Cruise Control
Achtergrondinformatie: Adaptive Cruise Control (ACC) is een systeem dat gebruikmaakt van sensoren, een boordcomputer en actuatoren om een voertuig op een veilige afstand te houden van een voorligger. Dit systeem regelt automatisch de snelheid en past deze aan wanneer een voertuig te dicht nadert.


De boordcomputer van de auto berekent voortdurend de afstand tot het voorliggende voertuig met behulp van sensoren zoals lasers of radar. Op basis van de ontvangen signalen en de ingestelde kruissnelheid bepaalt het systeem of er versneld of afgeremd moet worden.

Doel van de opdracht
Je onderzoekt hoe de boordcomputer van een auto beslist om af te remmen of te versnellen op basis van signalen en de ingestelde snelheid.

Stap 1: Begrijp de werking van Adaptive Cruise Control
De adaptieve cruisecontrol gebruikt sensoren, een boordcomputer en actuatoren om een veilige afstand tot andere voertuigen te bewaren. De bestuurder stelt de snelheid in via het touchscreen (bijv. 100 km/u). Lasers in de bumpers zenden signalen uit die terugkaatsen naar de sensoren, waarna de boordcomputer de afstand berekent. Bij een te kleine afstand remt de computer de auto af via actuatoren die de remmen activeren of het gas verminderen. Als de afstand weer veilig is, controleert de computer of de snelheid overeenkomt met de ingestelde snelheid en past deze zo nodig aan.

  • Noteer de stappen die de boordcomputer van de auto uitvoert:
  • Ontvangt signalen van de sensoren (afstand tot de voorligger).
  • Berekent de afstand.
  • Vergelijkt de gemeten afstand met de veilige afstand.
  • Indien de afstand te klein is, stuurt de computer een signaal naar de remmen of vermindert het gas.
  • Indien de afstand groot genoeg is, wordt gecontroleerd of de snelheid overeenkomt met de ingestelde waarde. Zo niet, dan past het systeem de snelheid aan.

Het proces kun je ook in een stroomdiagram weergeven:

Gebruik de gegeven tabel
De tabel in de opdracht geeft de stopafstand bij verschillende snelheden weer. Deze afstand bestaat uit:

  • Reactieafstand: de afstand die een auto aflegt voordat de bestuurder (of het systeem) begint met remmen.
  • Remweg: de afstand die een auto nodig heeft om volledig tot stilstand te komen nadat de remmen zijn geactiveerd.

Bekijk hoe deze waarden kunnen worden gebruikt om te bepalen of de auto moet afremmen.

De tabel met stopafstanden geeft een indicatie van de veilige afstand bij verschillende snelheden:

Snelheid in KM Stopafstand
30 10
50 21
60 30
70 40
80 54
90 67
100 70
110 94
120 110

 

Beschrijf de beslissingen van de boordcomputer
Gebruik het bovenstaande stroomdiagram en de tabel om te beschrijven hoe de boordcomputer beslist of de auto moet remmen.
Beantwoord de volgende vragen:

2. Hoe bepaalt de boordcomputer of de afstand tot de voorligger te klein is?

3. Wat gebeurt er als de afstand te klein is? Welke acties worden ondernomen?

4. Wat gebeurt er als de afstand groot genoeg is? Welke controles voert de boordcomputer nog meer uit?

5. Wat gebeurt er als de snelheid lager is dan de ingestelde snelheid en er geen obstakels zijn?

 

Extra opdracht (VWO)

Schrijf een pseudocode of maak een eenvoudig algoritme dat laat zien hoe het systeem deze beslissingen neemt. Dit kan worden gedaan in de vorm van een IF-ELSE-structuur.

Ga van de volgende stappen uit:

1. Meet de afstand tot het voorliggende voertuig.
2. Indien de afstand kleiner is dan de veilige afstand:
   a. Verminder de snelheid (remmen of gas verminderen).
3. Indien de afstand groter is dan de veilige afstand:
   a. Controleer of de snelheid overeenkomt met de ingestelde snelheid.
   b. Indien de snelheid lager is dan de ingestelde snelheid, verhoog de snelheid.
4. Herhaal dit proces continu.

Overgangen zonder uitvoer of invoer

In de definitie van een eindige automaat hierboven staat dat een overgang “gewoonlijk” een invoersymbool heeft en een uitvoersymbool.
Soms ontbreekt één van die twee, of soms ontbreken ze beiden.
Als er bij een overgang geen uitvoersymbool staat, levert deze overgang geen uitvoer.
We zullen ook voorbeelden tegenkomen waarbij er geen invoersymbool bij een overgang staat.
Dit betekent dat deze overgang “automatisch” plaatsvindt, zonder een symbool uit de invoer te verwerken.

We geven hier een voorbeeld van een erg eenvoudige automaat:

Een eenvoudige eindige automaat


Deze automaat heeft één invoersymbool: A, twee uitvoersymbolen: X en Y, en twee toestanden: 0 en 1. 0 is de begintoestand.

Wat doet deze automaat?

  • elk volgend invoersymbool geeft een overgang van de ene toestand naar de andere.
  • het uitvoersymbool bij deze overgang hangt af van de toestand, niet van de invoer.

Voorbeeld van een reeks invoertekens met de bijbehorende uitvoer en de nieuwe toestand (S).

T in uit S
0 A X 1
1 A Y 0
0 A X 1
1 A Y 0
0 A X 1
1 A Y 0


Je kunt deze automaat zien als:

  • een aan/uit drukschakelaar: elke keer drukken (A) verandert de toestand, van “uit” naar “aan” en omgekeerd;
  • een automaat om “even” en “oneven” te kunnen onderscheiden. De uitvoer Y betekent dat er een even aantal A’s verwerkt is, X staat voor oneven.
  • een “twee-deler”: als je uitvoer X vervangt door A, en Y weglaat, dan is het aantal A’s in de uitvoer is de helft van het aantal A’s in de invoer.


Voorbeeld van een automaat, een klokje:

Een klokje met knoppen M en T voor het instellen van de tijd


De manier waarop je met de knoppen de tijd kunt aanpassen beschrijven we met de volgende automaat:

Eindige automaat voor het instellen van de tijd


Met de knop M (voor “mode”) stel je in of de klok gewoon loopt, of dat je de uren instelt, of de minuten.
Elke keer dat je M indrukt gaat de automaat over in de volgende toestand.
In toestand A heeft het indrukken van knop T geen effect: er is geen uitvoer, en de toestand verandert niet.
In toestand B heeft het indrukken van de knop T als uitvoer H+: dit verhoogt de urenteller.
In toestand C heeft T als uitvoer M+: dit verhoogt de minutenteller.

Merk op dat bij een klokje alles “rond telt”: als je aan het eind gekomen bent, begin je weer bij het begin.
Dit geldt voor de toestanden, maar het geldt ook voor de uren- en minutentellers: ophogen van de minutenteller bij stand 59 geeft stand 00.

Meer voorbeelden van eindige automaten zullen we zien bij het onderdeel “talen en grammatica’s”.

★ Aan de slag 48

De onderstaande figuur beschrijft een snoepautomaat.
De invoersymbolen “50” en “100” staan voor het inwerpen van een muntje van 50 en 100 cent, “Ka” en “Kb” voor de knoppen “kies A” en “kies B”.
De uitvoersymbolen “Pa” en “Pb” staan voor “geef product A” en “geef product B”.

  1. Ga na hoe deze automaat werkt. Geef in een tabel een voorbeeld van een proces: een invoerreeks met bijbehorende uitvoer en volgende toestand.
  2. Hoe duur zijn de producten A en B?
  3. Breid de automaat uit zodat deze ook twee munten van 100 cent accepteert, en in dat geval geld teruggeeft. Gebruik hiervoor het uitvoersymbool “R50”.
  4. Breid de automaat uit met een product C dat 50 cent duurder is dan product A.
Een snoepautomaat

 

Rekenen met automaten

Beschouw de volgende automaat:

Opteller voor binaire getallen


Deze automaat heeft als invoeralfabet 4 symbolen, die we aangeven als 00, 01, 10, en 11.
Het uitvoeralfabet bestaat uit twee symbolen: 0 en 1. Als we de invoer opvatten als twee binaire getallen (“van rechts naar links”), waarvan de bits steeds één invoersymbool vormen, dan kunnen we de uitvoer zien als de som van deze twee getallen.
De toestand houdt steeds bij wat we moeten “onthouden” voor de volgende optelling.

We kunnen de overgangen van deze automaat ook beschrijven in de vorm van een tabel; toestand’ is hierin de volgende toestand.

Input Toestand Toestand' Output
00 0 0 0
01 0 0 1
10 0 0 1
11 0 1 0
00 1 0 1
01 1 1 0
10 1 1 0
11 1 1 1

 

Een voorbeeld van invoer- en uitvoerreeksen geven we hieronder.

01010 - inputreeks A (v.r.n.l.)
00111 - inputreeks B
11100 - toestandenreeks
10001 - outputreeks

Deze reeksen zijn hier van rechts naar links weergegeven. Op die manier zie je sneller welke getallen dit voorstellen: A (v.l.n.r. 01010, decimaal 10) en B (11100, decimaal 7) geeft als output: 10001 (decimaal 17).


Links en Verdieping
Eindige automaten (finite state machines) worden op veel plaatsen in de informatica en ICT gebruikt, van het laagste hardware-niveau tot abstracte Turingmachines.
Zo zou je met behulp van een geheugen (ROM) en een register een eindige automaat in hardware kunnen maken.

Er is een directe relatie tussen eindige automaten en reguliere expressies.
Bij het verwerken van invoer in een programma komen deze vaak van pas.

Ook voor het programmeren van een Arduino vormen eindige automaten een handig programmeerhulpmiddel.

Zoeken

Zoeken komt in veel toepassingen voor, bijvoorbeeld het zoeken van het nulpunt van een functie, of als onderdeel van “opslaan en terugzoeken”.
De twee belangrijkste basisalgoritmen om te zoeken zijn lineair zoeken en binair zoeken. We behandelen deze aan de hand van het raden van een getal: dat kun je ook als een zoekprobleem beschouwen.

Voor binair zoeken heb je veel minder stappen nodig dan voor lineair zoeken, maar binair zoeken is alleen mogelijk als de “zoekruimte” handig georganiseerd is, bijvoorbeeld als een alfabetische lijst van namen.

Merk op dat we bij het zoeken alleen de vorm gebruiken, bijvoorbeeld namen of getallen. De betekenis van deze namen of getallen speelt hierbij geen rol.

Bij het opslaan en terugzoeken van gegevens gebruik je meestal een deel van de gegevens als zoeksleutel (key); bijvoorbeeld om het telefoonnummer en het e-mailadres van één van je contacten te zoeken, gebruik je de naam als zoeksleutel.
Als deze zoeksleutels handig georganiseerd zijn, bijvoorbeeld als alfabetische lijst, dan kun je de andere gegevens daarmee efficiënt terugzoeken.

Raad een getal
We proberen een slimme oplossing te vinden voor het probleem om een getal te raden, bijvoorbeeld tussen 0 en 99 (“tot honderd”).

Lineair zoeken
Een simpele manier is om de getallen één voor één te proberen: is het 0? is het 1? enz.
Dit is niet erg efficiënt: je hebt in het ergste geval 100 vragen nodig, en gemiddeld nog altijd 50 vragen.

Deze aanpak, “lineair zoeken”, is wel effectief: je weet zeker dat je het gezochte getal vindt.
Als je geen betere aanpak kunt vinden, kun je daarom altijd terugvallen op lineair zoeken.

Binair zoeken
Als je mag vragen of het te raden getal groter of kleiner is dan een getal dat je noemt, dan kun je met veel minder vragen toe.
Je halveert dan in elke stap het gebied waarin het gezochte getal kan liggen. Vanwege dit halveren heet deze aanpak “binair zoeken”.

Raad een getal (met binair zoeken)


We kunnen deze aanpak het best uitleggen aan de hand van de getallenlijn, met daarop de getallen 0..100, en twee blokjes.
Het linkerblokje lo leg je bij het getal 0, het rechterblokje hi bij het getal 100. Het gezochte getal x ligt nu tussen deze twee blokjes: lo≤x<hilo≤x<hi. Als hi=lo+1hi=lo+1 - de blokjes liggen tegen elkaar aan, zijn we klaar: lo is het gezochte getal, immers lo≤x<lo+1lo≤x<lo+1.

We onderzoeken steeds het getal in het midden tussen lo en hi: m=lo+hi/2m=lo+hi/2. (We gebruiken hier de deling voor gehele getallen: 99/2 = 49. Dit heet ook wel het quotient.)
Als m groter is dan het gezochte getal, dan verplaatsen we hi naar m. In het andere geval verplaatsen we lo naar m.
Merk op dat nu blijft gelden dat lo≤x<hilo≤x<hi. Het gezochte getal ligt tussen de twee blokjes. Dit noemen we daarom wel de invariant van dit algoritme.

We kunnen deze aanpak beschrijven in een spreadsheet, op de volgende manier:

  • de cel met het getal dat geraden moet worden noemen we x.
  • kolom A gebruiken we voor het volgnummer van de rekenstap; stap 0 is de initialisatie, de volgende stappen herhalen steeds dezelfde berekening;
  • voor de waarden lo, m en hi gebruiken we opeenvolgende kolommen (B, C, D).
  • we beginnen (stap 0) met de waarden lo=0lo=0 en hi=100hi=100: B2=0, D2=100.
  • elke rij van de spreadsheet is een stap in het algoritme
  • m ligt midden tussen lo en hi: =QUOTIENT(B2+D2, 2)
  • de volgende waarde van lo hangt af van de vergelijking tussen m en x:
              =IF(x < C2; B2; C2)
  • de volgende waarde van hi hangt af van de vergelijking tussen m en x:
              =IF(x < C2; C2; D2)

In een spreadsheet ziet dit er zo uit:

  A B C D
1 n lo m hi
2 0 0 =QUOTIENT(B2+D2,2) 100
3 1 =IF(x < C2, B2, C2) =QUOTIENT(B3+D3,2) =IF(x < C2, C2, D2)
4 2 =IF(x < C3, B3, C3) =QUOTIENT(B4+D4,2) =IF(x < C3, C3, D3)
... ... ... ... ...


De spreadsheet met dit voorbeeld (zoeken-en-sorteren) vind je onder Bijlagen

Deze aanpak van het raden van een getal kunnen we gebruiken bij het zoeken naar een waarde in geordende reeks.
Enkele voorbeelden: het zoeken in een woordenboek of in een geordende lijst van namen. (Het zoeken van een naam in een telefoonboek zal niet meer tot de verbeelding spreken.)

Omdat deze aanpak van het zoekprobleem zo efficiënt is, is sorteren ook belangrijk: we zorgen ervoor dat reeksen waarden waarin we moeten zoeken, geordend zijn, zodat we efficiënt kunnen zoeken.

★ Aan de slag 49

Welke reeks waarden voor lo en hi krijg je bij het raden

  1. van het getal 23, als getal onder de 100, volgens het Binair Zoeken-algoritme?
    Controleer je antwoord met de spreadsheet.
  2. van het getal 789, als getal onder de 1000, volgens dezelfde methode?
    Controleer je antwoord met de spreadsheet.
  3. In hoeveel stappen heb je het getal geraden in geval (a)? in hoeveel stappen in geval (b)? Hoeveel stappen heb je nodig voor het raden van een getal onder de 1.000.000?

★ Aan de slag 50

Je hebt 10 munten waarvan je weet dat er 1 vals is, met een afwijkend gewicht.
Je hebt een balansweegschaal waarmee je gewichten kunt vergelijken.

  1. Je weet dat de valse munt lichter is.
    Hoe vaak moet je wegen om de valse munt te vinden?
    Beschrijf hoe je dit aanpakt.
  2. Je weet niet of de valse munt zwaarder of lichter is.
    Hoe vaak moet je wegen om de valse munt te vinden?
    Beschrijf hoe je dit aanpakt.

★ Aan de slag 51

Je hebt een (lange) lijst met namen en bijbehorende telefoonnummers.
De lijst is alfabetisch geordend op naam.

  1. Welke methode gebruik je voor het zoeken van een telefoonnummer bij een naam?
  2. Welke methode gebruik je voor het zoeken van een naam bij een telefoonnummer?

Sorteren

In het spreadsheet-voorbeeld hebben we ook een demonstratie van het sorteren van een reeks getallen.
Dit sorteren werkt als volgt:

  • in de ene stap vergelijken we de waarden (1,2), (3,4), enz.; we verwisselen (“swap”) deze waarden eventueel zodat deze voor elk paar in de goede volgorde staan.
  • in de volgende stap vergelijken we de waarden (2,3), (4,5), enz.; ook deze zetten we per paar in de goede volgorde;
  • deze stappen herhalen we N keer, voor een reeks van N waarden.

In spreadsheet-formaat wordt dit:

  A B C D
1 13 11 5 9
2 =IF(A1<=B1,A1,B1) =IF(A1<=B1,B1,A1) =IF(C1<=D1,C1,D1) =IF(C1<=D1,D1,C1)
3 =A2 =IF(B2<=C2,B2,C2) =IF(B2<=C2,C2,B2) =D2
4 =IF(A3<=B3,A3,B3) =IF(A3<=B3,B3,A3) =IF(C3<=D3,C3,D3) =IF(C3<=D3,D3,C3)
... ... ... ... ...


De spreadsheet voor zoeken bevat ook het sorteervoorbeeld.

Links en verdieping
Binair zoeken komt in heel veel situaties van pas: je moet het algoritme dan zelf aanpassen aan de situatie.
Een voorwaarde is dat je zoekt voor een willekeurige waarde x kunt bepalen of de gezochten waarde “links” of “rechts”, “voor” of “achter” deze waarde x te vinden is.

Zoals gezegd is sorteren belangrijk omdat dit efficiënt zoeken mogelijk maakt. Maar het is dan ook nodig dat je efficiënt kunt sorteren.
Er zijn veel efficiëntere sorteeralgoritmes dan die gebruikt in het spreadsheet-voorbeeld, onder andere quicksort (Wikipedia: quicksort) en mergesort (Wikipedia: mergesort).
In de praktijk gebruik je voor sorteren meestal een bibliotheekfunctie: dan hoef je quicksort of mergesort niet zelf uit te programmeren.
In de keuzemodule Objectgeoriënteerd programmeren wordt hier dieper op ingegaan.

 

★ Aan de slag 52

Zoals we gezien hebben, heeft het gegeven algoritme voor het sorteren van een reeks van N getallen N stappen nodig.
Hoeveel extra vergelijkingen heb je nodig als je de reeks 1 langer maakt?

Map/reduce

In dit gedeelte behandelen we enkele patronen voor het rekenen met rijen van waarden zoals je die in bijvoorbeeld spreadsheets vaak tegenkomt.
De twee belangrijke patronen zijn:

  • map: bereken voor elke waarde een bijbehorende andere waarde
    • voorbeeld: bereken voor elk bedrag de bijbehorende BTW
    • (a0,a1,a2,...,an)⇒(b0,b1,b2,...,bn)
  • reduce: vat een rij waarden samen in een enkele waarde
    • voorbeeld: sommeer alle waarden.
    • (a0,a1,a2,...,an)⇒(a0+a1+a2+...+an)

We behandelen deze patronen in de context van spreadsheets.
De online-versie van de voorbeelden vind je via: map-reduce spreadsheet.
Download het bestand en open deze in excel.
Je kunt het Excel-bestand ook vinden onder Bijlagen.

Map
Je kunt in een spreadsheet met een kolom van getallen een nieuwe kolom van afgeleide waarden maken.
Bijvoorbeeld: bij een kolom met bedragen exclusief 21% BTW, maak je een kolom met deze bedragen inclusief 21% BTW.
De formules in deze extra kolom zijn berekeningen met de waarde in dezelfde rij.
Als x het bedrag exclusief BTW is, en y het bedrag inclusief BTW, dan:

  • Stap n: y[n] = x[n]∗1.21

In een spreadsheet wordt dit bijvoorbeeld:

  A B C
1 n x y
2 0    
3 1 42 =B3 * 1.21
4 2 13 =B4 * 1.21
... ... ... ...

 

Samenvatten (reduce)
In een spreadsheetprogramma heb je ingebouwde functies om een reeks getallen samen te vatten: je reduceert een rij waarden tot 1 waarde.
Voorbeelden hiervan zijn: som, maximum, minimum, gemiddelde.
Dit zijn opdrachten om een operatie voor twee waarden, bijvoorbeeld optellen, uit te voeren voor alle elementen in een rij.

Dit reductiepatroon kun je ook gebruiken voor andere waarden dan getallen.
Voorbeelden: het samenvoegen van een rij strings tot één lange string; een and-operatie voor een rij boolean waarden.

In dit gedeelte maak je zelf zo’n reductie-algoritme voor een rij, met behulp van de basisoperatie voor twee waarden.

Voorbeeld 1: som
Als eerste voorbeeld geven we som, voor het optellen van een rij getallen x[1..N].

Opmerking: in veel programmeertalen, zoals Python en Java, beginnen rijen met index 0; in spreadsheets tellen de rijen en kolommen vanaf 1 (vanwege historische redenen).

In de kolom som houden we de som van de rij waarden tot nu toe bij:

som[n]=x[1]+x[2]+...+x[n]

We beginnen met som[0] als som van de getallen x[1..0]: deze rij bevat geen getallen, de som is dan 0.
Voor een willekeurige waarde n,n>0 geldt:

  • som[n]=x[1]+x[2]+...+x[n−1]+x[n], ofwel:
  • som[n]=som[n−1]+x[n]

We drukken de volgende waarde van som uit in de voorafgaande waarde van som.
Samenvattend:

  • Stap 0: som[0]=0
  • Stap n: som[n]=som[n−1]+x[n](voor n>0)

In een spreadsheet wordt dit:

  A B C
1 n x som
2 0   0
3 1 42 =C2+B3
4 2 13 =C3+B4
... ... ... ...

 

Voorbeeld 2: maximum
Als tweede voorbeeld bepalen we het maximum van een rij getallen. Het belangrijkste verschil met het som-voorbeeld is dat we geen maximum voor een lege rij getallen kunnen bepalen: er is geen “stap 0”, we moeten met “stap 1” beginnen.
We gebruiken de functie MAX voor het maximum van 2 getallen.

  • Stap 1: max[1]=x[1]
  • Stap n: max[n]=MAX(max[n−1],x[n])

In een spreadsheet wordt dit:

  A B C
1 n x max
2 0   0
3 1 42 =MAX(C2,B3)
4 2 13 =MAX(C3,B4)
... ... ... ...


In plaats van =MAX(C2,B3) kun je ook schrijven: =IF(C2 >= B3, C2, B3).

Map/reduce
Je kunt deze map- en reduce-patronen op veel manieren combineren.
We geven hier als voorbeeld het bepalen van de som van een reeks kwadraten.
Als eerste proberen we Stap 0 (de initialisatie) en Stap 1 te formuleren.

  • Stap 0: som[0]=0
  • Stap n: x[n]=n∗n,som[n]=som[n−1]+x

Dit werken we uit in een spreadsheet:

  A B C
1 n x som
2 0   0
3 1 =A3 * A3 =C2 + B3
4 2 =A4 * A4 =C3 + B4
... ... ... ...

 

Links en verdieping
De begrippen map en reduce komen uit de wereld van functioneel programmeren. Maar het toepassingsgebied is veel groter: hiermee kun je efficiënt rekenen met grote hoeveelheden waarden in lijsten (rijen).
In het bijzonder maakt dit parallelle verwerking van de berekeningen mogelijk: de berekeningen worden verdeeld over meerdere rekeneenheden of over meerdere computers.

Zie ook: Wikipedia - MapReduce

Ook voor het werken met gegevens in spreadsheets is dit een handige aanpak.

★ Aan de slag 53

  1. (map)
    Maak een spreadsheet volgens onderstaand patroon, met in kolom x de kwadraten van n.
    • Bereken op deze manier in elk geval de kwadraten van 1..20.
    • Maak een grafiek van de kolommen n (x-as) en x (y-as).
      A B
    1 n x
    2 0  
    3 1 = ...
    4 2 = ...
    ... ... ...

 

  1. (reduce)
    Maak aan de hand van de voorbeelden voor som een spreadsheet-programma voor prod: het product van alle getallen in de rij x.
    prod[n]=x[1]∗x[2]∗...∗x[n]
    • Welke waarde kies je voor prod[0]?
    • Wat kies je voor prod[n]?
    • Maak de spreadheet, voor een rij van tenminste 20 getallen.

(Plaats n (0..) in kolom A, plaats de getallen in kolom B (vanaf positie n=1; en het product in kolom C, vanaf positie n=0)

★ Aan de slag 54

(map/reduce) 
Maak een spreadsheet-programma voor het uitrekenen van de gemiddelde waarde van een rij getallen (gemiddelde[n]=som[n]/n), waarin som[n] de som is zoals in het som-voorbeeld hierboven gegeven is.

Hint: ga uit van het som-voorbeeld, en voeg een extra kolom gemiddelde toe: een combinatie van de waarden n en som.

★ Aan de slag 55

(map/reduce)
Maak een spreadsheet-programma voor het uitrekenen van de som van de derde machten: 1^3+2^3+...20^3.

★ Aan de slag 56

(map/reduce)
Bepaal volgens het schema van de voorgaande voorbeelden het totaal inclusief BTW van een reeks bedragen exclusief BTW.

F Talen en grammatica's

Inleiding

We hebben hiervoor rekenen beschreven als “spelen met vormen”.
In de voorbeelden van eindige automaten zijn de vormen enkelvoudige symbolen, of reeksen van symbolen - bijvoorbeeld een reeks van invoer- of uitvoersymbolen.

Gewoonlijk communiceren mensen (en computers) niet op basis van willekeurige reeksen symbolen, maar met een taal die structuur aanbrengt in deze reeks.
Deze structuur speelt een belangrijke rol bij het vaststellen van de betekenis.

In een natuurlijke taal gebruik je geen losse woorden, maar combineer je woorden tot zinnen die voldoen aan de regels van (bijvoorbeeld) het Nederlands.

Voorbeeld: je kunt de woorden “de”, “hond”, “man”, “bijt” tot veel verschillende reeksen woorden combineren. Maar enkele van deze reeksen woorden vormen een Nederlandse zin. Bovendien hangt de betekenis van deze zinnen af van de volgorde van de woorden.

In dit gedeelte gaan we in op het gebruik van grammatica’s voor het beschrijven van talen - zowel van formele talen (zoals programmeertalen) als van stukjes natuurlijke taal. Een taal is hier een (mogelijk oneindige) verzameling zinnen.
Een zin is een eindige reeks symbolen of woorden. (Dit begrip woord moet je hier ruim interpreteren: ook (lees)tekens kunnen daaronder vallen.
Bij programmeertalen heb je bijvoorbeeld te maken met tekens als “(“, “;”, “=” en “*”.)

Grammatica's en betekenis

Met behulp van een grammatica van een taal kun je twee dingen:

  1. nagaan of een bepaalde zin een zin is in deze taal;
  2. de structuur van de zin bepalen - om daarmee de betekenis van de zin te bepalen.

Dit laatste is wat je bij het vak Nederlands leert, als redekundig en taalkundig ontleden.
Je leert dat in “de hond bijt de man”, “de hond” onderwerp is, “bijt” het werkwoord, en “de man” lijdend voorwerp (in dit geval ook letterlijk).
De volgorde van deze onderdelen in een Nederlandse zin staat vast: de zin “de man bijt de hond” heeft een andere betekenis.

Eindige automaten

Een eerste manier om bepaalde volgordes van woorden af te dwingen is met behulp van een eindige automaat.
Met de onderstaande automaat kunnen we een aantal zinnen met de genoemde woorden maken.

Eindige automaat voor het maken van eenvoudige zinnen

 

★ Aan de slag 57

1. Wat is het doel van de beschreven automaat?

  1. Het vermenigvuldigen van twee binaire getallen
  2. Het optellen van twee binaire getallen
  3. Het omzetten van binaire getallen naar decimale getallen
  4. Het genereren van willekeurige binaire reeksen

2. Wat stelt de toestand in de automaat voor?

  1. Het onthouden van een carry 
  2. Het getal dat als invoer wordt gegeven
  3. De som van de binaire getallen op dat moment
  4. De uitvoer van de automaat

3. Wat gebeurt er als de invoer '11' is en de huidige toestand '1' is?

  1. De nieuwe toestand wordt '0' en de uitvoer wordt '1'
  2. De nieuwe toestand blijft '1' en de uitvoer wordt '1'
  3. De nieuwe toestand wordt '1' en de uitvoer wordt '0'
  4. De nieuwe toestand blijft '0' en de uitvoer wordt '1'

 

★ Aan de slag 58

Ontwerp een automatische deur die alleen opent als een specifieke volgorde van handelingen wordt uitgevoerd (bijvoorbeeld: pas scannen → code invoeren → hand aanraken). Hoe kan een eindige automaat (finite state machine) worden gebruikt om dit systeem te modelleren? Beschrijf de mogelijke toestanden en overgangen. 

Geef de toestand en overgang weer in de volgende tabel:

Toestand Beschrijving
0  
1  
2  
3  
Overgangen Voorwaarden
Van 0 naar 1  
Van 1 naar 2  
Van 2 naar 3  
Van 3 terug naar 0  

 

★ Aan de slag 59

Versie VWO

Nederlandse postcodes hebben een vast formaat: vier cijfers gevolgd door een spatie en twee hoofdletters (bijvoorbeeld: "1234 AB"). Hoe kan een eindige automaat worden gebruikt om te controleren of een invoer daadwerkelijk een geldige Nederlandse postcode is? Beschrijf de mogelijke stappen die de automaat zou doorlopen en leg uit wat er gebeurt als een invoer niet aan het patroon voldoet.

 

Versie HAVO

Nederlandse postcodes hebben een vast formaat: vier cijfers gevolgd door een spatie en twee hoofdletters (bijvoorbeeld: "1234 AB"). Een eindige automaat kan worden gebruikt om te controleren of een invoer daadwerkelijk een geldige Nederlandse postcode is. De mogelijke stappen die de automaat zou doorlopen, kunnen als volgt worden beschreven: eerst controleert de automaat of de eerste vier tekens cijfers zijn; vervolgens controleert hij of het vijfde teken een spatie is; tot slot controleert hij of de laatste twee tekens hoofdletters zijn. Als een invoer niet aan dit patroon voldoet, zal de automaat aangeven dat de invoer ongeldig is.

 

★ Aan de slag 60

Foutdetectie met de eindige automaat VWO versie
Wat gebeurt er als een invoer een onjuiste postcode bevat? Beschrijf drie mogelijke fouten die kunnen optreden en leg uit hoe de eindige automaat hierop zou reageren.

 

Foutdetectie met de eindige automaat HAVO versie
Een eindige automaat voor Nederlandse postcodes moet invoer in het volgende formaat hebben:
✅ 1234 AB (vier cijfers, een spatie en twee hoofdletters).

Hieronder zie je drie veelvoorkomende fouten bij invoer van een postcode. Leg uit waarom de automaat deze invoer afwijst en bij welke stap het misgaat.

"1234AB" (ontbrekende spatie)

In welke stap verwacht de automaat een spatie?
Wat gebeurt er als er direct een letter wordt ingevoerd?
"12A4 AB" (letter in plaats van een cijfer)

De eerste twee tekens zijn correct. Op welke plek in de invoer zit de fout?
Waarom wordt deze invoer door de automaat niet geaccepteerd?
"1234 ab" (kleine letters in plaats van hoofdletters)

Op welke positie verwacht de automaat een hoofdletter?
Wat gebeurt er als een kleine letter wordt ingevoerd in plaats van een hoofdletter?
 

★ Aan de slag 61

Eindige automaat voor het maken van eenvoudige zinnen

 

  1. Welke zinnen kun je met deze automaat maken?
  2. Breid de bovenstaande automaat uit zodat ook vragende zinnen mogelijk zijn als “bijt de hond de man?”.
    Het vraagteken kun je hierbij buiten beschouwing laten.

Deze aanpak met eindige automaten werkt voor eenvoudige talen, bijvoorbeeld om te beschrijven hoe een komma-getal of een postcode eruit kunnen zien.
Voor grotere en complexere talen, zoals programmeertalen of natuurlijke talen, is dit te beperkt.

Grammatica's

Een volgende stap is het gebruik van grammatica’s met herschrijfregels. Zo’n grammatica bestaat uit de volgende onderdelen:

  • een verzameling taalsymbolen
        het “alfabet” van de taal;
        we noemen deze ook wel de “woorden” van de taal;
        elke zin in de taal is een reeks van deze symbolen.
  • een verzameling hulpsymbolen
        deze gebruiken we alleen in het werken met de grammatica;
        in de zinnen van de taal komen deze niet voor.
  • een verzameling herschrijfregels;
        elke regel beschrijft hoe je hulpsymbool kunt herschrijven in een reeks taal- en hulpsymbolen.
  • één van deze hulpsymbolen is het startsymbool:
        alle zinnen in de taal zijn afgeleid van dit symbool.

Tijdens het werken met de grammatica hebben we te maken met zinsvormen: een zinsvorm is een reeks symbolen, waarbij een symbool een taalsymbool is of een hulpsymbool.

Aan de hand van de voorbeelden zal duidelijk worden hoe je met een kleine verzameling regels een groot aantal zinnen kunt beschrijven.
We geven hier de herschrijfregels eerst in een grafische notatie: syntaxdiagrammen of railroad diagrams. Later zullen we ook een tekstnotatie gebruiken: deze kun je wat gemakkelijker door een computer later verwerken.

Hoe werkt zo’n grammatica?

We laten zien hoe je een zin maakt met behulp van de herschrijfregels van een grammatica.

Beschouw de volgende grammatica:

Het startsymbool is “Z”. De hulpsymbolen zijn Z, Ow, Gz, Lv, Zd. De taalsymbolen zijn “de” “hond” “man” “bijt” “aait”.

1. Z  -> Ow Gz Lv
2. Ow -> Zd
3. Gz -> "bijt" | "aait"
4. Lv -> Zd
5. Zd -> "de" "man" | "de" "hond"

In deze herschrijfregels vormt | het scheidingsteken voor alternatieven. Regel (3) is een afkorting voor:

3a. Gz -> "bijt"
3b. Gz -> "aait"

We kunnen deze herschrijfregels ook grafisch weergeven, in de vorm van syntaxdiagrammen (of railroad diagrams).

Syntaxdiagrammen


We geven de afleiding van de zin “de man aait de hond” uit het startsymbool Z, met behulp van deze regels.

Z
=> (regel 1)
Ow Gz Lv =>
=> (regel 2)
Zd Gz Lv
=> (regel 5a)
"de" "man" Gz Lv
=> (regel 3b)
"de" "man" "aait" Lv
=> (regel 5)
"de" "man" "aait" "de" "hond​

De afleiding levert vanuit het startsymbool Z, via een aantal zinsvormen met taalsymbolen en hulpsymbolen, een zin die alleen uit taalsymbolen bestaat. Bij deze afleiding herschrijven we steeds het linker hulpsymbool in de zinsvorm: we vervangen dit door één van de alternatieven van de herschrijfregel voor dit symbool.

Bij deze afleiding kunnen we de volgende afleidingsboom maken:

Ontleedboom bij de afleiding (A)


Deze boom geeft de structuur van de zin weer; deze structuur gebruiken we bij het bepalen van de betekenis.

★ Aan de slag 62

Geef de afleiding van de zin “de hond bijt de man”.

Voorbeeld: Expressies

Het volgende voorbeeld is een grammatica voor eenvoudige expressies.
We beperken ons hierbij tot expressies met gehele getallen, haakjes, optellen en aftrekken.

1. Expr -> Term (Operator Term)*
2. Term -> Number | "(" Expr ")"
3. Number -> "0" | "1" | "2" | "3"
4. Operator -> "+" | "-"

Hier betekent “*” : herhaal het voorafgaande 0 of meer keer.

Ook deze regels kunnen we weergeven in een syntaxdiagram:

syntaxdiagram expr-taal



Voorbeeld: afleiding van “1-(2+3)”

Expr
=> (regel 1; herhaal rechterdeel 1 keer)
Term Operator Term
=> (regel 2, 1e alternatief)
Number Operator Term
=> (regel 3)
"1" Operator Term
=> (regel 4)
"1-" Term
=> (regel 2, 2e alternatief)
"1-(" Expr ")"
=> (regel 1; herhaal rechterdeel 1 keer)
"1-(" Term Operator Term ")"
=> (regel 2, 1e alternatief)
"1-(" Number Operator Term ")"
=> (regel 3)
"1-(2" Operator Term ")"
=> (regel 4)
"1-(2+" Term ")"
=> (regel 2, 1e alternatief)
"1-(2+" Number ")"
=> (regel 3)
"1-(2+3)"

De bijbehorende boom ziet er als volgt uit:

ontleedboom bij de afleiding (b)


We kunnen deze boom vereenvoudigen door alle hulpsymbolen weg te laten:


Uit deze afleiding, en de bijbehorende boom, kun je zien dat het deel tussen haakjes eerst berekend moet worden: met haakjes kun je de volgorde van de berekening precies aangeven.

Dit is een voorbeeld hoe de structuur van een “zin” zoals die volgt uit de regels van de grammatica, de betekenis van die zin bepaalt.

★ Aan de slag 63

Gegeven is de onderstaande grammatica voor expressies.
Dit is een kleine uitbreiding van de grammatica die we eerder gebruikt hebben, met vermenigvuldiging als uitbreiding.
Het startsymbool is Expr, de hulpsymbolen zijn Expr, Term, Factor, Number, Addop en Mulop.
De eindsymbolen (taalsymbolen) zijn “0”, “1”, “2”, “3”, “+”, “-“, “*”, “/”, “(” en “)”.

1. Expr -> Term (Addop Term)*
2. Term -> Factor (Mulop Factor)*
3. Factor -> Number | "(" Expr ")"
4. Number -> "0" | "1" | "2" | "3"
5. Addop -> "+" | "-"
6. Mulop -> "*" | "/"

  1. Maak met deze regels een afleiding voor “1+2*3”. Teken de bijbehorende afleidingsboom. Laat daarmee zien dat deze grammatica aangeeft dat vermenigvuldigen (“*”) voor optellen (“+”) gaat.
  2. Maak een grammatica voor zinnen die uit netjes gepaarde haakjes “(” en “)” bestaan. Enkele voorbeelden: “()” “((()))()” “()()()”. Enkele tegenvoorbeelden (van “niet-zinnen”): “(” “)(” “((())()”
  3. Geef een grammatica voor de decimale notatie van gehele getallen. De eindsymbolen zijn hierbij de cijfers “0”..”9”. De notatie begint niet met een 0, tenzij het getal 0 is. Enkele voorbeelden: “0” “12” “900” “1234567890987654321”. Enkele tegenvoorbeelden: “00” “007”.
  4. Breid deze grammatica uit voor getallen met een decimale punt. Welke eindsymbo(o)l(en) krijg je er dan bij?

​

★ Aan de slag 64

Gegeven is de volgende grammatica voor (iets minder eenvoudige) zinnen.
Het startsymbool is Z:

1. Z  -> Ow Gz Lv
2. Ow -> Zd
3. Gz -> "bijt" | "aait"
4. Lv -> Zd
5. Zd -> "de" "man" | "de" "hond" | Ow "die" Lv Gz 

  1. Laat zien dat je hiermee zinnen kunt maken als “de hond bijt de man die de hond aait”.
  2. Geef een voorbeeld van een zin die tweemaal zo lang is.

Toets 1

In de volgende toets wordt getoetst wat je inmiddels zou moeten weten over het onderwerp grondslagen.
Maak de toets:

Grondslagen

Voortgang

Bekijk hier je voortgang

Kernprogramma

 

Docent kan groepen aanmaken en leerlingen volgen
Een docent kan op de profielpagina groepen aanmaken. Als een docent dat gedaan heeft, kunnen de leerlingen zich aan de groep koppelen. Als de leerlingen dat gedaan hebben, kan de docent de voortgang van de leerlingen volgen.

>> Inlogpagina gebruikersaccount

Log hier in met je Entree account.

Om toegang te krijgen tot Portfolio-site, log je in bij Mijn VO-content en klik je op Entree.



Log in met je SCHOOLACCOUNT

 

Profielpagina

Als je ingelogd bent, vul je profielpagina verder in. Je kunt de niveaus aanklikken (waar je lesmateriaal van wilt zien voor de andere programma's) en ook de vakken. De profielpagina werkt voor alle Extra Programma's van VO-content.

Je kunt deze keuzes achteraf ook altijd aanpassen.
Let op: verifieer je e-mailadres na de eerste keer inloggen. Als je dat gedaan hebt kan je bij een storing van de ELO of Entree alsnog met je e-mailadres inloggen.

 
 
 

  • Het arrangement Module: Enigma - Grondslagen is gemaakt met Wikiwijs van Kennisnet. Wikiwijs is hét onderwijsplatform waar je leermiddelen zoekt, maakt en deelt.

    Auteur
    VO-content
    Laatst gewijzigd
    2025-07-19 08:54:41
    Licentie

    Dit lesmateriaal is gepubliceerd onder de Creative Commons Naamsvermelding 4.0 Internationale licentie. Dit houdt in dat je onder de voorwaarde van naamsvermelding vrij bent om:

    • het werk te delen - te kopiëren, te verspreiden en door te geven via elk medium of bestandsformaat
    • het werk te bewerken - te remixen, te veranderen en afgeleide werken te maken
    • voor alle doeleinden, inclusief commerciële doeleinden.

    Meer informatie over de CC Naamsvermelding 4.0 Internationale licentie.

    Aanvullende informatie over dit lesmateriaal

    Van dit lesmateriaal is de volgende aanvullende informatie beschikbaar:

    Toelichting
    Deze module is onderdeel van de arrangeerbare leerlijn van de Stercollecties voor het kerndeel van Informatica voor hv456. In de module Grondslagen behandelen we de basisprincipes van informatie en rekenen. In de informatica is rekenen het manipuleren van vormen, volgens bepaalde regels. Deze voorschriften noem je ook wel algoritmes. In deze module leer je daarmee werken. Daarnaast ga je meer leren over informatieprocessen en verschillende structuren die daarbij passen. In ieder onderdeel vind je, verdeeld over verschillende pagina's, informatie in de vorm van teksten, afbeeldingen en video's. Daarnaast ga je zelf aan de slag met toepassingsopdrachten en toetsen. Van de toetsen wordt je voortgang bijgehouden en deze voortgang zal zowel door jou als je docent te bekijken zijn. Veel succes!
    Leerniveau
    HAVO 4; VWO 6; HAVO 5; VWO 4; VWO 5;
    Leerinhoud en doelen
    Informatica;
    Eindgebruiker
    leerling/student
    Moeilijkheidsgraad
    gemiddeld
    Trefwoorden
    algoritme, arrangeerbaar, boomstructuren, enigma- grondslagen, hv456, informatica, informatie, informatieproces, kerndeel, stercollectie

  • Downloaden

    Het volledige arrangement is in de onderstaande formaten te downloaden.

    Metadata

    LTI

    Leeromgevingen die gebruik maken van LTI kunnen Wikiwijs arrangementen en toetsen afspelen en resultaten terugkoppelen. Hiervoor moet de leeromgeving wel bij Wikiwijs aangemeld zijn. Wil je gebruik maken van de LTI koppeling? Meld je aan via info@wikiwijs.nl met het verzoek om een LTI koppeling aan te gaan.

    Maak je al gebruik van LTI? Gebruik dan de onderstaande Launch URL’s.

    Arrangement

    IMSCC package

    Wil je de Launch URL’s niet los kopiëren, maar in één keer downloaden? Download dan de IMSCC package.

    Voor developers

    Wikiwijs lesmateriaal kan worden gebruikt in een externe leeromgeving. Er kunnen koppelingen worden gemaakt en het lesmateriaal kan op verschillende manieren worden geëxporteerd. Meer informatie hierover kun je vinden op onze Developers Wiki.

  • Gebruik
    Weergave
  • Wikiwijs is een dienst van