Учебная работа. Реферат: Машинная имитация случайной последовательности чисел

Учебная работа. Реферат: Машинная имитация случайной последовательности чисел

Федеральное агентство по образованию

Государственное образовательное учреждение высшего

проф образования

Тульский муниципальный институт

Факультет экономики и Права

Кафедра Автоматических информационных и управляющих систем

отчет по лабораторной работе №1:

«

МАШИННАЯ ИМИТАЦИЯ

СЛУЧАЙНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ ЧИСЕЛ

».

Выполнила: студентка гр.730971

Иммель Я.С.

Принял: Семенчев Е. А.

Тула 2010

ЦЕЛЬ:
исследование функционирования программных датчиков псевдослучайных чисел. Практическая проверка свойства генераторов случайных чисел.

Ход работы:

Мультипликативный конгруэнтный способ
. Способ представляет собой арифметическую функцию для генерирования конечной последовательности умеренно распределённых чисел. Основная формула способа имеет вид:

Xi+1
=aXi
(mod m),

где a и m — неотрицательные целые числа. Согласно этому выражению, мы должны взять крайнее случайное число Xi
, помножить его на неизменный коэффициэнт a
и взять модуль приобретенного числа по m ( т.е. поделить на aXi
и остаток считать как Xi+1
). Потому для генерирования последовательности чисел Xi
нужны изначальное

Верный выбор модуля не зависит от системы счисления, применяемой в данной ЭВМ (Электронная вычислительная машина — комплекс технических средств, предназначенных для автоматической обработки информации в процессе решения вычислительных и информационных задач). Для ЭВМ (Электронная вычислительная машина — комплекс технических средств, предназначенных для автоматической обработки информации в процессе решения вычислительных и информационных задач), где применяется двоичная система счисления, m=2N
( N-число двоичных цифр в машинном слове ). Тогда наибольший период (который выходит при правильном выборе a и X0
)

L=2N-2
=m/4, (N>2) .

Выбор a
и X0
зависит также от типа ЭВМ (Электронная вычислительная машина — комплекс технических средств, предназначенных для автоматической обработки информации в процессе решения вычислительных и информационных задач). Для двоичной машинки

a=8T±3;

где T быть может хоть каким целым положительным числом, а X0
-любым положительным, но нечётным числом. Обозначенный выбор констант упрощает и ускоряет вычисления, но не обеспечивает получения периода наибольшей длины. Больший период можно получить, если взять m, равное большему обычному числу, которое меньше чем 2N
, и a, равное корню из m. Наибольшая длина последовательности будет увеличена от m/4 до m-1 ( способ Хатчинсона). Изложенный метод, записанный на псевдокоде, представлен в приложении. имя подпрограммы-RANDU.

Подпрограмма RANDU (RANDOM) имеется в математическом обеспечении почти всех ЭВМ (Электронная вычислительная машина — комплекс технических средств, предназначенных для автоматической обработки информации в процессе решения вычислительных и информационных задач) (в том числе и РС). При всем этом константы, применяемые в подпрограмме, для 32-разрядного машинного слова имеют значения a=513
=1220703125, i/m=0,4656613E-9.

Смешанные конгруэнтные способы.
На базе конгруэнтной формулы были сделаны и испытаны 10-ки генераторов псевдослучайных чисел. Работа этих генераторов базирована на использовании формулы

Xi+1
=aXi
+C(mod m),

где a, c, m- константы, обычно автоматом вычисляемые в подпрограмме. На базе этого метода разработана процедура URAND, которая приведена в приложении 1.1. Грин, Смит и Клем предложили аддитивный конгруэнтный способ.
н основан на использовании рекуррентной формулы

Xi+1
=(Xi
+Xi-1
)(mod m).

При X0
=0 и X1
=1 этот приводит к особенному случаю, именуемому последовательностью Фибоначчи.

Остальные методы основаны на композиции 2-ух генераторов с перемешиванием получаемых последовательностей.

Так как при использовании детерминированных алгоритмов получаемая последовательность чисел является псевдослучайной, возникает вопросец: как они близки по собственному поведению случайным? Для ответа на него предложено величавое огромное количество самых различных способов статических испытаний.

Частотные испытания.
Употребляют или аспект хи-квадрат, или аспект Колмогорова-Смирнова для сопоставления близости распределения приобретенного набора чисел к равномерному распределению.

Весь спектр чисел [0,1] разбивается на k интервалов. Статистика определяется выражением

где f0
-наблюдаемая частота для всякого интервала; fe
-ожидаемая частота для всякого интервала ( fe
=p*N, N-число опытов ).

Если =0, то наблюдаемые и на теоретическом уровне предсказанные значения частот буквально совпадают. Если >0, то расчётные значения сравниваются с табличными значениями T
. Значения T
табулированы для разных чисел степеней свободы v=r-1-m, где r-число интервалов, m-число характеристик распределения, определяемых из опыта, и уровней доверительной вероятности 1-a. Если расчётная величина оказывается больше табличной, то меж наблюдаемым и теоретическим распределением имеется существенное расхождение.

Набросок 1 – Схема алгоратма

Набросок 2 – Рабочая программка

Выводы:
исследование функционирования программных датчиков псевдослучайных чисел. Практическая проверка свойства генераторов случайных чисел.

способы получения на ЭВМ (Электронная вычислительная машина — комплекс технических средств, предназначенных для автоматической обработки информации в процессе решения вычислительных и информационных задач) значений случайной величины, умеренно распределённой в интервале [0,1], можно поделить на три огромные группы:

1.
Внедрение физических датчиков (генераторов) случайных чисел.

2.
Внедрение таблиц случайных чисел.

3.
Получение псевдослучайных чисел.

]]>