Algorytm online
Algorytm online to specyficzny typ algorytmu, który nie ma pełnej wiedzy o danych wejściowych na początku, lecz odbiera je w partiach (turach). Po każdej turze algorytm jest zobowiązany do przedstawienia częściowej odpowiedzi.
Problemy online
Problemy, które są rozwiązywane przez algorytmy online, określane są jako problemy online. Naturalnymi przykładami są zadania związane z przydziałem czasu lub pamięci procesora (scheduling), ponieważ zazwyczaj nie jest znane, jakie procesy będą wymagały zasobów w przyszłości. Dlatego konieczne jest przydzielanie ich wyłącznie na podstawie aktualnej sytuacji.
Przykłady zastosowania
Jednym z bardziej matematycznych przykładów jest kolorowanie grafu online, gdzie zaczynamy od pustego grafu, a w każdej turze dodajemy pojedynczy wierzchołek wraz z wszystkimi jego krawędziami. Celem algorytmu jest wybór koloru dla nowego wierzchołka w taki sposób, aby kolorowanie było akceptowalne i jednocześnie wykorzystać jak najmniejszą liczbę kolorów.
Algorytmy online obejmują również klasyczne algorytmy, które nie muszą przetwarzać całych danych wejściowych, lecz mogą działać na bieżąco. Przykładami takich algorytmów są algorytm KMP do dopasowywania wzorców oraz algorytm Ukkonena do konstrukcji drzewa sufiksowego.
Konkurencyjność
Oczywiście, gdybyśmy mieli pełne dane na początku, prawdopodobnie moglibyśmy znaleźć lepsze rozwiązanie danego problemu (na przykład bardziej efektywny przydział pamięci czy mniejszą liczbę użytych kolorów). Dlatego porównywanie wyników algorytmu online z optymalnym rozwiązaniem na tych samych danych wejściowych jest uzasadnione.
Jeśli dla każdego możliwego zestawu danych algorytm online generuje wynik, który jest co najwyżej c razy gorszy niż rozwiązanie optymalne, stwierdzamy, że algorytm jest c-konkurencyjny. Liczbę c nazywamy współczynnikiem konkurencyjności algorytmu.
Uogólnieniem tego pojęcia jest funkcja konkurencyjności: jest to funkcja f, która dla dowolnych danych wejściowych zapewnia wynik nie gorszy niż f(w), gdzie w jest wynikiem optymalnym.
