Случайные числа в программировании

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ…………………………………………………………………...……….3

ГЛАВА 1. СЛУЧАЙНЫЕ И ПСЕВДОСЛУЧАЙНЫЕ  ЧИСЛА.

 ГЕНЕРАТОРЫ  СЛУЧАЙНЫХ ЧИСЕЛ……………………...……….. 4

1.1.Определение  случайного и псевдослучайного числа.

Формы случайных чисел………………………………………........…....4

1.2.Генераторы  случайных  чисел (ГСЧ) и  их характеристика…...…..6

1.3.Аппаратные  ГСЧ……………………………………………...……....7

1.4. Табличные  ГСЧ…………………………….………………..…...…..9

1.5.Программные ГСЧ…………………………………………...……...10

1.6.Области применения случайных чисел…………………..………..15

ГЛАВА 2. СЛУЧАЙНЫЕ ЧИСЛА В PASCAL…………………………….……...16

2.1 Генератор случайных чисел в Pascal ABC……………….…….….16

     2.2. Рассмотрение примеров………………………………………….....19

ЗАКЛЮЧЕНИЕ…………………………………………………………………….....24

СПИСОК  ИСПОЛЬЗОВАНОЙ ЛИТЕРАТУРЫ………………………………......25 

     ВВЕДЕНИЕ

     Тема  курсовой работы: «Случайные числа  в программировании».

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

     Курсовая  работа состоит из двух основных частей: теоретической и практической. В  теоретической части будет рассмотрено понятие «случайного числа» и «псевдослучайного числа», понятие «генератора случайных чисел», применение случайных чисел, методы генерирования случайных  и псевдослучайные чисел. Немного истории о генерировании случайных чисел, а также  методе середины квадрата, Монте-Карло и других методах. В практической части – применение случайных чисел для решения задач на языке Pascal,применение метода Монте-Карло для решения задач.

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

ГЛАВА 1.

СЛУЧАЙНЫЕ И ПСЕВДОСЛУЧАЙНЫЕ  ЧИСЛА.

ГЕНЕРАТОРЫ  СЛУЧАЙНЫХ ЧИСЕЛ.

1.1.Определение  случайного и псевдослучайного  числа. Формы случайных  чисел.

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

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

Два основных требования к последовательности случайных  чисел - это случайность и непредсказуемость.

     Случайность

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

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

     Непредсказуемость

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

     Формы случайных чисел

1. Действительные значения. Генератор случайных чисел большинства компьютерных систем, возвращая результат в виде действительного числа, распределенного равномерно. Под равномерным распределением мы понимаем, что если мы возьмем два интервала одинаковой длины, не выходящих из диапазона генерируемых функцией значений, тогда результат с равной вероятностью попадет как в один, так и в другой из выбранных интервалов. Поскольку диапазон нашей функции лe жит в пределах от О до N , это определение означает, что вероятность того, что результат попадет в любой подинтервал, равный длине этого подинтервала. На диапазон генерируемых чисел обычно накладывается еще одно ограничение: 0 может появляться в качестве результата, но N  не может. В математических терминах область случайных чисел представляет собой полуоткрытый интервал [0,N).

