Различия

Показаны различия между двумя версиями страницы.

Ссылка на это сравнение

Предыдущая версия справа и слева Предыдущая версия
Следующая версия
Предыдущая версия
study:spring2016:sm_sim_pract [2016/03/27 03:36]
ash
study:spring2016:sm_sim_pract [2016/05/23 16:36] (текущий)
ash
Строка 4: Строка 4:
 **Преподаватель:** Шлемов Александр Юрьевич <shlemovalex@gmail.com>                     \\ **Преподаватель:** Шлемов Александр Юрьевич <shlemovalex@gmail.com>                     \\
 ---- ----
 +
 +
  
 ===== Темы и материалы к занятиям ===== ===== Темы и материалы к занятиям =====
-//17 февраля // \\+//16 февраля // \\
   - Общая постановка задачи моделирования случайных величин   - Общая постановка задачи моделирования случайных величин
   - Физические и математические генераторы   - Физические и математические генераторы
Строка 12: Строка 14:
   - Понятие о периоде   - Понятие о периоде
   - Понятие о многомерном распределении   - Понятие о многомерном распределении
-  - Метод Монте-Карло для вычисления интегралов +  
-  - Randu +
 **Материалы:**\\ **Материалы:**\\
 Для случайного генератора "Statmod" параметры: модуль 2^32, множитель 663608941. Сам генератор можно взять на [[study:fall2014:3cpp_pract|странице курса НЭ]], но лучше реализовать самостоятельно. Для случайного генератора "Statmod" параметры: модуль 2^32, множитель 663608941. Сам генератор можно взять на [[study:fall2014:3cpp_pract|странице курса НЭ]], но лучше реализовать самостоятельно.
  
-//24 февраля // \\+//27 февраля // \\ 
 +  - Метод Монте-Карло для вычисления интегралов 
 +  - Randu
   - Линейный конгруэнтный генератор   - Линейный конгруэнтный генератор
   - Понятия о волновом числе и наименьшем числе гиперплоскойстей   - Понятия о волновом числе и наименьшем числе гиперплоскойстей
Строка 33: Строка 35:
 Для случайного генератора Кнута (из "Искусства программирования") формула: X[j] = (X[j-100] - X[j-37]) mod 2^30 Для случайного генератора Кнута (из "Искусства программирования") формула: X[j] = (X[j-100] - X[j-37]) mod 2^30
  
-//марта//+//марта//
   - Комбинированные генераторы (как из дюжины зайцев сложить одного льва) и генератор L'Ecuyer'а   - Комбинированные генераторы (как из дюжины зайцев сложить одного льва) и генератор L'Ecuyer'а
   - Распараллеливание случайных генераторов (leap-frog & jump ahead)   - Распараллеливание случайных генераторов (leap-frog & jump ahead)
Строка 39: Строка 41:
   - Случайные генераторы в R   - Случайные генераторы в R
  
-//10 марта //+//12 марта //
   - Введение в криптографию   - Введение в криптографию
   - Криптографически стойкие генераторы (Fortuna, BBS, ...)   - Криптографически стойкие генераторы (Fortuna, BBS, ...)
-  - Генерирование случайных больших простых чисел 
- 
-//17 марта //\\ 
   - Криптографически стойкие хеш-функции   - Криптографически стойкие хеш-функции
   - Парадокс дней рождений и birthday attack   - Парадокс дней рождений и birthday attack
 +
 +//15 марта//
 +  - RSA
 +  - Вероятностная проверка большого числа на простоту (тесты Ферма, Миллера-Рабина)
 +  - Генерация случайных больших простых чисел
 +  - Diffie-Hellman
   - Электронные подписи, сертификаты   - Электронные подписи, сертификаты
   - https и ssh, установление подлинности сервера и авторизация по ключу   - https и ssh, установление подлинности сервера и авторизация по ключу
-  - Алгоритм факторизации Pollard pho 
  
-//24 марта //\\+//22 марта //\\
   - Статистические тесты для генераторов и популярные батареи тестов   - Статистические тесты для генераторов и популярные батареи тестов
   - Тест на распределение бит {0, 1} и непрерывный тест дней рождений   - Тест на распределение бит {0, 1} и непрерывный тест дней рождений
   - Хи-квадрат-критерий. Обобщенный хи-квадрат-критерий и проблема оценки параметров   - Хи-квадрат-критерий. Обобщенный хи-квадрат-критерий и проблема оценки параметров
  
-//31 марта //\\+ 
 + 
 + 
 +//29 марта //\\ 
 +  - Проверка гипотез (повторение --- мать учения)
   - KS-test и критерий Лилиефорса. Построение точных критериев с помощью моделирования (Монте-Карло критическая область)   - KS-test и критерий Лилиефорса. Построение точных критериев с помощью моделирования (Монте-Карло критическая область)
  
-//апреля //\\+ 
 +** Будущие темы ** 
 +//апреля //\\
   - Моделирование одномерных случайных распределений в R   - Моделирование одномерных случайных распределений в R
   - Отбор   - Отбор
Строка 65: Строка 75:
   - Смесь   - Смесь
  
