Università degli Studi di Parma

il mondo che ti aspetta
  • english version

menu

LABORATORIO DI ALGORITMI E STRUTTURE DATI

COD. 15397
Insegnamento del corso di Laurea triennale (DM509) in INFORMATICA
Tipologia insegnamento: Caratterizzante

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

Docenti

Prof.ssa LOTTI Grazia
ANNO ACCADEMICO: 2007/2008
Anno di corso: 1
SEMESTRE: II° semestre
NUMERO CFU: 4
SSD: INFORMATICA (INF/01)
AMBITO: Formazione informatica
Ore di attivita' frontale: 40

Altri insegnamenti

ANNO DI CORSO: 1

ANNO DI CORSO: 2

ANNO DI CORSO: 3