Algoritme Les 4

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

Eindige automaten

vandaag

eindige automaten

waarom?

Toestandsdiagram

afspraken

Een smartphone is dus een voorbeeld van een apparaat dat:
•    Complexe taken uitvoert.
•    Gedrag vertoont dat voortdurend verandert.

Noem een apparaat die altijd hetzelfde gedrag vertoont

een lift

De lift gaat van en naar de begane grond en twee verdiepingen. De lift is ontworpen om het volgende te kunnen doen:
•    Stilstaan op een van de verdiepingen.
•    Onderweg zijn naar een andere verdieping.

Het gedrag van de lift kunnen we beschouwen als een

eindige toestandsautomaat.

eindige toestandsautomaat

Dat is een apparaat dat zich in een bepaalde vaste toestand bevindt en dat kan overgaan naar een andere toestand.

In plaats van de term eindige toestandsautomaat gebruiken we meestal het kortere eindige automaat.

Terug naar de lift

De lift bevindt zich in één van de drie vaste toestanden, dat zijn de verdiepingen waarop de lift stilstaat. De lift kan naar een andere toestand (een andere verdieping) overgaan.

Een verkeerslicht

Een verkeerslicht is ook een voorbeeld van een eindige automaat. Het heeft slechts drie toestanden: rood, groen en oranje. Bij een verkeerslicht gaat de overgang van de ene naar de andere toestand heel snel. In een fractie van een seconde schakelt het over van rood naar groen. Bij een lift duurt een toestandsovergang wat langer.

Gedrag van een apparaat

Als we een apparaat een eindige automaat noemen, dan bedoelen we dat het zich gedraagt als een eindige automaat. Een lift is daarvan een voorbeeld. Toch kan er in de lift een computer zijn ingebouwd die hele andere en complexe taken uitvoert. Denk aan een verbinding maken met het internet om een storing door te geven. Maar dat verandert niets aan waar de lift voor bedoeld is.

Internet of Things

Sinds de opkomst van het Internet Of Things zijn veel alledaagse apparaten aangesloten op het internet. Denk aan zonnepanelen waarvan je online de opbrengst kunt volgen. Of een thermostaat die je met een app kunt bedienen. In zijn gedrag is een thermostaat een eindige automaat. Maar in de praktijk is er een (complexe) computer in de thermostaat verwerkt.

In de praktijk zijn apparaten dus nooit echte eindige automaten. Waarom zijn ze dan toch belangrijk?

Er zijn 3 redenen hiervoor:

Inzicht in een probleem

Eindige automaten helpen je om een complex probleem helder en overzichtelijk te maken. Een voorbeeld daarvan is een druk kruispunt waar verkeerslichten worden geplaatst. Door een eindige automaat te ontwerpen zorg je voor een helder overzicht van alle verkeersstromen die tegelijk over de kruising mogen. Ook krijg je inzicht in hoe de verkeerslichten ingesteld moeten worden.

Veilig ontwerpen

Eindige automaten zijn ook een handig hulpmiddel om een apparaat, of een onderdeel daarvan, veilig te ontwerpen. Zo mag een wasmachine pas gaan werken als er water beschikbaar is. Een lift mag pas omhoog of omlaag als de deuren dicht zijn. Bij het ontwerpen van een eindige automaat wordt je gedwongen om alle toegestane toestanden in kaart te brengen.

Theoretische informatica

Ten slotte spelen eindige automaten een belangrijke rol in de theoretische informatica. We hebben al gezien dat het belangrijk is om te bepalen of een algoritme efficiënt is. Ook weten we dat niet elk probleem door een computer correct kan worden opgelost. Eindige automaten zijn een belangrijk hulpmiddel om de efficiëntie en correctheid van een algoritme te bepalen.

Eindige automaten ontwerpen

Eindige automaten kun je op een overzichtelijke manier weergeven in een schema. Zo'n schema noem je een toestandsdiagram. Het gedrag van een verkeerslicht kunnen we zo weergeven met een toestandsdiagram

Een stoplicht kent drie toestanden, Groen, Geel en Rood. Bij deze toestanden horen ook overgangen van een toestand naar een ander. Deze overgangen noemen we transities en zijn aangegeven met een pijl.

Dit stoplicht kan vanuit de toestand Groen overgaan in de toestand Geel, vanuit de toestand Geel naar de toestand Rood en vanuit de toestand Rood weer terug naar de toestand Groen. Omdat er geen transitie bestaat vanuit de toestand Groen naar de toestand Rood is die overgang dus niet mogelijk.

In het buitenland komen ook wel stoplichten voor die vanuit Rood niet direkt naar Groen gaan, maar eerst Geel worden. Wat zou je moeten veranderen om dit toestandsdiagram geschikt te maken voor een stoplicht zoals dat in het buitenland gebruikt wordt?

Het stoplicht dat hier beschreven is, zou gebruikt kunnen worden voor fietsers en auto’s. Een stoplicht toestandsdiagram voor voetgangers ziet er iets anders uit. Probeer dat eens voor jezelf te tekenen.

De lift

De cirkels staan voor de drie toestanden van de lift: de verdiepingen waarheen de lift heen kan. BG is de begane grond. 1 is de eerste verdieping. 2 is de tweede verdieping. De pijlen geven aan welke toestandsovergangen mogelijk zijn.

Eigenschappen van eindige automaten

Een eindige toestandsautomaat:

•    is steeds maar in één toestand,
•    kan van toestand veranderen
•    heeft eindig veel toestanden.

Begin- en eindtoestand

Verkeerslichten en liften werken altijd, tenzij ze worden uitgezet. Ze hebben geen speciale begintoestand en geen eindtoestand. Veel automaten hebben wel een duidelijke begintoestand en één of meerdere eindtoestanden. De eindtoestand is de toestand waarin de automaat mag stoppen. Voor de begin- en eindtoestand bestaat er een speciale notatie.

Een toestandsdiagram voor een snoepautomaat

Begint bij een nul-inworp van geld. Vervolgens kunnen er verschillende munten in de automaat gestopt worden, waardoor er verschillende transities zijn naar een nieuw saldo. Zodra een saldo voldoende is, kan een keuze gemaakt worden, wordt eventueel wisselgeld teruggegeven en bereikt de automaat zijn eindtoestand.

Toestand

Begintoestand

Eindtoestand

Transitie

Wat heb je geleerd deze les?