2. Целочисленные  значения. Второй часто используемой формой случайных чисел являются целые числа. Мы, однако, не можем с полным правом говорить о случайных целых числах, поскольку количество целых чисел бесконечно, а в компьютере можно образовать лишь определенное их количество. Отсюда вероятность того, что истинно случайное целое окажется таким, что его можно получить в компьютере, равно О. Поэтому мы рассматриваем только целые числа в диапазоне между двумя целыми числами low и high, включительно. Для вычисления такого целого числа мы начинаем со случайного действительного числа из диапазона [0,1), умножаем его на low - high + 1, поскольку именно столько чисел содержится в требуемом диапазоне, усекаем результат до целого числа и добавляем low, чтобы поместить результат в требуемый диапазон целых чисел.

 3. Значения, распределенные по закону Пуассона. Третья, более изощренная форма случайных чисел. Такие числа носят название Пуассоновского распределения случайных целых чисел. Мы начинаем с положительного действительного числа, называемого математическим ожиданием v последовательности случайных чисел. Тогда если мы говорим, что последовательность неотрицательных целых чисел подчиняется распределению Пуассона с математическим ожиданием v, это означает, что на достаточно длинных подпоследовательностях среднее значение целых чисел в последовательности стремится к v.

     Если, например, мы начинаем с математического  ожидания 1.5, мы могли бы получить последовательность 1, О, 2, 2, 1, 1,3, О, 1,2, О, О, 2, 1, 3,4, 2, 3, 1, 1, Если вычислять средние значения для  под последовательностей этой последовательности, обнаружим, что иногда среднее будет меньше 1.5, иногда больше, но постепенно оно будет все больше приближаться к 1.5 [4, c. 663-670].  

     1.2.Генераторы  случайных  чисел  (ГСЧ) и их характеристика.

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

     Для получения случайных чисел можно  использовать различные способы. В  общем случае все методы генерирования  случайных чисел можно разделить  на аппаратные, табличные и программные. Устройства или алгоритмы получения случайных чисел называют генераторами случайных чисел (ГСЧ) или датчиками случайных чисел [11,c.38].      За эталон генератора случайных чисел принят такой генератор, который порождает последовательность случайных чисел с равномерным законом распределения в интервале (0; 1). За одно обращение данный генератор возвращает одно случайное число. Если наблюдать такой ГСЧ достаточно длительное время, то окажется, что, например, в каждый из десяти интервалов (0; 0.1), (0.1; 0.2), (0.2; 0.3), …, (0.9; 1) попадет практически одинаковое количество случайных чисел — то есть они будут распределены равномерно по всему интервалу (0; 1). Если генератор выдает числа, смещенные в какую-то часть интервала (одни числа выпадают чаще других), то результат решения задачи, решаемой статистическим методом, может оказаться неверным. Поэтому проблема использования хорошего генератора действительно случайных и действительно равномерно распределенных чисел стоит очень остро.

     Характеристики  ГСЧ

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

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

1.3.Аппаратные  ГСЧ

     Аппаратные  ГСЧ  (или по-другому их называют физические) представляют собой устройства, преобразующие в цифровую форму какой-либо параметр окружающей среды или физического процесса. Параметр и процесс выбираются таким образом, чтобы обеспечить хорошую «случайность» значений при считывании. Простым примером аппаратного (физического) генератора может служить урна с десятью одинаковыми шарами, на которых написаны цифры от 1 до 9. Если эти шары после перемешивания извлекать из урны по одному и считывать записанную на них цифру, возвращая шар назад перед следующим отбором, то последовательность полученная таким образом будет случайной.

     Очень часто используются паразитные процессы в электронике (токи утечки, туннельный пробой диодов, цифровой шум видеокамеры, шумы на микрофонном входе звуковой карты и т.п.). Формируемая таким  образом последовательность чисел, как правило, носит абсолютно  случайный характер и не может  быть воспроизведена заново по желанию  пользователя. Генерирование на ЭВМ таких случайных числовых последовательностей получило название «метод Монте-Карло» (по названию города, где расположена знаменитая рулетка, которую можно рассматривать как “генератор” случайных чисел).

     Почти все крупные производители микрочипов поставляют аппаратные ГСЧ с различными источниками энтропии¹, используя различные методы для их очистки от неизбежной предсказуемости. Однако на данный момент скорость сбора случайных чисел всеми существующими микрочипами (несколько тысяч бит в секунду) не соответствует быстродействию современных процессоров.

     В персональных компьютерах авторы аппаратных ГСЧ используют гораздо более быстрые источники энтропии, такие, как шум звуковой карты или счётчик тактов процессора. Сбор энтропии являлся наиболее уязвимым местом ГСЧ. Эта проблема до сих пор полностью не разрешена во многих устройствах (например, смарт-картах), которые таким образом остаются уязвимыми. Многие ГСЧ используют традиционные испытанные, хотя и медленные, методы сбора энтропии вроде измерения реакции пользователя (движение мыши и т. п.), как, например, в PGP и Yarrow, или взаимодействия между потоками, как, например, в Java secure random. Примеры источников энтропии приведены в таблице 1.1 [3].

     Таблица 1.1–Примеры ГСЧ и источников энтропии

