Algoritmi e strutture dati
A.A. 2018/2019
Obiettivi formativi
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.
Risultati apprendimento attesi
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.
Programma e organizzazione didattica
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]
Docente/i