Pytania otagowane jako ds.algorithms

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

6
Algorytmy strumienia danych „Dziel i rządź”
Jakie istnieją przydatne algorytmy, które działają na ogromnych strumieniach danych, a także ich wyniki są dość małe i można obliczyć wynik dla mieszanki dwóch strumieni, łącząc w jakiś sposób ich wyniki? Mogę wymienić kilka: Oczywiste rzeczy, takie jak suma, min, maksimum, liczba, najwyższe K itp. Przybliżone tak zwane „oparte na …
3
Derandomizacja strumieniowa
Algorytmy strumieniowe wymagają w większości przypadków randomizacji, aby zrobić coś nietrywialnego, a ze względu na ograniczenie małej przestrzeni potrzebują programów PRG, które zajmują mało miejsca. Znam dwie metody, które do tej pory były cytowane w algorytmach strumieniowych: -niezależne PRG-y, takie jak 4-mądra, niezależna rodzina używana przez Alona / Matiasa / …
1
Próbkowanie z wielowymiarowego Gaussa z grafem kowariancji Laplaciana (odwrotna)
Wiemy np. Z Koutis-Miller-Peng (na podstawie pracy Spielmana i Tenga), że możemy bardzo szybko rozwiązać układy liniowe dla macierzy które są wykresem macierzy Laplaciana dla niektórych rzadkich wykresów z nieujemnymi wagami krawędzi .Ax=bAx=bA x = bAAA Teraz (pierwsze pytanie) rozważ użycie jednej z tych grafów macierzy Laplaciana jako kowariancji lub …
3
Złożoność obliczania parzystości odczytu dwukrotnego przeciwnego do wzoru CNF (
W dwukrotnej, przeciwnej do odczytu formule CNF, każda zmienna pojawia się dwukrotnie, raz dodatnia, a raz ujemna. Jestem zainteresowany w problem, który polega na obliczaniu parytetu liczby spełniających zadania o przeciwnej wzoru CNF odczytu dwukrotnie.⊕ Rtw-Opp-CNF⊕Rtw-Opp-CNF\oplus\text{Rtw-Opp-CNF} Nie udało mi się znaleźć odniesienia do złożoności takiego problemu. Najbliższe, jakie udało mi …
2
Zabawa z odwrotnym Ackermannem
Odwrotna funkcja Ackermanna występuje często podczas analizy algorytmów. Świetna prezentacja tego jest tutaj: http://www.gabrielnivasch.org/fun/inverse-ackermann . i [Notacja: [x] oznacza, że ​​zaokrąglamy w górę x do najbliższej liczby całkowitej, podczas gdy log ∗ omówiono tutaj iterowaną funkcję dziennika: http://en.wikipedia.org/wiki/Iterated_logarithm ]α1(n)=[n/2]α1(n)=[n/2]\alpha_1(n) = [n/2] α2(n)=[log2n]α2(n)=[log2⁡n]\alpha_2(n) = [\log_2 n] α3(n)=log∗nα3(n)=log∗⁡n\alpha_3(n) = \log^* n ......... …
2
Jak mogę obliczyć węzły?
Czy istnieje udokumentowany sposób obliczania węzłów? (obwody osadzone w trójwymiarowej przestrzeni euklidesowej). Mam na myśli typ danych, który je reprezentuje, oraz algorytm określający, czy dwa wystąpienia typu danych reprezentują ten sam węzeł. Jeśli odpowiedź jest pozytywna, co ze złożonością tego problemu?
7
Podręcznik zaawansowanych algorytmów
Szukam zasobów (najlepiej podręcznika) na zaawansowane tematy w algorytmach (tematy wykraczające poza to, co są omówione w podręcznikach algorytmów, takich jak CLRS i DPV). Rodzaj materiału, który można wykorzystać do nauczania tematów w kursie algorytmów, takich jak Erik Demaine i kurs Davida Kargera Advanced Algorytmy . Preferowane są zasoby, które …
2
Algorytm czasu liniowego znajdowania przesuniętego maks
Załóżmy, że otrzymujemy tablicę A[1..n]A[1..n]A[1..n] zawierającą nieujemne liczby całkowite (niekoniecznie różne). BBBAAAm=maxi∈[n]B[i]+i.m=maxi∈[n]B[i]+i.m = \max_{i\in [n]} B[i]+i. Oczywistym rozwiązaniem jest sortowanie a następnie obliczanie . Daje to algorytm działający w czasie w najgorszym przypadku.AAAmmmO(nlgn)O(nlg⁡n)O(n \lg n) Czy można to zrobić lepiej? Czy możemy obliczyć czasie liniowym?mmm Moje główne pytanie to powyższe. …
2
Trudności ze zrozumieniem algorytmu kwantowego dla problemu ukrytej podgrupy abelowej
Mam trudności ze zrozumieniem ostatnich kroków algorytmu AHSP. Niech GGG była grupą abelowa i fff jest funkcją, która ukrywa podgrupy HHH . Niech G∗G∗G^* reprezentują podwójną grupę GGG . Oto kroki algorytmu Najpierw przygotuj państwo, I=1|G|∑g∈G|g⟩|0⟩I=1|G|∑g∈G|g⟩|0⟩\qquad \displaystyle I=\frac{1}{|G|} \sum_{g \in G} |g\rangle|0\rangle. Następnie zastosuj kwantową wyrocznię, która ocenia fff na …
1
zmaksymalizować MST (G [S]) na wszystkich indukowanych podgraphach G [S] na wykresie metrycznym
Czy ten problem był już badany? Biorąc pod uwagę metryczny niekierowany wykres G (długości krawędzi spełniają nierówność trójkąta), znajdź zestaw S wierzchołków, tak że MST (G [S]) jest zmaksymalizowany, gdzie MST (G [S]) jest minimalnym drzewem rozpinającym podgrafu wywołanym przez S. Czy ten problem był już badany? Czy to trudne …
3
Czy możemy obliczyć
Szukam wydajnego algorytmu dla problemu: Wejście : dodatnia liczba całkowita 3)n3n3^n (zapisana w bitach) dla jakiejś liczby całkowitej n ≥ 0n≥0n \geq 0 . Wyjście : liczba nnn . Pytanie : Czy możemy obliczyć nnn na podstawie bitów 3)n3)n3^n w czasie O ( n )O(n)O(n) ? To jest teoretyczne pytanie …
2
Znajdź wszystkie pary wartości bliskich odległości Hamminga
Mam kilka milionów wartości 32-bitowych. Dla każdej wartości chcę znaleźć wszystkie inne wartości w odległości Hamminga wynoszącej 5. W podejściu naiwnym wymaga to porównań O(N2)O(N2)O(N^2) , których chcę uniknąć. Uświadomiłem sobie, że jeśli potraktowałem te 32-bitowe wartości jako liczby całkowite i posortowałem listę raz, to wartości, które różniły się tylko …
4
Dolna granica dla testowania bliskości w normie ?
Zastanawiałem się, czy istnieje jakakolwiek dolna granica (pod względem złożoności próby) znana z następującego problemu: Biorąc pod uwagę przykładowy dostęp do wyroczni do dwóch nieznanych dystrybucji , D_2 w \ {1, \ dots, n \} , test (whp) czyD1D1D_1D2D2D_2{1,…,n}{1,…,n}\{1,\dots,n\} D1=D2D1=D2D_1=D_2 lub d2(D1,D2)=∥D1−D2∥2=∑ni=1(D1(i)−D2(i))2−−−−−−−−−−−−−−−−−−√≥ϵd2⁡(D1,D2)=‖D1−D2‖2=∑i=1n(D1(i)−D2(i))2≥ϵ\operatorname{d_2}(D_1,D_2)=\lVert D_1-D_2\rVert_2 = \sqrt{\sum_{i=1}^n\left(D_1(i)-D_2(i)\right)^2} \geq \epsilon Batu i in. …
2
Jak generować wykresy ze znaną optymalną osłoną wierzchołków
Szukam sposobu generowania wykresów, aby znana była optymalna osłona wierzchołków. Nie ma ograniczeń co do liczby węzłów lub krawędzi, tylko to, że wykres jest całkowicie połączony. chodzi o wygenerowanie wykresu, który nie jest łatwy do znalezienia optymalnej osłony wierzchołków, aby móc przetestować na niej różne heurystyki Znalazłem artykuł Arthur, J. …
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.