Grondslagen lessenserie Roomba

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

 Rrrrrrroombaargh!

Wat gaan wij doen de komende lessen?

Les 1: Eindige Automaten

• DFA
  
• NFA
  

Les 2: Toestandsdiagrammen

• Toestanden
  
• Overgangen

Leerdoelen

• Je kunt uitleggen wat een eindige automaat is.
  
• Je kunt in een toestandsdiagram een toestand en een toestandsovergang aanwijzen.
  
• Je kunt in een toestandsdiagram de begintoestand en mogelijke eindtoestanden aanwijzen.
  
• Je kunt een eindige toestandsautomaat doorlopen bij gegeven overgangen.
  
• Je kunt een relatie leggen tussen de toestand van de Roomba en het gedrag van de Roomba.
  
• Je begrijpt dat de automaat los staat van de gebruikte context.
  
• Je kunt een valide serie overgangen noemen en niet valide overgangen herkennen.
  

Les 1: Eindige automaten

Het woord eindig geeft hier aan dat een systeem op enig moment maar in één bepaalde toestand tegelijk kan bevinden.

Bij een Roomba is dit ook het geval, dat zal je zo zien. 

Een verkeerslicht is ook een voorbeeld van een eindige automaat. Welke toestanden kent een verkeerslicht?

Normaal verkeerslicht

Voetgangerslicht

Wat voor toestanden kan een Roomba hebben?

DFA & NDFA

Bij een deterministische eindige automaat (ook wel DFA genoemd)komt elke overgang maar 1 keer voor per toestand.

 

Een niet-deterministische eindige automaat (ook wel NDFA genoemd) kan dezelfde overgang hebben naar verschillende toestanden.

Wat is hier een NDFA?

1. Spraakherkenning
2. Pacman
3. Boter, kaas & eieren
4. Drankjesmachine

Geef een voorbeeld van een DFA

Is een Roomba een DFA of een NDFA?

NFA

DFA

Zelfstandig werken

Ga aan de slag met de hand-out.

-> Lees de stof + uitleg

-> Ga aan de slag met de vragen

-> Klaar? Check jezelf

Wat heb je vandaag geleerd?

De les was

leerzaam

niet leerzaam

Volgende les:

Toestandsdiagrammen toepassen op eindige automaten

Les 2: Toestandsdiagrammen

Een toestandsdiagram is een grafische weergave van de verschillende toestanden waarin de eindige automaat zich kan bevinden. 

Ook wordt in de toestandsdiagram de mogelijke eindtoestand aangegeven.

Toestandsdiagrammen

Toestanden zijn bolletjes

Overgangen zijn pijlen

Begintoestand heeft een instroompijl.

Eindtoestand is bolletje met dubbele rand.

Wat mist bij dit
toestandsdiagram?

Elementen en structuur van toestandsdiagram

Voorwaardelijke overgangen

• Aan toestandsovergangen mag je voorwaarden koppelen (guards)
• Alleen bij voldoen aan de voorwaarde kan de overgang plaatsvinden
• Guards staan tussen deze [haken]
• (let op: dit staat niet in de stof!)

Wat klopt niet in dit toestandsdiagram?

Het toestandsdiagram hiernaast betreft een telefoon.
Welke teksten kunnen bij de letters A t/m D staan?
(© TU Delft)

1. A: na 30 seconden B: gesprek beëindigen C: gesprek doorschakelen D: opnemen
2. A: gesprek beëindigen B: opnemen C: gesprek doorschakelen D: voicemail inspreken
3. A: na 30 seconden B: gesprek beëindigen C: opnemen D: in gesprek
4. A: gesprek beëindigen B: voicemail inspreken C: gesprek doorschakelen D: opnemen

Zelfstandig werken

Ga aan de slag met de hand-out.

-> Lees de stof + uitleg

-> Ga aan de slag met de vragen

-> Klaar? Check jezelf

Wat heb je vandaag geleerd?

De les was

leerzaam

niet leerzaam

Behaald

(Nog) niet behaald

Leerdoel 1

Leerdoel 2

Leerdoel 3

Leerdoel 4

Leerdoel 5

Leerdoel 6

Leerdoel 7