Computer Science - Informatica

FLAVIO CHIERICHETTI

Obiettivi generali:
Questo corso propone lo studio di algoritmi evoluti e di strutture dati avanzate per risolvere problemi complessi.

Obiettivi specifici:
Applicare conoscenza e comprensione:
Al termine del corso lo studente avrà gli strumenti per individuare il nucleo matematico del problema da affrontare, e per identificare la tecnica più appropriata per la soluzione dello stesso.

Capacità critiche e di giudizio
Gli studenti saranno in grado di determinare quali approcci siano più adatti per risolvere problemi algoritmici.

Capacità comunicative:
Lo studente sarà in grado di presentare idee algoritmiche, e di spiegare le caratteristiche dei problema da risolvere.

Capacità di apprendimento:
Lo studente avrà acquisito la capacità di pensare in modo algoritmico.

1: Conoscenza e comprensione
Gli studenti dimostrano una conoscenza e una comprensione approfondite dei principali concetti, algoritmi e strutture dati utilizzati nell'analisi e nella progettazione degli algoritmi avanzati. Essi sono in grado di spiegare i concetti di base e le strategie di progettazione degli algoritmi.

2: Capacità di applicare conoscenze e comprensione
Gli studenti dimostrano la capacità di applicare le loro conoscenze e comprensione per risolvere una vasta gamma di problemi algoritmici complessi. Sono in grado di selezionare e adattare gli algoritmi appropriati per affrontare specifiche sfide computazionali, valutando la loro efficacia e comprensione dei trade-off coinvolti nelle scelte algoritmiche.

3: Capacità critica e di giudizio
Gli studenti dimostrano una capacità avanzata di valutare criticamente gli algoritmi esistenti, analizzando le loro prestazioni in termini di complessità computazionale, tempo di esecuzione, spazio di memoria e scalabilità. Sono in grado di identificare e comprendere le proprietà fondamentali degli algoritmi, come la correttezza e l'ottimalità, nonché di valutare la loro adattabilità a contesti specifici. Saranno svolte discussioni in aula per sviluppare queste capacità.

4: Capacità di comunicare
Gli studenti dimostrano la capacità di valutare in modo critico le soluzioni algoritmiche esistenti, sintetizzando idee e concetti provenienti da fonti diverse per sviluppare nuove strategie e approcci innovativi per risolvere problemi complessi. Inoltre, sono in grado di comunicare in modo chiaro e convincente le loro idee e scoperte agli altri, dimostrando una comprensione approfondita dei concetti algoritmici avanzati. Saranno svolte discussioni in aula per sviluppare questa capacità.

5: Capacità di apprendere
Gli studenti dimostrano una capacità avanzata di apprendimento autonomo e di riflessione critica sul proprio apprendimento nel campo degli algoritmi avanzati. Sono in grado di individuare lacune nella propria comprensione, di identificare aree di interesse e di approfondire la propria conoscenza attraverso la ricerca indipendente e l'esplorazione di nuovi sviluppi nel campo.

Gli studenti dovranno essere in grado di comprendere dimostrazioni matematiche, ed avere conoscenze base di algoritmica, probabilità e combinatoria.

Il corso presenterà tecniche algoritmiche avanzate.

Algoritmi di Ottimizzazione:
- algoritmi basati su tecnica greedy (10 ore)
- algoritmi basati su LP (10 ore)
- algoritmi basati su SDP (5 ore)
- Ottimizzazione Submodulare (5 ore)
Algoritmi per la risoluzione di problemi su grandi quantità di dati:
- analisi di Grafi (5 ore)
- Clustering (10 ore)
- LSH (5 ore)
- algoritmi online (10 ore)

Algorithm Design (Kleinberg / Tardos).

Vi saranno lezioni in presenza.

La presenza non è obbligatoria, ma è fortemente consigliata.

Ad ogni esame vi sarà una prova scritta (con domande aperte e chiuse), della durata di circa 2 ore, sugli argomenti svolti nel corso.

Si determini l'integrality gap del rilassamento lineare classico di Vertex Cover.