Дискретна математика: практикум : ( збірник задач здискретної математики) навчальний посібник ; В. А. Висоцька, В. В. Литвин, О. В. Лозинська

Coauthor: Автор, Висоцька, В. А., Вікторія Анатолієвна; Автор, Литвин , В. В., Василь Володимирович; Автор, Лозинська, О. В., Ольга ВолодимирівнаLanguage: українська.Country: УКРАЇНА.Publication: Львів : Новий Світ - 2000, 2023Description: 576 с. : іл.ISBN: 978-617-7519-29-3.Contents note: Вступ -- 8 Розділ 1 Множини та операції над ними -- 15 1.1. Множина Кортеж. Декартів добуток -- 15 1.2. Операції над множинами -- 18 1.3. Взаємно однозначна відповідність -- 21 1.4. Комп'ютерне подання множин -- 21 1.5. Еквівалентність та потужність множин -- 30 1.6. Тестові завдання для самоконтролю -- 35 1.7. Ключ до тестових завдань -- 37 1.8. Індивідуальні завдання для виконання лабораторної роботи -- 37 1.9. Комп’ютерний проект -- 39 1.10. Додаткові завдання для самостійної роботи -- 39 1.11. Контрольні запитання -- 42 Розділ 2. Логіка висловлювань та логіка першого ступеня -- 43 2.1. Логіка висловлювань та логіка першого ступеня -- 43 2.2. Закони логіки висловлень -- 48 2.3. Загальнозначущість та заперечуваність у логіці висловлень -- 49 2.4. Нормальні форми логіки висловлювань -- 50 2.5. Логіка першого ступеня -- 52 2.6. Закони логіки предикатів -- 58 2.7. Випереджена нормальна форма логіки предикатів -- 60 2.8. Логічне виведення у логіці висловлювань -- 61 2.9. Правила виведення в логіці висловлювань -- 63 2.10. Метод резолюцій -- 65 2.11. Алгоритми методу резолюцій доведення теорем у штучному інтелекті -- 68 2.11.1. Правила виведення у численні предикатів -- 69 2.11.2. Підстановка та уніфікація. Найзагальніший уніфікатор -- 71 2.11.3. Алгоритм уніфікації -- 73 2.11.4. Сколемівська нормальна форма -- 75 2.11.5. Метод резолюцій у численні предикатів -- 77 2.11.6. Хорнівські диз’юнкти та метод SLD-резолюцій -- 85 2.11.7. Алгоритм SLD-резолюції -- 87 2.11.8. Принцип логічного програмування -- 88 2.11.9. Інтерпретатор логічної програми -- 90 2.12. Тестові завдання для самоконтролю -- 94 2.13. Ключ до тестових завдань -- 95 2.14. Індивідуальні завдання для виконання лабораторної роботи -- 96 2.15. Комп’ютерний проект -- 103 2.16. Додаткові завдання для виконання лабораторної роботи -- 103 2.17. Контрольні запитання -- 129 Розділ 3. Відношення -- 131 3.1. Відношення та їх властивості -- 131 3.2. Відношення еквівалентності -- 135 3.3. Відношення часткового порядку -- 136 3.4. Відношення толерантності -- 137 3.5. Топологічне сортування -- 140 3.6. Операції над відношеннями -- 142 3.7. Замикання відношень -- 143 3.8. Алгоритм Уоршалла для побудови транзитивного замикання -- 144 3.9. База даних і відношення -- 146 3.10. Бінарні відношення та їх особливості -- 149 3.11. Основні властивості та типи бінарних відношень -- 155 3.12. Агрегація відношень. Поняття фактор-відношення -- 164 3.13. Елементи теорії впорядкованих множин -- 167 3.14. Подання переваг ОПР за допомогою бінарних відношень -- 171 3.15. Неметризовані бінарні відношення -- 178 3.16. Метризовані бінарні відношення -- 183 3.17. Тестові завдання для самоконтролю -- 186 3.18. Ключ до тестових завдань -- 188 3.19. Індивідуальні завдання для виконання лабораторної роботи -- 188 3.20. Комп’ютерний проект -- 192 3.21. Додаткові завдання для виконання лабораторної роботи -- 197 3.22. Контрольні запитання -- 202 Розділ 4. Булеві функції -- 205 4.1. Означення булевої функції -- 205 4.2. Диз’юнктивна нормальна форма (ДНФ) -- 209 4.3. Кон’юнктивна нормальна форма (КНФ) -- 209 4.4. Методи побудови скороченої ДНФ -- 211 4.5. Алгоритми Куайна та Девіса-Патнема доведення теорем у штучному інтелекті -- 213 4.6. Логічні методи подання функцій та механізмів вибору -- 216 4.7. Логічна форма функцій вибору -- 220 4.8. Класи функцій вибору та взаємозв’язки між ними -- 224 4.9. Механізм вибору -- 228 4.10. Тестові завдання для самоконтролю -- 241 4.11. Ключ до тестових завдань -- 242 4.12. Індивідуальні завдання для виконання лабораторної роботи -- 242 4.13. Комп’ютерний проект -- 244 4.14. Додаткові завдання для самостійної роботи -- 244 4.15. Контрольні запитання -- 246 Розділ 5. Елементи комбінаторного аналізу -- 248 5.1. Основні правила комбінаторного аналізу. Поняття вибірки. Розміщення та сполучення -- 248 5.2. Обчислення кількості розміщень, перестановок і сполучень -- 257 5.3. Комбінаторика без повторень -- 258 5.3.1. Перестановки -- 258 5.3.2. Розміщення -- 261 5.3.3. Сполучення -- 264 5.3.4. Перестановки з нерухомими точками -- 271 5.4. Комбінаторна з повторенням -- 277 5.4.1. Перестановки -- 277 5.4.2. Розміщення -- 280 5.4.3. Сполучення -- 286 5.4.4. Задача про цілочисельні розв’язки -- 293 5.5. Приклади розв'язування комбінаторних задач -- 294 5.6. Рекурсія для комбінаторики -- 298 5.7. Розбиття множини на підмножини -- 306 5.7.1. Впорядковане розбиття множини на задане число підмножин заданих потужностей -- 306 5.7.2. Невпорядковане розбиття множини на задане число підмножин заданих потужностей -- 311 5.7.3. Невпорядковане розбиття множини на задане число непорожніх підмножин довільних потужностей -- 317 5.7.4. Довільні невпорядковані розбиття множини на непорожні підмножини -- 319 5.8. Поліноміальна формула -- 320 5.9. Біном Ньютона -- 320 5.10. Інверсії -- 323 5.11. Зворотні перестановки -- 324 5.12. Рекурентні рівняння. Розв’язування рекурентних рівнянь -- 326 5.13. Тестові завдання для самоконтролю -- 327 5.14. Ключ до тестових завдань -- 328 5.15. Індивідуальні завдання для виконання лабораторної роботи -- 328 5.16. Комп’ютерний проект -- 335 5.17. Додаткові завдання для самостійної роботи -- 346 5.18. Контрольні запитання -- 368 Розділ 6. Теорія графів -- 369 6.1 Основні означення та властивості -- 369 6.2. Способи подання графів -- 372 6.3. Шляхи та цикли -- 378 6.4. Алгоритми обходу графів -- 380 6.4.1. Алгоритм пошуку вглиб у графі -- 380 6.4.2. Алгоритм проходження графу вшир -- 383 6.5. Розфарбовування графа -- 385 6.6. Алгоритм Дейкстри -- 385 6.7. Цікаві задачі на графах -- 389 6.7.1. Топологічне сортування -- 389 6.7.2. Пошук мостів -- 390 6.7.3. Задача про максимальний потік -- 390 6.7.4. Мінімальні кістякові дерева -- 392 6.7.5. Задача Пріма-Крускала -- 392 6.7.6. Алгоритм Пріма -- 394 6.7.7. Алгоритм Крускала -- 396 6.7.8. Алгоритм Флойда-Уоршелла -- 398 6.7.9. Оптимальне розміщення -- 403 6.7.10. Задача про комівояжера -- 404 6.7.11. Алгоритм Літтла -- 406 6.7.12. Задача про паросполучення -- 409 6.7.13. Оптимальність для підзадач -- 411 6.8. Тестові завдання для самоконтролю -- 412 6.9. Ключ до тестових завдань -- 413 6.10. Індивідуальні завдання для виконання лабораторної роботи -- 413 6.11. Комп’ютерний проект -- 418 6.12. Додаткові завдання для самостійної роботи -- 421 6.13. Контрольні запитання -- 424 Розділ 7. Дерева -- 426 7.1. Основні означення та властивості -- 426 7.2. Подання дерев -- 428 7.2.1. Подання дерев на зв’язній пам’яті -- 428 7.2.2. Подання дерев на суміжній пам’яті -- 429 7.3. Алгоритми обходу дерев -- 432 7.4. Рекурсія для обходу дерев -- 436 7.5. Подання дерев у програмуванні -- 437 7.6. Програмна реалізація алгоритмів обходу дерева вглиб та вшир -- 439 7.7. Бінарне (двійкове) дерево -- 439 7.8. Реалізація двійкових дерев у мові програмування -- 441 7.8.1. Опис вершини -- 441 7.8.2. Дерева мінімальної висоти -- 442 7.8.3. Формування бінарного дерева -- 443 7.8.4. Алгоритм обходу бінарного дерева -- 444 7.8.5. Пошук за допомогою дерева -- 444 7.8.6. Побудова дерева пошуку -- 446 7.8.7. Пошук по дереву -- 446 7.9. Розбір арифметичного виразу -- 448 7.9.1. Дерево для арифметичного виразу -- 448 7.9.2. Форми запису арифметичного виразу -- 448 7.9.3. Алгоритм побудови дерева -- 449 7.9.4. Обчислення виразу по дереву -- 450 7.9.5. Розбір виразу з дужками -- 451 7.9.6. Багатозначні числа і змінні -- 452 7.9.7. Спрощення виразу за допомогою дерева -- 453 7.9.8. Операція виключення з бінарного дерева -- 454 7.9.9. Подання бінарного дерева в прямокутній пам’яті -- 455 7.9.10. Застосування бінарних дерев -- 455 7.9.11. Збалансоване дерево -- 456 7.10. Каркаси -- 457 7.11. Бектрекінг -- 459 7.12. Індукція дерев рішень -- 467 7.13. Тестові завдання для самоконтролю -- 471 7.14. Ключ до тестових завдань -- 473 7.15. Індивідуальні завдання для виконання лабораторної роботи -- 473 7.16. Комп’ютерний проект -- 474 7.17. Додаткові завдання для самостійної роботи -- 476 7.18. Контрольні запитання -- 479 Розділ 8. Мови, граматики, автомати -- 480 8.1. Граматики з фразовою структурою -- 480 8.2. Типи граматик з фразовою структурою -- 482 8.3. Дерева виведення -- 483 8.4. Форми Бекуса-Наура -- 484 8.5. Скінченний автомат з виходом -- 485 8.6. Скінченний автомат без виходу -- 485 8.7. Мови -- 486 8.8. Математична модель мовосприйняття -- 487 8.8.1. Визначення способів подання мови на синтаксичному рівні -- 488 8.8.2. Механізм виводу фраз формальної граматики -- 492 8.9. Тестові завдання для самоконтролю -- 496 8.10. Ключ до тестових завдань -- 497 8.11. Індивідуальні завдання для виконання лабораторної роботи -- 498 8.12. Комп’ютерний проект -- 503 8.13. Додаткові завдання для самостійної роботи -- 503 8.14. Контрольні запитання -- 512 Розділ 9. Основи теорії алгоритмів -- 513 9.1. Основні вимоги до алгоритмів -- 514 9.2. Машина Тюрінга -- 516 9.3. Обчислення числових функцій на машинах Тюрінга -- 521 9.4. Теза Тюрінга. Приклади алгоритмічно нерозв’язних проблем -- 522 9.5. Формальні алгоритмічні системи -- 523 9.6. Теорія складності обчислень -- 527 9.7. Тестові завдання для самоконтролю -- 529 9.8. Ключ до тестових завдань -- 530 9.9. Індивідуальні завдання для виконання лабораторної роботи -- 530 9.10. Комп’ютерний проект -- 533 9.11. Додаткові завдання для самостійної роботи -- 535 9.12. Контрольні запитання -- 538 Список літератури -- 540 Додатки -- 552 Додаток А. Дістинги програм -- 552 Лістинг А.1. Множини -- 552 Лістинг А-2 Відображення -- 554 Лістинг А.З. Граф -- 556 Лістинг А.4. Дерева -- 559 Лістинг А.5. Алгоритм Пріма -- 561 Лістинг А.6. Алгоритм Крускала -- 563 Лістинг А.7. Алгоритм Дейкстри -- 565 Лістинг А.8. Алгоритм Флойда -- 567 Додаток Б. Додаткові індивідуальні та тестові завдання -- 570 Abstract: Навчальний посібник містить матеріал для вивчення основних теоретичних засад, функціональних можливостей та практичного застосування дискретної математики, основи математичної логіки і теорії множин, елементи комбінаторного аналізу, основи теорії відношень, основи теорії графів та дерев, основи теорії кодування, булеві функції, мови, граматики та автомати, основи теорії алгоритмів, основи теорії кодування. Посібник призначений для здобуття студентами практичних навичок застосування класичних алгоритмів дискретної математики та сучасних алгоритмів штучного інтелекту, що використовуються при побудові комп’ютерних програм. Теоретичний та практичний матеріал викладено у доступній формі. Викладення. 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) / Д48 (Browse shelf (Opens below)) Checked out 18.01.2025 41683-011926
Бібліотека Українського Гуманітарного Інституту
Науковий фонд
517-519.2(075.8) / Д48 (Browse shelf (Opens below)) Available 41683-011927
Бібліотека Українського Гуманітарного Інституту
Науковий фонд
517-519.2(075.8) / Д48 (Browse shelf (Opens below)) Available 41683-011924
Бібліотека Українського Гуманітарного Інституту
Науковий фонд
517-519.2(075.8) / Д48 (Browse shelf (Opens below)) Available 41683-011925
Бібліотека Українського Гуманітарного Інституту
Науковий фонд
517-519.2(075.8) / Д48 (Browse shelf (Opens below)) Available 41683-011922
Бібліотека Українського Гуманітарного Інституту
Науковий фонд
517-519.2(075.8) / Д48 (Browse shelf (Opens below)) Available 41683-011923
Бібліотека Українського Гуманітарного Інституту
Науковий фонд
517-519.2(075.8) / Д48 (Browse shelf (Opens below)) Available 41683-011920
Бібліотека Українського Гуманітарного Інституту
Науковий фонд
517-519.2(075.8) / Д48 (Browse shelf (Opens below)) Available 41683-011921
Бібліотека Українського Гуманітарного Інституту
Науковий фонд
517-519.2(075.8) / Д48 (Browse shelf (Opens below)) Checked out 31.08.2024 41683-011918
Бібліотека Українського Гуманітарного Інституту
Науковий фонд
517-519.2(075.8) / Д48 (Browse shelf (Opens below)) Checked out 31.08.2024 41683-011919
Browsing Бібліотека Українського Гуманітарного Інституту shelves, Shelving location: Науковий фонд Close shelf browser (Hides shelf browser)
517-519.2(075.8) / Д48 Дискретна математика: практикум , ( збірник задач здискретної математики) навчальний посібник 517-519.2(075.8) / Д48 Дискретна математика: практикум , ( збірник задач здискретної математики) навчальний посібник 517-519.2(075.8) / Д48 Дискретна математика: практикум , ( збірник задач здискретної математики) навчальний посібник 517-519.2(075.8) / Д48 Дискретна математика: практикум , ( збірник задач здискретної математики) навчальний посібник 517-519.2(075.8) / Д48 Дискретна математика: практикум , ( збірник задач здискретної математики) навчальний посібник 517-519.2(075.8) / Д48 Дискретна математика: практикум , ( збірник задач здискретної математики) навчальний посібник 517-519.2(075.8) / Д48 Дискретна математика: практикум , ( збірник задач здискретної математики) навчальний посібник

