Algoritmo online

Questa voce sull'argomento programmazione è solo un abbozzo.

Contribuisci a migliorarla secondo le convenzioni di Wikipedia.

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

Più precisamente, l'algoritmo riceve in ingresso una generica sequenza σ di input di cui, per ogni termine σ_i, deve fornire una risposta o prendere una decisione, basandosi solo sugli input ricevuti fino a tale istante, σ_j con j ≤ i.

A questa tipologia si contrappone la definizione di algoritmo offline che designa i classici algoritmi, i quali possiedono tutti i dati d'ingresso fin dall'inizio dell'elaborazione, ovvero tutta la 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 avere.

Per lo studio di questo tipo di algoritmi si utilizza quindi una tecnica detta analisi competitiva^[1], che consiste nel rapportare il costo dell'algoritmo online al costo dell'algoritmo offline ottimo che risolve il medesimo problema conoscendo tutti gli input sin dall'inizio.

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, l'algoritmo A è α-competitivo se per ogni possibile sequenza di input σ si ha:

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

Dove α e c sono costanti tra loro indipendenti all'aumentare delle quali diminuisce la competitività dell'algoritmo. Nella definizione classica di α-competitività la costante c è assente (ovvero ha valore nullo), la sua introduzione si rende però necessaria in vari contesti.

Note

Voci correlate

• Algoritmo
• Analisi competitiva

Portale Informatica: accedi alle voci di Wikipedia che trattano di informatica