URSS.ru - Издательская группа URSS. Научная и учебная литература
Об издательстве Интернет-магазин Контакты Оптовикам и библиотекам Вакансии Пишите нам
КНИГИ НА РУССКОМ ЯЗЫКЕ


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

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

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]. Эта теория дает новые подходы к исследованию алгоритмических проблем; появление в ней теорем, относящихся не только к конкретным алгоритмическим проблемам, позволяет считать, что она выходит из стадии первоначального накопления фактов, это оправдывает (если не сказать: делает необходимым) систематическое изложение этой теории или ее основной части, и предлагаемая книга -- попытка такого изложения.

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

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

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

В.А.Шурыгин

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



 Об авторе

Виктор Афанасьевич ШУРЫГИН

Представитель научной школы А. А. Маркова в области конструктивного направления в математике.

Конструктивная математика основана не на теории множеств, однако целесообразно и в рамках конструктивной математики использовать аналоги понятия множества из классической математики. В качестве таких аналогов можно рассматривать множества конструктивных объектов (слов или натуральных чисел), для которых определено отношение эквивалентно сти (позволяющее эквивалентные элементы рассматривать как коды одного и того же элемента). Первые исследования В. А. Шурыгина в области конструктивной математики, по предложению А. А. Маркова, были связаны со свойствами алгорифмических отображений таких множеств, сохраняющих эквивалентность их элементов. Была введена классификация таких множеств, в основе которой - возможность построения алгорифмов, определенным образом связанных с рассматриваемыми множествами; она оказалась удобной для исследования общих свойств алгорифмических отображений, сохраняющих отношения эквивалентности. При этом были обнаружены и некоторые неожиданные свойства таких отображений.

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

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

В. А. Шурыгин - автор более 20 научных работ, опубликованных, главным образом, в изданиях Академии наук. Им написаны монографии "Основы конструктивного математического анализа" (URSS, 2004) и "Сложностный метод теории алгоритмов".

 
© URSS 2016.

Информация о Продавце