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

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

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

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

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

2 a). Реализовать процедуру jump-ahead для одного из следующих типов: студенты 1, 4 и 7 – линейный конгуэнтный, Wichman-Hill, L'Ecuyer; 2, 5, 8 – фибоначчиевый тип по сложению или вычитанию; 3, 6, 9 – фибоначчиевый тип по умножению или XOR. Номера см. в табличке снизу. Можно взять вариант потруднее, если хотите. Необходимо сгенерировать какую-нибудь последовательность и а) продемонстрировать, что 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 а) Реализовать многомерное нормальное распределение с невырожденной и вырожденной (несколько примеров) ковариационной матрицей, без использования готовой функций (для моделирования в R разрешён только rnorm()). Продемонстрировать проекции на различные плоскости на рисунке.

4 б) Реализовать равномерное распределение в d-мерном шаре и на сфере (несколько примеров). Продемонстрировать проекции на различные плоскости на рисунке. По желанию можно попробовать пакет rgl.

5 а) Реализовать метод отбора на R, «наивным» и быстрым способом. Сравнить по скорости. Проверить корректность с помощью критерия Колмогорова-Смирнова. В качестве плотности распределения можно взять любую, например, C (exp(x)+exp(-x)) на [-1;1].

Замечание: реализацию «наивным» способом можно не писать, если ваша плотность распределения лежит в (-∞;+∞) или [0; +∞).

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

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

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

1 2 3 4 5
1) Быков Кирилл + + + + +
2) Лунев Иван + + + + +
3) Федоров Никита + + + + +
4) Страшко Владислав + + + + +
5) Третьякова Александра + + + + +
6) Романова Елизавета + + + + +
7) Зенкова Наталья + + + +
8) Понизова Вероника + + + +
9) Мийоски Антоний + + + + +

Литература (прошлогодняя)

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