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

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

Критерий получения зачёта

1. Пять плюсиков за все задания
2. Минимум 2 из 5 сданных программ должны быть написаны на Python

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

  - 14/02/23 Введение. Классификация генераторов. RANDU (без теории).
  - 21/02/23 //Пропуск (болел)//
  - 28/02/23 Моделирование равномерного дискретного р-ния. Линейный конгруэнтный датчик. Гиперплоскости и волновое число. Взлом линейного конгруэнтного датчика.
  - 07/03/23 Датчики Фибоначчи. Комбинированные генераторы (Wichmann-Hill...). Jump Ahead: быстрое возведение матрицы в степень, etc.
  - 14/03/23 Известные батареи тестов. Birthday spacings test и другие тесты. Немного про Mersenne Twister. Идеи семейства PCG.
  - 21/03/23 Немного про Python 3.
  - 28/03/23 ГПСЧ в C++  ([пример](https://pastebin.com/CX7H5txk)). Моделирование р.р. в выпуклом и невыпуклом многоугольнике. Тривиальная аналитическая геометрия, алгоритмы Джарвиса и «отрезания ушей».
  - 04/04/23 ГПСЧ в R. Написание своего ГПСЧ в R. Моделирование случайных перестановок и подвыборок. [Теория](../../assets/study/spring2020/permutations.pdf).
  - 11/04/23 Многомерное нормальное распределение. Eigendecomposition, разложение Холецкого. Равномерное распределение на сфере, в шаре, в эллипсоиде. [Теория](../../assets/study/spring2020/multivariate_norm.pdf).
  - 18/04/23 Ассоциативные массивы: двоичное дерево поиска и хэш-таблицы. Хэш-функции. Немного о требованиях к криптографическим хэш-функциям. Полиномиальный хэш: связь с LCG, [коллизии на строках Морса-Туэ](http://codeforces.com/blog/entry/4898).
  - 25/04/23 //Приём задач//
  - 02/05/23 //Приём задач//
  - 09/05/23 //Пропуск (праздник)//
  - 16/05/23 //Приём задач//
  - 23/05/23 //Приём задач//
  - 31/05/23 //Зачёт: среда, 11:00, 2444//

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

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

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

1 б). Трёхмерные интегралы и RANDU. 1. Взять датчик RANDU, написать его реализацию, продемонстрировать распределение случайных трехмерных векторов, сгенерированных им, в единичном кубе [0;1)^3 (например, с использованием пакета rgl в R или рисованием точек на плоскости с использованием подходящей проекции…), наглядно показать гиперплоскости, на которых лежат точки. 2. Подобрать трёхмерный интеграл, на котором метод Монте-Карло с использованием псевдослучайных величин из датчика RANDU даёт далёкую от истинной оценку интеграла по единичному кубу. Сравнить значения, полученные по М-К с помощью RANDU, с помощью адекватного генератора (например, Mersenne Twister) и посчитанные аналитически (если это возможно).

2 a). Реализовать процедуру jump-ahead для датчика (вариант указан в таблице). Продемонстрировать, что jump-ahead совпадает с вычислением “в лоб” для небольших N (N порядка сотни), и работает мгновенно для более-менее разумного большого N, например, миллиарда.

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

2 б). Случайный генератор Blum-Blum-Shub. В файле содержится последовательность, полученная случайным генератором BBS, т.е. \$x_{k+1} = x_k^2\$ \$(\text{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 в C++, random.choices в python.

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

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

5 Реализовать моделирование многомерного нормального распределения с заданной ковариационной матрицей, без использования готовой функций (для моделирования в R разрешён только rnorm()). Убедиться, что выборочная ковариационная матрица (cov() в R) сходится к заданной с увеличением размера выборки. Реализовать равномерное распределение на заданном множестве X. Продемонстрировать проекции на различные плоскости на рисунке. По желанию можно попробовать продемонстрировать результаты с помощью пакета rgl. Два варианта:

а) Для многомерного нормального — случай невырожденной ковариационной матрицы, X — d-мерный шар.

б) Для многомерного нормального — случай вырожденной ковариационной матрицы, X — d-мерная сфера.

Прошлогодние темы

  - 15/02/22 Введение. Классификация генераторов. RANDU (без теории).
  - 22/02/22 Линейный конгруэнтный датчик. Гиперплоскости и волновое число. Взлом линейного конгруэнтного датчика.
  - 01/03/22 Датчики Фибоначчи. Комбинированные генераторы (Wichmann-Hill...). Jump Ahead: быстрое возведение матрицы в степень, etc.
  - 08/03/22 //Пропуск (праздник)//
  - 15/03/22 Моделирование равномерного дискретного отбором (забыл на 1 паре). Известные батареи тестов. Birthday spacings test и другие тесты. Немного про Mersenne Twister. Идеи семейства PCG.
  - 22/03/22 Немного про Python 3.
  - 29/03/22 ГПСЧ в C++  ([пример](https://pastebin.com/CX7H5txk)). Моделирование р.р. в выпуклом и невыпуклом многоугольнике. Тривиальная аналитическая геометрия, алгоритм Джарвиса и «отрезания ушей».
  - 05/04/22 ГПСЧ в R. Написание своего ГПСЧ в R. Моделирование случайных перестановок и подвыборок. [Теория](../../assets/study/spring2020/permutations.pdf).
  - 12/04/22 Многомерное нормальное распределение. Eigendecomposition, разложение Холецкого. Равномерное распределение на сфере, в шаре, в эллипсоиде. [Теория](../../assets/study/spring2020/multivariate_norm.pdf).
  - 19/04/22 Ассоциативные массивы: двоичное дерево поиска и хэш-таблицы. Хэш-функции. Немного о требованиях к криптографическим хэш-функциям. Полиномиальный хэш: связь с LCG, [коллизии на строках Морса-Туэ](http://codeforces.com/blog/entry/4898).
  - 26/04/22 //Приём задач//
  - 03/05/22 //Приём задач//
  - 10/05/22 //Пропуск (праздник)//
  - 17/05/22 //Приём задач//
  - 24/05/22 //Приём задач//
  - 03/06/22 11:00, 2408 Зачёт

Ссылка на прошлый год

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

	1	2	3	4	5
1) Арина Филатова	+P	+P	+P	+	+P
2) Яна Салова	+P	+P	+P	+	+P
3) Дарья Булгакова	+P	+P	+P	+	+P
4) Михаил Олейник	+	+P	+P	+	+
5) Егор Потешкин	+P	+P	+P	+	+
6) Никита Хромов	+P	+P	+P	+	+
7) Яков Подлеснов	+P	+P	+P	+P	+P
8) Михаил Киселев	+P	+P	+P	+	+

Литература (старая)

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

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

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