Дискретная математика (Хороший учебник по дискретной математике)

Ф. А. Новиков ДЛЯ ПРОГРАММИСТОВ ф систематинеское И ЗЛ 0)КЕН И Е ОСНОВ Н ЫХ РазделоВ дискретнОЙ математики е осноеные способы и Редста Влен ия ОбъектОВ ДискретноЙ математики с помощью ста нда Ртн ых структяэ данных Рецензенты. Кафедра «Прикпаднан математиках Санкт-Петербургского государственного технического университета Лавров С. С., доктор технических наук, профессор, член-корреспондент Российской академии наук Н73 Дискретная математика для программистов ! Ф.

А. Новиков — СПб: Питер, 2000. — 304 с.: ил. 18ВМ 6-272-00183.4 ББК 32.973-018я7+22.174 УДК 681.3.06:81 !078) Эпектронная версия скачана с сайтв йй:81гобожпю.гнгогйег!61ев.йтю 18ВН 6-272-00183-4 о ф. д. новиков, голо о с р, орормленмг, издательский лом «питер», гооо В учебнике изложены основные разделы дискретной математики и описаны важнейшие алгоритмы на дискретных структурах данных. Основу книги составляет матерная лекционного курса, который автор читает в Санкт-Петербургском государственном техническом университете последние полтора десятилетия. Для студентов вузов, практикующих программистов и всех желающих изучить дисхретнуГо математику.

!9 51 79 ...100 ГЛАВА 5. Комбинаторика ГЛАВА 6. Кодирование ГЛАВА 7. Графы ГЛАВА 8. Связность ГЛАВА 9. Деревья ГЛАВА 10. Циклы ГЛАВА 11. Независимость и покрытия ГЛАВА 12. Раскраска графов Литература Алфавитный указатель .159 ...189 ...210 .260 ...289 ...281 ..290 ,.292 Краткое содержание ГЛАВА 1. Множества и отношения ГЛАВА 2. Алгебраические структуры ГЛАВА 3. Булавы функции ГЛАВА 4. Логические исчисления Содержание Вступительное слово Введение 12 13 ГЛАВА 1. Множества и отношения ..

1,1. Множества . 1.1Л. Элементы и множества 1.1.2. Задание множеств 1.1.3. Парадокс Рассела 1.2. Операции над множествами 1.2.1. Сравнение множеств 1.2.2. Операции над множествами . 1.2.3. Разбиения и покрытия 1.3. Алгебра подмно:кеств . 1.3.1. Булеан 1.3.2. Свойства операций над множествами 1.4.

Представление множеств в ЭВМ 1.4.1. Реализация операций нвд подмножествами заданного универсума О 1.4.2. Генерация всех подмножеств универсума................,.... 1.4.3. Алгоритм построения бинарного кода Грея 1.4.4. Представление множеств упорядоченными списками ............ 1.4.5.

Проверка включения слиянием . 1.4.6. Вычисление обьединения слиянием ................,........ 1,4.7. Вычисление пересечения слиянием 1.5. Отношения . 1.5.1. Упорядоченные пары 1.5.2. Прямое произведение множеств 1.5.3. Отношения 1.5.4. Композиция отношений 1.5.5. Степень отношения 1.5.6. Ядра отношения . 1.5.7. Свойства отношений 1.5.8. Представление отношений в ЭВМ 1.6.

Функции 1.6.1. Определения 1.6.2. Инъекция, сюръекция и биекция . 1.6.3. Индуцированная функция 1.6.4. Представление функций в ЭВМ 1.7. Отношения эквивалентности 1 7.1. Определения 19 19 .. 20 .. 21 .. 21 .. 22 .. 22 23 .. 23 .. 24 .. 25 .. 25 .. 27 .. 27 .. 28 .. 29 .. 30 .. 30 .. 32 .. 33 .. 33 .. 33 ..

35 .. 35 .. 36 .. 37 .. 38 .. 38 .. 39 .. 41 .. 41 .. 42 одержание 42 43 44 44 45 45 46 47 47 47 48 48 49 49 ножества 1.7.2. Классы эквивалентности 1.7.3. Фактормножества . 1.7.4. Ядро функции 1.8. Отношения порядка 1.8.1. Определения 1.8.2. Минимальные элементы....................., .. 1.8.3. Алгоритм топологической сортировки 1.8.4. Монотонные функции 1.9.

Замыкание отношений . 1.9.1. Замыкание отношения относительно свойства ....... 1.9.2. Транзитивное и рефлексивное транзитивное замыкания 1.9.3. Алгоритм Уоршзлла Комментарии Упражнения ГЛАВА 2. Алгебраические структуры ..... 2.1. Операции и алгебры 2.1.1. Алгебраические структуры 2.1.2. Замыкания и подалгебры ......... 2.1.3.

