Progettazione Unità DidatticaGli automiViola Anesin

Titolo Obiettivi trasversali

Obiettivi generali Prerequisiti Unità didattiche

Il sistema di elaborazione

•microlinguaggio•educazione al lavoro di gruppo•modellazione formale

•Cogliere l’aspetto sistemico del sistema di elaborazione e della sua logica di funzionamento•Conoscere le risorse hardware, software e le funzioni del S.O.

•Conoscenza terminologia informatica di base•Conoscenza elementi di algebra booleana

Gli Automi•Le risorse hardware e software •Dall’algoritmo al programma•Il sistema operativo Windows

Classe

• 3^ Istituto Tecnico Commerciale, indirizzo programmatori.• La classe di 19 alunni è abbastanza omogenea per competenze, ha appena terminato un modulo su nozioni di

base e richiami matematici (termini di uso comune, sistemi di numerazione, rappresentazione numeri, connettivi logici)

Modulo

Titolo Prerequisiti(oltre a quelli del modulo)

Strategie didattiche

Obiettivi specifici Obiettivi minimi

Obiettivi di eccellenza

ConoscenzeCompetenzeCapacità

Gli Automi

Conoscenze basilari dei concetti di Dato,Modello,Algoritmo,Processo,Processore.

lezione frontale con PowerPoint

•Conoscere la descrizione formale di automa, funzione di transizione e grafo di transizione•saper riconoscere il funzionamento di un automa dato il suo grafo o le sue tabelle •saper descrivere tramite grafo o tabelle il funzionamento di un automa dato•saper progettare un automa (tramite grafo o tabelle) che risponda a date caratteristiche di funzionamento, anche formalizzando un semplice sistema reale.

Conoscenza delle definizioni di automa, funzione di transizione, grafo di transizione

Progettare un automa, descrivendolo formalmente, a partire da un sistema reale anche moderatamente complesso

Conoscenze:•Descrizione formale automa, stati, input, output, funzione di transizione•Competenze:•Riconoscere la funzione di un automa•Comprendere i principi generali di funzionamento

Abilità•Rappresentare tramite grafo o tabelle il funzionamento di un automa, anche a partire da un sistema reale

Materiali Luoghi Tempi Keywords

Approfondimenti

Valutazione

•libro di testo A. Lorenzi, D. Rossi Basi teoriche dell’InformaticaProgettazione degli Algoritmi – Atlas da pag. 47 a pag. 52•Software Visual Automata Simulator (shareware)

Laboratorio

8 ore automa, stato, funzione di transizione

In laboratorio, simulazione di funzioni di transizione tramite il software Visual Automata Simulator

•verifica sommativa finale

Unità didattica

Gli AutomiGli Automi(1)(1)

Distributore automatico di bevande

E’ una macchina in grado di svolgere un compito in modo autonomo.Il suo funzionamento è regolato da un “procedimento” che descrive minuziosamente le operazioni da eseguire per ottenere la lattina in corrispondenza all’inserimento delle 2 monete:

UN ALGORITMO !

0,1€

(1) Le slides contegono riferimenti tratti dal libro di A. Lorenzi e D. Rossi Basi teoriche dell’Informatica -

Progettazione degli Algoritmi (Atlas) e dall’UD “Automi” di B.Franceschini - ITI Bolzano

0,1€cola

fanta

acqua

0,00€Importo inserito

annulla

Gli AutomiGli AutomiAlgoritmoAlgoritmo

STARTSTART

1. Attendi moneta1. Attendi moneta

2. Introduci moneta2. Introduci moneta

3. Introduci moneta3. Introduci moneta

4. Attendi richiesta bibita o restituzione monete4. Attendi richiesta bibita o restituzione monete

4. Emetti bibita o restituisci monete4. Emetti bibita o restituisci monete

5. GO START UNTIL Machine is OFF5. GO START UNTIL Machine is OFF

STOPSTOP

Gli AutomiGli AutomiStatoStato

Durante il suo funzionamento, la macchina Durante il suo funzionamento, la macchina viene caratterizzata dagli viene caratterizzata dagli STATI STATI che può che può assumere:assumere:

S0S0 Off (spenta)Off (spenta)

S1S1 On, in attesa moneta nr.1On, in attesa moneta nr.1S2S2 On, in attesa moneta nr.2On, in attesa moneta nr.2S3S3 On, in attesa scelta bevanda o restituzione On, in attesa scelta bevanda o restituzione

monetemonete

NB: gli NB: gli stati stati sono un “certo” numero, ben sono un “certo” numero, ben definito.definito.

Gli AutomiGli AutomiMessaggiMessaggi

Durante il suo funzionamento, la macchina emette Durante il suo funzionamento, la macchina emette ““MESSAGGIMESSAGGI” in corrispondenza ai passaggi di ” in corrispondenza ai passaggi di stato:stato:

