Algoritmi e complessità
Indice
- Avvisi
- Orario
- Link per seguire le lezioni da remoto
- Appelli
- Programma del corso
- Modalità d'esame
- Ricevimento studenti
Avvisi
- Lezioni del 24-26/11. Sono stato segnalato come contatto di primo livello di un caso di positività al COVID-19. Le lezioni del 24-26/11 si svolgeranno on-line; riprenderemo le lezioni in presenza dal 1/12.
Orario
Le lezioni si svolgeranno con il seguente orario:
- mercoledì ore 10:30-12:30 (aula Epsilon, via Celoria 18)
- venerdì ore 10:30-12:30 (aula 210, Settore didattico).
Link per seguire le lezioni da remoto
Gli studenti che devono seguire da le lezioni di teoria da remoto sono pregati di autenticarsi usando il loro account Teams d'Ateneo e di collegarsi a questo link. Ricordiamo che lo scopo della trasmissione in streaming è di favorire "[...] la partecipazione degli studenti con particolari fragilità o che risultino immunodepressi, degli studenti non ancora in possesso della certificazione verde covid-19 nonché degli studenti internazionali che in presenza di limitazioni agli spostamenti determinati dall'emergenza epidemiologica tuttora in corso sarebbero impossibilitati a garantire la presenza in aula" (Decreto rettorale sulla didattica del 23 agosto). In tutti gli altri casi, è fortemente consigliata la presenza in aula.Appelli
L'esame si tiene su appuntamento e consiste in una prova orale. Per poterlo sostenere occorre contattare il docente con sufficiente anticipo.
| Data | |
|---|---|
| Gennaio 2022 (*) | |
| Gennaio 2022 | |
| Febbraio 2022 | |
| Giugno 2022 | |
| Luglio 2022 | |
| Settembre 2022 |
L'appello di Gennaio indicato con (*) è riservato agli studenti degli A/A precedenti.
Programma di massima del corso di Programmazione
Il corso di Algoritmi e complessità è un corso di 6 crediti che costituisce una naturale prosecuzione di un corso di algoritmi di base. L'obiettivo è quello di fornire allo studente una conoscenza di algoritmi avanzati, che richiedono tecniche di progettazione sofisticate e un diverso approccio all'analisi. In particolare, il corso si concentrerà su algoritmi di approssimazione, algoritmi probabilistici e strutture succinte.
Contenuti del corso
Il programma di massima del corso è il seguente:
Programma
Algoritmi di approssimazione
- Classi NPO, APX, PTAS, FPTAS
- Tecniche greedy
- Problema del bilanciamento del carico (load balancing) [A]
- Problema della selezione dei centri (center selection) [A]
- Inapprossimabilità del problema della selezione dei centri [C]
- Problema della copertura di insiemi (set cover) [A]
- Tecnica di pricing
- Problema della copertura di vertici (vertex cover) [A]
- Problema dei cammini disgiunti (disjoint paths) [A]
- Tecniche basate sull'arrotondamento
- Problema della copertura di vertici mediante arrotondamento [A]
- Altri esempi
- Algoritmo di Christofides per il TSP metrico [B]
- Inapprossimabilità del TSP [D.6]
- Schemi di approssimazione in tempo polinomiale e pienamente polinomiale
- Un PTAS (basato sulla soluzione esaustiva ridotta) per il problema della partizione minima (minimum partition) [G]
- Un FPTAS (basato sull'arrotondamento) per il problema dello zaino (knapsack) [C]
Algoritmi probabilistici
- L'algoritmo di Karger per il problema del taglio minimo globale (minimum global cut) [E]
L'algoritmo di Miller-Rabin per la primalità (senza dimostrazione) [H]- Un algoritmo basato sull'arrotondamento aleatorio per la copertura di insiemi [D.4]
- Un algoritmo randomizzato per MaxEkSat e la sua derandomizzazione [D.3]
Teoria della complessità di approssimazione
- Teorema PCP (senza dimostrazione) [F.3, Teorema 1]
- PCP e inapprossimabilità di MaxSat e MaxE3Sat [F.3.1]
- PCP e inapprossimabilità del problema dell'insieme indipendente (independent set) [F.4.4, Claim 13 e Claim 14]
Strutture succinte, quasi-succinte e compatte
- Strutture succinte per rango e selezione; il "Four-Russians Trick" [D.9, escluso 9.2]
- Strutture succinte per alberi binari [D.10]
- Codifica quasi-succinta di Elias-Fano per sequenze monotone [D.11, esclusi D.11.1 e D.11.2]
- Struttura compatta per le parentesi bilanciate [D.12]
- Funzioni quasi-succinte: la tecnica MWHC [D.13]
Hash minimali perfetti [D.13]
Riferimenti bibliografici
Note di lezione
Rendo pubblici gli appunti che ho scritto durante le lezioni. Queste note sono finalizzate solamente a consentire agli studenti frequentanti di completare i loro appunti; non hanno ovviamente alcun significato se estrapolati dal contesto della lezione.
Modalità d'esame
L'esame consiste in una prova orale.
Ricevimento studenti
Il docente riceve nel suo studio di via Celoria 18 (quinto piano) o in via telematica, in ogni caso su appuntamento. Un appuntamento può essere fissato inviando una e-mail al docente e attendendo una risposta di conferma.