Algoritmo online

In informatica, con la locuzione algoritmo online si intende un algoritmo, per la risoluzione di un problema, che deve fornire dei risultati pur mancando, inizialmente, alcuni dei dati in ingresso.

Più precisamente, l'algoritmo riceve in ingresso una sequenza σ di input per ogni termine della quale fornisce un risultato, basandosi solo sui dati ricevuti fino a quell'istante.

A questa tipologia si contrappone la definizione di algoritmo offline che designa i classici algoritmi, i quali conoscono tutti i dati d'ingresso fin dall'inizio dell'elaborazione, ovvero tutti i termini della sequenza σ.

Competitività

Mancando alcuni dati di ingresso, il costo della strategia offerta da un'algoritmo online sarà superiore rispetto a quello che un algoritmo offline può offrire. Lo studio dell'efficienza di questo tipo di algoritmi è limitato dal fatto che, in genere, non si conosce la distribuzione di probabilità dei possibili input che si possono verificare.

Per lo studio di questo tipo di algoritmi si applica quindi la cosiddetta analisi competitiva^[1], che consiste nel rapportare il costo dell'algoritmo online al costo dell'algoritmo offline ottimo per la risoluzione del medesimo problema.

L'analisi competitiva permette di valutare un parametro detto α-competitività (o c-competitività) di un algoritmo online. Dato un algoritmo online A, il cui costo è C_A ed un algoritmo offline ottimo OPT il cui costo è C_OPT, esso è α-competitivo se per ogni possibile sequenza di input σ si ha:

${\displaystyle C_{A}(\sigma )\leq \alpha \cdot C_{OPT}(\sigma )+c}$ 

Dove α è una costante e valori più bassi di α indicano un algoritmo più competitivo. La presenza della costante c, che in alcuni casi è nulla, riduce la competitività dell'algoritmo.

Note

1. ^ D. Sleator e R. E. Tarjan. Amortized efficiency of list update and paging rules, Communications of the ACM, 1985, 28, 202-208.

Voci correlate

• Algoritmo
• Analisi competitiva