Это старая версия документа!
Содержание
322 гр., спец. СМ, Вычислительный практикум (моделирование распределений)
Место и время проведения: вторник, вторая пара, ауд. 2412
Преподаватель: Звонарев Никита nikitazvonarev@gmail.com
Критерий получения зачёта
- Пять плюсиков за все задания
- Минимум 2 из 5 сданных программ должны быть написаны на Python
Темы прошедших занятий
- 16/02/21 Введение. Классификация генераторов. RANDU (без теории).
- 23/02/21 Пропуск
- 02/03/21 Линейный конгруэнтный датчик. Гиперплоскости и волновое число. Взлом линейного конгруэнтного датчика.
- 09/03/21 Датчики Фибоначчи. Комбинированные генераторы (Wichmann-Hill…). Jump Ahead: быстрое возведение матрицы в степень, etc.
- 16/03/21 Известные батареи тестов. Birthday spacings test и другие тесты. Немного про Mersenne Twister. Идеи семейства PCG.
- 23/03/21 Введение в Python 3.
- 30/03/21 ГПСЧ в C++ (пример). Моделирование в выпуклом и невыпуклом многоугольнике. Тривиальная аналитическая геометрия, алгоритм Джарвиса и «отрезания ушей».
- 06/04/21 Моделирование случайных перестановок и подвыборок. Теория .
- 13/04/21 ГПСЧ в R. Написание своего ГПСЧ в R. Многомерное нормальное распределение. Eigendecomposition, разложение Холецкого. Равномерное распределение на сфере, в шаре, в эллипсоиде. Теория .
- 20/04/21 Ассоциативные массивы: двоичное дерево поиска и хэш-таблицы. Хэш-функции. Немного о требованиях к криптографическим хэш-функциям. Полиномиальный хэш: связь с LCG, коллизии на строках Морса-Туэ.
- 27/04/21 Приём задач
- 04/05/21 Пропуск
- 11/05/21 Приём задач
Задачи и материалы к ним
Из двух задач с одинаковым номером можно взять любую (на ваш выбор). Главное – сдать её до зачёта :).
1 a). Дан текстовый файл, содержащий последовательность, полученную линейным конгруэнтным генератором вида $X_{i+1} = A X_i + C$ $(\text{mod}\; M)$, где 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) сходится к заданной с увеличением размера выборки. Продемонстрировать проекции на различные плоскости на рисунке.
5 б) Реализовать равномерное распределение в d-мерном шаре и на сфере (несколько примеров). Продемонстрировать проекции на различные плоскости на рисунке.
По желанию можно попробовать продемонстрировать результаты с помощью пакета rgl
.
Прошлогодние темы
- 11/02/20 Введение. Мультипликативный датчик, RANDU
- 18/02/20 Линейный конгруэнтный датчик. Гиперплоскости и волновое число. Взлом линейного конгруэнтного датчика.
- 25/02/20 Датчики Фибоначчи. Комбинированные генераторы. Jump Ahead: быстрое возведение матрицы в степень, etc.
- 03/03/20 Известные батареи тестов. Birthday spacings test и другие тесты. Немного про Mersenne Twister. Идеи семейства PCG.
- 10/03/20 ГПСЧ в C++ (пример). Моделирование в выпуклом и невыпуклом многоугольнике. Тривиальная аналитическая геометрия, алгоритм Джарвиса и «отрезания ушей».
- 17/03/20 (Удалённый режим). Моделирование случайных перестановок и подвыборок. Теория .
- 24/03/20 (Удалённый режим). Приём задач/пропуск
- 31/03/20 (Удалённый режим). Многомерное нормальное распределение. Eigendecomposition, разложение Холецкого. Равномерное распределение на сфере, в шаре, в эллипсоиде. Теория .
- 10/04/20 (Удалённый режим через Skype). Хэш-функции. Ассоциативные массивы: двоичное дерево поиска и хэш-таблицы. Немного о требованиях к криптографическим хэш-функциям. Полиномиальный хэш: связь с LCG, коллизии на строках Морса-Туэ.
- 14/04/20 (Удалённый режим через Skype). ГПСЧ в R. Написание своего ГПСЧ в R.
Результаты сдачи заданий
1 | 2 | 3 | 4 | 5 | |
---|---|---|---|---|---|
1) Айнабеков Захар | +P | Wichmann-Hill | |||
2) Васильцов Арсений | LCG | ||||
3) Веселова Влада | Fibonacci, + | ||||
4) Григорьев Дмитрий | +P | +P | +P | +P | |
5) Логинов Андрей | +P | Fibonacci, * | |||
6) Положиев Роман | Wichmann-Hill | ||||
7) Попов Сергей | LCG | ||||
8) Сенов Михаил | +P | Fibonacci, + | |||
9) Дядичкин Михаил | +P | Fibonacci, XOR |
Литература (старая)
- 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 Более современная книга по вычислительной алгебре
- Василенко, О. Н. Теоретико-числовые алгоритмы в криптографии
Литература (новая)
- 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