Вычислительный практикум (моделирование распределений), 322 гр., спец. СМ (14.Б02-мм)

Место и время проведения: вторник, первая пара, ауд. 2408
Преподаватель: Звонарев Никита nikitazvonarev@gmail.com

Темы прошедших занятий¶

  - 14/02/17 Введение. Мультипликативный датчик (начало)
  - 21/02/17 RANDU. Линейный конгруэнтный датчик. Гиперплоскости и волновое число. Датчики Фибоначчи.
  - 28/02/17 Комбинированные генераторы. Mersenne Twister.
  - 07/03/17 Jump-ahead и leap-frog. Возведение матрицы в степень. ГПСЧ в Cpp и в R.
  - 14/03/17 Моделирование в выпуклом и невыпуклом многоугольнике. Тривиальная аналитическая геометрия, алгоритмы Джарвиса, Грэхэма, отрезания ушей.
  - 21/03/17 Немного про критерий Колмогорова, Хи-квадрат, проверку гипотез, как применяется для тестирования генераторов. Birthday spacings test. Известные батареи тестов. Идеи семейства [PCG](http://www.pcg-random.org/).
  - 28/03/17 Пример на Cpp с[синглтоном](../../assets/study/spring2017/prgcpp2017.zip) [(ещё вариант)](../../assets/study/fall2012/3cpp_mm/randomdemomulfiles.zip). Многомерное нормальное распределение. EVD, SVD. Равномерное распределение на сфере, в шаре.
  - 04/04/17 Метод отбора, векторизованная реализация на R.
  - 11/04/17 Моделирование смеси, векторизованная реализация на R. Моделирование случайных перестановок и подвыборок.
  - 18/04/17 Python 3: введение
  - 25/04/17 //сдача заданий//
  - 02/05/17 Ещё немного про Python + сдача
  - 09/05/17 День Победы (выходной)
  - 16/05/17 //Сдача//
  - 24/05/17 //Зачёт//

Задачки и материалы к ним¶

Из двух задач с одинаковым номером можно взять любую (на ваш выбор). Главное – сдать её до зачёта :).

1 а). Трёхмерные интегралы и RANDU. Взять плохой датчик и продемонстрировать, что М-К для одно- или двумерного интеграла работает, а для трёхмерного ломается. Достаточно выбрать подходящую (объяснял на паре) ограниченную функцию на [0, 1]^k, у которой вы можете взять интеграл аналитически.

1 б). Дан текстовый файлик, содержащий последовательность, полученную линейным конгруэнтным генератором вида X_{i+1} = A X_i + C (mod M), где M – простое. Требуется восстановить все параметры генератора. Утверждается, что всё можно спокойно посчитать в int64.

2 a). Реализовать процедуру jump-ahead для одного из следующих типов: студенты 1, 4 и 7 – линейный конгуэнтный, Wichman-Hill, L’Ecuyer; 2, 5, 8 – фибоначчиевый тип по сложению или вычитанию; 3, 6, 9 – фибоначчиевый тип по умножению или XOR. Номера см. в табличке снизу. Можно взять вариант потруднее, если хотите. Необходимо сгенерировать какую-нибудь последовательность и а) продемонстрировать, что jump-ahead совпадает с вычислением “в лоб” для небольших N (N порядка сотни) б) работает мгновенно для более-менее разумного большого N, например, миллиарда.

Важное замечание: следите за отсутствием переполнений при возведении матрицы в степень.

2 б). Случайный генератор Blum-Blum-Shub. В файле содержится последовательность, полученная случайным генератором BBS, т.е. x_{k+1} = x_k^2 mod pq, где p, q — большие простые числа, такие, что целые части p/2 и q/2 тоже простые (так называемые, Safe primes). Первая задача — научиться продолжать последовательность вперед. Вторая задача — научиться делать для этой последовательности jump-ahead, т.е. быстро находить x_N для произвольного N. Третья задача — научиться продолжать последовательность назад. Четвертая — научиться делать jump-ahead назад. Пятая — найти какое-нибудь число, кратное периоду последовательности. Шестая — найти период последовательности. // Задача подразумевает желание немного вспомнить алгебру //

