ALGORITMI E STRUTTURE DATI I ( cod. 14839)
Insegnamento di INFORMATICA (Corsi di Laurea)
Facoltà di Corsi di Laurea triennale (D.M. 270/04)
TIPOLOGIA DELL'INSEGNAMENTO: ATTIVITÀ FORMATIVE CARATTERIZZANTI LA CLASSE
Lingua Insegnamento:
italiano
FREQUENZA FACOLTATIVA
Obiettivi
Scopo del corso e’ familiarizzare gli studenti con gli algoritmi, le strutture
dati e con le tecniche per analizzare la loro efficienza.
Contenuti dell'insegnamento
Il corso presenta un’introduzione alle piu' importanti strutture dati e alle tecniche
di programmazione.
Programma esteso
• Indecibilita', intrattabilita' dei problemi computazionali,
• Complessita' computazionale: modelli di calcolo, analisi di algoritmi.
• Tecnica divide et impera, relazioni di ricorrenza, Lemma fondamentale.
• Strutture dati di base: linked lists, stacks, queues, trees.
• Algoritmi di sorting basati sui confronti: Insertionsort, Mergesort, Quick-
sort, Heapsort.
• Limiti inferiori all’ordinamento e alla ricerca.
• Sorting in tempo lineare.
• Mediano and statistiche d’ordine.
• Introduzione alla programmazione dinamica e alla tecnica greedy.
• Alberi binari, alberi binari di ricerca, alberi AVL, B-alberi.
• Tabelle hash.
• Grafi, BFS,DFS, DAG, ordinamento topologico, componenti fortemente
connesse.
• Union-find, MST, algoritmo di Kruskal, algoritmo di Prim.
• Algoritmo di Dijkstra, algoritmo di Bellman-Ford.
Bibliografia Consigliata
• 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 in C++, Princeton University.
Metodi di valutazione:
Esame scritto e orale. Metodi didattici
Lezioni, esercitazioni ed esercitazioni in laboratorio.
Docenti
Anno accademico:
2012
Anno di corso:
1
Semestre:
2
Numero CFU:
9
SSD:
INFORMATICA (INF/01)
Ambito:
Discipline Informatiche
Ore di attivita frontale:
72 