Это базовый курс дискретной математики и комбинаторики. Он для всех, кто хочет развить математическую интуицию, помогающую в работе с дискретными объектами и алгоритмами на них
1. Введение и знакомство с базовыми понятиями
1.1 Приветствие
1.2 Множества, отображения
1.3 Суммы и произведения с параметром
1.4 Целые части
1.5 Принцип Дирихле
1.6 Индукция
1.7 Основные дискретные объекты комбинаторики
1.8 Задачи на подсчёт
1.9 Биномиальные коэффициенты
1.10 Формула включений-исключений
1.11 Рекуррентные соотношения и метод выделенного элемента
1.12 Повторение материала первого модуля
2. Основные понятия теории графов
2.1 Азбука теории графов I: графы, подграфы, степени вершин
2.2 Азбука теории графов II: специальные графы, путешествия по графу
2.3 Одинаковые графы: изоморфизм
2.4 Задачи, задачи, задачи…
2.5 Деревья
2.6 Как нарисовать граф
2.7 Раскраски графов
2.8 Эйлеровы и гамильтоновы циклы
2.9 Повторение материала второго модуля
3. Асимптотики дискретных величин
3.1 Кто побеждает в битве на бесконечности: рассудят O, Ω, Θ, o, ~
3.2 Оценки для факториала и биномиальных коэффициентов
3.3 Суммы, быстро растущие функции, и другие насущные вещи
4. Вероятностный метод
4.1 Теорема Рамсея, числа Рамсея
4.2 Ликбез по теории вероятностей + случайные графы на десерт
4.3 Вероятностный метод на примере нижней оценки чисел Рамсея
4.4 Продолжение ликбеза: случайные величины, Марков и Чебышёв
4.5 Теорема о числе скрещиваний
4.6 Теорема Эрдёша о нелокальности хроматического числа
5. Алгебра на службе дискретной математики
5.1 Ликбез по алгебре: простые числа, равенство по модулю
5.2 Ликбез по алгебре: поля вычетов, многочлены
5.3 Nullstellensatz: обобщение теоремы Лагранжа и его следствия
5.4 Комбинаторика алгебры: аддитивная комбинаторика
5.5 Ликбез по алгебре: линейные пространства
5.6 Скалярные произведения и теорема Фишера
5.7 Конструктивная нижняя оценка чисел Рамсея
6. Избранные сюжеты комбинаторики и теории графов
6.1 Потоки в сетях и паросочетания в двудольных графах
6.2 Решённая задача Турана и открытая проблема Заранкевича
6.3 Решаем частный случай проблемы Заранкевича при помощи алгебры
6.4 Две замечательные теоремы о раскрасках: теоремы Брукса и Кёнига
6.5 Подводим итоги курса
Дискретная математика
Комбинаторика
Алгоритмы
Графы
Асимптотический анализ
English
Русский
Comments