Программа курса ''Теория алгоритмов" для I курса ММФ НГУ
    (I семестр)

   I. Основные понятия вычислимости.

   Некоторые положения, приведшие к развитию формальной теории
алгоритмов.
   Языки формулирования понятия алгоритма. Причины выбора функций на
натуральных чисел в качестве области для формулировки понятия
вычислимости.
   Машина Тьюринга.
   Примеры.
   Последовательный запуск программ. 
   Макросы для машины Тьюринга. 
   Примеры применения макросов.
   Определение вычислимости по Клини. Частично-рекурсивные и
общерекурсивные функции.
   Операторы суперпозиции, примитивной рекурсии, минимизации.
   Вычислимость по Тьюрингу частично-рекурсивных функций.
   Тезис Черча и его интуитивное обоснование.

   II.  Универсальные вычислимые функции и представления чрф.

   Реализация операторов программами машины Тьюринга.
   Универсальные вычислимые функции и интуитивные предпосылки к их
существованию.
   Кодирования программ машины Тьюринга.
   Кодирование процесса работы машины Тьюринга.
   Программа, реализующая вычислимую функцию, универсальную для класса
всех вычислимых функций одного аргумента.
   Эквивалентность подходов Тьюринга и Клини к вычислимости.
   Некоторые проблемы с кодированиями в подходе Клини.
   Варианты в подходе Клини.
   Различные варианты машин Тьюринга и их эквивалентность.
   Элиминация ограниченной минимизации.
   Различные формы рекурсии.
   Теорема Клини о нормальной форме.

    III. Нумерации и неразрешимость.

   Неразрешимые проблемы.
   Проблемы с определимостью класса всех общерекурсивных функций.
   Универсальные функции для классов вычислимых функций нескольких
переменных.
   Понятие вычислимой нумерации.
   s-m-n-теорема.
   Существование некоторых вычислимых нумераций и теорема о неподвижной
точке.
   Приложения теоремы о неподвижной точке. Теорема Райса. Формулировки
некоторых неразрешимых проблем в терминах свойств программ.

    IV. Рекурсивно-перечислимые множества.

    Явления рекурсивной перечислимости и рекурсивного порождения.
    Формальные определения рекурсивной перечислимости и их
эквивалентность. Псевдопараллельные вычисления.
    Рекурсивность и рекуривная перечислимость. Теорема Поста.
    Рекурсивные и рекурсивно-перечислимые предикаты.
    Канонические рекурсивно-перечислимые множества.
    Варианты теорем для рекурсивно-перечислимых множеств.
    
    V.  Конечные автоматы и их основные свойства.

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

    VI.  Формальные грамматики.

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

   VII.  Представления о сложности алгоритмов.

   Понятие абстрактной сложности.
   Общее свойство функций сложности вычислений.
   Теорема Блюм об ускорении.
   Сводимости и иерархии.

   
    Литература.

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