Pytania otagowane jako ds.algorithms

Pytania dotyczące dobrze zdefiniowanych instrukcji wykonania zadania oraz odpowiedniej analizy pod względem czasu / pamięci / itp.

10
Pobieranie #SAT Solver
Czy ktoś mógłby wskazać jedną lub więcej stron internetowych, z których można pobrać działającą implementację solvera #SAT? Interesują mnie osoby zwracające dokładną liczbę rozwiązań, a nie przybliżenie.
3
Sortowanie za pomocą czarnej skrzynki
Załóżmy, że chcemy posortować listę z liczb rzeczywistych. Załóżmy, że otrzymujemy czarną skrzynkę, która może natychmiast posortować liczb rzeczywistych. Ile korzyści możemy zyskać dzięki tej czarnej skrzynce?S.SS √nnnn−−√n\sqrt n Na przykład, czy możemy posortować numery za pomocą tylko wywołań do czarnej skrzynki? Najlepszy algorytm, jaki znalazłem, wykorzystuje wywołań do czarnej …
2
wydajny algorytm różnicowy dla drzew i odległości Levenshteina
Niedawno przeczytałem to podsumowanie zagadnień związanych z różnicowaniem między drzewami i zainteresowało mnie poznanie najnowocześniejszych rozwiązań tego problemu. Załóżmy również, że między dozwolonymi operacjami edycji jest tradycyjny węzeł dodawania / usuwania, edytuj zawartość, którą dodajesz rozszerzonymi operacjami poddrzewa kopiuj / przenieś, czy to sprawia, że ​​problem (znalezienie optymalnej różnicy) jest …
2
n-wymiarowe dopasowanie wzoru
Jakie są znane wyniki znalezienia dokładnej n-wymiarowej podtablicy wewnątrz n-wymiarowej tablicy? W 1D jest to tylko problem dopasowania łańcucha, KMP robi to w czasie liniowym. W 2D ten dokument pokazał, że można to zrobić w czasie liniowym z niewielką dodatkową przestrzenią. Czy ten problem można rozwiązać w najgorszym przypadku liniowym …
1
Znajdowanie odległości między dwoma wielomianami (przedstawionymi jako drzewa)
Kolega pracujący nad programowaniem genetycznym zadał mi następujące pytanie. Najpierw próbowałem go rozwiązać w oparciu o chciwe podejście, ale po drugiej myśli znalazłem kontrprzykład na algorytm chciwy. Pomyślałem więc, że warto tu wspomnieć. Rozważ dwa wielomiany reprezentowane przez drzewa wyrażeń. Na przykład x3)- 2 x + 1x3)-2)x+1x^3-2x+1 i x2)+ 4x2)+4x^2 …
3
Badanie algorytmów / złożoności algebry liniowej
Szukam dobrej ankiety na temat algorytmów i złożoności algebry liniowej (operacje takie jak rank, inverse, wartości własne, ... dla Boolean, oraz liczby całkowite / racjonalne) z naciskiem na równoległość ( hierarchia ) i algorytmy politime. Nie mogłem znaleźć ostatniego. NCfapFp\mathbb{F}_pN.doNCNC Czy znasz dobrą ostatnią ankietę lub książkę na temat złożoności …
5
Deterministyczny algorytm równoległy do ​​idealnego dopasowania na ogólnych wykresach?
W klasie złożoności istnieją pewne domniemania, że ​​NIE występują w klasie , tj. Problemy z deterministycznymi algorytmami równoległymi. Problem maksymalnego przepływu jest jednym z przykładów. I są problemy, WIĘCEJ, że są w , ale dowód jeszcze nie został znaleziony.N C N C.P.P\mathsf{P}N C.NC\mathsf{NC}N C.NC\mathsf{NC} Znakomite dopasowanie problemem jest to jeden …
4
Pozytywne uporządkowanie topologiczne, weź 3
Załóżmy, że mamy macierz n na n. Czy można zmienić kolejność wierszy i kolumn, tak aby uzyskać matrycę górnego trójkąta? To pytanie jest motywowane tym problemem: Pozytywne uporządkowanie topologiczne Pierwotny problem decyzyjny jest co najmniej tak trudny jak ten, więc wynik kompletności NP również by go rozwiązał. Edycja: Laszlo Vegh …
2
Szacowanie średniej w czasie wielomianowym
Niech f:{0,1}n→(2−n,1]f:{0,1}n→(2−n,1]f \colon \lbrace 0,1 \rbrace ^ n \to (2^{-n},1] będzie funkcją. Chcemy oszacować średnią fff ; to znaczy: E[f(n)]=2−n∑x∈{0,1}nf(x)E[f(n)]=2−n∑x∈{0,1}nf(x)\mathbb{E}[f(n)]=2^{-n}\sum_{x\in \lbrace 0,1 \rbrace ^ n}f(x) . NOTE: In the OP, the range of f was [0,1]. I changed this a bit for technical reasons. (This should simplify the problem; if …
1
Edytuj odległość w przestrzeni podliniowej
Jaka jest najbardziej znana złożoność obliczenia dokładnej odległości edycji między dwoma ciągami o tej samej długości przy użyciu przestrzeni roboczej, która jest podliniowa w wielkości wejścia? Zakładam, że dane wejściowe są przechowywane w jakimś formacie tylko do odczytu. Czy to wcześniej badany problem? Aby uczynić pytanie nieco bardziej szczegółowym, co …
1
Znalezienie dobrze wywołanego podgrupy
Otrzymujesz wykres z n wierzchołkami. Jeśli chcesz, może być dwustronny. Istnieje m zestawów krawędzi E 1 , … , E m ⊆ E (powiedz rozłączny). Interesuje mnie problem znalezienia podzbioru S ⊆ V , tak małego, jak to możliwe (lub nawet mniejszego), takiego, że indukowany wykres G S ma co …
2
Obliczanie stałej Cheegera: możliwe dla jakich klas?
Obliczanie stałej Cheegera na wykresie , znanej również jako stała izoperymetryczna (ponieważ jest to zasadniczo minimalny stosunek powierzchni do objętości), jest znana jako NP-zupełna. Ogólnie jest to przybliżone. Chciałbym się dowiedzieć, czy dokładne algorytmy wielomianowe są znane dla specjalnych klas grafów. Na przykład, czy nadal jest kompletny NP dla zwykłych …
1
Scalanie list delikatnych obiektów
Tło: Chao Xu opublikował kiedyś pytanie: „ Czy są znane algorytmy sortowania porównawczego, które nie ograniczają się do sieci sortujących, tak że każdy element jest porównywany razy?O ( logn )O(log⁡n)O(\log n) ”. Wygląda na to, że trochę utknęliśmy w tym problemie; Omówiłem ten sam problem z Valentinem Polczukiem w 2009 …
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.