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

lezione
lezione
Richiami di classificazione dei sistemi, calcolo delle probabilità, teoria dei grafi, automi e linguaggi
Tipo di risorsa Tipo: lezione
Materia di appartenenza Materia: Sistemi a eventi discreti
Avanzamento Avanzamento: lezione completa al 25%

Richiami sulla classificazione dei sistemi modifica

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

  •   ingressi di controllo
  •   ingressi di disturbo (non manipolabili)
  •   uscite controllate
  •   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   lo stato del sistema al tempo  

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

Sistema ad eventi discreti modifica

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   degli eventi accadibili
  • Spazio di stato discreto  
  • Evoluzione dello stato di tipo "event driven": lo stato cambia nel tempo solo in dipendenza dell'occorrenza di eventi asincroni appartenenti all'insieme  

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 modifica

Sia   un automa a stati finiti con  

Passo 1

1.1 Marcare tutte le coppie  

1.2 Per ogni coppia   non marcata, inizializzare a vuota la corrispondente lista  

Passo 2 Per tutte le coppie   non marcate al passo 1

2.1 Se la coppia   è marcata per qualche  

2.1.1 Marcare la coppia  

2.1.2 Marcare tutte le coppie   e ripetere a ritroso per tutte le coppie  

Passo 2.2 (se le coppie   non sono marcate per alcun  )

2.2.1 per ogni   se  , aggiungere   alla lista