PARTE SECONDA: Ordinamento in Tempo Ottimale

8/10/03: (3 ore)

Approfondimento: Algoritmo di fusione di due sequenze ordinate: algoritmo ottimale con complessità $\Omega(n \log n)$.

Lower bound $\Omega(n \log n)$ 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: 19, 23, 23, 24, 25, 26, 27.

 

14/10/03: (3 ore)

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.