Мастер-класс: «Генерация случайных чисел»

Автор: Коновальцева Ольга Сергеевна

учитель информатики МБУ «Школа №93» г.о.Тольятти

 

1.      Прежде, чем начать свой  мастер-класс, предлагаю вам посмотреть небольшой видеосюжет.

Демонстрация отрывка из мультипликационного фильма «Кунг-фу Панда».

 

2.      Итак, случайности – не случайны. Сегодня мне хотелось бы поговорить о генерации случайных чисел.

Презентация: слайд №1

 

3.    Есть строгое определение для случайной величины. Случайная величина — это величина, которая принимает в результате опыта одно из множества значений, причём появление того или иного значения этой величины до её измерения нельзя точно предсказать.

Презентация: слайд №2

- А как вы думаете, что можно считать простейшим генератором случайных чисел?

- Простые игральные кости (также распространено название «дайс» и зары (зарики)), широко использовавшиеся в азартных играх в прошлом и в настольных играх в настоящее время. Доподлинная дата появления игральной кости неизвестна. Древнейшие игральные кости возрастом около 5200 лет были найдены в Иране вместе с комплектом для игры в нарды; метки на гранях костей практически не отличаются от современных.

 Презентация: слайд №3

4.      А давайте прямо сейчас сгенерируем с помощью «зариков» несколько случайных чисел. Каждому члену фокус-группы (6 человек) предлагается кинуть кубик один раз. Результат записывается на доске. Получается шестизначное число (постоянная а).

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

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

Презентация: слайд №4

Сгенерируем с помощью лототрона еще несколько случайных чисел. Желающие достают три шарика. Результат записывается на доске. Получается трехзначное число (постоянная m).

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

5.      Для автоматической генерации больших массивов данных современная информатика широко использует псевдослучайные числа.

Псевдослучайные числа — алгоритмически вырабатываемая последовательность чисел, обладающих свойствами случайных чисел и используемых взамен последних при решении на ЭВМ ряда классов задач.

Презентация: слайд №5

Вопрос залу:

- Что значит алгоритмически?

- Значит, выполняя какую-либо последовательность команд, инструкций, действий.

 6.   Я предлагаю фокус-группе (две группы по 3 человека) выполнить следующие алгоритмыЖ

 Для группы №1:

·         Задумайте число.

·         Запишите его на бланке ответа №1.

·         Отнимите 1.

·         Остаток удвойте.

·         Прибавьте первоначально задуманное число.

·         На бланке ответа №2 укажите получившийся результат.

Презентация: слайд №6

 

Для группы №2:

• Прибавьте к результату 2.
• Сумму разделите на 3.
• Частное — задуманное число.
• На бланке ответа укажите задуманное число.

Вопрос к группе №2

-Скажите, пожалуйста, как вам удалось угадать, казалось бы, случайно сгенерированное число вашего оппонента?

-Совершенно верно, вам был известен алгоритм разгадывания чисел.

 

Презентация: слайд №7

7.      Конечно же, это известный арифметический фокус. Но в основе большинства известных генераторов псевдослучайных чисел определенно лежит алгоритм.

Можно сказать, что ГСЧ = ГПСЧ + источник энтропии.

Источники энтропии используются для накопления энтропии с последующим получением из неё начального значения (initial value, seed), необходимого генераторам случайных чисел (ГСЧ) для формирования случайных чисел. ГПСЧ использует единственное начальное значение, откуда и следует его псевдослучайность, а ГСЧ всегда формирует случайное число, имея в начале высококачественную случайную величину, предоставленную различными источниками энтропии.
Энтропия – это мера беспорядка. Информационная энтропия — мера неопределённости или непредсказуемости информации.

Существует ряд алгоритмов для генерации случайных чисел. В состав стандартных библиотек практически всех языков программирования входит линейный конгруэнтный генератор

(данный метод иногда называют линейным сравнительным методом, Д.Г.Лемер 1949 год). Несмотря на свою простоту, этот генератор иногда оказывается достаточно хорош.

Xk+1  - очередное случайное число 

a, c и m  - константы 

m = 2e  e – длина машинного слова

Xk  - предыдущее случайное число

Презентация: слайд №8

Пусть генератор выдал несколько случайных чисел X0, X1, X2, X3. Получается система уравнений:


Презентация: слайд №9

Решив эту систему, можно определить коэффициенты a, c, m, и как следствие предугадать следующее число, которое будет сгенерировано.

8.      Давайте проделаем следующий опыт. В среде adc pascal я предварительно составила программу-генератор, работающую по этому алгоритму. Сгенерировав с помощью этой программы 3 числа, попробуем угадать четвертое.

Для этого:

·         воспользуемся нашими числами для величин a, c и m;

·         подставим значения в формулу;

·         произведем расчет;

·         запишем результат.

Каждая фокус-группа получает бланки для расчета.

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

И это еще одно доказательство алгоритмического принципа работы генераторов случайных чисел.

9.      Обман интернет-казино — группа мошенничеств, в которых жертва завлекается предложением быстро и легко зарабатывать деньги, обыгрывая интернет-казино. Реклама такого способа заработка утверждает, что существует способ, с помощью которого можно гарантированно выигрывать деньги в интернет-казино, и что автор рекламного сообщения готов поделиться этим способом на определённых условиях или безвозмездно. В результате жертва лишается денег, которые вложила в эту авантюру.

Во многих казино есть так называемая «партнёрская программа», суть которой в том, что тот, кто привлекает в онлайн-казино новых игроков, получает часть проигранных ими денег. Такой заработок является настоящей целью многих мошенников, утверждающих, что они знают способ обмануть казино. Кроме казино деньги с этого имеют те, кто распространяет мошеннические предложения.

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

Никогда не забывайте, что

СЛУЧАЙНОСТИ НЕ СЛУЧАЙНЫ!