Teoretyczne informatyka ds.algorithms

9

Szukam źródła ogromnych zestawów danych do przetestowania implementacji algorytmu grafowego. Proszę również podać informacje o typie / rozkładzie (np. Skierowane / nieukierowane, proste / nie proste, ważone / nieważone) wykresów w źródle, jeśli są one znane.

36 ds.algorithms graph-theory ds.data-structures data-sets

5

Mnożenie liczb całkowitych, gdy jedna liczba całkowita jest ustalona

Niech AAA będzie stałą dodatnią liczbą całkowitą o rozmiarze nnn bitów. Można odpowiednio wstępnie przetworzyć tę liczbę całkowitą. Biorąc pod uwagę kolejną dodatnią liczbę całkowitą BBB o rozmiarze mmm bitów, jaka jest złożoność mnożenia ABABAB ? ϵ = 0(max(n,m))1+ϵ(max(n,m))1+ϵ(\max(n,m))^{1+\epsilon}ϵ=0ϵ=0\epsilon=0

35 cc.complexity-theory ds.algorithms circuit-complexity algebraic-complexity arithmetic-circuits

3

Max-cut z ujemnymi krawędziami wagi

G=(V,E,w)G = (V, E, w)w:E→Rw:E\rightarrow \mathbb{R}arg max S ⊂ V ∑ ( u , v ) ∈ E : u ∈ S , v ∉ S w ( u , v ) w ( e ) ≥ 0 e ∈ EargmaxS⊂V∑(u,v)∈E:u∈S,v∉Sw(u,v)\arg\max_{S \subset V} \sum_{(u,v) \in E : u \in S, …

35 ds.algorithms graph-theory approximation-algorithms max-cut

1

Mnożenie n wielomianów stopnia 1

Problem polega na obliczeniu wielomianu . Załóżmy, że wszystkie współczynniki mieszczą się w słowie maszynowym, tzn. Można nimi manipulować w czasie jednostkowym.(a1x+b1)×⋯×(anx+bn)(a1x+b1)×⋯×(anx+bn)(a_1 x + b_1) \times \cdots \times (a_n x + b_n) Możesz zrobić czas , stosując FFT w sposób drzewny. Czy możesz zrobić O ( n log n ) …

35 ds.algorithms reference-request open-problem polynomials

8

Jakiej definicji asymptotycznej stopy wzrostu powinniśmy uczyć?

Kiedy postępujemy zgodnie ze standardowymi podręcznikami lub tradycją, większość z nas uczy następującej definicji notacji Big-Oh w pierwszych kilku wykładach klasy algorytmów: Być może podajemy nawet całą listę ze wszystkimi jej kwantyfikatorami:f=O(g) iff (∃c>0)(∃n0≥0)(∀n≥n0)(f(n)≤c⋅g(n)).f=O(g) iff (∃c>0)(∃n0≥0)(∀n≥n0)(f(n)≤c⋅g(n)). f = O(g) \mbox{ iff } (\exists c > 0)(\exists n_0 \geq 0)(\forall n …

35 ds.algorithms soft-question teaching

8

Algorytmy wyższego rzędu

Większość dobrze znanych algorytmów jest pierwszego rzędu, w tym sensie, że ich dane wejściowe i wyjściowe są danymi „prostymi”. Niektóre są drugiego rzędu w trywialny sposób, na przykład sortowanie, tablice skrótów lub funkcje mapowania i składania: są one parametryzowane przez funkcję, ale tak naprawdę nie robią z nią nic ciekawego …

35 ds.algorithms functional-programming ds.data-structures pl.programming-languages

11

Algorytmy aproksymacyjne dla problemów w P.

Zwykle myśli się o zbliżeniu rozwiązań (z gwarancjami) do problemów trudnych dla NP. Czy trwają badania nad zbliżeniem problemów, o których wiadomo, że są w P? To może być dobry pomysł z kilku powodów. Z góry mojej głowy algorytm aproksymacyjny może działać ze znacznie mniejszą złożonością (lub nawet znacznie mniejszą …

34 ds.algorithms approximation-algorithms

3

Biorąc pod uwagę ważony Dag, czy istnieje algorytm O (V + E), który zastępuje każdą wagę sumą wag przodka?

Problemem jest oczywiście podwójne liczenie. Jest to dość łatwe dla niektórych klas DAG = drzewo, a nawet drzewo szeregowo-równoległe. Jedynym algorytmem, który znalazłem, który działa na ogólnych DAG w rozsądnym czasie, jest przybliżony (dyfuzja streszczenia), ale zwiększenie jego precyzji jest wykładnicze pod względem liczby bitów (i potrzebuję dużo bitów). Tło: …

34 ds.algorithms graph-theory directed-acyclic-graph

1

Przykłady zabawek dla solverów Plotkin-Shmoys-Tardos i Arora-Kale

Chciałbym zrozumieć, w jaki sposób solver Arora-Kale SDP aproksymuje relaksację Goemansa-Williamsona w prawie liniowym czasie, jak solver Plotkin-Shmoys-Tardos aproksymuje ułamkowe problemy „upakowania” i „pokrycia” w prawie liniowym czasie oraz jak algorytmy są instancjami abstrakcyjnych ram „uczenia się od ekspertów”. Teza Kale'a ma doskonałą prezentację, ale bardzo trudno mi przejść bezpośrednio …

34 ds.algorithms approximation-algorithms linear-programming primal-dual semidefinite-programming

3

Najtrudniejszy znany problem naturalny w P?

Zastanawiam się, jaka jest (obecnie) największa liczba , tak że znany jest naturalny problem z następującymi właściwościami:kkk algorytm został już, że do tego problemu.O(nk)O(nk)O(n^k) Dla każdego ustalonego algorytmu no znany jest ten sam problem. (Zauważ, że istnieć szybszy algorytm , tylko nie jest jeszcze znany, więc nie szukam sprawdzonej dolnej …

33 cc.complexity-theory ds.algorithms

6

Wydajne i proste randomizowane algorytmy, w których determinizm jest trudny

Często słyszę, że w przypadku wielu problemów znamy bardzo eleganckie algorytmy randomizowane, ale nie ma, lub tylko bardziej skomplikowane, deterministyczne rozwiązania. Znam jednak tylko kilka przykładów. Najbardziej widoczne Randomized Quicksort (i powiązane algorytmy geometryczne, np. Dla wypukłych kadłubów) Randomized Mincut Testowanie tożsamości wielomianowej Problem Klee'a Spośród nich jedynie testowanie tożsamości …

33 ds.algorithms randomized-algorithms derandomization

2

Jakie klasy programów matematycznych można rozwiązać dokładnie lub w przybliżeniu w czasie wielomianowym?

Jestem raczej zdezorientowany literaturą o ciągłej optymalizacji i literaturą TCS o tym, które rodzaje (ciągłych) programów matematycznych (MP) można skutecznie rozwiązać, a które nie. Wydaje się, że społeczność ciągłej optymalizacji twierdzi, że wszystkie programy wypukłe można skutecznie rozwiązać, ale uważam, że ich definicja „wydajnego” nie pokrywa się z definicją TCS. …

31 ds.algorithms optimization linear-programming semidefinite-programming polynomial-time

3

Konsekwencje istnienia silnie wielomianowego algorytmu programowania liniowego?

Jednym ze świętych graali projektowania algorytmów jest znalezienie silnie wielomianowego algorytmu programowania liniowego, tj. Algorytmu, którego czas działania jest ograniczony wielomianem w liczbie zmiennych i ograniczeń i jest niezależny od wielkości reprezentacji parametrów (przy założeniu arytmetyka kosztów jednostkowych). Czy rozwiązanie tego pytania miałoby implikacje poza lepszymi algorytmami programowania liniowego? Na …

31 ds.algorithms conditional-results linear-programming computing-over-reals simplex

9

Randomizowany algorytm, który „wygląda” deterministycznie?

Czy istnieje interesujący przykład losowego algorytmu dla problemu wyszukiwania, który zawsze generuje tę samą (poprawną) odpowiedź, niezależnie od wewnętrznej losowości, ale który wykorzystuje losowość, dzięki czemu jej oczekiwany czas działania jest lepszy niż czas działania najszybszego znanego algorytm deterministyczny dla problemu? W szczególności zastanawiałem się, czy istnieje taki algorytm do …

31 ds.algorithms randomized-algorithms

5

co jest łatwe dla niewielkich wykluczonych wykresów?

Przybliżenie liczby kolorów wydaje się łatwe na niewielkich wykluczonych wykresach przy użyciu algorytmu Jung / Shah. Jakie są inne przykłady problemów, które są trudne na ogólnych wykresach, ale łatwe na niewielkich wykluczonych wykresach? Aktualizacja 10/24 Wydaje się, że podąża za wynikami Grohe, że wzór, którym jest FPT do testowania na …

31 ds.algorithms graph-theory graph-minor

Pytania otagowane jako ds.algorithms