Algoritmi e strutture dati
A.A. 2023/2024
Learning objectives
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.
Expected learning outcomes
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.
Course syllabus and organization
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:
http://sforestiasd.ariel.ctu.unimi.it/
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", 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.
http://sforestiasd.ariel.ctu.unimi.it/
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", 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.
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.
Educational website(s)
Professor(s)