 |
Дискретная математика для программистов
Род Хаггарти
Год выпуска: 2018
ISBN: 978-5-94836-303-5
Переплёт: твердый
400 страниц
Цена: 416.00 грн.
|
"Дискретная математика для программистов" - основополагающее введение в дискретную математику, без знания которой невозможно успешно заниматься информатикой и программированием. Ни одно из многочисленных изданий по этой дисциплине, вышедших на русском языке, не читается с таким удовольствием и пользой. В доступной и весьма увлекательной форме автор рассказывает о фундаментальных понятиях дискретной математики – о логике, множествах, графах, отношениях и булевых функциях. Теория изложена кратко и иллюстрируется многочисленными простыми примерами, что делает ее доступной даже школьнику. После каждой главы (начиная со второй) рассматривается приложение описанных методов к информатике.
Дополнения в издании на русском языке посвящены актуальным задачам теории графов, рекурсивным алгоритмам, общей проблеме перебора и задачам целочисленного программирования.
Книга будет полезна студентам, изучающим курс дискретной математики, а также всем желающим проникнуть в технику написания и проверки корректности алгоритмов, включая программистов-практиков.
Содержание книги Род Хаггарти "Дискретная математика для программистов"
Указатель обозначений.........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
|