Рекуррентные соотношения: определение, примеры, метод решения. Суммирование рекуррентных последовательностей. Множества, способы задания, операции, отношения. Бинарные отношения: определение, примеры, свойства. Матрица бинарного отношения и ее свойства. Основные типы задач и правила комбинаторики. Основные комбинаторные конфигурации (кортеж, размещение, перестановка, сочетание). Комбинаторные конфигурации с повторением (размещения, перестановки и сочетания с повторением). Свойства сочетаний. Треугольник Паскаля. Полиномиальная формула. Бином Ньютона. Биномиальные коэффициенты: основные тождества. Разбиения множества. Принцип включения-исключения. Принцип Дирихле. Обобщенный принцип Дирихле. Основные понятия теории графов: граф, инцидентность, степень вершины, формула Эйлера для степеней вершин, смежность, изоморфизм. Понятие пути и цикла в графе. Эйлеровый цикл (цепь), критерий существования эйлерового цикла (цепи), примеры. Решение задачи о 7 мостах. Гамильтоновый цикл: определение, примеры, достаточные условия Оре и Дирака, задача коммивояжёра. Способы задания неориентированного графа: перечисление, матрица смежности, матрица инцидентности, список смежности, список рёбер. Свойства. Способы задания ориентированного графа: перечисление, матрица смежности, матрица инцидентности, список смежности, список дуг. Определения и свойства. Плоские графы. Грань плоского графа. Формула Эйлера для плоских графов. Примеры. Планарные графы. Критерий планарности (критерий Понтрягина-Куратовского). Решение задачи о трёх домах и трёх колодцах. Правильная раскраска и хроматическое число графа, примеры. Задача о политической карте. Теорема о пяти красках. Гипотеза четырёх красок.

Рекомендуемая литература

Основная:

A. Дискретная математика для программистов: учебник для вузов по направлению подготовки специалистов «Информатика и вычислительная техника»: доп. М-вом образования РФ. СПб.: Питер, 2006. – 364с Редькин математика. – М.: Физматлит, 2009. – 174с. Поздняков математика: учебник для вузов: доп. М-вом образования и науки РФ. – М.: Академия, 2008. – 448с.

Дополнительная:

Гаврилов и упражнения по дискретной математике [Электронный ресурс] / Режим доступа: http://www. biblioclub. ru/book/68128/ Микони математика для бакалавра: множества, отношения, графы [Электронный ресурс] / Режим доступа:http://e. /books/element. php? pl1_cid=25&pl1_id=4316. Редькин математика [Электронный ресурс] : учебник для вузов : доп. УМО вузов РФ / . - Режим доступа :http://www. biblioclub. ru/book/75709/.