Будь умным!

У вас вопросы?
У нас ответы:) SamZan.net

ЛЬВІВСЬКА ПОЛІТЕХНІКА

Работа добавлена на сайт samzan.net:

Поможем написать учебную работу

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

Предоплата всего

от 25%

Подписываем

договор

Имя

Выберите тип работы:

Принимаю Политику конфиденциальности

Скидка 25% при заказе до 11.11.2024

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ

НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ "ЛЬВІВСЬКА ПОЛІТЕХНІКА"

МОДЕЛЮВАННЯ СИСТЕМ

МЕТОДИЧНІ ВКАЗІВКИ

до виконання лабораторної роботи

“Алгоритмічні методи генерації псевдовипадкових чисел за рівномірним законом розподілу”

для студентів базового напрямку "Комп’ютерні науки"

спеціальності “Інформаційні управляючі системи та технології”

Затверджено

на засіданні кафедри

автоматизовані системи управління

Протокол № 12-2006/2007

від 30.05.2007 року

Львів - 2007

МОДЕЛЮВАННЯ СИСТЕМ: Методичні вказівки до виконання лабораторної роботи “Алгоритмічні методи генерації псевдовипадкових чисел за рівномірним законом розподілу” для студентів базового напрямку “Комп'ютерні науки” спеціальності “Інформаційні управляючі системи та технології”.

Укл.: О.В. Кузьмін – Львів: Видавництво Національного університету “Львівська політехніка”, 2007 - 13 с.

Укладач: Кузьмін О.В., канд.техн.наук, доц.

Відповідальний за випуск: Шпак З.Я., канд.техн.наук, доц.

Рецензент: Різник В.В., док.техн.наук., проф.

1. Мета

Вивчення конгруентних методів генерації псевдовипадкових чисел за рівномірним законом розподілу на ЕОМ. Об’єм роботи: 4 години.

2. Теоретичні положення

2.1.1. Основні способи генерації псевдовипадкових чисел

Проблема моделювання випадкових величин, функцій і процесів належить до найважливіших проблем, які виникають у процесі синтезу та експлуатації імітаційних моделей складних систем. Основою для моделювання випадкових величин служить датчик псевдовипадкових чисел, рівномірно розподілених в інтервалі (0,1), з допомогою якого шляхом деяких перетворень можна моделювати різноманітні випадкові числа, функції та процеси. Псевдовипадкові числа, рівномірно розподілені в інтервалі (0,1), можна отримати з допомогою трьох основних способів - апаратного, табличного та алгоритмічного.

Апаратний спосіб для генерації випадкових чисел використовує електронні пристрої - генератори випадкових чисел, які служать зовнішніми пристроями ЕОМ. В основу таких генераторів покладено використання фізичного ефекту шумів в електронних і напівпровідникових приладах (так звані "генератори білого шуму") [1, c.96].

Табличний спосіб реалізується шляхом формування відповідного файлу, в якому записані конкретні значення послідовності випадкових чисел в оперативній або зовнішній пам'яті ЕОМ.

Алгоритмічний спосіб ґрунтується на формуванні випадкових величин в ЕОМ з допомогою спеціальних програм.

Переваги та недоліки зазначених способів наведені в табл. 2.1.

На практиці в основному віддають перевагу алгоритмічному способу генерації псевдовипадкових чисел.

Таблиця 2.1

Переваги та недоліки основних способів

генерації псевдовипадкових чисел

Спосіб	Переваги	Недоліки
Апаратний	Кількість чисел, які генеруються, необмежена. Використовується невелика кількість операцій ЕОМ. Не потребує місця в пам’яті ЕОМ	Потрібна періодична перевірка якості послідовності випадкових чисел. Повторення ідентичної послі-довності неможливе. Необхідно ви-користовувати спеціальний пристрій
Табличний	Перевірка якості послідовності виконується один раз - у процесі формування файлу. Можливе повторення ідентичних послідов-ностей випадкових чисел	Кількість чисел необмежена. При розміщенні в оперативній пам’яті файл займає багато місця. При розміщенні в зовнішній пам’яті зростає час звертання до файлу
Алгоритмічний	Перевірка якості послідовності виконується один раз - при випробуванні програми. Можливе багаторазове повторення послі-довності. Займає мало місця в пам’яті ЕОМ. Не використо-вуються зовнішні пристрої	Кількість чисел послідовності обмежена внаслідок періодичності датчика. Необхідні витрати машинного часу на отримання псевдовипадкових чисел

2.1.2. Вимоги до генераторів псевдовипадкових чисел,

