- Home
- Didattica
- I corsi di studio
- Corsi di laurea
LABORATORIO DI ALGORITMI E STRUTTURE DATI
Obiettivi formativi
Scopo del corso e' familiarizzare gli studenti con gli algoritmi, le strutture dati e con le tecniche per analizzare la loro efficienza.
Gli studenti dovranno preparare un progetto di programmazione.
Prerequisiti
E' richiesta una certa esperienza con il linguaggio C++ e la conoscenza dei concetti base di matematica discreta e di calcolo.
Contenuti dell'insegnamento
Modelli di calcolo, analisi di algoritmi.
Structure dati di base: linked lists, stacks, queues, trees.
Algoritmi di sorting di base , lower bounds per il sorting.
Quicksort, heapsort. Sorting in tempo lineare.
Mediano and statistiche d'ordine.
Tecnica divide et impera.
Introduzione alla programmazione dinamica e alla tecnica greedy.
Alberi di Huffman. Binary trees, binary search trees, B-trees, red-black trees.
Hash tables.
Grafi, BFS,DFS, DAG, topological sort e componenti fortemente connesse.
Union-find, MST, algoritmo di Kruskal, algoritmo di Prim.
Algoritmo di Dijkstra, algoritmo di Bellman-Ford.
Bibliografia
T. Cormen, C. Leiserson, R. Rivest, C. Stein, Introduction to Algorithms, McGraw-Hill;
C. Demetrescu, I. Finocchi, G.F. Italiano, Algoritmi e strutture dati, McGraw-Hill;
R. Sedgwick, Algorithms, Princeton University.
Metodi didattici
Altri insegnamenti
ANNO DI CORSO: 1
ANNO DI CORSO: 2
ANNO DI CORSO: 3

