Uni.A-ConcettiIniziali History
Hide minor edits - Show changes to output
Changed line 28 from:
!!Misure di calcolo della complessità to:
!!!Misure di calcolo della complessità Changed line 42 from:
!!Progettare gli algoritmi to:
!!!Progettare gli algoritmi Changed lines 45-46 from:
->'''Output''': una permutazione (riordinamento) <a'_1_'', a'_2_'', ... , a'_n_''> della sequenza di input tale che a'_1_''<= a'_2_''<= ... <= a'_n_''. to:
->'''Output''': una permutazione (riordinamento) <a'_1_'', a'_2_'', ... , a'_n_''> della sequenza di input tale che \\
a'_1_''<= a'_2_''<= ... <= a'_n_''. Changed line 50 from:
!!Metodo DIVIDE ET IMPERA to:
!!!Metodo DIVIDE ET IMPERA Changed line 58 from:
to:
Changed line 64 from:
!!!!Metodo di sostituzione to:
!!!!!Metodo di sostituzione Changed line 68 from:
!!!!Metodo dell'albero di ricorsione to:
!!!!!Metodo dell'albero di ricorsione Changed line 72 from:
to:
Added lines 1-77:
(:title Algoritmi e strutture dati - Concetti iniziali:)
[[Torna alla pagina di Algoritmi e strutture dati->Uni.Algoritmi]]
----
>>evvai<<
Questa pagina è stata aggiornata GRAZIE agli appunti che AVETE INVIATO nel periodo di chiusura della sezione UniCrema!! '''''È SERVITA A QUALCOSA, NO?!''''' [++;)++]
>><<
%titolo%''':: 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 T'_A_'(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 S'_A_'(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->A-AlgOrdinamento]]. 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->Uni.Algoritmi]]
|
