Algoritmo online: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
m Bot: Aggiungo controllo di autorità (ref) |
|||
| (11 versioni intermedie di 8 utenti non mostrate) | |||
Riga 1:
{{S|
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.
Riga 10:
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 [[variabile casuale|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''<ref>D. Sleator e R. E. Tarjan. ''Amortized efficiency of list update and paging rules'', ''Communications of the ACM'', 1985, 28, 202-208.</ref>, 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<sub>A</sub> ed un algoritmo offline ottimo OPT il cui costo è C<sub>OPT</sub>, l'algoritmo A è α-competitivo se per ogni possibile sequenza di input σ si ha:
<math>C_A(\sigma) \leq \alpha \cdot C_{OPT}(\sigma) + c</math>
Riga 22:
== Voci correlate ==
* [[Algoritmo]]
* [[Analisi competitiva]]
{{Controllo di autorità}}
{{portale|informatica}}
[[
| |||