Документ взят из кэша поисковой машины. Адрес оригинального документа : http://new.math.msu.su/content_root/programs/kaf/special/logica/teor-ver.doc Дата изменения: Mon Nov 10 08:55:54 2008 Дата индексирования: Sun Apr 10 03:10:31 2016 Кодировка: koi8-r

ТЕОРИЯ СЛОЖНОСТИ ВЫЧИСЛЕНИЙ
проф. Н.К. Верещагин
1/2 года, для магистрантов специальности "Теоретические вопросы
информатики"
Понятие алгоритма, вычислимой функции. Разрешимые и перечислимые
множества. Нумерации вычислимых функций. Модели вычислений. Примеры
неразрешимых проблем. Сводимость одних проблем к другим. Время и память как
меры сложности алгоритмов. Классы P и NP; проблема перебора. NP-полные
проблемы. Элементы теории сложности описаний.
1. Понятие вычислимой функции, разрешимого множества.
2. Перечислимые множества.
3. Перечислимость и разрешимость (теорема Поста, теорема о проекции
разрешимого множества).
4. Теорема о графике вычислимой функции.
5. Универсальные вычислимые функции.
6. Нумерации вычислимых функций. Главные универсальные функции.
7. Построение перечислимого неразрешимого множества. Алгоритмически
неразрешимые проблемы в теории алгоритмов.
8. Машины Тьюринга: определения и примеры. Тезис Чёрча.
9. Неразрешимость проблемы тождества в полугруппах. Примеры других
алгоритмически неразрешимых проблем в алгебре и теории чисел.
10. m-Сводимость, m-полные перечислимые множества.
11. Машины с оракулом и сводимость по Тьюрингу. Существование неполных
перечислимых неразрешимых множеств.
12. Адресные машины.
13. Время и память (зона) как характеристики сложности вычислений.
14. Полиномиальная эквивалентность по времени машин Тьюринга и адресных
машин.
15. Класс P языков, разрешимых за полиномиальное время. Примеры проблем
из класса P.
16. Теорема об иерархии для зонной сложности.
17. Теорема об иерархии для временной сложности.
18. Класс NP. Примеры проблем из класса NP. О проблеме P=?NP.
19. Полиномиальный аналог m-сводимости. Доказательство сводимости
проблемы ВЫПОЛНИМОСТЬ к проблеме 3-КНФ.
20. Доказательство сводимости проблемы 3-КНФ к проблеме ВЕРШИННОЕ
ПОКРЫТИЕ.
21. NP-полные проблемы. Теорема Кука-Левина. Примеры NP-полных проблем.
22. Определение колмогоровской энтропии как меры количества информации в
строке символов. Невычислимость энтропии.

Литература
1. Роджерс Х. Теория рекурсивных функций и эффективная вычислимость. М.,
Мир, 1972.
2. Верещагин Н.К., Шень А. Лекции по математической логике и теории
алгоритмов. Вычислимые функции. М., МЦНМО, 1999.
3. Гэри M., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.,
Мир, 1982.
4. Колмогоров А.Н. Три подхода к определению понятия "количество
информации".// Проблемы передачи информации, 1965, т. 1, ? 1, с. 3-11.