Grondslagen - Reggesteyn

Grondslagen - Reggesteyn

A Inleiding

Leerdoelen

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

  • weet je dat communicatie gaat over vormen en betekenis geven;
  • weet je dat het verband tussen een vorm en een betekenis een kwestie van afspraak (conventie) is;
  • kun je uitleggen waarom sommige vormen handiger zijn om mee te werken dan andere vormen;
  • weet je het verschil tussen een analoge en een digitale vorm;
  • kun je uitleggen wat een symbolische vorm is;
  • kun je uitleggen wat wordt bedoeld met “informatie stuurt”;
  • weet je wat bij informatica met een boom bedoeld wordt;
  • kun je uitleggen wat wordt bedoeld met een recursieve structuur;
  • kun je de verschillende niveaus in een boom onderscheiden;
  • kun je voorbeelden geven van boomstructuren;
  • weet je wat bedoeld wordt met paden in een boom;
  • weet je wat een binaire zoekboom is;
  • weet je wat een ontleedboom is;
  • weet je wat bij informatica met rekenen bedoeld wordt;
  • kun je uitleggen wat een algoritme is;
  • weet je wat cellulaire automaten zijn;
  • weet je wat het verschil is tussen een ééndimensionale – en een tweedimensionale cellulaire automaat;
  • weet je wat wordt bedoeld met rule 110;
  • kun je de onderdelen van een eindige automaat benoemen;
  • weet je wat lineair en binair zoeken is;
  • weet je wat het verschil tussen map en reduce is;
  • weet je waarvoor grammatica’s gebruikt worden;
  • weet je 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.

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.

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 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?
  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.
  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.

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 11

Humpty Dumpty

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?

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

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

  1. Wat bepaalt de nauwkeurigheid waarmee het oorspronkelijke analoge geluidssignaal wordt benaderd?
  2. Wat is het verschil tussen geluid in PCM-formaat en in MP3-formaat?

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.

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

Welke van de onderstaande vormen zijn analoog, welke symbolisch?

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

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.

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

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

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.

Voorbeeld: HTML

HTML (Hyper Text Markup Language) is de taal voor het beschrijven van webpagina's, als HTML-documenten. Met een webbrowser kun je deze HTML-documenten bekijken.
De structuur van een HTML-document geef je weer met behulp van speciale symbolen: tags.

Deze tags komen meestal in (haakjes)paren: de inhoud van het element staat tussen deze haken.
Een tag heeft de vorm <tagname> (voor een openingshaak) of </tagname> (voor de bijbehorende sluithaak).
Voorbeelden: <html>...</html>, <p>...</p>, <div>... </div>

Voorbeeld van een eenvoudig HTML-document:

<!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>

Door middel van inspringen geven we de structuur van het document weer (“horizontale boomstructuur”).
We kunnen deze structuur ook tekenen als een “normale” boom:

HTML-boom


CSS
De structuur van een HTML-document is van belang bij het vormgeven hiervan in de browser. Als je de opmaak van een knoop verandert, bijvoorbeeld de kleur of het lettertype, verandert de opmaak van de hele bijbehorende subboom. Anders gezegd: de kindknopen in de boom erven de opmaak van de ouderknoop. Dit is het “cascading” aspect van “cascading style sheets” (Wikipedia: CSS).

JavaScript
In JavaScript in de browser gebruik je de DOM: Document Object Model. Dit is een boomstructuur die afgeleid is van het oorspronkelijke HTML-document. Je voert in JavaScript operaties uit op deze boomstructuur, in plaats van op het HTML-document. De browser geeft steeds de actuele inhoud van de DOM weer.

★ Aan de slag 26

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 27

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 28

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.

★ Aan de slag 29

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

Als we de elementen in een boom op een handige manier organiseren, dan kunnen we hierin efficiënt zoeken.

Een binaire boom is een boom waarbij elke knoop 2 subbomen heeft: een linker- en een rechter subboom. Hierbij kan een subboom leeg zijn.

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.

Voorbeeld van een binaire zoekboom:

Binaire zoekboom


