Основы дискретной математики

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

Описание

Целью курса является знакомство слушателей с основными понятиями и методами дискретной математики.

Правила сдачи курса:

Будет выдано несколько домашних заданий, на последнем семинаре состоится контрольная работа. Пусть \(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\) — курс не засчитывается

Для вопросов и обсуждения практик следует вступить в этот Telegram-чат.

Текущие успехи ведутся в этой Google-табличке.

По всем вопросам о курсе, семинарах и домашних заданиях можно писать преподавателям практики

Книги – источники знаний

(перечислены в порядке возрастания сложности)

  • Н. Я. Виленкин — Комбинаторика
  • 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)-плотные множества, множества с двумя расстояниями и т.д.)