Introduzione agli Algoritmi a.a. 2008-2009
(canale P-Z)

Giovedì 26 febbraio 2009     Informazioni generali sul corso. Brevissima panoramica degli argomenti del corso. Gli obbiettivi della disciplina che si occupa degli algoritmi. Analisi dell'efficienza degli algoritmi: discussione delle problematiche relative alla valutazione dell'efficienza. Analisi del tempo di esecuzione di semplici algoritmi (somma dei valori di un vettore e ricerca di un valore in un vettore): indipendenza dalle caratteristiche della macchina. Tempo di calcolo in funzione della dimensione dell'input. Analisi nei casi migliore, peggiore e medio.

Martedì 3 marzo 2009     Esempio di due algoritmi per lo stesso problema e confronto diretto delle rispettive valutazioni asintotiche di complessità temporale. Ordini asintotici O(f(n)), Ω(f(n)) e Θ(f(n)). Proprietà e esempi.

Esercizio 1     n√n ∈ O(n)?    n√n ∈ O(n²)?    2ⁿ ∈ Ω(n¹⁰⁰⁰)?    2ⁿ ∈ O(3^n/2)?    2ⁿ ∈ Θ(2^{n + log n})?

Giovedì 5 marzo 2009     Discussione esercizio 1. Ordine asintotico di un polinomio. Confronto tra polinomi ed esponenziali. Analisi asintotica della complessità di algoritmi ricorsivi: fattoriale e numeri di fibonacci. Equazioni di ricorrenza. Risoluzione tramite iterazione.

Esercizio 2     Analizzare la complessità asintotica del seguente programma che implementa una versione ricorsiva del selection-sort:

    int Ssort(int A[], int n) {
        if (n >= 2) {
            int i, imin = 0;
            for (i = 1 ; i < n ; i++)
                if (A[i] < A[imin]) imin = i;
            SWAP(A[0], A[imin])
            Ssort(A + 1, n - 1);
        }
    }

Martedì 10 marzo 2009     Esercitazione: discussione esercizio 2, analisi bubble-sort ricorsivo ed esercizi di analisi asintotica.

Giovedì 12 marzo 2009     Come semplificare una equazione di ricorrenza con due o più termini per ottenere delimitazioni inferiori e superiori alla crescita asintotica della soluzione. Analisi della ricerca binaria (ricorsiva).

Esercizio 3     Analizzare la complessità asintotica del seguente programma che implementa una variante ricorsiva del insertion-sort:

    int sort2(int A[], int n) {
        if (n >= 2) {
            sort2(A, n - 2);
            if (A[n-1] < A[n-2]) SWAP(A[n-1], A[n-2])
            int k1 = A[n-1], k2 = A[n-2];
            int i = n - 3;
            while (i >= 0 && k1 < A[i]) {
                A[i+2] = A[i];
                i--;
            }
            A[i+2] = k1;
            while (i >= 0 && k2 < A[i]) {
                A[i+1] = A[i];
                i--;
            }
            A[i+1] = k2;
        }
    }

Martedì 17 marzo 2009     Discussione esercizio 3. Algoritmo di ordinamento merge-sort: descrizione e analisi della complessità.

Giovedì 19 marzo 2009     Algoritmo di ordinamento quick-sort: descrizione, analisi della complessità nei casi migliore e peggiore, cenni sulla complessità nel caso medio. Albero di ricorsione: merge-sort e quick-sort con partizioni sbilanciate.

Esercizio 4     Definire un algoritmo di ordinamento che è una versione ternaria del merge-sort: il vettore è partizionato in tre parti (uguali o quasi uguali) e poi le tre parti sono ordinate tramite una versione ternaria dell'algoritmo di merge. Analizzare la complessità dell'algoritmo.

Martedì 24 marzo 2009     Sospensione della didattica: seminario del Prof. Madhu Sudan.

Giovedì 26 marzo 2009     Esercitazione: discussione esercizio 4, mergesort k-ario, ricerca binaria (problemi 2.9 e 2.10).

Martedì 31 marzo 2009     Teorema fondamentale delle ricorrenze (solo enunciato). Delimitazione inferiore sul numero di confronti per algoritmi di ordinamento basati su confronti: albero delle decisioni. Counting-sort: descrizione ed analisi. Code con priorità: analisi di implementazioni tramite liste e vettori.

