Pytania otagowane jako pseudo-random-generators

Pytania o algorytmy, które deterministycznie generują sekwencje liczb, które mają stochastyczne właściwości ciągów losowych.

6
Dlaczego nie łączymy generatorów liczb losowych?
Istnieje wiele aplikacji, w których używany jest pseudolosowy generator liczb losowych. Dlatego ludzie wdrażają taki, który ich zdaniem jest świetny, aby później stwierdzić, że jest wadliwy. Coś takiego stało się ostatnio z generatorem liczb losowych Javascript. RandU też dużo wcześniej. Istnieją również problemy z niewłaściwym początkowym zaszczepieniem czegoś takiego jak …
7
Czy można używać PRNG do magicznej kompresji?
Pomysł ten przyszedł mi do głowy jako dziecko uczące się programowania i przy pierwszym spotkaniu z PRNG. Nadal nie wiem, jak realistyczne jest, ale teraz jest wymiana stosów. Oto 14-letni schemat niesamowitego algorytmu kompresji: Weź PRNG i zaszczep go ziarnem, saby uzyskać długą sekwencję pseudolosowych bajtów. Aby przekazać tę sekwencję …
2
Symulowanie prawdopodobieństwa 1 z 2 ^ N przy mniej niż N losowych bitach
Powiedz, że muszę zasymulować następujący rozkład dyskretny: P(X=k)={12N,1−12N,if k=1if k=0P(X=k)={12N,if k=11−12N,if k=0 P(X = k) = \begin{cases} \frac{1}{2^N}, & \text{if $k = 1$} \\ 1 - \frac{1}{2^N}, & \text{if $k = 0$} \end{cases} Najbardziej oczywistym sposobem jest narysowanie losowych bitów i sprawdzenie, czy wszystkie są równe (lub ). Jednak teoria …
1
Sprawdzanie bezpieczeństwa generatora liczb pseudolosowych Nisan-Wigderson
Niech częściowe -design i być funkcją logiczną. Generator Nisan- jest zdefiniowany w następujący sposób:S={Si}1≤i≤nS={Si}1≤i≤n\cal{S}=\{S_i\}_{1\leq i\leq n}(m,k)(m,k)(m,k)f:{0,1}m→{0,1}f:{0,1}m→{0,1}f: \{0,1\}^m \to \{0,1\}Gf:{0,1}l→{0,1}nGf:{0,1}l→{0,1}nG_f: \{0,1\}^l \to \{0,1\}^n Gf(x)=(f(x|S1),…,f(x|Sn))Gf(x)=(f(x|S1),…,f(x|Sn))G_f(x) = (f(x|_{S_1}) , \ldots, f(x|_{S_n}) ) Aby obliczyć ty bit , bierzemy bity z indeksami w a następnie stosujemy do nich .iiiGfGfG_fxxxSiSiS_ifff Załóżmy, że jest twarde dla …
4
PRNG do generowania liczb z n dokładnie ustawionymi bitami
Obecnie piszę kod do generowania danych binarnych. W szczególności muszę wygenerować liczby 64-bitowe przy określonej liczbie ustawionych bitów; dokładniej, procedura powinna zająć około i zwrócić pseudolosową 64-bitową liczbę z dokładnie bitami ustawionymi na , a resztą ustawioną na 0.0 &lt; n &lt; 640&lt;n&lt;640 < n < 64nnn111 Moje obecne podejście …
4
Jaki jest dobry algorytm do generowania losowych DFA?
Generuję losowe DFA, aby przetestować na nich algorytm redukcji DFA. Algorytm, którego teraz używam, jest następujący: dla każdego stanu , dla każdego symbolu w alfabecie dodaj do jakiegoś losowego stanu. Każde państwo ma takie samo prawdopodobieństwo, że stanie się stanem końcowym.qqqdodocδ( q, c )δ(q,do)\delta (q, c) Czy to dobra metoda …
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.