Teoretyczne informatyka ds.algorithms

1

Szukam referencji na temat złożoności problemu równoważenia formuł logicznych . W szczególności, Czy było wiadomo, że formuły logiczne można wyważyć w AC0AC0\mathsf{AC^0} ? Czy istnieje prosty dowód na to, że równoważenie boolowskiej formuły jest w AC0AC0\mathsf{AC^0} ? Przez „proste” mam na myśli dowód prostsze niż ten wspominam poniżej, w szczególności …

10 cc.complexity-theory ds.algorithms reference-request lo.logic boolean-formulas

1

Jaki jest asymptotycznie najszybszy znany algorytm obliczania pustej przestrzeni macierzy?

Wiem, że eliminacja Gaussa wymaga operacji arytmetycznych , ale nie jestem pewien, czy znane są lepsze algorytmy.O ( n3))O(n3))O(n^3)

10 ds.algorithms linear-algebra matrices

1

Jakie są wyniki algorytmów szacujących wielomiany dla danego zestawu punktów?

Wydaje się, że istnieje wiele randomizowanych algorytmów do testowania tożsamości wielomianowej, sprawdzających, czy dany wielomian ma wartość zero. Czy są jakieś wyniki algorytmów, które dokonują pewnego rodzaju oszacowania wielomianów w określonym zestawie punktów? Może to być na przykład przybliżenie, dla jakiej części tych punktów wielomian ocenia się na zero, lub …

10 ds.algorithms approximation-algorithms randomized-algorithms derandomization polynomials

2

Numeracja podzbiorów

Napraw . Dla każdego wystarczająco dużego chcielibyśmy oznaczyć wszystkie podzbiory wielkości dokładnie dodatnimi liczbami całkowitymi z . Chcielibyśmy, aby to etykietowanie spełniało następującą właściwość: istnieje zestaw liczb całkowitych , uln { 1 .. n } n / k { 1 ... T } S.k ≥ 5k≥5k\ge5nnn{ 1 .. n }{1 …

10 ds.algorithms graph-algorithms it.information-theory nt.number-theory exp-time-algorithms

1

Generowanie wykresów obwodu

Niech . Muszę wygenerować proste wykresy obwodu tak aby zestaw wszystkich motocykli tworzy podwójną osłonę (to znaczy, każda krawędź jest dzielona przez dokładnie dwa motocykle) i takie, że przecięcie dowolnych dwóch motocykle to albo wierzchołek, krawędź, albo pusty. Wygenerowane wykresy powinny być dowolnie duże.G g g G g gsol≥ 3g≥3g\geq …

10 ds.algorithms reference-request graph-theory co.combinatorics pseudorandom-generators

1

Algorytmy na wykresach reprezentowane za pomocą BDD

Najprostsze reprezentacje wykresów wykorzystują macierze / listy przyległości, co oznacza, że każdy węzeł i krawędź są wyraźnie reprezentowane. Znaczenie ukrytych reprezentacji dla wykresów wykazujących silne prawidłowości od dawna zostało uznane. Na przykład Galperin i Wigderson (1983), Papadimitriou i Yannakakis ( Nota o zwięzłych reprezentacjach grafów , 1986) badali kwestię wykresów, …

10 ds.algorithms reference-request graph-theory survey binary-decision-diagrams

1

Czym jest algorytm znajdujący minimalną osłonę wierzchołków na dwustronnym grafie z ważonymi wierzchołkami?

Wiem, że dla nieważonego grafu dwustronnego mogę znaleźć minimalną osłonę wierzchołków, najpierw znajdując maksymalne dopasowanie i przekształcając ją w osłonę wierzchołków za pomocą Twierdzenia Königa. Czy istnieje modyfikacja, której można by użyć, gdyby węzły były ważone?

10 ds.algorithms graph-theory

1

Problem decyzyjny rozkładu Hamiltona

Niech będzie wykresem niekierowanym. Rozkładem V na podzbiory rozłączne V i nazywa się Hamilton rozkładu z G jeśli subgraph wywołanych przez każdy zestaw V i jest albo wykres Hamiltona lub składa się z jednej krawędzi z | V i | = 2 .G = ( V, E)sol=(V.,mi)G=(V,E)V.V.VV.jaV.jaV_isolsolGV.jaV.jaV_i| V.ja| =2|V.ja|=2)|V_i|=2 Przykład …

