Obiettivi formativi
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.
Attività formative
Il corso viene svolto in 80 ore di lezione frontale, di cui 60 ore
nel primo quadrimestre e 20 ore nel secondo quadrimestre. Nelle 80
ore di lezione sono comprese 26 ore di esercitazione nelle quali
gli studenti devono risolvere problemi specifici sotto la guida del
docente.
Programma del corso
- 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, heap di
Fibonacci, 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.