Обложка Шурыгин В.А. Сложностный метод теории алгоритмов
Id: 57051
350 руб.

Сложностный метод теории алгоритмов

URSS. 2009. 200 с. ISBN 978-5-397-00185-4.
  • Мягкая обложка

Аннотация

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

Примерно в это же время А.Н.Колмогоров для исследований оснований теории информации и ...(Подробнее)теории вероятностей начал создавать теорию, основанную на использовании минимальных размеров кодов алгоритмов.

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

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


Оглавление
Предисловие
 § 1.Введение
 § 2.Обзор теории нормальных алгорифмов
 § 3.Оценки сложности алгорифмических проблем
 § 4.Некоторые общие теоремы об оценках сложности проблем распознавания
 § 5.Оценки сложности проблемы распознавания применимости нормальных алгорифмов к словам
 § 6.Инвариантная (минимальная) сложность нормальных алгорифмов
 § 7.Некоторые оценки сложности нормальных алгорифмов, свя-занных с продуктивными множествами нормаль-ных алгорифмов
 § 8.Оценки сложности проблемы распознавания инвариант-ных свойств нормальных алгорифмов
 § 9.Об оценках сложности нормальных алгорифмов, распознающих полноту нормальных алгорифмов
 § 10.Оценки сложности проблемы распознавания эквивалентности нормальных алгорифмов
 § 11.Оценки сложности проблемы распознавания подобия нормальных алгорифмов
 § 12.Основные теоремы об алгорифмических проблемах, не имеющих верхних оценок сложности
 § 13.Примеры алгорифмических проблем, не имеющих верхних оценок сложности
 § 14.Сложность алгорифмов и время их работы
 § 15.Об алгорифмах, связанных с булевыми функциями
 § 16.Некоторые применения теории сложности алгорифмов в конструктивном математическом анализе
 § 17.Определение сложности конструктивных объектов в теории А.Н.Колмогорова
Литература
Готический шрифт в обозначениях нормальных алгорифмов
Указатель обозначений
Указатель терминов

Предисловие

В математической литературе термин сложность алгоритма используется, по крайней мере, в двух смыслах, которые можно передать словами сложность вычислений, задаваемых алгоритмом, и сложность описания алгоритма. Здесь термин сложность алгоритма используются во втором из названных смыслов; точнее говоря, он обозначает размеры наборов знаков, которыми задаются алгоритмы при определенном способе их записи.

Истоками представленной в этой книге теории следует считать работы А.А.Маркова [2] и А.Н.Колмогорова [4]. Эта теория дает новые подходы к исследованию алгоритмических проблем; появление в ней теорем, относящихся не только к конкретным алгоритмическим проблемам, позволяет считать, что она выходит из стадии первоначального накопления фактов, это оправдывает (если не сказать: делает необходимым) систематическое изложение этой теории или ее основной части, и предлагаемая книга -- попытка такого изложения.

В теории сложности алгоритмов объекты изучения -- алгоритмы -- должны допускать запись в стандартной форме, например, определенной в какой-нибудь из хорошо развитых теорий алгоритмов. Здесь в основу изложения взята теория нормальных алгорифмов А.А.Маркова.

Многие из представленных здесь результатов были опубликованы в изданиях Академии Наук СССР. Почти все заимствованные теоремы здесь даны с иными доказательствами, чем в первоисточниках. Изменения в доказательствах вызваны стремлением изложить весь материал в едином стиле, стремлением показать возможность применения некоторых общих методов теории сложности алгорифмов в исследовании различных по характеру алгорифмических проблем, а также стремлением изложить материал без ссылок на факты, которые могут быть не известны тем читателям, чья узкая специализация не связана с теорией рекурсивных функций; кроме того, заменяя авторские доказательства из первоисточников новыми доказательствами, я исходил также из того, что новые доказательства известных теорем могут представлять определенный интерес. Здесь, за редкими исключениями, нет пометок, указывающих, что та или иная теорема приведена в первоисточнике без доказательства или что приводимое здесь доказательство отличаются от авторского, и ответственность за все приведенные здесь доказательства я беру на себя.

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

В.А.Шурыгин

Снежинск, Челябинская обл.