Курсовая работа: Програмне генерування РВП0 1

Оператор 1 звертається до генератора випадкових чисел, що відповідають рівномірному закону розподілу на інтервалі (0; 1). Оператор 2 перевіряє умову потрапляння випадкової величини x в інтервал (0; L1). Якщо ця умова виконується, то вважається, що відбулася подія А1. Якщо ця умова не виконується, то алгоритм передбачає перевірку умов потрапляння випадкової величини в інші інтервали.

3. Моделювання дискретної випадкової величини

Розподіл дискретної випадкової величини може бути поданий у вигляді таблиці

ճ	Х1	Х2	…	Хn
Pi	P1	P2	…	Pn

Тут pj — імовірність того, що випадкова величина х набуває значення хj, j = 1, …, n.

Накладається також умова:

Поділимо інтервал (0; 1) на n відрізків, довжини котрих дорівнюють заданим імовірностям. Якщо випадкове число x, що формується генератором випадкових чисел, котрі відповідають рівномірному закону розподілу на інтервалі (0; 1), потрапляє до інтервалу pk, то випадкова величина х набуває значення хk. Отже, під час моделювання дискретної випадкової величини фактично використовується та сама процедура, що й за моделювання повної групи несумісних подій.

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

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

Технічно термін "генератор випадкових чисел" - це абсурд; числа само по собі не є випадковими. Наприклад, 100 - це випадкове число? А 25? Що насправді означає цей термін, так це те, що створюється послідовність чисел, що з'являються випадковим чином. Це породжує складніше питання: що таке послідовність випадкових чисел? Єдино правильна відповідь: послідовність випадкових чисел – це послідовність, в якій всі елементи є незв'язаними. Це визначення наводить до такого парадоксу, що будь-яка послідовність може бути як випадковою, так і невипадковою залежно від того, як ця послідовність отримана. Наприклад, наступний рядок чисел 1 2 3 4 5 6 7 8 9 0 був отриманий друкуванням верхнього рядка клавіатури по порядку, таким чином послідовність звичайно не може розглядатися як що згенерувала випадковим чином. Але як бути, якщо ви отримаєте ту ж саму послідовність, виймаючи пронумерований тенісні кулі з боченка. В даному випадку це вже випадковим чином послідовність, що згенерувала. Даний приклад показує, що випадковість послідовності залежить від того, як вона була отримана, а не від неї самої. Пам'ятаєте, що послідовність чисел, що згенерувала комп'ютером, є детермінованою: кожне число, окрім першого, залежить від попередніх чисел. Технічно це означає, що комп'ютером може згенерувати лише квазівипадкова послідовність чисел. Проте, це вистачає для більшості завдань і в даній курсовій роботі такі послідовності для простоти називатимуться випадковими. У загальному випадку вважається добре, коли числа в послідовності випадкових чисел розподілені рівномірно (не плутайте це з нормальним розподілом або колоколообразной кривою). При рівномірному розподілі всі події рівноімовірні так, що діаграма рівномірного розподілу прагне до прямої горизонтальної лінії, а не до кривої.

До широкого поширення комп'ютерів всякий раз, коли необхідні були випадкові числа, вони виходили або киданням гральних кісток, або вийманням пронумерованих куль з ящика. У 1955 році фірма RAND опублікувала таблицю з 1 мільйона випадкових чисел, отриманих за допомогою обчислювальної машини. На ранній стадії розвитку обчислювальної техніки було розроблено багато методів генерації випадкових чисел, але більшість з них не знайшла вживання. Один дуже цікавий метод був розроблений Джоном фон Нейманом; його часто називають середньоквадратичним. У даному методі попереднє випадкове число зводиться в квадрат, а потім з результату виділяються середні цифри. Наприклад, якщо ви створюєте числа з трьох цифр, а попереднє число було 121, то зведення в квадрат дає результат 14641. Виділення трьох середніх цифр дає наступне випадкове число 464. Недоліком даного методу є те, що він має дуже короткий період повторення, званий циклом. З даної причини даний метод сьогодні не використовується.

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

при виконанні наступних умов

Відзначимо, що R - це попереднє число, а R - наступне. Даний метод інколи називають лінійним порівняльним методом. Формула така проста, що ви можете подумати, що генерувати випадкові числа просто. Проте, це пастка: наскільки добре працює дана формула, дуже сильно залежить від значення а, з і m. Вибір значень інколи більшою мірою мистецтво, ніж наука. Існують складні правила, які можуть допомогти вам вибрати значення; проте, ми розглянемо лише декілька простих правил і прикладів. Модуль (m) має бути досить великим, оскільки він визначає область випадкових чисел.

