Совместный проект Школы анализа данных Яндекса, CS клуба, Академии современного программирования и ФМЛ №239. Целью курса является знакомство слушателей с понятиями, которые понадобятся им для понимания дальнейших курсов (теория множеств, логика, элементарная комбинаторика, асимптотические оценки и производящие функции, теория графов, теория вероятности).

Лекция 1. Теория множеств

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

Лекция 2. Логика

Логика высказываний. Таблицы истинности. Пропозициональные формулы. Кванторы. Предикаты. Языки логики первого порядка. Интерпретация языков.

Лекция 3. Основы комбинаторики

Основные комбинаторные величины и простейшие комбинаторные формулы. Числа сочетания (с повторениями и без повторений), числа размещения (с повторениями и без повторений), перестановки. Треугольник Паскаля. Бином Ньютона и биномиальные коэффициенты.

Лекция 4. Формула включений-исключений

Формула включений-исключений. Задача о беспорядках. Задача о разбиении множеств. Мультиноминальные коэффициенты. Задачи о разбиениях чисел на слагаемые. Упорядоченные и неупорядоченные разбиения. Диаграммы Юнга.

Лекция 5. Оценки и асимптотики для комбинаторных величин

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

Лекция 6. Производящие функции

Производящие функции. Числа Фибоначчи. Формула Бинэ и матричное представление чисел Фибоначчи. Линейные рекуррентные соотношения с постоянными коэффициентами. Применение производящих функций для решения рекуррентных соотношений. Производящие функции и разбиения чисел. Теорема Харди-Рамануджана (б/д). Производящие функции для биномиальные коэффициентов.

Лекция 7. Экспоненциальные производящие функции

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

Лекция 8. Основы теории графов

Основы теории графов. Пути, циклы, матрица инцидентности, связность. Дополнительный граф. Задача Рамсея. Изоморфизмы графов.

Лекция 9. Деревья, пути, циклы

Деревья. Двудольные графы. Эйлеровы и Гамильтоновы пути и циклы.

Лекция 10. Лемма Холла

Лемма Холла и ее переформулировки. Теорема Кенига и ее переформулировки. Планарные графы. Формула Эйлера (б/д). Теорема Куратовского (б/д).

Лекция 11. Основы теории вероятностей

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

Лекция 12. Случайные величины

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

Лекция 13. Предельные теоремы

Закон больших чисел для схемы Бернулли. Локальная и интегральная предельные теоремы Муавра-Лапласа для схемы Бернулли. Теорема Пуассона. Приложения к комбинаторике.