ALGORITMI E STRUTTURE DATI I
cod. 23640

Anno accademico 2007/08
2° anno di corso - Secondo semestre
Docente
Settore scientifico disciplinare
Informatica (INF/01)
Field
Formazione interdisciplinare e applicativa
Tipologia attività formativa
Affine/Integrativa
48 ore
di attività frontali
6 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 /><br />

Prerequisiti

E' richiesta  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.<br />

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 />

Metodi didattici

<br />

Modalità verifica apprendimento

- - -

Altre informazioni

- - -