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 » 1.Introduzione ai sistemi ad eventi discreti


Sommario della lezione

Introduzione ai sistemi ad eventi discreti

  • Concetti di Sistema e Modello
  • Concetto di Stato: i sistemi dinamici
  • Sistemi ad eventi discreti (SED)
  • Livelli di astrazione nello studio dei SED

Motivazione

Negli ultimi 20/30 anni, a causa del forte sviluppo tecnologico, si è evidenziata la necessità di studiare i sistemi complessi realizzati (spesso realizzati dall’uomo) con tecniche diverse rispetto a quelle classiche della Teoria dei Sistemi.

Questi sistemi complessi sono sistemi dinamici i cui stati possono assumere valori logici o simbolici e non necessariamente numerici, come per i sistemi a stato vettore.

L’evoluzione dello stato tipicamente avviene a seguito dell’occorrenza di eventi.

Le leggi che regolano l’evoluzione dinamica non è esprimibile in termini numerici in modo semplice.

Sistemi ad eventi discreti (SED)

Lo studio dei sistemi ad eventi discreti (SED) riguarda lo studio di Sistemi Dinamici, la cui evoluzione dipende dall’occorrenza di Eventi, Considerati Instantanei e Asincroni e il cui spazio di stato è Discreto (non necessariamente di dimensione finita)

Sistemi e modelli

Nell’ambito delle discipline ingegneristiche è di fondamentale importanza poter avere una descrizione Quantitativa del comportamento di un Sistema.

Tale descrizione formale prende il nome di Modello ed è necessaria per poter sviluppare tecniche di analisi e sintesi  (Progetto).

Nel linguaggio comune si utilizzano indifferentemente i due vocaboli Sistema e Modello.

Ingressi e uscite di un sistema

  • u sono le grandezze indipendenti la cui evoluzione non dipende da S.
  • y sono le grandezze il cui comportamento dipende da u e da S.
Sistema.

Sistema.


Stato di un sistema dinamico

L’uscita y ad un istante di tempo t può dipendere

  • solo dall’ingresso u nello stesso istante (sistemi Statici o Algebrici)
  • dall’ingresso u nello stesso istante e dalla storia pregressa del sistema (sistemi Dinamici)

Per poter portare in conto la “storia” del sistema nei sistemi dinamici si introduce la Variabile di Stato. Ad esempio per i sistemi a stato vettore a tempo-continuo si ha:

\dot{x}(t) = f(x(t),u(t),t)\,,\quad x(t_0)=x_0

Definizione formale di SED

Un SED è un sistema Dinamico il cui comportamento è caratterizzato dall’accadimento ASINCRONO di EVENTI, i quali individuano lo svolgimento di attività di durata non necessariamente nota.

Formalmente un SED è caratterizzato da:

  • l’insieme E dei possibili eventi
  • lo spazio di stato discreto X
  • evoluzione guidata dagli eventi (event-driven):

x_{k+1} = \delta\bigl(x_k\,,e_k\bigr)\,,\quad k\in\mathbb{N}

con:

x_{k+1} – stato raggiunto dopo l’accadimento del k-mo evento
e_kk-mo evento accaduto a partire dall’istante iniziale considerato
\delta:X\times E\mapsto X – funzione transizione di stato

Esempio – Sistemi “a coda”

Gli elementi base di un sistema a coda sono:
i Clienti, vale a dire le entità che attendono per utilizzare delle Risorse.
le Risorse per le quali ci si mette in coda. Una risorsa è capace di fornire un Servizio pertanto vengono anche detta Servente.
la Coda, vale a dire lo “spazio” di attesa.

Sistema “a coda”.

Sistema “a coda”.


Sistemi “a coda”

Visto come un SED, un sistema “a coda” è definito dagli eventi E = \bigl\{a\,,p\bigr\} con:

  • a arrivo di un cliente
  • p partenza di un cliente

e lo stato corrisponde alla lunghezza della coda.

Esempio – Database Mangement System

Un Database Management System (DBMS) deve garantire la consistenza dei dati a seguito di operazioni concorrenti su una base di dati.

Una Transazione è una sequenza di operazione di lettura e/o scrittura su record di database, richiesta da un singolo utente.

Un DBMS, quindi, ha il compito di schedulare le transazioni, che per forza di cose sono sequenziali.

DBMS

Notazione:

  • r_1(a) – lettura dati dal record a da parte della transazione 1.
  • w_2(b) – scrittura dati sul record b da parte della transazione 2.

Transazione 1r_1(a)r_2(b) (per calcolare la somma in a e b)
Transazione 2r_2(a)w_2(a)r_2(b)w_2(b) (per trasferire 100 € da a a b)
Schedule ammissibiler_2(a)w_2(a)r_1(a)r_2(b)w_2(b)r_1(b)
Schedule non ammissibiler_2(a)w_2(a)r_1(a)r_1(b)r_2(b)w_2(b)
Sequenza “bloccante”r_1(a)r_2(a)w_2(a)r_2(b)w_2(b), questa sequenza non può essere completata restituendo un risultato corretto per la Transazione 1.

Livelli di astrazione nello studio dei SED

È possibile considerare tre tipi di sequenze di eventi:

  • sequenza Logiche, in cui non viene specificato l’istante di occorrenza degli eventi
  • sequenze Temporizzate deterministiche, in cui viene specificato l’istante di occorrenza degli eventi
  • sequenze Temporizzate stocastiche, in cui gli istanti di occorrenza degli eventi sono caratterizzati in termini statistici attraverso funzioni di distribuzione di probabilità

Strumenti per la modellistica dei SED

Modelli Logici

  • Automi
  • Reti di Petri

Modelli Temporizzati

  • Automi temporizzati (deterministici e stocastici)
  • Reti di Petri temporizzate (deterministiche e stocastiche)
  • Algebra (max,+)
  • Catene di Markov

I materiali di supporto della lezione

Capitolo 1 da Di Febbraro-Giua

Capitolo 1 da Cassandras-Lafortune

  • 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