Algoritmi e strutture dati
A.A. 2020/2021
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
Lezioni (in caso di erogazione a distanza):
Lezioni sincrone tramite la piattaforma Zoom
Esami (in caso di svolgimento a distanza):
L'esame consiste in una prova scritta della durata di 2.00 ore, che include domande a risposta aperta ed esercizi.
Tutte le risposte vanno inserite nel sistema, utilizzando gli strumenti di scrittura e disegno messi a disposizione dalla piattaforma.
L'esame viene svolto utilizzando Exam.net + SEB e controllo in video-conferenza tramite Zoom.
Lezioni sincrone tramite la piattaforma Zoom
Esami (in caso di svolgimento a distanza):
L'esame consiste in una prova scritta della durata di 2.00 ore, che include domande a risposta aperta ed esercizi.
Tutte le risposte vanno inserite nel sistema, utilizzando gli strumenti di scrittura e disegno messi a disposizione dalla piattaforma.
L'esame viene svolto utilizzando Exam.net + SEB e controllo in video-conferenza tramite Zoom.
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
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.
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.
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.
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.
La valutazione della prova è espressa in trentesimi.
I risultati della prova vengono resi disponibili sulla pagina Ariel dell'insegnamento.
Professor(s)