Вступ 8

Розділ 1 Множини та операції над ними 15 1.1. Множина Кортеж. Декартів добуток 15 1.2. Операції над множинами 18 1.3. Взаємно однозначна відповідність 21 1.4. Комп'ютерне подання множин 21 1.5. Еквівалентність та потужність множин 30 1.6. Тестові завдання для самоконтролю 35 1.7. Ключ до тестових завдань 37 1.8. Індивідуальні завдання для виконання лабораторної роботи 37 1.9. Комп’ютерний проект 39 1.10. Додаткові завдання для самостійної роботи 39 1.11. Контрольні запитання 42

Розділ 2. Логіка висловлювань та логіка першого ступеня 43 2.1. Логіка висловлювань та логіка першого ступеня 43 2.2. Закони логіки висловлень 48 2.3. Загальнозначущість та заперечуваність у логіці висловлень 49 2.4. Нормальні форми логіки висловлювань 50 2.5. Логіка першого ступеня 52 2.6. Закони логіки предикатів 58 2.7. Випереджена нормальна форма логіки предикатів 60 2.8. Логічне виведення у логіці висловлювань 61 2.9. Правила виведення в логіці висловлювань 63 2.10. Метод резолюцій 65 2.11. Алгоритми методу резолюцій доведення теорем у штучному інтелекті 68 2.11.1. Правила виведення у численні предикатів 69 2.11.2. Підстановка та уніфікація. Найзагальніший уніфікатор 71 2.11.3. Алгоритм уніфікації 73 2.11.4. Сколемівська нормальна форма 75 2.11.5. Метод резолюцій у численні предикатів 77 2.11.6. Хорнівські диз’юнкти та метод SLD-резолюцій 85 2.11.7. Алгоритм SLD-резолюції 87 2.11.8. Принцип логічного програмування 88 2.11.9. Інтерпретатор логічної програми 90 2.12. Тестові завдання для самоконтролю 94 2.13. Ключ до тестових завдань 95 2.14. Індивідуальні завдання для виконання лабораторної роботи 96 2.15. Комп’ютерний проект 103 2.16. Додаткові завдання для виконання лабораторної роботи 103 2.17. Контрольні запитання 129

