Algoritmi e Strutture Dati
Corsi di Laurea in Informatica e in Tecnologie Web e Multimediali
Università degli Studi di Udine
Anno Accademico 2017-2018
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 e una prova orale. Le due prove devono essere sostenute nello stesso appello. La prova scritta consente l'ammissione all'orale solo se è stata valutata almeno 16 trentesimi. La prova orale è obbligatoria solo per chi ha conseguito nella prova scritta un voto inferiore a 20 o superiore a 27.
Per sostenere le prove scritte e orali è necessario essersi iscritti al relativo appello su Esse3.
La prova scritta relativa al primo appello dell'anno accademico (appello di Giugno) è sostituita da due compitini che si tengono rispettivamente durante l'interruzione tra I e II periodo didattico e 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. La prova risulta superata quando la media è almeno 16 (15,5 si arrotonda a 16). Se la media ottenuta è inferiore a 20 o superiore a 27 è obbligatorio sostenere la prova orale. La prova orale può essere sostenuta nell'appello di giugno o in quello di luglio.
Oltre al secondo compitino non ci saranno altre prove scritte in Giugno.
Il laboratorio di ASD prevede la consegna un progetto assegnato e corretto dal Prof. Policriti.
Il voto del corso di Algoritmi e Strutture Dati e Laboratorio sarà calcolato come media pesata tra il voto di ASD (peso 9/12) e il voto del laboratorio di ASD (peso 3/12).
Per la registrazione del voto del corso di Algoritmi e Strutture Dati e Laboratorio, una volta superate tutte le prove, è necessario iscriversi su Esse3 al primo appello orale disponibile e inviare una mail con oggetto Registrazione ASD a carla.piazza@uniud.it con le seguenti informazioni:
- nome, cognome e numero di matricola;
- data e voto della prova scritta;
- data e voto dell'eventuale prova orale;
- data e voto del laboratorio.
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.
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.
