Algoritmo online

Da Wikipedia, l'enciclopedia libera.

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à[modifica | modifica wikitesto]

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 è CA ed un algoritmo offline ottimo OPT il cui costo è COPT, l'algoritmo A è α-competitivo se per ogni possibile sequenza di input σ si ha:

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[modifica | modifica wikitesto]

  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[modifica | modifica wikitesto]

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