Pytania otagowane jako randomized-algorithms

Algorytm, którego zachowanie jest determinowane przez jego dane wejściowe, oraz generator generujący jednolicie losowe liczby.

5
Kiedy randomizacja przyspiesza algorytmy i „nie powinna”?
Dowód Adlemana, że jest zawarty w pokazuje, że jeśli istnieje algorytm losowy dla problemu, który działa w czasie na wejściach o rozmiarze , to istnieje również algorytm deterministyczny dla problemu, który działa w czasie na materiale o wielkości [algorytm prowadzi randomizowane algorytm na niezależnych łańcuchów losowości. Musi istnieć losowość powtarzanego …
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 …
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 …
1
Czy jednolity RNC jest zawarty w przestrzeni polilogu?
Logarytmiczna jednolita NC jest zawarta w deterministycznej przestrzeni polilogu (czasami zapisywanej jako PolyL). Czy RNC o jednolitej przestrzeni logów również należy do tej klasy? Standardowa losowa wersja PolyL powinna być w PolyL, ale nie widzę, aby (jednolity) RNC był w randomizowanym-PolyL. Trudność, jaką widzę, polega na tym, że w RNC …
10
Algorytmy probabilistyczne (randomizowane) przed pojawieniem się „nowoczesnej” informatyki
Edycja: wybieram odpowiedź z najwyższym wynikiem do 6 grudnia 2012 r. To delikatne pytanie. Pojęcie (deterministycznych) algorytmów sięga BC. Co z algorytmami probabilistycznymi? W tym wpisie wiki algorytm Rabina dla problemu najbliższej pary w geometrii obliczeniowej podano jako pierwszy algorytm losowy (rok ???). Lipton wprowadził algorytm Rabina jako początek ery …
1
Inne zastosowania wzmocnienia rozgałęzień Karger-Stein?
Właśnie nauczyłem losowego algorytmu skrótu Karger-Stein w mojej klasie algorytmów dla absolwentów. To prawdziwy klejnot algorytmiczny , więc nie mogę tego nie uczyć, ale zawsze denerwuje mnie, ponieważ nie znam innych zastosowań głównej techniki. (Trudno więc przypisać pracę domową, która doprowadzi ten punkt do domu.) Algorytm Kargera i Steina jest …
1
Kto pierwszy zaproponował użycie
Jestem pewien, że wszyscy wiedzą o eksperymencie igły Buffona w XVIII wieku, który jest jednym z pierwszych algorytmów probabilistycznych do obliczeniaππ\pi. Implementacja algorytmu w komputerach zwykle wymaga użycia ππ\pilub funkcja trygonometryczna, która nawet jeśli są zaimplementowane jako skrócone serie, to w pewnym sensie nie udaje się to osiągnąć. Aby obejść …
4
Jakie konkretne dowody istnieją dla P = RP?
RP to klasa problemów rozstrzyganych przez niedeterministyczną maszynę Turinga, która kończy się w czasie wielomianowym, ale dopuszczalny jest również błąd jednostronny. P jest zwykłą klasą problemów rozstrzyganych przez deterministyczną maszynę Turinga, która kończy się w czasie wielomianowym. P = RP wynika z zależności w złożoności obwodu. Impagliazzo i Wigderson wykazali, …
1
Losowa złożoność zapytań problemu drzew połączonych
Ważny artykuł z 2003 roku autorstwa Childsa i in.wprowadził „problem drzew połączonych”: problem dopuszczający wykładnicze przyspieszenie kwantowe, który nie jest podobny do żadnego innego znanego nam problemu. W tym problemie otrzymaliśmy wykładniczo duży wykres, taki jak ten pokazany poniżej, który składa się z dwóch kompletnych dwójkowych drzewek głębokości n, których …
2
Zasada Minimax Yao dotycząca algorytmów Monte Carlo
Słynny Yao Minimax Zasada stwierdza zależność między złożonością i dystrybucyjnej randomizowanym złożoności. Niech PPP być problemu ze skończonego zbioru wejść i skończonego zbioru deterministycznego algorytmu rozwiązania . Niech także oznacza rozkład wejściowy, a niech oznacza rozkład prawdopodobieństwa na . Następnie zasada głosi: XX\mathcal{X}AA\mathcal{A}PPPDD\mathcal{D}RR\mathcal{R}AA\mathcal{A}minA∈AEcost(A,D)≤maxx∈XEcost(R,x)for all D and R.minA∈AEcost(A,D)≤maxx∈XEcost(R,x)for all D and …
3
Uogólniając „sztuczkę środkową” do wyższych wymiarów?
W przypadku algorytmów losowych przyjmujących rzeczywiste wartości „sztuczka medianowa” jest prostym sposobem zmniejszenia prawdopodobieństwa niepowodzenia do dowolnego progu , kosztem tylko wielokrotności narzut. Mianowicie, jeśli wyjście mieści się w „dobrym zakresie” z prawdopodobieństwem (co najmniej) , to uruchamianie niezależnych kopii i przyjmując medianę swoich wyników spowoduje, że wartość spadnie do …
1
Schemat blokowy granic stężenia
Kiedy uczę ograniczeń ogona, używam zwykłego postępu: Jeśli twoje Rv jest dodatnie, możesz zastosować nierówność Markowa Jeśli masz niezależność, a także ograniczoną wariancję, możesz zastosować nierówność Czebyszewa Jeśli każdy niezależny rv ma również ograniczone wszystkie chwile, możesz użyć ograniczenia Chernoffa. Po tym wszystko staje się trochę mniej czyste. Na przykład …
2
Ogranicza się do
Jeśli jest funkcją wypukłą, to nierówność Jensena stwierdza, że i mutatis mutandis, gdy jest wklęsłe. Oczywiście w najgorszym przypadku nie można górnej granicy w kategoriach dla wypukłego , ale czy istnieje granica, która idzie w tym kierunku, jeśli jest wypukły, ale „niezbyt wypukły”? Czy istnieje jakieś standardowe ograniczenie, które określa …
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 …
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.