Розділ 3. Відношення 131 3.1. Відношення та їх властивості 131 3.2. Відношення еквівалентності 135 3.3. Відношення часткового порядку 136 3.4. Відношення толерантності 137 3.5. Топологічне сортування 140 3.6. Операції над відношеннями 142 3.7. Замикання відношень 143 3.8. Алгоритм Уоршалла для побудови транзитивного замикання 144 3.9. База даних і відношення 146 3.10. Бінарні відношення та їх особливості 149 3.11. Основні властивості та типи бінарних відношень 155 3.12. Агрегація відношень. Поняття фактор-відношення 164 3.13. Елементи теорії впорядкованих множин 167 3.14. Подання переваг ОПР за допомогою бінарних відношень 171 3.15. Неметризовані бінарні відношення 178 3.16. Метризовані бінарні відношення 183 3.17. Тестові завдання для самоконтролю 186 3.18. Ключ до тестових завдань 188 3.19. Індивідуальні завдання для виконання лабораторної роботи 188 3.20. Комп’ютерний проект 192 3.21. Додаткові завдання для виконання лабораторної роботи 197 3.22. Контрольні запитання 202

Розділ 4. Булеві функції 205 4.1. Означення булевої функції 205 4.2. Диз’юнктивна нормальна форма (ДНФ) 209 4.3. Кон’юнктивна нормальна форма (КНФ) 209 4.4. Методи побудови скороченої ДНФ 211 4.5. Алгоритми Куайна та Девіса-Патнема доведення теорем у штучному інтелекті 213 4.6. Логічні методи подання функцій та механізмів вибору 216 4.7. Логічна форма функцій вибору 220 4.8. Класи функцій вибору та взаємозв’язки між ними 224 4.9. Механізм вибору 228 4.10. Тестові завдання для самоконтролю 241 4.11. Ключ до тестових завдань 242 4.12. Індивідуальні завдання для виконання лабораторної роботи 242 4.13. Комп’ютерний проект 244 4.14. Додаткові завдання для самостійної роботи 244 4.15. Контрольні запитання 246

