Les 1 & 2 - Eindige automaten en een nooddienstregeling bij de spoorwegen

Eindige automaten

Nooddienstregeling bij de spoorwegen

1 / 64
volgende
Slide 1: Slide
newEditorInformaticaMiddelbare schoolhavo, vwoLeerjaar 4-6

In deze les zitten 64 slides, met interactieve quizzen en tekstslides.

time-iconLesduur is: 50 min
Dit is niet oké

Onderdelen in deze les

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?

A

AAB

B

ABABAB

C

BBBAA

D

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.

15

minute

00

second

Wat is de kortst mogelijke geldige route?

Kortste route?

De kortst mogelijke route is: BBAB.

Is het mogelijke een langste route te bepalen?

A

Ja

B

Nee

C

Hangt van de automaat af

D


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?

A

3 toestanden, 6 transities

B

3 toestanden, 9 transities

C

6 toestanden, 3 transities

D

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.


1

minute

00

second

Hoeveel transities heb je nodig om dit toestandsdiagram te tekenen?

A

1

B

2

C

3

D

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?


1

minute

00

second

Hoeveel mogelijke toestanden heb je gevonden?

A

1

B

2

C

3

D

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.


1

minute

00

second

Hoelang duurt een hele rondgang?

A

30 sec.

B

33 sec.

C

60 sec.

D

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.

A

Waar

B

Onwaar

C


D


In een toestandsdiagram zie je in welke toestand de eindige automaat zich bevindt.

A

Waar

B

Onwaar

C


D


Een eindige automaat kan van een toestand naar dezelfde toestand gaan.

A

Waar

B

Onwaar

C


D


Er kan maar één eindtoestand zijn.

A

Waar

B

Onwaar

C


D


Er kan maar één begintoestand zijn.

A

Waar

B

Onwaar

C


D


Een eindige automaat houdt bij in welke toestanden hij is geweest.

A

Waar

B

Onwaar

C


D


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)