Реферат: Генератор случайных чисел - текст реферата. Скачать бесплатно.
Банк рефератов, курсовых и дипломных работ. Много и бесплатно. # | Правила оформления работ | Добавить в избранное
 
 
   
Меню Меню Меню Меню Меню
   
Napishem.com Napishem.com Napishem.com

Реферат

Генератор случайных чисел

Банк рефератов / Программирование

Рубрики  Рубрики реферат банка

закрыть
Категория: Реферат
Язык реферата: Русский
Дата добавления:   
 
Скачать
Microsoft Word, 1264 kb, скачать бесплатно
Заказать
Узнать стоимость написания уникального реферата

Узнайте стоимость написания уникальной работы

6 27 Генератор случайных чисел Содержание 1. Способы получения случайных чисел 3 2. Характеристики ГСЧ 5 3. Применение ГСЧ 6 4. Генерирование равномерно распределенных случайных чисел 9 5. Генерирование чисел с произвольным распределением 12 6. Тестирование ГСЧ 17 7. Генератор случайных чисел в Borland C ++ 21 8. Практические задания 23 8.1 Случайные числа в заданном диапазоне 23 8.2 Двумерные случайные величины 23 8.3 Генерация одномерной случайной величины 23 8.4 Оценить вероятность. 23 8.5. Медианы треугольника. 24 9. Лабораторные задания 25 9.1 ГСЧ фон Неймана 25 9.2 Случайная матрица 25 9.3 Площадь фигуры 26 9.4 Случайная величина с заданными свойствами 26 10. Дополнительные задания 27 10.1 Многомерные случайные величины 27 10.2 Быки и коровы 27 Библиографический список 28 1. Способы получения случайных чисел В программировании достаточно часто находят применение последовательн о сти чисел, выбранных случайным образом из некоторого множества. В качестве примеров задач, в которых используются случайные числа, можно привести сл е дующие: - тестирование алгоритмов; - имитационное моделирование; - некоторые задачи численного анализа; - имитация пользовательского ввода. Для получения случайных чисел можно использовать различные способы. В общем случае все методы генерирования случайных чисел можно разделить на а п паратные и программные. Устройства или алгоритмы получения случайных чисел наз ы вают генераторами случайных чисел (ГСЧ) или датчиками случайных чисел. Аппаратные ГСЧ представляют собой устройства, преобразующие в цифр о вую форму какой-либо параметр окружающей среды или физического процесса. П а раметр и процесс выбираются таким образом, чтобы обеспечить хорошую «случа й ность» значений при считывании. Очень часто используются паразитные процессы в электронике (токи утечки, туннельный пробой диодов, цифровой шум видеокамеры, шумы на микрофонном входе звуковой карты и т.п. ). Формируемая таким образом последовательность чисел, как правило, носит абсолютно случайный характер и не может быть воспроизведена заново по желанию пользов а теля. К программным ГСЧ относятся различные алгоритмы генерирования послед о вательности чисел, которая по своим характеристикам напоминает случайную. Для формирования очередного числа последовательности используются различные а л гебраические преобразования. Одним из первых программных ГСЧ является метод средин квадратов, предложенный в 1946 г . Дж. фон Нейманом. Этот ГСЧ формирует следующий элемент последовательности на основе предыдущего путем возведения его в квадрат и выделения средних цифр полученного числа. Например, мы хотим получить 10 - з начное число и предыдущее число равнялось 5772156649. Возводим его в квадрат и получаем 33317792380594909201; значит, следующим числом будет 7923805949. Очевидным недостатком этого метода является зацикливание в случае, если очередное число будет равно нулю. Кроме того, существуют и другие сравн и тельно короткие циклы. Любые программные ГСЧ, не использующие внешних «источников энтропии» и формирующие очередное число только алгебраическими преобразованиями, не дают чисто случайных чисел. Последовательность на выходе такого ГСЧ выглядит как случайная, но на самом деле подчиняется некоторому закону и, как правило, р а но или поздно зацикливается. Такие числа называются псевдослучайными. В дальнейшем мы будем рассматривать лишь программные генераторы псе в дослучайных чисел. 2. Характеристики ГСЧ Последовательности случайных чисел, формируемых тем или иным ГСЧ, должны удовлетворять ряду требований. Во-первых, числа должны выбираться из определенного множества (чаще всего это действительные числа в интервале от 0 до 1 либо целые от 0 до N ). Во-вторых, последовательность должна подчиняться опр е деленному распределению на заданном множестве (чаще всего распределение ра в номерное). Необязательным является требование воспроизводимости последов а тельности. Если ГСЧ позволяет воспроизвести заново однажды сформированную последовательность, отладка программ с использованием такого ГСЧ значительно упрощается. Кроме того, требование воспроизводимости часто выдвигается при и с пользовании ГСЧ в криптографии. Поскольку псевдослучайные числа не являются действительно случайными, качество ГСЧ очень часто оценивается по «случайности» получаемых чисел. В эту оценку могут входить различные показатели, например, длина цикла (количество итераций, после которого ГСЧ зацикливается), взаимозависимости между соседн и ми числами (могут выявляться с помощью различных методов теории вероятностей и математической статистики) и т.п. Подробнее оценка качества ГСЧ рассмотрена ниже. 3. Применение ГСЧ Одна из задач, в которых применяются ГСЧ, – это грубая оценка объемов сложных областей в евклидовом пространстве более чем четырех или пяти измер е ний. Разумеется, сюда входит и приближенное вычисление интегралов. Обозначим область через R ; обычно она определяется рядом неравенств. Предположим, что R – подмножество n - м ерного единичного куба K . Вычисление объема множества R м е тодом Монте-Карло сводится к тому, чтобы случайным образом выбрать в K бол ь шое число N точек, которые с одинаковой вероятностью могут оказаться в любой части K . Затем подсчитывают число M точек, попавших в R , т.е. удовлетворяющих неравенствам, определяющим R . Тогда M / N есть оценка объема R . Можно показать, что точность такой оценки будет довольно низкой. Тем не менее, выборка из 10 000 точек обеспечит точность около 1 % , если только объем не слишком близок к 0 или 1. Такой точности часто бывает достаточно, и добиться лучшего другими методами может оказат ь ся очень трудно. В качестве примера можно рассмотреть вычисление площади фигуры, зада н ной некоторой системой неравенств. Пусть фигура будет определена следующим образом: . Сначала необходимо определить прямоугольную область, из которой будут выбираться случайные точки. Это может быть любая область, полностью содерж а щая фигуру, площадь которой требуется найти. Возьмем в качестве исходной обла с ти прямоугольник с координатами углов (0; – 1) – (1 ; 1 ). Будем последовательно г е нерировать точки, равномерно распределенные внутри этого прямоугольника, и для каждой точки проверять неравенства, описывающие фигуру. Если точка удовлетв о ряет всем неравенствам, значит, она принадлежит фигуре. При достаточно большом числе таких экспериментов отношение числа точек N F , удовлетворяющих нераве н ствам, к общему числу сгенерированных точек N R показывает долю площади прям о угольника, которую занимает фигура. Площадь прямоугольника S R известна (в н а шем случае она равна 2), площадь фигуры S F вычисляется тривиально: . Очевидно, что для такой простой области можно легко посчитать область ч е рез определенный интеграл. Тем не менее, описанный метод применим и в случае гораздо более сложных фигур, когда рассчитать площадь другим способом стан о вится слишком сложно. Другим примером приближенного взятия определенного интеграла с помощью ГСЧ является вычисление объема шара в n - м ерном пространстве. Объем n - м ерного шара выражается формулой: , где Г ( z ) – некоторая гамма-функция, определяемая следующим соотношен и ем: Г ( z + 1)= z · Г ( z ), Г (1)=1. Таким образом, для натуральных z гамма-функция равна факториалу z . Для вычисления знаменателя можно воспользоваться известным значением : . Можно показать, что для шара единичного радиуса при увеличении размерн о сти n объем стремится к нулю. Наиболее просто это можно объяснить тем, что чи с литель растет со скоростью степенной функции, а знаменатель – с факториальной. Таким образом, для больших n метод вычисления через случайные числа будет д а вать значительные погрешности. 4. Генерирование равномерно распределенных случайных чисел Почти повсеместно используемый метод генерирования псевдослучайных ц е лых чисел состоит в выборе некоторой функции f , отображающей множество целых чисел в себя. Выбирается какое-нибудь начальное число х 0 , а каждое следующее число порождается с помощью рекуррентного соотношения: x k +1 = f( x k ) Число x k часто называется зерном (англ. seed ) ГСЧ и полностью определяет текущее с о стояние ГСЧ и следующее генерируемое значение. Поначалу функции f выбирались как можно более сложные и трудно понима е мые. Например, f ( x ) определялась как целое число, двоичное представление котор о го составляет средний 31 разряд 62 - р азрядного квадрата числа x (модификация м е тода средин квадратов). Но отсутствие теории относительно f приводило к катас т рофическим последствиям. Для метода средин квадратов это уже упоминавшееся зацикливание при обращении очередного числа в нуль. Поэтому уже довольно да в но перешли к использованию функций, свойства которых вполне известны. Всякая последовательность целых чисел из интервала (0, 2 31 – 1) должна содержать повтор е ния самое большое после 2 31
1Архитектура и строительство
2Астрономия, авиация, космонавтика
 