10 cc.complexity-theory ds.algorithms graph-theory np-hardness hamiltonian-paths

1

Określ minimalną liczbę ważeń monet

W artykule Na temat dwóch problemów teorii informacji Erdõs i Rényi wyznaczają dolne granice minimalnej liczby ważeń, które należy zrobić, aby określić liczbę fałszywych monet w zestawie monet.nnn Bardziej formalnie: Fałszywe monety mają mniejszą wagę niż właściwe monety; znane są wagi i zarówno prawych, jak i fałszywych monet. Podana jest …

10 ds.algorithms reference-request co.combinatorics it.information-theory randomized-algorithms

4

Czy drzewa sufiksów mogą być użyte do znalezienia wszystkich popularnych podciągów?

Próbuję użyć drzewa sufiksów do porównania sekwencji ciągów. Znalazłem implementacje / teorię najdłuższego wspólnego problemu podciągów przy użyciu drzewek sufiksów. Jednak to, czego szukam, to omówienie powiązanego problemu - „wszystkich typowych podciągów”. W szczególności mam problem, w którym muszę najpierw znaleźć najdłuższy wspólny podciąg, a następnie znaleźć następny najdłuższy wspólny …

10 ds.algorithms string-matching

1

Najszybszy znany algorytm znajdowania prostych ścieżek przez dany zestaw wierzchołków

Dla nieukierunkowane wykres i dany zbiór S wierzchołków, co jest znane asymptotycznie najszybciej Algorytm znalezienia prostą drogę, zawierający wszystkie elementy S . Co jeśli wymagamy, aby ścieżka była jak najkrótsza?GGGSSSSSS

10 ds.algorithms graph-algorithms time-complexity

2

Czy obwody quasi-wielomianowe dla 3-SAT są banalne?

Załóżmy, że rozważamy 3-SAT ze zmiennymi i klauzulami c . Badam metodę, która wydaje się zajmować czas / przestrzeń O ( v 2 + log c ) w celu rozwiązania dowolnego problemu SAT pasującego do tego opisu, z błędem, który można dostosować do dowolnej kwoty. Jest jednak pewien haczyk.vvvdoccO ( …

10 ds.algorithms sat upper-bounds

1

Znajdowanie ścieżek rozłącznych wierzchołków od minimum do maksimum ze wspólnym źródłem na wykresach planarnych

Biorąc pod uwagę płaski wykres nieważony i zbiór par wierzchołków ( k ≥ 2 jest stałą), znajdź k ścieżek rozłącznych wierzchołków (z wyjątkiem źródła) od s do t i tak, że długość najdłuższej ścieżki jest zminimalizowana.( s , t1) , … , ( S , tk)(s,t1),…,(s,tk)(s,t_1),\dots,(s,t_k)k ≥ 2k≥2k\ge2kkkssstjatit_i Pytanie: Czy …

10 ds.algorithms graph-algorithms

1

Łączenie komórek za pomocą permutacji liniowych i kolumnowych w skończonej siatce

Chciałbym wiedzieć, czy wcześniej zbadano następujący prosty problem i czy znane jest jakieś rozwiązanie. Niech G będzie siatką skończoną (MxN), S podzbiorem komórek G („okruchy”). Mówi się, że dwie okruchy są (lokalnie) połączone, jeśli ich współrzędne różnią się co najwyżej o jeden (tj. Jeśli narysowane jako kwadraty, dzielą co najmniej …

10 ds.algorithms graph-theory graph-algorithms

1

Znalezienie rozpinających się pająków

Czy istnieje algorytm wielomianowy do znalezienia - jeśli taki istnieje - pająka rozpinającego danego wykresu ? Pająk to drzewo z co najmniej jednym węzłem o stopniu większym niż 2: Wiem, że różne warunki stopnia na (zasadniczo wystarczająco duże stopnie węzła) gwarantują istnienie pająka rozpinającego. Ale zastanawiam się, czy istnieje algorytm …

10 ds.algorithms reference-request graph-theory graph-algorithms

Pytania otagowane jako ds.algorithms