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


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

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


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

16 февраля

  1. Общая постановка задачи моделирования случайных величин
  2. Физические и математические генераторы
  3. Мультипликативный случайный генератор (генератор Лемера)
  4. Понятие о периоде
  5. Понятие о многомерном распределении

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

27 февраля

  1. Метод Монте-Карло для вычисления интегралов
  2. Randu
  3. Линейный конгруэнтный генератор
  4. Понятия о волновом числе и наименьшем числе гиперплоскойстей
  5. Математическое обоснование для генераторов типа фибоначчи, попарная независимость и одинаковая распределенность {xi + \eta}, xi, eta при xi, eta ~ U[0, 1]
  6. Решение проблемы многомерных распределений — генераторы фибоначчиевого типа
  7. Немного о битовых генераторах Таусворта
  8. Свойства и проблемы фибоначчиевых генераторов
  9. Возможные операции для датчиков фибоначчиевого типа (+, -, *, XOR, …)
  10. Почему «сложное хуже простого, новое хуже старого»
  11. Инициализация случайными значениями в C++ и Python
  12. Свойства распределения отдельных бит в случайных генераторах

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

1 марта

  1. Комбинированные генераторы (как из дюжины зайцев сложить одного льва) и генератор L'Ecuyer'а
  2. Распараллеливание случайных генераторов (leap-frog & jump ahead)
  3. State of the art: Mersenne twister
  4. Случайные генераторы в R

12 марта

  1. Введение в криптографию
  2. Криптографически стойкие генераторы (Fortuna, BBS, …)
  3. Криптографически стойкие хеш-функции
  4. Парадокс дней рождений и birthday attack

15 марта

  1. RSA
  2. Вероятностная проверка большого числа на простоту (тесты Ферма, Миллера-Рабина)
  3. Генерация случайных больших простых чисел
  4. Diffie-Hellman
  5. Электронные подписи, сертификаты
  6. https и ssh, установление подлинности сервера и авторизация по ключу

22 марта

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

Будущие темы

29 марта

  1. Проверка гипотез (повторение — мать учения)
  2. KS-test и критерий Лилиефорса. Построение точных критериев с помощью моделирования (Монте-Карло критическая область)

5 апреля

  1. Моделирование одномерных случайных распределений в R
  2. Отбор
  3. Сужение
  4. Смесь

12 апреля

  1. Моделирование многомерного нормального распределения
  2. Моделирование равномерного распределения в выпуклом плоском многоугольнике

14 апреля — 3 мая Преподаватель на конференции

10 мая

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

17 мая

  1. Моделирование равномерного распределения на многомерной сфере, в многомерном шаре, в многомерном эллипсоиде
  2. Моделирование Винеровского процесса, условные распределения Винеровского процесса
  3. Функции и замыкания в R
  4. Алгоритм факторизации Pollard pho
  5. Схема разделения секрета Шамира

Задачи

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

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

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

(3') Случайный генератор 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 назад. Пятая — найти период последовательности. Шестая — найти наименьший период последовательности. Задача подразумевает желание немного вспомнить алгебру

(4) Моделирование равномерного распределения в многоугольнике Реализовать функцию, моделирующую равномерное распределение в невырожденном выпуклом многоугольнике. Многоугольник задается вершинами в порядке обхода против часовой стрелки. Функция должна быть векторизована, т.е. возвращать матрицу из двух столбцов — координат. Опционально 1. Вершины заданы в произвольном порядке 2. Вершины заданы в порядке обхода, но не гарантируется, что многоугольник выпуклый.

(5) Моделирование Винеровского процесса Реализовать функцию, которая будет возвращать реализацию винеровского процесса в следующем смысле: будет генерироваться некий функциональный объект, при вызове которого с аргументом координаты точки будет возвращаться значение процесса в данной точке. При этом объект должен уметь сохранять уже сгенерированные значения и каждый раз возвращать значения с учетом уже сгенерированных (т.е. внутри должно моделироваться условное распределение). Конкретно как такое реализовать в R, мы поговорим на следующем занятии, пока стоит просто реализовать и проверить формулы условного распределения. Опционально Реализовать данную схему на Python или C++, используя эффективную структуру для хранения уже сгенерированных значений (таким образом, чтобы трудоемкость генерации новой величины была порядка logN)

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

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 Параллельное программирование на R
  5. Akritas A.G. Elements of Computer Algebra With Applications Об алгоритмах компьютерной алгебры (проверка на простоту, разложение на множители, характериситческие многочлены и прочее). Сама книга достаточно редкая, но ее русский перевод (Основы компьютерной алгебры с приложениями, 1994) найти очень легко.
  6. Shoup V. A Computational Introduction to Number Theory and Algebra Более современная книга по вычислительной алгебре
study/spring2016/sm_sim_pract.1459708351.txt.gz · Последнее изменение: 2016/04/03 21:32 — ash
Наверх
CC Attribution-Noncommercial-Share Alike 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0