WWW.INFO.Z-PDF.RU
БИБЛИОТЕКА  БЕСПЛАТНЫХ  МАТЕРИАЛОВ - Интернет документы
 


«научно-техническое направление Работу выполнили - ученицы 10з класса Лысова Елизавета и Юксина Мария Руководитель проекта – Сутула Надежда Андреевна ...»

ГБОУ Лицей № 1502 при МЭИ

Псевдослучайные числа и методы их генерации

научно-техническое направление

Работу выполнили -

ученицы 10з класса Лысова Елизавета и Юксина Мария

Руководитель проекта –

Сутула Надежда Андреевна

учитель информатики

Оглавление

TOC \o "1-3" \h \z \u Введение PAGEREF _Toc477619175 \h 3Основная часть PAGEREF _Toc477619176 \h 4Метод середины квадрата PAGEREF _Toc477619177 \h 5Линейно конгруэнтный метод PAGEREF _Toc477619178 \h 6Выводы PAGEREF _Toc477619179 \h 8Литература PAGEREF _Toc477619180 \h 9

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

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

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

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

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

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

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

Цель: разработать генератор псевдослучайных чисел

Задачи:

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

написание программы генерации псевдослучайных чисел использующий метод середины квадрата и линейно конгруэнтный метод в среде ABC Pascal;

написание программы с использованием линейно конгруэнтного метода в среде Lazarus.

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

Генератор псевдослучайных чисел – алгоритм, порождающий последовательность чисел; числа не возникают ниоткуда, а появляются в результате работы функции. У каждого ряда случайных чисел есть определённая зависимость. Компьютер — не человек, он не может придумать число, ему нужна функция, в которую он сможет по порядку подставлять числа, чтобы сгенерировать новое число. Из чего следует, что числа, сгенерированные компьютером, не могут быть полностью случайными. Компьютер использует определённые алгоритмы для генерирования псевдослучайных чисел. Нашей задачей стало обеспечить его таковыми. Существует множество способов получить ряд случайных чисел, но все они генерируют относительно случайные числа и рано или поздно зацикливаются. Итак, у нас получается ряд чисел, который повторяется через определённое количество итераций.

Проблемы генерации случайных чисел:





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

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

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

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

1. Если какой-нибудь член последовательности окажется равным нулю, то все последующие члены также будут нулями.

2. Последовательности имеют тенденцию "зацикливаться", т. е. в конце концов, числа образуют цикл, который повторяется бесконечное число раз.

Число, возводимое в квадрат, должно быть достаточно большим, если взять маленькое число использование данного метода будет неэффективным. Хотя, даже если взять большое число, велика вероятность того, что через несколько итераций число обнулится. Следовательно, прежде всего встаёт вопрос выбора начального значения.

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

Xn+1=(aXn+c) mod m, где m является количеством значений, из которых формируется последовательность чисел, лишь когда выполняются следующие условия:

Числа c и m взаимно простые;

b=a-1 кратно p, для каждого простого p, являющегося делителем m;

b кратно 4, если m кратно 4.

при этом выводимая линейная последовательность чисел периодична, период не превышает m.

Кроме того, есть ряд условий для выбора наиболее удачного значения m:

m должно быть достаточно большим, так как период ряда ПСЧ не больше m.

m не должно быть слишком большим, во избежание занятия большого объема памяти компьютера.

m>2.

Принято считать, что наиболее удачным значением для переменной m будет значение, как минимум, равное размеру слова ОС. Иными словами, для 32-разрядных ОС m выбирается 31 или 32 бита.

Таким образом, наложенные на переменную m ограничения ведут к сведению её рандомности к нулю.

Несмотря на то, что в настоящее время линейный конгруэнтный метод является одним из самых простых методов генерации псевдослучайных чисел, но и у него можно найти ряд серьезных недостатков:

легко предсказать зависимость между числами;

начальное значение генератора известно заранее и зависит от пользователя;

ограниченная периодичность ряда псевдослучайных чисел.

Программа может быть написана двумя методами:

Пользователь вводит переменные a, c, m, программа выводит периодичную последовательность псевдослучайных чисел;

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

