Програмне генерування РВП0 1

Рефераты по информатике » Програмне генерування РВП0 1 Скачать

Національний Університет Біоресурсів і Природокористування


Кафедра економічної кібернетики


Курсова робота:

«Програмне генерування РВП(0; 1)»


Виконав

Студент 4-го курсу 3-ї групи

Лєвошко Д. М.


Київ - 2009


Зміст


Вступ

Способи генерування рівномірної випадкової послідовності

Табличний спосіб

Фізичне генерування

Програмний спосіб

Моделювання випадкових величин

Програмне генерація РВП(0; 1)

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

Визначення якості генераторів

Використання декількох генераторів

Висновок

Список використаної літератури


Вступ


Алгоритмічне (імітаційне) моделювання — це числовий метод дослідження систем і процесів за допомогою моделюючого алгоритму.

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

Послідовності випадкових чисел використовуються в програмуванні в найрізноманітніших випадках починаючи з моделювання (це найбільш часте вживання) і кінчаючи іграми і іншим розважальним програмним забезпеченням. Турбо Паськаль містить вбудовану функцію звану Random яка генерує випадкові числа. Random - це чудовий генератор випадкових чисел але для деяких вживань вам може потрібно два або більш різних генераторів для забезпечення різних наборів випадкових чисел для різних завдань. Тому в даній курсовій роботі Random буде порівняний з двома іншими генераторами Ran1 і Ran2 та створено генератор що поєднує роботу трьох генераторів.

Отже метою даної курсової роботи є дослідити методи програмного генерування рівномірно розподіленої випадкової послідовності на проміжку (0; 1). Та проаналізувати роботу деяких вже існуючих програмних генераторів РВП порівнявши їх з створеними генераторами Ran1 і Ran2.

Завдання курсової роботи:

- ознайомитися із способами генерування РВП(0; 1);

- вивчити програмні способі генерування випадкової послідовності;

- розглянути моделювання випадкових величин за допомогою чисел РВП(0; 1);

- ознайомитися з принципом роботі деяких генераторів РВП проаналізувати якість їх роботи та створити генератор що поєднує роботу кількох генераторів тим самим генеруючи більш якісну послідовність.


1. Способи генерування рівномірної випадкової послідовності


1.1 Табличний спосіб


Основна проблема в методі Монте-Карло полягає в тому щоб дістати рівномірну випадкову послідовність чисел РВП розподілених на відрізку [0 1]. При побудові стохастичних імітаційних моделей ці числа дають змогу генерувати випадкові події або випадкові величини з довільним розподілом. У разі коли для програмної реалізації використовуються мови моделювання (GPSS симула тощо) що забезпечені вмонтованими генераторами випадкових послідовностей чисел програмістові немає потреби розробляти програми утворення таких чисел. Крім того бібліотеки більшості ЕОМ включають спеціальні стандартні підпрограми котрі можна використати з відповідною метою.

Проте в організаціях які ще не мають достатнього досвіду створення імітаційних моделей програмісти часто стикаються з тим що потрібні їм стандартні підпрограми або взагалі не включені до бібліотеки стандартних підпрограм або містять численні помилки. Тому виникає необхідність створювати програми породження РВП [0 1].

Існують три способи дістати рівномірну випадкову послідовність чисел розподілених на відрізку [0 1]: табличний програмний і фізичне генерування.

Фізичний пристрій чи програма на ЕОМ породження РВП [0 1] називається генератором (датчиком) випадкових чисел.

Табличний спосіб одержання РВП [0 1] полягає ось у чому. Існують розроблені з допомогою фізичних або програмних датчиків спеціальні таблиці випадкових цифр. У процесі машинної імітації використовуються здебільшого випадкові числа у загальноприйнятій десятковій системі числення. Тому для створення випадкового числа у вигляді десяткового дробу із заданою кількістю значущих цифр після коми достатньо із будь-якого місця таблиці вибрати підряд потрібну кількість випадкових цифр. У табл. Д.1 наведено 2200 випадкових цифр або 440 п’ятиёрозрядних випадкових чисел. Почавши наприклад з першого випадкового числа сформуємо серію трирозрядниих РВП [0 1]: 0 104; 0 802; 0 236; 0 824; 0 130 і т.д.

Зауважимо що табличний метод у користуванні має як переваги так і недоліки.

Переваги табличного методу:

1) числа можна діставати з надвисокою швидкістю якщо таблицю записано в оперативну пам’ять;

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

3) забезпечується одноразова перевірка якості випадкових чисел.

Недоліки табличного методу:

1) таблиця займає багато місця в оперативній пам’яті;

2) запас чисел обмежений;

3) необхідна зовнішня пам’ять.

Тепер розроблено чимало таблиць випадкових цифр. У таблицях що належать до ГОСТ 11.003-73 «Прикладна статистика. Рівномірно розподілені випадкові числа» наведено 8192 випадкові десяткові цифри. У світі відомі нині такі таблиці зі значно більшою кількістю цифр. Наприклад фірма РЕНД (США) з допомогою спеціальної електронної апаратури побудувала таблицю що містить близько мільйона цифр. Ця таблиця записана на магнітну стрічку що дає змогу вводити цифри в пам’ять швидкодіючої ЕОМ.

