Федеральне агентство з освіти
Бійський технологічний інститут (філія)
державного освітнього закладу
вищої професійної освіти
«Алтайський державний технічний університет ім. І.І. Ползунова »
(БТІ АлтГТУ)
КАФЕДРА
Інформаційних і керуючих систем
ПОЯСНЮВАЛЬНА ЗАПИСКА
До Курсові проекти (роботи)
«Генерування псевдовипадкових чисел. Метод середини квадрата »
2009
Введення
Курсова робота складається з двох основних частин: теоретичної та практичної. У теоретичній буде розглянуто поняття імовірнісного алгоритму, поняття «генератор випадкових чисел», застосування, методи генерування випадкових чисел, псевдовипадкові числа, трохи історії про генерування випадкових чисел і методі середини квадрата. У практичній - розгляд і реалізація методу середини квадрата, для цього робота розбита на кілька частин:
1. формулювання завдання.
2. побудова моделі
3. розробка алгоритму
4. кодування (реалізація) алгоритму
5. аналіз складності
6. перевірка правильності
Теоретична частина
Алгоритм називається імовірнісним (randomized), якщо він використовує генератор випадкових чисел (random - number generator). Це класичне визначення, дається в більшості літературних джерел (у нашому випадку Т. Кормен, Ч. Лейзерсон, Р. Ривест). Орієнтовна робота генератора виглядає так: Random [a, b] повертає з рівною імовірністю будь-яке ціле число в інтервалі від а до b. Наприклад Random [0,1] повертає 0 або 1с ймовірністю 1 / 2 частіше на практиці використовують генератор псевдовипадкових чисел (pseudorandom - number generator) - детермінований алгоритм, який видає числа, схожі на випадкові.
Крім того, генератори випадкових чисел називають датчиками випадкових чисел - це можуть бути різноманітні технічні пристрої, які здатні виробляти випадкові величини. Використовуємо приклад, наведений в опорному літературному джерелі (А. В. Налімов, Основи алгоритмізації) - використання шумливих радіоелектронних приладів (діоди, транзистори). При роботі такого приладу будемо рахувати, скільки разів v за фіксований час Δt напруга перевищило заданий рівень E0. двійкове випадкове число отримуємо за допомогою співвідношення μ = v mod 2. якщо частоти появи 0 і 1 рівні, то можна вважати, що пристрій виробляє випадкову послідовність двійкових цифр. Якщо ж частоти не рівні то вводимо яку-небудь схему стабілізації: групувати цифри парами, трійками, і т.д., а значення 0 і 1 приписувати деяким комбінаціям.
Зазвичай датчики містять кілька генераторів описаного типу, що працюють незалежно один від одного. Так що датчиком видається число 0, а 1 ... а m, записане у формі m-розрядної двійковій дробу.
Що стосується псевдовипадкових чисел, візьмемо будь-яку випадкову величину z, значення z 1, ..., z n, які обчислюються з якої-небудь заданої формулою і можуть бути використані замість випадкових чисел при вирішенні деяких завдань, називаються псевдовипадковими. Однією з переваг псевдовипадкових чисел є їх швидка генерація, до того ж вони не вимагають запам'ятовуючих пристроїв. Запас псевдовипадкових чисел обмежений. В якості стандартних звичайно рівномірно розподілені на інтервалі [0,1] псевдовипадкові числа.
Розглянемо так само поняття рівномірного розподілу. Рівномірним розподілом на кінцевій множині чисел називається такий розподіл, при якому будь-яке з можливих чисел має однакову ймовірність появи. Якщо не задано певний розподіл на кінцевій множині чисел, то прийнято вважати його рівномірним.
Більшість алгоритмів обчислення випадкових (псевдовипадкових) чисел, використовуваних при практичних розрахунках, засновані на рекурентних формулах першого порядку: γ n +1 = Φ (γ n), де γ o задано. Гладка функція y = Φ (x) не може породити хорошу послідовність псевдовипадкових чисел, тому що якщо при
допомогою дійсно випадкових чисел завдати точки з координатами (γ 1, γ 2); (γ 2, γ три); ...; (γ n, γ n +1); на квадрат [(0,1) * (0,1) ], то точки (γ 1, Φ (γ 1)); (γ 2, Φ (γ 2)); ...; (γ n, Φ (γ n)); ... На основі етогоположенія можна сформулювати умову щодо функції Φ ( x). Що б функція y = Φ (x) породжувала псевдовипадкові числа, її графік має щільно заповнювати квадрат [(0,1) * (0,1)] тобто вона повинна бути розривною в кожній точці. Оскільки рівномірно розподілені випадкові числа повинні довлетворять статистичним вимогам (наприклад, математичне сподівання дорівнює 0,5, дисперсія дорівнює 1 / 12 і т.д.), то умова щільного заповнення всього квадрата є тільки необхідним. Ще одна особливість алгоритмів типу γ n +1 = Φ (γ n) полягає в тому, що вони завжди породжують періодичні послідовності. Отже існують такі L і l, що γ L + i = γ l + i, (i = 1,2 ...). Нехай тепер L - найменше число, яке задовольняє останньому рівності і таке, що l <L. Існує безліч генераторів псевдовипадкових чисел. Практично всі алгоритми генерування псевдовипадкових чисел орієнтовані на конкретні машини (враховують особливості роботи процесора і способи зберігання інформації) та компілятори (враховуються особливості арифметики, реалізованої в конкретній мові програмування для конкретної машини). Тому готові генератори псевдовипадкових чисел перед використанням необхідно ретельно перевірити і налаштувати їх на конкретні умови.
Кожна з 10 цифр від 0 до 9 буде з'являтися приблизно один раз з 10 у рівномірній послідовності випадкових цифр. Кожній парі двох послідовних цифр слід з'явитися 1 раз з 100 і т.д. однак якщо взяти конкретну випадкову послідовність довжиною в мільйон цифр, то вона не завжди буде містити 100 000 нулів, 100 000 одиниць і т.д. Дійсно, можливість появи такої послідовності незначна; насправді, якщо розглядати досить велику сукупність таких послідовностей, то в середньому буде з'являтися 100 000 нулів, 100 000 одиниць і т.д.
Будь-яка конкретна послідовність, яка містить мільйон цифр, так само ймовірна, як і будь-яка інша. Якщо ми виберемо мільйон цифр навмання і якщо виявиться, що перші 999 999 з них - нулі, то ймовірність того, що остання цифра в цій послідовності - також нуль, все ще залишиться точно рівною однієї десятої в істинно випадкової ситуації. Це твердження, хоч і здається парадоксальним, не суперечить реальності.
Недосконалість перших механічних методів у спочатку пробудило інтерес до отримання випадкових чисел за допомогою звичайних арифметичних операцій, закладених в комп'ютер. Джон фон Нейман першим запропонував такий підхід близько 1946 року; його ідея полягала в тому, щоб звести в квадрат попереднє випадкове число і виділити середні цифри. Наприклад, ми хочемо отримати 10-значне число і попереднє дорівнювало 5772156649. зводимо його в квадрат і отримуємо 33317792380594909201, значить наступним числом буде 7923805949.
Метод середин квадратів фон Неймана, як було показано, фактично є порівняно бідним джерелом випадкових чисел. Небезпека полягає в тому, що послідовність прагнути ввійти у звичну колію, тобто короткий цикл повторюваних елементів. Наприклад, кожна поява нуля як числа послідовності призведе до того, що всі наступні числа також будуть нулями.
Деякі вчені експериментували з методом середин квадратів на початку 50-х років. Працюючи з чотиризначними числами замість десятизначних, Дж.Е. Форсайт випробував 16 різних початкових значень і виявив, що 12 з них призводять до циклічних послідовностей, що закінчується циклом 6100, 2100, 4100, 8100, 6100, ..., у той час як дві з них призводять до послідовностей, вироджуються в 0. більш інтенсивні дослідження, головним чином у двійковій системі числення, провів Н.К. Метрополіс. Він показав, що якщо використовувати 20-розрядне число, то послідовність випадкових чисел, отримана методом середин квадратів, вироджується в 13 різних циклів, причому довжина найбільшого періоду дорівнює 142.
Досить легко запустити метод середин квадратів з новим вихідним значенням, якщо виявити число 0, однак позбутися довгих циклів є доволі важко.
Практична частина
Метод середини квадрата
Формулювання завдання
Цей алгоритм є одним з перших і запропонований Дж. Нейманом. Нехай числа γ n 2k значимі, тобто γ n = 0, а1, а2, ... а2k. Тоді функцію Φ (γ n) визначимо
наступним чином: γ n +1 = Φ (γ n) = Franc {10-2k * Int (10 3k * γ 2 n)} тобто зведемо γ n в квадрат і отримаємо. γ n 2 = 0, b 1, b 2, ... b 4k. Потім відберемо середні 2k цифр і отримаємо γ n +1 = 0, b k +1 b 2 ... b 3 k. Тепер перейдемо до більш детального розгляду алгоритму.
У результаті роботи програми повинні отримати математичне сподівання і дисперсію, визначені для послідовності з 50 000 елементів. Дана послідовність з 50 000 елементів. По ходу рішення генеруємо 2k - розрядні псевдовипадкові числа. На вході повинно бути задано х 0-2k розрядне початкове число. М - послідовність випадкових чисел. Є ймовірність, що числа, що генеруються за допомогою алгоритму обнуляться, за умови х 0 <10 4. щоб уникнути цього потрібно довжину відрізка аперіодічності L збільшити, що детально буде розглянуто нижче.
Побудова моделі
Випадкова величина γ рівномірно розподілена на інтервалі [0,1], якщо визначаються співвідношеннями:
Р γ (γ) = 1, γε [0,1]; F γ (γ) =
Математичне сподівання
Тепер про згадане збільшенні довжини відрізка аперіодічності. Є ймовірність, що числа, що генеруються за допомогою алгоритму обнуляться, за умови х 0 <10 4. щоб уникнути цього потрібно довжину відрізка аперіодічності L збільшити. Практичні розрахунки показали, що L (довжина відрізка аперіодічності) достатньо мала, і це може стати причиною відмови від алгоритму середини квадрата. Довжину відрізка аперіодічності можна дещо збільшити, якщо при виконанні умови
Тепер функція γ n прийме наступний вигляд:
Φ (γ n) =
Для реалізації алгоритму потрібно визначити найбільше можливе значення k (чим більше це число, тим більше число значущих розрядів, а, отже, і довжина відрізка аперіодічності).
Таким чином, для забезпечення максимальної довжини відрізка аперіодічності потрібно, використовуючи найпростіші типи даних, вибрати такі, які забезпечують найбільше значення для k.
Наприклад, можна прийняти, що γ n є величина типу Single, а
При довжині слова в 64 біта під мантиссу відводиться 24 +32 розряду. За допомогою 56 розрядів можна закодувати 2 56 = (1024) 5 * 64, що відповідає 15 .. 16 значущим цифр. Таким чином, при величинах такого типу максимально можливе значення k одно 3 (т. к. 2k <7; 4k <15).
Розробка алгоритму
Приступимо до розробки алгоритму.
Алгоритм seredina [середина квадрата]
Шаг0 [ініціалізація] х: = х 0;
Шаг1 [цикл, обчислення послідовності M випадкових чисел х [1 .. M].]
For j: = 1 to M do [закінчення КРОК 2 і stop]
КРОК 2 [генерація нового випадкового числа]
Y: = X 2 [Y має 4k розрядів]
Число Х отримуємо видаленням по k розрядів з кожного кінця Y
X [j]: = X;
При k = 2 і х 0 = 0.2134 відповідно до першого оператором КРОК 2 отримаємо Y =
Для реалізації алгоритму потрібно написати процедуру, що реалізує метод середини квадрата, яку назвемо Rand, в якій при першому зверненні задається ціле число IX з [0.999999] і між викликами воно не повинно змінюватися. На виході маємо числа: Rand числа типу Single з (0,1), IX числа типу LongInt з (0,999999), K числа типу LongInt з (0, К +1). Далі поставимо змінні. Обнулив 7 і далі розряди числа Х, обчислимо квадрат Х. Виберемо 4 ... 9 розряди числа Y. Визначимо нове ціле випадкове число IX з [0.999999] і випадкову величину з [0.1]. Обчислимо число К з [0.K +1].
SHAPE \ * MERGEFORMAT
Малюнок 1. блок-схем програми
Ні SHAPE \ * MERGEFORMAT 
SHAPE \ * MERGEFORMAT
Малюнок 2. блок-схема процедури Rand
Кодування алгоритму
Program seredina {метод середини квадрата}
Uses crt;
Var
Urand: Single;
Dm, Dd: Double;
n, i, j, k, l, ll: LongInt;
F: Text;
Procedure Rand (var Ix, k: LongInt; Urand: Single);
Var
x, z: Single;
y, z1: Double; i: LongInt;
Begin
z: = Ix; x: = z {* 1.e-6}; {обнулив 7 і далі розряди числа Х.}
z1: = x +1. e-6; y: = z1 * z1 * 1.e-12; {обчислимо квадрат Х.}
z1: = y * 1.e +3; y: = z1-Trunc (z1); {виберемо 4 ... 9 розряди числа Y.}
if y <1.e-6 then
Begin
z1: = y * 1.e +6;
y: = z1-Trunc (z1);
End;
z1: = y * 1.e +6;
y: = Trunc (z1);
Ix: = Trunc (y); y: = y * 1.e-6; Urand: = y;
{Визначили нове ціле випадкове число IX з [0.999999] і випадкову величину з [0.1]}
k: = Round ((k +1) * y); {обчислюємо число К з [0, К +1]}
End; {Rand}
Begin
Clrscr;
Assign (F, 'd: / F / Rand.dat');
Rewrite (F);
n: = 3-23; Dm: = 0; Dd: = 0; ll: = 50000;
for l: = 1 to ll do
begin
k: = 100;
Rand (n, k, Urand);
Dm: = Dm + Urand / ll;
Dd: = Dd + (Urand-0.5) * (Urand-0.5) / ll;
End;
Writeln (F, 'M =', Dm, 'Sig ^ 2 =', Dd);
Close (F);
End.
У результаті роботи алгоритму, після створення текстового файлу за вказаною адресою, отримуємо файл Rand, що містить результат - математичне очікування і дисперсію.
Аналіз складності алгоритму
Для цього скористаємося способом, що полягає в підрахунку арифметичних операцій, необхідних для виконання алгоритму (в цьому випадку визначається робоча функція).
Нехай G (n) - алгоритм для вирішення певного класу задач, а n - розмірність розмірність окремої задачі з цього класу. Визначимо
Алгоритм G (n) поліноміальний, якщо
Функцію f (n) визначають як О
Бійський технологічний інститут (філія)
державного освітнього закладу
вищої професійної освіти
«Алтайський державний технічний університет ім. І.І. Ползунова »
(БТІ АлтГТУ)
КАФЕДРА
Інформаційних і керуючих систем
ПОЯСНЮВАЛЬНА ЗАПИСКА
До Курсові проекти (роботи)
«Генерування псевдовипадкових чисел. Метод середини квадрата »
2009
Введення
Курсова робота складається з двох основних частин: теоретичної та практичної. У теоретичній буде розглянуто поняття імовірнісного алгоритму, поняття «генератор випадкових чисел», застосування, методи генерування випадкових чисел, псевдовипадкові числа, трохи історії про генерування випадкових чисел і методі середини квадрата. У практичній - розгляд і реалізація методу середини квадрата, для цього робота розбита на кілька частин:
1. формулювання завдання.
2. побудова моделі
3. розробка алгоритму
4. кодування (реалізація) алгоритму
5. аналіз складності
6. перевірка правильності
Теоретична частина
Алгоритм називається імовірнісним (randomized), якщо він використовує генератор випадкових чисел (random - number generator). Це класичне визначення, дається в більшості літературних джерел (у нашому випадку Т. Кормен, Ч. Лейзерсон, Р. Ривест). Орієнтовна робота генератора виглядає так: Random [a, b] повертає з рівною імовірністю будь-яке ціле число в інтервалі від а до b. Наприклад Random [0,1] повертає 0 або 1с ймовірністю 1 / 2 частіше на практиці використовують генератор псевдовипадкових чисел (pseudorandom - number generator) - детермінований алгоритм, який видає числа, схожі на випадкові.
Крім того, генератори випадкових чисел називають датчиками випадкових чисел - це можуть бути різноманітні технічні пристрої, які здатні виробляти випадкові величини. Використовуємо приклад, наведений в опорному літературному джерелі (А. В. Налімов, Основи алгоритмізації) - використання шумливих радіоелектронних приладів (діоди, транзистори). При роботі такого приладу будемо рахувати, скільки разів v за фіксований час Δt напруга перевищило заданий рівень E0. двійкове випадкове число отримуємо за допомогою співвідношення μ = v mod 2. якщо частоти появи 0 і 1 рівні, то можна вважати, що пристрій виробляє випадкову послідовність двійкових цифр. Якщо ж частоти не рівні то вводимо яку-небудь схему стабілізації: групувати цифри парами, трійками, і т.д., а значення 0 і 1 приписувати деяким комбінаціям.
Зазвичай датчики містять кілька генераторів описаного типу, що працюють незалежно один від одного. Так що датчиком видається число 0, а 1 ... а m, записане у формі m-розрядної двійковій дробу.
Що стосується псевдовипадкових чисел, візьмемо будь-яку випадкову величину z, значення z 1, ..., z n, які обчислюються з якої-небудь заданої формулою і можуть бути використані замість випадкових чисел при вирішенні деяких завдань, називаються псевдовипадковими. Однією з переваг псевдовипадкових чисел є їх швидка генерація, до того ж вони не вимагають запам'ятовуючих пристроїв. Запас псевдовипадкових чисел обмежений. В якості стандартних звичайно рівномірно розподілені на інтервалі [0,1] псевдовипадкові числа.
Розглянемо так само поняття рівномірного розподілу. Рівномірним розподілом на кінцевій множині чисел називається такий розподіл, при якому будь-яке з можливих чисел має однакову ймовірність появи. Якщо не задано певний розподіл на кінцевій множині чисел, то прийнято вважати його рівномірним.
Більшість алгоритмів обчислення випадкових (псевдовипадкових) чисел, використовуваних при практичних розрахунках, засновані на рекурентних формулах першого порядку: γ n +1 = Φ (γ n), де γ o задано. Гладка функція y = Φ (x) не може породити хорошу послідовність псевдовипадкових чисел, тому що якщо при
допомогою дійсно випадкових чисел завдати точки з координатами (γ 1, γ 2); (γ 2, γ три); ...; (γ n, γ n +1); на квадрат [(0,1) * (0,1) ], то точки (γ 1, Φ (γ 1)); (γ 2, Φ (γ 2)); ...; (γ n, Φ (γ n)); ... На основі етогоположенія можна сформулювати умову щодо функції Φ ( x). Що б функція y = Φ (x) породжувала псевдовипадкові числа, її графік має щільно заповнювати квадрат [(0,1) * (0,1)] тобто вона повинна бути розривною в кожній точці. Оскільки рівномірно розподілені випадкові числа повинні довлетворять статистичним вимогам (наприклад, математичне сподівання дорівнює 0,5, дисперсія дорівнює 1 / 12 і т.д.), то умова щільного заповнення всього квадрата є тільки необхідним. Ще одна особливість алгоритмів типу γ n +1 = Φ (γ n) полягає в тому, що вони завжди породжують періодичні послідовності. Отже існують такі L і l, що γ L + i = γ l + i, (i = 1,2 ...). Нехай тепер L - найменше число, яке задовольняє останньому рівності і таке, що l <L. Існує безліч генераторів псевдовипадкових чисел. Практично всі алгоритми генерування псевдовипадкових чисел орієнтовані на конкретні машини (враховують особливості роботи процесора і способи зберігання інформації) та компілятори (враховуються особливості арифметики, реалізованої в конкретній мові програмування для конкретної машини). Тому готові генератори псевдовипадкових чисел перед використанням необхідно ретельно перевірити і налаштувати їх на конкретні умови.
Кожна з 10 цифр від 0 до 9 буде з'являтися приблизно один раз з 10 у рівномірній послідовності випадкових цифр. Кожній парі двох послідовних цифр слід з'явитися 1 раз з 100 і т.д. однак якщо взяти конкретну випадкову послідовність довжиною в мільйон цифр, то вона не завжди буде містити 100 000 нулів, 100 000 одиниць і т.д. Дійсно, можливість появи такої послідовності незначна; насправді, якщо розглядати досить велику сукупність таких послідовностей, то в середньому буде з'являтися 100 000 нулів, 100 000 одиниць і т.д.
Будь-яка конкретна послідовність, яка містить мільйон цифр, так само ймовірна, як і будь-яка інша. Якщо ми виберемо мільйон цифр навмання і якщо виявиться, що перші 999 999 з них - нулі, то ймовірність того, що остання цифра в цій послідовності - також нуль, все ще залишиться точно рівною однієї десятої в істинно випадкової ситуації. Це твердження, хоч і здається парадоксальним, не суперечить реальності.
Недосконалість перших механічних методів у спочатку пробудило інтерес до отримання випадкових чисел за допомогою звичайних арифметичних операцій, закладених в комп'ютер. Джон фон Нейман першим запропонував такий підхід близько 1946 року; його ідея полягала в тому, щоб звести в квадрат попереднє випадкове число і виділити середні цифри. Наприклад, ми хочемо отримати 10-значне число і попереднє дорівнювало 5772156649. зводимо його в квадрат і отримуємо 33317792380594909201, значить наступним числом буде 7923805949.
Метод середин квадратів фон Неймана, як було показано, фактично є порівняно бідним джерелом випадкових чисел. Небезпека полягає в тому, що послідовність прагнути ввійти у звичну колію, тобто короткий цикл повторюваних елементів. Наприклад, кожна поява нуля як числа послідовності призведе до того, що всі наступні числа також будуть нулями.
Деякі вчені експериментували з методом середин квадратів на початку 50-х років. Працюючи з чотиризначними числами замість десятизначних, Дж.Е. Форсайт випробував 16 різних початкових значень і виявив, що 12 з них призводять до циклічних послідовностей, що закінчується циклом 6100, 2100, 4100, 8100, 6100, ..., у той час як дві з них призводять до послідовностей, вироджуються в 0. більш інтенсивні дослідження, головним чином у двійковій системі числення, провів Н.К. Метрополіс. Він показав, що якщо використовувати 20-розрядне число, то послідовність випадкових чисел, отримана методом середин квадратів, вироджується в 13 різних циклів, причому довжина найбільшого періоду дорівнює 142.
Досить легко запустити метод середин квадратів з новим вихідним значенням, якщо виявити число 0, однак позбутися довгих циклів є доволі важко.
Практична частина
Метод середини квадрата
Формулювання завдання
Цей алгоритм є одним з перших і запропонований Дж. Нейманом. Нехай числа γ n 2k значимі, тобто γ n = 0, а1, а2, ... а2k. Тоді функцію Φ (γ n) визначимо
наступним чином: γ n +1 = Φ (γ n) = Franc {10-2k * Int (10 3k * γ 2 n)} тобто зведемо γ n в квадрат і отримаємо. γ n 2 = 0, b 1, b 2, ... b 4k. Потім відберемо середні 2k цифр і отримаємо γ n +1 = 0, b k +1 b 2 ... b 3 k. Тепер перейдемо до більш детального розгляду алгоритму.
У результаті роботи програми повинні отримати математичне сподівання і дисперсію, визначені для послідовності з 50 000 елементів. Дана послідовність з 50 000 елементів. По ходу рішення генеруємо 2k - розрядні псевдовипадкові числа. На вході повинно бути задано х 0-2k розрядне початкове число. М - послідовність випадкових чисел. Є ймовірність, що числа, що генеруються за допомогою алгоритму обнуляться, за умови х 0 <10 4. щоб уникнути цього потрібно довжину відрізка аперіодічності L збільшити, що детально буде розглянуто нижче.
Побудова моделі
Випадкова величина γ рівномірно розподілена на інтервалі [0,1], якщо визначаються співвідношеннями:
Р γ (γ) = 1, γε [0,1]; F γ (γ) =
Математичне сподівання
Тепер про згадане збільшенні довжини відрізка аперіодічності. Є ймовірність, що числа, що генеруються за допомогою алгоритму обнуляться, за умови х 0 <10 4. щоб уникнути цього потрібно довжину відрізка аперіодічності L збільшити. Практичні розрахунки показали, що L (довжина відрізка аперіодічності) достатньо мала, і це може стати причиною відмови від алгоритму середини квадрата. Довжину відрізка аперіодічності можна дещо збільшити, якщо при виконанні умови
Тепер функція γ n прийме наступний вигляд:
Φ (γ n) =
Для реалізації алгоритму потрібно визначити найбільше можливе значення k (чим більше це число, тим більше число значущих розрядів, а, отже, і довжина відрізка аперіодічності).
Таким чином, для забезпечення максимальної довжини відрізка аперіодічності потрібно, використовуючи найпростіші типи даних, вибрати такі, які забезпечують найбільше значення для k.
Наприклад, можна прийняти, що γ n є величина типу Single, а
При довжині слова в 64 біта під мантиссу відводиться 24 +32 розряду. За допомогою 56 розрядів можна закодувати 2 56 = (1024) 5 * 64, що відповідає 15 .. 16 значущим цифр. Таким чином, при величинах такого типу максимально можливе значення k одно 3 (т. к. 2k <7; 4k <15).
Розробка алгоритму
Приступимо до розробки алгоритму.
Алгоритм seredina [середина квадрата]
Шаг0 [ініціалізація] х: = х 0;
Шаг1 [цикл, обчислення послідовності M випадкових чисел х [1 .. M].]
For j: = 1 to M do [закінчення КРОК 2 і stop]
КРОК 2 [генерація нового випадкового числа]
Y: = X 2 [Y має 4k розрядів]
Число Х отримуємо видаленням по k розрядів з кожного кінця Y
X [j]: = X;
При k = 2 і х 0 = 0.2134 відповідно до першого оператором КРОК 2 отримаємо Y =
Для реалізації алгоритму потрібно написати процедуру, що реалізує метод середини квадрата, яку назвемо Rand, в якій при першому зверненні задається ціле число IX з [0.999999] і між викликами воно не повинно змінюватися. На виході маємо числа: Rand числа типу Single з (0,1), IX числа типу LongInt з (0,999999), K числа типу LongInt з (0, К +1). Далі поставимо змінні. Обнулив 7 і далі розряди числа Х, обчислимо квадрат Х. Виберемо 4 ... 9 розряди числа Y. Визначимо нове ціле випадкове число IX з [0.999999] і випадкову величину з [0.1]. Обчислимо число К з [0.K +1].
SHAPE \ * MERGEFORMAT
X: = X 0 |
For j: = 1 to M |
Y: = X 2 |
X [j]: = X |
Малюнок 1. блок-схем програми
z: = Ix; x: = z; z1: = x +1. e-6; y: = z1 * z1 * 1.e-12; z1: = y * 1.e +3; y: = z1- Trunc (z1) |
y <1 |
|
SHAPE \ * MERGEFORMAT
z1: = y * 1.e +6; y: = Trunc (z1); Ix: = Trunc (y); y: = y * 1.e-6; Urand: = y; k: = Round ((k +1) * y); |
Малюнок 2. блок-схема процедури Rand
Кодування алгоритму
Program seredina {метод середини квадрата}
Uses crt;
Var
Urand: Single;
Dm, Dd: Double;
n, i, j, k, l, ll: LongInt;
F: Text;
Procedure Rand (var Ix, k: LongInt; Urand: Single);
Var
x, z: Single;
y, z1: Double; i: LongInt;
Begin
z: = Ix; x: = z {* 1.e-6}; {обнулив 7 і далі розряди числа Х.}
z1: = x +1. e-6; y: = z1 * z1 * 1.e-12; {обчислимо квадрат Х.}
z1: = y * 1.e +3; y: = z1-Trunc (z1); {виберемо 4 ... 9 розряди числа Y.}
if y <1.e-6 then
Begin
z1: = y * 1.e +6;
y: = z1-Trunc (z1);
End;
z1: = y * 1.e +6;
y: = Trunc (z1);
Ix: = Trunc (y); y: = y * 1.e-6; Urand: = y;
{Визначили нове ціле випадкове число IX з [0.999999] і випадкову величину з [0.1]}
k: = Round ((k +1) * y); {обчислюємо число К з [0, К +1]}
End; {Rand}
Begin
Clrscr;
Assign (F, 'd: / F / Rand.dat');
Rewrite (F);
n: = 3-23; Dm: = 0; Dd: = 0; ll: = 50000;
for l: = 1 to ll do
begin
k: = 100;
Rand (n, k, Urand);
Dm: = Dm + Urand / ll;
Dd: = Dd + (Urand-0.5) * (Urand-0.5) / ll;
End;
Writeln (F, 'M =', Dm, 'Sig ^ 2 =', Dd);
Close (F);
End.
У результаті роботи алгоритму, після створення текстового файлу за вказаною адресою, отримуємо файл Rand, що містить результат - математичне очікування і дисперсію.
Аналіз складності алгоритму
Для цього скористаємося способом, що полягає в підрахунку арифметичних операцій, необхідних для виконання алгоритму (в цьому випадку визначається робоча функція).
Нехай G (n) - алгоритм для вирішення певного класу задач, а n - розмірність розмірність окремої задачі з цього класу. Визначимо
Алгоритм G (n) поліноміальний, якщо
Функцію f (n) визначають як О
Функція h (n) є Про 
Якщо f (n) є Про
Алгоритм G (n) називається поліноміальним, якщо
Розглянемо процедуру Rand. У ній всього 4 кроки, одне порівняння. Для процедури G (n) робоча функція має вигляд
Перевірка правильності програми
Аналіз структури програми
Для цього скористаємося керуючим графом (орієнтований граф, вершини якого - оператори, а дуги з'єднують оператори, між якими можлива передача управління).
6 7 8 9 10 11 12 14
SHAPE \ * MERGEFORMAT
22 21 20 19 18 17 15
Малюнок 4. Схема Мартинюка
На наведеній вище схемі Мартинюка шлях є простим, тому що він не містить жодної вершини або дуги більше одного разу. Схема правильна, так як виконується умова, що кожна вершина належить хоча б одному шляху по графу.
Таблиця 2. Матриця Шляхів
Матриця шляхів С - шляхів довжини 1.
Рис. 6
Таблиця 3. Матриця Шляхів
Матриця Р - матриця всіх шляхів
Всі елементи 1 стовпця рівні 1, значить в 1 вершину управління не передається ні з якою іншою. Всі елементи 1 рядка рівні 1, значить з 1 вершини управління не передається ні в яку іншу, звідси випливає, що схема програми є правильною.
Перевірка діапазону значень змінних
Dm - математичне сподівання, Dm: Dm + Urand / ll;
Dd - дисперсія, Dd: Dd + Urand;
k: Round ((k +1) * y);
L: array [1 .. 50 000];
ll: 50 000;
Ix: Trunc (y);
Urand: y;
X: z;
Z: Ix;
Y: z1 * z1z * 1.e-12, z1-Trunc (z1), Trunc (z1);
Z1: x +1. E-6, y * 1.e +3, y * 1.e +6.
Тестування програми
Перевірка вхідних даних. N: = 3-23, Dm: = 0, Dd: = 0, ll: = 50000, l: = [1 .. ll], k: = 10. всі вхідні дані обробляються правильно.
Список літератури
1. Основи алгоритмізації, навчальний посібник. А.В. Налімов. Барнаул 2000
2. Аналіз та розробка алгоритмів, методичні рекомендації. А.В. Налімов. Барнаул 2001
3. Алгоритми побудова і аналіз, Т. Кормен, Ч. Лейзерсон, Р. Ривест. Москва 2007 р.
4. Алгоритми дискретної математики, Л.Є. Захарова. Москва 2007 р.
5. Мистецтво програмування, Д.Е. Батіг. Том 2.
Якщо f (n) є Про
Алгоритм G (n) називається поліноміальним, якщо
Розглянемо процедуру Rand. У ній всього 4 кроки, одне порівняння. Для процедури G (n) робоча функція має вигляд
Перевірка правильності програми
Аналіз структури програми
Для цього скористаємося керуючим графом (орієнтований граф, вершини якого - оператори, а дуги з'єднують оператори, між якими можлива передача управління).
6 7 8 9 10 11 12 14
1 |
2 |
8 |
3 |
4 |
5 |
6 |
7 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
На наведеній вище схемі Мартинюка шлях є простим, тому що він не містить жодної вершини або дуги більше одного разу. Схема правильна, так як виконується умова, що кожна вершина належить хоча б одному шляху по графу.
Таблиця 2. Матриця Шляхів
Матриця шляхів С - шляхів довжини 1.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | |
| 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 2 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 3 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 4 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 5 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 6 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 7 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
| 8 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
| 9 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
| 10 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
| 11 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 |
| 12 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
| 13 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 |
| 14 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
| 15 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
Таблиця 3. Матриця Шляхів
Матриця Р - матриця всіх шляхів
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | |
| 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 2 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 3 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 4 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 5 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 6 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 7 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 8 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 9 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | |
| 10 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 |
| 11 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| 12 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 |
| 13 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 |
| 14 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
| 15 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
Перевірка діапазону значень змінних
Dm - математичне сподівання, Dm: Dm + Urand / ll;
Dd - дисперсія, Dd: Dd + Urand;
k: Round ((k +1) * y);
L: array [1 .. 50 000];
ll: 50 000;
Ix: Trunc (y);
Urand: y;
X: z;
Z: Ix;
Y: z1 * z1z * 1.e-12, z1-Trunc (z1), Trunc (z1);
Z1: x +1. E-6, y * 1.e +3, y * 1.e +6.
Тестування програми
Перевірка вхідних даних. N: = 3-23, Dm: = 0, Dd: = 0, ll: = 50000, l: = [1 .. ll], k: = 10. всі вхідні дані обробляються правильно.
Список літератури
1. Основи алгоритмізації, навчальний посібник. А.В. Налімов. Барнаул 2000
2. Аналіз та розробка алгоритмів, методичні рекомендації. А.В. Налімов. Барнаул 2001
3. Алгоритми побудова і аналіз, Т. Кормен, Ч. Лейзерсон, Р. Ривест. Москва 2007 р.
4. Алгоритми дискретної математики, Л.Є. Захарова. Москва 2007 р.
5. Мистецтво програмування, Д.Е. Батіг. Том 2.