Раздел 6. Дискретная математика

Тема 1. Теория множеств.

Способы задания конечных четких множеств. Элемент множества. Кванторы общности и существования. Мощность множества. Ординарные и неординарные множества. Равенство множеств. Подмножество. Включение строгое и нестрогое. Собственные и несобственные подмножества.

Определения и свойства операций над множествами. Разбиения множества. Тривиальные и нетривиальные разбиения.

Прямое (декартово) произведение множеств. Степень множества. Понятие и свойства кортежей. Инверсия и композиция кортежа. График. Свойства графиков. Инверсия, проекция и композиция графиков.

Соответствие. Определение и способы задания соответствий. Свойства соответствий. Понятие образа и прообраза при соответствии. Понятие функции. Отображение функции.

Отношение. Определение и способы задания отношений. Свойства отношений. Операции над отношениями. Отношение эквивалентности. Отношение порядка.

Расплывчатые (нечеткие) множества. Определение и способ задания. Степень принадлежности. Степень включения двух нечетких множеств.

Тема 2. Элементы Булевой алгебры

Переключательные функции. Способы задания переключательных функций. Минимизация переключательных функций. Теорема о функциональной полноте. Функционально полный базис.

Тема 3. Теория графов.

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

Пути в графе. Определения маршрута, цепи, цикла, простой цепи и простого цикла. Подсчет числа маршрутов в графе. Понятие связности.

Эйлеровы и Гамильтоновы циклы в графе. Задача коммивояжера.

Построение деревьев в графе. Дерево, корни, ветви. Определение дерева. Покрывающие деревья. Число покрывающих деревьев в полном графе. Понятие расстояния в графе.

Числа графов. Цикломатическое число. Понятие компоненты связности. Хроматическое число. Задача раскраски. Число внутренней устойчивости. Независимые подмножества. Число внешней устойчивости. Доминирующие подмножества.

3.6. Изоморфизм. Понятие планарности. Число планарности.

ЛИТЕРАТУРА

1. Мелихов А.Н., Берштейн Л.С. Конечные четкие и нечеткие множества. Ч. 1, 2. – Таганрог: Изд-во ТРТУ, 1981.

2. Курейчик В.М. Математическое обеспечение конструкторского и технологического проектирования с применением САПР. – М.: Радио и связь, 1990.

3. Гладков Л.А., Курейчик В.В., Курейчик В.М. Дискретная математика: Учебное пособие. Ч. 1. Теория множеств. / Под ред. В.М. Курейчика. – Таганрог: Изд-во ТРТУ, 2005.

4. Курейчик В.М. Дискретная математика: Учебное пособие. Ч. 1. – Таганрог: Изд-во ТРТУ, 1997.

5. Курейчик В.М. Дискретная математика: Учебное пособие. Ч. 2. Элементы теории графов. № 2536-2. – Таганрог: Изд-во ТРТУ, 1997.

6. Новиков Ф.А. Дискретная математика для программистов. – СПб.: Питер, 2000.

7. Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов. – М.: Физматлит, 2002.