Учебные материалы (Практические занятия, контрольные задания, конспект лекций) / Контроль знаний / Контрольные вопросы
.docКонтрольные вопросы по курсу “Алгоритмы и алгоритмическая сложность ”
1.Исторически обзор теории алгоритмов.
2.Определение машины Тьюринга.
3. Машина Маркова.
4. Нумерация машин Тьюринга.
5. Пример невычислимой функции, построенной по методу диагонализации Кантора.
6. Распознающие машины Тьюринга и языки. Проблема распознавания языков.
7. Неразрешимость проблемы самоприменимости.
8. Неразрешимость проблемы остановки.
9. Другие примеры неразрешимых алгоритмически задач.
10. Рекурсивные функции и их построение из простейших.
11. Операторы подстановки, рекурсии и минимизации. Частично рекурсивные функции.
12. Тезис Черча.
13. Рекурсивно перечислимые множества. Связь между рекурсивной перечислимостью и рекурсивностью.
14. Подходы к определению сложности алгоритмов.
15. Алгоритмическая, информационная и инфологическая сложность.
16. Понятие вычислительной сложности. Примеры ее определения.
17. Класс P и NP.
18. Классы co-NP, PSPACE, NPSPACE.
19. Задача ВЫПОЛНИМОСТЬ и теорема С.Кука о полноте задачи ВЫПОЛНИМОСТЬ.
20. Другие NP-полные задачи. Примеры сводимости в классе NP.
21. Метод резолюций Робинсона для задачи ВЫПОЛНИМОСТЬ.
22. Метод отсечения литер для задачи ВЫПОЛНИМОСТЬ.
23. Метод групповых резолюций для задачи ВЫПОЛНИМОСТЬ.
24. Гипотеза P≠NP и ее обоснование.
25. Описание дискретных оптимизационных задач на языке логики.