Основы дискретной математики
Санкт-Петербург / осень 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
Дата и время Название Место Материалы
06 сентября
18:30–19:50
Элементарная комбинаторика, лекция Таймс, ауд. с белыми досками Нет
06 сентября
20:00–21:20
Сочетания, семинар Таймс, ауд. с белыми досками файлы
20 сентября
18:30–19:50
Принцип включений-исключений, лекция Таймс, ауд. с белыми досками Нет
20 сентября
20:00–21:20
Принцип Дирихле, семинар Таймс, ауд. с белыми досками файлы
27 сентября
18:30–19:50
Частично упорядоченные множества, лекция Таймс, ауд. с белыми досками Нет
27 сентября
20:00–21:20
Принцип включений-исключений, семинар Таймс, ауд. с белыми досками файлы
04 октября
18:30–19:50
Группа перестановок, лекция Таймс, ауд. с белыми досками Нет
04 октября
20:00–21:30
Группа перестановок, семинар Таймс, ауд. с белыми досками файлы
11 октября
18:30–19:50
Разбиения числа в сумму слагаемых, лекция Таймс, ауд. с белыми досками Нет
11 октября
20:00–21:30
Разбиения и производящие функции, семинар Таймс, ауд. с белыми досками файлы
18 октября
18:30–19:50
Рекуррентные соотношения. Числа Каталана и числа Белла, лекция Таймс, ауд. с белыми досками Нет
18 октября
20:00–21:30
Разбиения, производящие функции и рекуррентные соотношения, семинар Таймс, ауд. с белыми досками файлы
25 октября
18:30–19:50
Методы линейной алгебры в комбинаторике, лекция Таймс, ауд. с белыми досками Нет
25 октября
20:00–21:30
Рекурренты и линейная алгебра, семинар Таймс, ауд. с белыми досками файлы
01 ноября
19:00–21:00
Линейная алгебра в комбинаторике, семинар Таймс, ауд. с белыми досками файлы
08 ноября
18:30–19:50
Основы теории графов, лекция Таймс, ауд. с белыми досками Нет
08 ноября
20:00–21:30
Основы теории графов, семинар Таймс, ауд. с белыми досками файлы
15 ноября
18:30–19:50
Ориентированные графы, лекция Таймс, ауд. с белыми досками Нет
15 ноября
20:00–21:30
Раскраски графов, лекция Таймс, ауд. с белыми досками Нет
22 ноября
18:30–19:50
Паросочетания и покрытия, лекция Таймс, ауд. с белыми досками Нет
22 ноября
20:00–21:20
Ориентированные графы и паросочетания, семинар Таймс, ауд. с белыми досками файлы
29 ноября
18:30–19:50
Планарные графы, лекция Таймс, ауд. с белыми досками Нет
29 ноября
20:00–21:20
Планарные графы, семинар Таймс, ауд. с белыми досками файлы
06 декабря
19:00–21:00
Контрольная работа, семинар Таймс, ауд. с белыми досками Нет
13 декабря
19:00–21:00
Контрольная работа 2, семинар Таймс, ауд. с белыми досками Нет
20 декабря
19:00–21:00
Финальное занятие, семинар Таймс, ауд. с белыми досками Нет