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

2026/2027

Учебный год

RUS

Обучение ведется на русском языке

3

Кредиты

Кто читает:

Департамент больших данных и информационного поиска

Статус:

Курс по выбору

Когда читается:

1-й курс, 1 модуль

Преподаватели

Бельдиев Иван Сергеевич

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

Программа дисциплины

Аннотация

Курс знакомит с фундаментальными понятиями и методами двух тесно связанных областей дискретной математики. В первой части рассматриваются основные комбинаторные принципы: правила суммы и произведения, биномиальные и полиномиальные коэффициенты, формула включений-исключений, а также метод математической индукции в его различных формах. Вторая часть посвящена теории графов — изучаются неориентированные и ориентированные графы, деревья, связность, эйлеровы циклы, раскраски и хроматический многочлен, паросочетания, вершинные покрытия и теорема Кёнига. Кроме того, курс включает введение в вероятностные методы: вероятностное пространство, условная вероятность, независимость, математическое ожидание, неравенства Маркова и Чебышёва, а также классические приложения вероятностного метода в комбинаторике, включая оценки чисел Рамсея.