Algoritmi e strutture dati
A.A. 2024/2025
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.
Periodo: Primo semestre
Modalità di valutazione: Esame
Giudizio di valutazione: voto verbalizzato in trentesimi
Corso singolo
Questo insegnamento non può essere seguito come corso singolo. Puoi trovare gli insegnamenti disponibili consultando il catalogo corsi singoli.
Programma e organizzazione didattica
Edizione unica
Responsabile
Periodo
Primo semestre
Programma
1- Concetti fondamentali
Concetti di problema e di algoritmo; complessità computazionale di algoritmi, notazioni asintotiche; 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à; 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]
Concetti di problema e di algoritmo; complessità computazionale di algoritmi, notazioni asintotiche; 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à; 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]
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' consigliato il superamento dell'esame di Matematica del Continuo.
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' consigliato il superamento dell'esame di Matematica del Continuo.
Metodi didattici
Lezioni frontali
Materiale di riferimento
Sito web:
https://myariel.unimi.it/course/view.php?id=826
dove verranno messi a disposizionegli appunti delle lezioni
Testo di riferimento:
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein,
"Introduction to Algorithms", 4/ed, 2022
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", 4/ed, 2023
McGraw-Hill
[ISBN: 9788838665158]
Letture consigliate:
V. Aho, J.E. Hopcroft, J.D. Ullman, "Data Structures and Algorithms," Addison-Wesley, Reading, MA, 1983.
https://myariel.unimi.it/course/view.php?id=826
dove verranno messi a disposizionegli appunti delle lezioni
Testo di riferimento:
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein,
"Introduction to Algorithms", 4/ed, 2022
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", 4/ed, 2023
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 circa 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.
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
Turni:
Turno
Docente:
Foresti SaraSiti didattici
Docente/i