Strutture dati e algoritmi per la fisica dei dati
A.A. 2020/2021
Obiettivi formativi
L'insegnamento si propone di introdurre le basi matematiche e informatiche e i principali strumenti e tecniche per la progettazione di algoritmi efficienti. Particolare risalto viene posto all'analisi di strutture dati, fondamentali nella progettazione di algoritmi sofisticati applicabili in svariati ambiti scientifici. Vengono introdotti i principali strumenti matematici per l'analisi delle prestazioni e la valutazione di efficienza degli algoritmi e vengono illustrate le principali tecniche di progetto, discutendo la costruzione di algoritmi notevoli. Vengono infine presentati elementi di calcolo parallelo e distribuito.
Risultati apprendimento attesi
Lo studente sarà in grado di affrontare problemi tipicamente rivolti all'analisi dei dati, progettando concettualmente algoritmi sofisticati efficienti di soluzione. A tale scopo, saprà applicare le tecniche di costruzione di algoritmi viste durante l'insegnamento, così come utilizzare a supporto le principali strutture dati. Tali conoscenze potranno eventualmente essere messe a frutto mediante lo sviluppo di progetti C++ o Python.
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
Sui siti dedicati all'insegnamento (vedi sotto) verranno tempestivamente pubblicati avvisi riportanti le modalità di erogazione per un'eventuale fase di didattica emergenziale.
In caso di teledidattica, le lezioni verranno erogate via Zoom in modo sincrono e contestualmente registrate per un'eventuale fruizione asincrona. Il programma dell'insegnamento e le risorse per la preparazione dell'esame non subiranno modifiche. L'esame avverrà mediante Zoom secondo la forma e i criteri adottati per l'esame in presenza e sotto riportati.
In caso di teledidattica, le lezioni verranno erogate via Zoom in modo sincrono e contestualmente registrate per un'eventuale fruizione asincrona. Il programma dell'insegnamento e le risorse per la preparazione dell'esame non subiranno modifiche. L'esame avverrà mediante Zoom secondo la forma e i criteri adottati per l'esame in presenza e sotto riportati.
Programma
· Problemi e algoritmi
· Centralità degli algoritmi nell'Informatica
· Algoritmi da un punto di vista tecnologico: hardware vs. software
· Progetto e analisi degli algoritmi, una caso di studio: il problema dell'ordinamento
Un semplice algoritmo: insertion sort, analisi di correttezza e di prestazioni
Un algoritmo più sofisticato: merge sort, analisi di correttezza e prestazioni
Complessità in tempo, worst/best/average case
· Strumenti per la valutazione della complessità in tempo di algoritmi
Tasso di crescita
Valutazione asintotica della complessità in tempo
I simboli di Landau
Efficienza
· Una tecnica di costruzione degli algoritmi: divide et impera, ricorsione
Esempi
Strumenti matematici per l'analisi di algoritmi ricorsivi
Equazioni di ricorrenza e loro soluzione. Master Theorem
· Le principali strutture dati
Stack
Code
Liste
Principali funzionalità e operazioni nelle strutture dati, possibili implementazioni
· Hashing
Tabelle e funzioni di hashing
Hashing interno ed esterno
Hashing perfetto
· Alberi binari di ricerca
Definizione
Le operazioni di inserzione e delezione, ribilanciamento
Interrogazione
Valutazione delle prestazioni
· Tecniche avanzate di costruzione degli algoritmi
Programmazione dinamica, esempi
Algoritmi greedy, esempi. I matroidi
· Principali problemi e algoritmi su grafi
Nozioni base di teoria dei grafi
Rappresentazione dei grafi
Visita in ampiezza e profondità
Albero minimo di sostegno, algoritmi di Kruskal e Prim
Cammini minimi in grafi, algoritmi di Bellman-Ford e Dijkstra
Cammini minimi tra ogni coppia di nodi, algoritmi matriciali e di Floyd-Warshall
· Applicazioni della teoria degli algoritmi in ambito fisico: alcuni casi di studio
· Cenni alla progettazione e analisi di algoritmi su sistemi non Von Neumann
Algoritmi paralleli e distribuiti
· Centralità degli algoritmi nell'Informatica
· Algoritmi da un punto di vista tecnologico: hardware vs. software
· Progetto e analisi degli algoritmi, una caso di studio: il problema dell'ordinamento
Un semplice algoritmo: insertion sort, analisi di correttezza e di prestazioni
Un algoritmo più sofisticato: merge sort, analisi di correttezza e prestazioni
Complessità in tempo, worst/best/average case
· Strumenti per la valutazione della complessità in tempo di algoritmi
Tasso di crescita
Valutazione asintotica della complessità in tempo
I simboli di Landau
Efficienza
· Una tecnica di costruzione degli algoritmi: divide et impera, ricorsione
Esempi
Strumenti matematici per l'analisi di algoritmi ricorsivi
Equazioni di ricorrenza e loro soluzione. Master Theorem
· Le principali strutture dati
Stack
Code
Liste
Principali funzionalità e operazioni nelle strutture dati, possibili implementazioni
· Hashing
Tabelle e funzioni di hashing
Hashing interno ed esterno
Hashing perfetto
· Alberi binari di ricerca
Definizione
Le operazioni di inserzione e delezione, ribilanciamento
Interrogazione
Valutazione delle prestazioni
· Tecniche avanzate di costruzione degli algoritmi
Programmazione dinamica, esempi
Algoritmi greedy, esempi. I matroidi
· Principali problemi e algoritmi su grafi
Nozioni base di teoria dei grafi
Rappresentazione dei grafi
Visita in ampiezza e profondità
Albero minimo di sostegno, algoritmi di Kruskal e Prim
Cammini minimi in grafi, algoritmi di Bellman-Ford e Dijkstra
Cammini minimi tra ogni coppia di nodi, algoritmi matriciali e di Floyd-Warshall
· Applicazioni della teoria degli algoritmi in ambito fisico: alcuni casi di studio
· Cenni alla progettazione e analisi di algoritmi su sistemi non Von Neumann
Algoritmi paralleli e distribuiti
Prerequisiti
Insegnamenti introduttivi alla programmazione e alla matematica (quali quelli erogati alle triennali scientifiche).
Metodi didattici
L'insegnamento è costituito da lezioni frontali erogate in modo tradizionale. In tali lezioni vengono proposte anzitutto le basi informatiche e matematiche necessarie per lo sviluppo e l'analisi di algoritmi complessi applicabili in svariati ambiti. Vengono inoltre proposti e discussi esercizi, problemi e progetti che mirano a consolidare la teoria e a stimolare l'interesse verso argomenti più avanzati che richiedono e sviluppano una certa maturità informatica.
Materiale di riferimento
Testi:
Algoritmi e Strutture Dati
· T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein. Introduction to Algorithms. Third Edition, MIT Press, 2009. (Di questo testo è disponibile anche la versione italiana.)
· A.V. Aho, J.E. Hopcroft, J.D. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley, 1974.
Programmazione:
· P. Deitel, H. Deitel. Intro to Python. Pearson, 2020. (Versione italiana in preparazione.)
· D.S. Malik: Introduction to C++ Programming. Cengage South-Western, 2009.
Siti web:
- ARIEL https://cmereghettisdafd.ariel.ctu.unimi.it/
Algoritmi e Strutture Dati
· T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein. Introduction to Algorithms. Third Edition, MIT Press, 2009. (Di questo testo è disponibile anche la versione italiana.)
· A.V. Aho, J.E. Hopcroft, J.D. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley, 1974.
Programmazione:
· P. Deitel, H. Deitel. Intro to Python. Pearson, 2020. (Versione italiana in preparazione.)
· D.S. Malik: Introduction to C++ Programming. Cengage South-Western, 2009.
Siti web:
- ARIEL https://cmereghettisdafd.ariel.ctu.unimi.it/
Modalità di verifica dell’apprendimento e criteri di valutazione
L'esame consiste di una discussione orale che copre il più completamente possibile tutti gli argomenti trattati all'insegnamento. Verranno proposte domande volte ad accertare la padronanza, da parte dello studente, sia dei concetti base sia della capacità di applicare le tecniche principali di progettazione algoritmica nella soluzione di tipici problemi in ambito scientifico. Verranno anche proposte domande in cui si chiederà un contributo "originale" da parte dello studente, al fine di cogliere una certa maturità progettuale a livello algoritmico. La durata della prova orale è di circa 40 minuti circa. Sarà inoltre valutata la possibilità di affiancare la prova orale con la realizzazione di progetti software C++ o Python. Il voto finale dell'esame è espresso in trentesimi.
FIS/01 - FISICA SPERIMENTALE
FIS/07 - FISICA APPLICATA (A BENI CULTURALI, AMBIENTALI, BIOLOGIA E MEDICINA)
FIS/07 - FISICA APPLICATA (A BENI CULTURALI, AMBIENTALI, BIOLOGIA E MEDICINA)
Lezioni: 42 ore
Docenti:
Mereghetti Carlo, Tamascelli Dario
Docente/i
Ricevimento:
su appuntamento via mail
Uff. S 6008, VI piano, Dip. Informatica "Giovanni Degli Antoni", via Celoria 18, 20133 Milano, Italy
Ricevimento:
Martedì, 9:00-10:00 o su appuntamento (richiesta via e-mail al docente)
Stanza C12, quinto piano edificio LITA, Dipartimento di Fisica, via Celoria 16.