Дискретная математика: Учебное пособие

Description

Издание содержит теоретический материал по основным разделам дисциплины «Дискретная математика»: теории множеств, теории графов, а также основные свойства булевых функций и их минимизация в классе дизъюнктивных нормальных форм. Теоретический материал каждого раздела сопровождается примерами решения типовых задач. В конце представлены задачи для самостоятельного решения и задания к контрольным работам. Подготовлено на кафедре «Компьютерные технологии» и предназначено для обучающихся по специальностям 10.05.02 «Информационная безопасность телекоммуникационных систем», 10.05.03 «Информационная безопасность автоматизированных систем», 01.05.01 «Фундаментальные математика и механика» и по направлению подготовки 01.03.02. «Прикладная математика и информатика», изучающих дисциплины «Дискретная математика», «Математическая логика». Введение Г л а в а 1 ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ 1.1. Понятие множества 1.2. Операции над множествами 1.3. Бинарные отношения 1.4. Функции 1.5. Отношения эквивалентности. Фактор-множества 1.6. Отношения порядка Задачи к главе 1 Г л а в а 2 ТЕОРИЯ ГРАФОВ 2.1. Основные понятия теории графов 2.2. Деревья. Свойства деревьев 2.3. Орграфы 2.4. Геометрическая реализация графов 2.5. Непланарность графов K5 и K3,3. Теорема Понтрягина ( Куратовского 2.6. Операции над графами 2.7. О числе путей в графах 2.8. Задачи о кратчайших путях 2.9. Метод поиска в ширину 2.10. Алгоритм Дейкстры 2.11. Алгоритм Флойда 2.12. Задача о кратчайшем остове графа. Алгоритм Краскала 2.13. Эйлеровы циклы 2.14. Алгоритм поиска эйлерова цикла 2.15. Задача почтальона 2.16. Гамильтоновы циклы 2.17. Теорема о раскраске планарных графов в пять цветов Задачи к главе 2 Г л а в а 3 БУЛЕВЫ ФУНКЦИИ 3.1. Функции алгебры логики, способы их задания и основные свойства 3.2. Замкнутые классы в Р2 3.2.1. Класс функций, сохраняющих константу 0 3.2.2. Класс функций, сохраняющих константу 1 3.2.3. Класс монотонных функций 3.2.4. Класс линейных функций 3.2.5. Принцип двойственности. Совершенная конъюнктивная нормальная форма 3.2.6. Класс самодвойственных функций 3.3. Теорема о полноте Задачи к главе 3 Г л а в а 4 Минимизация булевых функций (в классе дизъюнктивных нормальных форм) 4.1. Проблема минимизации булевых функций 4.2. Упрощение дизъюнктивных нормальных форм и тупиковые дизъюнктивные нормальные формы (относительно упрощений) 4.3. Постановка задачи в геометрической форме 4.4. Сокращенная дизъюнктивная нормальная форма 4.5. Тупиковость на основе геометрических представлений. Методы построения тупиковых дизъюнктивных нормальных форм 4.6. Сложность минимальной дизъюнктивной нормальной формы. Особенности дизъюнктивной нормальной формы для функций некоторых классов Задачи к главе 4 Библиографический список Учебное издание