Проте табличний метод породження РВП [0 1] з огляду на повільний увід табличних даних у пам’ять ЕОМ і необхідність використовувати значний обсяг пам’яті щоб зберігати їх для машинної імітації вважається неефективним і застосовується здебільшого для ручних розрахунків. У дослідженнях на ЕОМ він застосовується нечасто насамперед для налагодження програм або дублювання особливо важливих дослідів.


1.2 Фізичне генерування


До появи ЕОМ як генератори випадкових чисел використовувалися різні механічні пристрої — колесо рулетки спеціальні гральні кості та пристрої які перемішували фішки з номерами що витягувалися вручну по одній. Деякі з таких засобів дають цілком задовільні результати в разі невеликої кількості фішок або чисел.

Останнім часом фізичне генерування РВП [0 1] базується на використанні формули згідно з якою при генеруванні наступного m-розрядного випадкового двійкового числа необхідно дістати m реалізацій випадкової величини Z що набуває значення 0 або 1 з однаковою ймовірністю 0 5.

Реалізації випадкової величини Z можна дістати скориставшись такими фізичними явищами:

радіоактивне випромінювання;

власні шуми електронних ламп.

Радіоактивне випромінювання. Сутність методу що грунтується на радіоактивному випромінюванні полягає ось у чому.

1. Вибирається джерело радіоактивного випромінювання з інтенсивністю .

2. Залежно від значення вибирається відрізок часу .

3. За допомогою лічильника визначається кількість частинок що їх випромінює джерело за час .

4. Застосовується схема:

1) якщо кількість частинок парна то = 0;

2) якщо кількість частинок непарна то = 1.

Примітка. Лічильник частинок працює у двійковій системі числення тому значення — число молодшого розряду.

Щоб дістати m-розрядне випадкове двійкове число достатньо m разів звернутися до лічильника радіоактивних частинок.

Власні шуми електронних ламп. Власними шумами електронних ламп називають явище існування вихідної напруги U при нульовій вхідній. Посилюючи власні шуми можна дістати реалізацію стаціонарного випадкового процесу U(t)(рис.1.1).


Рис. 1.1. Графік функції U (t) (власні шуми електронних ламп)


Попередньо вибирають деякий рівень відсікання a для якого в довільний момент часу t маєвиконуватись умова



Випадкова величина імітується за схемою


(1)


Щоб дістати m-розрядне випадкове двійкове число РВП [0 1] досить провести m вимірюваньшуму лампи в моменти часу і скористатися перетворенням (1).

Послідовність квазірівномірних випадкових чисел за допомогою фізичного генерування утворюється спеціальними електронними приставками до ЕОМ — фізичними генераторами випадкових чисел. Для знаходження наступного випадкового числа РВП [0 1] при проведенні машинних розрахунків досить один раз звернутися до цього пристрою.

Переваги методу фізичного генерування:

1) швидкість здобування чисел надвисока (проміжок часу звертання до електронного пристрою ЕОМ дуже малий);

2) місця в оперативній пам’яті не займає;

3) запас чисел не обмежений.

Недоліки методу фізичного генерування:

1) не можна повторити спроби (немає змоги фізичний датчик зафіксувати на певному випадковому числі);

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

3) необхідно мати спеціальний пристрій до ЕОМ.

Фізичне генерування випадкових чисел використовується здебільшого там де дуже часто розв’язуються задачі методом Монте-Карло. Проте останніми роками навіть за цих умов надається перевага програмним генераторам випадкових чисел.


1.3 Програмний спосіб


При програмному способі наступне випадкове число дістають за допомогою рекурентного співвідношення



Генеровані так випадкові числа називаються псевдовипадковими (псевдо... від грец. — обман вигадка помилка; відповідає поняттям «несправжній» «неправильний») оскільки між двома сусідніми числами існує залежність. Функцію вибирають складною що включає логічні перетворення аби згадана залежність практично не впливала на результат.

Один із перших алгоритмів утворення випадкових чисел за допомогою рекурентного співвідношення — метод серединних квадратів запропонований 1946 року фон Нейманом і Метрополісом. Сутність його розкриємо спочатку на прикладі а далі розглянемо загальний випадок.

Приклад.

Загальний випадок.

Нехай — m-розрядне двійкове число (0 < < 1) причому — парне. Загальний вигляд:



де коефіцієнти набувають значення 0 або 1.

Квадрат цього числа



Виокремимо середні розряди цього числа і покладемо



Як показали статистичні випробування утворювані таким способом випадкові числа мають розподіл близький до РВП [0 1]. Очевидний недолік методу серединних квадратів полягає ось у чому. У разі відсутності заміни нульового значення випадкового числа котре може зявитися в результаті наступної спроби якимось іншим усі наступні числа послідовності будуть нулями.

