Materiale¶
La dispensa e l'eserciziario in PDF, con la stessa numerazione di definizioni, teoremi, esempi ed esercizi del sito, le slide dei capitoli e i notebook Colab con il codice degli algoritmi. Testo e figure sono rilasciati con licenza CC BY 4.0, il codice con licenza MIT.
Dispensa ed eserciziario¶
| Volume | Contenuto | Capitoli | File |
|---|---|---|---|
| Dispensa | Algoritmi di approssimazione: rapporti di prestazione e schemi di approssimazione, con algoritmi e analisi del caso peggiore per lo zaino, il bin packing, il TSP metrico e lo scheduling su macchine parallele, e i limiti dell'approssimazione per la colorazione dei vertici, la clique massima e il TSP generale. | 1–7 | PDF (1.1 MB) |
| Eserciziario | Esercizi svolti sui capitoli del volume 1, algoritmi di approssimazione: ogni esercizio è seguito dalla sua soluzione completa. | 1–7 | PDF (0.7 MB) |
Slide¶
Le slide delle lezioni, un PDF per capitolo, con le stesse definizioni ed esempi della dispensa.
| Capitolo | Titolo | File |
|---|---|---|
| 1 | Principi degli algoritmi di approssimazione | PDF (0.4 MB) |
| 2 | Algoritmi di approssimazione per lo zaino (1/2) | PDF (0.6 MB) |
| 2 | Algoritmi di approssimazione per lo zaino (2/2) | PDF (0.6 MB) |
| 3 | Algoritmi di approssimazione per il bin packing | PDF (0.6 MB) |
| 4 | Colorazione dei vertici: limiti dell'approssimazione | PDF (0.4 MB) |
| 5 | Clique massima: limiti dell'approssimazione | PDF (0.3 MB) |
| 6 | TSP: il caso generale e il caso metrico | PDF (0.5 MB) |
| 7 | Approssimazione per \(P\|C_{\max}\) | PDF (0.4 MB) |
Notebook Colab¶
Il codice degli algoritmi, un notebook per capitolo e per linguaggio, da eseguire in Google Colab o da scaricare (link .ipynb). Come si usano: la pagina dei notebook.
| Capitolo | Python | C++ |
|---|---|---|
| 2. Algoritmi di approssimazione per lo zaino | ||
| 3. Algoritmi di approssimazione per il bin packing |
Banca delle domande del quiz¶
Tutte le domande dell'autovalutazione, divise per parte e capitolo, con la risposta corretta e la spiegazione; per le domande generate, che cambiano i numeri a ogni avvio, alcuni esempi.