DALMINE
Dati Generali
Periodo di attività
Syllabus
Obiettivi Formativi
L'obiettivo del corso è studiare ed imparare a risolvere problemi algoritmici che si trovano tipicamente in competizioni di programmazione. Particolare attenzione viene dedicata a come utilizzare algoritmi fondamentali, strutture dati, e approcci tipici (patterns) per produrre soluzioni con bassa complessità computazionale. Al termine del corso lo studente sarà in grado di applicare le conoscenze acquisite anche al di fuori dello specifico ambito delle competizioni di programmazione, e sarà in grado di implementare delle soluzioni che performano bene anche nel caso problemi caratterizzati da input di grandi dimensioni.
Prerequisiti
Non ci sono prerequisiti formali. Il corso assume che lo studente abbia familiarità con la programmazione e la notazione asintotica.
Metodi didattici
Lezioni con approfondimenti teorici abbinate a sessioni di programmazione interattiva ed esercizi di laboratorio. Il docente esporrà allo studente un problema algoritmico, spiegherà come risolvere in modo efficiente il problema, infine implementerà una soluzione in modo interattivo.
Una copia di tutto il materiale utilizzato dal docente sarà disponibile sulla piattaforma e-learning dell'università.
Verifica Apprendimento
Esame scritto e progetto obbligatorio.
L'esame scritto è strutturato in 2/3 esercizi che coprono i primi 6 moduli del programma. L'obiettivo dell'esame è verificare che lo studente abbia appreso gli algoritmi ed i concetti spiegati durante il corso. E' consuetudine che compaia un esercizio che richiede di implementare un algoritmo studiato in classe ed un esercizio stile coding interview dove viene valutata la capacità di applicare le nozioni apprese durante il corso al fine di risolvere un problema applicativo. Il tempo disponibile è di solito di 1.5 o 2 ore.
Il progetto obbligatorio è focalizzato sulla valutazione dei moduli di programmazione evolutiva ed algoritmi di ricerca.
I punteggi ottenuti nell'esame scritto e nel progetto contribuiscono entrambi alla definizione del voto finale (in misura proporzionale al numero di ore dedicate ai moduli).
Contenuti
Il corso è strutturato in unità.
- Introduzione alle coding competitions. Lo studente verrà introdotto alla programmazione competitiva. Lo studente ripasserà il concetto di complessità computazionale (tempo e spazio), che viene utilizzato per determinare la qualità di una soluzione. Lo studente ripasserà la notazione asintotica.
- Scelta del linguaggio di programmazione. Lo studente comprenderà i vantaggi e gli svantaggi legati all'uso di diversi linguaggi di programmazione nel dominio delle competizioni di programmazione. Lo studente ripasserà le fondamenti della programmazione in Python. Problemi specifici verranno utilizzati per studiare le differenze tra array, lista, e hashmap. Analisi e valutazione del dynamic resizing.
- Ordinamento. Lo studente implementerà i principali approcci per ordinare numeri. Lo studente comprenderà le proprietà associate ad ogni metodo di ordinamento. Inoltre, lo studente imparerà a utilizzare in modo combinato (e.g., approccio ibrido) i diversi metodi di ordinamento, con l'obiettivo di migliorare l'efficienza in caso di limitazioni legate all'hardware (e.g., limitata quantità di memoria).
- Strutture dati. Lo studente studierà ed implementerà le strutture dati fondamentali quali Pila, Coda (anche con priorità), Heap, Albero Binario (eventualmente con auto-bilanciamento), Grafo, LRU Cache, Trie, Union-Find, Segment Tree, Sparse Table. Una selezione di coding questions sarà usata per mettere in risalto il vantaggio che si può trarre dall'uso di ciascuna struttura.
- Programmazione dinamica e ricorsione. Lo studente studierà come utilizzare la programmazione dinamica e la ricorsione per risolvere problemi algoritmici. Lo studente studierà anche le problematiche associate a ciascuno dei due approcci.
- Soluzione di problemi per categoria. Lo studente studierà e risolverà una selezione di problemi da categorie comuni. Per la categoria string ad esempio, lo studente apprenderà come cercare prefissi in modo efficiente.
- Programmazione evolutiva e genetica. Lo studente studierà i principi e i concetti comuni alla computazione evolutiva. Si studierà in dettaglio la programmazione evolutiva (concetti come popolazione, mutazioni, selezione) e la programmazione genetica (concetti come genotipo, crossover, fitness).
- Algoritmi di ricerca. Lo studente sarà introdotto all'utilizzo di algoritmi di ricerca, con un focus su tecniche di base e avanzate (metaeuristiche), per lo sviluppo di soluzioni software efficienti in diversi contesti applicativi.