Algoritmi e strutture dati

A.A. 2019/2020
Insegnamento per
6
Crediti massimi
48
Ore totali
SSD
INF/01
Lingua
Italiano
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.

Struttura insegnamento e programma

Edizione attiva
Responsabile
INF/01 - INFORMATICA - CFU: 6
Lezioni: 48 ore
Docente: Foresti Sara
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
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]
Propedeuticità
Nessuna
Prerequisiti e modalità di esame
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.
Metodi didattici
Lezioni frontali.
Materiale didattico e bibliografia
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]
STUDENTI NON 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
Prerequisiti e modalità di esame
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.
Materiale didattico e bibliografia
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]
Periodo
Primo semestre
Periodo
Primo semestre
Modalità di valutazione
Esame
Giudizio di valutazione
voto verbalizzato in trentesimi
Docente/i
Ricevimento:
su appuntamento
via Celoria, 18 - Milano (MI)