Подробное описание документа

Шурыгин В. А.
   Сложностный метод теории алгоритмов / Шурыгин В. А. - М. : ЛИБРОКОМ, 2009. - 193 с. - Библиогр.: с. 187-190. - ISBN 978-5-397-00185-4.

Направление в теории алгоритмов,в котором размеры программ, задающих алгоритмы, используются как средство исследования алгоритмических проблем, было основано А.А. Марковым в начале 60-х годов XX В. Сложностный метод А.А. Маркова позволяет расширить область применимости теорий,исследующих или использующих неразрешимые алгоритмические проблемы.
Примерно в это же время А.Н. Колмогоров для исследований оснований теории информации и теории вероятностей начал создавать теорию,основанную на использовании минимальных размеров кодов алгоритмов.
Марковское и колмогоровское направления теории сложности алгоритмов различались определениями основных понятий и изначально имели разное предназначение, но в процессе их развития произошло их сближение, поэтому их можно рассматривать как начала общей теории,использующей специфические методы исследований. В предлагаемой книге даются изложение основ этой теории и некоторые ее приложения.
Книга адресована,в первую очередь, математикам, чья специализация связана с теорией алгоритмов,но она может быть интересной и более широкому кругу читателей для ознакомления с одним из новых направлений в теории алгоритмов.