Nessuno - S0 Nessuno - S0 Off (spenta)Off (spenta)

U0 U0 Visualizza Visualizza 0,000,00 € - S1 € - S1 On, in attesa moneta nr.1On, in attesa moneta nr.1U1 U1 Visualizza Visualizza 0,100,10 € - S2 € - S2 On, in attesa moneta nr.2On, in attesa moneta nr.2U3U3 Visualizza Visualizza €€!€€! se seleziono la bevanda senza aver se seleziono la bevanda senza aver

inserito l’importo sufficiente inserito l’importo sufficienteU2 U2 Visualizza Visualizza 0,200,20 € - S3 € - S3 On, in attesa conferma o restituzioneOn, in attesa conferma o restituzione

NB: I NB: I Messaggi Messaggi sono un “certo” numero, ben sono un “certo” numero, ben definito.definito.

Gli AutomiGli AutomiInputInput

Durante la permanenza nello stato Durante la permanenza nello stato SiSi, la macchina accetta , la macchina accetta ““InputInput” :” :Nessuno - S0 Nessuno - S0 Off (spenta)Off (spenta)

Input monetaInput moneta: : Accetta Accetta 0,10 € se è in stato S1 0,10 € se è in stato S1 in attesa moneta nr.1in attesa moneta nr.1

Input moneta: Input moneta: Accetta Accetta 0,10 € se è in stato S2 0,10 € se è in stato S2 in attesa moneta nr.2in attesa moneta nr.2

Input tastoInput tasto: : Accetta Accetta tastoscelta - S3 tastoscelta - S3 On, in attesa On, in attesa conferma o conferma o

restituzionerestituzione

Input tasto: Input tasto: Accetta Accetta tastorest - S3 tastorest - S3 On, in attesa On, in attesa conferma o conferma o

restituzionerestituzione

NB: Gli NB: Gli Input Input sono un “certo” numero, ben definito.sono un “certo” numero, ben definito.

Gli AutomiGli AutomiDefinizione di AutomaDefinizione di Automa

L’automa è completamente caratterizzato da:L’automa è completamente caratterizzato da:

1.1. l’insieme dei simboli di l’insieme dei simboli di inputinput I={i I={i11,i,i22,…,i,…,inn}}

2.2. L’insieme dei simboli di L’insieme dei simboli di outputoutput U={u U={u11,u,u22,…,u,…,umm}}

3.3. L’insieme dei possibili L’insieme dei possibili statistati S={s S={s11,s,s22,…,s,…,spp}}

4.4. La La funzione degli statifunzione degli stati successivi F(i successivi F(itt, s, st-1t-1))→→sstt

5.5. La La funzione delle uscitefunzione delle uscite G(i G(itt, s, st-1t-1) ) →→uutt

L’automa è la quintupla A=(I, U, S, F, G)L’automa è la quintupla A=(I, U, S, F, G)

Gli AutomiGli AutomiNel nostro casoNel nostro caso

l’insieme dei simboli di l’insieme dei simboli di input èinput è I={iI={imonetamoneta,i,itasto_colatasto_cola, i, itasto_fanta, tasto_fanta, iitasto_acqua, tasto_acqua, iitasto_annullatasto_annulla}}

L’insieme dei simboli di L’insieme dei simboli di outputoutput è U={u è U={u0,00€0,00€, u, u0,10€0,10€, u, u0,20€0,20€, u, u€€!€€!}}

L’insieme dei possibili L’insieme dei possibili stati èstati è S={s S={s0_spento0_spento, s, s1_attesa1^moneta1_attesa1^moneta, s, s2_attesa2^moneta2_attesa2^moneta, s, s3_attesa_tasto3_attesa_tasto}}

Le funzioni F degli stati successivi e G delle uscite sono:Le funzioni F degli stati successivi e G delle uscite sono:

S0S0 S1S1 S2S2 S3S3

S0S0 S2S2 S3S3 S3S3

S0S0 S1S1 S2S2 S1S1

S0 S0 S1S1 S2S2 S1S1

S0S0 S1S1 S2S2 S1S1

S0S0 S1S1 S1S1 S1S1

iimonetamoneta

IItasto_colatasto_cola

IItasto_fantatasto_fanta

IItasto_acquatasto_acqua

IItasto_annullatasto_annulla

S0S0 S1S1 S2S2 S3S3

--0,10€0,10€ 0,20€0,20€

--

--€€€€!! €€€€!! 0,00€0,00€

--€€€€!! €€€€!! 0,00€0,00€

--€€€€!! €€€€!! 0,00€0,00€

--0,00€0,00€ 0,00€0,00€ 0,00€0,00€

G F

Gli AutomiGli AutomiMatrice di transizioneMatrice di transizione

