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

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

Описание

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

В 2013 году курс записываться не будет, лекции 2012 года доступны по ссылке.

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

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

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

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

  • Успенский В. А., Верещагин Н. К., Плиско В. Е. Вводный курс математической логики. М., Физматлит, 2004.
  • Верещагин Н. К., Шень А. Х. Начала теории множеств. М., МЦНМО, 2002.
Элементарный асимптотический анализ

Асимптотики сумм и рекуррентных последовательностей. Теорема Штольца. Оценки и асимптотики для комбинаторных величин. Элементарные оценки факториалов, биномиальных коэффициентов и пр. Формула Стирлинга (без доказательства).

  • Грэхем Р., Кнут Д., Паташник О. Конкретная математика. Основание информатики. М., Мир, 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.
Оценки и асимптотики для комбинаторных величин

Понятие об энтропии. Асимптотики для биномиальных коэффициентов и прочее. Оценки сумм биномиальных коэффициентов. Замена сумм интегралами в асимптотических оценках. Преобразование Абеля. Примеры: гармонические числа, постоянная Эйлера, суммирование по простым числам и т.д.

  • Грэхем Р., Кнут Д., Паташник О. Конкретная математика. Основание информатики. М., Мир, 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.
  • Greene D.H., Knuth D.E. Mathematics for the Analysis of Algorithms. Birkhauser, 1990.
Производящие фунцкии

Применение степенных рядов и производящих функций для доказательства комбинаторных тождеств. Производящие функции для биномиальных коэффициентов. Произведение Адамара. Взаимно рекуррентные последовательности.

  • Ландо С.К.Лекции о производящих функциях. М., МЦНМО, 2004.
  • Грэхем Р., Кнут Д., Паташник О. Конкретная математика. Основание информатики. М., Мир, 1998.
  • Greene D.H., Knuth D.E. Mathematics for the Analysis of Algorithms. Birkhauser, 1990.
Экспоненциальные производящие фунцкии

Экспоненциальные производящие фунцкии. Формальная связь с обычными производящими функциями. Факториальные степени. Числа Стирлинга и их применение. Числа Белла.

  • Грэхем Р., Кнут Д., Паташник О. Конкретная математика. Основание информатики. М., Мир, 1998.
  • Риордан Д. Введение в комбинаторный анализ. М., ИЛ, 1963.
Числа и многочлены Бернулли

Числа и многочлены Бернулли. Формула суммирования Эйлера–Маклорена. Ее частные случаи и приложения.

  • Грэхем Р., Кнут Д., Паташник О. Конкретная математика. Основание информатики. М., Мир, 1998.
  • Риордан Д. Введение в комбинаторный анализ. М., ИЛ, 1963.
Основы теории вероятностей

Дискретная вероятность. Классическое определение вероятности. Условные вероятности. Независимость событий. Формулы полной вероятности и Байеса. Схема Бернулли. Полиномиальная схема. Случайные графы и множества. Приложения к комбинаторике: нижняя оценка чисел Рамсея, теоремы Эрдеша–Мозера и Эрдеша–Хайнала.

  • Ширяев А. Н. Вероятность. М. Наука, 1989.
  • Грэхем Р., Кнут Д., Паташник О. Конкретная математика. Основание информатики. М., Мир, 1998.
  • Алон Н., Спенсер Дж. Вероятностный метод. М. Бином, 2009. (приложения к комбинаторике)
Случайные величины

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

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

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

  • Ширяев А. Н. Вероятность. М. Наука, 1989.
  • Алон Н., Спенсер Дж. Вероятностный метод. М. Бином, 2009. (приложения к комбинаторике)
Геометрическая вероятность и общее определение вероятности

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

  • Ширяев А. Н. Вероятность. М. Наука, 1989.
  • Алон Н., Спенсер Дж. Вероятностный метод. М. Бином, 2009. (приложения к комбинаторике)
Центральная предельная теорема

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

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