Сложностный метод теории алгоритмов
Оформить заказ
Автор:Шурыгин В.А.
Издательство:Либроком
Страниц:200
Год:2009
Обложка:Мягкий переплет
Размер:60x90/16
SKU:RU340504
ISBN:9785397001854
Наша цена:US $37.00
Пункты выдачи магазин ТРОЙКА
Отправка почтой: June 16th от US $12.00, бесплатно при заказе от US $100.00.
Точная стоимость доставки будет рассчитана при оформлении заказа.
Направление в теории алгоритмов, в котором размеры программ, задающих алгоритмы, используются как средство исследования алгоритмических проблем, было основано А.А.Марковым в начале 60-х годов XX в. Сложностный метод А.А.Маркова позволяет расширить область применимости теорий, исследующих или использующих неразрешимые алгоритмические проблемы.Примерно в это же время А.Н.Колмогоров для исследований оснований теории информации и теории вероятностей начал создавать теорию, основанную на использовании минимальных размеров кодов алгоритмов.Марковское и колмогоровское направления теории сложности алгоритмов различались определениями основных понятий и изначально имели разное предназначение, но в процессе их развития произошло их сближение, поэтому их можно рассматривать как начала общей теории, использующей специфические методы исследований. В предлагаемой книге даются изложение основ этой теории и некоторые ее приложения.Книга адресована, в первую очередь, математикам, чья специализация связана с теорией алгоритмов, но она может быть интересной и более широкому кругу читателей для ознакомления с одним из новых направлений в теории алгоритмов.