3Безопасность жизнедеятельности
4Биология
 
5Военная кафедра, гражданская оборона
 
6География, экономическая география
7Геология и геодезия
8Государственное регулирование и налоги
 
9Естествознание
 
10Журналистика
 
11Законодательство и право
12Адвокатура
13Административное право
14Арбитражное процессуальное право
15Банковское право
16Государство и право
17Гражданское право и процесс
18Жилищное право
19Законодательство зарубежных стран
20Земельное право
21Конституционное право
22Конституционное право зарубежных стран
23Международное право
24Муниципальное право
25Налоговое право
26Римское право
27Семейное право
28Таможенное право
29Трудовое право
30Уголовное право и процесс
31Финансовое право
32Хозяйственное право
33Экологическое право
34Юриспруденция
 
35Иностранные языки
36Информатика, информационные технологии
37Базы данных
38Компьютерные сети
39Программирование
40Искусство и культура
41Краеведение
42Культурология
43Музыка
44История
45Биографии
46Историческая личность
47Литература
 
48Маркетинг и реклама
49Математика
50Медицина и здоровье
51Менеджмент
52Антикризисное управление
53Делопроизводство и документооборот
54Логистика
 
55Педагогика
56Политология
57Правоохранительные органы
58Криминалистика и криминология
59Прочее
60Психология
61Юридическая психология
 
