Понятие, история, разновидности генераторов

СОДЕРЖАНИЕ

 

АННОТАЦИЯ.. 3

ВВЕДЕНИЕ. 4

ГЛАВА I. ТЕОРЕТИЧЕСКИЕ ОСНОВЫ РАЗРАБОТКИ И РЕАЛИЗАЦИИ ПРИЛОЖЕНИЯ.. 6

1.1. Понятие, история, разновидности генераторов. 6

1.2. Понятие, назначение, основные компоненты, этапы создания оконного приложения. 13

1.3. Обзор подобных приложений. 16

ВЫВОДЫ ПО I ГЛАВЕ. 19

ГЛАВА II. ПРАКТИЧЕСКАЯ РАБОТА ПО ПРОЕКТИРОВАНИЮ И РАЗРАБОТКЕ ОКОННОГО ПРИЛОЖЕНИЯ ПО ТЕМЕ: «ГЕНЕРАТОР РАНДОМНЫХ ПРИЛОЖЕНИЙ». 20

1.1. Разработка приложения: «Генератор рандомных чисел». 20

1.2. Этапы разработки приложения «Генератор рандомных чисел». 20

ВЫВОДЫ ПО II ГЛАВЕ. 21

ЗАКЛЮЧЕНИЕ. 22

СПИСОК ЛИТЕРАТУРЫ.. 23

АННОТАЦИЯ

 

Объем курсовой работы – … стр.

Количество иллюстраций – … шт.

Количество таблиц – …шт.

Количество приложений – … шт.

Количество использованных источников – … шт.

Перечень ключевых слов: …

Полученные результаты: ….

 

 

ВВЕДЕНИЕ

 

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

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

Актуальность генераторов случайных чисел состоит в том, что они широко используются в процессе решения задач. К таким областям относятся статистическое моделирование и защита информации в ЭВМ и сетях. Для решения, задач которых необходимо вырабатывать огромные количества случайных чисел с самыми разнообразными свойствами. Генерация случайных чисел находит применение в большом количестве задач: в криптографии, в области численного моделирования, в игровой индустрии и т.д. В связи с расширением области применения компьютеров и быстрым развитием электронных сетей, число таких задач постоянно растет, а требования к качеству генерации постоянно ужесточаются. Эти случайности имеют наибольшее значение для практики так как от качества и быстродействия которых существенно зависят результаты решения поставленных задач. Генераторы случайных чисел делятся на программные и аппаратные. Для решения задач создания (выработки) ключевой информации применяются различного рода генераторы псевдослучайных чисел, которые делятся на два больших класса – программные и аппаратные. В аппаратных генераторах источником случайного процесса является шум в электронных приборах. Очевидно, применение аппаратных генераторов требует наличия специального оборудования. Обычно для генерации последовательности псевдослучайных чисел применяют компьютерные программы, которые на самом деле выдают детерминированные числовые последовательности, по своим свойствам похожие на случайные.

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

Цель проекта: разработать и реализовать приложение «Генератор рандомных чисел».

Объект проекта: оконное приложение «Генератор случайных чисел».

Предмет проекта: использование в качестве проведения статистических испытаний. Visual Studio (C#) как средство реализации оконного приложения.

Задачи проекта:

1. Рассмотреть учебную и учебно-техническую литературу по теме КР.

2. Рассмотреть понятие, историю, разновидности генераторов.

3. Рассмотреть понятие, назначение, основные компоненты, этапы создания оконного приложения. (описать основные инструменты Visual Studio)

4. Выполнить обзор подобных приложений.

5. Разработать приложение «Генератор рандомных чисел».

6. Описать этапы проектирования приложения «Генератор рандомных чисел».

Программные средства: Visual Studio (C#).

Целевая аудитория: приложение ориентированно для возрастной группы 16 - 25 лет для в процессе решения задач.

 

 

ГЛАВА I. ТЕОРЕТИЧЕСКИЕ ОСНОВЫ РАЗРАБОТКИ И РЕАЛИЗАЦИИ ПРИЛОЖЕНИЯ

 

Понятие, история, разновидности генераторов

 

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

Генераторы случайных чисел – ключевая часть веб-безопасности. Генераторы случайных чисел применяются как:

· Генераторы сессий(PHPSESSID)

· Генерация текста для капчи

· Шифрование

· Генерация соли для хранения паролей в необратимом виде

· Генератор паролей

Самым примитивным генератором случайных чисел генератором случайных чисел (ГСЧ) является монета. Издревле монету использовали для решения некоторых споров, при сложности сделать осознанный выбор. Но монета раньше далеко не всегда имела равномерные края и распределение веса (рис.1). Поэтому нельзя было считать, что этот ГСЧ генерирует независимую последовательность.

Более интересным представителем старинных генераторов случайных чисел является игральный кубик (рис.2). Древнейшие игральные кости возрастом около 5200 лет были найдены в Иране [1]. По своей сути он представляет собой генератор, способный генерировать последовательность от 1 до 6 с равной вероятностью (если у него не смещен центр тяжести). В 1890 году английский исследователь Фрэнсис Гальтон описал способ использования игровых костей для генерации случайных чисел в научных целях.

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

Для решения прикладных задач необходим большие массива данных. В 1939 М. Ж. Кендалл и Б. Бабингтон-Смит построили первую машину, генерирующую случайные числа для построения таблицы, содержащей 100000 случайных чисел. А через 16 лет корпорацией RAND, с использованием специальных устройств, была построена таблица из миллиона случайных чисел. Несмотря на оживление табличного метода в 1996 Марсальей, построившего 650 Мбайт случайных чисел, круг применимости таких таблиц очень узок

Гораздо большее распространение получили генераторы случайных чисел, генерирующие их в реальном времени. В 1951 году в компьютер Ferranti Mark 1 была включена программа, идея которой принадлежала А. Тьюрингу, генерирующая случайные числа, используя шум Резистора. А в 1957 году была изобретена машина ERNIE (Electronic Random Number Indicator Equipment), четвертая версия которой была представлена в 2004 году. Это устройство изначально предназначено для генерации номеров выигрышных облигаций в британской лотерее [2].

Задача получения «случайной» последовательности чисел с помощью компьютера на удивление сложна. Интуитивно это можно обосновать тем фактом, что философия цифровых систем и архитектура современных ЭВМ направлены на достижение абсолютной точности, на уничтожение даже намёка на неопределённость в результате работы. Хранимые и передаваемые данные заверяются контрольными суммами, электрические цепи дублируются.

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

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

Однако практическое применение «чистых» аппаратных ГСЧ ограничено следующими факторами:

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

· Во-вторых, статистические характеристики такой последовательности могут быть не самые лучшие – распределение не то или меняется со временем, ширина чисел меньше требуемой, тенденция выдавать нули чаще, чем единицы (англ. bias) и т.п.

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

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

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

Случайность.

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

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

2. Независимость: ни одно значение в последовательности не должно зависеть от других.

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

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

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

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

- тестирование алгоритмов;

- имитационное моделирование;

- некоторые задачи численного анализа;

- имитация пользовательского ввода.

Для получения случайных чисел можно использовать различные способы. В общем случае все методы генерирования случайных чисел можно разделить на аппаратные и программные. Устройства или алгоритмы получения случайных чисел называют генераторами случайных чисел (ГСЧ) или датчиками случайных чисел.

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

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

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

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

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

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

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

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

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

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

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

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

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

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