PARTE SECONDA: Ordinamento in
Tempo Ottimale
-
12/10/04:
Algoritmo di fusione di due sequenze ordinate: algoritmo sub-ottimale
con complessità
ed algoritmo ottimale con complessità
.
Approfondimento: Algoritmo di ordinamento BUBBLE
SORT. Ingegnerizzazione dell'algoritmo, caso migliore
e caso peggiore.
Dispense: 19,
20,
21.
-
13/10/04:
-
Lower bound
per il problema dell'ordinamento tramite confronti: albero di decisione,
approssimazione di Stirling. Paradigma di programmazione divide et impera.
Introduzione del MERGE SORT.
Esemplificazione del suo funzionamento.
-
Dispense: 22,
23,
24,
25,
26,
27.
-
14/10/04:
-
Complessità computazionale del MERGE
SORT
e sua ottimalità.
-
Approfondimento: Innesto di INSERTION SORT
all'interno
di MERGE SORT. Complessità
computazionale ed ottimalità in funzione della lunghezza delle sottosequenze
ordinate tramite INSERTION SORT.
-
Dispense: 28,
29,
30,
31,
32,
33,
34.
-