Перейти к содержанию

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

Место и время проведения: вторник 1 пара, 2444-1
Преподаватель: Шлемов Александр Юрьевич shlemovalex@gmail.com

Темы и материалы к занятиям

11 февраля
- Общая постановка задачи моделирования случайных величин

  1. Физические и математические генераторы
  2. Мультипликативный и линейный конгруэнтный генератор
  3. Понятие о периоде
  4. Понятие о многомерном распределении
  5. Randu

Материалы:
Для случайного генератора “Statmod” параметры: модуль 2^32, множитель 663608941. Сам генератор можно взять на странице курса НЭ, но лучше реализовать самостоятельно.

18 февраля
- Понятия о волновом числе и наименьшем числе гиперплоскойстей

  1. Математическое обоснование для генераторов типа фибоначчи, попарная независимость и одинаковая распределенность {xi + \eta}, xi, eta при xi, eta ~ U[0, 1]
  2. Решение проблемы многомерных распределений — генераторы фибоначчиевого типа
  3. Немного о битовых генераторах Таусворта
  4. Свойства и проблемы фибоначчиевых генераторов
  5. Возможные операции для датчиков фибоначчиевого типа (+, -, *, XOR, …)
  6. Почему не надо использовать вещественную арифметику в генераторах и почему “сложное хуже простого, новое хуже старого”
  7. Инициализация случайными значениями в C++ и Python
  8. Свойства распределения отдельных бит в случайных генераторах
  9. генераторы “with carry” (с переносом разрядов) и генераторы по модулю простого числа Мерсена (типа 2^31-1) как решение проблемы. Начало

Материалы
Для случайного генератора Кнута (из “Искусства программирования”) формула: X[j] = (X[j-100] - X[j-37]) mod 2^30

25 февраля

  1. Продолжение рассказа про генераторы с переносом и генераторы по модулю простого числа
  2. Распараллеливание случайных генераторов (leap-frog & jump ahead)
  3. “Прогрев” генератора
  4. Комбинированные генераторы (как из дюжины зайцев сложить одного льва) и генератор L’Ecuyer’а

//4 марта //

  1. State of the art: Mersenne twister
  2. Случайные генераторы и моделирование распределений в R
  3. Работа в классе с R

11 марта

  1. Статистические тесты для генераторов и популярные батареи тестов
  2. Тест на распределение бит {0, 1} и непрерывный тест дней рождений
  3. Хи-квадрат-критерий. Обобщенный хи-квадрат-критерий и проблема оценки параметров

18 марта

  1. K-S-test и критерий Лилиефорса. Построение точных критериев с помощью моделирования (Монте-Карло критическая область)
  2. Таймирование в R
  3. Работа в классе с R

// 25 марта//

  1. Введение в криптографию
  2. Криптографически стойкие генераторы (Fortuna, BBS, …)
  3. Генерирование случайных больших простых чисел

// 1 апреля//

  1. Subsampling, описание и постановка задачи
  2. алгоритм тасовки колоды (метод перестановок)
  3. простой выбор с отклонением (classical subsampling)
  4. последовательный однопроходный жадный выбор (sequential subsampling)
  5. однопроходный нежадный выбор для исходного набора неизвестной длины (reservoir sampling aka алгоритм Кнута)

// 8 апреля//

  1. Метод отбора в R. Наивная и векторизованная реализация
  2. Моделирование сужений распределений с помощью обратных функций
  3. Моделирование смесей распределений в R. Наивная и векторизованная реализации

// 15 апреля//

  1. Возможные узкие места производительности (процессор, память, внешние устройства)
  2. Понятие о кешировании и концепция “многоуровневой памяти”. Файл подкачки и дисковый кеш
  3. О способах ускорения моделирования и программ вообще (использавание SSD, баз данных, буферизация, оптимизатор)
  4. Особенности производительности в R (медленный интерпретатор и частые переаллокации)
  5. Профилирование (на примере R). Функция “Rprof()” и пакет “profr”
  6. Компиляция и JIT-компиляция в R

// 22 апреля//

  1. Параллелизм с разделенной памятью (на примере R). Пакет “parallel”.
  2. Кластер, загрузка данных на ноды, выполнение команд (makeCluster, clusterExport, clusterCall, clusterEvalQ)
  3. parXapply-функции (parApply, parLapply, parSapply, …, parLapplyLB, parSapplyLB)
  4. Параллельное моделирование и параллельный ГСЧ
  5. Решение задач по моделированию распределений из курса ВВ

