Теория алгоритмов

Новосибирский государственный университет, С.Л. Березнюк. – 111 с. Содержание:
Общий обзор теории алгоритмов.
Алфавиты и языки.
Конечные представления языков.
Конечные автоматы.
Регулярные и нерегулярные языки
Минимизация числа состояний.
Контекстно-свободные грамматики и языки.
Нормальные алгорифмы Маркова.
Машины Шенфилда.
Частично вычислимые функции.
Кодирование конечных последовательностей.
Универсальные функции.
Вычислимые и вычислимо-перечислимые множества.
Проблема остановки.
Теорема о рекурсии и теорема Райса.
Машины Тьюринга (обзор результатов)
Вычислительная сложность.
Сводимость. Формат – PDF.