Vai alla Home Page About me Courseware Federica Living Library Federica Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica
 
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Gianmaria De Tommasi » 4.Automi deterministici temporizzati


Sommario della lezione

  • SED temporizzati;
  • Automi temporizzati deterministici;
  • Evoluzione temporale di un automa temporizzato deterministico.

Sistemi ad Eventi Discreti Temporizzati

Sequenze temporizzate

Quando si passa allo studio dei SED temporizzati il comportamento del sistema è caratterizzato dalle sequenze temporizzate di eventi

s = \bigl\{(e_1\,,\tau_1)\,,(e_2\,,\tau_2)\,,\ldots\,,(e_n\,,\tau_n)\,,\ldots\bigr\}
con
e_i evento i-mo
\tau_i istante di occorrenza dell’evento i-mo

Sistemi ad Eventi Discreti Temporizzati (segue)

Struttura di temporizzazione

Per poter associare ad ogni evento l’istante temporale di occorrenza è necessario aggiungere al modello di automa logico una struttura di temporizzazione.

Sistemi ad Eventi Discreti Temporizzati (segue)

Ritardo di attivazione

Il ritardo di attivazione è l’intervallo di tempo che intercorre tra l’abilitazione di un evento e la sua occorrenza.

I ritardi di attivazione possono essere noti (modello temporizzato deterministico) oppure caratterizzati da una funzione di distribuzione di probabilità (modello temporizzato stocastico).

Sistemi ad Eventi Discreti Temporizzati (segue)

Tempo di attivazione e tempo residuo

Si consideri il generico istante di tempo \tau e il generico evento e. Se \tau_k e \tau_{k+1} sono rispettivamente gli istanti di abilitazione e occorrenza di e, si indica con

\varphi_e(\tau) il tempo di attivazione;
o_e(\tau) il tempo residuo (o clock);
\theta_e il ritardo di attivazione.


Sistemi ad Eventi Discreti Temporizzati (segue)

Struttura di temporizzazione deterministica

Dato un insieme di eventi E la struttura di temporizzazione deterministica associata ad E è l’insieme

\Theta=\bigl\{\Theta_e\ :\ e\in E\bigr\}

i cui elementi \Theta_e sono le sequenze:

\Theta_e=\bigl\{\theta_{e\,,1}\,,\theta_{e\,,2}\,,\ldots\bigr\}

con e\in E, \theta_{e\,,k}\in\mathbb{R}_+\cup\bigl\{0\bigr\}, k\in\mathbb{N}.

\theta_{e\,,k} è il k-mo ritardo di attivazione dell’evento e.

Sistemi ad Eventi Discreti Temporizzati (segue)

Contatore di attivazione

Dato un evento e, il contatore di attivazione \nu_e indica il numero di volte che l’evento e è stato attivato a partire dall’istante iniziale.

Se all’istante \tau' avviene la transizione tra gli stati x_k e x_{k+1}, allora

\mathrm{se}\ e\in\Gamma\bigl(x_{k+1}\bigr)\Rightarrow\nu'_e=\left\{\begin{array}{ll}\nu_e+1 & \mathrm{se}\ e\ \mathrm{e'\ occorso\ oppure\ se}\ e\notin\Gamma\bigl(x_k\bigr)\\ \nu_e&\mathrm{altrimenti}\end{array}\right.

I valori iniziali \nu_e sono:
\nu_e=1 se e\in\Gamma\bigl(x_0\bigr)
\nu_e=0 altrimenti

Automi temporizzati deterministici

Definizione di Automa Temporizzato Deterministico

Un automa temporizzato (deterministico) è un 6-pla:

G_d=\Bigl(X\,,E\,,f\,,\Gamma\,,x_0\,,\Theta\Bigr)

Dove la 5-pla \Bigl(X\,,E\,,f\,,\Gamma\,,x_0\Bigr) è un automa logico e \Theta è un struttura di temporizzazione (deterministica).

Automi temporizzati deterministici (segue)

Osservazioni

Un automa temporizzato genera un sequenza di stati sulla base della sequenza di accadimento degli eventi seguendo l’equazione

x'=f\bigl(x\,,e'\bigr)

con x' stato prossimo e e'\in\Gamma\bigl(x\bigr)

La sequenza di eventi che occorrono è determinata sulla base dei valori correnti dei loro clock (tempi residui) secondo la relazione

e'=\arg\min_{e\in\Gamma\bigl(x\bigr)}\big\{o_e\big\}

dove o_e(\tau) rappresenta il valore corrente del clock associato all’evento e.

Automi temporizzati deterministici (segue)

Aggiornamento dei tempi residui (clock)

Se o'_e è il valore di o_e quando si raggiunge lo stato x' allora

\mathrm{se}\ e\in\Gamma\bigl(x'\bigr)\Rightarrow o'_e=\left\{\begin{array}{ll}o_e-o^\ast & \mathrm{se}\ e\neq e'\ \mathrm{e}\ e\in\Gamma\bigl(x\bigr)\\ \theta_{e\,,\nu_e+1}&\mathrm{altrimenti}\end{array}\right.

con o^\ast=\min_{e\in\Gamma\bigl(x\bigr)}\bigl\{o_e\bigr\}. o^\ast indica il tempo in cui è avvenuta la transizione da x a x'.

Le condizioni iniziali per i clock sono
o_e =\theta_{e\,,1} se e\in\Gamma\bigl(x_0\bigr)
o_e=\mathrm{indefinito} altrimenti

Evoluzione di un automa temporizzato

Evoluzione temporale di un automa temporizzato

Supponiamo che l’automa temporizzato G_d si trovi nello stato x all’istante \tau

  1. Individuare o^\ast mediante la relazione o^\ast=\min_{e\in\Gamma\bigl(x\bigr)}\bigl\{o_e\bigr\};
  2. Determinare il prossimo evento come evento associato a o^\ast, cio e'=\arg\min_{e\in\Gamma\bigl(x\bigr)}\bigl\{o_e\bigr\};
  3. Determinare il prossimo stato come x' =f\bigl(x\,,e'\bigr);
  4. Determinare il tempo di occorrenza di e' come \tau'=\tau+o^\ast;
  5. Calcolare i nuovi valori di o'_e e \nu'_e per tutti gli eventi;
  6. Ritornare al passo 1.

I materiali di supporto della lezione

Paragrafo 3.1 (fino a pagina 77) da Di Febbraro-Giua.

Esempi 3.4 e 3.5.

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion