Algoritmi e Strutture Dati
Corsi di Laurea in Informatica e in Tecnologie Web e Multimediali
Università degli Studi di Udine
Anno Accademico 2015-2016
Finalità
Il corso si propone di introdurre ai fondamenti della teoria degli algoritmi, delle strutture dati e all'analisi della complessità computazionale di programmi. Il principale obiettivo del corso è familiarizzare lo studente con le principali problematiche e tecniche relative al disegno e alla progettazione di algoritmi. Ci si propone inoltre di introdurre i metodi di base utilizzati per stabilire la complessità di programmi e i criteri utilizzati per scegliere e progettare strutture dati.
Dopo aver superato l'esame si ritiene che lo studente sia in grado di risolvere algoritmicamente problemi classici e scegliere motivatamente le strutture dati adatte ad ottenere soluzioni computazionalmente efficienti. Sia in grado di porre limiti superiori sufficientemente precisi e indipendenti dall'architettura alla complessità computazionale di programmi di media difficoltà. Conosca i più importanti problemi e algoritmi classici del campo nonché le più importanti e utilizzate tecniche di analisi della complessità e di strutturazione dei dati.
Argomenti
- Introduzione e nozioni preliminari.
Introduzione. Elementi di logica e teoria degli insiemi. Alberi e grafi. Matematica discreta e analisi asintotica. Modelli di calcolo per la determinazione della complessità degli algoritmi. Problemi ricorsivi e aspetti algoritmici. - Algoritmi di ricerca e ordinamento.
Algoritmi primitivi di ricerca e ordinamento: binary search, selection-sort, insertion-sort, bubble-sort, heap-sort. Algoritmi ricorsivi di ordinamento: quick-sort, merge-sort. Analisi della complessità e limiti inferiori. Algoritmi di ordinamento lineari non basati sul confronto: counting-sort, radix-sort, bucket-sort. Algoritmi di ricerca: selezione in tempo lineare. - Strutture dati.
Strutture dati primitive: liste, pile, code, heap. Algoritmi e strutture dati per la gestione e manipolazione di insiemi: tabelle hash, alberi di ricerca (BST), bilanciamento, red-black alberi e B-alberi. Algoritmi e strutture dati per il problema Union-Find. Cenni alle strutture dati self-adjusting. - Algoritmi sui grafi.
Tecniche di rappresentazione di grafi orientati e non orientati. Algoritmi di visita in ampiezza (BFS) e profondita' (DFS). Algoritmi di visita su alberi. Calcolo delle componenti fortemente connesse. Algoritmi per la determinazione di topological-sort, minimum spanning tree (Prim e Kruskal), cammino minimo da una sorgente (Dijkstra, Bellmann-Ford) cammini minimi da sorgenti multiple (Floyd-Warshall, Johnson).
Laboratorio
Al corso di ASD è associato un laboratorio gestito dal Prof. Alberto Policriti.
Modalità d'Esame
Il corso di ASD prevede una prova scritta di ammissione all'orale e una prova orale. Le due prove devono essere sostenute nello stesso appello. Una prova scritta consente l'ammissione all'orale solo se è stata valutata più di 16 trentesimi.
Per sostenere la prova scritta è necessario essersi iscritti all'appello scritto su Esse3. Per sostenere la prova orale e per registrare il voto è necessario iscriversi all'appello orale su Esse3.
La prova scritta relativa al primo appello dell'anno accademico (l'appello di Giugno) è sostituita da due compitini che si tengono rispettivamente durante l'interruzione tra I e II periodo didattico ed in occasione del primo appello della sessione estiva. Il voto che si ottiene dopo aver svolto i compitini è la media dei voti conseguiti in ciascun compitino e la prova risulta superata quando tale media supera i 16 trentesimi. In caso tale votazione venga raggiunta è consentito sostenere la prova orale nel primo appello (Giugno) o nel successivo (Luglio).
Oltre al secondo compitino non ci saranno altre prove scritte in Giugno.
La prova orale è obbligatoria per coloro i quali hanno conseguito un voto inferiore a 20 oppure superiore a 27. Se la prova orale non viene superata è necessario ripetere anche la prova scritta.
L'esame prevede anche una parte di laboratorio. Il voto conseguito nel laboratorio verrà trasformato in trentesimi e il voto del corso sarà calcolato come media pesata tra il voto dell'orale (peso 3/4) e il voto del laboratorio (peso 1/4).
Bibliografia
- Cormen T.H., Leiserson C.E., Rivest R.L, Stein C., Introduction to Algorithms, MIT Press, Third edition, 2009.
- Altri testi utili:
- A. Bertossi, A. Montresor. Algoritmi e Strutture Dati, 2/ed, Citta'Studi Edizioni, 2010.
- C. Demetrescu, I. Finocchi, G. F. Italiano, Algoritmi e Strutture Dati, 2/ed, McGraw-Hill, 2007.
- P. Crescenzi, G. Gambosi, R. Grossi. Strutture di Dati e Algoritmi, Addison-Wesley Pearson, 2006.
- Aho A.V., Hopcroft J.E., Ullman J.D., Data Structures and Algorithms, Addison-Wesley, 1983.
- Aho A.V., Hopcroft J.E., Ullman J.D., The Design and Analysis of Computer Algorithms, Addison-Wesley, 1974.
- Appunti non ufficiali delle lezioni. Da consultare solo per vedere l'elenco degli argomenti svolti.
Alcuni Link Esterni Utili
- Lezioni del Prof. Leiserson al MIT
- Data Structure Visualizations: visualizzazione di strutture dati e algoritmi
- HackerRank: esercitarsi con il codice
- GeeksQuiz: esercitarsi con quiz e codice
Esercitazioni Settimanali
Questa sezione contiene alcuni esercizi con suggerimenti e soluzioni. Non si tratta di esercizi di base, ma neanche di esercizi di particolare difficoltà. Non è sufficiente aver svolto questi esercizi per avere una buona preparazione per l'esame.
