Случайности не случайны

V Международный конкурс научно-исследовательских и творческих работ учащихся
Старт в науке

Личный портфель

Случайности не случайны

Неграш Д.А. 1
1МОУ "СОШ № 11" г. Воскресенск Московской области
Михайлова Г.С. 1
1МОУ "СОШ № 11" г. Воскресенска
Автор работы награжден дипломом победителя II степени
Диплом школьникаСвидетельство руководителя
Текст работы размещён без изображений и формул.
Полная версия работы доступна во вкладке "Файлы работы" в формате PDF

Введение

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

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

 

Задачи исследовательской работы:

  1. Провести терминологический анализ.
  2. Провести эксперимент по сбору случайных чисел и генерации псевдослучайных.
  3. Сравнить и проанализировать результаты экспериментов.

Актуальность исследовательской работы:

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

Основная часть

 

Случайность - философская категория, выражающая один из предельных видов (классов) взаимосвязей и взаимоотношений в мире, характеризующийся отсутствием прямых закономерных связей в поведении и функционировании объектов и систем [1]. Таким образом, появление случайного числа не может быть описано какой-либо закономерностью, то есть, не может быть предопределено или заранее известно. Следовательно, говоря о случайном событии, следует сказать и о вероятности события. Например: вероятность выпадения «орла» или «решки» в эксперименте бросания монеты в идеальных условиях одинакова и равна 50%, а вероятности выпадения чисел в диапазоне от 0 до 9 (цифры) так же одинаковы и равны 10%.

Идеальное распределение вероятностей появления чисел от 0 до 9

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

Математическая формула для вычисления вероятности события (то есть выпадения конкретной цифры, в нашем случае) имеет следующий вид:

 

,

 где P – вероятность события, Nп – число полезных исходов, Nо – число общих исходов

Второй термин, требующий анализа и обсуждения, - это псевдослучайное число, являющееся продуктом работы генератора псевдослучайных чисел. Генератор псевдослучайных чисел (ГПСЧ) - это алгоритм, порождающий последовательность чисел, элементы которой почти независимы друг от друга и подчиняются заданному распределению (обычно равномерному) [2]. Наиболее распространенными являются метод на основе полиномиального счетчика (сдвигового регистра) и линейный конгруэнтный метод, который используется в стандартной функции получения случайных чисел в большинстве языков программирования.

Впервые этот метод был предложен Лехмером в 1949 году. Выбирается 4 числа:

1.Модуль m (m>0);

2.Множитель a (0<=a<m);

3.Приращение c (0<=c<m);

4.Начальное значение X0 (0<= X0<m) [3].

Последовательность получается с использование следующей формулы: Xn+1=(a* Xn+c) mod m.

X0, a, m и с можно задать разными способами. Их можно получить случайным образом, используя физические генераторы шумов такие как, газоразрядные трубки или детекторы ионизирующей радиации, брать из готового (заранее подготовленного) списка, содержащего большое количество случайных чисел, или привязать получение к числу тактов процессора от момента последнего прерывания (сброса).

Однако «генерация случайных чисел слишком важна, чтобы оставлять её на волю случая» [4]. Этот афоризм знаменитого американского математика Роберта Кавью очень хорошо подходит для случая реализации генератора псевдослучайных чисел линейно-конгруэнтным методом.

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

Предположим, что случайные значения таковы: m=7, X0=1, a=2, c=4. Тогда

X1=(a* X0+c) mod m = (2*1+4) mod 7 = 6

X2=(a* X1+c) mod m = (2*6+4) mod 7 = 2

X3=(a* X2+c) mod m = (2*2+4) mod 7 = 1

X4=(a* X3+c) mod m = (2*1+4) mod 7 = 6

X5=(a* X4+c) mod m = (2*6+4) mod 7 = 2

X6=(a* X5+c) mod m = (2*2+4) mod 7 = 1

X7=(a* X6+c) mod m = (2*1+4) mod 7 = 6

Произошло зацикливание, а последовательность псевдослучайных чисел очень короткая. Вывод напрашивается сам собой: числа X0, a, m и с не могут быть случайными. Но, если задать эти числа жестко единожды, то имея значения четырех чисел из последовательности псевдослучайных чисел и решив систему уравнений:

X1=(a* X0+c) mod m

X2=(a* X1+c) mod m

X3=(a* X2+c) mod m

X4=(a* X3+c) mod m, можно восстановить значения исходных чисел и как следствие рассчитать любое число из последовательности псевдослучайных чисел. Возникает проблема предсказуемости.

В преодолении проблемы предсказуемости может помочь, например, использование внутренних системных часов для изменения последовательности случайных чисел. «Один из способов применения часов состоит в перезапуске последовательности после N чисел, используя текущее значение часов по модулю m в качестве нового начального значения. Другой способ состоит в простом добавлении значения текущего времени к каждому случайному числу по модулю m» [5].