Операція узяття по модулю породжує залишок від ділення числа на модуль. Отже, 10 по модулю 4 рівне 2. Таким чином, якщо модуль дорівнює 12, то формулою породжуються числа від 0 до 11, а якщо модуль дорівнює 21425, то породжуються числа від 0 до 21424. Вибір множника а і прирости з є дуже складним завданням. У загальному випадку множник може бути задоволений великим, а приріст - маленьким. Безліч спроб і перевірок необхідна, аби створити хороший генератор. Як перший приклад тут приведений один з найчастіше використовуваних генераторів випадкових чисел. Рівняння, показане в Rаn1 використовується як основа для генератора випадкових чисел у ряді популярних мов.

Дана функція має три головні особливості. По-перше, випадкові числа насправді є цілими, хоча функція повертає дійсні числа. Даний метод працює з цілими числами, але генератори випадкових чисел, як це прийнято, повинні повертати числа в межах від 0 до 1, що означає, що це мають бути числа з плаваючою комою. По-друге, початкове значення задається через глобальну змінну а1. До першого виклику Ran1 змінна а1 має бути встановлена в 1. По-третє, в Ran1 випадкові числа діляться на модуль перш, ніж вони будуть повернені функцією, для того, щоб числа лежали в області від 0 до 1. Якщо ви поцікавитеся значенням глобальної змінної а1 до повернення рядка, то воно повинне лежати в області від 0 до 32748. Отже, коли а1 ділиться на 32749, отримане число буде більше або рівне 0 і менше 1. Багато генераторів випадкових чисел не застосовні, оскільки вони породжують не рівномірний розподіл або мають короткий цикл повторення. Навіть коли ці недоліки не дуже впадають в очі, вони можуть породити змішаний результат, якщо такий генератор використовується знову і знову. Рішення полягає в тому, аби створити різні генератори і застосовувати їх індивідуально або спільно для здобуття якісніших послідовностей випадкових чисел. Вживання декількох генераторів може згладити розподіл послідовності за рахунок зменшення малих змішень окремих генераторів. Далі приведена функція генерування випадкових чисел, звана Ran2, яка породжує хороший розподіл:

Обоє цих генератора випадкових чисел породжують хороші послідовності випадкових чисел. Проте залишаються питання: чи досить "випадковою" є послідовність? Чи хороші дані генератори?

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

Ви можете застосувати різні тексти для визначення випадковості послідовності чисел. Жоден з тестів не скаже, що послідовність є випадковою, проте, він скаже, якщо вона не є такій. Тести можуть виявити не випадкові послідовності, але, якщо тест не знайшов недоліків, це не означає, що дана послідовність дійсно випадкова. Тести, проте, підвищують упевненість в генераторі випадкових чисел, який породив послідовність. Тепер ми коротко розглянемо декілька простих способів тестування послідовностей. Спершу розглянемо спосіб визначення того, наскільки близький розподіл чисел в послідовності відповідає очікуваному. Наприклад, ви намагаєтеся генерувати послідовність випадкових чисел від 0 до 9. Вірогідність появи кожної цифри дорівнює 1/10. Хай згенерувала наступна последовательность

Якщо ви підрахуєте число появ кожної цифри, то отримаєте результат

Далі вам слід відповісти самому собі на питання, чи досить схожий даний розподіл на очікуване вами. Пам'ятаєте: якщо генератор випадкових чисел хороший, він генерує послідовності випадково. У істинно випадковому варіанті всі послідовності можливі. Дійсно, як якась послідовність може бути не випадковою, якщо будь-яка послідовність можлива? Просто деякі послідовності менш схожі на те, якою має бути випадкова послідовність, чим інші. Ви можете визначити вірогідність того, що дана послідовність є випадковою, використовуючи критерій хі-квадрат. У критерії хі-квадрат очікувана кількість віднімається із спостережуваної кількості зустрічей числа в послідовності, що згенерувала. Цей результат називається V. Ви можете використовувати Vдля знаходження відсотка в таблиці значень хі-квадрат. Цей відсоток визначає вірогідність того, що була породжена випадкова послідовність. Мала таблиця хі-квадрат приведена на рисунку (3.1); ви можете знайти повні таблиці в більшості книг за статистикою

Рис. 3.1. Мала таблиця хі-квадрат