Obiettivi formativi
Scopo del corso è familiarizzare gli studenti con gli algoritmi, le strutture dati e con le tecniche per analizzare la loro efficienza.
Conoscenza e capacità di comprensione:
Acquisizione degli strumenti di base per l’analisi e la sintesi di soluzioni algoritmiche a problemi elementari del mondo reale. Lo studente alla fine del corso acquisirà una buona conoscenza dei principali algoritmi e delle più importanti strutture dati, usati per sviluppare software strutturato, efficiente, riusabile e pratico.
Capacità di applicare conoscenza e comprensione:
Sarà in grado di confrontare algoritmi diversi per uno stesso problema, di predire o garantire le prestazioni di un algoritmo per risolvere problemi di grandi dimensioni. Sarà in grado di studiare le limitazioni inerenti dei problemi da risolvere, organizzare e strutturare i dati da elaborare nel modo più opportuno, individuare e/o progettare algoritmi corretti ed efficienti.
Prerequisiti
- - -
Contenuti dell'insegnamento
Il corso presenta un’introduzione alle più importanti strutture dati e alle tecniche di base per la progettazione e l’analisi degli algoritmi.
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
• T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein. Introduction to algorithms, MIT Press, third edition, 2011.
• C. Demestrescu, I. Finocchi, G. F. Italiano, Algoritmi e strutture dati, McGraw Hill, seconda edizione, 2008.
• P. Crescenzi, G. Gambosi, R. Grossi. Strutture di Dati e Algoritmi, Pearson, prima edizione, 2006
Metodi didattici
Lezioni frontali con esercitazioni. L'insegnamento viene svolto nello stesso semestere di “Fondamenti di Programmazione B”, nelle cui ore di laboratorio vengono implementate alcuni delle più significative strutture dati utilizzando il linguaggio C++.
Modalità verifica apprendimento
L'esame comprende una prova scritta ed un eventuale colloquio orale che viene effettuato per sciogliere residui dubbi di valutazione. La prova scritta consiste di alcune domande di teoria e di un certo numero di esercizi, da svolgersi senza poter consultare libri o appunti. Gli esercizi possono comportare la risoluzione di problemi che sono minime varianti di questioni viste a lezione, o richiedere la risoluzione di problemi che non coincidono con nessuno dei problemi visti a lezione, ma che possono essere risolti con le tecniche sviluppate in classe.
La sufficienza può essere raggiunta rispondendo correttamente alle domande e risolvendo correttamente gli esercizi del primo tipo.
Altre informazioni
- - -
Obiettivi agenda 2030 per lo sviluppo sostenibile
- - -
