Шиханович Ю.А. - Минимум по теории алгоритмов для нематематиков

«Минимум по теории алгоритмов для нематематиков» /Шиханович Ю.А. – М.: Научный мир, 2011 – 160 с., ISBN 978-5-91522-055-2. Содержание книги основано на материалах лекций, которые автор читал студентам Отделения структурной и прикладной лингвистики филологического факультета МГУ им. М.В. Ломоносова и Отделения теоретической и прикладной лингвистики Российского государственного гуманитарного университета.

Предполагается, что читатель знаком с основными понятиями и фактами теории алгоритмов; требуется владение материалом книги Ю.А. Шихановича «Введение в математику» (Москва, Научный мир, 2005), термины и обозначения из которой часто используются в данной книге.

Излагаются самые общие начала теории алгоритмов – базисные понятия теории алгоритмов: предписание (исходное неопределяемое понятие), перечислимые множества (операции над перечислимыми множествами, существование неперечислимого множества, относительная перечислимость), алгоритмы (общее понятие, соотношение с перечислимыми множествами, каноническое задание программы алгоритма), вычислимые функции, разрешимые множества.

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

В дополнении описываются нормальные алгорифмы., рекурсивные функции и нумерационная теория алгоритмов.

Книга предназначена для студентов и аспирантов нематематических вузов, не требуя дополнительных знаний по высшей математике.