Algoritmi e strutture dati
A.A. 2018/2019
Learning objectives
Il corso ha l'obiettivo di introdurre i concetti fondamentali degli algoritmi e delle strutture dati, l'analisi della complessità degli algoritmi, le strutture dati elementari (i.e., liste, stack, coda, dizionario), la struttura dati albero, la struttura grafo, il problema dell'ordinamento, e la progettazione di algoritmi.
Expected learning outcomes
Non definiti
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
STUDENTI FREQUENTANTI
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; classi di complessità
2- Strutture dati elementari
Stack, code, liste: definizioni e operazioni, implementazione tramite array e puntatori; tabelle di hash
3- Alberi
Definizione di albero, principali operazioni su alberi, rappresentazione di alberi; alberi binari di ricerca: definizione, rappresentazione, operazioni; alberi binari bilanciati
4- Grafi
Definizione di grafo, rappresentazione di grafi; visita in ampiezza e profondità, concetto di componente connessa; minimum spanning tree; problema del cammino minimo
5- Algoritmi di ordinamento
Il problema dell'ordinamento; algoritmi di ordinamento: insertion 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; classi di complessità
2- Strutture dati elementari
Stack, code, liste: definizioni e operazioni, implementazione tramite array e puntatori; tabelle di hash
3- Alberi
Definizione di albero, principali operazioni su alberi, rappresentazione di alberi; alberi binari di ricerca: definizione, rappresentazione, operazioni; alberi binari bilanciati
4- Grafi
Definizione di grafo, rappresentazione di grafi; visita in ampiezza e profondità, concetto di componente connessa; minimum spanning tree; problema del cammino minimo
5- Algoritmi di ordinamento
Il problema dell'ordinamento; algoritmi di ordinamento: insertion 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
Informazioni sul programma
1. Concetti fondamentali
2. Strutture dati elementari
3. Alberi
4. Grafi
5. Algoritmi di ordinamento
6. Tecniche di progettazione di algoritmi [cenni]
2. Strutture dati elementari
3. Alberi
4. Grafi
5. Algoritmi di ordinamento
6. Tecniche di progettazione di algoritmi [cenni]
Propedeuticità
Nessuna
Prerequisiti
Prerequisiti: Nessuno
Modalità d'esame: L'esame consiste in una prova scritta che comprende sia domande di teoria sia esercizi pratici sugli argomenti trattati dal corso, volti a valutare la preparazione dello studente.
Modalità d'esame: L'esame consiste in una prova scritta che comprende sia domande di teoria sia esercizi pratici sugli argomenti trattati dal corso, volti a valutare la preparazione dello studente.
Metodi didattici
Lezioni frontali.
Materiale di riferimento
STUDENTI NON FREQUENTANTI
Materiale didattico fornito dal docente disponibile sulla piattaforma Ariel (http://sforestiasd.ariel.ctu.unimi.it/v3/Home/)
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]
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]
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; classi di complessità
2- Strutture dati elementari
Stack, code, liste: definizioni e operazioni, implementazione tramite array e puntatori; tabelle di hash
3- Alberi
Definizione di albero, principali operazioni su alberi, rappresentazione di alberi; alberi binari di ricerca: definizione, rappresentazione, operazioni; alberi binari bilanciati
4- Grafi
Definizione di grafo, rappresentazione di grafi; visita in ampiezza e profondità, concetto di componente connessa; minimum spanning tree; problema del cammino minimo
5- Algoritmi di ordinamento
Il problema dell'ordinamento; algoritmi di ordinamento: insertion 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; classi di complessità
2- Strutture dati elementari
Stack, code, liste: definizioni e operazioni, implementazione tramite array e puntatori; tabelle di hash
3- Alberi
Definizione di albero, principali operazioni su alberi, rappresentazione di alberi; alberi binari di ricerca: definizione, rappresentazione, operazioni; alberi binari bilanciati
4- Grafi
Definizione di grafo, rappresentazione di grafi; visita in ampiezza e profondità, concetto di componente connessa; minimum spanning tree; problema del cammino minimo
5- Algoritmi di ordinamento
Il problema dell'ordinamento; algoritmi di ordinamento: insertion 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
Prerequisiti: Nessuno
Modalità d'esame: L'esame consiste in una prova scritta che comprende sia domande di teoria sia esercizi pratici sugli argomenti trattati dal corso, volti a valutare la preparazione dello studente.
Modalità d'esame: L'esame consiste in una prova scritta che comprende sia domande di teoria sia esercizi pratici sugli argomenti trattati dal corso, volti a valutare la preparazione dello studente.
Materiale di riferimento
Materiale didattico fornito dal docente disponibile sulla piattaforma Ariel (http://sforestiasd.ariel.ctu.unimi.it/v3/Home/)
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]
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]
Professor(s)