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 ::
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:
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.
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.
Il problema dell'ordinamento può essere definito nel modo seguente:
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.
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:
La complessità può essere espressa mediante una relazione di ricorrenza che può essere risolta attraverso tre metodi:
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.
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.
Questo metodo viene utilizzato per risolvere equazioni ricorsive con la forma:
Il metodo dell'esperto dipende dal teorema dell'esperto.