Кафедра: Автоматика та Обчислювальна Техніка
Генератор випадкових чисел
Зміст
1. Способи отримання випадкових чисел. 3
2. Характеристики ГВЧ. 5
3. Застосування ГВЧ. 6
4. Генерування рівномірно розподілених випадкових чисел. 9
5. Генерування чисел з довільним розподілом. 12
6. Тестування ГВЧ. 17
7. Генератор випадкових чисел в Borland C + +. 21
8. Практичні завдання. 23
8.1 Випадкові числа в заданому діапазоні. 23
8.2 Двовимірні випадкові величини .. 23
8.3 Генерація одновимірної випадкової величини .. 23
8.4 Оцінити ймовірність. 23
8.5. Медіани трикутника. 24
9. Лабораторні завдання. 25
9.1 ГВЧ фон Неймана. 25
9.2 Випадкова матриця. 25
9.3 Площа фігури .. 26
9.4 Випадкова величина із заданими властивостями. 26
10. Додаткові завдання. 27
10.1 Багатовимірні випадкові величини .. 27
10.2 Бики і корови .. 27
Бібліографічний список. 28
1. Способи отримання випадкових чисел
У програмуванні досить часто знаходять застосування послідовності чисел, вибраних випадковим чином з деякого безлічі. В якості прикладів задач, в яких використовуються випадкові числа, можна привести наступні:
- тестування алгоритмів;
- імітаційне моделювання;
- деякі задачі чисельного аналізу;
- імітація користувальницького введення.
Для отримання випадкових чисел можна використовувати різні способи. У загальному випадку всі методи генерування випадкових чисел можна розділити на апаратні і програмні. Пристрої або алгоритми отримання випадкових чисел називають генераторами випадкових чисел (ГВЧ) або датчиками випадкових чисел.
Апаратні ГВЧ являють собою пристрої, що перетворюють в цифрову форму небудь параметр навколишнього середовища або фізичного процесу. Параметр і процес вибираються таким чином, щоб забезпечити гарну В«випадковістьВ» значень при зчитуванні. Дуже часто використовуються паразитні процеси в електроніці (струми витоку, тунельний пробій діодів, цифровий шум відеокамери, шуми на мікрофонному вході звукової карти і т.п.). Формована таким чином послідовність чисел, як правило, носить абсолютно випадковий характер і не може бути відтворена заново за бажанням користувача.
До програмних ГВЧ відносяться різні алгоритми генерування послідовності чисел, яка за своїми характеристиками нагадує випадкову. Для формування чергового числа послідовності використовуються різні алгебраїчні перетворення. Одним з перших програмних ГВЧ є метод серединної квадратів, запропонований у 1946 р. Дж. фон Нейманом. Цей ГВЧ формує наступний елемент послідовності на основі попереднього шляхом зведення його в квадрат і виділення середніх цифр отриманого числа. Наприклад, ми хочемо отримати 10-значне число і попереднє число дорівнювало 5772156649. Зводимо його в квадрат і отримуємо 33317792380594909201; значить, наступним числом буде 7923805949. Очевидним недоліком цього методу є зациклення у випадку, якщо чергове число буде дорівнює нулю. Крім того, існують і інші порівняно короткі цикли.
Будь програмні ГВЧ, які не використовують зовнішніх В«джерел ентропіїВ» і формують чергове число тільки алгебраїчними перетвореннями, не дають чисто випадкових чисел. Послідовність на виході такого ГВЧ виглядає як випадкова, але насправді підпорядковується деякому закону і, як правило, рано чи пізно зациклюється. Такі числа називаються псевдовипадковими.
Надалі ми будемо розглядати лише програмні генератори псевдовипадкових чисел.
2. Характеристики ГВЧ
Послідовності випадкових чисел, формованих тим або іншим ГВЧ, повинні задовольняти ряду вимог. По-перше, числа повинні вибиратися з певного безлічі (найчастіше це дійсні числа в інтервалі від 0 до 1 або цілі від 0 до N ). По-друге, послідовність повинна підкорятися певним розподілом на заданій множині (частіше всього розподіл рівномірний). Необов'язковим є вимога відтворюваності послідовності. Якщо ГВЧ дозволяє відтворити заново одного разу сформовану послідовність, налагодження програм з використанням такого ГВЧ значно спрощується. Крім того, вимога відтворюваності часто висувається при використанні ГВЧ в криптографії.
Оскільки псевдовипадкові числа не є дійсно випадковими, якість ГВЧ дуже часто оцінюється по В«випадковостіВ» отримуваних чисел. У цю оцінку можуть входити різні показники, наприклад, довжина циклу (Кількість ітерацій, після якого ГВЧ зациклюється), взаємозалежності між сусідніми числами (можуть виявлятися за допомогою різних методів теорії ймовірностей і математичної статистики) і т.п. Докладніше оцінка якості ГВЧ розглянута нижче.
3. Застосування ГВЧ
Одне із завдань, в яких застосовуються ГВЧ, - це груба оцінка обсягів складних областей в евклідовому просторі більш ніж чотирьох або п'яти вимірювань. Зрозуміло, сюди входить і наближене обчислення інтегралів. Позначимо область через R ; зазвичай вона визначається рядом нерівностей. Припустимо, що R - підмножина n -мірного одиничного куба K . Обчислення об'єму безлічі R методом Монте-Карло зводиться до того, щоб випадковим чином вибрати в K велике число N точок, які з однаковою ймовірністю можуть опинитися в будь-якій частині K . Потім підраховують число M точок, які потрапили в R , тобто задовольняють нерівностям, визначальним R . Тоді M / N є оцінка обсягу R . Можна показати, що точність такої оцінки буде досить низькою. Тим не менш, вибірка з 10 000 точок забезпечить точність близько 1%, якщо тільки обсяг не надто близький до 0 або 1. Такий точності часто буває достатньо, і домогтися кращого іншими методами може виявитися дуже важко.
Як приклад можна розглянути обчислення площі фігури, заданої деякою системою нерівностей. Нехай фігура буде визначена наступним чином:
.
Спочатку необхідно визначити прямокутну область, з якої будуть вибиратися випадкові точки. Це може бути будь-яка область, повністю містить фігуру, площу якої потрібно знайти. Візьмемо в якості вихідної області прямокутник з координатами кутів (0; -1) - (1; 1). Будемо послідовно генерувати точки, рівномірно розподілені усередині цього прямокутника, і для кожної точки перевіряти нерівності, які описують фігуру. Якщо точка задовольняє всім нерівностям, значить, вона належить фігурі. При достатньо великому числі таких експериментів відношення числа точок N F , задовольняють нерівностям, до загального числа згенерованих точок N R показує частку площі прямокутника, яку займає постать. Площа прямокутника S R відома (в нашому випадку вона дорівнює 2), площа фігури S F обчислюється тривіально:
.
Очевидно, що для такої простої області можна легко порахувати область через певний інтеграл. Тим не менш, описаний метод застосовний і в разі набагато більш складних фігур, коли розрахувати площу іншим способом стає занадто складно.
Іншим прикладом наближеного взяття певного інтеграла за допомогою ГВЧ є обчислення об'єму кулі в n -мірному просторі. Обсяг n -мірного кулі виражається формулою:
,
де О“ ( z ) - Деяка гамма-функція, визначувана наступним співвідношенням:
О“ ( z +1) = z В· О“ ( z ),
О“ (1) = 1.
Таким чином, для натуральних z гамма-функція дорівнює факторіалів z . Для обчислення знаменника можна скористатися відомим значенням
:
.
Можна показати, що для кулі одиничного радіуса при збільшенні розмірн...
