Дискретная математика в задачах

Содержание книги "Дискретная математика в задачах"

Глава 1. Теория множеств
1.0. Введение
1.1. Множество и его элементы
1.2. Универсальное множество и пустое множество
1.3. Подмножества
1.4. Диаграммы Венна
1.5. Операции над множествами
1.6. Фундаментальное произведение множеств
1.7. Классы множеств, степенные множества и разбиения
1.8. Алгебра множеств и двойственность
1.9. Доказательство тождеств с множествами
1.10. Математическая индукция
1.11. Представление множеств формулами
1.12. Многочлены алгебры множеств
1.13. Полные нормальные формы
1.14. Определение минимальных форм
1.15. Представление формул алгебры множеств графами
1.16. Минимизация формул алгебры множеств на графе
1.17. Решенные задачи
Глава 2. Отношения
2.0. Введение
2.1. Декартово произведение множеств
2.2. Отношения
2.3. Представление отношений
2.4. Композиция отношений
2.5. Свойства отношений
2.6. Замыкание свойств
2.7. Отношение эквивалентности
2.8. Отношение частичного порядка
2.9. Решенные задачи
Глава 3. Упорядоченные множества и решетки
3.0. Введение
3.1. Упорядоченные множества
3.2. Диаграммы Хассе
3.3. Супремум и инфимум
3.4. Изоморфизм упорядоченных множеств
3.5. Решетки
3.6. Нижняя грань 0 и верхняя грань I
3.7. Дистрибутивные решетки
3.8. Решенные задачи
Глава 4. Теория графов
4.0. Введение
4.1. Определения
4.2. Подграфы. Изоморфизм и гомеоморфизм графов
4.3. Дополнение графа
4.4. Маршруты, цепи, циклы
4.5. Расстояние в графе
4.6. Двудольные и k-дольные графы
4.7. Операции над графами
4.8. Многомерный куб как произведение графа K2
4.9. Связность графов
4.10. Деревья
4.11. Векторные пространства циклов и разрезов графа
4.12. Представления графов. Матрицы и списки смежности графов
4.13. Покрытия, независимость и паросочетания
4.14. Раскрашивание графов
4.15. Метод Магу для определения доминирующих и независимых подмножеств вершин графа, а также паросочетаний
4.16. Эйлеровы и гамильтоновы графы
4.17. Планарность
4.18. Ориентированные графы
4.19. Решенные задачи
Глава 5. Сети
5.0. Введение
5.1. Алгоритмы построения остовных деревьев
5.2. Алгоритмы поиска кратчайших путей на сети
5.3. Задача коммивояжера
5.4. Потоки в сетях
5.5. Алгоритм Форда – Фалкерсона (алгоритм расстановки меток)
5.6. Решенные задачи
Глава 6. Логика и исчисление высказываний
6.0. Введение
6.1. Высказывания и составные высказывания
6.2. Логические операции
6.3. Таблицы истинности для высказываний
6.4. Тавтологии и контрадикции
6.5. Логическая тождественность
6.6. Условные высказывания
6.7. Алгебра высказываний
6.8. Построение выводов в исчислении высказываний
6.9. Исчисление предикатов
6.10. Решенные задачи
Глава 7. Языки, автоматы, машины Тьюринга
7.0. Введение
7.1. Алфавит и слова
7.2. Языки
7.3. Регулярные выражения и языки
7.4. Конечные автоматы FSA (finite state automata)
7.5. Конечные автоматы FSM (finite state machines)
7.6. Машины Тьюринга
7.7. Решенные задачи
Глава 8. Кодирование в повседневной жизни
8.0. Введение
8.1. Коды Брайля и Морзе
8.2. Контрольные цифры
8.3. Штрих-коды (Bar codes)
8.4. Компьютерные коды
8.5. Решенные задачи
Глава 9. Разностные уравнения
9.0. Введение
9.1. Рекурсии
9.2. Итерации
9.3. Разностные уравнения первого порядка
9.4. Банковские кредиты
9.5. Разностные уравнения второго порядка
9.6. Решенные задачи
Предметный указатель
Литература