62Радиоэлектроника
63Религия
 
64Сельское хозяйство и землепользование
65Социология
66Страхование
 
67Технологии
68Материаловедение
69Машиностроение
70Металлургия
71Транспорт
72Туризм
 
73Физика
74Физкультура и спорт
75Философия
 
76Химия
 
77Экология, охрана природы
78Экономика и финансы
79Анализ хозяйственной деятельности
80Банковское дело и кредитование
81Биржевое дело
82Бухгалтерский учет и аудит
83История экономических учений
84Международные отношения
85Предпринимательство, бизнес, микроэкономика
86Финансы
87Ценные бумаги и фондовый рынок
88Экономика предприятия
89Экономико-математическое моделирование
90Экономическая теория

 Анекдоты - это почти как рефераты, только короткие и смешные Следующий
Девушка - парню:
- Сёма, а если бы была женская армия, ты бы меня стал ждать?
- Я бы в неё пошёл.
Anekdot.ru

Узнайте стоимость курсовой, диплома, реферата на заказ.

Обратите внимание, реферат по программированию "Генератор случайных чисел", также как и все другие рефераты, курсовые, дипломные и другие работы вы можете скачать бесплатно.

Смотрите также:


Банк рефератов - РефератБанк.ру
© РефератБанк, 2002 - 2016
Рейтинг@Mail.ru