Программа лекций по курсу "Теория алгоритмов"


                 Введение

Исторический обзор. Основы теории множеств. Бинарные отношения.
Мощности множеств. Упорядочение числовых функций по скорости роста.

             Алфавиты и языки

Понятия алфавита и языка.
Конечные представления языков. Регулярные выражения. Регулярные
языки. 

               Автоматы и языки

Неформальное описание конечного автомата. Детерминированный конечный
автомат, его конфигурация. Язык, распознаваемый автоматом.
Недетерминированный конечный автомат, его конфигурация. Язык,
распознаваемый автоматом.

Теорема о существовании детерминированного конечного автомата,
эквивалентного данному недетерминированному. Теорема о замкнутости
класса языков, распознаваемых данным конечным автоматом, относительно
основных операций. Теорема о совпадении класса регулярных языков и
класса языков, распознаваемых конечными автоматами. Теорема о накачке.
Минимизация числа состояний автомата. Теорема Майхилла-Нероуда. Связь
регулярных языков и алгоритмов (детерминированный и
недетерминированный случаи).

Контекстно-свободные грамматики. Нерегулярные контекстно-свободные
языки. Теорема о замкнутости контекстно-свободных языков относительно
объединения, конкатенации и "звёздочки Клини". Теорема о контекстной
свободности регулярных языков.

                Способы формализации понятия алгоритма

Неформальное обсуждение свойств алгоритмов.  Нормальные алгорифмы Маркова.
Теорема о существовании композиции нормальных алгорифмов.

Определение частично вычислимых функций. Простейшие функции.
Операторы суперпозиции, минимизации, примитивной рекурсии. Всюду
определенные вычислимые функции. Кодирование последовательностей.
Лемма о совместной рекурсии.

Определение машины Шёнфилда и функций, вычислимых на ней. Макросы.
Теорема об элиминации макросов.

Теорема о совпадении классов функций, вычислимых на машинах Шёнфилда
и класса частично вычслимых функций. Тезис Чёрча. Универсальные
вычислимые функции. Теорема о неподвижной точке.  Теорема о
параметризации (s-m-n-теорема). Теорема Клини о нормальной
форме.  Несуществование всюду определенной универсальной вычислимой
функции.

Машины Тьюринга. Простейшие машины Тьюринга. Операции на машинах
Тьюринга и их свойства.

             Дальнейшие результаты о вычислимости

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

                 Вопросы сложности алгоритмов

Классы P и NP. NP-полные проблемы. Теорема Кука. Способы доказательства
NP-полноты.


Литература:

1)А.И.Мальцев "Алгоритмы и рекурсивные функции", М.: Наука, 1986.

2)Х.Роджерс "Теория рекурсивных функций и эффективная вычислимость",
М.: Мир, 1972.

3)А.С.Морозов "Машины Шёнфилда", Новосибирск, РИО НГУ, 1996.


                                      Программу составил
                                      к.ф.-м.н. С.Л.Березнюк