Предыдущая страница реферата | 29  30  31  32  33  34  35  36  37  38  39 | Следующая страница реферата

слишком большой объем. Вместо этого решено было создать библиотеку реализаций

и сложить в одном месте в инете. Пока это место находится по адресу:

ftp://ftp.wtc-ural.ru/pub/ru.crypt

XI. Здесь пары вопрос/ответ, которые я затруднился определить в какой-либо

раздел. Вобщем, "разное" :)

Q: Как проверить "случайность" моего ГСП (генератор случайной

последовательности).

A1: В интеpнете есть "Diehard test battery". Этот комплект содеpжит 15 тестов

чисел на случайность. Адpес http://stat.fsu.edu/~geo/diehard.html

       

A2:

Предположим у тебя имеется файл (массив,набор чисел) значений некоторой

случайной величины и ставится задача изучения ее свойств, т.е. являются ли

эти значения равномерно распределенными (равновероятными) в некотором

интервале.

Относительно изучаемой случайной величины можно сделать два предположения,

называемых нуль-гипотезой и альтернативной гипотезой:

1) Случайная величина имеет равномерное распределение (нуль-гипотеза)

2) Случайная величина не имеет равномерного распределения, т.е. закон

   распределения случайной имеет уклонения от равномерного распределения

   (альтернативная гипотеза).

    В математической статистике сущесвуют ряд тестов, назваемых критериями

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

соответствия теоретически ожидаемому закону распределения. Примерами

таких критериев согласия являются Хи-квадрат (критерий Пирсона) и критерий

Kолмогорова-Смирнова, критерий серий и т.д. Kритериев много.

    Статистические критерии могут установить только отличие теоретического

и экспериментального распределений,  поэтому нуль-гипотеза,как правило

выдвигается для проверки - нет ли оснований для ее отбрасывания.

Другими словами невозможно доказать "чистую случайность" последовательности,

но можно с определенной степенью вероятности опровергнуть противоположное

утверждение. Таким образом, для решения является ли различие достоверным

необходимо установить границы для близости-различия частот в выборке и

теоретически ожидаемых частот. Данная величина называется уровнем значимости,

и обычно принимает значения 5%, 1%, 0.1%. Результат называется значимым на

уровне 5%, если правильная нуль-гипотеза будет отклонена не более, чем в 5%

случаев.

                  Kритерий согласия Хи-квадрат.

    Пусть необходимо протестировать генератор, выдающий некоторую

последовательность бит, относительно которой выдвигается нуль-гипотеза

о том, что эта последовательность имеет равномерное распределение.

Обозначим объем выборки n. Пусть мы сгенерировали 100 бит, тогда n=100.

    Пусть выборка разделена на k классов. Если, например, исследуем частоты

появления только 0 и 1 - тогда количество классов два.  Пусть В_i -

наблюдаемая частота=количество появлений некоторого признака в выборке.

Обозначим В_0 - количество  нулей, В_1 - количество единиц.

Пусть E_i - ожидаемая частота признака i. Для нашего случая E_0=E_1= 0.5*n.

    Формула Хи-квадрат для вычисления различия между экспериментальным и

теоретическим распределениями следующая:

             i=k-1

Рекомендуем скачать другие рефераты по теме: ответы 5 класс, реферат теория.





Предыдущая страница реферата | 29  30  31  32  33  34  35  36  37  38  39 | Следующая страница реферата