Это старая версия документа!
Содержание
322 гр., спец. СМ. Вычислительный практикум (моделирование распределений)
Место и время проведения: вторник, первая пара, ауд. 2408
Преподаватель: Звонарев Никита nikitazvonarev@gmail.com
Темы прошедших занятий
- 13/02/18 Введение. Мультипликативный датчик (начало), RANDU
- 20/02/18 Линейный конгруэнтный датчик. Гиперплоскости и волновое число. Датчики Фибоначчи.
- 27/02/18 Комбинированные генераторы. Jump Ahead: быстрое возведение матрицы в степень, etc.
- 06/03/18 Известные батареи тестов. Birthday spacings test и другие тесты. Немного про Mersenne Twister. Идеи семейства PCG.
- 13/03/18 Моделирование в выпуклом и невыпуклом многоугольнике. Тривиальная аналитическая геометрия, алгоритмы Джарвиса, Грэхэма, «отрезания ушей».
- 20/03/18 ГПСЧ в Cpp. Моделирование случайных перестановок и подвыборок.
- 27/03/18 ГПСЧ в R. Многомерное нормальное распределение. Eigendecomposition, разложение Холецкого. Равномерное распределение на сфере, в шаре, в эллипсоиде.
- 03/04/18 сдача заданий
- 10/04/18 Введение в Python 3 и сдача заданий
- 17/04/18 Продолжение Python 3 и сдача заданий
- 24/04/18 сдача заданий
- 01/05/18 День труда (выходной)
- 08/05/18 сдача заданий
- 15/05/18 сдача заданий
- 22/05/18 зачёт неофициальный
Задачки и материалы к ним
Из двух задач с одинаковым номером можно взять любую (на ваш выбор). Главное – сдать её до зачёта :).
1 а). Трёхмерные интегралы и RANDU. Взять плохой датчик и продемонстрировать, что М-К для одно- или двумерного интеграла работает, а для трёхмерного ломается. Достаточно выбрать подходящую (объяснял на паре) ограниченную функцию на [0, 1]^k, у которой вы можете взять интеграл аналитически.
1 б). Дан текстовый файл, содержащий последовательность, полученную линейным конгруэнтным генератором вида X_{i+1} = A X_i + C (mod M), где M – простое. Требуется восстановить все параметры генератора. Утверждается, что всё можно спокойно посчитать в int64.
2 a). Реализовать процедуру jump-ahead для датчика, выданного на паре. а) продемонстрировать, что 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) Реализовать моделирование случайной перестановки с помощью одного из упомянутого на паре метода на Cpp
. Промоделировать перестановку много (~10^5-~10^7) раз, проверить распределение перестановок с помощью распределения позиции i-го элемента и числа циклов длины k для малых и больших длин перестановок (пользуясь соотношениями, упомянутыми на паре, и критерием Хи-квадрат).
Замечание: проверку распределения проще сделать в R
, сгенерировав готовый файл со статистиками.
5 а) Реализовать моделирование многомерного нормального распределения с невырожденной и вырожденной (несколько примеров) ковариационной матрицей, без использования готовой функций (для моделирования в R разрешён только rnorm()
). Продемонстрировать проекции на различные плоскости на рисунке.
5 б) Реализовать равномерное распределение в d-мерном шаре и на сфере (несколько примеров). Продемонстрировать проекции на различные плоскости на рисунке.
По желанию можно попробовать продемонстрировать результаты с помощью пакета rgl
.
Прошлогодние темы
- 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.
- 28/03/17 Пример на Cpp ссинглтоном (ещё вариант). Многомерное нормальное распределение. 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 | 2 | 3 | 4 | 5 | |
---|---|---|---|---|---|
1) Заляев Тимур | + | + | + | ||
2) Константинов Антон | + | + | + | + | + |
3) Соколиков Евгений | + | + | + | + | + |
4) Сандалов Сергей | + | + | + | + | + |
5) Карасов Николай | + | + | + | + | + |
6) Барсуков Егор | + | + | + | + | + |
7) Вирко Елизавета | + | + | + | + | + |
Литература (старая)
- 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