Содержание
- 2. Питання NP-складність задач. NP-повнота задач. Приклади наближених алгоритмів для NP-повних задач.
- 3. Задача пошуку (search problem) Задача пошуку (search problem) задається алгоритмом С, який отримує на вході умову
- 4. Теза Черча - Тьюринга Будь-яка обчислювана функція обчислюється машиною Тьюринга. Поліноміальні алгоритми існують для багатьох задач.
- 5. Задача «від прогулянок по Кенігсбергу до реконструкції геному». Перша половина XVIII століття. Великий математик Леонард Ейлер
- 6. Твердження: P⊆PC. Доказ: оскільки детерміновані машини Тьюринга є частковим випадком не детермінованих. Отже, до детермінованих класів
- 7. Існують більш високі класи. Крім класу P вивчають інші класи, які визначаються порядком зростання часу роботи
- 8. До класу NP відносяться недетерміновані машини Тьюрінга. Формально недетерміновані обчислення проводяться на недетермінованій машині Тьюринга. Клас
- 9. NP-повнота Якщо Р не збігається з NP, то відмінність між Р і NP\P дуже істотна. Всі
- 10. Поняття поліноміальної зведеності Основна ідея умовного підходу заснована на понятті поліноміальної зведеності. Будемо говорити, що має
- 11. Лемма 1. Якщо L1∞L2, то з L2∈Р слідує, що L1∈Р. (Еквівалентне твердження: з L1 Р слід,
- 12. Лемма 2. Якщо L1∞L2 та L2∞L3 , L1∞L3. Лемма 2 стверджує, що це відношення є відношенням
- 13. Мова L називається NP-повною, якщо L∈NP і будь-яка інша мова L'∈NP зводиться до мови L. Pадача
- 14. Будь-яка NP-повна задача П має властивість: якщо P≠NP, то П∈NP\P. Точніше, П∈Р тоді і тільки тоді,
- 15. Приклади наближених алгоритмів для NP-повних задач Алгоритм, який повертає рішення, близькі до оптимальних, називається наближеним алгоритмом.
- 16. Методи розв’язання NP-повних задач Наближені та евристичні методи – застосування евристик для вибору елементів рішення. Псевдополіноміальні
- 17. Метод локальних покращень Розпочати з довільного рішення. Для покращення поточного рішення застосувати до нього будь-яке перетворення
- 18. Метод гілок та меж Вирішуючи дискретну екстремальну задачу, розіб'ємо множину всіх можливих варіантів на класи і
- 19. Дискретна екстремальна (на мінімум) задача в загальному вигляді: Нехай задано дискретну множину А і визначено на
- 20. Алгоритм методу: Розіб'ємо множину А на підмножини Аі і на кожному з них знайдемо нижню оцінку
- 22. Скачать презентацию