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

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

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

  1. 13/02/18 Введение. Мультипликативный датчик (начало), RANDU
  2. 20/02/18 Линейный конгруэнтный датчик. Гиперплоскости и волновое число. Датчики Фибоначчи.
  3. 27/02/18 Комбинированные генераторы. Jump Ahead: быстрое возведение матрицы в степень, etc.
  4. 06/03/18 Известные батареи тестов. Birthday spacings test и другие тесты. Немного про Mersenne Twister. Идеи семейства PCG.
  5. 13/03/18 Моделирование в выпуклом и невыпуклом многоугольнике. Тривиальная аналитическая геометрия, алгоритмы Джарвиса, Грэхэма, «отрезания ушей».
  6. 20/03/18 ГПСЧ в Cpp. Моделирование случайных перестановок и подвыборок.
  7. 27/03/18 ГПСЧ в R. Многомерное нормальное распределение. Eigendecomposition, разложение Холецкого. Равномерное распределение на сфере, в шаре, в эллипсоиде.
  8. 03/04/18 сдача заданий
  9. 10/04/18 Введение в Python 3 и сдача заданий
  10. 17/04/18 Продолжение Python 3 и сдача заданий
  11. 24/04/18 сдача заданий
  12. 01/05/18 День труда (выходной)
  13. 08/05/18 сдача заданий
  14. 15/05/18 сдача заданий
  15. 22/05/18 зачёт неофициальный

FIXME

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

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

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.

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

  1. 14/02/17 Введение. Мультипликативный датчик (начало)
  2. 21/02/17 RANDU. Линейный конгруэнтный датчик. Гиперплоскости и волновое число. Датчики Фибоначчи.
  3. 28/02/17 Комбинированные генераторы. Mersenne Twister.
  4. 07/03/17 Jump-ahead и leap-frog. Возведение матрицы в степень. ГПСЧ в Cpp и в R.
  5. 14/03/17 Моделирование в выпуклом и невыпуклом многоугольнике. Тривиальная аналитическая геометрия, алгоритмы Джарвиса, Грэхэма, отрезания ушей.
  6. 21/03/17 Немного про критерий Колмогорова, Хи-квадрат, проверку гипотез, как применяется для тестирования генераторов. Birthday spacings test. Известные батареи тестов. Идеи семейства PCG.
  7. 28/03/17 Пример на Cpp ссинглтоном (ещё вариант). Многомерное нормальное распределение. EVD, SVD. Равномерное распределение на сфере, в шаре.
  8. 04/04/17 Метод отбора, векторизованная реализация на R.
  9. 11/04/17 Моделирование смеси, векторизованная реализация на R. Моделирование случайных перестановок и подвыборок.
  10. 18/04/17 Python 3: введение
  11. 25/04/17 сдача заданий
  12. 02/05/17 Ещё немного про Python + сдача
  13. 09/05/17 День Победы (выходной)
  14. 16/05/17 Сдача
  15. 24/05/17 Зачёт

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

1 2 3 4 5
1) Заляев Тимур + + + + +
2) Константинов Антон + + + + +
3) Соколиков Евгений + + + + +
4) Сандалов Сергей + + + + +
5) Карасов Николай + + + + +
6) Барсуков Егор + + + + +
7) Вирко Елизавета + + + + +

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

  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/spring2018/sm_sim_pract.txt · Последние изменения: 2018/05/22 14:31 — nikita
Наверх
CC Attribution-Noncommercial-Share Alike 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0