Algoritmi e Strutture Dati
Programmazione delle Lezioni
Primo Semestre
Giovedì 13:30 - 17:30
Aula V3, via Venezian
Orario di Ricevimento
dopo la lezione, oppure
su appuntamento via email
Programma del corso
- Concetti fondamentali
Concetti di problema e di algoritmo; analisi di algoritmi, complessità in spazio e complessità computazionale di algoritmi, notazioni asintotiche, analisi della complessità di algoritmi; equazioni di ricorrenza - Strutture dati elementari
Stack, code, liste: definizioni e operazioni, implementazione tramite array e puntatori; dizionari e tabelle di hash - Alberi
Definizione di albero, principali operazioni su alberi, rappresentazione di alberi; alberi binari di ricerca: definizione, rappresentazione, operazioni; alberi bilanciati: alberi AVL, alberi B - Grafi
Definizione di grafo, rappresentazione di grafi; visita in ampiezza e profonditì, concetto di componente connessa; minimum cost spanning tree; problema del cammino minimo - Algoritmi di ordinamento
Il problema dell'ordinamento; algoritmi di ordinamento: insertion sort, merge sort, heap sort, quick sort (e sua analisi); sorting in tempo lineare - Tecniche di progettazione di algoritmi [cenni]
Divide-et-impera; algoritmi greedy; programmazione dinamica
Pagina Web
Pagina myAriel dell'insegnamento.
Testo di Riferimento
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein,
Introduction to Algorithms
The MIT Press, 2009 (third edition)
[ISBN: 9780262033848]
disponibile anche in italiano
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein,
Introduzione agli algoritmi e strutture dati
McGraw-Hill, 2010 (terza edizione)
[ISBN: 9788838665158]
Letture Consigliate
V. Aho, J.E. Hopcroft, J.D. Ullman,
Data Structures and Algorithms
Addison-Wesley, Reading, MA
Esami
L'esame consiste in una prova scritta che comprende sia domande di teoria sia esercizi pratici sugli argomenti trattati dal corso.