Однажды Джон фон Нейман сказал, что «всякий, кто питает слабость к арифметическим методам получения случайных чисел, грешен вне всяких сомнений» [6]. Возможно ли, чтобы некий алгоритм смог генерировать случайные числа или числа, выглядящие как случайные для неспециалиста? Для получения ответа на этот вопрос было проведено небольшое исследование, которое состояло из трех экспериментов.

Практическая часть

  1. Эксперимент

Первый эксперимент состоял в сборе случайных чисел среди обучающихся и учителей нашей школы. Для этого была составлена анкета и проведен опрос с использованием сервиса Google-форма технологии Web2.0. В анкете предлагалось выбрать одну из 10 цифр. В опросе приняло участие более 130 респондентов (Приложение 1).

В среде Pascal ABC генератор псевдослучайных чисел реализуется через стандартную функцию Random. Поэтому второй эксперимент состоял в генерации псевдослучайных чисел с использованием программы, написанной в среде программирования Pascal_ABC.Net (Приложение 2).

В ходе анализа результатов первого эксперимента было принято решение о проведении дополнительного третьего эксперимента по сбору случайных чисел, заключающегося в проведении обычного опроса среди обучающихся 1-вых классов и технического персонала школы. Количество респондентов в третьем эксперименте – 93 человека.

  1. Анализ результатов эксперимента

Анализ результатов экспериментов проводился с помощью сервиса Google-таблицы технологии Web2.0, которая позволяет совместное создание и редактирование документов в облаке, с использованием статистической функции СЧЕТЕСЛИ и построением диаграмм. В Приложении 3 показаны диаграммы, отражающие результаты 1-го, 2-го и дополнительного 3-го эксперимента.

Анализ результатов первого эксперимента показал, что большинство респондентов остановило свой выбор на числе «5» и в немного меньшей степени числе «7». Вероятность появления числа «5» - 27 %, а «7» - 22,6%.

Во втором эксперименте генератор псевдослучайных чисел показал достаточно равномерное распределение. Возник вполне закономерный вопрос: Почему большинство респондентов отдали свои предпочтения числам 5 и 7? Рабочей гипотезой стало утверждение о том, что на выбор респондентов оказывали воздействие некоторые психологические аспекты: все респонденты напрямую или косвенно, связаны со школьной системой оценивания знаний, а число «5» выбрано как наиболее приятная и желаемая отметка, число «7» также ассоциируется с удачей, счастьем и воскресеньем (7-мым днем недели, выходным днем). Для проверки этой гипотезы и был проведен третий эксперимент по сбору случайных чисел.

Анализ результатов третьего эксперимента показал, что рабочая гипотеза нашла свое подтверждение: респонденты, несвязанные напрямую или косвенно с системой оценивания знаний, не проявили интереса к цифре «5» (14%), но отдали предпочтение цифре «7» (24%).

  1. Практическая значимость
  2. Результаты исследовательского проекта могут быть использованы на уроках информатики или занятий внеурочной деятельности в качестве иллюстративного материала.
  3. Работа в целом может стать частью большего исследования или основой для другого исследовательского проекта.

Выводы

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

  1. при получении случайного числа от респондента-человека с вероятностью около 40% будет названо число «5» или «7»;
  2. при эксперименте с генератором псевдослучайных чисел распределение вероятностей появления цифр достаточно однородно.

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

Список литературы

1. https://dic.academic.ru/dic.nsf/enc_philosophy/1107/%D0%A1%D0%9B%D0% A3%D0%A7%D0%90%D0%99%D0%9D%D0%9E%D0%A1%D0%A2%D0%AC (19.11.2017 9:48)

2. https://dic.academic.ru/dic.nsf/ruwiki/449830 (19.11.2017 10:02)

3. https://habrahabr.ru/post/132217/ (17.12.2017 10:12)

4. Генератор псевдослучайных чисел https://ru.wikipedia.org/ (04.02.2018 14:12)

5. https://www.intuit.ru/studies/courses/28/28/lecture/20414?page=6 (04.02.2018 14:53)

6. http://mipt1.ru/file.php?f=7_infosafe&id=22&all=1&dd=1 (19.11.2017 10:12)

Приложение 1.

Анкета-опрос «Случайное число»

Приложение 2.

Листинг программы:

program random_numbers;

var a:array[0..9] of integer;

 i,x:integer;

Begin

 For i:=1 to 130 do

 Begin

 x:=Random(10);

 inc(a[x]);

 End;

 For i:=0 to 9 do

 writeln(i,' - ', a[i]);

End.

Приложение 3.

Просмотров работы: 269