Федеральне державне бюджетне освітня установа
Вищої професійної освіти
тольяттінській державний університет
Інститут математики, фізики та інформаційних технологій
Кафедра Прикладної математики та інформатики
Профіль Математичне моделювання
Звіт по самостійній роботі
з дисципліни Получісленние алгоритми
на тему: Емпіричні критерії перевірки випадкових послідовностей
Виконала: Парамонова К.С.
група ПМІм - тисяча триста одна
Прийняв: Мельников Б.Ф.
Тольятті 2014
Зміст
Емпіричні критерії перевірки випадкових послідовностей. Критерій частот, серій, інтервалів, разбиений, перестановок, монотонності, конфліктів
Лінійний конгруентний метод
Основні критерії перевірки випадкових спостережень
Емпіричні критерії
Критерій серій
Покер-критерій (критерій разбиений)
Критерій перестановок
Критерій монотонності
Критерій конфліктів
Емпіричні критерії перевірки випадкових послідовностей. Критерій частот, серій, інтервалів, разбиений, перестановок, монотонності, конфліктів
Числа, які вибираються випадковим чином, знаходять безліч корисних застосувань: моделювання.
Це дозволяє зробити моделі схожими на реальні явища; вибірковий метод. Часто неможливо досліджувати всі варіанти, але випадкова вибірка забезпечує розуміння того, що можна назвати типовою поведінкою raquo ;; чисельний аналіз.
Для вирішення складних завдань чисельного аналізу була розроблена техніка, що використовує випадкові числа; комп'ютерне програмування. Випадкові числа є хорошим джерелом даних для тестування ефективності комп'ютерних алгоритмів; прийняття рішень; естетика; розваги.
Рівномірним розподілом на кінцевій множині чисел називається такий розподіл, при якому кожне з можливих чисел має однакову ймовірність появи. Якщо не задано певний розподіл на кінцевій множині чисел, то прийнято вважати його рівномірним [3]. Джон фон Нейман першим запропонував в 1946 р ідею звести в квадрат випадкове число і виділити з нього середні цифри. Наприклад, необхідно отримати нове десятизначні числа по числу 5772156649 . Зводимо наявне число в квадрат і виділяємо середні 10 чисел:
.
Новим сгенерованими числом буде число 7923805949. Ця послідовність не випадкова, вона здається такою. Послідовності, що генеруються детерміністичним шляхом, таким як цей, називаються псевдовипадковими або квазіслучайном.
Метод середини квадратів фактично є порівняно бідним джерелом випадкових чисел. Небезпека полягає в короткому циклі (періоді) повторюваних елементів. Розглянемо методи генерування послідовності випадкових дробів [3], тобто випадкових дійсних чисел U n , рівномірно розподілених між нулем і одиницею. Будемо генерувати ціле число Х n між нулем і деяким числом U , тоді дріб при m gt;=U
U n =Х n /m
буде належати [0,1]. Зазвичай m вибирають рівним розміру комп'ютерного слова. Позначимо m=b e , де b - основа системи числення, використовуваної ЕОМ, а e - число розрядів машини. Тому Х n можна за традицією розглядати як ціле число, що займає все комп'ютерне слово з крапкою в правому кінці слова, а U n - як вміст того ж слова з крапкою в лівому кінці слова.
Лінійний конгруентний метод
Виберемо чотири числа [3]:
m - модуль, m gt; 0 ;
a - множник, 0 ? a lt; m ;
c - приріст, 0 ? з lt; m ; ...
