Algoritmi e strutture dati
A.A. 2023/2024
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 può essere seguito come corso singolo.
Programma e organizzazione didattica
Edizione unica
Responsabile
Periodo
Primo semestre
Programma
1- Concetti fondamentali
Concetti di problema e di algoritmo; analisi di algoritmi, complessità in spazio, complessità in tempo, notazioni asintotiche, analisi della complessità di algoritmi; equazioni di ricorrenza
2- Algoritmi di ordinamento
Il problema dell'ordinamento; algoritmi di ordinamento: insertion sort, selection sort, merge sort, heap sort, quick sort; ordinamento in tempo lineare
3- Strutture dati elementari
Stack, code, liste: definizioni e operazioni, implementazione tramite array e puntatori; dizionari e tabelle di hash
4- Alberi
Definizione di albero, principali operazioni su alberi, implementazione di alberi; alberi binari di ricerca: definizione, rappresentazione, operazioni; alberi bilanciati: alberi Rosso Neri, B-alberi
5- Grafi
Definizione di grafo, rappresentazione di grafi; visita in ampiezza e profondità, concetto di componente connessa; minimum cost spanning tree; problema del cammino minimo
6- Tecniche di progettazione di algoritmi [cenni]
Esempi di algoritmi greedy e di algoritmi di programmazione dinamica
Concetti di problema e di algoritmo; analisi di algoritmi, complessità in spazio, complessità in tempo, notazioni asintotiche, analisi della complessità di algoritmi; equazioni di ricorrenza
2- Algoritmi di ordinamento
Il problema dell'ordinamento; algoritmi di ordinamento: insertion sort, selection sort, merge sort, heap sort, quick sort; ordinamento in tempo lineare
3- Strutture dati elementari
Stack, code, liste: definizioni e operazioni, implementazione tramite array e puntatori; dizionari e tabelle di hash
4- Alberi
Definizione di albero, principali operazioni su alberi, implementazione di alberi; alberi binari di ricerca: definizione, rappresentazione, operazioni; alberi bilanciati: alberi Rosso Neri, B-alberi
5- Grafi
Definizione di grafo, rappresentazione di grafi; visita in ampiezza e profondità, concetto di componente connessa; minimum cost spanning tree; problema del cammino minimo
6- Tecniche di progettazione di algoritmi [cenni]
Esempi di algoritmi greedy e di algoritmi di 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 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' fortemente consigliato il superamento dell'esame di Matematica del Continuo.
Metodi didattici
Lezioni frontali
Materiale di riferimento
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", 4/ed, 2023 McGraw-Hill
[ISBN: 8838656215 · 9788838656217]
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", 4/ed, 2023 McGraw-Hill
[ISBN: 8838656215 · 9788838656217]
Modalità di verifica dell’apprendimento e criteri di valutazione
L'esame consiste in una prova scritta, che include domande a risposta aperta ed esercizi.
La prova è volta a valutare la comprensione e l'apprendimento degli algoritmi e strutture dati studiati nell'insegnamento. La prova ha inoltre l'obiettivo di valutare la capacità di scelta 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 prova è volta a valutare la comprensione e l'apprendimento degli algoritmi e strutture dati studiati nell'insegnamento. La prova ha inoltre l'obiettivo di valutare la capacità di scelta e utilizzo delle strutture dati e degli algoritmi studiati alla risoluzione di problemi semplici. Non è consentito consultare appunti o altro materiale durante la prova.
Siti didattici
Docente/i
Ricevimento:
su appuntamento
stanza 3012 via Celoria 18