Хаггарти Р. Дискретная математика для программистов. - 2-е изд. дополненное. - М., 2005. - 400с. Мир программирования
Элементарное введение в дискретную математику. Ни одно из немногочисленных изданий по этой дисциплине, вышедших на русском языке, не читается с таким удовольствием и пользой. В доступной и весьма увлекательной форме автор рассказывает о фундаментальных понятиях дискретной математики - о логике, множествах, графах, отношениях и булевых функциях. Теория изложена кратко и иллюстрируется многочисленными простыми примерами, что делает её доступной даже школьнику. После каждой главы (начиная со второй) рассматривается приложение описанных методов к информатике.Книга будет полезна студентам, изучающим курс дискретной математики, а также всем желающим проникнуть в технику написания и проверки корректности алгоритмов, включая программистов-практиков.
Содержание
Указатель обозначений................................................7
Предисловие.........................................................................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. Свойства отношений................................................73
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.
Ориентированные графы............................................ 171
8.1. Ориентированные графы............................................... 171
8.2. Пути в орграфах.......................................................... 175
8.3. Кратчайший путь......................................................... 181
Набор упражнений 8........................................................... 184
Краткое содержание главы.................................................. 187
Приложение. Коммуникационные сети.................................. 189
Глава 9.
Булева алгебра............................................................. 194
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
Д.З. Эйлеровы циклы......................................................... 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. Понятие т-мерного евклидова целочисленного пространства ................................ 361
д.6.2. Общая постановка, типизация и примеры задач целочисленного программирования............. 362
Д.6.3. NP-полные задачи и проблема перебора................... 366
Д.6.4. Обзор точных методов решения задач целочисленного программирования.................... 368
Д.6.5. Точное рещение задачи одномерной упаковки методом динамического программирования.......... 372
Д.6.6. Метод ветвей и границ и задача коммивояжера........ 381
Набор упражнений Д.6...........................................392
Литература...................................................................395
Предметный указатель................................................397
