Асимптотический анализ и теория вероятностей

Санкт-Петербург, осень 2016

Описание

В курсе будут разобраны такие темы, как: теория множеств, асимптотики, производящие функции, дискретная и условная вероятность, случайные величины, предельные теоремы.

Сдача курса

Каждое д/з 20 баллов, за все д/з можно набрать 80 баллов. Контрольная стоит 50 баллов. Итого вместе с д/з можно набрать 130 баллов.
  • Набравшие 110 баллов получают оценку 5.
  • Набравшие 98 баллов получают оценку 4.
  • Набравшие 85 баллов получает оценку 3.
(По окончании проверки контрольной не исключено небольшое понижение планок). Слушатели, не набравшие 50 баллов за д/з (в том числе и с помощью иногда встречающихся бонусов), автоматически получают за курс оценку 2 и к контрольной не допускаются.

Необходимые знания для понимания курса

Комбинаторика

Необходимо знание комбинаторики примерно в объеме первой лекции курса «Основы дискретной математики».

Начиная со 2-й лекции нужно: знакомство с факториалами и биномиальными коэффициентами (число перестановок, число сочетаний), основные комбинаторные величины и простейшие комбинаторные формулы.

Для понимания некоторых примеров применения теории вероятностей в комбинаторике (8-я лекция и далее) нужно знакомство с базовыми определениями теории графов. Достаточно первой лекции по графам из курса «Основы дискретной математики».

Математический анализ

Необходимо знание математического анализа в объеме первого курса технического ВУЗа.

Умение вычислять простые пределы (2-я лекция и далее). Знакомство с определенными интегралами и их связью с площадями (3-я лекция и далее). Начиная с 4-й лекции нужно умение дифференцировать и интегрировать. Достаточно уметь интегрировать рациональные функции (точнее нужно уметь раскладывать их на простейшие, что требуется при интегрировании рациональных функций), а также некоторые достаточно простые функции. Знакомство с формулами Тейлора для элементарных функций. Знакомство с формулой интегрирования по частям. Определение ряда, суммы ряда и сходимости ряда. В нескольких примерах в курсе (6-я лекция) возникают простые дифференциальные уравнения, но неумение их решать не влияет на понимание курса.

Алгебра

Иногда в небольших количествах в курсе используются матрицы и комплексные числа.

Преподаватели

Список лекций

Теория множеств

Основные понятия теории множеств. Бинарные отношения и функции. Рефлексивность, симметричность, транзитивность. Взаимно-однозначные соответствия. Счетные множества.

  • Успенский В. А., Верещагин Н. К., Плиско В. Е. Вводный курс математической логики. М., Физматлит, 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. (приложения к комбинаторике)
Случайные величины

Случайные величины. Функции распределения. Независимые случайные величины. Математическое ожидание и дисперсия. Случайные графы: выбор двудольного подграфа. Неравенства Маркова, Чебышёва и Чернова. Приложение к комбинаторике: выбор двудольного подграфа.

Предельные теоремы

Ковариация и коэффициент корреляции. Независимость и некоррелированность случайных величин. Закон больших чисел для схемы Бернулли. Локальная и интегральная предельные теоремы Муавра–Лапласа для схемы Бернулли. Теорема Пуассона. Приложения случайных величин к теории чисел: теорема Харди–Рамануджана о числе простых делителей.

Геометрическая вероятность и общее определение вероятности

Геометрическая вероятность. Парадокс Бертрана. Метод Монте-Карло. Абсолютно непрерывные распределения. Основные виды распределений. Числовые характеристики распределений: математическое ожидание, дисперсия, моменты, факториальные моменты. Совместные распределения. Ковариация и корреляция.

Центральная предельная теорема

Производящие функции и характеристические функции случайных величин. Центральная предельная теорема (различные формулировки).

  • Ширяев А. Н. Вероятность. М. Наука, 1989.
  • Грэхем Р., Кнут Д., Паташник О. Конкретная математика. Основание информатики. М., Мир, 1998.