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


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

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

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

  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 (Удалённый режим). Моделирование случайных перестановок и подвыборок. Теория .
TODO

– ГПСЧ в R.

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

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

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

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

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, вершины в порядке обхода против часовой стрелки. Помните, что между последней и первой вершиной есть отрезок), и продемонстрировать ваше решение на нём.

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

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

TODO

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

  1. 12/02/19 Введение. Мультипликативный датчик, RANDU
  2. 19/02/19 Линейный конгруэнтный датчик. Гиперплоскости и волновое число. Взлом линейного конгруэнтного датчика.
  3. 26/02/19 Датчики Фибоначчи. Комбинированные генераторы. Jump Ahead: быстрое возведение матрицы в степень, etc.
  4. 05/03/19 Известные батареи тестов. Birthday spacings test и другие тесты. Немного про Mersenne Twister. Идеи семейства PCG.
  5. 12/03/19 ГПСЧ в C++ (пример). Моделирование в выпуклом и невыпуклом многоугольнике. Тривиальная аналитическая геометрия, алгоритмы Джарвиса, Грэхэма, «отрезания ушей».
  6. 19/03/19 ГПСЧ в R. Моделирование случайных перестановок и подвыборок.
  7. 26/03/19 Многомерное нормальное распределение. Eigendecomposition, разложение Холецкого. Равномерное распределение на сфере, в шаре, в эллипсоиде.
  8. 02/04/19 Приём задач
  9. 09/04/19 Введение в динамическое программирование (основы, динамика на подотрезках/подмножествах, расстояние Левенштейна и пр.).
  10. 16/04/19 Введение в алгоритмы на графах (способы хранения, DFS/BFS, поиск наикратчайшего пути в 0-1, Дейкстра с кучей/без кучи).
  11. 23/04/19 Пропуск
  12. 30/04/19 Приём задач
  13. 07/05/19 Приём задач
  14. 14/05/19 Приём задач
  15. 21/05/19 Приём задач
  16. 11/06/19 Зачёт

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

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

1 2 3 4 5
1) Шаповал Егор + Wichmann-Hill
2) Чемокос Олег Фибоначчи, *
3) Белкова Анна Линейный конгруэнтный
4) Бощенко Алина Фибоначчи, +
5) Попов Владимир + Фибоначчи, XOR
6) Конищева Злата Фибоначчи, +
7) Лобанова Полина Wichmann-Hill
8) Шешуков Илья + Фибоначчи, XOR
9) Глушков Игорь Линейный конгруэнтный
10) Сурушкин Иван Фибоначчи, *

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

  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/spring2020/sm_sim_pract.1584976306.txt.gz · Последнее изменение: 2020/03/23 18:11 — nikita
Наверх
CC Attribution-Noncommercial-Share Alike 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0