Главная » Файлы » Вуз » Дискретная математика

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

Если у вас возникли трудности при выполнении домашнего задания по предмету Дискретная математика, то Дискретная математика Плотников А.Д. поможет вам. С помощью данного решебника вы сможете решить задания Вуз. Книга Дискретная математика Плотников А.Д. позволит вам найти правильное решение онлайн и исправить ошибки.

Уважаемые посетители сайта, если вы не согласны с той информацией которая представлена на данной странице или считаете ее не правильной, не стоит попросту тратить свое время на написание негативных высказываний, вы можете помочь друг другу, для этого присылайте в комментарии свое "правильное" решение и мы его скорее всего опубликуем.

13.11.2015, 13:17

Оглавление
От автора………………………………………………………………………………………………….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

 

 

 


Категория: Дискретная математика | Добавил: Админ | Теги: плотников
Просмотров: | Загрузок: 0 | Рейтинг: 0.0/0
Смотрите также:

Дискретная математика Плотников А.Д. скачать бесплатно

Всего комментариев: 0
avatar