Новини освіти і науки:

G+

Тлумачний словник
Авто
Автоматизація
Архітектура
Астрономія
Аудит
Біологія
Будівництво
Бухгалтерія
Винахідництво
Виробництво
Військова справа
Генетика
Географія
Геологія
Господарство
Держава
Дім
Екологія
Економетрика
Економіка
Електроніка
Журналістика та ЗМІ
Зв'язок
Іноземні мови
Інформатика
Історія
Комп'ютери
Креслення
Кулінарія
Культура
Лексикологія
Література
Логіка
Маркетинг
Математика
Машинобудування
Медицина
Менеджмент
Метали і Зварювання
Механіка
Мистецтво
Музика
Населення
Освіта
Охорона безпеки життя
Охорона Праці
Педагогіка
Політика
Право
Програмування
Промисловість
Психологія
Радіо
Регилия
Соціологія
Спорт
Стандартизація
Технології
Торгівля
Туризм
Фізика
Фізіологія
Філософія
Фінанси
Хімія
Юриспунденкция

Поняття про генератори (датчики) випадкових чисел.

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

Крім того, бібліотеки більшості ЕОМ включають спеціальні стандартні підпрограми, котрі можна використати з відповідною метою.

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

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

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

2. Табличний спосіб одержання РВП [0,1]

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

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

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

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

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

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

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

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

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

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

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

3. Фізичний спосіб одержання РВП [0,1]

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

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

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

1) радіоактивне випромінювання (Рис. 7.2);

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

Рис. 6.1 Схема реалізації випадкової величини на прикладі радіоактивного випромінювання

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

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

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

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

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

. (6.1)

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

(6.2)

Щоб дістати m- розрядне випадкове двійкове число РСП [0, 1], досить провести m вимірювань шyму лампи в моменти часу t1,t2,...,tm і скористатися перетворенням.

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

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

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

2) об’єм використання оперативної пам’яті мінімальний;

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

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

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

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

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

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

4. Програмні способи одержання РВП [0,1]

При програмному способі наступне випадкове число дістають за допомогою рекурентного співвідношення = f( ). Так, генеровані випадкові числа називаються псевдовипадковими (псевдо – обман, вигадка, помилка; відповідає поняттям «несправжній», «неправильний»), оскільки між двома сусідніми числами існує залежність. Функція f( ) повинна бути такою, щоб вона включала логічні перетворення, аби згадана залежність практично не впливала на результат.

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

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

(6.3)

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

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

(6.3)

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

(6.4)

Як показали статистичні випробування, утворювані таким способом випадкові числа мають розподіл, близький до РСП [0, 1]. Очевидний недолік методу серединних квадратів полягає в тому, що у разі відсутності заміни нульового значення випадкового числа, котре може з'явитися в результаті наступної спроби, якимось іншим, усі наступні числа послідовності будуть нулями. Можливе циклічне повторення й інших цифр. Нехай, наприклад, потрібно дістати серію випадкових 4-розрядних десяткових чисел , ,..., методом серединних квадратів. Розглянемо випадок, коли за початкове число даної серії взято 4500:

= 4500; = 20250000;

= 2500; = 06250000;

= 2500; і т.д.

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

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

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

Нагадаємо, що два цілі числа А ї В конгруентні (порівнянні) за модулем m, де m – ціле число, тоді і тільки тоді, коли існує таке ціле число k, що А – В = , тобто коли різниця А-В ділиться на m без остачі (числа А і В дають однакові остачі при діленні на абсолютну величину числа m).

Це визначення записується як А = B (mod m) і читається “A конгруентне В за модулем m”. Наприклад, 13 = 3 (за модулем 10), 124 = 4 (за модулем 10),

5 = 1 (за модулем 4), 4339 = 39 (за модулем 100 ) і т.д.

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

Читайте також:

<== попередня сторінка	\|	наступна сторінка ==>
Властивості рівномірної випадковості послідовності чисел	\|	Загально статистичні методи перевірки якості псевдовипадкових чисел

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.008 сек.