Можливе циклічне повторення й інших цифр. Нехай наприклад потрібно дістати серію випадкових чотирицифрових десяткових чисел методом серединних квадратів. Розглянемо випадок коли за початкове число даної серії взято 4500:

і т.д.

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

Загальної теорії побудови псевдовипадкових чисел досі не створено. Вигляд фунції установлюють емпірично. Ця функція містить різні арифметичні та логічні операції. Якість утворюваних чисел перевіряється з допомогою спеціальних тестів.

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

Два цілі числа A і B конгруентні (порівнянні) за модулем m (де m — ціле число) тоді і тільки тоді коли існує таке ціле число k що A – B = km тобто коли різниця A – B ділиться на m без остачі (числа A та B дають однакові остачі при діленні на абсолютну величину числа m). Це визначення записується як і читається «А конгруентне В за модулем m». Наприклад 13 3 (за модулем 10) 124 4 (за модулем 10) 5 1 (за модулем 4) 4339 39 (за модулем 100 ) і т.д.

Найвідомішими є такі конгруентні методи: мультиплікативний мішаний і адитивний

Мультиплікативний конгруентний метод(метод лишків)

Випадкове число РВП [0 1] дістаємо перетворенням цілих чисел що визначаються з допомогою рекурентного виразу


(2)


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

Згідно з (2) для знаходження наступного випадкового числа достатньо виконати такі дії:

1) взяти останнє випадкове число ;

2) помножити його на коефіцієнт a ;

3) добуток поділити на модуль m;

4) остачу від ділення вважати шуканим випадковим числом ; це буде одне з цілих чисел 0 1 2 3 . . . m – 1.

Для генерування послідовності випадкових чисел потрібно мати початкове число множник a і модуль m. При виборі a і m потрібно виявити певну обережність. Коли a = 1 то = при будь-якому і . Коли = 0 то = 0 при довільному і . Очевидно що будь-який генератор псевдовипадкових чисел може дати лише скінченну множину цілих випадкових чисел; після чого послідовність повторюватиметься.

Період (довжина) послідовності залежить від розрядності ЕОМ та вибраного модуля а статистичні властивості — від вибору початкового числа та множника. Отже вибирати потрібно так щоб забезпечити максимальний період і мінімальну кореляцію (автокореляцію).

Мультиплікативний конгруентний метод пояснимо розглянувши процес генерування десяткових дробів з десятьма знаками після коми. Перепишемо формулу (2) узявши — довільне непарне число що не ділиться на 5:

Нехай x0= 123456789 тоді

і т.д.

У системах ЕОМ типу IBM широко застосовується метод Хатчинсона. Двійкові числа в цих машинах подаються 32 розрядами: 31 розряд містить значущі цифри крайній зліва розряд показує знак числа. За модуль беруть множник Максимальна довжина послідовності випадкових чисел дорівнює m – 1; 0 46566113. Запишемо програму цього датчика випадкових чисел мовою фортран.

SUBROUTINE RAND (N1 N R)

1. N = 1220703125 N1

2. IF(N)3 4 4

3. N = N + 2147483647 + 1

4. NI = N

5. R = N

6. R = R0.4656613E – 9

7. RETURN

8. END

У програмі — ціле число між 1 і — випадкове число з плаваючою крапкою (оператори 5 і 6 дають результати з плаваючою крапкою). Від’ємне число N може виникнути після команди 1 у результаті відкидання старших розрядів тому оператор 3 змінює його значення.

Щоб дістати кілька послідовностей випадкових чисел РВП [0 1] необхідно ввести різні значення початкових чисел: а щоб повторити початковий відрізок будь-якої послідовності достатньо всередині основної програми присвоїти відповідній змінній N1її початкове значення і повторити весь цикл звертань до генератора.

Описаний генератор грунтовно перевірявся і показав досить добру якість випадкових чисел.

Мішані конгруентні методи

Побудова мішаних когруентних методів грунтується на залежності


xi+1 (axi + c) (mod m)


де с — деяка константа.

Адитивний конгруентний метод

В основу цього методу покладено рекурентне співвідношення



Існують і складніші адитивні методи.

Переваги програмного методу:

1) місця в оперативній пам’яті займає мало (близько десяти машинних команд);

2) можна повторити спроби;

3) забезпечується одноразова перевірка якості випадкових чисел;

4) не потрібні зовнішні пристрої.

Недоліки програмного методу:

1) відносно невелика швидкість утворення випадкових чисел;

2) запас чисел обмежений.

Порівнюючи переваги та недоліки трьох методів генерування РВП [0 1] доходимо висновку що програмний спосіб породження псевдовипадкових чисел найприйнятніший для застосування в імітаційному моделюванні.


2. Моделювання випадкових величин


Алгоритмічне (імітаційне) моделювання — це числовий метод дослідження систем і процесів за допомогою моделюючого алгоритму.

Страницы: 1 2 3