Асимптотический анализ и теория вероятностей
Санкт-Петербург, осень 2018
Описание
В курсе будут разобраны такие темы, как: теория множеств, асимптотики, производящие функции, дискретная и условная вероятность, случайные величины, предельные теоремы.
Сдача курса
Каждое д/з 20 баллов, за все д/з можно набрать 80 баллов. Контрольная стоит 50 баллов. Итого вместе с д/з можно набрать 130 баллов.
- Набравшие 110 баллов получают оценку 5.
- Набравшие 98 баллов получают оценку 4.
- Набравшие 85 баллов получает оценку 3.
Необходимые знания для понимания курса
Комбинаторика
Необходимо знание комбинаторики примерно в объеме первой лекции курса «Основы дискретной математики».
Начиная со 2-й лекции нужно: знакомство с факториалами и биномиальными коэффициентами (число перестановок, число сочетаний), основные комбинаторные величины и простейшие комбинаторные формулы.
Для понимания некоторых примеров применения теории вероятностей в комбинаторике (8-я лекция и далее) нужно знакомство с базовыми определениями теории графов. Достаточно первой лекции по графам из курса «Основы дискретной математики».
Математический анализ
Необходимо знание математического анализа в объеме первого курса технического ВУЗа.
Умение вычислять простые пределы (2-я лекция и далее). Знакомство с определенными интегралами и их связью с площадями (3-я лекция и далее). Начиная с 4-й лекции нужно умение дифференцировать и интегрировать. Достаточно уметь интегрировать рациональные функции (точнее нужно уметь раскладывать их на простейшие, что требуется при интегрировании рациональных функций), а также некоторые достаточно простые функции. Знакомство с формулами Тейлора для элементарных функций. Знакомство с формулой интегрирования по частям. Определение ряда, суммы ряда и сходимости ряда. В нескольких примерах в курсе (6-я лекция) возникают простые дифференциальные уравнения, но неумение их решать не влияет на понимание курса.
Алгебра
Иногда в небольших количествах в курсе используются матрицы и комплексные числа.
Лекции 2017 года доступны по ссылке.
Статистика за 2015 год
- Записалось 86
- Сдавали хоть какие-нибудь д/з 64
- Сдали что-то хотя бы по трем д/з 60
- Писали к/р 50
- Максимальное число баллов, набранных на к/р 48 (из 50 возможных)
- Минимальное число баллов, набранных на к/р 0
- Средний балл за к/р (среди писавших) 22,9
- Итоговая оценка за курс: Отлично 10
- Хорошо 13
- Удовлетворительно 13
Статистика за 2016 год
- Записалось 68
- Сдавали хоть какие-нибудь д/з 60
- Сдали что-то хотя бы по трем д/з 56
- Писали к/р 50
- Максимальное число баллов, набранных на к/р 50 (из 50 возможных, впервые за всю историю)
- Минимальное число баллов, набранных на к/р 1
- Средний балл за к/р (среди писавших) 29,5
- Итоговая оценка за курс: Отлично 22
- Хорошо 15
- Удовлетворительно 10
Преподаватели
Список лекций
Основные понятия теории множеств. Бинарные отношения и функции. Рефлексивность, симметричность, транзитивность. Взаимно-однозначные соответствия. Счетные множества.
- Успенский В. А., Верещагин Н. К., Плиско В. Е. Вводный курс математической логики. М., Физматлит, 2004.
- Верещагин Н. К., Шень А. Х. Начала теории множеств. М., МЦНМО, 2002.
Асимптотики сумм и рекуррентных последовательностей. Теорема Штольца. Оценки и асимптотики для комбинаторных величин. Элементарные оценки факториалов, биномиальных коэффициентов и пр. Формула Стирлинга (без доказательства).
- Грин Д., Кнут Д. Математические методы анализа алгоритмов. М., Мир, 1989.
- Грэхем Р., Кнут Д., Паташник О. Конкретная математика. Основание информатики. М., Мир, 1998.
- Odlyzko A. M. Asymptotic Enumeration Methods. Глава из книги Handbook of Combinatorics, vol. 2, R. L. Graham, M. Groetschel and L. Lovasz, eds., Elsevier, 1995, pp. 1063–1229.
Понятие об энтропии. Асимптотики для биномиальных коэффициентов и прочее. Оценки сумм биномиальных коэффициентов. Замена сумм интегралами в асимптотических оценках. Преобразование Абеля. Примеры: гармонические числа, постоянная Эйлера, суммирование по простым числам и т.д.
Рекуррентные соотношения и производящие функции. Числа Фибоначчи. Формула Бинэ и матричное представление чисел Фибоначчи. Действия с производящими функциями. Применение производящих функций для решения рекуррентных соотношений.
- Ландо С.К. Лекции о производящих функциях. М., МЦНМО, 2004.
- Грэхем Р., Кнут Д., Паташник О. Конкретная математика. Основание информатики. М., Мир, 1998.
- Грин Д., Кнут Д. Математические методы анализа алгоритмов. М., Мир, 1989.
Линейные рекуррентные соотношения с постоянными коэффициентами. Применение степенных рядов и производящих функций для доказательства комбинаторных тождеств. Производящие функции для биномиальных коэффициентов. Взаимно рекуррентные последовательности.
Произведение Адамара. Экспоненциальные производящие функции. Числа Стирлинга и их применение. Числа Белла. Факториальные степени и их связь с обычными степенями. Экспоненциальные производящие функции для чисел Стирлинга, Белла и факториальных степеней.
- Грэхем Р., Кнут Д., Паташник О. Конкретная математика. Основание информатики. М., Мир, 1998.
- Риордан Д. Введение в комбинаторный анализ. М., ИЛ, 1963.
Числа и многочлены Бернулли. Формула суммирования Эйлера–Маклорена. Ее частные случаи и приложения.
Дискретная вероятность. Классическое определение вероятности. Условные вероятности. Независимость событий. Формулы полной вероятности и Байеса. Схема Бернулли. Полиномиальная схема. Случайные графы и множества. Приложения к комбинаторике.
- Ширяев А. Н. Вероятность. М. Наука, 1989.
- Грэхем Р., Кнут Д., Паташник О. Конкретная математика. Основание информатики. М., Мир, 1998.
- Алон Н., Спенсер Дж. Вероятностный метод. М. Бином, 2009. (приложения к комбинаторике)
Случайные величины. Функции распределения. Независимые случайные величины. Математическое ожидание и дисперсия. Неравенства Маркова, Чебышёва и Чернова. Приложение к комбинаторике: случайные графы.
Ковариация и коэффициент корреляции. Независимость и некоррелированность случайных величин. Закон больших чисел для схемы Бернулли. Локальная и интегральная предельные теоремы Муавра–Лапласа для схемы Бернулли. Теорема Пуассона. Приложения случайных величин к комбинаторике и теории чисел.
Геометрическая вероятность. Парадокс Бертрана. Метод Монте-Карло. Абсолютно непрерывные распределения. Основные виды распределений. Числовые характеристики распределений: математическое ожидание, дисперсия, моменты, факториальные моменты. Совместные распределения. Ковариация и корреляция.
Производящие функции и характеристические функции случайных величин. Центральная предельная теорема (различные формулировки).