Analisi degli Algoritmi e Complessità Computazionale. Introduzione a moduli Python per l'analisi dei dati e di grafi. Tecniche algoritmiche: programmazione dinamica e algoritmi golosi. Sviluppo di algoritmi efficienti in grafi per: community detection, centralità, analisi delle distanze.
- Libro interattivo "How to think like a data scientist" disponibile all'indirizzo:
https://runestone.academy/runestone/static/httlads/index.html
- Libro interattivo "Problem Solving with Algorithms and Data Structures using Python" disponibile all'indirizzo: https://interactivepython.org/courselib/static/pythonds/index.html
- dispense
Obiettivi Formativi
Lo scopo di questo corso è quello di introdurre gli studenti alla progettazione, all'analisi e alla sperimentazione di algoritmi efficienti per l'analisi dei dati, attraverso la sperimentazione e lo sviluppo di algoritmi per grafi. L'apprendimento e lo sviluppo in Python di algoritmi per grafi sarà un'occasione per sviluppare le abilità di problem solving e di programmazione, imparando a usare moduli Python finalizzati all'analisi dei dati. Alla fine del corso gli studenti avranno una buona conoscenza delle problematiche computazionali e delle tecniche algoritmiche necessarie per un calcolo efficiente, saranno in grado di formulare e risolvere problemi legati all'analisi dei dati e di valutare le possibili soluzioni sia in termini di semantica che di efficienza.
Prerequisiti
Gli studenti devono (1) avere una conoscenza di base di algoritmi e strutture dati, (2) avere familiarità con la teoria della probabilità e la statistica di base, (3) avere buone capacità di programmazione (per esempio, in Python).
Metodi Didattici
E' previsto un ripasso di Python e sull'analisi di algoritmi per il recupero dei concetti necessari. Utilizzo di libri interattivi online per consentire la sperimentazione delle diverse soluzioni proposte in un'ambiente controllato e più confortevole per lo studente.
Sperimentazione delle tecniche apprese in Python, usando specifiche librerie per l'analisi di dati.
Modalità di verifica apprendimento
La prova finale di compone di un esame orale (al momento dell'appello), una presentazione di un articolo e un piccolo progetto pratico. La valutazione sarà attribuita secondo il seguente schema: 25% progetto e relazione, 25% presentazione di un articolo, 50% esame orale.
Nel progetto e nella relazione verrà valutata la capacità di applicare le conoscenze acquisite per la risoluzione di problemi nuovi e la consapevolezza delle scelte implementate. Nella presentazione verrà valutata la capacità di comprensione di algoritmi nuovi e la chiarezza e precisione dell'esposizione. Per accedere alla prova orale è necessario avere una valutazione positiva al progetto, alla relazione e alla presentazione.
Nella prova orale verrà valutata la conoscenza degli argomenti presentati a lezione, l'acquisizione del linguaggio tecnico adeguato al contesto, la capacità di mettere in relazione fra loro argomenti diversi del programma, la comprensione del funzionamento degli algoritmi visti a lezione, la capacità e la velocità nel progettare soluzioni efficienti per problemi nuovi.
Programma del corso
Review su Analisi degli Algoritmi
Python Review
Strutture dati di base in Python
Introduzione al Modulo Python Pandas e Visualizzazione dei dati
Grafi: algoritmi di visita e calcolo delle distanze
Introduzione al modulo Python NetworkX
Algoritmi per l'analisi dello small-world in reti: diametro, distanza media, e distribuzione delle distanze
Conteggio probabilistico
Algoritmi di community detection
Algoritmi per il calcolo delle centralità