Бакалавриат
2026/2027
Комбинаторика и теория графов
Статус:
Курс по выбору (Прикладная математика и информатика)
Где читается:
Факультет компьютерных наук
Когда читается:
1-й курс, 1 модуль
Охват аудитории:
для своего кампуса
Язык:
русский
Кредиты:
3
Контактные часы:
40
Программа дисциплины
Аннотация
Курс знакомит с фундаментальными понятиями и методами двух тесно связанных областей дискретной математики. В первой части рассматриваются основные комбинаторные принципы: правила суммы и произведения, биномиальные и полиномиальные коэффициенты, формула включений-исключений, а также метод математической индукции в его различных формах. Вторая часть посвящена теории графов — изучаются неориентированные и ориентированные графы, деревья, связность, эйлеровы циклы, раскраски и хроматический многочлен, паросочетания, вершинные покрытия и теорема Кёнига. Кроме того, курс включает введение в вероятностные методы: вероятностное пространство, условная вероятность, независимость, математическое ожидание, неравенства Маркова и Чебышёва, а также классические приложения вероятностного метода в комбинаторике, включая оценки чисел Рамсея.