algorith that can process its input piece-by-piece in a serial fashion, i.e., in the order that the input is fed to the algorithm, without having the entire input available from the start
Algorytm online – szczególny rodzaj algorytmu, który nie zna danych wejściowych od początku w całości, lecz otrzymuje je w partiach (turach). Po każdej turze algorytm musi podać częściową odpowiedź. Problemy rozwiązywane przez algorytmy online nazywa się problemami online. Naturalnymi przykładami są przydział czasu lub pamięci procesora (scheduling) – ponieważ na ogół nie wiadomo, jakie procesy będą w przyszłości żądać zasobów, konieczne jest przydzielanie ich tylko na podstawie obecnej sytuacji. Bardziej matematycznym przykładem jest kolorowanie grafu online – startując od grafu pustego, w każdej turze dodaje się pojedynczy wierzchołek ze wszystkimi krawędziami. Zadaniem algorytmu jest wybrać dla niego kolor tak, aby kolorowanie było dopuszczalne i kolorów było możliwie najmniej. Algorytmami online nazywa się też te algorytmy klasyczne, które nie potrzebują czytać całych danych wejściowych, lecz mogą je przetwarzać na bieżąco. Takimi algorytmami są np. algorytm KMP dopasowania wzorca, czy algorytm Ukkonena konstrukcji drzewa sufiksowego.
Abstract from DBpedia / Wikipedia · CC BY-SA
via Wikidata sitelinks · CC0
Discovered by embedding cosine similarity (sentence-transformers MiniLM, 384-dim).