Когабаев Н.Т. Другие лекции по теории алгоритмов

Учебное пособие. — Новосибирск: мех.-математический факультет, Новосиб. гос. ун-т, 2015. — 73 с.В настоящем учебном пособии изложены математические основы теории алгоритмов. Пособие отражает содержание лекций основного курса «Дискретная математика и теория алгоритмов» для студентов 1-го курса механико-математического факультета НГУ и охватывает материал из нескольких областей математики, так или иначе связанных с понятием алгоритма: теория автоматов и регулярных языков, машины Тьюринга и частично рекурсивные функции, классическая теория вычислимости.
Предназначено для студентов 1-го курса механико-математического факультета НГУ, изучающих курс «Дискретная математика и теория алгоритмов», а также для всех желающих познакомиться с основами упомянутых в пособии математических теорий.Предварительные сведения
Некоторые аксиомы теории множеств
Алфавиты и формальные языки
Элементы комбинаторики
Конечные автоматы и формальные грамматики
Детерминированные конечные автоматы
Недетерминированные конечные автоматы
Недетерминированные конечные автоматы с пустыми переходами
Свойства автоматных языков
Регулярные выражения и языки
Формальные грамматики
Формализация понятия вычислимой функции
Определение машины Тьюринга
Базовые машины Тьюринга
Частично рекурсивные функции
Рекурсивность некоторых функций и отношений
Кодирование машин Тьюринга
Машины Тьюринга vs Частично рекурсивные функции
Универсальные функции
Теория вычислимости
Теорема о параметризации
Теорема о неподвижной точке
Вычислимо перечислимые множества