Posso unificare le due funzioni F (matrice degli satati successivi)Posso unificare le due funzioni F (matrice degli satati successivi)e G (matrice delle uscite) in un’unica funzione di transizione Te G (matrice delle uscite) in un’unica funzione di transizione T

T(iT(itt, s, st-1t-1))→(→(sst t , u, utt))rappresentata dalla matrice di transizionerappresentata dalla matrice di transizione

iimonetamoneta

IItasto_colatasto_cola

IItasto_fantatasto_fanta

IItasto_acquatasto_acqua

IItasto_annullatasto_annulla

S0S0 S1S1 S2S2 S3S3

S0 ,S0 ,

--

S2,S2,

0,10€0,10€

S3,S3,

0,20€0,20€

S3,S3,

0,00€0,00€

S0 ,S0 ,

--

S1, S1,

€€€€!!

S2,S2,

€€€€!!

S1,S1,

0,00€0,00€

S0 ,S0 ,

--

S1, S1,

€€€€!!

S2,S2,

€€€€!!

S1,S1,

0,00€0,00€

S0,S0,

--

S1, S1,

€€€€!!

S2,S2,

€€€€!!

S1,S1,

0,00€0,00€

S0 ,S0 ,

--

S1,S1,

0,00€ 0,00€

S1,S1,

0,00€0,00€

S1,S1,

0,00€0,00€

T

Gli AutomiGli AutomiGrafo di transizioneGrafo di transizione

L’automa si può rappresentare anche con un grafo, cioè una figura L’automa si può rappresentare anche con un grafo, cioè una figura composta da composta da nodinodi e e archi orientatiarchi orientati. . I nodi contengono gli stati, gli archi sono etichettati con l’input ed il I nodi contengono gli stati, gli archi sono etichettati con l’input ed il messaggio (uscita) corrispondente. messaggio (uscita) corrispondente. Nel caso del distributore di bevande si ha:Nel caso del distributore di bevande si ha:

S0

S2

S1

S3accensione

Imoneta/U0,20€

Imoneta/U0,10€

Itasto_scelta/U0,00€

Imoneta/U0,20€

Itasto_scelta/U€€!

Itasto_scelta/U€€!

Itasto_annulla/U0,00€

Itasto_annulla/U0,00€

Gli AutomiGli AutomiApprofondimenti / Attività di LaboratorioApprofondimenti / Attività di Laboratorio

Possiamo usare il software scaricabile dal sito Possiamo usare il software scaricabile dal sito http://www.cs.usfca.edu/~jbovet/vas.htmlhttp://www.cs.usfca.edu/~jbovet/vas.html

Questa applicazione permette di disegnare grafi di transizione e Questa applicazione permette di disegnare grafi di transizione e verificarne il funzionamento, come si può vedere nel video seguente:verificarne il funzionamento, come si può vedere nel video seguente:

Gli AutomiGli AutomiVerifica sommativaVerifica sommativa

1.1. Descrivere in modo formale (input, output, stati, funzione stati successivi, funzione Descrivere in modo formale (input, output, stati, funzione stati successivi, funzione uscite) l’automa seguente:uscite) l’automa seguente:un trasponder del tornello situato presso un impianto di risalita legge lo skipass dello un trasponder del tornello situato presso un impianto di risalita legge lo skipass dello sciatore, accende una luce verde e sblocca l’accesso se lo skipass è valido, accende sciatore, accende una luce verde e sblocca l’accesso se lo skipass è valido, accende una luce rossa e non sblocca l’accesso se lo skipass non è valido o non è riuscito a una luce rossa e non sblocca l’accesso se lo skipass non è valido o non è riuscito a completare la lettura.completare la lettura.

2.2. Descrivere tramite la matrice di transizione il funzionamento del seguente automa.Descrivere tramite la matrice di transizione il funzionamento del seguente automa.Che dispositivo fisico rappresenta?Che dispositivo fisico rappresenta?

Primo piano

Piano terra

Secondopiano

2/SU

1/SU

2/Fermo

T/Fermo

T/GIU’

T/GIU’

1/Fermo

1/GIU’

2/SU

Gli AutomiGli AutomiVerifica sommativa (continua)Verifica sommativa (continua)

3.3. Dare la definizione formale di automa.Dare la definizione formale di automa.4.4. Qual è la differenza tra funzione di transizione e funzione degli Qual è la differenza tra funzione di transizione e funzione degli

stati successivi? stati successivi? 5.5. Perché l’automa si definisce “a stati finiti”?Perché l’automa si definisce “a stati finiti”?6.6. In un grafo di transizione, ci può essere una situazione come In un grafo di transizione, ci può essere una situazione come

quella rappresentata in figura? Che effetti avrebbe?quella rappresentata in figura? Che effetti avrebbe?

SnSm

2/GIU’

2/SU

Sq