Алгоритмічні методи генерації псевдовипадкових чисел за рівномірним законом розподілу. Методичні вказівки з Моделювання систем. Робота № 520454

Перехід до торгівельного партнера Binance

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

Інформація про навчальний заклад

ВУЗ:

Національний університет Львівська політехніка

Інститут:

Не вказано

Факультет:

Комп’ютерні науки

Кафедра:

Не вказано

Інформація про роботу

Рік:

2007

Тип роботи:

Методичні вказівки

Предмет:

Моделювання систем

Завантажити

Частина тексту файла (без зображень, графіків і формул):

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ "ЛЬВІВСЬКА ПОЛІТЕХНІКА" МОДЕЛЮВАННЯ СИСТЕМ МЕТОДИЧНІ ВКАЗІВКИ до виконання лабораторної роботи “Алгоритмічні методи генерації псевдовипадкових чисел за рівномірним законом розподілу” для студентів базового напрямку "Комп’ютерні науки" спеціальності “Інформаційні управляючі системи та технології” Затверджено на засіданні кафедри автоматизовані системи управління Протокол ( 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. Порядок виконання роботи Скласти програму, яка виконує наступні дії: генерує випадкові послідовності за мультиплікативним конгруентним методом, змішаним конгруентним методом, адитивний конгруентним методом за параметрами згідно індивідуального завдання (таблиця 6.1), будує гістограми функції густини закону розподілу для кожного з методів на основі отриманих випадкових послідовностей, Зробити висновок про поведінку гістограм при збільшенні розміру вибірки. Оформити звіт по результатах виконаної роботи. Зміст звіту Мета роботи. Основні теоретичні положення. Вихідні дані варіанту індивідуального завдання. Гістограми розподілів. Висновок за результатами проведеного аналізу. Роздруки отриманих даних. Текст програми. Контрольні запитання Основні переваги та недоліки методів генерації випадкових чисел. Як вибираються параметри конгруентних генераторів псевдовипадкових чисел? Як визначається період датчика? Порядок побудови гістограми. Варіанти індивідуальних завдань Таблиця 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 с.: ил. НАВЧАЛЬНЕ ВИДАННЯ МОДЕЛЮВАННЯ СИСТЕМ МЕТОДИЧНІ ВКАЗІВКИ до виконання лабораторної роботи “Алгоритмічні методи генерації псевдовипадкових чисел за рівномірним законом розподілу” для студентів базового напрямку "Комп’ютерні науки" спеціальності “Інформаційні управляючі системи та технології” Укладач: Кузьмін Олександр Васильович Редактор: Комп’ютерне верстання:

Методичні вказівки Моделювання систем

77pazan77

20.02.2013 20:02-

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, або зареєструйтесь.

Ділись своїми роботами та отримуй миттєві бонуси!

Маєш корисні навчальні матеріали, які припадають пилом на твоєму комп'ютері? Розрахункові, лабораторні, практичні чи контрольні роботи — завантажуй їх прямо зараз і одразу отримуй бали на свій рахунок! Заархівуй всі файли в один .zip (до 100 МБ) або завантажуй кожен файл окремо. Внесок у спільноту – це легкий спосіб допомогти іншим та отримати додаткові можливості на сайті. Твої старі роботи можуть приносити тобі нові нагороди!

поділитись