Программа зачета по теории алгоритмов
2-й семестр 1999/2000 уч. года

1. Понятие рекурсивной (вычислимой) функции. Машина с неограниченными регистрами, формализация Клини.
2. Канторовская нумерационная функция, ее значение. Нумерация пар, n-ок и конечных последовательностей натуральных чисел. Нумерация машин с неограниченными регистрами.
3. Нумерация машин с неограниченными регистрами. Универсальная машина и универсальная функция.
4. Универсальная машина. s-m-n-теорема.
5. Неразрешимость проблемы остановки. Другие неразрешимые проблемы.
6. Рекурсивные и рекурсивно перечислимые множества, их простейшие свойства. Теорема Поста.
7. Основная теорема о рекурсивно перечислимых множествах.
8. Теорема о проекции. Теорема о графике рекурсивной функции.
9. Рекурсивно перечислимые и рекурсивные индексы множеств. Канонические индексы конечных множеств. Переход от рекурсивных к р.п. индексам и невозможность обратного перехода.
10. Рекурсивно перечислимые и рекурсивные индексы множеств. Канонические индексы конечных множеств. Переход от канонических к рекурсивным индексам и невозможность обратного перехода.
11. Теорема о неподвижной точке и ее следствия. Теорема об отсутствии алгоритма, оптимизирующего любую машину.
12. 1- и m-сводимости и степени, их простейшие свойства. 1- и m-полные множества. Устройство рекурсивных 1- и m- степеней.
13. Машины с оракулом. Сводимость по Тьюрингу и Тьюринговы степени, их простейшие свойства. Операция скачка.
14. Арифметическая иерархия. Представление арифметических отношений в виде предикатной формы от рекурсивных.
15. Арифметическая иерархия. Теорема о нормальной форме.