Strutture dati e algoritmi per la fisica dei dati
A.A. 2024/2025
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
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
· Introduzione ai Tensor-Networks
· 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
· Introduzione ai Tensor-Networks
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. Fourth Edition, MIT Press, 2022.
· A.V. Aho, J.E. Hopcroft, J.D. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley, 1974.
Programmazione:
· P. Deitel, H. Deitel. Introduzione a Python. Pearson, 2021.
· 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. Fourth Edition, MIT Press, 2022.
· A.V. Aho, J.E. Hopcroft, J.D. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley, 1974.
Programmazione:
· P. Deitel, H. Deitel. Introduzione a Python. Pearson, 2021.
· 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
La prova d'esame consiste nella preparazione di una presentazione orale su un argomento legato alla teoria degli algoritmi. Tale argomento, che deve essere PREVENTIVAMENTE comunicato e approvato dai docenti, può essere l'approfondimento di una tematica trattata durante l'insegnamento oppure la discussione di applicazioni e/o problemi non direttamente trattati a lezione ma comunque fortemente legati all'insegnamento stesso.
Oltre a tale presentazione di carattere teorico, è richiesta la realizzazione di software che implementi quanto trattato nella presentazione stessa; il software può essere sviluppato in C++, Python o un linguaggio a scelta.
In totale, presentazione più discussione del software dovranno durare circa 30 minuti, cui si aggiungerà tempo per discussioni e domande da parte dei docenti.
Al termine della presentazione, avverrà un breve colloquio orale sugli argomenti trattati al corso; tale colloquio sarà volto a saggiare la conoscenza dello studente non solo dell'argomento presentato ma in generale della teoria degli algoritmi e delle strutture dati.
Il voto finale dell'esame è espresso in trentesimi.
Coloro che non saranno soddisfatti della valutazione finale assegnata alla loro presentazione + orale potranno risostenere la prova d'esame che sarà un tradizionale colloquio orale sugli argomenti trattati al corso.
Oltre a tale presentazione di carattere teorico, è richiesta la realizzazione di software che implementi quanto trattato nella presentazione stessa; il software può essere sviluppato in C++, Python o un linguaggio a scelta.
In totale, presentazione più discussione del software dovranno durare circa 30 minuti, cui si aggiungerà tempo per discussioni e domande da parte dei docenti.
Al termine della presentazione, avverrà un breve colloquio orale sugli argomenti trattati al corso; tale colloquio sarà volto a saggiare la conoscenza dello studente non solo dell'argomento presentato ma in generale della teoria degli algoritmi e delle strutture dati.
Il voto finale dell'esame è espresso in trentesimi.
Coloro che non saranno soddisfatti della valutazione finale assegnata alla loro presentazione + orale potranno risostenere la prova d'esame che sarà un tradizionale colloquio orale sugli argomenti trattati al corso.
FIS/01 - FISICA SPERIMENTALE - CFU: 3
FIS/07 - FISICA APPLICATA (A BENI CULTURALI, AMBIENTALI, BIOLOGIA E MEDICINA) - CFU: 3
FIS/07 - FISICA APPLICATA (A BENI CULTURALI, AMBIENTALI, BIOLOGIA E MEDICINA) - CFU: 3
Lezioni: 42 ore
Docente:
Tamascelli Dario
Docente/i
Ricevimento:
Su appuntamento, inviare e-mail al docente
Stanza C12, quinto piano edificio LITA, Dipartimento di Fisica, via Celoria 16.