-//14 апреля //\\+//12 апреля //\\ 
 +  - Моделирование многомерного нормального распределения 
 +  - Моделирование равномерного распределения в выпуклом плоском многоугольнике 
 + 
 + 
 + 
 +//14 апреля --- 3 мая// Преподаватель на конференции 
 + 
 +//10 мая //\\
   - Subsampling, описание и постановка задачи   - Subsampling, описание и постановка задачи
   - алгоритм тасовки колоды (метод перестановок)   - алгоритм тасовки колоды (метод перестановок)
Строка 72: Строка 90:
   - однопроходный нежадный выбор для исходного набора неизвестной длины (reservoir sampling aka алгоритм Кнута)   - однопроходный нежадный выбор для исходного набора неизвестной длины (reservoir sampling aka алгоритм Кнута)
   - выбор без повторений с весами   - выбор без повторений с весами
- +  
-//21 апреля //\\ +//17 мая //\\
-  - Моделирование многомерного нормального распределения +
-  - Моделирование равномерного распределения в выпуклом плоском многоугольнике +
- +
-//28 апреля //\\+
   - Моделирование равномерного распределения на многомерной сфере, в многомерном шаре, в многомерном эллипсоиде   - Моделирование равномерного распределения на многомерной сфере, в многомерном шаре, в многомерном эллипсоиде
   - Моделирование Винеровского процесса, условные распределения Винеровского процесса   - Моделирование Винеровского процесса, условные распределения Винеровского процесса
- 
-//5 мая //\\ 
   - Функции и замыкания в R   - Функции и замыкания в R
-  - Самостоятельная работа+  - Алгоритм факторизации Pollard pho 
 +  - Схема разделения секрета Шамира 
  
  
Строка 104: Строка 118:
 ** (4) Моделирование равномерного распределения в многоугольнике ** Реализовать функцию, моделирующую равномерное распределение в невырожденном выпуклом многоугольнике. Многоугольник задается вершинами в порядке обхода против часовой стрелки. Функция должна быть векторизована, т.е. возвращать матрицу из двух столбцов --- координат. //Опционально// 1. Вершины заданы в произвольном порядке 2. Вершины заданы в порядке обхода, но не гарантируется, что многоугольник выпуклый. ** (4) Моделирование равномерного распределения в многоугольнике ** Реализовать функцию, моделирующую равномерное распределение в невырожденном выпуклом многоугольнике. Многоугольник задается вершинами в порядке обхода против часовой стрелки. Функция должна быть векторизована, т.е. возвращать матрицу из двух столбцов --- координат. //Опционально// 1. Вершины заданы в произвольном порядке 2. Вершины заданы в порядке обхода, но не гарантируется, что многоугольник выпуклый.
  
-** (5) Моделирование Винеровского процесса ** Реализовать функцию, которая будет возвращать реализацию винеровского процесса в следующем смысле: будет генерироваться некий функциональный объект, при вызове которого с аргументом координаты точки будет возвращаться значение процесса в данной точке. При этом объект должен уметь сохранять уже сгенерированные значения и каждый раз возвращать значения с учетом уже сгенерированных (т.е. внутри должно моделироваться условное распределение). Конкретно как такое реализовать в R, мы поговорим на следующем занятии, пока стоит просто реализовать и проверить формулы условного распределения. //Опционально// Реализовать данную схему на Python или C<html>++</html>, используя эффективную структуру для хранения уже сгенерированных значений (таким образом, чтобы трудоемкость генерации новой величины была порядка logN) +** (5) Моделивание сужений, смесей и метод отбора ** Реализовать на R метод отбора и моделирование смеси наивным образом и 
 +"каноническим" (как было показано в классе). Сравнить по скорости. В качестве примера можно взять любую задачу из курса моделирования распределений (например, моделирование распределения с плотностью C(exp(-x) + exp(x)) на отрезке [0, 1]). 
 + 
 + 
 +** (5') Моделирование Винеровского процесса ** Реализовать функцию, которая будет возвращать реализацию винеровского процесса в следующем смысле: будет генерироваться некий функциональный объект, при вызове которого с аргументом координаты точки будет возвращаться значение процесса в данной точке. При этом объект должен уметь сохранять уже сгенерированные значения и каждый раз возвращать значения с учетом уже сгенерированных (т.е. внутри должно моделироваться условное распределение). Конкретно как такое реализовать в R, мы поговорим на следующем занятии, пока стоит просто реализовать и проверить формулы условного распределения. //Опционально// Реализовать данную схему на Python или C<html>++</html>, используя эффективную структуру для хранения уже сгенерированных значений (таким образом, чтобы трудоемкость генерации новой величины была порядка logN)  
 + 
 + 
 + 
 + 
 + 
 + 
 + 
  
  
Строка 143: Строка 169:
  
 ^                    ^ 1 ^ 2 ^ 3 ^ 4 ^ 5 | ^                    ^ 1 ^ 2 ^ 3 ^ 4 ^ 5 |
-^ Суровикина Тамара   | + |     +^ Суровикина Тамара   | + | 
-^ Зотиков Дмитрий           +^ Зотиков Дмитрий           
-^ Сазыкин Дмитрий           +^ Сазыкин Дмитрий     
-^ Федорченко Сергей         +^ Федорченко Сергей         
-^ Арцыман Илья        |       |+^ Арцыман Илья        | |
  
  
study/spring2016/sm_sim_pract.1459038984.txt.gz · Последнее изменение: 2016/03/27 03:36 — ash
Наверх
CC Attribution-Noncommercial-Share Alike 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0