Obiettivi formativi
Scopo del corso e' familiarizzare gli studenti con gli algoritmi, le strutture dati e con le tecniche per analizzare la loro efficienza.<br />Gli studenti dovranno preparare un progetto di programmazione.<br /><br />
Prerequisiti
E' richiesta una certa esperienza con il linguaggio C++ e la conoscenza dei concetti base di matematica discreta e di calcolo. <br /><br />
Contenuti dell'insegnamento
<br /><br />Modelli di calcolo, analisi di algoritmi.<br />Structure dati di base: linked lists, stacks, queues, trees.<br />Algoritmi di sorting di base , lower bounds per il sorting.<br />Quicksort, heapsort. Sorting in tempo lineare.<br />Mediano and statistiche d'ordine.<br />Tecnica divide et impera.<br />Introduzione alla programmazione dinamica e alla tecnica greedy.<br /> Alberi di Huffman. Binary trees, binary search trees, B-trees, red-black trees.<br />Hash tables.<br />Grafi, BFS,DFS, DAG, topological sort e componenti fortemente connesse.<br />Union-find, MST, algoritmo di Kruskal, algoritmo di Prim.<br />Algoritmo di Dijkstra, algoritmo di Bellman-Ford.
Programma esteso
- - -
Bibliografia
<br /><br />T. Cormen, C. Leiserson, R. Rivest, C. Stein, Introduction to Algorithms, McGraw-Hill;<br />C. Demetrescu, I. Finocchi, G.F. Italiano, Algoritmi e strutture dati, McGraw-Hill; <br />R. Sedgwick, Algorithms, Princeton University.<br />
Metodi didattici
<br />
Modalità verifica apprendimento
- - -
Altre informazioni
- - -
Obiettivi agenda 2030 per lo sviluppo sostenibile
- - -