Pytania otagowane jako randomized-algorithms

Pytania o algorytmy, których zachowanie zależy nie tylko od danych wejściowych, ale także od źródła liczb losowych.

1
Randomized Meldable Heap - Oczekiwana wysokość
Randomizowane zgrzewalne stosy mają operację „łączenie”, której następnie używamy do zdefiniowania wszystkich innych operacji, w tym wstawiania. Pytanie brzmi: jaka jest oczekiwana wysokość tego drzewa nnn węzły? Twierdzenie 1 Gambina i Malinkowskiego, Randomized Meldable Priority Queues (Proceedings of SOFSEM 1998, Lecture Notes in Computer Science vol. 1521, ss. 344–349, 1998; …
2
Czy istnieje algorytm „sortowania”, który zwraca losową permutację podczas korzystania z komparatora z monetą?
Zainspirowane tym pytaniem, w którym pytający chce wiedzieć, czy czas działania zmienia się, gdy komparator użyty w standardowym algorytmie wyszukiwania zostaje zastąpiony uczciwym rzucie monetą, a także wyraźnym niepowodzeniem Microsoftu w napisaniu jednolitego generatora permutacji, moje pytanie jest zatem : Czy istnieje algorytm sortowania oparty na porównaniu, który w zależności …
3
Konkretne zrozumienie różnicy między definicjami PP i BPP
Jestem zdezorientowany co do definicji PP i BPP . Załóżmy, że jest charakterystyczną funkcją języka . M być probabilistyczną Maszyną Turinga. Czy następujące definicje są poprawne:χχ\chiLL\mathcal{L} BPP={L:Pr[χ(x)≠M(x)]≥12+ϵ∀x∈L, ϵ>0}BPP={L:Pr[χ(x)≠M(x)]≥12+ϵ∀x∈L, ϵ>0}BPP =\{\mathcal{L} :Pr[\chi(x) \ne M(x)] \geq \frac{1}{2} + \epsilon \quad \forall x \in \mathcal{L},\ \epsilon > 0 \} PP={L:Pr[χ(x)≠M(x)]>12}PP={L:Pr[χ(x)≠M(x)]>12}PP =\{\mathcal{L} :Pr[\chi(x) \ne …
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.