Вопросы по курсу

«Теория алгоритмов»

1. Элементы теории множеств.

2. Отношения на множествах, теорема о разбиении множества на классы эквивалентности.

3. Функции, теорема о несчетности множества подмножеств N.

4. Алфавиты, цепочки и языки.

5. Регулярные выражения и регулярные множества.

6. Графы и деревья.

7. Понятие алгоритма.

8. Детерминированные конечные автоматы и распознаваемые ими языки.

9. Недетерминированные конечные автоматы и распознаваемые ими языки, теорема о детерминизации.

10. Теорема о замкнутости класса языков, распознаваемых конечными автоматами, относительно основных операций.

11. Теорема о совпадении классов регулярных множеств и языков, распознаваемых конечными автоматами.

12. Теорема о разрастании, пример не регулярного множества.

13. Минимизация числа состояний конечного автомата, теорема о свойстве отношения эквивалентности цепочек относительно автомата.

14. Теорема Майхилла–Нероуда.

15. Контекстно–свободные грамматики и языки.

16. Деревья вывода, эквивалентные преобразования контекстно-свободных грамматик.

17. Теорема о замкнутости класса контекстно-свободных языков относительно основных операций.

18. Теорема о строгом включении регулярных множеств в класс контекстно-свободных языков.

19. Определение машин Шенфилда и функций, вычислимых на ней.

20. Теорема об элиминации макросов, полезные макросы.

21. Определение частично рекурсивных функций, теорема об их вычислимости на машине Шенфилда.

22. Определение примитивно рекурсивных и общерекурсивных функций.

23. Примеры вычислимых функций и вычислимых предикатов.

24. Кодирование последовательностей, лемма о совместной рекурсии.

25. Кодирование машин Шенфилда, теорема о совпадении класса функций, вычислимых на машинах Шенфилда, и класса частично рекурсивных функций.

26. Тезис Черча, теорема Клини о нормальной форме, универсальные вычислимые функции.

27. Теорема о параметризации (s-m-n-теорема).

28. Машины Тьюринга.

29. Нормальные алгорифмы Маркова.

30. Нумерации, теорема о неразрешимости проблемы самоприменимости.

31. Теорема об однозначной нумерации.

32. Теорема Клини о неподвижной точке.

33. Теорема Райса.

34. Приемлемые функции и их свойства.

35. Теорема о единственности приемлемой функции.

36. Перечислимые множества, их основные свойства.

37. Замкнутость перечислимых множеств относительно пересечения и объединения, теорема Поста.

38. Сложность алгоритмов и языков, класс P.

39. Теорема Цейтина.

40. Недетерминированные машины Тьюринга, теорема об их детерминированном моделировании.

41. Класс NP, полиномиальная сводимость, NP-полные языки.

42. Класс задач NP, задачи о выполнимости и о клике.

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

44. Теорема о NP-полнота задачи о вершинном покрытии, примеры NP-полных задач.

Проф. В. Н. Касьянов