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

Bruno Fadini » 19.Minimizzazione delle macchine sequenziali. Teoria - Modulo 4


Reti logiche

Minimizzazione delle macchine sequenziali. Teoria.

Argomenti

  • Macchine complete ed incomplete
  • Equivalenza
  • Compatibilità ed inclusione
  • Minimizzazione degli stati
  • Algoritmi di minimizzazione

Macchine complete e incomplete

Applicabilità di una sequenza

  • Una sequenza di ingressi J è applicabile a M in q – si dice a M(q) – se è definita u=λ(q, J), la funzione che fornisce l’uscita u che si ottiene applicando alla macchina la sequenza di ingressi J a partire da uno “stato iniziale” q.
  • Se la funzione di uscita λ è definita ovunque, la macchina si dice completa, incompleta altrimenti
  • Per le macchine incomplete esistono sequenze non applicabili

Equivalenza

Stati equivalenti (macchine complete)

  • Due stati (della stessa macchina o di macchine diverse) sono equivalenti se producono la stessa sequenza di uscite per qualsiasi sequenza di ingressi
  • Definizione ricorsiva
    • Due stati sono equivalenti se, per ciascun ingresso sono eguali le uscite e sono equivalenti gli stati successivi

Macchine equivalenti (complete)

Due macchine complete M e M’ sono equivalenti se per ciascuno stato q di M esiste almeno uno stato q’ di M’ ad esso equivalente e viceversa

Macchine equivalenti (incomplete)

  • Non tutte le sequenze di ingresso sono applicabili
  • Il concetto è sostituito da quelli di Compatibilità tra stati ed inclusione tra macchine

Compatibilità ed inclusione

Compatibilità fra stati

  • Due stati sono compatibili se per ogni sequenza di ingressi applicabile ad entrambi, le uscite prodotte sono identiche.
  • La compatibilità NON è una relazione di equivalenza
    • Non gode della proprietà transitiva; p.e.: q1~q2, q2~q3, l(q1,J)=a, , l(q2,J)=-, l(q3,J)=b

Definizione ricorsiva

  • Due stati sono compatibili se sono eguali le uscite per ciascun ingresso applicabile e compatibili gli stati successivi (se definiti)
  • Per le macchine complete la compatibilità è l’equivalenza

Compatibilità ed inclusione

Inclusione fra macchine

  • Concettualmente: una macchina include un’altra se “fa qualcosa in più”
  • Formalmente:
    • M’(q’) include M(q): M’(q’) ⊇ M(q) ⇔ ∀(J applicabile a M(q)) : λ(q’,J)=λ(q,J)
    • M’ include M: M’⊇ M ∀(q∈M) ∃ (q’∈M’) : M’(q’) ⊇ M(q)

Minimizzazione degli stati

Minimizzazione e classi di equivalenza

  • Data una macchina M se ne vuole trovare una equivqlente, M’, con un numero minimo di stati.
  • La famiglia delle classi di equivalenza degli stati di M è la soluzione: M’ ha uno stato per ogni elemento C della famiglia con:
    • uscita: pari alla uscita degli elementi di C, tutti eguali per essere questi equivalenti fra loro,
    • stato seguente: quello determinato da C stesso; essendo infatti gli stati di Ci equivalenti fra loro, devono avere tutti per seguenti stati equivalenti e quindi appartenere ad un unico elemento C’ della famiglia delle classi di equivalenza.
    • M’ ha un numero di stati minimo, per le proprietà delle classi di equivalenza.

Minimizzazione degli stati

Minimizzazione e classi di compatibilità massime

  • Per le macchine incomplete, proprietà analoghe a quelle delle classi di equivalenza, ma più complesse, hanno le classi di compatibilità massime – vedi approfondimenti
  • Si procede analogamente, con le seguenti peculiarità:
    • M’ include M (non è equivalente)
    • La soluzione potrebbe non essere minima, ma in generale presenta una macchina a “stati ridotti”
    • Si possono avere più soluzioni, potendo uno “stato seguente” essere incluso in più elementi distinti della famiglia di compatibilità massima

Minimizzazione degli stati

Classi di equivalenza e di compatibilità

  • Ne segue che per minimizzare occorre ricercare le classi di equivalenza (macchine complete) o gli insiemi di compatibilità massima (macchine incomplete)
  • Diversi metodi
    • Algoritmo del partizionamento (o suddivisione degli elementi per macchine incomplete)
    • Row merging (macchine complete)
    • Paull-Unger (preferibile per macchine complete)

Algoritmi di minimizzazione

Il partizionamento degli stati

Si potrebbe procedere così:

  • Si ritiene in partenza che l’insieme di stati Q costituisca una famiglia F={Q} di stati “presumibilmente equivalente”.
  • Si individuano in Q le disequivalenze e Q si partiziona in più sottoinsiemi, Q1,Q2,… disgiunti (Qi∩Qj = ∅);
  • Si assume quindi F={Q1,Q2,…}, proseguendo iterativamente sui sottoinsiemi, finché non esistono più disequivalenze.
  • Per la ricerca delle disequivalenze si opera come segue:
    1. Si cercano disequivalenze a causa delle uscite,
    2. Iterativamente, sii cercano disequivalenze a causa deglii stati seguenti, calcolando per ogni elemento di F l’insieme degli stati seguenti e verificando se questo è incluso nella famiglia F

Algoritmi di minimizzazione

La famiglia presumibilmente compatibile

Per le reti incomplete si procede come in precedenza, adattando l’algoritmo alle peculiarità della incompatibilità:

  • F={Q} è la famiglia di “presunta massima compatibilità”.
  • Invece di un partizionamento di Q, accertato che q1~q2, si pone Q1=Q-q1, Q2=Q-q2 e quindi Q1∩Q2 ≠ ∅).

Algoritmi di minimizzazione

Il row merging (solo per reti complete)

  • Due righe della tabella di stato, se si riconoscono equivalenti, possono essere “fuse”:
    • Una delle due scompare
    • Il riferimento nelle righe rimaste alla riga scomparsa è sostituito da un riferimento alla riga equivalente rimasta

Algoritmi di minimizzazione

Metodo di Paull-Unger (preferito per reti complete)

  • Organizza il procedimento in una matrice diagonale, dove gli elementi sono le coppie di stati e contengono:
    1. Il simbolo di non equivalenza (X) se la coppia è caratterizzata da usite diverse per almeno uno degli ingressi
    2. Le coppie di stati condizionanti l’equivalenza se non è possible segnarle immediatamente come X oppure ~
  • Per le caselle di tipo 2 si procede poi iterativamente, segnando con X le caselle contenenti coppie già riconosciute disequivalenti.

Al termine, le caselle senza X sono di coppie equivalenti: a queste poi si deducono le classi di equivalenza.

Prossima lezione

Minimizzazione delle macchine sequenziali. Esempi ed esercizi

I materiali di supporto della lezione

B. Fadini, A. Esposito, Teoria e Progetto delle Reti Logiche, Napoli Liguori Ed., II ed, 1994. Cap. VI

U. De Carlini, B. Fadini, Macchine per l'elaborazione delle informazioni, Napoli Liguori Ed., II ed., 1995 (Capitoli III e VII)

  • 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