Основы дискретной математики
Санкт-Петербург, осень 2018
Описание
Целью курса является знакомство слушателей с основными понятиями и методами дискретной математики.
Правила сдачи курса:
Будет выдано семь домашних заданий, на последнем семинаре состоится контрольная работа. Пусть \(H\) — сумма ваших баллов за все домашние работы, а \(T\) — ваши баллы за контрольную. Тогда ваш финальный балл за курс определяется так: \[S \,=\, 0.6 \frac{H + B}{max(H)} \,+\, 0.4\frac{T}{max(T)},\]
где
\(H\) — набранные баллы за домашние работы,
\(max(H)\) — максимально возможные баллы за домашние работы,
\(T\) — набранные баллы за контрольную (максимум из двух попыток),
\(max(T)\) — максимально возможные баллы за контрольную,
\(B\) — бонусные баллы за разборы на семинарах и допзадачи.
Будет две попытки написания контрольной. Пусть домашнее задание номер \(i\) может принести \(a_i\) баллов; тогда эти баллы учитываются в общей сумме, если вы набрали за задание \(i\) не меньше, чем \(0.6 \cdot a_i\) баллов (если студент набрал меньше 60% баллов за конкретную тему, эта тема не учитывается).
Алгоритм выставления оценок:
- \(0.8 \le S\) — оценка 5
- \(0.7 \le S < 0.8\) — оценка 4
- \(0.6 \le S < 0.7\) — оценка 3
- \(S < 0.6\) — вы молодец, но курс не засчитывается
Текущие успехи ведутся в этой Google-табличке. По всем вопросам о курсе, семинарах и домашних заданиях можно писать преподавателю практики Михаилу Слабодкину на slabodkin.m@gmail.com
Книги – источники знаний
(перечислены в порядке возрастания сложности)
- Н. Я. Виленкин —
Комбинаторика
- Miklós Bóna —
A Walk Through Combinatorics: An Introduction to Enumeration and Graph Theory
- Marshall Hall –
Combinatorial Theory
(существует в русском варианте) - Stasys Jukna –
Extremal Combinatorics
Преподаватели
Список лекций
Основные комбинаторные величины и простейшие комбинаторные формулы. Числа размещения и сочетания (с повторениями и без повторений). Бином Ньютона и биномиальные коэффициенты. Простейшие соотношения на биномиальные коэффициенты. Треугольник Паскаля. Обобщение бинома Ньютона и мультиномиальные коэффициенты.
Формула включений-исключений. Субфакториалы (задача о беспорядках). Формула обращения Мебиуса.
Понятие частично упорядоченного множества. Функция Мебиуса для частично упорядоченного множества. Цепи и антицепи. Теорема Дилуорса (б/д). Теорема Мирского.
Четность перестановки, разложение в произведение транспозиций, разбиение на циклы, четность цикла, классы сопряженных и циклический тип перестановки.
Задачи о разбиениях чисел на слагаемые. Упорядоченные и неупорядоченные разбиения. Диаграммы Юнга. Рекуррентные соотношения для функций разбиения. Формула Харди-Рамануджана (б/д).
Рекуррентные соотношения. Числа Каталана и числа Белла. Различные интерпретации чисел Каталана.
Использование линейной алгебры для доказательства комбинаторных результатов. Различные примеры использования этого метода (неравенство Фишера, (n,k)-плотные множества, множества с двумя расстояниями и т.д.)
Графы и орграфы. Основные определения. Матрицы смежности и инцидентности. Маршруты, пути и циклы. Связность, компоненты связности. Деревья и их свойства.
Связность орграфов: различные виды связности, компоненты сильной связности, граф компонент. Турнирные графы. Гамильтоновы пути в турнирном графе. Теорема Редеи (б/д). Циклы в сильно связных турнирах. Теорема Муна.
Двудольные графы, критерий двудольности. Вершинные и реберные раскраски графа. Простейшие свойства раскрасок. Теорема Брукса. Теоремы Визинга и Гупты (б/д). Совершенные графы. Слабая и сильная гипотезы Бержа: доказательство слабой гипотезы.
Независимые множества и покрытия. Связь между ними. Паросочетания в двудольном графе: теоремы Холла и Кёнига. Вывод теоремы Дилуорса из теоремы Кёнига.
Планарные и плоские графы. Формула Эйлера и следствия из нее. Понятие двойственного графа. Критерий раскрашиваемости граней в 2 цвета. Раскраска вершин планарного графа в 5 цветов. Гипотеза о четырех красках: формулировка, эквивалентность Тейта (б/д), обсуждение компьютерного доказательства. Теорема Куратовского (б/д).