Résumé de section

  • Lezione 33: 16/12/25

     
    • Introduzione al problema dell'ordinamento. Definizione di algoritmo basato su confronti. Design Pattern Divide and Conquer.
    • MergeSort: MergeSort (pseudocodice); Merge (pseudocodice); complessità di Merge; complessità di MergeSort.
    • QuickSort: strategia generale; QuickSortInPlace (pseudocodice).

    Lezione 34: 17/12/25

    • QuickSort: Partition (pseudocodice, correttezza, complessità); complessità di QuickSortInPlace tramite Albero della Ricorsione.
    • Randomized QuickSort: differenze rispetto a QuickSortInPlace.
    • Complessità probabilistica di Randomized QuickSort (alta probabilità e media).
    • InsertionSort: algoritmo in place; definizione di inversione; analisi in funzione della taglia dell'input e del numero di inversioni.

    Lezione 35: 18/12/25
     
    • Lower bound sulla complessità di un qualsiasi algoritmo di ordinamento basato su confronti (senza prova).
    • BucketSort: pseudocodice e analisi di complessità.
    • Nozione di ordinamento stabile.
    • RadixSort: algoritmo; analisi di complessità e di correttezza.
    • Caso di studio: ordinamento dei cittadini italiani per codice fiscale.

    Lezione 36: 23/12/25

    • Dimostrazione del lower bound sulla complessità di un qualsiasi algoritmo di ordinamento basato su confronti
    • Esercizi: ordinamento di n chiavi in [0,n^2-1] (Slide 86 e C-13.39 di [GTG14]); algoritmo CountIntersection per l' intersezione di 2 sequenze ordinate (primo esercizio di Slide 21); ordinamento di una sequenza di n bit (primo esercizio di Slide 43); calcolo del numero di inversioni tramite MergeSort (secondo esercizio di Slide 21)

    Materiale: