Pytania otagowane jako reference-request

Prośba o referencję jest wykorzystywana, gdy autor musi wiedzieć o pracy związanej z pytaniem.

5
Dowody poprawności kompilatora
Szukam materiału instruktażowego, który obejmuje dowody poprawności kompilatora, najlepiej przy użyciu metod denotacyjnych, na poziomie początkującego studenta. Alternatywnie, czy znasz kilka prostych przykładów kompilatora, których mógłbym zilustrować problemy? (Pierwszym przykładem, który przyszedł mi do głowy, był tłumacz z wyrażeń odrostkowych na wyrażenia postfiksowe. Ale nie pokazał niczego interesującego oprócz tego, …
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 …
5
Ograniczasz wykorzystanie miejsca przez łączność st za pomocą wielu przebiegów?
Załóżmy, że wykres z n wierzchołkami jest przedstawiony jako strumień m krawędzi, ale nad strumieniem dozwolonych jest wiele przejść.solGGnnnmmm Monika Rauch Henzinger, Prabhakar Raghavan i Sridar Rajagopalan zauważyli, że przestrzeń jest niezbędna do ustalenia, czy istnieje ścieżka między dwoma podanymi wierzchołkami w G , jeśli dopuszcza się k przejść przez …
4
Czy prowadzone są obecnie badania nad wdrożeniem ekstraktorów losowości?
Czy przeprowadzono badania nad implementacją konstrukcji ekstraktorów losowości? Wydaje się, że proofy ekstraktora wykorzystują Big-Oh, pozostawiając możliwość dużych, ukrytych stałych, czyniąc implementacje programowe potencjalnie nierealnymi. Trochę kontekstu: jestem zainteresowany wykorzystaniem ekstraktorów losowości jako szybkiego źródła (prawdopodobnie?) Liczb losowych do użycia w symulacjach Monte Carlo. My (grupa ETHZ Computational Physics) stronnicze …
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 …
1
Czy znane są skuteczne granice ogólne w stylu Bonferroniego?
Klasycznym problemem w teorii prawdopodobieństwa jest wyrażenie prawdopodobieństwa zdarzenia w kategoriach bardziej specyficznych zdarzeń. W najprostszym przypadku można powiedzieć . Write LET'S za zdarzenie .A B A ∩ BP[A∪B]=P[A]+P[B]−P[A∩B]P[A∪B]=P[A]+P[B]−P[A∩B]P[A \cup B] = P[A] + P[B] - P[A \cap B]ABABABA∩BA∩BA \cap B Istnieją zatem pewne sposoby na powiązanie , bez zakładania …
3
Testowanie właściwości w innych metrykach?
Istnieje duża literatura na temat „testowania właściwości” - problemu polegającego na utworzeniu niewielkiej liczby zapytań do czarnej skrzynki do funkcji celu rozróżnienia dwóch przypadków:f:{0,1}n→Rf:{0,1}n→Rf\colon\{0,1\}^n \to R fff jest członkiem pewnej klasy funkcjiCC\mathcal{C} fff jest -far z każdej funkcji w klasie .εε\varepsilonCC\mathcal{C} Zakres funkcji jest czasem wartością logiczną: , ale nie …
3
Jaki jest właściwy model teoretyczny do projektowania algorytmów dla obecnych i przyszłych komputerów o wysokiej wydajności
To pytanie jest podobne do bardziej ogólnego pytania dotyczącego tego, jaki jest właściwy model teoretyczny komputera do projektowania algorytmów i struktur danych. Tutaj pytam konkretnie o obecne komputery o wysokiej wydajności (takie jak te wymienione na liście 500 najlepszych ), a nawet o nadchodzące superkomputery. Biorąc pod uwagę, że komputery …
3
NP kompletne problemy graficzne na temat właściwości strukturalnych
(To pytanie jest trochę „ankietą”). Aktualnie pracuję nad problemem, w którym próbuję podzielić krawędzie turnieju na dwa zestawy, z których oba są wymagane do spełnienia niektórych właściwości strukturalnych. Problem „czuje się” bardzo trudne, a ja w pełni się spodziewać, że będzie N.P.NP\mathcal{NP} -complete.For jakiegoś powodu mam problemy ze znalezieniem nawet …
2
„Osadzanie” języka jako takiego
Pytanie główne / ogólne Niech LLL będzie językiem. Zdefiniuj języki LiLiL_i pomocą L0=LL0=LL_0 = L i Li={xwy:xy∈Li−1,w∈L}Li={xwy:xy∈Li−1,w∈L}L_i = \{xwy : xy \in L_{i-1}, w \in L\} dla i≥1i≥1i \geq 1 . Rozważmy L = ⋃ l i . Tak więc wielokrotnie „osadzić” L w siebie, aby uzyskać L .L^=⋃LiL^=⋃Li\hat{L} = …
1
Czy istnieje geometryczny obraz adiabatycznego obliczenia kwantowego?
W adiabatycznym obliczeniu kwantowym (AQC) koduje się rozwiązanie problemu optymalizacji w stanie podstawowym [problemu] Hamiltoniana . Aby dojść do tego stanu podstawowego, zaczynasz w łatwym do stanie początkowym (podstawowym) z Hamiltonianem i „wyżarzaniem” ( adiabatycznym) w kierunku , tj.H i H pH.pHpH_pH.jaHiH_iH.pHpH_p H.( s ) = s H.ja+ ( 1 …
2
Algorytm Runtime of Grover
Jaka jest złożoność czasowa (nie złożoność zapytań) algorytmu Grovera? Wydaje mi się jasne, że jest to ponieważ istnieją iteracje i każda iteracja wymaga użycia operacji odbicia, która z kolei wymaga czasu przy użyciu dowolnego standardowego zestawu bram uniwersalnych.Ω(log(N)N−−√)Ω(log⁡(N)N)\Omega(\log(N) \sqrt{N})Ω(N−−√)Ω(N)\Omega(\sqrt{N})Ω(log(N))Ω(log⁡(N))\Omega(\log(N)) Problem polega na tym, że nie mogę znaleźć ani jednego odniesienia, …
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.