ТЕОРИЯ АЛГОРИТМОВ

Лектор: к.ф.-м.н. С.Л. Березнюк

1 семестр

Введение

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

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

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

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

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

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

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

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

Неформальное обсуждение свойств алгоритмов.

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

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

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

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

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

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

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

P- и NP-проблемы. Понятие абстрактной сложности. Теорема Блюм об ускорении.

Литература

1. Мальцев А.И. Алгоритмы и рекурсивные функции. М.: Наука, 1986.
2. Роджерс Х. Теория рекурсивных функций и эффективная вычислимость. М.: Мир, 1972.
3. Морозов А.С. Машины Шёнфилда. Новосибирск: РИО НГУ, 1996.