Algoritmo online: differenze tra le versioni

Versione delle 23:19, 18 set 2007

Versione attuale delle 20:08, 8 apr 2022

(24 versioni intermedie di 17 utenti non mostrate)

Riga 1:

{{S|programmazione}}

In [[informatica]], con la locuzione '''algoritmo online''' si intende un [[algoritmo]], per la risoluzione di un [[problema]], che devono fornire dei risultati pur mancando, inizialmente, parte dei dati in ingresso.

In [[informatica]], con la locuzione '''algoritmo online''' si intende un [[algoritmo]], per la risoluzione di un [[problema]], che devonodeve fornire dei risultati pur mancandonon avendo a disposizione, inizialmente, partealcuni dei dati in ingresso.

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

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

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

A questa tipologia di algoritmo, si contrappone la definizione di ''algoritmo offline'' perche descriveredesigna i classici algoritmi, i quali conosconopossiedono tutti i dati d'ingresso allfin dall'inizio dell'elaborazione, ovvero tuttitutta i termini 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à}}

{{portale|informatica}}

[[Categoria:Algoritmi|onlineOnline, algoritmo]]