Программа курса ''Теория алгоритмов" для I курса ММФ НГУ (I семестр) I. Основные понятия вычислимости. Некоторые положения, приведшие к развитию формальной теории алгоритмов. Языки формулирования понятия алгоритма. Причины выбора функций на натуральных чисел в качестве области для формулировки понятия вычислимости. Машина Тьюринга. Примеры. Последовательный запуск программ. Макросы для машины Тьюринга. Примеры применения макросов. Определение вычислимости по Клини. Частично-рекурсивные и общерекурсивные функции. Операторы суперпозиции, примитивной рекурсии, минимизации. Вычислимость по Тьюрингу частично-рекурсивных функций. Тезис Черча и его интуитивное обоснование. II. Универсальные вычислимые функции и представления чрф. Реализация операторов программами машины Тьюринга. Универсальные вычислимые функции и интуитивные предпосылки к их существованию. Кодирования программ машины Тьюринга. Кодирование процесса работы машины Тьюринга. Программа, реализующая вычислимую функцию, универсальную для класса всех вычислимых функций одного аргумента. Эквивалентность подходов Тьюринга и Клини к вычислимости. Некоторые проблемы с кодированиями в подходе Клини. Варианты в подходе Клини. Различные варианты машин Тьюринга и их эквивалентность. Элиминация ограниченной минимизации. Различные формы рекурсии. Теорема Клини о нормальной форме. III. Нумерации и неразрешимость. Неразрешимые проблемы. Проблемы с определимостью класса всех общерекурсивных функций. Универсальные функции для классов вычислимых функций нескольких переменных. Понятие вычислимой нумерации. s-m-n-теорема. Существование некоторых вычислимых нумераций и теорема о неподвижной точке. Приложения теоремы о неподвижной точке. Теорема Райса. Формулировки некоторых неразрешимых проблем в терминах свойств программ. IV. Рекурсивно-перечислимые множества. Явления рекурсивной перечислимости и рекурсивного порождения. Формальные определения рекурсивной перечислимости и их эквивалентность. Псевдопараллельные вычисления. Рекурсивность и рекуривная перечислимость. Теорема Поста. Рекурсивные и рекурсивно-перечислимые предикаты. Канонические рекурсивно-перечислимые множества. Варианты теорем для рекурсивно-перечислимых множеств. V. Конечные автоматы и их основные свойства. Формализации и формальные системы. Языки и метаязыки. Определение конечных автоматов, их графическое изображение. Языки, распознаваемые конечными автоматами. Эквивалентность конечных автоматов и недетерминированных конечных автоматов. Замкнутость языков, распознаваемых конечными автоматами, VI. Формальные грамматики. Определение и примеры формальных грамматик. Контекстно--свободные и регулярные грамматики. Совпадение класса регулярных языков и языков, распознаваемых конечными автоматами. Алгоритмическая разрешимость множества слов контекстно--свободных языков. Замкнутость регулярных языков VII. Представления о сложности алгоритмов. Понятие абстрактной сложности. Общее свойство функций сложности вычислений. Теорема Блюм об ускорении. Сводимости и иерархии. Литература. [1] А.Н.Мальцев, Алгоритмы и рекурсивные функции, М., Наука, 1986. [2] Ю.Л.Ершов, Е.А.Палютин, Математическая логика, М., Наука, 1987. Программу составил к.ф.-м.н., доцент Ан.А.Мальцев