Анонс

  1. Решение задач по моделированию
  2. Моделирование многомерных распределений
  3. Еще идеи генераторов (inverse, …)
  4. Практика: Какие генераторы реально доступны и используются в популярных средах и языках и как ими воспользоваться
  5. Разные методы моделирования и их особенности
  6. Вычисление интегралов методом Монте-Карло
  7. Решение систем ЛУ методом Монте-Карло
  8. Моделирование марковских цепочек
  9. Моделирование сложных систем и оценка свойств (вероятно, на примере моделирования рынка акций, дорожного движения, etc)

Задачи

** (1) Многомерное интегрирование ** Известная проблема многих ГСЧ — плохие свойства многомерных распределений. Предлагается взять мультипликативный генератор по модулю 2^32 с множителем 3 (ну очень плохой генератор) и продемонстрировать, что при интегрировании одномерных функций нет никаких проблем, а при интегрировании уже двумерных проблемы имеются (можно посчитать число Пи двумя способоми: один раз как интерал под дугой окружности, другой как площадь квадрата, вписанного в круг; во втором случае, фактически, интегрируется индикаторная функция круга). Расширенный вариант задачи: взять генератор IBM360 (aka RANDU) и продемонстрировать проблемы с многомерным распределением на его примере. Для этого достаточно рассмотреть трехмерный интеграл (в принципе, любой)

** (2) Jump-ahead ** С широким распространением многопоточных вычислителей распараллеливание случайных датчиков стало актуальной задачей. Одним из часто искользуемых способов распараллеливания является следующий: в качестве псевдослучайной последовательности в первом потоке используется исходная, а во втором и последующих — исходная, сдвинутая на большое количество шагов вперед. Сдвиги выбираются так, чтобы участки последовательностей не пересеклись за максимально возможное время моделирования. Нам нужно уметь сдвигать состояние последовательности на большое число шагов вперед много быстрее, чем прокручиванием датчика вхолостую. Эта процедура называется jump-ahead. Предлагается реализовать ее для любого датчика на ваш выбор. Датчики в порядке возрастания сложности: мультипликативный (для ленивых), Wichman-Hill, линейный конгруэнтный, L’Ecuyer, фибоначчи по сложению или вычитанию (например, Knuth TAOCP), фибоначчи по XOR, фибоначчи по умножению

** (3) Тест дней рождений ** Мало иметь ГСЧ, надо еще уметь проверить его качество. Одним из актуальных подходов является статистическое тестирование — датчик используется для моделирования некоторой системы с известными статистическими свойствами, затем эти свойства проверяются как статистические гипотезы. Известно, что последовательные разности упорядоченных равномерно распределенных случайных величин распределены экспоненциально с неизвестным параметром. Предлагается проверить, верно ли это для актуальных датчиков из пакета R. Следует воспользоваться обобщенным критерием хи-квадрат, разбивать выборку на гистрограмму по квантилям. Расширенный вариант задачи: воспользоваться критерием К-С, предварительно построив с помощью моделирования критические области для статистики критерия для случая экспоненциального распределения с неизвестным параметром.

** (4) Большое простое число ** С помощью вероятностного теста Ферма сгенерировать простое число не короче, чем 300 десятичных знаков, начинающееся с цифр 31415. Для длинной арифметики в R следует использовать пакет “gmp” (под Linux требует установки libgmp-dev), в C/C++ — библиотеку “gmp”, в Python длинная арифметика встроена. Случаные числа в R моделируются встроенными методами, в C++ — модуль , в Python — модуль random.

** (5) Моделивание сужений, смесей и метод отбора ** Реализовать на R метод отбора и моделирование смеси наивным образом и “каноническим” (как было показано в классе). Сравнить по скорости. В качестве примера можно взять любую задачу из курса моделирования распределений (например, моделирование распределения с плотностью C(exp(-x) + exp(x)) на отрезке [0, 1]).

Личный состав

1 2 3 4 5
Абрамова Ася + + + + +
Бзикадзе Андрей + + + + +
Ельник Сергей + + + + +
Иванова Лиза + ? + + +
Иванова Полина + + + + +
Черный Артем + + + + +
Корчемкин Дмитрий + + + + +

Литература (и другие источники)

  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