Плотников А.Д. Дискретная математика ОНЛАЙН

Плотников А.Д. Дискретная математика: учеб. пособие /А.Д. Плотников. — М.: Новое знание, 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

Поделиться ссылкой:
  • Добавить ВКонтакте заметку об этой странице
  • Мой Мир
  • Facebook
  • Twitter
  • LiveJournal
  • В закладки Google
  • Яндекс.Закладки
  • Сто закладок
  • Blogger
  • Блог Li.ру
  • Блог Я.ру
  • Одноклассники
  • RSS

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Наш сайт находят по фразам:

×