Плотников А.Д. Дискретная математика: учеб. пособие /А.Д. Плотников. — М., 2005. — 288 с.
Книга написана на основе лекций, которые автор читал на протяжении 20 лет работы в Винницком техническом университете. Содержит следующие разделы: введение в теорию множеств, введение в теорию графов, элементы алгебры и математической логики, минимизация булевых функций, элементы комбинаторики, элементы теории алгоритмов, о разрешимости конструктивных комбинаторных задач, теоретико-множественные свойства экстремальных комбинаторных задач. Материал книги доступно изложен и проверен на нескольких поколениях студентов, содержит самые необходимые сведения для будущих инженеров-системотехников, программистов, кибернетиков и других специальностей. Дается описание некоторых алгоритмов и приведены отлаженные Паскаль-программы для наиболее важных из них. Эти программы могут служить основой для выполнения лабораторных работ по курсу. Для студентов, аспирантов и других читателей, интересующихся отдельными разделами дискретной математики.
Оглавление
От автора...........................................................................3
Глава 1
Введение в теорию множеств
1.1. Понятие множества и способы его задания...................................................5
1.2. Подмножества.................................................................................................7
1.3. Операции над множествами...........................................................................8
1.4. Свойства операций над множествами..........................................................11
1.5. Упорядоченные множества. Прямое произведение множеств....................13
1.5.1. Алгоритм упорядочивания множества...............................................15
1.6. Бинарные отношения...................................................................................16
1.6.1. Основные определения.......................................................................16
1.6.2. Способы задания бинарных отношений............................................18
1.6.3. Операции над бинарными отношениями..........................................19
1.7. Свойства бинарных отношений. Отношение эквивалентности...................21
1.8. Отношение порядка......................................................................................23
1.8.1. Основные определения.......................................................................23
1.8.2. Диаграмма Хассе.................................................................................24
1.9. Разбиение частично упорядоченного множества на цепи...........................25
1.10. Наименьший и наибольший элементы, границы упорядоченного множества...................................................................................................32
1.11. Функциональные бинарные отношения....................................................33
1.11.1. Отображения...................................................................................33
1.11.2. Классификация отображений и функций......................................34
1.12. Мощность множеств...................................................................................34
1.13. Матроиды....................................................................................................35
Контрольные вопросы.........................................................................................38
Упражнения.........................................................................................................40
Литература...........................................................................................................42
Глава 2
Введение в теорию графов
2.1. Основные понятия........................................................................................43
2.2. Способы задания графа................................................................................45
2.2.1. Матрица смежности............................................................................45
2.2.2. Матрица инцидентности....................................................................46
2.2.3. Список ребер.......................................................................................47
2.2.4. Структуры смежности.........................................................................48
2.2.5. Генерация графов................................................................................49
2.3. Части графов.................................................................................................51
2.4. Операции на графах......................................................................................52
2.5. Связность графов и деревья..........................................................................55
2.5.1. Поиск в глубину..................................................................................57
2.6. Числа графов.................................................................................................59
2.7. Эйлеровы и гамильтоновы графы.................................................................62
2.7.1. Поиск гамильтоновых циклов в графе...............................................63
2.8. Изоморфные графы......................................................................................68
2.9. Покрывающие деревья.................................................................................69
2.10. Кратчайший путь в графе............................................................................71
2.11. Паросочетания в графе...............................................................................76
2.12. Потоки в сетях.............................................................................................77
Контрольные вопросы.........................................................................................81
Упражнения.........................................................................................................82
Литература...........................................................................................................85
Глава 3 Элементы алгебры
3.1. Понятие алгебраической системы................................................................86
3.2. Группоиды и полугруппы..............................................................................86
3.3. Понятие группы............................................................................................89
3.4. Кольца, тела и поля.......................................................................................91
3.5. Гомоморфизм и изоморфизм........................................................................93
Контрольные вопросы.........................................................................................93
Упражнения.........................................................................................................94
Литература...........................................................................................................94
Глава 4
Элементы математической логики
4.1. Общие сведения о математической логике..................................................95
4.2. Понятие простого и сложного высказывания..............................................96
4.3. Булевы функции...........................................................................................98
4.4. Свойства булевых функций........................................................................100
4.5. Классы булевых функций...........................................................................102
4.6. Функционально полные системы...............................................................105
4.7. Дизъюнктивная нормальная форма...........................................................108
4.8. Конъюнктивная нормальная форма...........................................................109
4.9. Полиномиальные представления...............................................................111
4.10. Способы задания булевых функций.........................................................112
4.11. Задача ВЫПОЛНИМОСТЬ......................................................................ИЗ
4.12. Предикаты.................................................................................................114
4.13. Построение математических моделей......................................................115
4.13.1. Пример 1. Схема управления освещением.....................................113
4.13.2. Пример 2. Сумматор последовательного действия........................117
4.13.3. Пример 3.' Логическая модель гамильтоновости графа..................118
4.14. Реализация математических моделей.......................................................123
Контрольные вопросы.......................................................................................125
Упражнения.......................................................................................................126
Литература.........................................................................................................127
Глава 5
Минимизация булевых функций
5.1. Задача минимизации булевых функций.....................................................128
5.2. Постановка задачи минимизации в классе ДНФ.......................................131
5.3. Сокращенная ДНФ.....................................................................................133
5.4. Тупиковые ДНФ..........................................................................................135
5.5. Построение сокращенной ДНФ.................................................................137
5.5.1. Геометрический метод.......................................................................137
5.5.2. Метод Квайна-Мак-Класки.............................................................139
5.5.3. Метод Блейка....................................................................................142
5.6. Поиск минимальных ДНФ.........................................................................143
Контрольные вопросы.......................................................................................146
Упражнения.......................................................................................................146
Литература.........................................................................................................147
Глава 6
Элементы комбинаторики
6.1. предмет комбинаторики.............................................................................148
6.2. Понятие выборки........................................................................................149
6.3. Основные правила комбинаторики............................................................150
6.4. Пересчет упорядоченных выборок.............................................................151
6.4.1. Число упорядоченных выборок с повторениями.............................151
6.4.2. Число упорядоченных выборок без повторений...............................152
6.5. Порождение перестановок..........................................................................153
6.5.1. Представление перестановок............................................................154
6.5.2. Методы генерирования перестановок..............................................155
6.6. Пересчет числа неупорядоченных выборок...............................................166
6.6.1. Число неупорядоченных выборок без повторений..........................166
6.6.2. Число неупорядоченных выборок с повторением...........................168
6.7. Порождение подмножеств..........................................................................170
6.7.1. Представление подмножеств............................................................170
6.7.2. Генерирование всех подмножеств.....................................................171
6.7.3. Генерирование г-элементных подмножеств.....................................174
6.7.4. Генерирование подмножеств с повторениями.................................177
6.8. Число разбиений множества на подмножества..........................................177
6.9. Генерирование разбиений множеств и чисел.............................................179
6.9.1. Генерирование разбиений множества...............................................179
6.9.2. Генерирование разбиений числа.......................................................180
6.10. Метод включений и исключений.............................................................182
6.11. Метод рекуррентных соотношений..........................................................185
6.12. Решение линейных рекуррентных соотношений.....................................188
6.13. Понятие производящей функции.............................................................191
6.14. Свойства биномиальных коэффициентов................................................194
Контрольные вопросы.......................................................................................196
Упражнения.......................................................................................................197
Литература.........................................................................................................198
Глава 7
Элементы теории алгоритмов
7.1. Предмет теории алгоритмов.......................................................................199
7.2. Интуитивное понятие алгоритма................................................................199
7.3. Примитивно-рекурсивные функции..........................................................201
7.4. Машина Тьюринга......................................................................................205
7.5. Композиция машин Тьюринга...................................................................210
7.6. Алгоритмически неразрешимые проблемы................................................211
7.7. Понятие сложности алгоритма...................................................................212
7.8. Асимптотические оценки функций сложности.........................................214
7.9. Трудноразрешимые задачи..........................................................................218
7.10. Класс NP....................................................................................................220
7.11. NP-полные задачи.....................................................................................222
7.12. Пример полиномиального сведения........................................................224
7.12.1. Постановка задачи...........................................................................224
7.12.2. Графовая модель задачи минимизации...........................................227
7.13. Приближенные алгоритмы.......................................................................230
Контрольные вопросы.......................................................................................232
Упражнения.......................................................................................................233
Литература.........................................................................................................234
Глава 8
О разрешимости конструктивных комбинаторных задач
8.1. Введение......................................................................................................236
8.2. Последовательностный принцип построения решения............................238
8.3. Теоретико-множественная модель комбинаторных задач.........................240
8.4. Один пример комбинаторной задачи.........................................................242
8.5. Задачи без предвидения..............................................................................247
8.6. Разрешающая последовательность комбинаторных задач........................250
8.7. К методике решения задач класса NP........................................................254
8.8. О недетерминированной машине Тьюринга..............................................255
8.9. Заключение.................................................................................................256
Литература.........................................................................................................257
