2024/2025
Программирование генераторов случайных величин
Статус:
Общеуниверситетский факультатив
Кто читает:
Департамент математики
Когда читается:
1, 2 модуль
Охват аудитории:
для всех
Преподаватели:
Ломоносов Тимофей Александрович
Язык:
русский
Кредиты:
4
Контактные часы:
72
Программа дисциплины
Аннотация
Предполагается, что слушатели знакомы с основными понятиями теории вероятностей, читаемой на бакалавриате различных факультетов НИУ ВШЭ и владеют программированием на уровне Data Culture 2 (базовый уровень). Генераторы случайных величин имеют приложения в статистическом семплировании, т. е. управлении начальной выборкой при известной цели моделирования, компьютерной симуляции, криптографии, гейм-дизайне и других областях, в которых желательно произвести недетерминированный результат. Стандартные библиотеки большинства языков программирования предлагают генератор случайных величин, распределённых равномерно на отрезке [0,1], однако часто возникает необходимость генерации случайных величин, подчиняющихся иным законам распределения. На этом курсе студенты изучат основные методы генерации случайных величин и научатся реализовывать процедуры генерации случайных величин, распределённых по разным законам распределения.
Цель освоения дисциплины
- Разрабатывать алгоритмы генерации случайных величин
- Оценивать вычислительную сложность алгоритмов генерации случайных величин
- Реализовывать генерацию случайных величин наиболее эффективным в плане времени вычислений способом
Планируемые результаты обучения
- Анализировать сложность алгоритмов генерации случайных величин
- Получать эффективные алгоритмы различных видов
- Раскладывать некоторые распределения на более простые компоненты для последующей реализации
- Использовать взаимосвязь между различными распределениями для эффективной генерации случайных величин
- Получать строгие неравенства на функции плотностей распределения
Содержание учебной дисциплины
- Тема 1. Введение. Основные обозначения. Оценка генераторов случайных чисел.
- Тема 2. Основные принципы генерации случайных чисел.
- Тема 3. Метод отбрасывания. Разработка хороших алгоритмов отбрасывания.
- Тема 4. Принцип сжатия.
- Тема 5. Разложение на простые компоненты как дискретные смеси.
- Тема 6. Генерация дискретных случайных величин.
- Тема 7. Равномерные и экспоненциальные спейсинги
- Тема 8. Полярный метод. Радиально симметричные распределения.
- Тема 9. Генерация процесса Пуассона.
- Тема 10. Табличные методы для непрерывных случайных величин.
- Тема 11. Генерация случайных выборок.
- Тема 12. Стандартная последовательная генерация выборок.
- Тема 13. Избыточные выборки. Резервуарная выборка.
- Тема 14. Общие принципы генерации случайных комбинаторных объектов.
- Тема 15. Простые генераторы случайных перестановок.
- Тема 16. Генерация случайных бинарных деревьев методом последовательной выборки.
- Тема 17. Случайные разбиения. Случайные свободные деревья.
- Тема 18. Вероятностные методы уменьшения ожидаемого времени симуляции.
Промежуточная аттестация
- 2024/2025 2nd module0.334 * Лабораторная работа + 0.167 * Тесты по материалам лекций + 0.499 * Экзамен
Список литературы
Рекомендуемая основная литература
- Fabrizio Romano. (2018). Learn Python Programming : The No-nonsense, Beginner’s Guide to Programming, Data Science, and Web Development with Python 3.7, 2nd Edition: Vol. 2nd ed. Packt Publishing.
- Алгоритмы и структуры данных, Вирт, Н., 2001
- Введение в математическую статистику, Ивченко, Г. И., 2010
- Теория вероятностей : учебник для вузов, Вентцель, Е. С., 2002
Рекомендуемая дополнительная литература
- Jaworski, M., & Ziadé, T. (2019). Expert Python Programming, : Become a Master in Python by Learning Coding Best Practices and Advanced Programming Concepts in Python 3.7, 3rd Edition (Vol. 3rd ed). Birmingham: Packt Publishing. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=2116999
- Python 3, Прохоренок, Н. А., 2016
- Изучаем программирование на Python, Бэрри, П., 2017
- Наглядная математическая статистика : учеб. пособие для вузов, Лагутин, М. Б., 2012