рівномірно розподілених в інтервалі (0,1)

У процесі моделювання на ЕОМ програмна імітація випадкових дій довільної складності складається з двох основних етапів: генерації стандартного базового процесу та його подальшого функціонального перетворення. За базисний можна обрати довільний (зручний для моделювання) процес. При моделюванні на ЕОМ базовим процесом є послідовність чисел {хj} = х0, х1, …. xn – реалізації незалежних рівномірно розподілених в інтервалі (0,1) випадкових величин, тобто моделюється розподіл з функцією густини

та інтервальною функцією розподілу

з математичним сподіванням

та дисперсією

Отримати такий розподіл на цифрових ЕОМ неможливо, тому що вона оперує з п – розрядними числами з певним інтервалом дискретності. Тому на цифрових п – розрядних ЕОМ замість неперервної сукупності рівномірно розподілених в інтервалі (0,1) випадкових чисел використовують дискретну послідовність 2п випадкових чисел з того самого інтервалу, моделюючи, таким чином, квазірівномірний розподіл. Випадкова величина ξ, що має квазірівномірний розподіл в інтервалі (0,1), набуває значення хі = і/(2п – 1) з ймовірностями

Рі = (1/2)п, і = 0,2п – 1.

Математичне сподівання та дисперсія величин ξ

Ідеальну послідовність випадкових чисел на ЕОМ отримати неможливо внаслідок дискретності подання неперервних чисел і періодичності генерованої з допомогою алгоритмів послідовності. Тому програмні генератори генерують псевдовипадкові числа.

Ідеальний генератор псевдовипадкових чисел повинен задовольняти таким вимогам:

необхідно, щоб числа, які генеруються, були розподілені квазірівномірно;

числа послідовності мають бути статистично незалежними (тобто вони не повинні бути корельовані);

повинна існувати можливість відтворення послідовності псевдовипадкових чисел.

Доцільно, щоб генератор працював з мінімальними витратами часу та використовував мінімальний об’єм пам’яті ЕОМ.

У практиці моделювання для генерації псевдовипадкових чисел найчастіше використовуються рекурентні співвідношення першого та другого порядку:

Добру послідовність псевдовипадкових чисел породжує тільки така функція φ, графік якої “достатньо повно” заповнює одиничний квадрат, наприклад функція (рис. 2.1, а) - дробова частина а при достатньо великих цілих додатних значеннях А. Водночас функція (рис. 2.1, б) не може бути використана для генерації якісної послідовності псевдовипадкових чисел (якщо побудувати точки з координатами за псевдовипадковими числами з таблиці випадкових чисел, то вони будуть рівномірно розподілені в одиничному квадраті, а відповідні точки, побудовані за числами , будуть розташовані в площі, що обмежена кривою , і, крім того, з різною густиною).

Розглянуті умови є лише необхідними, але недостатніми, тобто при розгляді варіантів співвідношень, які можна використати як основу для побудови генератора, є можливість відразу відкинути неперспективні за ознакою заповнення одиничного квадрату. Для тих, які залишаться, необхідно провести додаткові перевірки з використанням різноманітних статистичних тестів.

Рис.2.1. Вплив функції  на якість генерованої

послідовності псевдовипадкових чисел

2.1.3. Методи отримання псевдовипадкових чисел

Метод серединних квадратів - це одна з перших процедур, яку запропонували в 1946р. Фон Нейман та Метрополіс. В наш час цей метод має лише історичний інтерес, тому що його роботу важко проаналізувати, працює він порівняно повільно й не дає статистично задовільних результатів. Наведемо основні кроки алгоритму, який реалізує даний метод:

Взяти довільне п - значне число.
Піднести це число в квадрат, і , якщо потрібно, доповнити його ліворуч нулями до 2п - значного числа.
Взяти n цифр з середини цього числа як наступне випадкове число.
Перейти до кроку 2.

Щоб отримати числа, рівномірно розподілені в інтервалі (0,1), достатньо промасштабувати (тобто поділити на 10n) результати, знайдені за допомогою описаного вище алгоритму. Обравши за початкове число 2152, в результаті роботи алгоритму отримаємо послідовність

...........................................................................................................

Масштабуючи, дістанемо 0,2152; 0,6311; 0,8287 і т.д.

Часто послідовність виявляється надто короткою:

У цій послідовності випадковість взагалі відсутня, тому що починаючи з другого числа весь час буде генеруватись 2500.

