Algoritmi e complessità
Indice
- Avvisi
- Telegram
- Orario
- Link per seguire le lezioni da remoto
- Appelli
- Programma del corso
- Modalità d'esame
- Ricevimento studenti
Avvisi
- Lezioni. La lezione di venerdì 2/12/2022 è sospesa.
Telegram
- Canale telegram. Il corso ha un canale telegram a cui gli studenti sono invitati a iscriversi, e che verrà utilizzato per le comunicazioni urgenti.
Orario
Le lezioni si svolgeranno con il seguente orario:
- mercoledì ore 10:30-12:30, aula Montanari (Chimica, mappa)
- venerdì ore 10:30-12:30, aula V9 (via Venezian, 21)
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 2023 (*) | |
| Gennaio 2023 | |
| Febbraio 2023 | |
| Giugno 2023 | |
| Luglio 2023 | |
| Settembre 2023 |
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.
Inoltre, ecco:
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.