Математичні алгоритми

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

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

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

Причини використання:

1. моделювання (ядерна фізика, системний аналіз);

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

3. числовий аналіз (для вирішення складних математичних задач, спеціальна технологія на випадкових числах);

4. аналіз алгоритмів (оцінка ефективності алгоритмів);

5. прийняття рішення (випадково обраний вибір (варіант)).

Методи отримання випадкових значень:

1. вибір із статичної таблиці;

2. обчислення «середини квадрату»: попереднє (вихідне) число підводиться у степінь двійки і з результату вилучаються середні цифри (тобто, ігноруються декілька перших і останніх чисел). Недолік – послідовності випадкових чисел мають тенденцію перетворюватися в короткі цикли елементів, що повторюються.

3. лінійний конгруентний метод: обчислюється дійсне значення, рівномірно розподілене між нулем і одиницею U(i)=X(i)m; ціле число у діапазоні від нуля до m – значення на одиницю більше максимального числа встановленої розрядності (наприклад, розрядність представлення цілого числа 16 біт -> 2(^16)=65536).

Ціле значення обчислюється за наступним відношенням: X(i+1)=(aX(i)+c)mod m, i>=0, початкове значення (0) більше чи ріне нулю, а – коефіцієнт (те ж), с – зсув (зміщення), му – модуль, що більший за початкове значення, а і с.

Цикл, що повторюється, називається періодом. Коли с=0 – мультиплікативний конгруентний метод, якщо с не дорівнює 0 – змішаний.

Вибір модулю.

Умови:

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

б) швидкість вироблення числа має бути як можна меншою.

Перший варіант:

вибрати значення му як 2(с)=омега +1 (омега – максимальне значення с із розрядністю е), тоді дорого вартісну операцію ділення можна не використовувати (скорочується час обчислення).

Другий варіант:

Вибір у якості му найбільшого простого числа, меншого за омегу.

Вибір коефіцієнта

Впливає на довжину періоду і випадковість вибірки.

Необхідна максимальна довжина періоду, тоді с і му – взаємно прості числв; бе = а-1 кратне р (тобто, всім простим дільникам му); бе кратне 4. Якщо і модуль кратний 4.

Значення а має бути таким, щоб а мод 8 = 5 (для двійкової СЧ);

а мод 200 = 21 (для десяткової СЧ);

корінь із му менше за а і менше за му-корінь з му.

Вибір зміщення

1. значення с має бути непарним і не кратним 5 (для десятинної СЧ);

2. відношення с поділити на му приблизно дорівнює 0.21113248654051871;

3.

4. адитивний метод:

це по суті змінений конгруентний метод, де наступне значення обчислюється у залежності від двох попередніх X(i+1)=(X(i)+X(i-k))mod m, k – деяке велике значення. Заздалегідь створюється послідовність X(0)…X(k), X(i)=X(k).

5. комбінований метод:

за двома заданими методами обчислюються дві послідовності <X(n)> I <Y(n)>, отримані двома незалежними способами, при цьому періоди цих послідовностей – взаємно прості числа. Використовується додатковий масив розмірності k, де воно дорівнює 100, котрий заповнюється першими кА елементами із послідовності Х(ен). Шукана послідовність випадкових значень формується за алгоритмом:

1. вичислюється j=kY(i)/m, when 0<=j<k, 0<=i<n;

2. з масиву обирається V(j);

3. елемент перевизначається V(j)=X(i).

Поиск по сайту: