Introduzione allo studio dell'informatica teorica: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
Riga 196:
=Il concetto di transizione=
Abbiamo visto che la tecnica che prevede di descrivere la computazione impiegando coppie ordinate <math>(\text{stato, azione})</math> è particolarmente espressiva e permette di risalire a gran parte delle informazioni coinvolte nella computazione stessa.
Nonostante ciò la descrizione è ancora incompleta in quanto in ogni passo della procedura si conoscono lo stato attuale e l'azione, ma non si conosce lo ''stato prossimo'', ossia lo stato in cui ci si troverà dopo aver svolto l'azione.
Per ovviare a questo inconveniente si possono impiegare due strategie: concepire lo stato prossimo come un'entità calcolata a partire dallo stato attuale e da un'azione oppure descrivere ogni passo come una tripla ordinata di elementi, in cui il primo è lo stato attuale, il secondo è l'azione ed il terzo è lo stato prossimo.
L'insieme dello stato attuale, dell'azione e dello stato prossimo prende il nome di ''transizione'' e va pensata come la trasformazione subita dalla computazione per opera di un'azione.
Vediamo come si rappresentano le transizioni impiegando entrambe le strategie, basandosi sull'esempio del calcolo dell'area del rettangolo esaminato poc'anzi.
==La transizione come funzione==
È possibile immaginare che esista una funzione che permette di calcolare lo stato prossimo della computazione conoscendo lo stato attuale e l'azione da svolgere.
Indicando con la lettera <math>f</math> una tale funzione e con <math>t_n</math> la successione delle transizioni, la computazione riguardante il calcolo dell'area del rettangolo diventerebbe:
# <math>t_1</math> = semiperimetro = f(perimetro, dimezzare);
# <math>t_2</math> = lunghezza lato mancante = f(semiperimetro, sottrarre);
# <math>t_3</math> = area = f(lunghezza lato mancante, moltiplicare).
Grazie a questa tecnica di rappresentazione delle transizioni è possibile sintetizzare l'intera computazione in un passaggio solo:
<math>area = f( \underbrace{f( \overbrace{f(perimetro, dimezzare)}^{semiperimetro}, sottrarre)}_{lato}, moltiplicare)</math>
Come si può notare, nella rappresentazione sintetica della computazione appena esposta compaiono solamente lo stato iniziale e la sequenza delle azioni da svolgere.
Si può anche notare come la discussione sia stata, per ora, fortemente informale: abbiamo introdotto una funzione matematica senza parlare né del suo insieme di partenza, né tantomeno dell'insieme di arrivo. L'intento in questo paragrafo é la presentazione intuitiva della tecnica impiegata per la rappresentazione delle transizioni, lasciando ad un momento successivo una sistemazione più rigorosa dei dettagli.
==La transizione come tripla ordinata==
Adottando questa strategia per la rappresentazione delle transizioni ed indicando con <math>t_n</math> la successione delle transizioni, è possibile descrivere la computazione come segue:
# <math>t_1</math> = (perimetro, dimezzare, semiperimetro);
# <math>t_2</math> = (semiperimetro, sottrarre, lato mancante);
# <math>t_3</math> = (lato mancante, moltiplicare, area).
La tecnica precedente ha l'innegabile vantaggio di essere più facile da applicare a livello di calcolo; la tecnica attuale, tuttavia, ha il pregio di essere molto descrittiva e sarà usata, nella prossima lezione, per introdurre una modalità di rappresentazione per gli automi a stati finiti.
=Bibliografia=
| |||