Nel corso vengono esaminati i concetti di base per la formulazione di soluzioni algoritmiche a problemi concreti. Vengono studiate soluzioni a problemi formulati in termini di strutture matematiche astratte (liste, code, grafi, ...) e vengono descritte metodologie per identificare i problemi astratti che più si addicono allo studio di un problema concreto. Gli algoritmi vengono valutati e confrontati in base alla quantità di risorse che richiedono. Il corso si concentra inoltre sul ruolo che ha lo studio delle strutture di dati nella formulazione e valutazione di nuovi algoritmi.
Il corso viene svolto in 64 ore di lezione frontale, di cui 32 ore nel primo quadrimestre e 32 ore nel secondo quadrimestre. Nelle 64 ore di lezione sono comprese 20 ore di esercitazione durante le quali gli studenti devono risolvere problemi specifici sotto la guida del docente.
Complessità: complessità degli algoritmi, notazione asintotica, metodi di risoluzione delle equazioni di ricorrenza, analisi ammortizzata.
Ordinamento e Selezione: insertion sort, merge sort, heap sort, quick sort, quick sort probabilistico. Studio della complessità degli algoritmi di ordinamento, limite inferiore dell'ordinamento per confronti. Algoritmi lineari, counting sort, radix sort, bucket sort. Algoritmi di selezione, minimo, massimo, selezione in tempo medio lineare, selezione in tempo pessimo lineare.
Strutture dati: Code, pile, liste, heap, alberi binari di ricerca, alberi RB, heap binomiali, insiemi disgiunti, tecniche di estensione di una struttura dati.
Grafi: Definizione e rappresentazione di un grafo, visita in ampiezza, visita in profondità, ordinamento topologico, componenti connesse, alberi di copertura di costo minimo (Prim e Kruskal), cammini minimi a sorgente singola (Dijkstra e Bellman-Ford) e multipla (Floyd-Warshall e Johnson), flusso massimo (Ford-Fulkerson, Karp), matching massimale su grafo bipartito.
Lezione 2:Complessità degli algoritmi, Notazione asintotica O(f), Omega(f), e Theta(f).
Riferimenti: [CLR] Capitolo 2.
Lezione 3: Algoritmi ricorsivi, Risoluzione di equazioni di ricorrenza
(metodo iterativo, metodo di sostituzione, teorema principale).
Riferimenti: [CLR] Capitolo 4 Sezioni 1-3.
Lezione 4: Algoritmi di ordinamento,
&Insertion sort, merge sort,
Studio della complessità,
Stabilità e ordinamento in loco.
Riferimenti: [CLR] Capitolo 1.
Lezione 5: Algoritmi di ordinamento: heap sort.
Riferimenti: [CLR] Capitolo 7.
Lezione 6: Algoritmi di ordinamento: quick sort, quick sort
probabilistico, Limite inferiore alla complessità di ordinamento per confronti.
Riferimenti: [CLR] Capitolo 8 Sezioni 1-3.
Lezione 7:Algoritmi di ordinamento lineari: counting sort,
radix sort, bucket sort.
Riferimenti: [CLR] Capitolo 9.
Lezione 8:Algoritmi di Selezione. Tempi medio e peggiore lineari.
Riferimenti: [CLR] Capitolo 10.
Lezione 9: Strutture dati elementari. Stack, code, liste,
Alberi binari di ricerca
Riferimenti: [CLR] Capitoli 11 e 13.
Lezione 10:RB-alberi.
Riferimenti: [CLR] Capitolo 14.
Lezione 11: Estensione di una struttura dati. Alberi di intervalli.
Riferimenti: [CLR] Capitolo 15.
Lezione 12:Heap binomiali.
Riferimenti: [CLR] Capitolo 20.
Lezione 13:Strutture per insiemi disgiunti.
Riferimenti: [CLR] Capitolo 22.
Lezione 14:Programmazione dinamica.
Riferimenti: [CLR] Capitolo 16.
Lezione 15:Algoritmi greedy.
Riferimenti: [CLR] Capitolo 17 Sezioni 1-3.
Lezione 16:Grafi: definizione e rappresentazione.
Riferimenti: [CLR] Capitolo 23 Sezione 1.
Lezione 17:Visita di grafi. BFS, DFS.
Riferimenti: [CLR] Capitolo 23 Sezioni 2-3.
Lezione 18: Ordinamento topologico. Componenti connesse.
Riferimenti: [CLR] Capitolo 23 Sezioni 4-5.
Lezione 19:Alberi di copertura di costo minimo. Algoritmi
di Kruskal e Prim.
Riferimenti: [CLR] Capitolo 24.
Lezione 20:Cammini minimi. Algoritmi di Dijkstra e Bellman-Ford
per sorgente singola.
Riferimenti: [CLR] Capitolo 25.
Lezione 21:Cammini minimi. Algoritmi di Floyd-Warshall e Johnson per
sorgenti multiple.
Riferimenti: [CLR] Capitolo 26.
Lezione 22:Flusso massimo. Algoritmo di Ford-Fulkerson. Matching
massimale su grafo bipartito.
Riferimenti: [CLR] Capitolo 27 Sezioni 1-3.