СЛОЖНОСТЬ АЛГОРИТМОВ И СЛУЧАЙНОСТЬ

Программа спецкурса

1. Геделевские нумерации алгоритмов. Теорема об итерации. Теорема об универсальной функции. Теорема Клини о непод- вижной точке.

2. Разрешимые и неразрешимые проблемы. Сводимости алгоритмических проблем. Неразрешимость проблем самоприменимости и остановки. Теорема Райса.

3. Рекурсивно перечислимые множества и их свойства. Пример не рекурсивно перечислимого множества.

4. Критерии сложности программ. Минимальные программы. Свойства множества мимнимальных программ. Минимальные программы для ограниченных языков программирования.

5. Сложности конструктивных объектов по Колмогорову-Маркову-Чейтину. Основные свойства мер сложности и соотношения между ними. Алгоритмическая информация.

6. Максимально сложные (случайные) слова. Их статистические свойства.

7. Случайные последовательности по Мартин-Лефу. Свойства случайных последовательностей.

8. Случайность и сложность. Омега-число Чейтина.

9. Приложения понятий алгоритмической сложности и случайности.

10. Сложность последовательностей при ограничениях на вычисления.