Algoritm online

Această intrare pe tema programării este doar o schiță . Contribuiți la îmbunătățirea acestuia în conformitate cu convențiile Wikipedia .

În informatică , termenul algoritm online înseamnă un algoritm , pentru rezolvarea unei probleme , care trebuie să ofere rezultate, deși inițial unele dintre datele de intrare nu sunt disponibile.

Mai precis, algoritmul primește ca intrare o secvență generică σ de intrări din care, pentru fiecare termen σ _i , trebuie să ofere un răspuns sau să ia o decizie, bazându-se doar pe intrările primite până la acel moment, σ _j cu j ≤ i .

Această tipologie contrastează cu definiția algoritmului offline care desemnează algoritmii clasici, care au toate datele de intrare de la începutul procesării, adică întreaga secvență σ.

Competitivitate

În lipsa unor date de intrare, costul strategiei oferite de un algoritm online va fi mai mare decât ceea ce poate oferi un algoritm offline. Studiul eficienței acestui tip de algoritm este limitat de faptul că, în general, distribuția probabilității posibilelor intrări nu este cunoscută.

Pentru studiul acestui tip de algoritm, se folosește, prin urmare, o tehnică numită analiză competitivă ^[1] , care constă în raportarea costului algoritmului online cu costul algoritmului offline optim care rezolvă aceeași problemă, cunoscând toate intrările din începutul.

Analiza competitivă permite evaluarea unui parametru numit α-competitivitate (sau c-competitivitate) a unui algoritm online. Având în vedere un algoritm online A, al cărui cost este C _A și un algoritm OPT offline optim al cărui cost este C _OPT , algoritmul A este α-competitiv dacă pentru fiecare posibilă secvență de intrare σ avem:

${\displaystyle {\mathrm{<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">C.</span></span>}}_{\mathrm{<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">LA</span></span>}}<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">(</span></span>\mathrm{<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">\sigma </span></span>}<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">)</span></span><span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">\le </span></span>\mathrm{<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">\alpha </span></span>}<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">\cdot </span></span>{\mathrm{<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">C.</span></span>}}_{\mathrm{<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">SAU</span></span>}\mathrm{<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">P.</span></span>}\mathrm{<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">T.</span></span>}}<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">(</span></span>\mathrm{<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">\sigma </span></span>}<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">)</span></span><span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">+</span></span>\mathrm{<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">c</span></span>}}${\ displaystyle C_ {A} (\ sigma) \ leq \ alpha \ cdot C_ {OPT} (\ sigma) + c}

În cazul în care α și c sunt constante independente unele de altele, deoarece acestea cresc competitivitatea algoritmului scade. În definiția clasică a competitivității α, constanta c este absentă (adică are o valoare nulă), dar introducerea ei este necesară în diverse contexte.

Notă

Elemente conexe

• Algoritm
• Analiza competitivă

Portal IT : accesați intrările Wikipedia care se ocupă cu IT