Рассказы о математике с примерами на языках Python и C

Елисеев Дмитрий Сергеевич

14. Так ли случайны случайные числа?

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

На языке Python вывести случайное число можно так:

import random

print(random.randint(0, 9))

Но как это работает? Задача вывода действительно случайного числа далеко не так проста как кажется. Чтобы вывести что-то на компьютере, это что-то надо сначала запрограммировать. Но очевидно, что задать формулой случайный, хаотический процесс,

невозможно — по определению формула и хаос противоречат друг другу. Именно поэтому числа на самом деле являются псевдослучайными — они лишь похожи на случайные, а в реальности являются результатом вполне конкретного алгоритма.

Одним из наиболее популярных и простых алгоритмов, является линейный конгруэнтный метод (linear congruential generator). Его формула проста:

Рассмотрим пример реализации на языке Python:

x = 123456789

m = 2**31 - 1

for p in range(10):

x = (1103515245 * x + 12345) % m

print(x)

Программа действительно выводит числа, которые вполне похожи на случайные: 295234770, 465300796, 1475666158, 588454008, 929838277, 50298429, 1089988954, 698778454, 2010473888, 36125306. Как нетрудно догадаться, при повторном запуске программы числа будут одни и те же. Чтобы числа не повторялись, такой генератор обычно инициализируют значением текущего системного времени.

Увы, такой генератор имеет определенные недостатки: во-первых, его последовательность рано или поздно начинает повторяться, во-вторых, он не является криптостойким — зная текущее значение, можно вычислить следующее, что к примеру, может позволить злоумышленнику узнать «случайно» сгенерированный пароль по его первым буквам.

Существуют другие алгоритмы генерации псевдослучайных чисел, например на основе простых чисел Мерсенна (Mersenne Twister generator). Существуют также аппаратные генераторы случайных чисел, например такая функция присутствует в процессорах Intel. Есть даже сайтс помощью которого можно сгенерировать случайную последовательность чисел. По заверениям авторов, они используют 3 радиоприемника, настроенных на частоту шума атмосферных помех.

Разумеется, в большинстве обычных программ, например при написании компьютерной игры, «качеством» случайных чисел можно пренебречь, встроенные алгоритмы вполне неплохи. Но при разработке специализированного ПО, где вопрос криптостойкости имеет значение, стоит уже обратить внимание на то, насколько надежен применяемый алгоритм.

15. Распределение случайных величин

С теорией вероятности связан еще один интересный момент — законы распределения случайных величин. Огромное количество процессов в реальности подчиняются всего лишь нескольким законам распределения.

Равномерное распределение

Возьмем игральный кубик и бросим его много раз. Очевидно, что вероятность выпадения каждого числа одинакова. На графике это можно изобразить примерно так:

Другим примером может быть время ожидания автобуса. Если человек пришел на остановку в случайное время, то период ожидания может быть любым, от нуля до максимума интервала движения.

Нормальное распределение

Возьмем группу людей, например в 100 человек, и измерим их рост. Очевидно, что будет некоторое количество людей небольшого роста, некоторое количество высоких людей, совсем мало очень высоких, и совсем мало очень низких. Такое распределение естественно для многих объектов, не только людей, потому оно и называется нормальным.

Формула нормального распределения совпадает с формулой Гаусса:

Подбирая коэффициенты, можно получить разные виды распределения.

Касаемо роста людей, согласно сайтуграфик роста для мужчин и женщин имеет следующий вид:

Распределение Пуассона

Следующий вид распределения не менее интересен. Рассмотрим события, происходящие с некоторой известной интенсивностью независимо друг от друга, например приход покупателей в магазин. Допустим, в магазин приходит в среднем 10 покупателей в минуту. Какова вероятность, что в какой-то момент времени в магазин придет 20 покупателей?

Вероятность таких событий описывается распределением Пуассона:

График распределения имеет примерно такой вид (в нашем примере = 10):

Этим же распределением описываются различные случаи, от вероятности неисправностей (если 0,01% телевизоров имеют неисправность, какова вероятность что в партии из 20 штук окажется 2 неисправных телевизора), до скорости роста колоний в чашке Петри.

Вернемся к нашему примеру с 20 покупателями. В интернете можно найти таблицы значений Пуассона для =10. По ним можно найти, что вероятность прихода сразу 20 человек составляет 0,19%.

16. Измерение скорости света

С бытовой точки зрения, скорость света практически мгновенна. Действительно, свет за секунду может обогнуть Землю 8 раз, а за 2 секунды пролетает расстояние от Земли до Луны. Поэтому до 17-го века про реальную скорость света никто не знал. Как же ее вычислили?

Сегодня опыт по измерению скорости света можно провести даже в школе — достаточно длинного куска кабеля, генератора импульсов и осциллографа. Действительно, задержка сигнала в куске кабеля длиной 50 м, будет равна 50/300000000, или 0,016 мкс — величина которую покажет даже дешевый осциллограф с максимальной частотой 10-20 МГц. Но как же это сделали в 17-м веке, когда не было не то что осциллографов, даже до появления лампы накаливания было еще 200 лет ожидания? Помогли астрономия, геометрия, и разумеется, математика.