Дискретна математика

Передмова ......Page 8
1.1. Логіка висловлювань ......Page 10
1.2. Закони логіки висловлювань ......Page 16
1.3. Нормальні форми логіки висловлювань ......Page 18
1.4. Логіка першого ступеня ......Page 20
1.5. Закони логіки першого ступеня ......Page 24
1.6. Випереджена нормальна форма ......Page 26
1.7. Логічне виведення в логіці висловлювань ......Page 27
1.8. Застосування правил виведення в логіці висловлювань ......Page 29
1.9. Метод резолюцій ......Page 31
1.10. Правила виведення в численні предикатів ......Page 33
1.11. Методи доведення теорем ......Page 35
1.12. Множина. Кортеж. Декартів добуток ......Page 36
1.13. Операції над множинами. Доведення рівностей з множинами ......Page 38
1.14. Комп\'ютерне подання множин ......Page 40
Контрольні запитання та завдання ......Page 41
Комп\'ютерні проекти ......Page 48
2.1. Основні правила комбінаторного аналізу. Розміщення та сполучення ......Page 49
2.2. Обчислення кількості розміщень і сполучень ......Page 51
2.3. Перестановки ......Page 52
2.4. Біном Ньютона ......Page 54
2.5. Поліноміальна теорема ......Page 56
2.7. Числа Стірлінга другого роду та числа Белла ......Page 57
2.8. Генерування перестановок ......Page 58
2.9. Генерування сполучень ......Page 60
2.10. Генерування розбиттів множини ......Page 62
2.11. Рекурентні рівняння ......Page 63
2.12. Розв\'язування рекурентних рівнянь ......Page 64
2.13. Принцип коробок Діріхле ......Page 69
2.14. Принцип включення-виключення ......Page 70
2.15. Принцип включення-виключення в альтернативній формі ......Page 71
2.16. Твірні функції ......Page 72
Контрольні запитання та завдання ......Page 83
Комп\'ютерні проекти ......Page 88
3.1. Основні означення та властивості ......Page 89
3.2. Деякі спеціальні класи простих графів ......Page 95
3.3. Способи подання графів ......Page 96
3.4. Шляхи та цикли. Зв\'язність ......Page 101
3.5. Ізоморфізм графів ......Page 106
3.6. Ейлерів цикл у графі ......Page 109
3.7. Гамільтонів цикл у графі ......Page 112
3.8. Зважені графи й алгоритми пошуку наикоротших шляхів ......Page 114
3.9. Обхід графів ......Page 121
3.10. Планарні графи ......Page 125
3.11. Розфарбовування графів ......Page 127
3.12. Незалежні множини вершин. Кліки ......Page 131
3.13. Паросполучення в графах. Теорема Холла ......Page 133
3.14. Найбільше паросполучення у дводольних графах ......Page 135
Контрольні запитання та завдання ......Page 139
Комп\'ютерні проекти ......Page 149
4.1. Основні означення та властивості ......Page 151
4.2. Рекурсія. Обхід дерев. Префіксна та постфіксна форми запису виразів ......Page 155
4.3. Бінарне дерево пошуку ......Page 161
4.4. Дерево прийняття рішень ......Page 164
4.5. Бектрекінг (пошук із поверненнями) ......Page 171
4.6. Каркаси (з\'єднувальні дерева) ......Page 176
Контрольні запитання та завдання ......Page 178
Комп\'ютерні проекти ......Page 183
5.1. Відношення та їх властивості ......Page 186
5.2. Відношення еквівалентності ......Page 189
5.3. Відношення часткового порядку ......Page 191
5.4. Топологічне сортування ......Page 193
5.5. Операції над відношеннями ......Page 196
5.6. Замикання відношень ......Page 198
5.7. Бази даних і відношення ......Page 203
Контрольні запитання та завдання ......Page 205
Комп\'ютерні проекти ......Page 214
6.1. Алфавітне й рівномірне кодування ......Page 216
6.2. Достатні умови однозначності декодування. Властивості роздільних кодів ......Page 217
6.3. Оптимальне кодування ......Page 221
6.4. Коди, стійкі до перешкод. Коди Хеммінга ......Page 227
Контрольні запитання та завдання ......Page 233
Комп\'ютерні проекти ......Page 235
7.1. Означення булевої функції. Реалізація функцій формулами ......Page 236
7.2. Алгебри булевих функцій ......Page 241
7.3. Спеціальні форми подання булевих функцій ......Page 244
7.4. Повнота й замкненість ......Page 251
7.5. Мінімізація булевих функцій ......Page 258
7.6. Реалізація булевих функцій схемами з функціональних елементів ......Page 268
Контрольні запитання та завдання ......Page 273
Комп\'ютерні проекти ......Page 276
8.1. Мови ......Page 277
8.2. Формальні породжувальні граматики ......Page 279
8.3. Типи граматик (ієрархія Хомскі) ......Page 282
8.4. Дерева виведення ......Page 284
8.5. Форми Бекуса-Наура ......Page 285
8.6. Скінченні автомати з виходом ......Page 286
8.7. Скінченні автомати без виходу ......Page 290
8.8. Подання мов ......Page 295
Контрольні запитання та завдання ......Page 304
Комп\'ютерні проекти ......Page 311
9.1. Основні вимоги до алгоритмів ......Page 313
9.2. Машини Тьюрінга ......Page 315
9.3. Обчислення числових функцій на машинах Тьюрінга ......Page 320
9.4. Теза Тьюрінга. Приклади алгоритмічно нерозв\'язних проблем ......Page 321
9.5. Рекурсивні функції ......Page 324
9.6. Теза Чорча. Зв\'язок рекурсивних функцій із машинами Тьюрінга ......Page 328
Контрольні запитання та завдання ......Page 329
Комп\'ютерний проект ......Page 330
10.1. Масові задачі, алгоритми та складність ......Page 331
10.2. Задачі розпізнавання, мови та кодування ......Page 335
10.3. Детерміновані машини Тьюрінга та клас Ρ ......Page 337
10.4. Недетерміновані машини Тьюрінга та клас NP ......Page 339
10.5. Поліноміальна звідність і NP-повні задачі ......Page 342
10.6. Теорема Кука ......Page 345
10.7. Приклади NP-повних задач. Доведення Л/Р-повноти ......Page 350
Контрольні запитання та завдання ......Page 355
Термінологічний словник ......Page 356
Література ......Page 362
Алфавітний покажчик ......Page 364