Questa pagina descrive il corso di dottorato “Algoritmi online: introduzione all’analisi teorica ed empirica“, tenuto dalle Profs. Ludovica Adacher e Gaia Nicosia.
Date
- mercoledì 26 maggio, 10:00-12:00
- giovedì 27 maggio, 10:00-12:00
- lunedì 7 giugno, 10:00-12:00
- martedì 8 giugno, 10:00-12:00
Codice Teams
plqgy5q
Abstract
Le tecniche classiche dell’ottimizzazione combinatoria forniscono un potente strumento per la risoluzione di problemi complessi che nascono da diverse applicazioni. Le tecniche tradizionali dell’ottimizzazione assumono, in generale, che la conoscenza dei dati di input sia completa. Tuttavia, esistono molti casi in cui devono essere prese delle decisioni in tempo reale, prima che un’informazione completa sull’input sia nota. Spesso, si deve produrre parte della soluzione del problema, non appena una “nuova parte di informazione” diventa nota. Questa situazione viene detta online e un algoritmo viene detto online se prende decisioni, ossia produce un output, senza la conoscenza completa dell’input. I problemi online nascono in contesti applicativi quali ad esempio l’allocazione e la gestione di risorse nei sistemi operativi, produttivi e logistici, la robotica, l’organizzazione dei dati, lo scheduling e i sistemi distribuiti.
Per misurare la qualità degli algoritmi online è possibile effettuare un’analisi del caso peggiore, detta analisi competitiva, che confronta la soluzione trovata dall’algoritmo online con la soluzione ottima trovata da un algoritmo che ha un’informazione completa sull’input. Questo tipo di analisi non è sempre applicabile e/o significativo. Vengono quindi introdotti alcuni problemi online rilevanti dal punto di vista applicativo per i quali sono presentate altre tecniche, spesso basate sulla simulazione, che consentono di valutare l’efficacia degli algoritmi proposti.