Torna alla pagina di Algoritmi e strutture dati
Questa pagina è stata aggiornata GRAZIE agli appunti che AVETE INVIATO nel periodo di chiusura della sezione UniCrema!! È SERVITA A QUALCOSA, NO?! ;)
:: Algoritmi e strutture dati - Concetti iniziali ::
Algoritmi
Un algoritmo è procedimento di calcolo che prende come input un insieme di valori e genera un valore o un insieme di valori, come output.
Può essere considerato anche come uno strumento per risolvere un problema computazionale ben definito.
La sequenza di input è detta istanza del problema dell'ordinamento.
Si parla di sintesi per indicare la creazione di un algoritmo per risolvere un problema.
Un algoritmo si dice corretto se, per ogni istanza di input, termina con l'output corretto.
L' analisi di un algoritmo consiste nel verificare se l'algoritmo risolve il problema per cui è stato disegnato e considera quindi la correttezza e la complessità (tempo e spazio) dell'algoritmo stesso.
La complessità indica la quantità di risorse consumate per eseguire un algoritmo:
- tempo computazionale (valutare il numero di operazioni che l'algoritmo esegue);
- spazio occupato;
- dispositivi hardware utilizzati.
Un consumo eccessivo di queste risorse pregiudica l'effettivo utilizzo dell'algoritmo stesso.
La classificazione consiste nel classificare gli algoritmi in base alla quantità di risorse che utilizzano per risolvere il problema.
Misure di calcolo della complessità
Il numero di operazioni elementari eseguite dall'algoritmo A sull'istanza x indica il tempo di calcolo TA(x). Esso per esempio, dipende dal numero di elementi che voglio ordinare.
Il numero di celle di memoria utilizzate dall'algoritmo su x viene detto spazio di memoria SA(x).
Si considera il tempo di esecuzione di un algoritmo nel caso peggiore o nel caso medio.
Il caso peggiore costituisce un limite superiore al tempo di esecuzione per qualsiasi input.
Conoscendo questo tempo, abbiamo la garanzia che l’algoritmo non potrà impiegare di più.
La complessità nel caso peggiore fornisce spesso una valutazione troppo pessimistica.
Il caso medio prende in considerazione i tempi di calcolo di tutte le istanze per poi calcolarne la media.
Spesso però questo caso è “brutto” quanto quello peggiore.
La complessità del caso medio assume una distribuzione uniforme sulle istanze.
Progettare gli algoritmi
Il problema dell'ordinamento può essere definito nel modo seguente:
Input: una sequenza di n numeri <a
1 , a
2 , ... , a
n>.
Output: una permutazione (riordinamento) <a
1', a
2', ... , a
n'> della sequenza di input tale che
a
1'<= a
2'<= ... <= a
n'.
Di algoritmi di ordinamento ce ne sono diversi, e saranno trattati in un'altra pagina di appunti. La scelta dell'algoritmo più appropriato dipende dal numero di elementi da ordinare, dal livello di ordinamento iniziale degli elementi, da eventuali vincoli sui valori degli elementi e dal tipo di unità di memorizzazione da usare.
Metodo DIVIDE ET IMPERA
Gli algoritmi che utilizzano questo metodo sono algoritmi ricorsivi. In particolare con questa tecnica suddividono il problema in vari sottoproblemi, che sono simili al problema originale, ma di dimensioni piccole, risolvono i sottoproblemi in modo ricorsivo e, poi, combinano le soluzioni per creare una soluzione del problema originale.
Questo metodo prevede tre passi:
- Divide: il problema viene diviso in un certo numero di sottoproblemi.
- Impera: i sottoproblemi vengono risolti in modo ricorsivo.
- Combina: le soluzioni dei sottoproblemi vengono combinate per generare la soluzione del problema originale.
Ricorrenze
La complessità può essere espressa mediante una relazione di ricorrenza che può essere risolta attraverso tre metodi:
- sostituzione;
- albero di ricorsione;
- metodo dell'esperto.
Metodo di sostituzione
Il metodo di sostituzione prima di tutto ipotizza un limite asintotico e successivamente verifica l'ipotesi fatta con una dimostrazione per induzione matematica.
Può essere usato per determinare il limite superiore e inferiore di una ricorrenza.
Metodo dell'albero di ricorsione
Questo metodo consiste nel costruire un albero di ricorsione i cui nodi rappresentano il costo di un singolo sottoproblema. Sommiamo i costi all’interno di ogni livello dell’albero per ottenere un insieme di costi per livello; poi sommiamo tutti i costi per livello per determinare il costo totale di tutti i livelli della ricorsione. Gli alberi di ricorsione sono particolarmente utili quando la ricorrenza descrive il tempo di esecuzione di un algoritmo divide et impera.
Questo metodo è un ottimo modo per formulare una ipotesi che poi sarà verificata con il metodo di sostituzione.
Metodo dell'esperto
Questo metodo viene utilizzato per risolvere equazioni ricorsive con la forma:
T(n) = aT(n/b) + f(n)
Il metodo dell'esperto dipende dal teorema dell'esperto.
Torna alla pagina di Algoritmi e strutture dati
