3. Эмпирические критерии

Критерий равномерности

Берём случайную величину, делаем n измерений, считаем количество случаев каждого значения. Вероятность каждого значения 1/D, если D-число категорий. Далее применяем хи-квадрат.

Критерий серии

Независимость распределения пар соседних чисел. Два числа Q и R. Вероятность 1/D^2.

Пары берутся так, чтобы элемент из одной пары не был в другой паре.

[2,7],[3,4],[8,1]

Критерий интервалов

Определяются длины интервалов между появлениями величины Uj на определённом отрезке.

Критерий разбиения (покер-критерий)

Берутся 5-ки значений. Подсчитывают, сколько получается пятёрок, где все числа разные (abcde), сколько пятёрок с 2-мя одинаковыми (aabcd), сколько пятёрок с 2 парами (aabbc), сколько пятёрок с тройками (aaabc), aaaab, aaaaa.

Критерий собирания купонов

Берутся длины отрезков, содержащих полный набор.

Критерий перестановок

Выбираются N групп по T элементов. Количество перестановок T! Способов.

Критерий монотонности

Берётся случайная величина, определяются возрастающие и убывающие серии.

Метод середины квадрата

Линейный конгруэнтный метод

Модуль линейной конгруэнтной последовательности

Понятие множителя, приращения, начального значения

Мультипликативный конгруэнтный метод xk+1 = (a*xk) mod m

Смешанный конгруэнтный метод

Период последовательности случайных чисел — количество значений

Потенциал линейной последовательности — наименьшее целое S, т.ч. (A-1)^S = 0 mod M.

Квадратичный конгруэнтный метод

Аддитивный генератор: xk+1 = xk + x(k-n) mod m.

Метод ковэю: xk+1 =xk*(xk + 1) mod N.

Метод митчелла и мурра: разновидность метода аддитивной генерации.

Обратная конгруэнтная последовательность

Рандомизация перемешиванием

Критерий хи-квадрат (метод максимального правдоподобия)

Функция распределения X

Эмпирическая выборочная функция распределение — количество Xi <= X / N — отношение числа элементов выборки к её объёму.

Критерий Колмогорова-Смирнова

Критерий равномерности (частот).

Критерий серий

Покер-критерий

Критерий собирания купонов

Критерий перестановок

Равномерное распределение

Нормальное (Гауссово) распределение

Экспоненциальное (показательное) распределение

Среднее значение

Дисперсия

мода — значение во множестве наблюдений, которое встречается наиболее часто

медиана выборки — значение, которое разбивает ряд значений на две части.

Эксцесс

Асимметричность — смещение распределения относительно мат. ожидания.

5. Технологии параллельных вычислений

Системы: MPI, OpenMP.

Будем работать с версией 1.2.5 .

{пропущено, ибо очевидно}

6. Порождение сочетаний, перестановок, кодов Грея

Сочетания

1,2,3,4,5.6

1,2,3 1,4,5 2,4,6

1,2,4 1,4,6 2,5,6

1,2,5 1,5,6 3,4,5

1,2,6 2,3,4 3,4,6

1,3,4 2,3,5 3,5,6

1,3,5 2,3,6 4,5,6

1,3,6 2,4,5

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

1,2,3

1,2,3 2,1,3 3,1,2

1,3,2 2,3,1 3,2,1

1 2 3 1/2 → 2 3 4 1

1 2 3 3/2 → 1 3 4 2

1 2 3 5/2 → 1 2 4 3

1 2 3 7/2 → 1 2 3 4

Коды Грея

Код, у которого каждое последующее число отличается от предыдущего в одном разряде.

000

010

011

111

110

100

101

001

Кодовое расстояние по Хэммингу = 1.

Циклический код Грея — у которого первое и последнее число различаются в одном разряде.