Algoritme Les 13

• Informatica
• Middelbare school
• havo, vwo
• Leerjaar 4

vandaag

• Beperkingen van een eindige automaat
• Turing machine
  

Je hebt gezien dat een automaat tekst kan controleren. Bijvoorbeeld of iets een postcode is. Wachtwoorden moeten vaak voldoen aan bepaalde bijzondere voorwaarden. Denk aan een minimaal aantal hoofdletters, kleine letters en vreemde tekens. Het is erg moeilijk om daarvoor een eindige automaat te maken. Het moet dan bijvoorbeeld het aantal vreemde tekens tellen die op verschillende plaatsen in het wachtwoord staan.

Beperkingen van een eindige automaat

Eindige automaten kom je ook tegen in andere vakgebieden dan informatica. Zo kunnen scheikundige processen op het niveau van moleculen vaak goed beschreven worden als een eindige automaat. Datzelfde geldt voor het delen van het DNA in een cel. Allerlei processen zijn dus te beschrijven als een eindige automaat.

Toch heeft een eindige automaat ook beperkingen. Het kan alleen dienen als een eenvoudig algoritme. Bijvoorbeeld voor het bedienen van een verkeerslicht. En in de automaat bij de game  kun je het gedrag van de tegenstander alleen heel globaal weergeven. Hoe de tegenstander moet vechten, wordt niet duidelijk.

Geheugen

Hoe komt het dat een eindige automaat niet erg geschikt is om te tellen? Het antwoord is eenvoudig. Hij kan input verwerken en genereert ook output, maar heeft geen geheugen om gegevens in op te slaan. Daarom kan hij niet goed tellen en rekenen. Om de uitkomst op te slaan, heb je geheugen nodig. Zonder geheugen zijn ook de standaardalgoritmen zoals je die kent niet uit te voeren met een eindige automaat.

Flexibiliteit

Een gewone computer heeft meer mogelijkheden dan een eindige automaat. Een computer, bijvoorbeeld je smartphone is flexibel. Omdat het geheugen heeft, kun je er nieuwe apps op installeren en uitvoeren. Daardoor gaat het ander gedrag vertonen. Een eindige automaat vertoont altijd hetzelfde gedrag en is dus niet flexibel.

Ga uit van tekst die alleen de letters a-z, A-Z, punten, komma’s en spaties bevatten.
Voor welke van de volgende problemen kun je een eindige automaat ontwerpen?

Je wilt controleren of een woord met een hoofdletter begint

1. wel
2. niet

Je wilt controleren of in een tekst elke zin begint met een hoofdletter en eindigt met een punt

1. wel
2. niet

Je wilt controleren of een zin twee woorden bevat

1. wel
2. niet

Je wilt controleren of een zin minstens twee woorden bevat

1. wel
2. niet

Je wilt controleren of een zin hoogstens twee woorden bevat

1. wel
2. niet

Je wilt controleren of een woord voor de helft uit klinkers bestaat

1. wel
2. niet

Je wilt controleren of een woord aaneengesloten klinkers bevat.

1. wel
2. niet

De Turingmachine

De wiskundige Alan Turing bedacht in 1936 een machine die niet de beperkingen heeft van een eindige automaat. Die machine wordt universele Turingmachine genoemd. De machine bestaat uit drie onderdelen:

1. Een eindige automaat,
2. een band die verdeeld is in vakjes waarin 1, 0 of niets staat,
3. een lees/schrijfkop die de band kan lezen en er op kan schrijven.

De lees/schrijfkop bevindt zich steeds boven één van de vakjes en kan één positie vooruit of achteruit bewegen over de band. Hij kan ook lezen wat er in een vakje staat. Tot slot kan hij een 1 of 0 in het vakje schrijven of het vakje leegmaken.

werking Alan Turing machine