Algoritmi e Strutture Dati
Corsi di Laurea in Informatica e in Internet of Things, Big Data and Web
Università degli Studi di Udine
Anno Accademico 2018-2019
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. 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.
Al termine delle prove scritte vengono fornite spiegazioni riguardo agli esercizi. Chi ritiene di aver consegnato una prova insufficiente può decidere di ritirarsi. Chi non si ritira e consegue un voto insufficiente deve saltare la prova scritta successiva.
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. Se la media dei compitini è insufficiente si può sostenere lo scritto 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.