Giovedì 2 aprile 2009     Alberi binari (terminologia). Struttura dati heap. Descrizione delle operazioni di inserimento, estrazione del massimo, modifica e cancellazione. Analisi della complessità. Inizio di implementazione di una coda con priorità tramite heap: procedure heapUp() e heapDown().

Martedì 7 aprile 2009     Code con priorità tramite heap: implementazione delle operazioni di inserimento, estrazione del massimo, modifica della priorità e cancellazione. L'algoritmo di ordinamento heap-sort: analisi della complessità. Procedura di costruzione di un heap tramite heapDown() e analisi della complessità.

Giovedì 16 aprile 2009     Esercizi di preparazione alla prova intermedia.

Martedì 28 aprile 2009     Definizioni e proprietà di alberi: ordine, altezza e numero di nodi. Alberi ordinati e non. Alberi binari. Rappresentazione di un albero m-ario tramite un albero binario. Rappresentazione in memoria di alberi: strutture linkate e vettore dei padri. Visite di alberi: visita posticipata per valutare una espressione.
Dizionari: operazioni fondamentali. Discussione di possibili implementazioni tramite vettori e liste, ordinati e non.

Giovedì 30 aprile 2009     Alberi binari di ricerca. Operazioni di ricerca, inserimento e rimozione: analisi della complessità e implementazione. Descrizione della procedura per trovare il predecessore (e il successore).

Martedì 5 Maggio 2009     Esercitazione: procedure per trovare il predecessore e il successore di un nodo in un albero binario di ricerca. Visita anticipata, posticipata e simmetrica. Descrizione della procedura per il calcolo dell' altezza di un albero k-ario rappresentato come albero binario.

Giovedì 7 Maggio 2009     Alberi binari di ricerca bilanciati: alberi AVL. Dimostrazione che un albero AVL ha altezza O(logn). Operazioni di rotazione. Procedura di ribilanciamento a seguito di un inserimento: descrizione e dimostrazione di correttezza.

Martedì 12 Maggio 2009     Implementazione delle operazioni di rotazione. Procedura di ribilanciamento a seguito di una eliminazione: descrizione e dimostrazione di correttezza.
Introduzione alle tabelle Hash.

Giovedì 14 Maggio 2009     Tabelle hash. Universo delle chiavi e funzioni hash. Il problema delle collisioni. Hashing con liste di trabocco (o liste di collisione). Cenni sulla complessità nel caso ideale. Hashing interno (o indirizzamento aperto): sequenze di scansione, scansione lineare (fenomeni di agglomerazione) e hashing doppio. Operazione di eliminazione. Cenni sulla complessità nel caso ideale.

Martedì 19 Maggio 2009     Esercitazione: Tabelle hash. Hashing perfetto. Alberi AVL. Ordinamento di un vettore tramite un generico albero binario di ricerca ed un albero AVL.

Giovedì 21 Maggio 2009     Esempi di grafi. Definizioni di base: grafi diretti e non diretti, adiacenza, grado, cammini e cicli. Connessione: componenti connesse.

Martedì 26 Maggio 2009     Visite di grafi. Visita in profondità e visita in ampiezza. Uso delle visite per determinare le componenti connesse di grafi non diretti. Alberi di visita. Rappresentazioni di grafi: liste di adiacenza e matrici di adiacenza.

Giovedì 28 Maggio 2009     Implementazione di grafi tramite liste di adiacenza. Implementazione della visita in ampiezza e della visita in profondità. Applicazioni: componenti connesse e cammini minimi.

Giovedì 4 giugno 2009     Esercizi di preparazione alla prova scritta: da [Esercizio_1] a [Esercizio_10] disponibili qui.

Martedì 9 giugno 2009     Esercizi di preparazione alla prova scritta: da [Esercizio_11] a [Esercizio_20] disponibili qui.

Giovedì 11 giugno 2009     Esercizi di preparazione alla prova scritta: esercizi e soluzioni.

Martedì 16 giugno 2009     Esercizi di preparazione alla prova scritta: [Esercizio_21], [Esercizio_22], [Esercizio_23], [Esercizio_24] disponibili qui.