Розділ 5. Елементи комбінаторного аналізу 248 5.1. Основні правила комбінаторного аналізу. Поняття вибірки. Розміщення та сполучення 248 5.2. Обчислення кількості розміщень, перестановок і сполучень 257 5.3. Комбінаторика без повторень 258 5.3.1. Перестановки 258 5.3.2. Розміщення 261 5.3.3. Сполучення 264 5.3.4. Перестановки з нерухомими точками 271 5.4. Комбінаторна з повторенням 277 5.4.1. Перестановки 277 5.4.2. Розміщення 280 5.4.3. Сполучення 286 5.4.4. Задача про цілочисельні розв’язки 293 5.5. Приклади розв'язування комбінаторних задач 294 5.6. Рекурсія для комбінаторики 298 5.7. Розбиття множини на підмножини 306 5.7.1. Впорядковане розбиття множини на задане число підмножин заданих потужностей 306 5.7.2. Невпорядковане розбиття множини на задане число підмножин заданих потужностей 311 5.7.3. Невпорядковане розбиття множини на задане число непорожніх підмножин довільних потужностей 317 5.7.4. Довільні невпорядковані розбиття множини на непорожні підмножини 319 5.8. Поліноміальна формула 320 5.9. Біном Ньютона 320 5.10. Інверсії 323 5.11. Зворотні перестановки 324 5.12. Рекурентні рівняння. Розв’язування рекурентних рівнянь 326 5.13. Тестові завдання для самоконтролю 327 5.14. Ключ до тестових завдань 328 5.15. Індивідуальні завдання для виконання лабораторної роботи 328 5.16. Комп’ютерний проект 335 5.17. Додаткові завдання для самостійної роботи 346 5.18. Контрольні запитання 368

