Міністерство освіти і науки України
Тернопільський національний технічний університет імені Івана Пулюя
Кафедра комп’ютерних систем та мереж
ЗВІТ
про виконання лабораторної роботи № 1
з дисципліни: “Моделювання комп’ютерних систем”
на тему: “ Моделювання випадкових чисел”
Виконав:
студент групи CІ-31
Макогон С. В.
Прийняла:
Луцик Н. С.
Тернопіль 2021
Тема: Моделювання випадкових чисел
Мета роботи: Вивчити методи та алгоритми моделювання випадкових величин.
Теоретичні відомості
1. Основні імовірнісні поняття
Випадковим досвідом або експериментом називається процес, при якому можливі різні результати, так що не можна заздалегідь передбачити, який буде результат. Величина X={xi}=x1, x2, ..., xn, що є результатом випадкового досвіду, називається випадковою величиною. Мінливість результату такого досвіду може бути пов'язане з наявністю випадкових помилок вимірювань або зі статистичною природою самої вимірюваної величини (наприклад, процес розпаду радіоактивної речовини). Будемо позначати окремі значення, які приймає випадкова величина (не обов'язково чисельні), як xi, де i = 1, 2, ...,n. Будь-яка функція від xi буде також випадковою величиною.
Під моделюванням випадкової величини Х прийнято розуміти процес отримання на ЕОМ її вибіркових значень x1, ..., xn. На практиці використовуються три основних способи генерації випадкових чисел:
-Табличний (файловий) - введення таблиць рівномірно розподілених випадкових чисел у зовнішню або оперативну пам'ять ЕОМ;
- Апаратний (фізичний) - використання спеціального пристосування до ЕОМ - "датчика" випадкових чисел, який формує випадкові величини шляхом фізичного моделювання деяких випадкових процесів (випромінювання радіоактивних джерел, шумів електронних ламп та ін);
-Алгоритмічний (програмний) - використання псевдовипадкових послідовностей, що реалізуються програмним генератором випадкових чисел. Псевдовипадковими числами називаються числа, що виробляються ЕОМ рекурентним способом за спеціальними алгоритмами, коли кожне наступне число xi виходить з попередніх в результаті застосування деяких арифметичних і логічних операцій. Така послідовність чисел задовольняє відомими критеріями випадковості, хоча вхідні в цю послідовність числа залежні між собою. Одним з недоліків цього методу є періодичність утворених програмним способом псевдовипадкових чисел, але для ряду завдань, які потребують великої кількості випадкових чисел, довжина періоду є достатньою.
Перший спосіб. При вирішенні задачі без застосування ЕОМ найчастіше використовують таблиці випадкових чисел. Таблиці отримують за допомогою спеціальних приладів (типу рулетки) і заносять в пам'ять ЕОМ, використовуються по мірі необхідності.
У таблицях випадкових чисел випадкові цифри імітують значення дискретної випадкової величини з рівномірним розподілом:
При складанні таких таблиць виконується вимога, щоб кожна з цих цифр від 0; 1; ...;9 зустрічалася приблизно однаково часто і незалежно від інших з ймовірністю pi = 0,1.
Найбільша з опублікованих таблиць випадкових чисел містить 1000000 цифр. Таблиці випадкових чисел вимагають ретельної перевірки за допомогою спеціальних статистичних тестів.
Основний недолік - необхідність у пам'яті досить великої ємності, що утруднює рішення "великих" завдань, тим більше що перевага "випадкових" таблиць перед "псевдовипадковими" числами, одержуваними алгоритмічно, ніким не було доведено.
У другому способі використовуються апаратні датчики, засновані на деяких фізичних процесах, випадкових за своєю природою (шуми в електронних і напівпровідникових приладах, процеси при радіоактивному розпаді і т.п.).
Або ж при вирішенні завдань на ЕОМ для вироблення випадкових чисел, рівномірно розподілених в інтервалі (0; 1), можуть застосовуватися генератори випадкових чисел. Дані генератори перетворюють результати випадкового фізичного процесу в двійкові числа. В якості випадкового фізичного процесу зазвичай використовують власні шуми (випадковим чином змінюється напруга).
Основні недоліки - неможливість повторного отримання однієї і тієї ж послідовності випадкових величин для перевірочних розрахунків і неможливість гарантувати постійну надійну роботу датчика.
Третій спосіб. Отримання псевдовипадкових чисел з рівномірним законом розподілу полягає у виробленні псевдовипадкових чисел.
Псевдовипадкові числа - це числа, отримані з будь-якої формулою і імітують значення випадкової величини. Під словом "імітують" мається на увазі, що ці числа задовільняють ряд тестів так, як якщо б вони були значеннями цієї випадкової величини.
Перший алгоритм для отримання псевдовипадкових чисел запропонував Дж. Нейман. Це так званий метод середини квадратів, який полягає в наступному:
Метод середин квадратів фон Неймана є порівняно бідним джерелом випадкових чисел, тому що послідовність прагне увійти у звичну колію, тобто короткий цикл повторюваних елементів.
Переваги методу псевдовипадкових чисел:
1.На отримання кожного випадкового числа витрачається кілька простих операцій, так що швидкість генерування випадкових чисел має той самий порядок, що і швидкість роботи ЕОМ.
2. Малий обсяг пам'яті ЕОМ для програмування.
3. Будь-яке з чисел легко відтворити.
4.Якість генеруються випадкових чисел досить перевірити один раз.
Випадкові величини бувають дискретні і безперервні, одномірні (залежні від однієї змінної) або багатовимірні (залежні від двох і більше змінних).
Дискретною випадковою величиною називається така величина, число можливих значень якої або кінцеве, або нескінченне рахункове.
Неперервною випадковою величиною називається така величина, можливі значення якої безперервно заповнюють деякий інтервал (кінцевий чи нескінченний) числової осі.
Повною характеристикою випадкової величини X з імовірнісної точки зору є її закон розподілу, тобто заданий в тій чи іншій формі зв'язок між можливими значеннями випадкової величини і ймовірностями їх появи.
Універсальною формою закону розподілу (безперервних і дискретних величин) є функція розподілу ймовірностей - це така функція F (x), значення якої в точці x рівне ймовірності (P) того, що при проведенні досвіду значення випадкової величини X виявиться менше, ніж x:
F(x) = P(X < x).
Основні властивості функції розподілу ймовірностей наступні:
1) числові значення укладені в межах 0 ≤ F(x) ≤ 1;
2) якщо x1≤ x2, то F(x1) ≤ F(x2), тобто F(x) - неспадаюча функція;
3) F (x) → 0 при x → - ∞, F (x) → 1 при x → ∞.
Рисунок 1. Графічне зображення функції розподілу ймовірностей
Якщо випадкова величина дискретна, то її функція розподілу являє собою східчасту функцію (рисунок 1a), а у безперервних випадкових величин функція розподілу також неперервна (рисунок 1b).
Функцію розподілу ймовірностей F (x) неперервної випадкової величини можна представити у вигляді інтеграла від деякої невід’ємної функції f (x):
.Функція f (x) називається щільністю розподілу ймовірності. Основні властивості щільності ймовірності такі:
1)
;2)
3) щільність ймовірності пропорційна ймовірності події (x ≤ X ≤ x + dx).
Крім закону розподілу, випадкову величину характеризують значеннями деяких параметрів, що визначають найбільш суттєві особливості її розподілу. Найбільш часто використовуваними параметрами розподілу є математичне сподівання чи середнє значення випадкової величини, а також дисперсія випадкової величини.
Параметри випадкової величини
Основне призначення числових характеристик випадкової величини полягає в тому, щоб в стислій формі висловити найбільш суттєві особливості того чи іншого розподілу.
Математичним сподіванням чи середнім значенням дискретної випадкової величини називається сума всіх можливих значень xi випадкової величини X, помножених на відповідні ймовірності:
,
,
.Так як функція від випадкової величини є також випадковою величиною, то математичне сподівання функції Y = H(X) визначається наступним чином:
.Для неперервних випадкових величин будемо мати:
і 
.Важливою характеристикою відхилення або розподілу випадкової величини від її середнього значення є дисперсія випадкової величини, що визначається як математичне сподівання квадрата відхилення випадкової величини X від свого середнього значення:
.Додатній квадратний корінь з дисперсії
називається стандартним або середньоквадратичним відхиленням. Середньоквадратичне відхилення кількісно показує, наскільки сильно значення випадкової величини X розподілені навколо середнього значення x.2. Моделювання дискретних випадкових величин
Розглянемо дискретну випадкову величину X, приймаючу n значень x1, x2, ..., xn з ймовірностями P1, P2 ,..., Pn. Ця величина задається таблицею розподілу
або
Для моделювання такої дискретної випадкової величини розбивають відрізок [0; 1] на n послідовних відрізків Δ1, Δ2 ,..., Δn, довжини яких дорівнюють відповідним ймовірностями P1, P2, ..., Pn. Тоді довжини відрізків будуть рівні:
Довжина
Довжина
.......................................................
Довжина
Видно, що довжина часткового інтервалу з індексом i дорівнює ймовірності Р з тим же індексом. Довжина Di=Pi. Отримують випадкову величину R, рівномірно розподілену в інтервалі (0; 1). Таким чином, при попаданні випадкового числа ri в інтервал Di випадкова величина X приймає значення xi з імовірністю Pi.
Теорема: якщо кожному випадковому числу ri(0≤ ri <1), яке потрапило в інтервал, поставити у відповідність можливе значення xi, то розігрувана величина буде мати заданий закон розподілу.
Розглянемо алгоритм моделювання дискретних випадкових величин:
1. Потрібно розбити інтервал [0;1) на n часткових інтервалів:
D1 – (0; P1), D2 – (P2; P1+ P2), …, Dn – (P1+P2 + … +Pn-1; 1).
2. Вибрати (наприклад, з таблиці випадкових чисел, або в комп'ютері) випадкове число ri з інтервалу [0; 1). Якщо ri потрапило в інтервал, то модельована дискретна випадкова величина прийняла можливе значення xi.
3. Перевірка гіпотези про закон розподілу методом гістограм
Нехай у результаті експерименту отримано n значень x1, x2, ..., xn випадкової величини X і всі вони укладені в межах a < xi < b.
Суть перевірки по гістограмі зводиться до наступного:
а) Висувається гіпотеза про рівномірність розподілу чисел в інтервалі (0;1).
б) Потім інтервал (a;b) розбивається на L (будь-яке число, не дуже велике і не занадто мале) рівних підінтервалів довжиною Δj, тоді при генерації послідовності {xi} кожне з чисел x з імовірністю pj =1/L,
, потрапляє в один з підінтервалів. Всього в кожен j-й підінтервал потрапляє Vj чисел послідовності {xi}, 
, причому 
. Відносна частота потрапляння випадкових чисел послідовності {xi} в кожен з підінтервалів буде дорівнює nj/n.в) Над кожним з підінтервалів розбиття будується прямокутник, площа якого дорівнює частоті потрапляння {xi} в цей підінтервал. Висота кожного прямокутника дорівнює частоті, поділеній на Δj. Отриману ступінчасту лінію називають гістограмою.
г) Вид відповідної гістограми представлений на рисунку 5, де пунктирна лінія відповідає теоретичному значенню pj, а суцільна - експериментальному nj/n. Очевидно, що якщо числа {xi} належать псевдовипадковій рівномірно розподіленій послідовності, то при досить великих n експериментальна гістограма (ламана лінія на рис. 5) наблизиться до теоретичної прямою pj=1/L.
Гістограма служить наближенням до невідомої щільності випадкової величини X. Площа гістограми, укладена між xi і xi +1, дає наближене значення ймовірності P{xi
Рисунок 2. Перевірка рівномірності послідовності
Хід роботи
1. Згенерувати послідовність з n00 рівномірно розподілених псевдовипадкових чисел (n=11)
1.1. Математичне сподівання отриманої послідовності.
1.2. Дисперсія отриманої послідовності.
1.3. Частотна таблиця
1.4. Побудова гістограми
2. Змоделюю дискретну випадкову величину.
2.1. Математичне сподівання отриманої дискретної випадкової величини.
2.2. Дисперсія отриманої дискретної випадкової величини.
2.3. Частотна таблиця.
2.4.Оцінюю закон розподілу випадкової величини за графіком частоти появи її значень у результаті експериментів.
Висновок: на лабораторній роботі я вивчив методи та алгоритми моделювання випадкових величин.