Программа курса ''Теория алгоритмов" 
(I семестр)

Введение (1 лекция).
Множества, их основные свойства и операции над ними.
Некоторые основные понятия в теории множеств.
Алфавиты и языки, длина слова, конкатенация слов,
степени с натуральным показателем,
звездочка Клини.

Конечные автоматы и их основные свойства (2 лекции)
Основные черты алгоритмических процессов.
Определение конечных автоматов.
Их графическое изображение.
Языки, распознаваемые конечными автоматами.
Эквивалентность конечных автоматов и
недетерминированных конечных автоматов.
Замкнутость языков, распознаваемых конечными автоматами,
относительно объединения, пересечения, дополнения,
конкатенации и звездочки Клини.

Формальные грамматики (2 лекции)
Определение и примеры формальных грамматик.
Контекстно--свободные и регулярные грамматики.
Совпадение класса регулярных языков и языков,
распознаваемых конечными автоматами.
Алгоритмическая разрешимость множества слов
контекстно--свободных языков.
Замкнутость регулярных языков
относительно объединения, пересечения, дополнения,
конкатенации и звездочки Клини.

Формализации понятия алгоритма (6 лекций).
Определение машин Шенфилда и функций, вычислимых на ней.
Макросы. Теорема об элиминации макросов.
Определение частично рекурсивных функций. Простейшие функции.
Операторы суперпозиции, примитивной рекурсии, минимизации.
Общерекурсивные функции. Примеры вычислимых функций. Вычислимые
(рекурсивные предикаты). Кодирование последовательностей.
Теорема о совпадении классов функций, вычислимых на машинах
Шенфилда и класса частично рекурсивных функций.
Тезис Черча. Теорема о параметризации (s-m-n-теорема).
Теорема Клини о нормальной форме.
Универсальные вычислимые функции.
Машины Тьюринга. Определение. Простейшие машины Тьюринга.
Операции на машинах Тьюринга и их свойства.
Нормальные алгорифмы Маркова. Определение. Примеры.

Дальнейшие результаты о вычислимости (2 лекции)
Общее понятие о нумерации. Понятие об алгоритмически разрешимых и
неразрешимых проблемах. Теорема о неподвижной точке. Теорема Райса.
Неразрешимость проблемы распознавания свойств функций по задающим
их программам. Вычислимый изоморфизм любых двух универсальных
вычислимых функций. Перечислимые множества, их основные свойства.
Нумерация Поста перечислимых множеств и ее свойства.

Вопросы сложности алгоритмов (2 лекции)
Понятие абстрактной сложности.
Общее свойство функций сложности вычислений.
Теорема Блюм об ускорении.


Примерные темы семинарских занятий (в скобках указано число занятий)
Теоретико-множественные упражнения (1).
Конечные автоматы (2).
Формальные грамматики (2)
Построение простейших алгоритмов для машин Шенфилда (1).
Частично рекурсивные функции (2).
Машины Тьюринга (2).
Нормальные алгорифмы Маркова (1).
Дальнейшие вопросы теории вычислимости (4).

Список литературы
[1] Ю.Л.Ершов, Е.А.Палютин, Математическая логика, М., Наука, 1987.
[2] А.Н.Мальцев, Алгоритмы и рекурсивные функции, М., Наука, 1986.
В течение семестра предполагается также издание пособия по
конечным автоматам и формальным грамматикам.

Программу составил
профессор, д.ф.-м.н.                   А.С.Морозов