Содержание
- 2. Питання Недетерміновані машини Тьюринга. Класи NTIME, NP і co-NP. Альтернативне визначення класу NP. Класи з ємнісною
- 3. k-стрічковою недетермінованою машиною Тьюринга називається п'ятірка M = (A, Q, S, П, q0). Значення всіх компонент
- 4. НМТ M допускає вхідне слово x, якщо хоча б одна така послідовність конфігурацій призводить до стану
- 5. НМТ M має часову складність T(n), якщо для будь-якого вхідного слова, що допускається, довжини n знайдеться
- 6. Масова проблема називається алгоритмічно розв’язуваною, якщо існує алгоритм (машина Тьюрінга), який дозволяє розв’язати кожну задачу цієї
- 7. Класифікація алгоритмів за їх часовою складністю 1. Алгоритм називається сталим, якщо його часова складність не залежить
- 9. Розв’язуваними називаються задачі, в яких використовуються алгоритми з поліноміальною часовою складністю. Складнорозв’язуваними або просто складними називаються
- 10. Класифікація задач за їх складністю розв’язування Клас P утворюють задачі, які можна розв’язати за поліноміальний час.
- 11. Класи задач за складністю щодо недетермінірованних алгоритмів: NDTIME(f(n)) - це клас задач, для кожної з яких
- 12. ТЕОРЕМА 2. Для будь-якої НМТ MN, яка розпізнає мову L за час T(n) знайдеться ДМТ MD
- 13. Мова L належить класу NP тоді і тільки тоді, коли існує детермінована машина Тьюринга M і
- 14. DSPACE(f(n)) - це клас мов, для кожного з яких існує детермінована МТ, що розпізнає цю мову
- 16. Скачать презентацию