Алгоритмы неформально. Инструкция для начинающих питонистов - [41]

Математические правила физики в нашем понимании соответствуют концепции детерминированной Вселенной, но также соответствуют и недетерминированной Вселенной, в которой случайность действительно существует — как выражаются некоторые, «Бог играет в кости». Они соответствуют и сценарию «множественных миров», в котором происходят все возможные версии события, но происходят они в разных Вселенных, недоступных друг для друга. Все эти интерпретации законов физики только усложняются, когда мы пытаемся найти в космосе место для свободы воли. Интерпретация математической физики, которую мы принимаем, зависит не от нашего математического понимания, а скорее от наших философских склонностей — с математической точки зрения приемлема любая позиция.

Независимо от того, существует во Вселенной случайность или нет, в вашем компьютере ее нет — или, по крайней мере, не должно быть. Предполагается, что компьютеры — наши идеально послушные слуги, которые делают только то, что мы им явно приказываем, в точности, когда и как приказываем. Когда вы приказываете компьютеру запустить видеоигру, выполнить машинное обучение на базе случайного леса или провести эксперимент с элементами случайности, вы приказываете изначально детерминированной машине сгенерировать нечто недетерминированное: случайное число. Выполнить такой приказ невозможно.

Так как компьютер не может обеспечить полноценную случайность, были разработаны алгоритмы, которые обеспечивают лучшее, что возможно в такой ситуации: псевдослучайность. Алгоритмы генерирования псевдослучайных чисел важны по всем тем же причинам, по которым важны случайные числа. Поскольку истинная случайность на компьютере невозможна (и не исключено, что невозможна во Вселенной в целом), алгоритмы генерирования псевдослучайных чисел должны проектироваться чрезвычайно внимательно, чтобы их вывод был по возможности близок к полноценной случайности. Как можно судить о том, в какой степени алгоритм генерирования псевдослучайных чисел напоминает настоящую случайность? Это зависит от математических определений и теории, которые вскоре будут представлены ниже.

Начнем с простого алгоритма генерирования случайных чисел и посмотрим, в какой степени его вывод напоминает случайные числа.

Линейные конгруэнтные генераторы

Один из простейших примеров генератора псевдослучайных чисел (ГПСЧ) — линейный конгруэнтный генератор (ЛКГ). Для реализации этого алгоритма необходимо выбрать три числа, которые мы назовем n1, n2 и n3. ЛКГ начинает с натурального числа (например, 1), после чего применяет следующее уравнение для получения следующего числа:

следующее = (предыдущее×n1 + n2) modn3.

Это весь алгоритм, который, по сути, состоит из одного шага. На языке Python вместо mod будет использоваться оператор %, а вся реализация функции ЛКГ приведена в листинге 5.8.

Листинг 5.8. Линейный конгруэнтный генератор

def next_random(previous,n1,n2,n3):

    the_next = (previous * n1 + n2) % n3

    return(the_next)

Обратите внимание: функция next_random() является детерминированной, то есть при получении одного ввода вы всегда будете получать один и тот же вывод. Стоит еще раз пояснить, что наш ГПСЧ должен быть таким из-за детерминированности самих компьютеров. ЛКГ генерирует не настоящие случайные числа, а числа, которые выглядят как случайные — то есть псевдослучайные.

Чтобы оценить способность этого алгоритма генерировать псевдослучайные числа, будет полезно просмотреть набор сгенерированных чисел. Вместо того чтобы получать случайные числа по одному, можно построить целый список значений с помощью функции, многократно вызывающей только что созданную функцию next_random():

def list_random(n1,n2,n3):

    output = [1]

    while len(output) <=n3:

        output.append(next_random(output[len(output) - 1],n1,n2,n3))

    return(output)

При вызове функции list_random(29,23,32) будет получен следующий список:

[1, 20, 27, 6, 5, 8, 31, 26, 9, 28, 3, 14, 13, 16, 7, 2, 17, 4, 11, 22, 21,

24, 15, 10, 25, 12, 19, 30, 29, 0, 23, 18, 1]

В этом списке сложно обнаружить какую-то закономерность — что, собственно, нам и нужно. Прежде всего можно заметить, что он содержит только числа от 0 до 32. Кроме того, можно заметить, что последний элемент этого списка равен 1, то есть совпадает с первым элементом. Если вам понадобится больше случайных чисел, то список можно было бы продолжить вызовом функции next_random() для его последнего элемента 1. Однако следует помнить, что функция next_random() является детерминированной. Продолжив список, вы получите повторение его начала, так как следующим «случайным» числом после 1 всегда будет 20, следующим случайным числом после 20 всегда будет 27, и т.д. Со временем вы снова вернетесь к числу 1, и весь цикл будет повторяться до бесконечности. Количество уникальных значений, которые можно получить до повторения, называется периодом ГПСЧ. В данном случае период нашего ЛКГ равен 32.

Оценка ГПСЧ

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