Конгруентні методи будуються на основі кількох рекурентних формул з використанням поняття конгруентності - порівнянності чисел по модулю. Два числа А та В конгруентні по модулю m (m - ціле число) тоді і лише тоді, коли існує таке ціле число К, що А - В = К m, або, іншими словами, при діленні на m числа А та В мають ідентичну остачу. Так, наприклад, 5~ 7 /mod 2/, 10 ~ 14 /mod 4/. Будь-який програмний генератор, що використовує функціональне співвідношення, є періодичним, тобто починаючи з деякого числа генерована послідовність повторюється.

Мультиплікативний конгруентний метод ґрунтується на використанні формули

де а, m – невід’ємні цілі числа.

Значення а, m і початкове значення х0 необхідно вибирати такими, щоб забезпечити максимальний період і мінімальну кореляцію між генерованими числами. Для двійкової машини значення модуля m=2b, для десяткової m=10d, де b, d - число відповідно двійкових (біт) та десяткових цифр у машинному слові використовуваної ЕОМ. При правильному виборі а та х0 максимальний період для двійкових машин , для десяткових . Для двійкових машин значення а вибирається з співвідношення , де Т - довільне ціле додатне; х0 - додатне непарне число. Для десяткової машини , де Q набуває одне із значень  (3, 11, 13, 19, 21, 27, 29, 37, 53, 59, 61, 67, 77, 83, 91); х0 - довільне непарне ціле, яке не ділиться на 5. Вибір модуля, який дорівнював би довжині машинного слова ЕОМ, приводить до прискорення роботи алгоритму, оскільки тоді обчислення остачі від ділення на m зводиться до виділення b молодших розрядів діленого, а перетворення цілого хі в раціональний дріб на інтервалі (0,1) здійснюється підстановкою ліворуч від хі двійкової або десяткової коми. Розглянемо приклад побудови датчика для 4 - розрядної двійкової машини. Використовуючи наведені раніше рекомендації, вибираємо b=4, х0=7 (0111), а=5 (0101):

Період генератора 2 4-2= 4

Змішаний конгруентний метод, який запропонував Томсон, використовує формулу

З обчислювальної точки зору змішаний метод складніший за мультиплікативний на одну операцію додавання, але можливість вибору додаткового параметра с дозволяє зменшити можливу кореляцію між генерованими числами.

Адитивний конгруентний метод працює за формулою

При х0 = 0 та х1 = 1 цей алгоритм призводить до послідовності Фібоначчі. Використання адитивного генератора, який працює за формулою

дає кращі результати, але потребує більшого обсягу пам’яті ЕОМ внаслідок необхідності збереження значень, проміжних між хі - к та хі. Якісно цей генератор працює при значенні к = 16.

Комбіновані методи генерують "ще більш випадкові" послідовності за рахунок зростання часу генерації. Так, наприклад, можна використати два генератори псевдовипадкових чисел, які генерують відповідно послідовності х0, х1, ..., хn та у0, у1, ...,yn псевдовипадкових чисел, що мають значення від нуля до m-1, незалежними способами і отримати вихідне псевдовипадкове число із співвідношення

При цьому бажано, щоб довжини періодів {xn} {yn} були взаємно простими числами.

Розглянуті методи отримання псевдовипадкових чисел мають певні переваги та недоліки, що дозволяє в кожному конкретному випадку обрати найбільш доцільний метод. Крім того, генератори псевдовипадкових чисел чутливі до вибору початкових значень і констант. Найчастіше в моделюванні застосовується звичайний мультиплікативний генератор, який має високі статистичні характеристики та швидкодію.

2.1.4. Побудова гістограми

Гiстограма являє собою емпіричний аналог функції густини закону розподілу f(x). Побудова гістограми відбувається наступним чином:

Визначаємо попередню кількість інтервалів розбиття осі абсцис К за формулою

заокруглюючи отримане число до найближчого більшого цілого.

Визначаємо довжину інтервалів за формулою

x = (xmax - xmin)/K

Для зручності обчислень значення можна дещо скоректувати.

Середину області зміни вибірки приймаємо як центр деякого інтервалу (xmax - xmin)/2, після чого знаходимо межі та остаточну кількість інтервалів таким чином, щоб вони в сукупності перекривали цілу область від xmin до xmax.
Підраховуємо кількість спостережень Nm, які потрапляють в кожен інтервал: Nm дорівнює числу членів варіаційного ряду, для яких справедлива нерівність xm  xi  xm + x, де xm , xm + x - межі т-го інтервалу. Значення xi, які потрапляють на межу між т-м та (т-1)м інтервалами, відносимо до т - го інтервалу.
Підраховуємо відносну кількість спостережень Nm/N, які потрапляють в даний інтервал.
Будуємо гістограму, яка являє собою криву зі сходинок, значення якої на т-му інтервалі (xm, xm + x) постійне та дорівнює Nm/N.

