Algoritmi di approssimazione¶
Un corso della collana Ricerca Operativa e Matematica · tutti i corsi
Materiale didattico ideato e sviluppato da Fabio Furini, professore associato al DIAG, Sapienza Università di Roma.
Le dispense del corso, online: che cosa garantisce un algoritmo di approssimazione e come lo si dimostra; algoritmi, analisi del caso peggiore e istanze tight per lo zaino, il bin packing, il TSP metrico e lo scheduling su macchine parallele; schemi di approssimazione; i limiti dell'approssimazione per la colorazione dei vertici, la clique massima e il TSP generale. Con definizioni, risultati con dimostrazione, esempi svolti, esercizi con le soluzioni, notebook Colab e app interattive.
Prerequisiti: Problemi di ottimizzazione combinatoria per i problemi e Algoritmi euristici per gli algoritmi che qui si analizzano (greedy, First Fit, LPT, nearest neighbour…).
Provalo subito¶
L'algoritmo di Christofides su dieci città: il giro trovato sopra il giro ottimo, con il rapporto che resta sotto la garanzia 3/2. Premi «Esegui» per rivedere albero ricoprente minimo, accoppiamento, circuito euleriano e scorciatoie, oppure passa al double tree.
Le parti del corso¶
I capitoli, per famiglia di problemi come nel menu: ogni scheda dice il capitolo della dispensa.
-
1. Principi degli algoritmi di approssimazione
Principi
Algoritmi di approssimazione · Schemi di approssimazione
-
2. Algoritmi di approssimazione per lo zaino
Problemi di zaino
Notazione · Oggetto critico e capacità residua · L'algoritmo greedy · L'algoritmo Ext-Greedy
-
3. Algoritmi di approssimazione per il bin packing
Problemi di packing
Notazione · Next Fit · La classe Any Fit · Proprietà di riempimento a metà
-
4. Colorazione dei vertici: limiti dell'approssimazione
Problemi di colorazione
Notazione · Il VCP non è approssimabile · Casi particolari · Esempi
-
5. Clique massima: limiti dell'approssimazione
Problemi di clique
Notazione · Il MCP non è approssimabile · Casi particolari · Esempio
-
6. TSP: il caso generale e il caso metrico
Problemi di routing
Il TSP generale non è approssimabile · Un caso particolare: il TSP metrico · L'algoritmo del doppio albero e l'algoritmo di Christofides · Proprietà strutturali
-
7. Approssimazione per P||Cmax
Problemi di scheduling
Notazione · Gli algoritmi \(LIST\) e \(LPT\) · Una proprietà del list scheduling · Garanzie di prestazione
Da non perdere¶
-
Esercizi con le soluzioni
Esercizi per ogni capitolo, ciascuno con la soluzione svolta che si apre con un clic.
-
Quiz di autovalutazione
Un facsimile d'esame nuovo a ogni avvio: 13 domande, 33 punti, con la soluzione e il link alle dispense. In Materiale c'è anche la banca completa delle domande.
-
Laboratorio interattivo
App che girano nel browser: muovi i parametri e guarda le idee del corso lavorare, un passo alla volta.
-
Dispense in PDF
Dispense, eserciziari e slide in PDF, con la stessa numerazione del sito.
-
Notebook in Colab
Il codice del corso che gira nel browser, senza installare niente.
-
Indice completo
Tutti i capitoli con le loro sezioni in una pagina, e come è fatto ogni capitolo.
La collana¶
Tutti i corsi della collana hanno la stessa impostazione: dispense online e in PDF, esercizi con le soluzioni, laboratorio interattivo e quiz di autovalutazione.
-
numeri reali, funzioni, limiti, derivate e serie, con i grafici interattivi
-
vettori, matrici, determinanti, sistemi lineari e autovalori, con il laboratorio di calcolo
-
rappresentazione dei numeri, pseudocodice, ordinamento e ricerca, analisi e algoritmi ricorsivi
-
poliedri, algoritmo del simplesso, dualità e simplesso duale, con il laboratorio interattivo
-
rilassamento continuo, disuguaglianze valide, piani di taglio, branch-and-bound e branch-and-cut
-
insiemi e funzioni convesse, problemi di ottimizzazione convessa, con grafici interattivi
-
grafi, alberi ricoprenti, cammini minimi, flussi su reti, simplesso su reti e gestione dei progetti
-
Problemi di ottimizzazione combinatoria
zaino, bin packing, colorazione, TSP, scheduling e lot sizing: i problemi, le formulazioni e gli algoritmi ad hoc
-
principi e algoritmi di PD per zaino, lot sizing, cambio monete e taglio delle aste
-
euristiche costruttive, ricerca locale, metaeuristiche ed euristiche MIP per i problemi di ottimizzazione combinatoria
-
Algoritmi di approssimazione · questo corso
garanzie di prestazione, schemi di approssimazione e limiti dell'approssimazione per i problemi combinatori
-
modelli di programmazione lineare per problemi gestionali, risolti con Python e Gurobi
-
modelli di programmazione non lineare, dal portafoglio al machine learning, con Python e Gurobi
-
modelli di programmazione lineare a variabili intere, dalla formulazione alla soluzione con i solver
Materiale didattico di Fabio Furini — DIAG, Sapienza Università di Roma.
Questo sito è disponibile anche in inglese.