"Дискретная математика для программистов" - основополагающее введение в дискретную математику, без знания которой невозможно успешно заниматься информатикой и программированием. Ни одно из многочисленных изданий по этой дисциплине, вышедших на русском языке, не читается с таким удовольствием и пользой. В доступной и весьма увлекательной форме автор рассказывает о фундаментальных понятиях дискретной математики – о логике, множествах, графах, отношениях и булевых функциях. Теория изложена кратко и иллюстрируется многочисленными простыми примерами, что делает ее доступной даже школьнику. После каждой главы (начиная со второй) рассматривается приложение описанных методов к информатике.
Дополнения в издании на русском языке посвящены актуальным задачам теории графов, рекурсивным алгоритмам, общей проблеме перебора и задачам целочисленного программирования.
Книга будет полезна студентам, изучающим курс дискретной математики, а также всем желающим проникнуть в технику написания и проверки корректности алгоритмов, включая программистов-практиков.


Содержание книги Род Хаггарти "Дискретная математика для программистов"



Указатель обозначений.........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. Функции...............................................................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