Розділ 6. Теорія графів 369 6.1 Основні означення та властивості 369 6.2. Способи подання графів 372 6.3. Шляхи та цикли 378 6.4. Алгоритми обходу графів 380 6.4.1. Алгоритм пошуку вглиб у графі 380 6.4.2. Алгоритм проходження графу вшир 383 6.5. Розфарбовування графа 385 6.6. Алгоритм Дейкстри 385 6.7. Цікаві задачі на графах 389 6.7.1. Топологічне сортування 389 6.7.2. Пошук мостів 390 6.7.3. Задача про максимальний потік 390 6.7.4. Мінімальні кістякові дерева 392 6.7.5. Задача Пріма-Крускала 392 6.7.6. Алгоритм Пріма 394 6.7.7. Алгоритм Крускала 396 6.7.8. Алгоритм Флойда-Уоршелла 398 6.7.9. Оптимальне розміщення 403 6.7.10. Задача про комівояжера 404 6.7.11. Алгоритм Літтла 406 6.7.12. Задача про паросполучення 409 6.7.13. Оптимальність для підзадач 411 6.8. Тестові завдання для самоконтролю 412 6.9. Ключ до тестових завдань 413 6.10. Індивідуальні завдання для виконання лабораторної роботи 413 6.11. Комп’ютерний проект 418 6.12. Додаткові завдання для самостійної роботи 421 6.13. Контрольні запитання 424

