"Информатика (базовый уровень)", Гейн А.Г., Юнерман Н.А.
Датчик случайных чисел выдаёт значения, используемые для моделирования случайных событий. Физический датчик получает их из непредсказуемых процессов, а программный генератор вычисляет по алгоритму. Поэтому компьютерные последовательности чаще называют псевдослучайными: они похожи на случайные, но зависят от начального значения и через некоторое время повторяются. Для оценки генератора проверяют равномерность, период и отсутствие заметных закономерностей.
Текст подготовлен нейронной сетью по теме параграфа и не заменяет учебник — важные факты и формулировки сверяйте с ним.
Датчик случайных чисел — устройство или программный механизм, выдающий числа, которые используются как случайные. Физический датчик получает их из шума или другого внешнего процесса, а программа вычисляет по заданному правилу. Это понятие нужно, чтобы отличать источник случайности от дальнейшей обработки чисел.
Псевдослучайная последовательность — последовательность чисел, полученная детерминированным алгоритмом и внешне похожая на случайную. Детерминированный значит однозначный: одинаковые исходные данные дают один и тот же результат. Такие последовательности позволяют проводить воспроизводимые компьютерные эксперименты.
Начальное значение — исходное число, от которого зависит вся псевдослучайная последовательность. Его также называют начальным состоянием или зерном генератора. Фиксируя это значение, можно повторить расчёт и проверить, как программа получила результат.
Период последовательности — число шагов до повторения уже появлявшегося состояния генератора. После повторения состояния дальнейшие значения начинают идти по тому же циклу. Период показывает, насколько долго генератор может выдавать новые состояния без повторов.
Физические датчики получают случайность из процессов, которыми нельзя точно управлять или заранее вычислить: электрического шума, радиоактивного распада, колебаний времени между событиями. Причина в том, что результат таких процессов не задаётся одной только программой. Компьютер измеряет источник, очищает данные от технических искажений и превращает их в числа.
Программный генератор действует иначе: он хранит текущее состояние и по алгоритму вычисляет следующее. Числа кажутся случайными, потому что формула специально создаёт сложное распределение и скрывает простые зависимости. Такой способ быстрее физического измерения и удобен, когда нужно получить много значений.
Одинаковое начальное значение приводит к одинаковой последовательности, потому что алгоритм на каждом шаге получает те же исходные данные. Если начальное значение изменить, первое состояние изменится, а затем обычно изменятся и все следующие состояния. Это позволяет либо воспроизводить эксперимент, либо получать разные результаты при разных запусках.
Типичная рекуррентная формула записывается так: xn+1 = f(xn). Она превращает текущее состояние в следующее, а операция mod ограничивает результат остатком от деления. Если возможных состояний конечное число, генератор не может бесконечно посещать новые состояния, поэтому какое-то состояние рано или поздно повторится.
Число u из диапазона [0; 1) можно перевести в целое на отрезке от a до b формулой a + ⌊u(b − a + 1)⌋. Скобки ⌊ ⌋ означают целую часть числа, поэтому значения распределяются по всем целым числам от a до b. Качество генератора проверяют по равномерности, отсутствию заметных закономерностей и длине периода, поскольку один удачный фрагмент ещё не доказывает хорошую работу.
| Характеристика | Датчик истинных случайных чисел | Датчик псевдослучайных чисел |
|---|---|---|
| Источник чисел | Внешний физический случайный процесс | Алгоритм и начальное значение |
| Воспроизводимость результата | Обычно невозможно точно повторить | Возможна при том же начальном значении |
| Зависимость от начального значения | Не является определяющей | Определяет всю последовательность |
| Наличие периода | Не задаётся алгоритмом | Есть из-за конечного числа состояний |
| Скорость получения чисел | Зависит от измерения физического процесса | Обычно очень высокая |
| Области применения | Криптография, научные измерения, лотереи | Игры, моделирование, тестирование, эксперименты |
Сначала определите, нужна ли непредсказуемость от внешнего источника или достаточно быстрого алгоритма. Затем сравните требования задачи с воспроизводимостью, скоростью и длиной периода. Таблица помогает увидеть, почему псевдослучайный генератор удобен не для всех целей.
Задача 1. С помощью датчика случайных чисел нужно смоделировать 20 бросков кубика и узнать, сколько раз выпало каждое значение от 1 до 6. Результаты надо не просто вывести, а сгруппировать по значениям. Для этого используются генерация целого числа и массив счётчиков.
Ответ. Получится таблица частот для значений 1, 2, 3, 4, 5 и 6. Конкретные числа зависят от последовательности генератора, поэтому при другом начальном значении результат может измениться.
Задача 2. Для генератора xn+1 = (5xn + 3) mod 16 при x0 = 2 нужно выписать последовательность до первого повторения. На каждом шаге сначала выполняем умножение и сложение, затем берём остаток от деления на 16. Повтор состояния означает начало цикла.
Ответ. Последовательность состояний: 2, 13, 4, 7, 6, 1, 8, 11, 10, 5, 12, 15, 14, 9, 0, 3, после чего снова появляется 2. Период равен 16, потому что повторилось начальное состояние после 16 переходов.
Задача 3. Нужно оценить π по 10 000 случайным точкам в квадрате, содержащем вписанную окружность. Пусть квадрат имеет стороны от −1 до 1, а точка имеет координаты x и y. Точка попадает в окружность, если x² + y² ≤ 1.
Ответ. Полученное число будет приближённым значением π. При увеличении числа точек случайные отклонения обычно уменьшаются, а разные начальные значения дают разные, но близкие оценки.
Считать псевдослучайные числа полностью случайными. Ошибка возникает, когда внешний вид последовательности принимают за доказательство её случайности. Нужно помнить о детерминированном алгоритме и возможном повторе состояний. Проверка: запустите генератор с тем же начальным значением и сравните результаты.
Забывать о начальном значении. Без него невозможно объяснить, почему два запуска дали разные последовательности или почему одинаковые результаты удалось повторить. Проверяйте, задано ли зерно явно и одинаково ли оно в сравниваемых экспериментах. Полезный тест — дважды запустить программу с одним значением.
Неправильно переводить [0; 1) в целый диапазон. Часто ошибочно используют длину отрезка b − a вместо b − a + 1 или допускают значение 1, которого в исходном диапазоне нет. Проверьте формулу на u = 0 и на значениях, близких к 1: результат должен лежать от a до b, а все границы должны учитываться.
Судить о качестве по нескольким первым числам. Короткий фрагмент может случайно выглядеть хорошим или плохим и ничего не сказать о всей последовательности. Проверяйте частоты на большой выборке, длину периода и наличие повторяющихся закономерностей. Для серьёзных задач применяют специальные статистические тесты.
До изучения темы нужны остаток от деления, рекуррентные алгоритмы и диапазоны целых и вещественных чисел. Циклы позволяют получать много значений, а массивы — хранить частоты и состояния. Эти знания связывают формулу генератора с программой.
Датчики случайных чисел применяются при моделировании случайных процессов и вычислительных экспериментах. В играх они определяют события, противников и расположение объектов. Понимание генераторов помогает оценивать, насколько правдоподобно работает модель.
Начальное значение связано с воспроизводимостью: один эксперимент можно повторить и проверить. Ограничения псевдослучайных генераторов важны для информационной безопасности, потому что предсказуемую последовательность нельзя считать надёжной защитой секрета.
Почему последовательность называется случайной, если её вычисляет программа?
Программа создаёт числа по алгоритму, поэтому сама последовательность не является истинно случайной. Но при хорошем алгоритме её закономерности трудно заметить, и для моделирования она ведёт себя как случайная.
Зачем задавать начальное значение генератора?
Начальное значение определяет, с какого состояния начнётся вычисление последовательности. Если использовать одно и то же значение, результат можно полностью воспроизвести.
Можно ли получить действительно случайное число с помощью компьютера?
Да, если компьютер использует внешний физический процесс: шум электронных схем, время между событиями или другой непредсказуемый источник. Обычная функция генерации случайных чисел чаще создаёт псевдослучайную последовательность.
Как определить период псевдослучайной последовательности?
Нужно последовательно вычислять состояния генератора и запоминать их. Периодом будет число шагов от первого появления состояния до его повторения, если цикл не начинается сразу с начального состояния.
Почему один и тот же генератор нельзя одинаково использовать для игры и для шифрования?
В игре достаточно, чтобы числа выглядели случайными и быстро получались. Для шифрования требуется непредсказуемость: если злоумышленник угадает алгоритм и начальное значение, он сможет восстановить последовательность.
§ 25. Датчики случайных чисел и псевдослучайные последовательности