In een dergelijke boom kunnen we efficiënt zoeken: het aantal zoekstappen is ongeveer 2log(N)2log(N). Dit is eigenlijk een vorm van binair zoeken (Binary Search); in het gedeelte over Zoeken en sorteren gaan we daar verder op in. Je zoekt in een binaire zoekboom op de volgende manier:

  • als de waarde die je zoekt gelijk is aan de waarde in de wortel, dan ben je klaar;
  • als de waarde die je zoekt kleiner is dan de waarde in de wortel, dan zoek je op dezelfde manier met de linker subboom als wortel;
  • als de waarde die je zoekt groter is dan de waarde in de wortel, dan zoek je op dezelfde manier met de rechter subboom als wortel.

Je krijgt op deze manier een pad van de wortel naar de uiteindelijke knoop met de gezochte waarde. Dit pad kun je ook gebruiken voor het identificeren van de plek van de knoop in de boom.

Het zoekproces in een binaire zoekboom is alleen efficiënt als de boom redelijk gebalanceerd is: voor elke subboom is dan het aantal knopen links en rechts ongeveer gelijk. De hoogte van de boom is dan ongeveer 2log(N)2log(N), waarbij N het aantal knopen in de boom is.
Voorbeeld: voor 1000 knopen is de hoogte ongeveer 10 (210=1024210=1024).

Links

 

★ Aan de slag 30

Gegeven is de zoekboom van de vorige pagina.

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).

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 31

  1. Zoek op het web naar een video over “peanut butter jelly sandwich instructions”.
  2. Wat maakt deze video duidelijk?

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 33

Call centra maken vaak gebruik van call scripts.

  1. Zoek een voorbeeld van een call script (dat je in praktijk tegen kunt komen).
  2. Bestudeer het EGBG tegenscript.
  3. Geef aan op welke manier daarin de volgende elementen genoteerd worden: (i) opeenvolging, (ii) keuze, (iii) invoer, (iv) uitvoer.

★ Aan de slag 34

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 35

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 36

Zoekalgoritme

Waaruit bestaat de invoer voor het Google zoekalgoritme dat uitgevoerd wordt als je een zoekopdracht geeft?

★ Aan de slag 37

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?

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 38

  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 39

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 40

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 41

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

Het spel Game of Life is een voorbeeld van een tweedimensionale cellulaire automaat:
het spel speelt zich af in het platte vlak.
In dit gedeelte gaan we verder in op eendimensionale cellulaire automaten: een toestand bestaat uit een reeks cellen op één lijn.
Je kunt de opeenvolgende toestanden dan onder elkaar plaatsen: in het platte vlak zie je dan in één oogopslag het proces: de ontwikkeling van het algoritme in de tijd.

In een eendimensionale cellulaire automaat heeft een cel 2 buren: links en rechts.
De volgende toestand van een cel hangt af van de huidige toestand van de cel en zijn twee buren.
Voor 3 cellen heb je 8 mogelijke configuraties. De regels van de automaat beschrijven voor elke configuratie welke kleur cel deze oplevert.

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).

 

★ Aan de slag 42

Zoek uit waar de naam rule 110 vandaan komt.

★ Aan de slag 43




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 44

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 45

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

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
2 A X 1
3 A Y 0
4 A X 1
5 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 46

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 algoritmen
  • 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 47

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 48

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 49

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 =A1 =IF(B2<=C2,B2,C2) =IF(B2<=C2,C2,B2) =D1
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 50

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?

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]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]x[1..0]: deze rij bevat geen getallen, de som is dan 0.
Voor een willekeurige waarde n,n>0n,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]=0som[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]max[1]=x[1]
  • Stap n: max[n]=MAX(max[n−1],x[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.

  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)

(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.

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 55

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 56

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 57

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 58

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 klassen aanmaken en leerlingen volgen
Een docent kan op de profielpagina klassen aanmaken. Als een docent dat gedaan heeft, kunnen de leerlignen zich aan de klas koppelen. Als de leerlingen dat gedaan hebben, kan de docent de voortgang van de leerlingen volgen.

>> Profielpagina

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

    Auteur
    Tom van der Wal
    Laatst gewijzigd
    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:

    Eindgebruiker
    leerling/student
    Moeilijkheidsgraad
    gemiddeld
    Studiebelasting
    4 uur 0 minuten

    Gebruikte Wikiwijs Arrangementen

    van der Wal, Tom. (2020).

    Grondslagen - Stad en Esch

    https://maken.wikiwijs.nl/156289/Grondslagen___Stad_en_Esch

  • 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