Розділ 7. Дерева 426 7.1. Основні означення та властивості 426 7.2. Подання дерев 428 7.2.1. Подання дерев на зв’язній пам’яті 428 7.2.2. Подання дерев на суміжній пам’яті 429 7.3. Алгоритми обходу дерев 432 7.4. Рекурсія для обходу дерев 436 7.5. Подання дерев у програмуванні 437 7.6. Програмна реалізація алгоритмів обходу дерева вглиб та вшир 439 7.7. Бінарне (двійкове) дерево 439 7.8. Реалізація двійкових дерев у мові програмування 441 7.8.1. Опис вершини 441 7.8.2. Дерева мінімальної висоти 442 7.8.3. Формування бінарного дерева 443 7.8.4. Алгоритм обходу бінарного дерева 444 7.8.5. Пошук за допомогою дерева 444 7.8.6. Побудова дерева пошуку 446 7.8.7. Пошук по дереву 446 7.9. Розбір арифметичного виразу 448 7.9.1. Дерево для арифметичного виразу 448 7.9.2. Форми запису арифметичного виразу 448 7.9.3. Алгоритм побудови дерева 449 7.9.4. Обчислення виразу по дереву 450 7.9.5. Розбір виразу з дужками 451 7.9.6. Багатозначні числа і змінні 452 7.9.7. Спрощення виразу за допомогою дерева 453 7.9.8. Операція виключення з бінарного дерева 454 7.9.9. Подання бінарного дерева в прямокутній пам’яті 455 7.9.10. Застосування бінарних дерев 455 7.9.11. Збалансоване дерево 456 7.10. Каркаси 457 7.11. Бектрекінг 459 7.12. Індукція дерев рішень 467 7.13. Тестові завдання для самоконтролю 471 7.14. Ключ до тестових завдань 473 7.15. Індивідуальні завдання для виконання лабораторної роботи 473 7.16. Комп’ютерний проект 474 7.17. Додаткові завдання для самостійної роботи 476 7.18. Контрольні запитання 479

