Володимир Пасічник » Дискретна математика
|
[додати інший файл чи обкладинку цього твору]
[додати цей твір до вибраного]
|
Дискретна математика
Підручник
|
|
|
| Написано: |
2007 року |
|
| Розділ: |
Навчальна |
|
| Твір додано: |
21.12.2025 |
|
| Твір змінено: |
21.12.2025 |
|
| Завантажити: |
djvu
(6.1 МБ)
|
|
| Опис: |
Нікольський Ю. В., Пасічник В. В., Щербина Ю. М.
Н64 Дискретна математика. — К.: Видавнича група BHV, 2007. — 368 с.: іл..
ISBN 966-552-201-9
У підручнику в логічній послідовності викладено основні поняття та методи дискретної
математики. Окрім таких розділів, як теорія множин і математична логіка, теорія графів, основи
теорії кодування, теорія булевих функцій, теорія алгоритмів та формальних мов, які
традиційно входять до базового курсу дисципліни, розглянуто також основи теорії складності
обчислень та деякі застосування дискретної математики у штучному інтелекті.
За змістом та обсягом підручник відповідає навчальним планам дисципліни «Дискретна
математика» для студентів базових напрямів «Комп'ютерні науки», «Комп'ютеризовані
системи, автоматика та управління», «Комп'ютерна інженерія» та «Прикладна математика».
|
|
| Зміст: |
[натисніть, щоб розгорнути]
Зміст
Передмова 7
Розділ 1. Основи: логіка та методи доведення, множини 9
1.1. Логіка висловлювань 9
1.2. Закони логіки висловлювань 15
1.3. Нормальні форми логіки висловлювань 17
1.4. Логіка першого ступеня 19
1.5. Закони логіки першого ступеня 23
1.6. Випереджена нормальна форма 25
1.7. Логічне виведення влогіці висловлювань 26
1.8. Застосування правил виведення в логіці висловлювань 28
1.9. Метод резолюцій ЗО
1.10. Правила виведення в численні предикатів 32
1.11. Методи доведення теорем 34
1.12. Множина. Кортеж. Декартів добуток 35
1.13. Операції над множинами. Доведення рівностеи з множинами 37
1.14. Комп'ютерне подання множин 39
Контрольні запитання та завдання 40
Комп'ютерні проекти 47
Розділ 2. Комбінаторний аналіз 48
2.1. Основні правила комбінаторного аналізу.
Розміщення та сполучення 48
2.2. Обчислення кількості розміщень і сполучень 50
2.3. Перестановки 51
2.4. Біном Ньютона 53
2.5. Поліноміальна теорема 55
2.6. Задача про цілочислові розв'язки 56
2.7. Числа Стірлінга другого роду та числа Белла 56
2.8. Генерування перестановок 57
2.9. Генерування сполучень 59
2.10. Генерування розбиттів множини 61
2.11. Рекурентні рівняння 62
2.12. Розв'язування рекурентних рівнянь 63
2.13. Принцип коробок Діріхле 68
2.14. Принцип включення-виключення 69
2.15. Принцип включення-виключення в альтернативній формі 70
2.16. Твірні функції 71
Контрольні запитання та завдання 82
Комп'ютерні проекти 87
Зміст 5
Розділ 3. Теорія графів 88
3.1. Основні означення та властивості 88
3.2. Деякі спеціальні класи простих графів 94
3.3. Способи подання графів 95
3.4. Шляхи та цикли. Зв'язність 100
3.5. Ізоморфізм графів 105
3.6. Ейлерів цикл у графі 108
3.7. Гамільтонів цикл у графі 111
3.8. Зважені графи й алгоритми пошуку наикоротших шляхів 113
3.9. Обхід графів 120
3.10. Планарні графи 124
3.11. Розфарбовування графів 126
3.12. Незалежні множини вершин. Кліки 130
3.13. Паросполучення в графах. Теорема Холла 132
3.14. Найбільше паросполучення у дводольних графах 134
Контрольні запитання та завдання 138
Комп'ютерні проекти 148
Розділ 4. Дерева та їх застосування 150
4.1. Основні означення та властивості 150
4.2. Рекурсія. Обхід дерев. Префіксна та постфіксна форми запису виразів 154
4.3. Бінарне дерево пошуку 160
4.4. Дерево прийняття рішень 163
4.5. Бектрекінг (пошук із поверненнями) 170
4.6. Каркаси (з'єднувальні дерева) 175
Контрольні запитання та завдання 177
Комп'ютерні проекти 182
Розділ 5. Відношення 185
5.1. Відношення та їх властивості 185
5.2. Відношення еквівалентності 188
5.3. Відношення часткового порядку 190
5.4. Топологічне сортування 192
5.5. Операції над відношеннями 195
5.6. Замикання відношень 197
5.7. Бази даних і відношення 202
Контрольні запитання та завдання 204
Комп'ютерні проекти 213
Розділ 6. Основи теорії кодування 215
6.1. Алфавітне й рівномірне кодування 215
6.2. Достатні умови однозначності декодування.
Властивості роздільних кодів 216
6.3. Оптимальне кодування 220
6.4. Коди, стійкі до перешкод. Коди Хеммінга 226
Контрольні запитання та завдання 232
Комп'ютерні проекти 234
6 Зміст
Розділ 7. Булеві функції 235
7.1. Означення булевої функції. Реалізація функцій формулами 235
7.2. Алгебри булевих функцій 240
7.3. Спеціальні форми подання булевих функцій 243
7.4. Повнота й замкненість 250
7.5. Мінімізація булевих функцій 257
7.6. Реалізація булевих функцій схемами з функціональних елементів 267
Контрольні запитання та завдання 272
Комп'ютерні проекти 275
Розділ 8. Мови, граматики й автомати 276
8.1. Мови 276
8.2. Формальні породжувальні граматики 278
8.3. Типи граматик (ієрархія Хомскі) 281
8.4. Дерева виведення 283
8.5. Форми Бекуса-Наура 284
8.6. Скінченні автомати з виходом 285
8.7. Скінченні автомати без виходу 289
8.8. Подання мов 294
Контрольні запитання та завдання 303
Комп'ютерні проекти 310
Розділ 9. Основи теорії алгоритмів 312
9.1. Основні вимоги до алгоритмів 312
9.2. Машини Тьюрінга 314
9.3. Обчислення числових функцій на машинах Тьюрінга 319
9.4. Теза Тьюрінга. Приклади алгоритмічно нерозв'язних проблем 320
9.5. Рекурсивні функції 323
9.6. Теза Чорча. Зв'язок рекурсивних функцій із машинами Тьюрінга 327
Контрольні запитання та завдання 328
Комп'ютерний проект 329
Розділ 10. Комбінаторні задачі та складність обчислень 330
10.1. Масові задачі, алгоритми та складність 330
10.2. Задачі розпізнавання, мови та кодування 334
10.3. Детерміновані машини Тьюрінга та клас Р 336
10.4. Недетерміновані машини Тьюрінга та клас NP 338
10.5. Поліноміальна звідність і Л/Р-повні задачі 341
10.6. Теорема Кука , 344
10.7. Приклади Л/Р-повних задач. Доведення А/Р-повноти : 349
Контрольні запитання та завдання 354
Термінологічний словник 355
Література 361
Алфавітний покажчик 363
|
|
|
|
| |
|
Відгуки читачів:
|
| |
|
Поки не додано жодних відгуків до цього твору.
|
| |
|
|
| |
