Pytania otagowane jako online-algorithms

1
Języki rozpoznawane przez DFA wielkości wielomianowej
W przypadku ustalonego skończonego alfabetu język formalny L ponad Σ jest regularny, jeśli istnieje deterministyczny automat skończony (DFA) ponad ΣΣΣ\SigmaLL.LΣΣ\SigmaΣΣ\Sigma który akceptuje dokładnie .LL.L Interesują mnie języki, które są „prawie” regularne w tym sensie, że mogą być rozpoznawane przez rodziny automatów wielkości, które rosną tylko wielomianowo wraz z długością słowa. …
2
utrzymywanie zrównoważonego drzewa opinającego rosnącego niekierowanego wykresu
Poszukuję sposobów na utrzymanie względnie zrównoważonego drzewa opinającego wykresu, gdy dodam do niego nowe węzły / krawędzie. Mam nieukierunkowany wykres, który zaczyna się jako pojedynczy węzeł, „root”. Na każdym kroku dodaję do wykresu albo nowy węzeł i krawędź łączącą go z wykresem, albo tylko nową krawędź łączącą dwa stare węzły. …
2
Algorytm dla „k” najczęściej występujących liczb
Szukałem najbardziej wydajnego algorytmu (streaming?), Który mówi mi „k” najczęściej występujące elementy w strumieniu danych w dowolnym momencie. Ten post: Algorytmy strumienia danych „Dziel i rządź” zainteresowały mnie. Załóżmy na przykład, że istnieją liczby: (4,3,5,1,6,2,4,3,3,8,8,9,1) i szukam 3 najczęściej występujących liczb (powiedzmy), to powinienem otrzymaj (3,4,1) jako odpowiedź. Próbowałem szukać …
2
Czy istnieje algorytm do skutecznego utrzymywania informacji o połączeniach dla DAG w przypadku wstawiania / usuwania?
Biorąc pod uwagę ukierunkowany wykres acykliczny, G(V,E)G(V,E)G(V,E) , czy można skutecznie obsługiwać następujące operacje? : Określa, czy w G istnieje ścieżkaod węzła a do węzła bisConnected(G,a,b)isConnected(G,a,b)isConnected(G,a,b)GGGaaabbb : Dodaje krawędź od a do b na wykresie Glink(G,a,b)link(G,a,b)link(G,a,b)aaabbbGGG : Usuwa krawędź od a do b w Gunlink(G,a,b)unlink(G,a,b)unlink(G,a,b)aaabbbGGG : Dodaje wierzchołek do Gadd(G,a)add(G,a)add(G,a) …
3
Czy istnieje algorytm aproksymacji stałego współczynnika dla problemu kolorowania prostokąta 2D?
Problem, który rozważamy tutaj, to rozszerzenie znanego problemu kolorowania interwałów. Zamiast przedziałów uważamy prostokąty o bokach równoległych do osi. Celem jest pokolorowanie prostokątów przy użyciu minimalnej liczby kolorów, tak aby każdemu z dwóch nachodzących na siebie prostokątów przypisano różne kolory. Ten problem jest znany jako trudny dla NP. Xin Han, …
1
Czy wystarczy, aby ograniczenia programu liniowego były spełnione w oczekiwaniu?
W artykule Randomized Primal-Dual analiza RANKING dla Online Dwustronnego dopasowywania , udowadniając jednocześnie, że algorytm RANKING jest -konkurencyjne, autorzy pokazują, że dualność jest wykonalna w oczekiwaniu (patrz Lemat 3 na stronie 5). Moje pytanie brzmi:(1−1e)(1−1e)\left(1 - \frac{1}{e}\right) Czy wystarczy, aby ograniczenia programu liniowego były spełnione w oczekiwaniu? Jedną rzeczą jest …
2
Książki z algorytmami online
Czy są jakieś najnowsze książki na temat algorytmów online? Znam tylko dwie książki na ten temat. Obliczenia online i analiza konkurencji Allana Borodina i Ran El-Yaniv: Jest to klasyczna, ale stara książka i nie zawiera wielu najnowszych osiągnięć w tej dziedzinie. Projektowanie konkurencyjnych algorytmów online za pomocą podejścia pierwotnego podwójnego …
3
Czy istnieje algorytm online do śledzenia komponentów na zmieniającym się niekierowanym wykresie?
Problem Mam nieukierunkowany wykres (z wieloma krawędziami), który z czasem się zmieni, węzły i krawędzie można wstawiać i usuwać. Przy każdej modyfikacji wykresu muszę aktualizować połączone elementy tego wykresu. Nieruchomości Dodatkowe właściwości polegają na tym, że żadne dwa składniki nigdy nie zostaną ponownie połączone. Oczywiście wykres może mieć dowolne cykle …
4
Ciągłe grupowanie
Mam więc problem z klastrowaniem danych na żywo i ciągłego przesyłania strumieniowego. Ponieważ mam stale rosnący zestaw danych, nie jestem pewien, jaki jest najlepszy sposób na wydajne i wydajne tworzenie klastrów. Wymyśliłem kilka możliwych rozwiązań, w tym: Ustawienie limitu liczby punktów danych, które mają być dozwolone, a więc za każdym …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.