Teoretyczne informatyka dynamic-algorithms

2

Czy istnieje naturalny równoległy analog do czerwono-czarnych drzew o podobnych lub nawet niezbyt gorszych właściwościach do aktualizacji, przy jednoczesnym zapewnieniu odpowiedniej wydajności pracy? Mówiąc bardziej ogólnie, co możemy zrobić dla wyszukiwania równoległego z aktualizacjami?

24 ds.algorithms ds.data-structures dc.parallel-comp concurrency dynamic-algorithms

1

Jaki jest najszybszy algorytm deterministyczny dla dynamicznej osiągalności digrafu bez usuwania krawędzi?

Jaki jest najlepszy wynik deterministyczny dla utrzymania dynamicznego zamknięcia przechodniego na ukierunkowanym wykresie z tylko wstawieniem krawędzi? Przeczytałem kilka artykułów na temat problemu dynamicznego zamykania przechodniego zarówno przy wstawianiu, jak i usuwaniu krawędzi. Czy są jednak lepsze algorytmy z tylko wstawianiem krawędzi?

16 ds.algorithms graph-theory graph-algorithms dynamic-algorithms

2

Złożoność przestrzeni w celu obliczenia optymalnego wyrównania łańcucha dla odległości edycji Levenshteina

Jeśli otrzymamy dwa ciągi o rozmiarze n1n1n_1 i , standardowe obliczanie odległości edycji Levenshteina odbywa się za pomocą algorytmu dynamicznego o złożoności czasowej i złożoności przestrzennej . (Niektóre ulepszenia można wprowadzić w zależności od odległości edycji , ale nie zakładamy, że jest szczególnie mały.) Jeśli interesuje Cię tylko wartość odległości …

12 cc.complexity-theory dynamic-algorithms edit-distance space-time-tradeoff

2

Utrzymanie wartości wielomianu nad dynamicznie aktualizowanym wejściem

Niech będzie wielomianem nad ustalonym skończonym polem. Załóżmy, że podano nam wartość w pewnym wektorze i wektorze .P.( x1, x2), … , Xn)P.(x1,x2),…,xn)P(x_1, x_2, \ldots, x_n)P.P.Py∈ { 0 , 1 }ny∈{0,1}ny \in \{0,1\}^nyyy Teraz chcemy obliczyć wartość na wektorze taki sposób, że i różnią się dokładnie w jednej pozycji (innymi …

10 polynomials dynamic-algorithms

1

Czy równania różniczkowe można zaklasyfikować do własnych klas złożoności?

Problemy zostały sklasyfikowane jako całość dzięki złożoności obliczeniowej. Ale czy w równaniach różniczkowych można klasyfikować równania różniczkowe w zależności od ich struktury obliczeniowej? Na przykład, jeśli równanie niejednorodne pierwszego rzędu jest stosunkowo trudne do rozwiązania niż, powiedzmy, równanie jednorodne 100 rzędu, czy można je zaklasyfikować jako osobne klasy wypukłości, biorąc …

10 cc.complexity-theory complexity-classes computability dynamic-algorithms

Pytania otagowane jako dynamic-algorithms