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.

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.

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.

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 conta le celle necessarie per scrivere l'input. In alcuni casi si

possono adoperare misure differenti:

• Il numero di bit necessari alla codifica dell'istanza;

• Il numero di elementi presenti nella struttura dati;

• La lunghezza di una sequenza;

• ...