Указатель обозначений.........6
Предисловие.......................9
Глава 1.
Введение...........................11
1.1. Моделирование.............11
1.2. Псевдокод.....................14
Набор упражнений 1..............19
Краткое содержание главы......21
Глава 2.
Логика и доказательство.........23
2.1. Высказывания и логика.....23
2.2. Предикаты и кванторы.......27
2.3. Методы доказательств........30
2.4. Математическая индукция....32
Набор упражнений 2..................35
Краткое содержание главы.........38
Приложение: Корректность алгоритмов....39
Глава 3.
Теория множеств.........................44
3.1. Множества и операции над ними........44
3.2. Алгебра множеств............................51
3.3. Дальнейшие свойства множеств..........53
Набор упражнений 3................................58
Краткое содержание главы........................61
Приложение: Система с базой знаний..........63
Глава 4.
Отношения............................................68
4.1. Бинарные отношения..........................68
4.2. Свойства отношений
4.3. Отношения эквивалентности и частичного порядка....77
Набор упражнений 4...................................82
Краткое содержание главы...........................85
Приложение: Системы управления базами данных...........86
Глава 5.
5. Функции...............................................................91
5.1. Обратные отношения и композиция отношений..........91
5.2. Функции...............................................................96
5.3. Обратные функции и композиция функций................102
5.4. Принцип Дирихле...................................................105
Набор упражнений 5......................................................108
Краткое содержание главы..............................................112
Приложение: Языки функционального программирования.....113
Глава 6
Комбинаторика................................................................117
6.1. Правила суммы и произведения....................................117
6.2. Формулы для вычислений.............................................120
6.3. Бином Ньютона...........................................................128
Набор упражнений 6..........................................................131
Краткое содержание главы..............................................135
Приложение. Эффективность алгоритмов............................136
Глава 7.
Графы........................................................................141
7.1. Графы и терминология.............................................142
7.2. Гамильтоновы графы.............................................147
7.3. Деревья..................................................................152
Набор упражнений 7....................................................158
Краткое содержание главы.............................................163
Приложение. Сортировка и поиск...................................165
Глава 8.
8.1. Ориентированные графы.....................................................171
8.2. Пути в орграфах..............................................................175
8.3. Кратчайший путь................................................................181
Набор упражнений 8..................................................................184
Краткое содержание главы.........................................................187
Приложение: Коммуникационные сети...........................................189
Глава 9
9.1. Булева алгебра..............................................................194
9.2. Карта Карно..................................................................200
9.3. Функциональные схемы.............................................205
Набор упражнений 9........................................................208
Краткое содержание главы................................................211
Приложение. Проектирование 2-битного сумматора.................212
Решения упражнений...........................................................217
Дополнение к первому изданию............................................275
Д.1. генератор случайных графов...........................................275
Д.1.1. Алгоритм построения случайного неориентированного графа...277
Д.1.2. Алгоритм построения случайного ориентированного графа...278
Д.1.3. Алгоритм построения случайного неориентированного
бесконтурногографа....................................................................279
Д.2. Связность в графах...............................................................281
Д.2.1. Алгоритм Уоршелла, вычисляющий матрицу связности............282
Д.2.2. Выделение компонент связности.........................................286
Д.3. Эйлеровы циклы...................................................................288
Д.3.1. Алгоритм построения эйлерова цикла в графе.........................289
Д.3.2. Алгоритм Терри...................................................................292
Д.4. Операции над множествами......................................................294
Д.4.1. Объединение множеств.........................................................300
Дополнение ко второму изданию......................................................305
Предисловие..................................................................................305
Д.5. Дополнительные главы дискретной математики..............................305
Введение........................................................................................305
Д.5.1. Исчисление и оценка конечных сумм..........................................306
Набор упражнений Д.5.1.......................................................................317
Д.5.2. Элементы теории рекурсии.........................................................318
Набор упражнений Д.5.2...................................................................332
Д.5.3. Конечные разности. Разностный и суммирующий операторы..........333
Набор упражнений Д.5.3.....................................................................344
Д.5.4. Производящие функции и комбинаторные подсчеты.......................345
Набор упражнений Д,5.4......................................................................359
Д.6. Общая проблема перебора и некоторые точные методы решения задач целочисленного программирования........................................................359
Введение............................................................................................359
Д.6.1. Понятие m -мерного евклидова целочисленного пространства.......................................................................................361
Д.6.2. Общая постановка, типизация и примеры задач целочисленного программирования..................................................................................362
Д.6.3. NP -полные задачи и проблема перебора...........................................366
Д.6.4. Обзор точных методов решения задач целочисленного программирования..368
Д.6.5. Точное решение задачи одномерной упаковки методом динамического программирования.....................................................................................372
Д.6.6. Метод ветвей и границ и задача коммивояжера....................................381
Набор упражнений Д.6................................................................................392
Литература............................................................................................395
Предметный указатель.............................................................................397