Алгебра термов 2.1.4. Система образующих 2.1.5. Свойства операций 2.2. Морфизмы 2.2.1. Гомоморфиэм......,........... 2.2.2. Изоморфиэм 2.3. Алгебры с одной операцией............ 2.3.1. Полугруппы 2.3.2. Моноиды 2.3.3. Группы . 2.4. Алгебры с двумя операциями 2.4.1. Кольца .

2,4.2. Области целостности............ 2.4.3. Поля, 2.5. Векторные пространства 2,5.1. Определения 2.5.2. Свойства нуль-вектора 2.5.3. Линейные коыбинации ........., . 2.5.4. Базис и размерность ............ 2.6. Решетки . 2.6.1. Определения 2.6.2.

Ограниченные решетки 2.6.3. Решетка с дополнением .......... 2.6.4. Частичный порядок в решетке 2.6.5. Булевы алгебры 2.7. Матроиды 2.7.1. Определения .............. 2.7.2. Максимальные независимые подм 2.7.3. Базисы 2.7.4. Ранг 2.7.5. Жвдныа алгоритм............... 2 7 6, ПРимеры матроидов Комментарии Упражнения 51 51 51 52 53 53 54 54 54 55 56 57 58 59 60 61 62 62 63 64 64 65 66 67 67 68 68 69 70 71 71 72 73 73 74 77 77 Содер;канне ГЛАВА 3. Булевы функции 3.1. Элементарные булевы функции 3.1.1. Функции алгебры логики 3.1.2. Существенные и несущественные переменные....

3.1.3. Булавы функции одной переменной ............ 3.1.4. Булевы функции двух переменных 3,2, Формулы 3.2.1. Реализация функций формулами 3,2.2. Равносильные формулы ..................... 3.2.3. Подстановка и замена 3.2.4. Алгебра булевых функций 3,3. Принцип двойственности 3.4. Нормальные формы . 3.4.1. Разложение булевых функций по переменным .... 3.4.2.

Совершенные нормальные формы ........,.... 3.4.3. Построение СДНФ 3.4.4. Алгоритм вычисления значения булевой функции .. 3.4.5. Эквивалентные преобразования ............... 3.5. Эамкнутые классы 3.5.1. Замыкание множества булевых функций 3.5.2. Некоторые замкнутые классы 3.6. Полнота . Комментарии Упражнения ГЛАВА 4. Логические исчисления $.1. Логические связки . 4.1.1. Высказывания 4.1.2. Формулы 4,1.3, Интерпретация 4.1.4.

Логическое следование и логическая эквивалентность . 4.1.5. Подстановки . $.2. Формальные теории . 4.2.1. Определение формальной теории 4.2.2. Выводимость 4.2.3, Интерпретация . 4.2.4. Общезначимость и непротиворечивость.........., . 4.2.5. Полнота, независимость и разрешимость........... $.3. Исчисление высказываний 4.3.1. Классическое определение исчисления высказываний . 4.3.2. Частный случай формулы 4.3.3. Алгоритм унификации 4.3.4. Конотруктивное определение исчисления высказываний 4.3.5. Производные правила вывода 4.3.6. Дедукцил 4.3,7.

Некоторые теоремы теории С 4.3.8. Множество теорем теории С 4.3.9, Другие аксиоматизации исчисления высказываний $.4. Исчисление предикатов 4.4.1. Определения . 4.4.2. Интерпретация 4.4.3. Общезначимость 4.4.4. Полнота чистого исчисления предикатов . 79 . 79 . 79 . 80 . 81 . 81 . 81 82 . 84 . 85 . 86 . 88 . 88 . 89 . 90 . 91 . 92 94 . 94 . 96 . 98 . 98 ..100 ..101 ..101 .,! 01 ..102 ..103 ..

104 .. 105 ..105 .. 106 ., 106 , .107 ..107 ..108 ..108 ..109 , .109 ..110 ..111 ..112 ..114 ..116 ..118 ..118 ..119 ..121 ..122 ..122 Содержание 123 123 124 124 126 127 127 128 128 130 131 131 .132 .133 . 133 своих переменных ящих от всех ффициентов 4.4.5. Логическое следование и логическая зквивалентность 4.4.6, Теория равенства . 4.4.7. Формальная арифметика 4.4.8. Теория (абелееых) групп 4,4.9. Теоремы Геделя о неполноте 4.5. Автоматическое доказательство теорем ....,.....,,.... 4.5.1. Постановка задачи .

