Дискретна математика : підручник / Ю. В. Нікольський, В. В. Пасічник, Ю. М. Щербина
Мова: українська.Країна: УКРАЇНА.Відомості про видання: 7-е вид. випр. та допов.Вихідні дані: Львів : Магнолія 2006, ЛНУ ім. Івіна Франка, ©2023Опис: 432 с. : іл.ISBN: 978-617-574-266-2; 978-617-10-0782-6.Серія: Комп`ютингПримітки про зміст: ПЕРЕДМОВА НАУКОВОГО РЕДАКТОРА СЕРІЇ ПІДРУЧНИКІВ ТА НАВЧАЛЬНИХ ПОСІБНИКІВ «КОМП’ЮТИНҐ» -- 9 ВСТУПНЕ СЛОВО АВТОРІВ -- 14 РОЗДІЛ 1. ОСНОВИ: ЛОГІКА І МЕТОДИ ДОВЕДЕННЯ, МНОЖИНИ, ФУНКЦІЇ -- 16 1.1. Логіка висловлювань -- 17 1.2. Закони логіки висловлювань -- 22 1.3. Нормальні форми логіки висловлювань -- 24 1.4. Логіка першого порядку -- 25 1.5. Закони логіки першого порядку -- 30 1.6. Випереджена нормальна форма. Алгоритм зведення довільної формули логіки першого порядку до випередженої нормальної форми -- 32 1.7. Логічне виведення в логіці висловлювань -- 33 1.8. Застосування правил виведення в логіці висловлювань -- 35 1.9. Метод резолюцій -- 37 Алгоритм методу резолюцій -- 38 1.10. Правила виведення у численні предикатів -- 40 1.11. Методи доведення теорем -- 41 1.11.1. Пряме доведення -- 41 1.11.2. Доведення від протилежного -- 41 1.11.3. Доведення аналізом випадків -- 42 1.11.4. Доведення еквівалентності -- 42 1.11.5. Теореми існування -- 42 1.11.6. Математична індукція -- 42 1.12. Множина. Кортеж. Декартів добуток -- 43 1.13. Операції над множинами. Доведення рівностей з множинами -- 45 1.14. Комп’ютерне подання множин -- 47 1.15. Функції -- 48 1.16. Зростання функцій. Оцінки складності алгоритмів -- 52 Резюме -- 55 Задачі для самостійного розв’язування -- 57 Комп’ютерні проекти -- 67 РОЗДІЛ 2. КОМБІНАТОРНИЙ АНАЛІЗ -- 68 2.1. Основні правила комбінаторного аналізу. Розміщення та сполучення -- 68 2.2. Обчислення кількості розміщень і сполучень -- 70 2.3. Перестановки -- 71 2.4. Біном Ньютона -- 72 2.5. Поліноміальна теорема -- 74 2.6. Задача про цілочислові розв’язки -- 75 2.7. Числа Стірлінга другого роду та числа Белла -- 76 2.8. Генерування перестановок -- 77 Алгоритм побудови лексикографічно наступної перестановки за перестановкою а1 а2... аn -- 78 Обґрунтування алгоритму -- 78 2.9. Генерування сполучень -- 78 Алгоритм побудови лексикографічно наступного сполучення -- 79 Обґрунтування алгоритму -- 79 2.10. Генерування розбиттів множини -- 80 2.11. Рекурентні рівняння -- 81 2.12. Розв’язування рекурентних рівнянь -- 82 2.13. Принцип коробок Діріхле -- 86 2.14. Принцип включення - виключення -- 87 2.15. Принцип включення - виключення в альтернативній формі -- 88 2.16. Продуктивні функції -- 89 2.16.1. Степеневі ряди та їхні властивості -- 89 2.16.2. Поняття продуктивної функції -- 91 2.16.3. Продуктивні функції для сполучень -- 91 2.16.4. Продуктивні функції для розміщень -- 95 2.16.5.Застосування продуктивних функцій до розв’язування рекурентних рівнянь -- 97 Резюме -- 99 Задачі для самостійного розв’язування -- 101 Комп’ютерні проекти -- 106 РОЗДІЛ 3. ТЕОРІЯ ГРАФІВ -- 107 3.1. Основні означення та властивості -- 107 3.2. Деякі спеціальні класи простих графів -- 112 3.3. Способи подання графів -- 114 3.3.1. Матриця інцидентності -- 114 3.3.2. Матриця суміжності -- 115 3.3.3. Подання графа списком пар (списком ребер) -- 116 3.3.4. Подання графа списками суміжності -- 117 3.4. Шляхи та цикли. Зв’язність -- 118 3.4.1. Головні означення та результати. Термінологія -- 118 3.4.2. Характеристики зв’язності простого графа -- 121 3.4.3. Критерій двочастковості графа -- 123 3.5. Ізоморфізм графів -- 124 3.6. Ейлерів цикл у графі -- 127 Алгоритм Флері побудови ейлерового циклу -- 129 3.7. Гамільтонів цикл у графі -- 130 3.8. Зважені графи та алгоритми пошуку найкоротших шляхів -- 132 3.8.1. Формулювання задач про найкоротші шляхи в графі. Алгоритм Дейкстри -- 132 -- 134 -- 134 3.8.2. Алгоритм Флойда -- 136 -- 137 3.8.3. Порівняння алгоритмів Флойда та Дейкстри -- 140 3.9. Обхід графів -- 140 3.9.1. Пошук углиб у простому зв’язному графі -- 140 -- 140 3.9.2. Пошук ушир у простому зв’язному графі -- 142 -- 142 3.10. Планарні графи -- 144 3.11. Розфарбування графів -- 146 3.11.1. Хроматичне число -- 146 3.11.2. Хроматичні поліноми -- 148 3.11.3. Практичні задачі, які зводяться до розфарбування графів -- 149 3.12. Незалежні множини вершин. Кліки -- 150 3.13. Паросполучення в графах. Теорема Голла -- 152 3.14. Найбільше паросполучення в двочасткових графах -- 154 Резюме -- 157 Задачі для самостійного розв’язування -- 160 Комп’ютерні проекти -- 184 РОЗДІЛ 4. ДЕРЕВА ТА ЇХ ЗАСТОСУВАННЯ -- 186 4.1. Основні означення та властивості -- 186 4.2. Рекурсія. Обхід дерев. Префіксна та постфіксна форми запису виразів -- 191 Алгоритм обходу дерева в прямому порядку - ОПП (корінь) -- 192 Алгоритм обходу дерева у внутрішньому порядку - ОВП (корінь) -- 192 Алгоритм обходу дерева у зворотному порядку - ОЗП (корінь) -- 192 4.3. Бінарне дерево пошуку -- 197 Алгоритм додавання об’єкта в дерево -- 197 Алгоритм пошуку об’єкта в дереві -- 198 4.4. Дерево рішень -- 200 Алгоритм побудови дерева рішень - IDЗ (0, С, А) -- 203 4.5. Бектрекінг (пошук із поверненнями) -- 208 Алгоритм побудови всіх максимальних незалежних множин вершин у простому графі G = (V, Г) -- 212 4.6. Дерева та сортування -- 212 Алгоритм «Бульбашкове сортування» -- 214 Алгоритм «Об’єднання двох списків» -- 216 4.7. Каркаси -- 218 Алгоритм Краскала -- 221 Резюме -- 223 Задачі для самостійного розв’язування -- 225 Комп’ютерні проекти -- 234 РОЗДІЛ 5. ВІДНОШЕННЯ -- 236 5.1. Відношення та їх властивості -- 236 5.2. Відношення еквівалентності -- 239 5.3. Відношення часткового порядку -- 241 5.4. Топологічне сортування -- 243 Алгоритм топологічного сортування -- 244 5.5. Операції над відношеннями -- 246 5.6. Замикання відношень -- 247 Алгоритм Уоршалла -- 251 5.7. Бази даних і відношення -- 252 Резюме -- 255 Задачі для самостійного розв’язування -- 256 Комп’ютерні проекти -- 266 РОЗДІЛ 6. ОСНОВИ ТЕОРІЇ КОДУВАННЯ -- 268 6.1. Алфавітне й рівномірне кодування -- 268 6.2. Достатні умови однозначності декодування. Властивості роздільних кодів -- 269 6.3. Оптимальне кодування -- 272 6.3.1. КодФано -- 272 6.3.2. Код Гаффмана -- 275 6.3.3. Стиснення даних -- 278 6. 4. Коди, стійкі до перешкод -- 279 6.4.1. Одна схема рівномірного двійкового кодування, вплив перешкод і найпростіші способи виявлення помилок -- 279 6.4.2. Один приклад коду Геммінґа -- 281 6.4.3. Кодова віддаль. Необхідні й достатні умови виявлення та виправлення помилок у каналах зв’язку з перешкодами -- 284 6.4.4. Лінійні або групові коди -- 287 Резюме -- 295 Задачі для самостійного розв’язування -- 297 Комп’ютерні проекти -- 301 РОЗДІЛ 7. БУЛЕВІ ФУНКЦІЇ -- 302 7.1. Означення булевої функції. Реалізація функцій формулами -- 302 7.2. Алгебри булевих функцій -- 306 Закони алгебри Буля -- 307 Закони алгебри Жегалкіна -- 307 7.3. Спеціальні форми подання булевих функцій -- 309 7.3.1. Диз’юнктивні нормальні форми -- 309 7.3.2. Кон’юнктивні нормальні форми -- 312 7.3.3. Поліном Жегалкіна -- 313 7.4. Повнота та замкненість -- 315 7.4.1. Функціонально повні системи -- 316 7.4.2. Замкнені класи -- 316 7.4.3. Критерій функціональної повноти системи булевих функцій -- 320 7.4.4. Послаблена функціональна повнота -- 321 7.4.5. Передповні класи -- 322 7.5. Мінімізація булевих функцій -- 323 7.5.1. Головні результати -- 323 7.5.2. Методи побудови скороченої ДНФ -- 324 -- 325 -- 325 7.5.3. Побудова тупикових ДНФ -- 327 -- 328 7.5.4. Властивості скороченої ДНФ -- 329 7.5.5. Метод карт Карно побудови мінімальних ДНФ -- 329 7.6. Реалізація булевих функцій схемами з функціональних елементів -- 333 Резюме -- 338 Задачі для самостійного розв’язування -- 339 Комп’ютерні проекти -- 343 РОЗДІЛ 8. МОВИ, ГРАМАТИКИ ТА АВТОМАТИ -- 344 8.1. Мови -- 344 8.2. Формальні породжувальні граматики -- 346 8.3. Типи граматик (ієрархія Хомського) -- 349 8.4. Дерева виведення -- 350 8.5. Форми Бекуса-Наура -- 352 8.6. Скінченні автомати з виходом -- 353 8.7. Скінченні автомати без виходу -- 357 8.8. Подання мов -- 361 Резюме -- 370 Задачі для самостійного розв’язування -- 372 Комп’ютерні проекти -- 379 РОЗДІЛ 9. ОСНОВИ ТЕОРІЇ АЛГОРИТМІВ -- 380 9.1. Основні вимоги до алгоритмів -- 380 9.2. Машини Тьюрінга -- 382 9.3. Обчислення числових функцій на машинах Тьюрінга -- 387 9.4. Теза Тьюрінга. Приклади алгоритмічно нерозв’язних проблем -- 388 9.5. Рекурсивні функції -- 392 9.6. Теза Чорча. Зв’язок рекурсивних функцій із машинами Тьюрінга -- 396 Резюме -- 396 Задачі для самостійного розв’язування -- 397 Комп’ютерний проект -- 399 РОЗДІЛ 10. КОМБІНАТОРНІ ЗАДАЧІ ТА СКЛАДНІСТЬ ОБЧИСЛЕНЬ -- 400 10.1. Масові задачі, алгоритми й складність -- 400 10.2. Задачі розпізнавання, мови та кодування -- 404 10.3. Детерміновані машини Тьюрінга й клас Р -- 405 10.4. Недетерміновані машини Тьюрінга й клас NP -- 408 10.5. Поліноміальна звідність і NР-повні задачі -- 411 10.6. Теорема Кука -- 414 10.7. Приклади NР-повних задач. Доведення NР-повноти -- 419 Резюме -- 423 Задачі для самостійного розв’язування -- 424 АЛФАВІТНИЙ ПОКАЖЧИК -- 425 ЛІТЕРАТУРА -- 430 Анотація: У підручнику викладено основні поняття та методи дискретної математики. Окрім таких розділів, як математична логіка, теорія множин і відношень, комбінаторний аналіз, теорія графів, основи теорії кодів, теорія булевих функцій, основи теорії формальних мов та алгоритмів, розглянуто також теорію складності обчислень. Виклад матеріалу супроводжується багатьма докладно розібраними прикладами, кожний розділ завершується збірником задач для самостійного розв’язування та списком комп’ютерних проектів для індивідуальних завдань. Ним можуть скористатись аспіранти та викладачі вищих навчальних закладів..Наявність бібліографії/покажчика: Бібліогр.: 430-431 с.. Тип одиниці:
Навчальні видання
Бібліогр.: 430-431 с.
ПЕРЕДМОВА НАУКОВОГО РЕДАКТОРА СЕРІЇ ПІДРУЧНИКІВ ТА НАВЧАЛЬНИХ ПОСІБНИКІВ «КОМП’ЮТИНҐ» 9
ВСТУПНЕ СЛОВО АВТОРІВ 14
РОЗДІЛ 1. ОСНОВИ: ЛОГІКА І МЕТОДИ ДОВЕДЕННЯ, МНОЖИНИ, ФУНКЦІЇ 16 1.1. Логіка висловлювань 17 1.2. Закони логіки висловлювань 22 1.3. Нормальні форми логіки висловлювань 24 1.4. Логіка першого порядку 25 1.5. Закони логіки першого порядку 30 1.6. Випереджена нормальна форма. Алгоритм зведення довільної формули логіки першого порядку до випередженої нормальної форми 32 1.7. Логічне виведення в логіці висловлювань 33 1.8. Застосування правил виведення в логіці висловлювань 35 1.9. Метод резолюцій 37 Алгоритм методу резолюцій 38 1.10. Правила виведення у численні предикатів 40 1.11. Методи доведення теорем 41 1.11.1. Пряме доведення 41 1.11.2. Доведення від протилежного 41 1.11.3. Доведення аналізом випадків 42 1.11.4. Доведення еквівалентності 42 1.11.5. Теореми існування 42 1.11.6. Математична індукція 42 1.12. Множина. Кортеж. Декартів добуток 43 1.13. Операції над множинами. Доведення рівностей з множинами 45 1.14. Комп’ютерне подання множин 47 1.15. Функції 48 1.16. Зростання функцій. Оцінки складності алгоритмів 52 Резюме 55 Задачі для самостійного розв’язування 57 Комп’ютерні проекти 67
РОЗДІЛ 2. КОМБІНАТОРНИЙ АНАЛІЗ 68 2.1. Основні правила комбінаторного аналізу. Розміщення та сполучення 68 2.2. Обчислення кількості розміщень і сполучень 70 2.3. Перестановки 71 2.4. Біном Ньютона 72 2.5. Поліноміальна теорема 74 2.6. Задача про цілочислові розв’язки 75 2.7. Числа Стірлінга другого роду та числа Белла 76 2.8. Генерування перестановок 77 Алгоритм побудови лексикографічно наступної перестановки за перестановкою а1 а2... аn 78 Обґрунтування алгоритму 78 2.9. Генерування сполучень 78 Алгоритм побудови лексикографічно наступного сполучення 79 Обґрунтування алгоритму 79 2.10. Генерування розбиттів множини 80 2.11. Рекурентні рівняння 81 2.12. Розв’язування рекурентних рівнянь 82 2.13. Принцип коробок Діріхле 86 2.14. Принцип включення - виключення 87 2.15. Принцип включення - виключення в альтернативній формі 88 2.16. Продуктивні функції 89 2.16.1. Степеневі ряди та їхні властивості 89 2.16.2. Поняття продуктивної функції 91 2.16.3. Продуктивні функції для сполучень 91 2.16.4. Продуктивні функції для розміщень 95 2.16.5.Застосування продуктивних функцій до розв’язування рекурентних рівнянь 97 Резюме 99 Задачі для самостійного розв’язування 101 Комп’ютерні проекти 106
РОЗДІЛ 3. ТЕОРІЯ ГРАФІВ 107 3.1. Основні означення та властивості 107 3.2. Деякі спеціальні класи простих графів 112 3.3. Способи подання графів 114 3.3.1. Матриця інцидентності 114 3.3.2. Матриця суміжності 115 3.3.3. Подання графа списком пар (списком ребер) 116 3.3.4. Подання графа списками суміжності 117 3.4. Шляхи та цикли. Зв’язність 118 3.4.1. Головні означення та результати. Термінологія 118 3.4.2. Характеристики зв’язності простого графа 121 3.4.3. Критерій двочастковості графа 123 3.5. Ізоморфізм графів 124 3.6. Ейлерів цикл у графі 127 Алгоритм Флері побудови ейлерового циклу 129 3.7. Гамільтонів цикл у графі 130 3.8. Зважені графи та алгоритми пошуку найкоротших шляхів 132 3.8.1. Формулювання задач про найкоротші шляхи в графі. Алгоритм Дейкстри 132 Опис Алгоритму Дейкстри 134 Обґрунтування алгоритму Дейкстри 134 3.8.2. Алгоритм Флойда 136 Опис Алгоритму Флойда 137 3.8.3. Порівняння алгоритмів Флойда та Дейкстри 140 3.9. Обхід графів 140 3.9.1. Пошук углиб у простому зв’язному графі 140 Алгоритм пошуку вглиб у простому зв’язному графі 140 3.9.2. Пошук ушир у простому зв’язному графі 142 Алгоритм пошуку вшир у простому зв’язному графі 142 3.10. Планарні графи 144 3.11. Розфарбування графів 146 3.11.1. Хроматичне число 146 3.11.2. Хроматичні поліноми 148 3.11.3. Практичні задачі, які зводяться до розфарбування графів 149 3.12. Незалежні множини вершин. Кліки 150 3.13. Паросполучення в графах. Теорема Голла 152 3.14. Найбільше паросполучення в двочасткових графах 154 Резюме 157 Задачі для самостійного розв’язування 160 Комп’ютерні проекти 184
РОЗДІЛ 4. ДЕРЕВА ТА ЇХ ЗАСТОСУВАННЯ 186 4.1. Основні означення та властивості 186 4.2. Рекурсія. Обхід дерев. Префіксна та постфіксна форми запису виразів 191 Алгоритм обходу дерева в прямому порядку - ОПП (корінь) 192 Алгоритм обходу дерева у внутрішньому порядку - ОВП (корінь) 192 Алгоритм обходу дерева у зворотному порядку - ОЗП (корінь) 192 4.3. Бінарне дерево пошуку 197 Алгоритм додавання об’єкта в дерево 197 Алгоритм пошуку об’єкта в дереві 198 4.4. Дерево рішень 200 Алгоритм побудови дерева рішень - IDЗ (0, С, А) 203 4.5. Бектрекінг (пошук із поверненнями) 208 Алгоритм побудови всіх максимальних незалежних множин вершин у простому графі G = (V, Г) 212 4.6. Дерева та сортування 212 Алгоритм «Бульбашкове сортування» 214 Алгоритм «Об’єднання двох списків» 216 4.7. Каркаси 218 Алгоритм Краскала 221 Резюме 223 Задачі для самостійного розв’язування 225 Комп’ютерні проекти 234
РОЗДІЛ 5. ВІДНОШЕННЯ 236 5.1. Відношення та їх властивості 236 5.2. Відношення еквівалентності 239 5.3. Відношення часткового порядку 241 5.4. Топологічне сортування 243 Алгоритм топологічного сортування 244 5.5. Операції над відношеннями 246 5.6. Замикання відношень 247 Алгоритм Уоршалла 251 5.7. Бази даних і відношення 252 Резюме 255 Задачі для самостійного розв’язування 256 Комп’ютерні проекти 266
РОЗДІЛ 6. ОСНОВИ ТЕОРІЇ КОДУВАННЯ 268 6.1. Алфавітне й рівномірне кодування 268 6.2. Достатні умови однозначності декодування. Властивості роздільних кодів 269 6.3. Оптимальне кодування 272 6.3.1. КодФано 272 6.3.2. Код Гаффмана 275 6.3.3. Стиснення даних 278 6. 4. Коди, стійкі до перешкод 279 6.4.1. Одна схема рівномірного двійкового кодування, вплив перешкод і найпростіші способи виявлення помилок 279 6.4.2. Один приклад коду Геммінґа 281 6.4.3. Кодова віддаль. Необхідні й достатні умови виявлення та виправлення помилок у каналах зв’язку з перешкодами 284 6.4.4. Лінійні або групові коди 287 Резюме 295 Задачі для самостійного розв’язування 297 Комп’ютерні проекти 301
РОЗДІЛ 7. БУЛЕВІ ФУНКЦІЇ 302 7.1. Означення булевої функції. Реалізація функцій формулами 302 7.2. Алгебри булевих функцій 306 Закони алгебри Буля 307 Закони алгебри Жегалкіна 307 7.3. Спеціальні форми подання булевих функцій 309 7.3.1. Диз’юнктивні нормальні форми 309 7.3.2. Кон’юнктивні нормальні форми 312 7.3.3. Поліном Жегалкіна 313 7.4. Повнота та замкненість 315 7.4.1. Функціонально повні системи 316 7.4.2. Замкнені класи 316 7.4.3. Критерій функціональної повноти системи булевих функцій 320 7.4.4. Послаблена функціональна повнота 321 7.4.5. Передповні класи 322 7.5. Мінімізація булевих функцій 323 7.5.1. Головні результати 323 7.5.2. Методи побудови скороченої ДНФ 324 Алгоритм Куайна 325 Алгоритм Мак-Кпаскі 325 7.5.3. Побудова тупикових ДНФ 327 Алгоритм знаходження всіх тупикових ДНФ 328 7.5.4. Властивості скороченої ДНФ 329 7.5.5. Метод карт Карно побудови мінімальних ДНФ 329 7.6. Реалізація булевих функцій схемами з функціональних елементів 333 Резюме 338 Задачі для самостійного розв’язування 339 Комп’ютерні проекти 343
РОЗДІЛ 8. МОВИ, ГРАМАТИКИ ТА АВТОМАТИ 344 8.1. Мови 344 8.2. Формальні породжувальні граматики 346 8.3. Типи граматик (ієрархія Хомського) 349 8.4. Дерева виведення 350 8.5. Форми Бекуса-Наура 352 8.6. Скінченні автомати з виходом 353 8.7. Скінченні автомати без виходу 357 8.8. Подання мов 361 Резюме 370 Задачі для самостійного розв’язування 372 Комп’ютерні проекти 379
РОЗДІЛ 9. ОСНОВИ ТЕОРІЇ АЛГОРИТМІВ 380 9.1. Основні вимоги до алгоритмів 380 9.2. Машини Тьюрінга 382 9.3. Обчислення числових функцій на машинах Тьюрінга 387 9.4. Теза Тьюрінга. Приклади алгоритмічно нерозв’язних проблем 388 9.5. Рекурсивні функції 392 9.6. Теза Чорча. Зв’язок рекурсивних функцій із машинами Тьюрінга 396 Резюме 396 Задачі для самостійного розв’язування 397 Комп’ютерний проект 399
РОЗДІЛ 10. КОМБІНАТОРНІ ЗАДАЧІ ТА СКЛАДНІСТЬ ОБЧИСЛЕНЬ 400 10.1. Масові задачі, алгоритми й складність 400 10.2. Задачі розпізнавання, мови та кодування 404 10.3. Детерміновані машини Тьюрінга й клас Р 405 10.4. Недетерміновані машини Тьюрінга й клас NP 408 10.5. Поліноміальна звідність і NР-повні задачі 411 10.6. Теорема Кука 414 10.7. Приклади NР-повних задач. Доведення NР-повноти 419 Резюме 423 Задачі для самостійного розв’язування 424
АЛФАВІТНИЙ ПОКАЖЧИК 425
ЛІТЕРАТУРА 430
У підручнику викладено основні поняття та методи дискретної математики. Окрім таких розділів, як математична логіка, теорія множин і відношень, комбінаторний аналіз, теорія графів, основи теорії кодів, теорія булевих функцій, основи теорії формальних мов та алгоритмів, розглянуто також теорію складності обчислень. Виклад матеріалу супроводжується багатьма докладно розібраними прикладами, кожний розділ завершується збірником задач для самостійного розв’язування та списком комп’ютерних проектів для індивідуальних завдань. Ним можуть скористатись аспіранти та викладачі вищих навчальних закладів.
Немає коментарів для цієї одиниці.
Натисніть на зображення, щоб переглянути його в оглядачі зображень