Вопросы и ответы к экзамену / ВОПРОСЫ К ЭКЗАМЕНУ

ВОПРОСЫ К ЭГЗАМЕНУ.

1. Словарные функции.

2. Вычислимые функции. Машина Тьюринга.

3. Словарное предствление машины Тьюринга.

4. Массовые алгоритмические проблемы. Разрешимые и перечислимые множества.

5. Теорема Поста.

6. Проблема остановки. Теорема Тьюринга.

7. Проблема пустой ленты. Проблема зацикливания.

8. Понятие массовой и индивидуальной задачи.

9. Понятие полиномиального алгоритма и труднорешаемой задачи.

10. Понятие схемы кодирования.

11. Задачи распознавания. Переход от оптимизационной задачи к задаче

распознавания.

12. Язык. Связь между задачами распознавания и языками.

13. Детерминированные машины Тьюринга и класс P.

14. Недетерминированное вычисление и класс NP.

15. Взаимоотношения между класами P и NP.

16. Полиномиальная сводимость.

17. NP-полные задачи.

18. Теорема Кука. 6 основных NP-полных задач.

19. Методы доказательства NP-полноты. Метод сужения.

20. Методы доказательства NP-полноты. Метод локальной замены.

21. Методы доказательства NP-полноты. Метод построения компонент.

22. Анализ подзадач NP-полной задачи.

23. Сильная NP-полнота.

24. Псевдополиномиальные алгоритмы.

25. Именная форма. Высказывания. Операции над высказываниями.

26. Основные логические законы. Логические тождества.

27. Правила обращения с кванторами.

28. Техника доказательств.

29. Операции над множествами и одноместными предикатами.

30. Булевы функции.