3) Реализовать моделирование равномерного распределения в многоугольнике, промоделировать ~10^4 – ~10^6 точек и нарисовать их. Два варианта:

3 а) Сгенерировать два выпуклых многоугольника (в ~10 вершин и в ~1000 вершин), реализовать моделирование в выпуклом случае.

3 б) Взять небольшой невыпуклый многоугольник, реализовать моделирование в невыпуклом случае. Например, можно взять многоугольник из файла (это CSV, вершины в порядке обхода против часовой стрелки. Помните, что между последней и первой вершиной есть отрезок), и продемонстрировать ваше решение на нём.

Важное замечание: моделирование дискретного распределения должно работать быстро! Быстро – это за константу или амортизированную константу, т.е. наивный метод обратной функции не подойдёт. Используйте sample() в R, std::discrete_distribution в Cpp.

4 а) Реализовать многомерное нормальное распределение с невырожденной и вырожденной (несколько примеров) ковариационной матрицей, без использования готовой функций (для моделирования в R разрешён только rnorm()). Продемонстрировать проекции на различные плоскости на рисунке.

4 б) Реализовать равномерное распределение в d-мерном шаре и на сфере (несколько примеров). Продемонстрировать проекции на различные плоскости на рисунке. По желанию можно попробовать пакет rgl.

5 а) Реализовать метод отбора на R, “наивным” и быстрым способом. Сравнить по скорости. Проверить корректность с помощью критерия Колмогорова-Смирнова. В качестве плотности распределения можно взять любую, например, C (exp(x)+exp(-x)) на [-1;1].

Замечание: реализацию “наивным” способом можно не писать, если ваша плотность распределения лежит в (-∞;+∞) или [0; +∞).

5 б) Реализовать моделирование случайной перестановки с помощью одного из упомянутого на паре метода на Cpp. Промоделировать перестановку много (~10^5-~10^7) раз, проверить распределение перестановок с помощью распределения позиции i-го элемента и числа циклов длины k для малых и больших длин перестановок (пользуясь соотношениями, упомянутыми на паре, и критерием Хи-квадрат).

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

Результаты сдачи заданий¶

	1	2	3	4	5
1) Быков Кирилл	+	+	+	+	+
2) Лунев Иван	+	+	+	+	+
3) Федоров Никита	+	+	+	+	+
4) Страшко Владислав	+	+	+	+	+
5) Третьякова Александра	+	+	+	+	+
6) Романова Елизавета	+	+	+	+	+
7) Зенкова Наталья	+	+		+	+
8) Понизова Вероника	+	+		+	+
9) Мийоски Антоний	+	+	+	+	+

Литература (прошлогодняя)¶

Fishman G.S. Monte-Carlo. Concepts, Algorithms and Applications Про методы Монте-Карло, моделирование случайных величин, генераторы. Отличное введение.
Schneier B. Applied Cryptography Если кто-то интересуется криптографическим аспектом моделирования случайных чисел, то надо начать с этой книги.
Knuth D. The Art of Computer Programming, volume II, chapter 3 (Random numbers) Про генераторы, фундаментально
McCallum Q.E., Weston S. Parallel R. Data Analysis in the Distributed World Параллельное программирование на R
Akritas A.G. Elements of Computer Algebra With Applications Об алгоритмах компьютерной алгебры (проверка на простоту, разложение на множители, характериситческие многочлены и прочее). Сама книга достаточно редкая, но ее русский перевод (Основы компьютерной алгебры с приложениями, 1994) найти очень легко.
Shoup V. A Computational Introduction to Number Theory and Algebra Более современная книга по вычислительной алгебре
Василенко, О. Н. Теоретико-числовые алгоритмы в криптографии

Литература (новая)¶

Melissa E. O’Neill. PCG: A Family of Simple Fast Space-Efficient Statistically Good Algorithms for Random Number Generation
Richard Arratia and Simon Tavare. The Cycle Structure of Random Permutations The Annals of Probability. Vol. 20, No. 3 (Jul., 1992), pp. 1567-1591
На ту же тему. Статья в блоге Теренса Тао The number of cycles in a random permutation