Eindige automaten
Nooddienstregeling bij de spoorwegen
Eindige automaten
Nooddienstregeling bij de spoorwegen
Leerdoel
Je weet wat een eindige automaat is, kent een aantal van haar eigenschappen en kunt een toestandsdiagram lezen/ begrijpen.
Tenslotte kun je met je computer testen of de invoer van een automaat geldig is.
CODE ROOD!
Nooddienstregeling bij de spoorwegen
CODE ROOD!
Naar de powerpoint met de werkvorm...
Welke route is geldig?
AAB
ABABAB
BBBAA
BABBBBAA
Eindige automaat
Apparaten die eenvoudige, voorspelbare taken hebben en steeds hetzelfde gedrag vertonen worden ook wel eindige automaten genoemd. Denk maar aan apparaten als een snoepautomaat, een verkeerslicht en een lift.
minute
second
Wat is de kortst mogelijke geldige route?
Kortste route?
De kortst mogelijke route is: BBAB.
Is het mogelijke een langste route te bepalen?
Ja
Nee
Hangt van de automaat af
Is het mogelijk een langste route te bepalen?
Bij deze specifieke automaat is het niet mogelijk de langste route te bepalen omdat je in rondjes kan blijven rijden. Bij automaten die niet terugkeren naar een eerder punt is dit wel mogelijk.
Wat is de kortst mogelijke geldige route die alle stations aandoet?
Wat is de kortst mogelijke geldige route die alle stations precies één keer aandoet?
De kortst mogelijke route die alle routes precies één keer aandoet is: ABABAB. We noemen dit ook wel een Hamilton-pad (of Hamilton-circuit als het weer bij het begin uitkomt).
c
Leerdoel gehaald?
Je weet wat een eindige automaat is, kent een aantal van haar eigenschappen en kunt een toestandsdiagram lezen/ begrijpen.
Tenslotte kun je met je computer testen of de invoer van een automaat geldig is.
Doornemen en maken
Informatica Baas -> Grondslagen -> Eindige automaten
3.1 & 3.2 Doorlezen, experimenteren
en maken vragen
3.3 Opdracht: de schatzoeker (maken &
inleveren)
Eindige automaten
Ontwerpen en eigenschappen
Leerdoel
Je kunt uitleggen wat een eindige automaat is, kent een aantal van haar eigenschappen en kunt een toestandsdiagram ontwerpen/ uitbreiden.
Eindige automaat
Apparaten die eenvoudige, voorspelbare taken hebben en steeds hetzelfde gedrag vertonen worden ook wel eindige automaten genoemd. Denk maar aan apparaten als een snoepautomaat, een verkeerslicht en een lift.
Eigenschappen eindige automaten
is steeds maar in één toestand,
kan van toestand veranderen en
heeft eindig veel toestanden.
Symbolen eindige automaten
Toestandsdiagram slimme thermostaat
Het gedrag van een slimme thermostaat kan (globaal) beschrijven worden met dezelfde eindige automaat.
Toestandsdiagram lift
Dit geldt ook voor het gedrag van een lift.
Eindige automaten kunnen
we op een overzichtelijke manier
weergeven in een schema.
Zo'n schema noemen we een
toestandsdiagram.
Toestandsdiagram lift
De cirkels staan voor de drie toestanden van de lift:
de verdiepingen waar de lift naartoe kan.
BG is de begane grond
1 is de eerste verdieping
2 is de tweede verdieping
De pijlen geven de mogelijke
toestandsovergangen (‘transities’)
mogelijk zijn.
Toestandsdiagram lift
De automaat kent 2 verschillende soorten transities:
Reizen tussen verdiepingen:
Bijvoorbeeld van BG naar 1 (omhoog) of
van 2 naar BG (omlaag).
Zelf-loops (Self-loops):
Als de lift al op verdieping 1 staat en er
wordt op knop 1 gedrukt, blijft de lift op 1.
De toestand verandert niet, wel vindt er
een transitie plaats naar dezelfde toestand!
Begin- en eindtoestand
Verkeerslichten en liften werken altijd, tenzij ze worden uitgezet. Ze hebben geen speciale begintoestand en geen eindtoestand.
Om deze reden tekenen we ze niet in
de toestandsdiagrammen waarin we hun
gedrag beschrijven. Is er wel sprake van
een duidelijke begin- en eindtoestand,
dan moet dit dus wel!
Hoeveel verschillende toestanden en transities (inclusief self-loops) kent dit diagram?
3 toestanden, 6 transities
3 toestanden, 9 transities
6 toestanden, 3 transities
9 toestanden, 3 transities
2 verkeerslichten
Bij een wegafzetting wordt vaak gebruikgemaakt van twee mobiele verkeerslichten om het verkeer te regelen. Die verkeerslichten werken eenvoudig: elk verkeerslicht staat een vast aantal seconden op rood, groen of oranje. Als het ene verkeerslicht groen of oranje is, is het andere verkeerslicht rood.
We kijken eerst naar één verkeerslicht.
Teken het schema van een eindige automaat met
daarin de drie toestanden van een verkeerslicht.
Voeg de mogelijke transities toe.
minute
second
Hoeveel transities heb je nodig om dit toestandsdiagram te tekenen?
1
2
3
4
Antwoord verkeerslicht
Bij een wegafzetting wordt vaak gebruikgemaakt van twee mobiele verkeerslichten om het verkeer te regelen. Die verkeerslichten werken eenvoudig: elk verkeerslicht staat een vast aantal seconden op rood, groen of oranje. Als het ene verkeerslicht groen of oranje is, is het andere verkeerslicht rood.
Antwoord: er zijn 3 transities nodig
om het toestandsdiagram te tekenen.
Verkeerslicht 2
Bij een wegafzetting wordt vaak gebruikgemaakt van twee mobiele verkeerslichten om het verkeer te regelen. Die verkeerslichten werken eenvoudig: elk verkeerslicht staat een vast aantal seconden op rood, groen of oranje. Als het ene verkeerslicht groen of oranje is, is het andere verkeerslicht rood.
Je gaat nu de situatie van twee gekoppelde verkeerslichten
bekijken. Noem ze verkeerslicht 1 en 2. Noteer de toestand
‘Verkeerslicht 1 is rood en verkeerslicht 2 is groen’ als r1 g2.
De verkeerslichten samen hebben maar een paar mogelijke
toestanden. Welke toestanden zijn dat?
minute
second
Hoeveel mogelijke toestanden heb je gevonden?
1
2
3
4
Antwoord 2 verkeerslichten
Bij een wegafzetting wordt vaak gebruikgemaakt van twee mobiele verkeerslichten om het verkeer te regelen. Die verkeerslichten werken eenvoudig: elk verkeerslicht staat een vast aantal seconden op
rood, groen of oranje. Als het ene
verkeerslicht groen of oranje is, is het
andere verkeerslicht rood.
Er zijn 4 mogelijke toestanden:
r1g2, r1o2, g1r2 en o1r2.
Schema verkeerlichten
Bij een wegafzetting wordt vaak gebruikgemaakt van twee mobiele verkeerslichten om het verkeer te regelen. Die verkeerslichten werken eenvoudig: elk verkeerslicht staat een vast aantal seconden op rood, groen of oranje. Als het ene verkeerslicht groen of oranje is, is het andere verkeerslicht rood.
Teken het schema van een eindige automaat bij de situatie:
r1g2, r1o2, g1r2 en o1r2.
Van groen naar oranje duurt 30 sec. Van oranje naar rood
duurt 3 sec. Vermeld dit bij de juiste toestand.
minute
second
Hoelang duurt een hele rondgang?
30 sec.
33 sec.
60 sec.
66 sec.
Antwoord schema verkeerlichten
Bij een wegafzetting wordt vaak gebruikgemaakt van twee mobiele verkeerslichten om het verkeer te regelen. Die verkeerslichten werken eenvoudig: elk verkeerslicht staat een vast aantal seconden op rood, groen of oranje. Als het ene verkeerslicht groen of oranje is, is het andere verkeerslicht rood.
Antwoord: Een hele rondgang duurt
30 + 3 + 30 + 3 = 66 sec.
30
30
3
3
Een eindige automaat kan in meer dan één toestand zijn.
Waar
Onwaar
In een toestandsdiagram zie je in welke toestand de eindige automaat zich bevindt.
Waar
Onwaar
Een eindige automaat kan van een toestand naar dezelfde toestand gaan.
Waar
Onwaar
Er kan maar één eindtoestand zijn.
Waar
Onwaar
Er kan maar één begintoestand zijn.
Waar
Onwaar
Een eindige automaat houdt bij in welke toestanden hij is geweest.
Waar
Onwaar
Leerdoel gehaald?
Je kunt uitleggen wat een eindige automaat is, kent een aantal van haar eigenschappen en kunt een toestandsdiagram ontwerpen/ uitbreiden.
Doornemen en maken
Informatica Baas -> Grondslagen -> Eindige automaten
3.4 & 3.5 Doorlezen, experimenteren
en maken vragen
3.6 Opdracht: de bewaker (maken &
inleveren)