Pytania otagowane jako randomness

Losowość jest sposobem matematycznego modelowania niepewności. Często zakładamy, że mamy dostęp do jakiegoś dobrze określonego źródła liczb losowych lub że wartości wejściowe lub zdarzenia mają pewien rozkład prawdopodobieństwa.

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
Jak asymptotycznie źle jest naiwne tasowanie?
Powszechnie wiadomo, że ten „naiwny” algorytm tasowania tablicy poprzez zamianę każdego elementu na inny losowo wybrany nie działa poprawnie: for (i=0..n-1) swap(A[i], A[random(n)]); W szczególności, ponieważ w każdym z nnn powtórzeń, jeden z nnn wyboru jest (z jednolitego prawdopodobieństwa) jest nnnnn^n możliwych ścieżek „” do obliczeń; ponieważ liczba możliwych permutacji …
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 …
7
Różnice i związki między algorytmami losowymi i niedeterministycznymi?
Jakie różnice i zależności występują między algorytmami losowymi a algorytmami niedeterministycznymi? Z Wikipedii Randomizowane algorytm jest algorytmem, w którym stosuje się stopniem losowości jako część logiki. Algorytm zwykle wykorzystuje jednolicie losowe bity jako pomocnicze dane wejściowe do kierowania jego zachowaniem, w nadziei na osiągnięcie dobrej wydajności w „przeciętnym przypadku” względem …
11
Czy przypadkowość von Neumanna w cytacie z grzechu nie ma już zastosowania?
Jakiś facet powiedział: Każdy, kto próbuje generować losowe liczby za pomocą deterministycznych środków, oczywiście żyje w stanie grzechu. To zawsze oznacza, że ​​nie można wygenerować prawdziwych liczb losowych za pomocą samego komputera. Powiedział też, że gdy komputery były równoważnej wielkości pojedynczego mikroprocesora Intel 8080 (~ 6000 zaworów). Komputery stały się …
1
Jak udowodnić poprawność algorytmu losowego?
Mam dwa sposoby tworzenia listy przedmiotów w losowej kolejności i chciałbym ustalić, czy są one równie uczciwe (obiektywne). Pierwszą metodą, której używam, jest skonstruowanie całej listy elementów, a następnie wykonanie losowania (powiedzmy losowanie Fisher-Yates). Druga metoda jest raczej metodą iteracyjną, która utrzymuje losowość listy przy każdym wstawieniu. W pseudokodzie funkcja …
8
Czym naprawdę jest przypadkowość
Jestem studentem informatyki i obecnie zapisuję się na kurs Symulacji Systemów i Modelowania. Obejmuje to radzenie sobie z codziennymi systemami wokół nas i symulowanie ich w różnych scenariuszach przez generowanie liczb losowych w różnych krzywych dystrybucyjnych, takich jak na przykład IID, Gaussa itp. Pracowałem nad projektem boids i właśnie uderzyło …
6
Czy możemy generować liczby losowe przy użyciu liczb niewymiernych, takich jak π i e?
Liczby niewymierne, takie jak , i mają unikatową i niepowtarzalną sekwencję po przecinku. Jeśli wyodrębnimy cyfrę z takich liczb (gdzie jest liczbą wywołań metody) i utworzymy liczbę z cyframi takimi, jakimi są, to czy nie powinniśmy uzyskać idealnego generatora liczb losowych? Na przykład, jeśli używamy , i , pierwsza liczba …
9
Jak symulować kość przy danej uczciwej monecie
Załóżmy, że otrzymałeś uczciwą monetę i chciałbyś zasymulować rozkład prawdopodobieństwa wielokrotnego rzutu rzetelną (sześciostronną) kością. Mój początkowy pomysł jest taki, że musimy wybrać odpowiednie liczby całkowite , takie, że . Więc po odwróceniu razy monety , mapujemy liczbę zakodowaną przez ciąg bitów o długości k na wyjścia matrycy, dzieląc zakres …
3
Czy próbka odrzucenia jest jedynym sposobem na uzyskanie prawdziwie jednolitego rozkładu liczb losowych?
Załóżmy, że mamy generator losowy, który generuje liczby w zakresie [0..R−1][0..R−1][0..R-1] o rozkładzie równomiernym i musimy wygenerować liczby losowe w zakresie [0..N−1][0..N−1][0..N-1] o rozkładzie równomiernym. Załóżmy, że N&lt;RN&lt;RN < R i NNN nie dzielą równomiernie RRR ; aby uzyskać naprawdę jednolity rozkład , możemy zastosować metodę próbkowania odrzucania : jeśli …
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.