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

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

Читайте также:
  1. Алгоритми пошуку
  2. Алгоритми «швидкого» сортування
  3. Закони Рауля, їх формулювання, математичні вираження, взаємозв'язок. Тиск насиченої пари над розчинами, температури кипіння та кристалізації розчинів.
  4. Зробити аналіз ситуаційних задач, створити навчальні алгоритми
  5. Тема 10. Основы программирования на алгоритмическом языке VBA.Объектно-ориентрованное программирование.
  6. Тема: Розробка програм з циклічною обробкою даних. Однопрохідні алгоритми.

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

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

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

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

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).


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |

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



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.003 сек.)