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

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ…………………………………………………………………...……….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–Примеры ГСЧ и источников энтропии

     

	Источник энтропии	ГСЧ	Достоинства	Недостатки
/dev/random в UNIX/Linux	Счётчик тактов процессора, собирается во время аппаратных прерываний	LFSR, с хешированием выхода через SHA-1	Есть во всех Unix, надёжный источник энтропии	Очень долго  «нагревается», может надолго «застревать», либо работает как ГПСЧ
Yarrow от Брюса Шнайера	Традиционные  методы	AES-256 и SHA-1 маленького внутреннего состояния	Гибкий криптостойкий  дизайн	Медленный