Strutture dati e algoritmi per la fisica dei dati
A.A. 2021/2022
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. 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. 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. 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.
Durante la presentazione, verranno poste domande volte a saggiare la conoscenza dello studente non solo dell'argomento trattato ma in generale della teoria degli algoritmi e delle strutture dati. 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. Il voto finale dell'esame è espresso in trentesimi.
Coloro che non saranno soddisfatti della valutazione finale assegnata alla loro presentazione potranno rifare la prova d'esame che ora sarà un tradizionale colloquio orale sugli argomenti trattati al corso.
Durante la presentazione, verranno poste domande volte a saggiare la conoscenza dello studente non solo dell'argomento trattato ma in generale della teoria degli algoritmi e delle strutture dati. 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. Il voto finale dell'esame è espresso in trentesimi.
Coloro che non saranno soddisfatti della valutazione finale assegnata alla loro presentazione potranno rifare la prova d'esame che ora sarà un tradizionale colloquio orale sugli argomenti trattati al corso.
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
Ufficio 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.