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

Da Wikiversità, l'apprendimento libero.
Jump to navigation Jump to search
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