Algoritmi e strutture dati

A.A. 2021/2022
6
Crediti massimi
48
Ore totali
SSD
INF/01
Lingua
Italiano
Obiettivi formativi
L'insegnamento ha l'obiettivo di introdurre i concetti fondamentali relativi alla progettazione e analisi di algoritmi e delle strutture dati che questi utilizzano. L'insegnamento illustrerà le principali strutture dati e si focalizzerà su alcuni algoritmi specifici, studiandone anche la complessità computazionale.
Risultati apprendimento attesi
Lo studente dovrà conoscere e saper utilizzare le strutture dati e gli algoritmi di base presentati nell'insegnamento. Lo studente dovrà inoltre essere in grado di proporre soluzioni algoritmiche adeguate, utilizzando le strutture dati più appropriate, a problemi semplici, stimandone la complessità computazionale.
Programma e organizzazione didattica

Edizione unica

Responsabile
Periodo
Secondo semestre
In relazione alla modalità di erogazione delle attività formative per l'a.a. 2021/2022, verranno date indicazioni più specifiche nei prossimi mesi, in base alla evoluzione della situazione sanitaria.
Programma
1- Concetti fondamentali
Concetti di problema e di algoritmo; analisi di algoritmi, complessità in spazio e complessità computazionale di algoritmi, notazioni asintotiche, analisi della complessità di algoritmi; equazioni di ricorrenza

2- Strutture dati elementari
Stack, code, liste: definizioni e operazioni, implementazione tramite array e puntatori; dizionari e tabelle di hash

3- Alberi
Definizione di albero, principali operazioni su alberi, implementazione di alberi; alberi binari di ricerca: definizione, rappresentazione, operazioni; alberi bilanciati: alberi AVL, alberi B

4- Grafi
Definizione di grafo, rappresentazione di grafi; visita in ampiezza e profondità, concetto di componente connessa; minimum cost spanning tree; problema del cammino minimo

5- Algoritmi di ordinamento
Il problema dell'ordinamento; algoritmi di ordinamento: bubble sort, insertion sort, selection sort, merge sort, heap sort, quick sort (e sua analisi); sorting in tempo lineare

6- Tecniche di progettazione di algoritmi [cenni]
Divide-et-impera; algoritmi greedy; programmazione dinamica
Prerequisiti
E' richiesta la conoscenza dei concetti e costrutti fondamentali della programmazione imperativa.
E' richiesta la conoscenza delle principali funzioni matematiche e delle principali notazioni asintotiche.
Il superamento dell'esame di Programmazione è propedeutico all'insegnamento di Algoritmi e Strutture Dati. E' fortemente consigliato il superamento di esami di Matematica del Continuo.
Metodi didattici
Lezioni frontali
Materiale di riferimento
Sito web:
http://sforestiasd.ariel.ctu.unimi.it/

Testo di riferimento:
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein,
"Introduction to Algorithms", 3/ed, 2009
The MIT Press
[ISBN: 9780262033848]

disponibile anche in italiano
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein,
"Introduzione agli algoritmi e strutture dati", 3/ed, 2010
McGraw-Hill
[ISBN: 9788838665158]

Letture consigliate:
V. Aho, J.E. Hopcroft, J.D. Ullman, "Data Structures and Algorithms," Addison-Wesley, Reading, MA, 1983.
Modalità di verifica dell’apprendimento e criteri di valutazione
L'esame consiste in una prova scritta della durata di 2.30 ore, che include domande a risposta aperta ed esercizi.
La prova è volta a valutare la comprensione e l'apprendimento degli algoritmi e strutture dati studiati dall'insegnamento. La prova ha inoltre l'obiettivo di valutare la capacità di applicazione e utilizzo delle strutture dati e degli algoritmi studiati alla risoluzione di problemi semplici. Non è consentito consultare appunti o altro materiale durante la prova.
La valutazione della prova è espressa in trentesimi.
I risultati della prova vengono resi disponibili sulla pagina Ariel dell'insegnamento.
INF/01 - INFORMATICA - CFU: 6
Lezioni: 48 ore
Docente: Foresti Sara
Docente/i
Ricevimento:
su appuntamento
via Celoria, 18 - Milano (MI)