LABORATORIO DI ALGORITMI E STRUTTURE DATI
cod. 15397

Anno accademico 2008/09
1° anno di corso - Secondo semestre
Docente
Settore scientifico disciplinare
Informatica (INF/01)
Field
Formazione informatica
Tipologia attività formativa
Caratterizzante
40 ore
di attività frontali
4 crediti
sede: -
insegnamento
in - - -

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

- - -