4.5.2. Доказательство от противного 4.5.3. Сведение к предложениям 4.5.4. Правило резолюции для исчисления высказываний 4.5.5. Правило резолюции для исчисления предикатов 4.5.6. Опровержение методом резолюций .........,.... 4.5.7. Алгоритм метода резолюций Комментарии Упражнения ГЛАВА 5. Комбинаторика 5.1. Комбинаторные конфигурации 5.1.1. Комбинаторные задачи . 5.1.2.

Размещения . 5.1.3. Размещения без повторений 5.1.4. Перестановки..........,....,..., . 5.1.5. Сочетания 5.1.6. Сочетания с повторениями 5.2. Подстановки 5.2.1. Группа подстановок 5.2.2. Графическое представление подстановок 5.2.3. Циклы 5.2.4. Подстановки и перестановки 5.2.5. Инверсии . 5.2.6. Генерация перестановок . 5.3. Биномиальные коэффициенты 5.3.1. Элементарные тождества . 5.3.2.

Бином Ньютона 5.3.3. Свойства биномиальных козффициентов 5.3.4. Треугольник Паскаля 5.3.5. Генерация подмножеств . 5.4. Разбиения 5.4.1. Определения 5.4.2. Числа Стирлинга второго рода 5.4.3. Числа Стирлинга первого рода 5.4.4. Число Белла .

5.5. Принцип включения и исключения 5.5.1. Обьединение конфигураций . 5.5.2. Принцип включения и исключения 5.5.3. Число булевых функций, существенно завис 5.6. Формулы обращения 5.6.1. Теорема обращения 5.6.2: Формулы обращения для биномиальных коз 5.6.3. Формулы для чисел Стирлинга . 5.7. Производящие функции . 5.7.1. Основная идея . 5.7.2. Метод неопРеделенных коэффициентов . 134 135 135 135 136 136 137 138 138 139 140 140 141 141 142 144 144 145 .146 146 . 147 .

148 .148 .149 .150 .150 .151 .151 .152 .153 .153 .153 .154 .155 .156 .156 .157 Содержание 157 157 (омментарии Упрюкнения ГЛАВА 6. Кодирование 5.1. Алфавитное кодирование 6.1.1. Префикс и постфикс слова 6.1.2. Таблица кодов 6,1.3. Разделимые схемы...,... 6.1.4. Префиксные схемы 6.1.5. Неравенство Макмиллана..........,..., .. 8.2. Кодирование с минимальной избыточностью ....,..., 6.2.1. Минимизация длины кода сообщения..........

6.2.2. Цена кодирования 6.2.3. Алгоритм Фано . 6.2.4. Оптимальное кодирование .................. 6.2.5. Алгоритм Хаффмена 8.3. Помехоустойчивое кодирование.................,, 6.3.1. Кодирование с исправлением ошибок 6.3.2. Классификация ошибок 6.3.3. Возможность исправления всех ошибок ........ 6.3.4.

Кодовое расстояние . 6.3.5. Код Хзмминга для исправления одного замещения $.4, Сжатие данных 6.4.1. Сжатие текстов 6.4.2, Предварительное построение словаря ......... 6.4.3. Алгоритм дамаева — Зива 3.5. Шифрование 6.5,1. Криптография 6.5.2. Шифрование с помощью случайных чисел 6.5.3. Криптостойкость 6.5.4. Модулярная арифметика 6.5.5. Шифрование с сткрытыы ключом 6.5.6. Цифровая подпись (омментарии Гпражнения ЛАВА 7.

Графы ..............., .. '.1. Определения графов 7.1,1. История теории графов . 7.1.2. Основное определение 7.1.3. Смежность 7.1.4. Диаграммы 7.1.5. Другие определения . 7.1.6. Изоморфизм графов 02. Элементы графов . 7.2.1. Подграфы 7.2.2. Валентность 7.2.3. Маршруты, цепи, циклы 7.2.4. Расстояние между вершинами . 7.2.5. Связность '.3.

Виды графов и операции над графами 7.3.1. Тривиальные и полные графы .. 7.3.2, Двудольные графы .159 . 161 .161 .161 .! 62 . 162 .163 .165 .165 .166 .167 .168 .170 .172 .Ч72 .173 .173 .174 .175 П77 .177 .178 . 179 . 180 .181 .181 .182 .183 .185 .187 .188 .188 , .189 ..189 ..190 ..191 ..191 ..192 .. Ч92 ..193 ..194 ..194 ..194 ..!95 ..196 ..197 ..197 ..!97 ..197 одержание 7.3.3. Направленные орграфы и сети . 7.3.4. Операции над графами П4.