Направление в теории алгоритмов, в котором размеры программ, задающих алгоритмы, используются как средство исследования алгоритмических проблем, было основано А.А.Марковым в начале 60-х годов XX в. Сложностный метод А.А.Маркова позволяет расширить область применимости теорий, исследующих или использующих неразрешимые алгоритмические проблемы. Примерно в это же время А.Н.Колмогоров для исследований оснований теории информации и теории вероятностей начал создавать теорию, основанную на использовании минимальных размеров кодов алгоритмов. Марковское и колмогоровское направления теории сложности алгоритмов различались определениями основных понятий и изначально имели разное предназначение, но в процессе их развития произошло их сближение, поэтому их можно рассматривать как начала общей теории, использующей специфические методы исследований. В предлагаемой книге даются изложение основ этой теории и некоторые ее приложения. Книга адресована, в первую очередь,...
Napravlenie v teorii algoritmov, v kotorom razmery programm, zadajuschikh algoritmy, ispolzujutsja kak sredstvo issledovanija algoritmicheskikh problem, bylo osnovano A.A.Markovym v nachale 60-kh godov XX v. Slozhnostnyj metod A.A.Markova pozvoljaet rasshirit oblast primenimosti teorij, issledujuschikh ili ispolzujuschikh nerazreshimye algoritmicheskie problemy. Primerno v eto zhe vremja A.N.Kolmogorov dlja issledovanij osnovanij teorii informatsii i teorii verojatnostej nachal sozdavat teoriju, osnovannuju na ispolzovanii minimalnykh razmerov kodov algoritmov. Markovskoe i kolmogorovskoe napravlenija teorii slozhnosti algoritmov razlichalis opredelenijami osnovnykh ponjatij i iznachalno imeli raznoe prednaznachenie, no v protsesse ikh razvitija proizoshlo ikh sblizhenie, poetomu ikh mozhno rassmatrivat kak nachala obschej teorii, ispolzujuschej spetsificheskie metody issledovanij. V predlagaemoj knige dajutsja izlozhenie osnov etoj teorii i nekotorye ee prilozhenija. Kniga adresovana, v pervuju ochered,...
