Псевдослучайная последовательность

Псевдослуча́йная после́довательность (ПСП) — последовательность чисел, которая была вычислена по некоторому определённому арифметическому правилу, но имеет все свойства случайной последовательности чисел в рамках решаемой задачи.

Хотя псевдослучайная последовательность в этом смысле часто, как может показаться, лишена закономерностей, однако любой псевдослучайный генератор с конечным числом внутренних состояний повторится после очень длинной последовательности чисел. Это может быть доказано с помощью принципа Дирихле.

Генерация случайных чисел имеет множество применений таких как построение случайной выборки, методы Монте-Карло, настольные иазартные. Однако в физике большинство процессов, таких как гравитационное ускорение, являются детерминированными, что означает, что они всегда приводят к одному и тому же результату из одной и той же начальной точки. Некоторыми заметными исключениями являются радиоактивный распад и квантовые измерения, моделируемые как действительно случайные процессы благодаря лежащей в их основе физике. Поскольку эти процессы не являются практическими источниками случайных чисел, люди используют псевдослучайные числа, которые в идеале обладают непредсказуемостью действительно случайной последовательности, несмотря на то, что генерируются детерминированным процессом.

Во многих приложениях детерминированный процесс представляет собой компьютерный алгоритм, называемый генератором псевдослучайных чисел, которому сначала должно быть предоставлено число, называемое случайным начальным значением^[en]. Поскольку одно и то же начальное значение каждый раз будет давать одну и ту же последовательность, важно, чтобы начальное значение было хорошо выбрано и оставалось скрытым, особенно в приложениях безопасности, где непредсказуемость шаблона является критической особенностью.

В некоторых случаях, когда важно, чтобы последовательность была явно непредсказуемой, люди использовали физические источники случайных чисел, такие как радиоактивный распад, атмосферный электромагнитный шум, улавливаемый радиоприемником или смешанные тайминг нажатий клавиш^[en] людьми.

ИсторияПравить

До появления современных вычислений исследователи, которым требовались случайные числа, либо генерировали их с помощью различных объектов (кости, карты, колесо рулетки, и т.д.), либо использовали существующие таблицы случайных чисел.

Первая попытка предоставить исследователям готовый набор случайных цифр была предпринята в 1927 году, когда издательство Кембриджского университета опубликовало таблицу из 41 600 цифр, разработанную Л.Г.К.Типпеттом. В 1947 году корпорация RAND сгенерировала числа с помощью электронного моделирования колеса рулетки. Результаты были в конечном итоге опубликованы в 1955 году как A Million Random Digits with 100,000 Normal Deviates^[en].

Псевдослучайная последовательность

ИсторияПравить

См. такжеПравить

СсылкиПравить