9 Algoritmi

Introduzione all'analisi degli algoritmi

Un problema computazionale è definito dalle sue specifiche, che sono sostanzialmente la relazione tra possibili ingressi e uscite.

Una soluzione è costituita da un algoritmo. Un algoritmo è corretto quando "rispetta" la specifica del problema.

Correttezza degli algoritmi

Un algoritmo A si dice parzialmente corretto rispetto alla specifica S quando, per ogni ingresso che rispetta le pre-condizioni, se l’algoritmo termina, allora il risultato rispetta le post-condizioni.

Un algoritmo A si dice totalmente corretto rispetto alla specifica data se, per ogni ingresso che rispetta le pre-condizioni di S, l’algoritmo termina e l’uscita rispetta le post-condizioni.

La correttezza degli algoritmi è importante ma non ne assicura l'efficienza. Per valutare quanto sia efficace un algoritmo si possono seguire due strade:

• La valutazione a posteriori delle prestazioni attraverso la misura delle risorse effettivamente adoperate dell'algoritmo;
• L'analisi a priori dell'algoritmo stesso con strumenti analitici per prevederne le necessità in termini di risorse.

Prestazioni degli algoritmi

Con il termine prestazione (di un algoritmo) ci riferiamo ad una misura dell'efficienza del codice che lo implementa. Nella valutazione delle prestazioni si possono misurare il tempo effettivo di esecuzione del codice e la quantità di memoria adoperata durante l'esecuzione.

Per valutare le prestazioni, se non siamo in grado di controllare tutti i fattori che influenzano le prestazioni, possiamo riferirci ad un modello ed effettuare le nostre misure con strumenti matematici:

• Il modello è la macchina astratta;
• Gli strumenti di misura sono di seguito.

Efficienza e complessità

Una volta completata la soluzione corretta, bisogna quindi porsi il problema della sua efficienza nell'uso delle due risorse fondamentali: tempo e spazio. La complessità in tempo o spazio è una stima matematica del tempo o dello spazio necessario all'algoritmo per calcolare la risposta.

La complessità di un algoritmo si esprime per mezzo di una funzione matematica che dipende dalle dimensioni dell'input.

• La dimensione di una specifica istanza è la misura dello spazio necessario per definirla;
• La funzione che misura la complessità in tempo calcola il numero di passi elementari necessari per definire l'algoritmo;
• Analogamente, la funzione che misura la complessità in spazio fornisce una stima della quantità di memoria necessaria per eseguire il calcolo.

La dimensione di un'istanza misura essenzialmente lo spazio necessario per rappresentare l'input ed è rappresentata da un numero intero positivo che co...