Продолжение таблицы 1.1

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

Таблица 1.2– Случайные числа равномерно распределенные от 0 до 1

Случайные цифры								Равномерно распределенные  от 0 до 1 случайные числа
9	2	9	2	0	4	2	6	0.929
9	5	7	3	4	9	0	3	0.204
5	9	1	6	6	5	7	6	0.269
…								…

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

     1.5.Программные ГСЧ

       К программным ГСЧ относятся различные алгоритмы генерирования последовательности чисел, которая по своим характеристикам напоминает случайную. Для формирования очередного числа последовательности используются различные алгебраические преобразования. Одним из первых программных ГСЧ является метод средин квадратов (Среднеквадратичный метод), предложенный в 1946 г. Дж. фон Нейманом. Этот ГСЧ формирует следующий элемент последовательности на основе предыдущего путем возведения его в квадрат и выделения средних цифр полученного числа. Например, мы хотим получить 10-значное число, и предыдущее число равнялось 5772156649. Возводим его в квадрат и получаем 33317792380594909201; значит, следующим числом будет 7923805949. Очевидным недостатком этого метода является зацикливание в случае, если очередное число будет равно нулю.

     Некоторые ученые экспериментировали с методом  середин квадратов в начале 50-х  годов. Работая с четырехзначными  числами вместо десятизначных, Дж.Э. Форсайт испытал 16 различных начальных значений и обнаружил, что 12 из них приводят к циклическим последовательностям, заканчивающимся циклом 6100, 2100, 4100, 8100, 6100,…, в то время как две из них приводят к последовательностям, вырождающимся в 0. более интенсивные исследования, главным образом в двоичной системе счисления, провел Н.К. Метрополис. Он показал, что если использовать 20-разрядное число, то последовательность случайных чисел, полученная методом середин квадратов, вырождается в 13 различных циклов, причем длина самого большого периода равна 142.

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

     Линейный  конгруэнтный метод.

     В настоящий момент наиболее часто  применяется метод генерации  случайных чисел, основывающийся на использовании уравнения или по-другому он называется линейный конгруэнтный метод. Метод довольно старый–1950х годов. Разработал его Деррик Лемер. Этот метод использует следующее уравнение:

 
       При выполнении следующих условий: R>0, a>0, c>0, m>R , a и c.  Отметим, что Rn - это предыдущее число, а Rn+1 - следующее. Данный метод иногда называют линейным сравнительным методом. Формула так проста, что можно подумать, что генерировать случайные числа просто. Однако, это ловушка: насколько хорошо работает данная формула, очень сильно зависит от значения а, с и m. Модуль (m) должен быть довольно большим, так как он определяет область случайных чисел. Операция взятия по модулю порождает остаток от деления числа на модуль. Следовательно, 10 по модулю 4 равно 2. Таким образом, если модуль равен 12, то формулой порождаются числа от 0 до 11, а если модуль равен 21425, то порождаются числа от 0 до 21424. Выбор множителя а и приращения с является очень сложной задачей. В общем случае множитель может быть довольно большим, а приращение - маленьким. Множество попыток и проверок необходимо, чтобы создать хороший генератор.

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

 var 
      a1: integer;  
    function Ran1: real; 
    var 
      t: real; 
    begin 
      t := (a1*32749+3) mod 32749; 
      a1 := Trunc(t); 
      Ran1 := Abs(t/32749); 
    end;

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

     Во-вторых, начальное значение задается через  глобальную переменную а1. До первого вызова Ran1 переменная а1 должна быть установлена в 1.