Розділ 8. Мови, граматики, автомати 480 8.1. Граматики з фразовою структурою 480 8.2. Типи граматик з фразовою структурою 482 8.3. Дерева виведення 483 8.4. Форми Бекуса-Наура 484 8.5. Скінченний автомат з виходом 485 8.6. Скінченний автомат без виходу 485 8.7. Мови 486 8.8. Математична модель мовосприйняття 487 8.8.1. Визначення способів подання мови на синтаксичному рівні 488 8.8.2. Механізм виводу фраз формальної граматики 492 8.9. Тестові завдання для самоконтролю 496 8.10. Ключ до тестових завдань 497 8.11. Індивідуальні завдання для виконання лабораторної роботи 498 8.12. Комп’ютерний проект 503 8.13. Додаткові завдання для самостійної роботи 503 8.14. Контрольні запитання 512

Розділ 9. Основи теорії алгоритмів 513 9.1. Основні вимоги до алгоритмів 514 9.2. Машина Тюрінга 516 9.3. Обчислення числових функцій на машинах Тюрінга 521 9.4. Теза Тюрінга. Приклади алгоритмічно нерозв’язних проблем 522 9.5. Формальні алгоритмічні системи 523 9.6. Теорія складності обчислень 527 9.7. Тестові завдання для самоконтролю 529 9.8. Ключ до тестових завдань 530 9.9. Індивідуальні завдання для виконання лабораторної роботи 530 9.10. Комп’ютерний проект 533 9.11. Додаткові завдання для самостійної роботи 535 9.12. Контрольні запитання 538

Список літератури 540

Додатки 552

Додаток А. Дістинги програм 552

Лістинг А.1. Множини 552

Лістинг А-2 Відображення 554

Лістинг А.З. Граф 556

Лістинг А.4. Дерева 559

Лістинг А.5. Алгоритм Пріма 561

Лістинг А.6. Алгоритм Крускала 563

Лістинг А.7. Алгоритм Дейкстри 565

Лістинг А.8. Алгоритм Флойда 567

Додаток Б. Додаткові індивідуальні та тестові завдання 570

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

There are no comments on this title.

to post a comment.

Click on an image to view it in the image viewer

Powered by Koha