Local cover image
Local cover image

Дискретна математика : підручник / Ю. В. Нікольський, В. В. Пасічник, Ю. М. Щербина

Main Author: Автор, Нікольський, Ю. В., (1953-2013), Юрій ВолодимировичCoauthor: Автор, Пасічник, В. В., 1956-, Володимир Володимирович; Автор, Щербина, Ю. М., Юрій МиколайовичLanguage: українська.Country: УКРАЇНА.Edition Statement: 7-е вид. випр. та допов.Publication: Львів : Магнолія 2006, ЛНУ ім. Івіна Франка, ©2023Description: 432 с. : іл.ISBN: 978-617-574-266-2; 978-617-10-0782-6.Series: Комп`ютингContents note: ПЕРЕДМОВА НАУКОВОГО РЕДАКТОРА СЕРІЇ ПІДРУЧНИКІВ ТА НАВЧАЛЬНИХ ПОСІБНИКІВ «КОМП’ЮТИНҐ» -- 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 Abstract: У підручнику викладено основні поняття та методи дискретної математики. Окрім таких розділів, як математична логіка, теорія множин і відношень, комбінаторний аналіз, теорія графів, основи теорії кодів, теорія булевих функцій, основи теорії формальних мов та алгоритмів, розглянуто також теорію складності обчислень. Виклад матеріалу супроводжується багатьма докладно розібраними прикладами, кожний розділ завершується збірником задач для самостійного розв’язування та списком комп’ютерних проектів для індивідуальних завдань. Ним можуть скористатись аспіранти та викладачі вищих навчальних закладів..Bibliography: Бібліогр.: 430-431 с.. Item type: Навчальні видання
Tags from this library: No tags from this library for this title. Log in to add tags.
Star ratings
    Average rating: 0.0 (0 votes)
Holdings
Current library Call number Status Date due Barcode
Бібліотека Українського Гуманітарного Інституту Науковий фонд 517-519.2(075.8) / Н64 (Browse shelf(Opens below)) Available 41683-011936
Бібліотека Українського Гуманітарного Інституту Науковий фонд 517-519.2(075.8) / Н64 (Browse shelf(Opens below)) Available 41683-011937
Бібліотека Українського Гуманітарного Інституту Науковий фонд 517-519.2(075.8) / Н64 (Browse shelf(Opens below)) Available 41683-011934
Бібліотека Українського Гуманітарного Інституту Науковий фонд 517-519.2(075.8) / Н64 (Browse shelf(Opens below)) Available 41683-011935
Бібліотека Українського Гуманітарного Інституту Науковий фонд 517-519.2(075.8) / Н64 (Browse shelf(Opens below)) Available 41683-011932
Бібліотека Українського Гуманітарного Інституту Науковий фонд 517-519.2(075.8) / Н64 (Browse shelf(Opens below)) Available 41683-011933
Бібліотека Українського Гуманітарного Інституту Науковий фонд 517-519.2(075.8) / Н64 (Browse shelf(Opens below)) Available 41683-011930
Бібліотека Українського Гуманітарного Інституту Науковий фонд 517-519.2(075.8) / Н64 (Browse shelf(Opens below)) Checked out 31.08.2024 41683-011931
Бібліотека Українського Гуманітарного Інституту Науковий фонд 517-519.2(075.8) / Н64 (Browse shelf(Opens below)) Available 41683-011928
Бібліотека Українського Гуманітарного Інституту Науковий фонд 517-519.2(075.8) / Н64 (Browse shelf(Opens below)) Checked out 31.08.2024 41683-011929

Бібліогр.: 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

У підручнику викладено основні поняття та методи дискретної математики. Окрім таких розділів, як математична логіка, теорія множин і відношень, комбінаторний аналіз, теорія графів, основи теорії кодів, теорія булевих функцій, основи теорії формальних мов та алгоритмів, розглянуто також теорію складності обчислень. Виклад матеріалу супроводжується багатьма докладно розібраними прикладами, кожний розділ завершується збірником задач для самостійного розв’язування та списком комп’ютерних проектів для індивідуальних завдань. Ним можуть скористатись аспіранти та викладачі вищих навчальних закладів.

There are no comments on this title.

to post a comment.

Click on an image to view it in the image viewer

Local cover image

Powered by Koha