Algoritmo online: differenze tra le versioni

Versione delle 23:23, 18 set 2007

Versione attuale delle 20:08, 8 apr 2022

(22 versioni intermedie di 17 utenti non mostrate)

Riga 1:

{{S|informaticaprogrammazione}}

In [[informatica]], con la locuzione '''algoritmo online''' si intende un [[algoritmo]], per la risoluzione di un [[problema]], che deve fornire dei risultati pur mancandonon 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 dellaσ_i, qualedeve forniscefornire ununa risultatorisposta o prendere una decisione, basandosi solo suisugli datiinput ricevuti fino a quell'tale istante, σ_j con j ≤ i.

A questa tipologia si contrappone la definizione di ''algoritmo offline'' che designa i classici algoritmi, i quali conosconopossiedono tutti i dati d'ingresso fin dall'inizio dell'elaborazione, ovvero tutti i terminitutta dellala 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 [[variabile casuale|distribuzione di probabilità]] dei possibili input che si possono verificareavere.

Per lo studio di questo tipo di algoritmi si applicautilizza quindi launa cosiddettatecnica 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 perche larisolve risoluzione delil 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, essol'algoritmo A è α-competitivo se per ogni possibile sequenza di input σ si ha:

<math>C_A(\sigma) \leq \alpha \cdot C_{OPT}(\sigma) + c</math>

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.

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 ==

{{<references}} />

== Voci correlate ==

* [[Algoritmo]]

* [[Analisi competitiva]]

{{Controllo di autorità}}

[[Categoria:Algoritmi|online, algoritmo]]

{{portale|informatica}}

[[Categoria:Algoritmi|onlineOnline, algoritmo]]