В-третьих, в  Ran1 случайные числа делятся на модуль прежде, чем они будут возвращены функцией, для того, чтобы числа лежали в области от 0 до 1. Если поинтересоваться значением глобальной переменной а1 до возврата строки, то оно должно лежать в области от 0 до 32748. Следовательно, когда а1 делится на 32749, полученное число будет больше или равно 0 и меньше 1.

     Многие  генераторы случайных чисел не применимы, так как они порождают не равномерное  распределение или имеют короткий цикл повторения. Даже когда эти  недостатки не очень бросаются в  глаза, они могут породить смешанный  результат, если такой генератор  используется снова и снова. Решение  заключается в том, чтобы создать  различные генераторы и применять  их индивидуально или совместно  для получения более качественных последовательностей случайных  чисел. Применение нескольких генераторов  может сгладить распределение последовательности за счет уменьшения малых смешений отдельных генераторов. Далее приведена  функция генерирования случайных  чисел, называемая Ran2, которая порождает  хорошее распределение:   

var 
      a2:integer; { установить в значение 203 до первого вызова 
                    Ran2 } 
    function Ran2: real; 
    var 
      t: real; 
    begin 
      t := (a2*10001+3) mod 17417; 
      a2 := Trunc(t); 
      Ran2 := Abc(t/17417); 
    end; {Ran2}

     Оба этих генератора случайных чисел  порождают хорошие последовательности случайных чисел.

     Алгоритм Блюма, Блюма  и Шуба (Blum Blum Shub, BBS)

Предложен в 1986 году Ленор и Мануэлем Блюм и  Майклом Шубом.

BBS заключается  в применении следующей формулы:

     x_n+1 = (x_n)² modM          (1.2)

где M=p*q является произведением двух больших простых p и q.

На каждом шаге алгоритма выходные данные получаются из x_n путём взятия либо бита чётности, либо одного или больше наименее значимых бит x_n. И НОД(φ(p-1), φ(q-1)) должен быть мал [14].

     Интересной  особенностью этого алгоритма является то, что для получения x_n необязательно вычислять все n - 1 предыдущих чисел, если известно начальное состояние генератора x₀ и числа p и q. n-ное значение может быть вычислено "напрямую" используя формулу:

                                   (1.3)

     Метод Монте-Карло

     Метод Монте-Карло можно определить как  метод моделирования случайных  величин с целью вычисления характеристик  их распределений.

    Для того чтобы подробнее рассмотреть  этот метод посмотрим дополнительные теоретические сведения:

      Дискретной называют случайную  величину, которая принимает отдельные,  изолированные возможные значения  с определёнными вероятностями.  Число возможных значений дискретной  случайной величины может быть  конечным или бесконечным. 

    Математическим  ожиданием дискретной случайной  величины называют сумму произведений всех её возможных значений на их вероятность.

                                  ,

     где Х – случайная величина, - значения, вероятности которых соответственно равны .

     Математическое  ожидание приближённо равно (тем  точнее, чем больше число испытаний) среднему арифметическому наблюдаемых  значений случайной величины.

    Дисперсией (рассеянием) случайной величины называют математическое ожидание квадрата отклонения случайной величины от её математического  ожидания: .

    Средним квадратичным отклонением случайной  величины Х называют квадратный корень из дисперсии: .

    Сущность  метода Монте-Карло состоит в  следующем: требуется найти значение а некоторой изучаемой величины. Для этого выбирают такую случайную величину Х, математическое ожидание которой равно а:

      М(Х)=а.

    Практически же поступают так: производят n испытаний, в результате которых получают n возможных значений Х; вычисляют их среднее арифметическое и принимают x в качестве оценки (приближённого значения) a^*  искомого числа a:

                                              .

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