Комбинаторика и теория графов 2026/2027

ОБЪЯВЛЕНИЯ

Группа курса

Общая информация о курсе Комбинаторика и теория графов, М++, 1 курс

Преподаватели и ассистенты

Лектор: Артём Максимович Максаев

Семинарист: Иван Сергеевич Бельдиев

Ассистенты: Пётр Крамарский, Михаил Далингер, Андрей Кандрашкин

Таблица оценок

Ведомость

Правила оценивания

Домашние задания выдаются еженедельно и сдаются перед следующим семинаром. Предварительная оценка за домашнее задание пропорциональна доле решенных задач (с учетом неполных решений, за которые выставляется неполный балл). Оценка становится окончательной после защиты домашнего задания. Один раз за весь курс домашнее задание разрешается сдать на неделю позже срока без потери баллов (предварительно уведомив ассистента).

Экзамен — это письменная работа. Пересдача проводится по правилам экзамена. Комиссия проводится по тем же правилам в письменном формате (передаётся только экзамен, формула учитывает накопленную за курс оценку по остальным элементам контроля).

Оценка за курс

Итоговая оценка = Округление(0.25 * ДЗ + 0.35 * КОЛЛ + 0.4 * ЭКЗ)

В вычислениях текущие оценки и промежуточные величины не округляются. Результат вычисляется точно и округляется только в момент выставления промежуточной и итоговой оценок. Округление арифметическое.

Программа курса

Далее приводится содержание лекций с указанием литературного источника. Отметим, что литературный источник не заменяет лекции и лишь приблизительно ей соответствует: материал в нем может быть изложен иначе, быть неполным или, наоборот, чрезмерным для нашего курса.

Лекция 1. Множества и их элементы, примеры множеств. Парадокс Рассела. Операции со множествами. Доказательство теоретико-множественных тождеств: по определению и через таблицу истинности (разбор случаев). Упорядоченная пара, декартово произведение множеств. Определение функции, ее области определения и области значений, образа и полного прообраза множества. Инъекции, сюръекции, биекции.

Литература: [1, §5.1-5.2, §6.3-6.4]

Онлайн лекция 1. Правило суммы, задача о числе путей. Правило произведения, конечные слова в алфавите. Упорядоченный выбор k элементов из n (с повторениями или без повторений). Числа сочетаний: явная и рекуррентная формула. Треугольник Паскаля. Бином Ньютона. Сумма и знакочередующаяся сумма биномиальных коэффициентов. Полиномиальные коэффициенты. Сочетания с повторениями. Число элементов в объединении двух множеств. Формула включений-исключений.

Литература: [1, лекция 2, §5.6]

Записи лекций

На курсе есть две предзаписанные онлайн-лекции:

папка LEC 01 - лекция по базовой комбинаторике (просьба посмотреть до 7.09);

папка LEC 02 - лекция по основам теории неориентированных графов (просьба посмотреть до 21.09);