Асимптотический анализ и теория вероятностей
Санкт-Петербург, осень 2015
Описание
В курсе будут разобраны такие темы, как: теория множеств, асимптотики, производящие функции, дискретная и условная вероятность, случайные величины, предельные теоремы.
Сдача курса
Каждое д/з 20 баллов, за все д/з можно набрать 80 баллов. Контрольная стоит 50 баллов. Итого вместе с д/з можно набрать 130 баллов.
- Набравшие 110 баллов получают оценку 5.
- Набравшие 98 баллов получают оценку 4.
- Набравшие 85 баллов получает оценку 3.
Необходимые знания для понимания курса
Комбинаторика
Необходимо знание комбинаторики примерно в объеме первой лекции курса «Основы дискретной математики».
Начиная со 2-й лекции нужно: знакомство с факториалами и биномиальными коэффициентами (число перестановок, число сочетаний), основные комбинаторные величины и простейшие комбинаторные формулы.
Для понимания некоторых примеров применения теории вероятностей в комбинаторике (8-я лекция и далее) нужно знакомство с базовыми определениями теории графов. Достаточно первой лекции по графам из курса «Основы дискретной математики».
Математический анализ
Необходимо знание математического анализа в объеме первого курса технического ВУЗа.
Умение вычислять простые пределы (2-я лекция и далее). Знакомство с определенными интегралами и их связью с площадями (3-я лекция и далее). Начиная с 4-й лекции нужно умение дифференцировать и интегрировать. Достаточно уметь интегрировать рациональные функции (точнее нужно уметь раскладывать их на простейшие, что требуется при интегрировании рациональных функций), а также некоторые достаточно простые функции. Знакомство с формулами Тейлора для элементарных функций. Знакомство с формулой интегрирования по частям. Определение ряда, суммы ряда и сходимости ряда. В нескольких примерах в курсе (6-я лекция) возникают простые дифференциальные уравнения, но неумение их решать не влияет на понимание курса.
Алгебра
Иногда в небольших количествах в курсе используются матрицы и комплексные числа.
В 2015 году курс перезаписываться не будет, лекции 2012 года доступны по ссылке.
Статистика за 2014 год
- Записалось на курс 66
- Сдавали хоть какие-нибудь д/з 56
- Сдали что-то хотя бы по трем д/з 48
- Писали к/р 45
- Максимальное число баллов, набранных на к/р (из 50 возможных) 43
- Минимальное число баллов, набранных на к/р 1
- Средний балл за к/р (среди писавших) 24,4
- Итоговая оценка за курс: отлично 11
- Хорошо 13
- Удовлетворительно 7
Преподаватели
Список лекций
Основные понятия теории множеств. Бинарные отношения и функции. Рефлексивность, симметричность, транзитивность. Взаимно-однозначные соответствия. Счетные множества.
- Успенский В. А., Верещагин Н. К., Плиско В. Е. Вводный курс математической логики. М., Физматлит, 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.
Числа и многочлены Бернулли. Формула суммирования Эйлера–Маклорена. Ее частные случаи и приложения.
- Грэхем Р., Кнут Д., Паташник О. Конкретная математика. Основание информатики. М., Мир, 1998.
- Риордан Д. Введение в комбинаторный анализ. М., ИЛ, 1963.
Дискретная вероятность. Классическое определение вероятности. Условные вероятности. Независимость событий. Формулы полной вероятности и Байеса. Схема Бернулли. Полиномиальная схема. Случайные графы и множества. Приложения к комбинаторике: теоремы Эрдеша–Мозера и Эрдеша–Хайнала.
- Ширяев А. Н. Вероятность. М. Наука, 1989.
- Грэхем Р., Кнут Д., Паташник О. Конкретная математика. Основание информатики. М., Мир, 1998.
- Алон Н., Спенсер Дж. Вероятностный метод. М. Бином, 2009. (приложения к комбинаторике)
Случайные величины. Функции распределения. Независимые случайные величины. Математическое ожидание и дисперсия. Случайные графы: выбор двудольного подграфа. Неравенства Маркова, Чебышёва и Чернова.
Ковариация и коэффициент корреляции. Независимость и некоррелированность случайных величин. Приложения случайных величин к комбинаторике и теории чисел: балансировка векторов, семейства с различными суммами. Закон больших чисел для схемы Бернулли. Локальная и интегральная предельные теоремы Муавра–Лапласа для схемы Бернулли. Теорема Пуассона.
Геометрическая вероятность. Парадокс Бертрана. Метод Монте-Карло. Абсолютно непрерывные распределения. Основные виды распределений. Числовые характеристики распределений: математическое ожидание, дисперсия, моменты, факториальные моменты. Совместные распределения. Ковариация и корреляция.
Производящие функции и характеристические функции случайных величин. Центральная предельная теорема (различные формулировки).
- Ширяев А. Н. Вероятность. М. Наука, 1989.
- Грэхем Р., Кнут Д., Паташник О. Конкретная математика. Основание информатики. М., Мир, 1998.