Это старая версия документа!


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

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

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

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

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

FIXME

  1. 16/02/21 Введение. Классификация генераторов. RANDU (без теории).
  2. 23/02/21 Пропуск
  3. 02/03/21 Линейный конгруэнтный датчик. Гиперплоскости и волновое число. Взлом линейного конгруэнтного датчика.
  4. 09/03/21 Датчики Фибоначчи. Комбинированные генераторы (Wichmann-Hill…). Jump Ahead: быстрое возведение матрицы в степень, etc.
  5. 16/03/21 Известные батареи тестов. Birthday spacings test и другие тесты. Немного про Mersenne Twister. Идеи семейства PCG.
  6. 23/03/21 Введение в Python 3.
  7. 30/03/21 ГПСЧ в C++ (пример). Моделирование в выпуклом и невыпуклом многоугольнике. Тривиальная аналитическая геометрия, алгоритм Джарвиса и «отрезания ушей».
  8. 06/04/21 Моделирование случайных перестановок и подвыборок. Теория .
  9. 13/04/21 ГПСЧ в R. Написание своего ГПСЧ в R. Многомерное нормальное распределение. Eigendecomposition, разложение Холецкого. Равномерное распределение на сфере, в шаре, в эллипсоиде. Теория .
  10. 20/04/21 Ассоциативные массивы: двоичное дерево поиска и хэш-таблицы. Хэш-функции. Немного о требованиях к криптографическим хэш-функциям. Полиномиальный хэш: связь с LCG, коллизии на строках Морса-Туэ.
  11. 27/04/21 Приём задач
  12. 04/05/21 Пропуск
  13. 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.

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

  1. 11/02/20 Введение. Мультипликативный датчик, RANDU
  2. 18/02/20 Линейный конгруэнтный датчик. Гиперплоскости и волновое число. Взлом линейного конгруэнтного датчика.
  3. 25/02/20 Датчики Фибоначчи. Комбинированные генераторы. Jump Ahead: быстрое возведение матрицы в степень, etc.
  4. 03/03/20 Известные батареи тестов. Birthday spacings test и другие тесты. Немного про Mersenne Twister. Идеи семейства PCG.
  5. 10/03/20 ГПСЧ в C++ (пример). Моделирование в выпуклом и невыпуклом многоугольнике. Тривиальная аналитическая геометрия, алгоритм Джарвиса и «отрезания ушей».
  6. 17/03/20 (Удалённый режим). Моделирование случайных перестановок и подвыборок. Теория .
  7. 24/03/20 (Удалённый режим). Приём задач/пропуск
  8. 31/03/20 (Удалённый режим). Многомерное нормальное распределение. Eigendecomposition, разложение Холецкого. Равномерное распределение на сфере, в шаре, в эллипсоиде. Теория .
  9. 10/04/20 (Удалённый режим через Skype). Хэш-функции. Ассоциативные массивы: двоичное дерево поиска и хэш-таблицы. Немного о требованиях к криптографическим хэш-функциям. Полиномиальный хэш: связь с LCG, коллизии на строках Морса-Туэ.
  10. 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

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

  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 Более современная книга по вычислительной алгебре

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

  1. Richard Arratia and Simon Tavare. The Cycle Structure of Random Permutations The Annals of Probability. Vol. 20, No. 3 (Jul., 1992), pp. 1567-1591
  2. На ту же тему. Статья в блоге Теренса Тао The number of cycles in a random permutation
study/spring2021/sm_sim_pract.1620654169.txt.gz · Последнее изменение: 2021/05/10 16:42 — nikita
Наверх
CC Attribution-Noncommercial-Share Alike 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0