Introduzione allo studio dell'informatica teorica: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
Aggiunta una sezione sul concetto di computazione |
|||
Riga 72:
La teoria della complessità cerca di dare una risposta a questi interrogativi, sviluppando strumenti utili per l'analisi degli algoritmi e per sviluppare previsioni ragionate sulle loro prestazioni in genere.
Per formarsi un'idea di cosa siano gli automi a stati finiti è quindi importante definire il concetto di computazione, che secondo alcuni autori si può far risalire ad un ''comportamento'', intendendo con questo una successione finita o infinita di passi.
==Il concetto di computazione==
Descrivere una computazione implica la capacità di rappresentare la successione dei passi che la caratterizza, ognuno dei quali viene spesso interpretato come un'''azione'', come uno ''stato'', oppure come una ''transizione'', intesa come una coppia <math>(stato, azione)</math>.
In base alla modalità scelta si potranno quindi avere tre possibili descrizioni per la computazione:
* se si descrive il passo come un'azione, la computazione sarà una successione di azioni;
* se si descrive il passo come uno stato la computazione sarà una successione di stati;
* se si descrive il passo come una transizione la computazione sarà una successione di coppie <math>( stato, azione )</math>.
Nelle sezioni seguenti verranno riportati tre esempi con lo scopo di illustrare le tecniche appena introdotte.
===Computazione come successione di azioni===
Supponiamo di voler calcolare l'area di un rettangolo conoscendo il suo perimetro e la lunghezza di uno dei lati.
Indichiamo con <math>a_n</math> la successione che descrive la sequenza di azioni necessaria per attuare la computazione desiderata.
Potremo scrivere:
# <math>a_1</math>: dimezzare (il perimetro);
# <math>a_2</math>: sottrarre (la lunghezza del lato al semiperimetro);
# <math>a_3</math>: moltiplicare (i due lati).
Le azioni sono rappresentate solo dai verbi: le informazioni tra parentesi sono date unicamente per migliorare la comprensibilità della procedura.
La necessità di questo accorgimento mostra un importante limite di questa tecnica di rappresentazione: è poco comunicativa.
===Computazione come successione di stati===
Supponiamo di voler rappresentare la computazione precedente impiegando una successione di stati anziché di azioni.
Indichiamo con <math>q_n</math> la successione che descrive la sequenza di stati necessaria per attuare la computazione desiderata.
Potremo scrivere:
# <math>q_1</math>: perimetro
# <math>q_2</math>: semiperimetro
# <math>q_3</math>: lunghezza del lato mancante
# <math>q_4</math>: area
Come si può notare questa descrizione riesce a rendere l'idea senza che sia necessario includere informazioni aggiuntive a dimostrazione del fatto che è più espressiva rispetto alla precedente.
===Computazione come successione di transizioni===
Anche in questa sezione rappresenteremo la stessa computazione esaminata negli altri due casi, ma impiegando la logica delle transizioni.
Indicando con <math>t_n</math> la successione che indica la sequenza di transizioni necessarie per attuare la computazione desiderata potremo scrivere:
# <math>t_1</math>: semiperimetro = (perimetro, dimezzare)
# <math>t_2</math>: lunghezza del lato mancante = (semiperimetro, sottrarre)
# <math>t_3</math>: area = (lunghezza del lato mancante, moltiplicare)
Come si può notare confrontando le tre situazioni, questa tecnica di rappresentazione è indubbiamente la più espressiva e sarà quella impiegata durante il corso.
=Bibliografia=
| |||