Дискретная математика: вопросы к дифференцированному зачету для 4 курса ПО ЭО

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

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

Основная:

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/.