При написании программы вторым методом (далее М2) необходимо разделить её на две части, выполняющие различные этапы для достижения результата. Изначально необходимо составить программу, назовём её П1, которая при вводе в нее переменной m находит множество возможных значений для переменных a и c, основываясь на уже описанных выше условиях их взаимосвязи, и формирует из них матрицы A и C соответственно. Здесь П1 должна запрашивать у пользователя границы области допустимых значений m, чтобы избежать нежелательно большого количества промежуточных и конечных результатов, а также учитывать возможные аномалии в случае некорректного ввода значения переменной. Следующая часть программы (далее П2) должна обработать данные массивов А и С, беря из них соответственно парные значения переменных а и с и подставляя их и введенное значение m в вышеописанную формулу. В итоге П2 выводит конечный результат в виде последовательности псевдослучайных чисел.

Таким образом псевдослучайные числа, полученные в результате П2, хотя и находятся более длинным способом, являются наиболее приближенными к понятию случайного числа. Чего нельзя сказать о первом методе (М1) формирования программы. В этом случае пользователь вводит значения всех необходимых переменных, а программа должна лишь найти результаты их подстановки в формулу. То есть большая часть переменных зависит от пользователя, который вводит неслучайные числа, из чего следует то, что выведенные в таком случае значения переменной X также не будут являться случайными.

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

ЛитератураГончарук В. С., Атаманов Ю. С., Гордеев С. Н. Методы генерации случайных чисел // Молодой ученый. — 2017. — №8. — С. 20-23.  

Дональд Э. Кнут. Глава 3. Случайные числа // Искусство программирования— 3-е изд. — М.: Вильямс, 2000. — Т. 2. Получисленные алгоритмы. — 832 с. 

Гнеденко  Б.В.  «Курс  теории  вероятностей»,  М.:  Наука,  1988.

Слеповичев И.И. Генераторы псевдослучайных чисел



Похожие работы:

«"УТВЕРЖДАЮ" И.О. Директора СПб ГБУ " Служба заказчика Администрации Кронштадтского района" _ Косицин Д.Ю.РЕГЛАМЕНТ Отдела технического контроля (надзора)Действия инженера при поступлении заявки на составлении сметной документации. Заявка поступившая от Заказчика регистрируется документов...»

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования"НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ ТОМСКИЙ ПОЛИТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ История Китая лекции Часть I Рекомендовано в качестве учебного пособия Редакционно-издательским советом Томского...»

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ АВТОНОМНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯНАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ ТЕХНОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ "МИСиС" Кафедра инжиниринга технологического оборудования А.Д. Зобнин Ме...»

«Проблемные вопросы Даниловского МР :В услуге "Реализация дополнительных общеобразовательных предпрофессиональных программ в области искусства" стоит направление "Декоративно-прикладное творчество", а МБОУ ДО ДШИ г.Данилова занимается по направлению "Живопись", соответственно это другие предметы, другие учебные планы. Буд...»

«"Биомеханика кошки" Автор: Осипова Ольга Сергеевна Россия, Мурманская область, г. Снежногорск, МБОУ ООШ № 269 ЗАТО Александровск, 9 класс Оглавление TOC \o 1-3 \h \z \u Глава 1. Кошка, биомеханика и д...»

«ПОЛИТИКА КОНФИДЕНЦИАЛЬНОСТИ. Администрация сайта капитал-авто.рф с уважением относится к правам посетителей Сайта. Мы безоговорочно признаем важность конфиденциальности личной информации посетителей нашего Сайта. Используя эт...»

«ФЕДЕРАЛЬНАЯ АНТИМОНОПОЛЬНАЯ СЛУЖБАПИСЬМО от 23 июля 2009 г. N АЦ/24234О РАЗГРАНИЧЕНИИ ПОНЯТИЙ РЕКЛАМА И ВЫВЕСКА ФАС России рассмотрела обращение о разграничении понятий вывеска и реклама с учетом внесения изменений в статью 3 Федерального зак...»

«"Утверждаю" _С.Г. Палий Директор МБОУ СОШ № 10 Протокол № _"" _ 2015 г. Программа Комплексной безопасности МБОУ СОШ №10 Калининград, 2015г. Программа комплексной безопасности МБОУ СОШ города Калининграда №10 Настоящая Программа разработан...»

«СОДЕРЖАНИЕ1.Перечень планируемых результатов обучения по дисциплине (модулю), соотнесенные с результатами освоения образовательной программы32.Место дисциплины (модуля) в структуре образовательной программы.63.Объем дисциплины (модуля) в зачетных единицах с указанием количества академи...»








 
2018 www.info.z-pdf.ru - «Библиотека бесплатных материалов - интернет документы»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 2-3 рабочих дней удалим его.