Порядок виконання роботи
1. Скласти програму, яка виконує наступні дії:
- генерує випадкові послідовності за мультиплікативним конгруентним методом, змішаним конгруентним методом, адитивний конгруентним методом за параметрами згідно індивідуального завдання (таблиця 6.1),
- будує гістограми функції густини закону розподілу для кожного з методів на основі отриманих випадкових послідовностей,
1. Зробити висновок про поведінку гістограм при збільшенні розміру вибірки.
2. Оформити звіт по результатах виконаної роботи.

Зміст звіту
1. Мета роботи.
2. Основні теоретичні положення.
3. Вихідні дані варіанту індивідуального завдання.
4. Гістограми розподілів.
5. Висновок за результатами проведеного аналізу.
6. Роздруки отриманих даних.
7. Текст програми.

Контрольні запитання
1. Основні переваги та недоліки методів генерації випадкових чисел.
2. Як вибираються параметри конгруентних генераторів псевдовипадкових чисел?
3. Як визначається період датчика?
4. Порядок побудови гістограми.
Варіанти індивідуальних завдань

Таблиця 6.1

Варіант	Значення початкових даних генераторів
	Х0	Х1	А	С	В
1	10253	275211	09865	10041	16
2	04527	21045	10057	05701	17
3	11429	22153	02359	14277	18
4	22111	24765	09867	00555	19
5	12121	25567	12353	21333	20
6	02263	00329	2І35І	31575	21
7	10133	21359	30899	01267	22
8	12999	01977	21455	08989	23
9	00579	15467	21579	30211	24
10	10101	15743	24211	03999	25
11	21297	11757	03397	12567	26
12	15677	39975	21987	31197	27
13	09899	10677	12777	21879	28
14	10119	31479	09753	21689	29
15	10975	29545	29677	07987	30
16	31755	21655	17577	21567	31

Література
Советов Б.Я., Яковлев С.А. Моделирование систем: Учебник для вузов по спец. “Автоматизированные системи управления”. -М.: Высш. шк., 1985. – 271 c., ил.
Шеннон Р. Имитационное моделирование систем - искусство и наука.-М.:Мир, 1978. – 418 с.: ил.

НАВЧАЛЬНЕ ВИДАННЯ

МОДЕЛЮВАННЯ СИСТЕМ

МЕТОДИЧНІ ВКАЗІВКИ

до виконання лабораторної роботи

“Алгоритмічні методи генерації псевдовипадкових чисел за рівномірним законом розподілу”

для студентів базового напрямку "Комп’ютерні науки"

спеціальності “Інформаційні управляючі системи та технології”

Укладач: Кузьмін Олександр Васильович

Редактор:

Комп’ютерне верстання:

1. Российская Империя в XVIII веке
2. Византия Золотой мост в истории христианской цивилизации
3. тематики и программирования ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ Государственное образо
4. да или нет на следующие вопросы- Я хотел бы в большей степени контролировать свои мысли
5. Цивилизация Ацтеки. Особенности ее культуры
6. Лабораторная работа 3 ИЗУЧЕНИЕ ПЕРСОНАЛЬНЫХ СРЕДСТВ ЗАЩИТЫ ИНФОРМАЦИИ НА ПРИМЕРЕ ПРОГРАММНОГО СРЕДСТВА К
7. Методики исследования агрессивности
8. ЗубовоПолянская гимназия Согласовано Руководитель ШМО -Н..
9. хлитровый и 7литровый кувшины добейся того чтобы в одном из них находился один литр компота 3 литра компота
10. 00 ПОМИДОРЫ ОГУРЦЫ КАПУСТА ПЕРЕЦ Суп ГОРОХОВЫЙ С 300
11. Влияние водных растворов аминокислот на пищевое поведение моллюска большого прудовика
12. статьями 34 и 36 ФЗ 52 от 30
13. Биохимия
14. 923. А.Н.Гришанов ТАНАТОЛОГИЯ НАРЦИССИЧЕСКОЙ ЛИЧНОСТИ В статье рассматриваются отношения личн
15. . Структура Бершадської міжрайонної державної податкової інспекції
16. Субъективные средства защиты в адаптационный период связанный с вредными и опасными факторами
17. экономический институт Ректор акад
18. модуль Схемадопуск II модуль Альбом Зачет
19. Сонатная форма в эволюционном развитии
20. Государственность Древней Руси IXXII веков

Материалы собраны группой SamZan и находятся в свободном доступе