Локальне зображення обкладинки
Локальне зображення обкладинки

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

Альтернативний автор-особа: Автор, Висоцька, В. А., Вікторія Анатолієвна; Автор, Литвин , В. В., Василь Володимирович; Автор, Лозинська, О. В., Ольга ВолодимирівнаМова: українська.Країна: УКРАЇНА.Вихідні дані: Львів : Новий Світ - 2000, 2023Опис: 576 с. : іл.ISBN: 978-617-7519-29-3.Примітки про зміст: Вступ -- 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 Анотація: Навчальний посібник містить матеріал для вивчення основних теоретичних засад, функціональних можливостей та практичного застосування дискретної математики, основи математичної логіки і теорії множин, елементи комбінаторного аналізу, основи теорії відношень, основи теорії графів та дерев, основи теорії кодування, булеві функції, мови, граматики та автомати, основи теорії алгоритмів, основи теорії кодування. Посібник призначений для здобуття студентами практичних навичок застосування класичних алгоритмів дискретної математики та сучасних алгоритмів штучного інтелекту, що використовуються при побудові комп’ютерних програм. Теоретичний та практичний матеріал викладено у доступній формі. Викладення. Тип одиниці: Навчальні видання
Мітки з цієї бібліотеки: Немає міток з цієї бібліотеки для цієї назви. Ввійдіть, щоб додавати мітки.
Оцінки зірочками
    середня оцінка: 0.0 (0 голосів)
Фонди
Поточна бібліотека Шифр зберігання Стан Очікується на дату Штрих-код
Бібліотека Українського Гуманітарного Інституту Науковий фонд 517-519.2(075.8) / Д48 (Огляд полиці(Відкривається нижче)) Доступно 41683-011926
Бібліотека Українського Гуманітарного Інституту Науковий фонд 517-519.2(075.8) / Д48 (Огляд полиці(Відкривається нижче)) Видано 31.08.2024 41683-011927
Бібліотека Українського Гуманітарного Інституту Науковий фонд 517-519.2(075.8) / Д48 (Огляд полиці(Відкривається нижче)) Доступно 41683-011924
Бібліотека Українського Гуманітарного Інституту Науковий фонд 517-519.2(075.8) / Д48 (Огляд полиці(Відкривається нижче)) Доступно 41683-011925
Бібліотека Українського Гуманітарного Інституту Науковий фонд 517-519.2(075.8) / Д48 (Огляд полиці(Відкривається нижче)) Доступно 41683-011922
Бібліотека Українського Гуманітарного Інституту Науковий фонд 517-519.2(075.8) / Д48 (Огляд полиці(Відкривається нижче)) Доступно 41683-011923
Бібліотека Українського Гуманітарного Інституту Науковий фонд 517-519.2(075.8) / Д48 (Огляд полиці(Відкривається нижче)) Доступно 41683-011920
Бібліотека Українського Гуманітарного Інституту Науковий фонд 517-519.2(075.8) / Д48 (Огляд полиці(Відкривається нижче)) Доступно 41683-011921
Бібліотека Українського Гуманітарного Інституту Науковий фонд 517-519.2(075.8) / Д48 (Огляд полиці(Відкривається нижче)) Доступно 41683-011918
Бібліотека Українського Гуманітарного Інституту Науковий фонд 517-519.2(075.8) / Д48 (Огляд полиці(Відкривається нижче)) Видано 31.08.2024 41683-011919

Вступ 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

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

Немає коментарів для цієї одиниці.

для можливості публікувати коментарі.

Натисніть на зображення, щоб переглянути його в оглядачі зображень

Локальне зображення обкладинки

Працює на АБІС Коха