Андерсон, Джеймс А. Дискретная математика и комбинаторика. - Пер. с англ. — М., 2004. — 960 с.
Книга представляет собой современный учебник по дискретной математике. Кроме таких разделов, как математическая логика, теория множеств, комбинаторика, теория графов, теория алгоритмов и вычислений, традиционно включаемых в основной курс дискретной математики, она содержит обширные сведения по теории вероятностей, алгебре и теории чисел. Особое внимание уделено теории доказательств. Чтение книги требует некоторой математической культуры, хотя для изучения основных глав достаточно знаний по математике в объеме средней школы. Материал сопровождается многочисленными примерами, в конце каждого раздела приводится большое количество упражнений.Книга адресована в первую очередь преподавателям и студентам технических специальностей. Она будет также полезна тем, кто интересуется дискретной математикой и желает изучить ее самостоятельно.
Содержание
Предисловие 10
1. Таблицы истинности, логика, доказательства 15
1.1. Высказывания и логические связки 15
1.2. Условные высказывания 23
1.3. Эквивалентные высказывания 27
1.4. Аксиоматические системы: умозаключения и доказательства 34
1.5. Полнота в логике высказываний 45
1.6. Карты Карно 50
1.7. Коммутационные схемы 56
2. Теория множеств 67
2.1. Понятие множества 67
2.2. Операции над множествами 71
2.3. Диаграммы Венна 77
2.4. Булевы алгебры 84
2.5. Отношения 90
2.6. Частично упорядоченные множества юз
2.7. Отношения эквивалентности 106
3. Логика, целые числа и доказательства из
3.1. Исчисление предикатов 113
3.2. Основные положения теории доказательств и теории целых чисел 123
3.3. Математическая индукция 129
3.4. Делимость 139
3.5. Простые числа 144
3.6. Сравнения 149
4. Функции и матрицы 150
4.1. Функции 156
4.2. Специальные функции 161
4.3. Матрицы 167
4.4. Мощность 177
4.5. Мощность (продолжение) 178
5. Алгоритмы и рекурсия 184
5.1. Циклы и алгоритмы для матриц 184
5.2. Рекурсивные функции и алгоритмы 188
5.3. Сложность алгоритмов 201
5.4. Алгоритмы сортировки 205
5.5. Префиксная и суффиксная записи 214
5.6. Двоичные и шестнадцатеричные числа 219
5.7. Числа со знаком 231
5.8. Дальнейшее изучение матриц 237
6. Графы, ориентированные графы и деревья 244
6.1. Графы 244
6.2. Ориентированные графы 252
6.3. Деревья 259
6.4. Мгновенное безумие 267
6.5. Пути и циклы Эйлера 270
6.6. Матрицы инцидентности и смежности 278
6.7. Гиперкубы и код Грея 290
7. Теория чисел 298
7.1. Решето Эратосфена 298
7.2. Метод выделения множителей Ферма 300
7.3. Алгоритмы деления и алгоритм Евклида 301
7.4. Цепные дроби 306
7.5. Подходящие дроби 310
8. Комбинаторика и вероятность 311
8.1. Основные комбинаторные принципы 316
8.2. Комбинаторный принцип сложения 324
8.3. Перестановки и сочетания 331
8.4. Формирование перестановок и сочетаний 343
8.5. Введение вероятности 347
8.6. Обобщенные перестановки и сочетания 354
8.7. Перестановки и сочетания с повторением 359
8.8. Принцип клеток 363
8.9. Снова о вероятности 369
8.10. Теорема Байеса 384
8.11. Цепи Маркова 386
9. Алгебраические структуры 392
9.1. Вновь о частично упорядоченных множествах 392
9.2. Полугруппы и полурешетки 397
9.3. Решетки 403
9.4. Группы 409
9.5. Группы и гомоморфизмы 415
10. Некоторые специальные вопросы теории чисел 422
10.1. Целочисленные решения линейных уравнений 422
10.2. Решения сравнений 424
10.3. Китайская теорема об остатках 428
10.4. Свойства функции (/) 433
10.5. Порядок целого числа 439
11. Некоторые специальные вопросы теории рекурсии 448
11.1. Однородные линейные рекуррентные отношения 448
11.2. Неоднородные линейные рекуррентные отношения 460
11.3. Конечные разности 469
11.4. Факториальные многочлены 473
11.5. Суммирование разностей 483
12. Снова о комбинаторных подсчетах 489
12.1. Задачи о размещении 489
12.2. Числа Каталана 495
Часть 1
12.3. Общее включение-исключение и разупорядочения 502
12.4. Ладейные полиномы и запрещенные позиции 509
13. Производящие функции 523
13.1. Определение производящей функции 523
13.2. Производящие функции и рекуррентные отношения 525
13.3. Производящие функции и комбинаторные подсчеты 535
13.4. Разбиения 542
13.5. Экспоненциальные производящие функции 549
14. Некоторые специальные вопросы теории графов 556
14.1. Алгебраические свойства графов 556
14.2. Планарные графы 580
14.3. Раскраска графов 586
14.4. Пути и циклы Гамильтона 600
14.5. Взвешенные графы и алгоритмы поиска кратчайшего пути 611
15. Деревья 624
15.1. Свойства деревьев 624
15.2. Бинарные деревья поиска 631
15.3. Взвешенные деревья 638
15.4. Обход бинарных деревьев 649
15.5. Остовные деревья 658
15.6. Минимальные остовные деревья 682
16. Сети 691
16.1. Сети и потоки 691
16.2. Паросочетание 707
16.3. Сети Петри 716
17. Теория вычислений 725
17.1. Регулярные языки 725
17.2. Автоматы 731
17.3. Грамматики 741
18. Теория кодов 753
18.1. Введение 753
18.2. Порождающие матрицы 757
18.3. Коды Хемминга 767
19. Перечисление цветов 775
19.1. Теорема Бернсайда 775
19.2. Теорема Пойа 781
20. Кольца, области целостности и поля 788
20.1. Кольца и области целостности 788
20.2. Области целостности 797
20.3. Полиномы 801
20.4. Алгебры и полиномы 808
21. Характеры групп и полугрупп 8i9
21.1. Комплексные числа 819
21.2. Характеры групп 820
21.3. Характеры полугрупп 825
22. Приложения теории чисел 829
22.1. Приложение: поиск по образу 829
22.2. Приложение: функции хеширования 837
22.3. Приложение: криптография 843
Литература 850
Ответы к упражнениям 856
Предметно-именной указатель 942
Список обозначений 954
Часть 2
