Richiami di classificazione dei sistemi, calcolo delle probabilità, teoria dei grafi, automi e linguaggi

Richiami sulla classificazione dei sistemi

Il sistema è l'oggetto, o un insieme di oggetti, di cui si vogliono analizzare proprietà e comportamenti

• $u_{c}$ ingressi di controllo
• $u_{d}$ ingressi di disturbo (non manipolabili)
• $y_{c}$ uscite controllate
• $y_{m}$ uscite misurate

Lo stato di un sistema ne sintetizza tutta la storia passata, nei sistemi fisici questo concetto è fortemente legato ai concetti di energia e memoria. Notazione: si indica con $x(t)$ lo stato del sistema al tempo $t$

Un sistema si dice statico se è caratterizzato da un legame istantaneo tra ingresso ed uscite, altrimenti si dice dinamico.

Sistema ad eventi discreti

Un sistema ad eventi discreti (SED) è un sistema dinamico la cui evoluzione temporale è asincrona: è basata sui tempi di occorrenza degli eventi, non su una temporizzazione regolare.

Definizione formale di un SED

• Insieme discreto $\xi$ degli eventi accadibili
• Spazio di stato discreto $\chi$
• Evoluzione dello stato di tipo "event driven": lo stato cambia nel tempo solo in dipendenza dell'occorrenza di eventi asincroni appartenenti all'insieme $\xi$

Esempi di sistemi ad eventi discreti:

• Processi produttivi,
• Reti di elaboratori elettronici,
• Reti di trasporto,
• Reti di comunicazione..

Esempi di eventi:

• Azioni specifiche, per esempio: pressione di un tasto sulla tastiera, arrivo di un cliente in coda, completamento di una lavorazione, trasmissione di un pacchetto dati ...
• Occorrenze spontanee, per esempio: guasti, interruzioni di servizio ...
• Soddisfacimento di una o più condizioni, per esempio: superamento di una soglia di allerta...

In un SED nulla cambia fino al prossimo evento, per questo si dice che la sua dinamica è determinata dagli eventi

Algoritmo per la determinazione di stati equivalenti

Sia $(\xi ,\chi ,f,x_{0},{\mathcal {F}})$ un automa a stati finiti con $({\mathcal {F}}\neq \chi )$

Passo 1

1.1 Marcare tutte le coppie $\{x,y\}:x\in {\mathcal {F}},y\notin {\mathcal {F}}$

1.2 Per ogni coppia $\{x,y\}$ non marcata, inizializzare a vuota la corrispondente lista ${\mathcal {P}}(\{x,y\})$

Passo 2 Per tutte le coppie $\{x,y\}$ non marcate al passo 1

2.1 Se la coppia $\{f(x,e),f(y,e)\}$ è marcata per qualche $e\in {\mathcal {E}}$

2.1.1 Marcare la coppia $\{x,y\}$

2.1.2 Marcare tutte le coppie $\{x',y'\}\in {\mathcal {P}}(\{x,y\})$ e ripetere a ritroso per tutte le coppie $\{x'y'\}$

Passo 2.2 (se le coppie ${f(x,e),f(y,e)}$ non sono marcate per alcun $e\in \xi$)

2.2.1 per ogni $e\in \xi$ se $f(x,e)\neq f(y,e)$, aggiungere ${x,y}$ alla lista ${\mathcal {P}}({f(x,e),f(y,e)})$