Абрамов С. А

A16 Лекции о сложности алгоритмов. — М.: МЦНМО,

2009.—256 с.

ISBN 978-5-94057-433-0

В книге излагаются основные (начальные) разделы теории сложности алгоритмов. Различаются алгебраическая и битовая сложности, каждая из которых рассматривается в худшем случае и в среднем. Ряд основных по­нятий теории сложности, как-то: оценки снизу и сверху, нижняя граница сложности алгоритмов некоторого класса, оптимальный алгоритм и т.д., рассматривается не только в обычном функциональном, но и в асимпто­тическом смысле: асимптотические оценки, асимптотическая нижняя гра­ница, оптимальность по порядку сложности и т. д. Показывается, что при исследовании существования алгоритма решения задачи, имеющего «не очень высокую» сложность, важную роль может играть сводимость одной задачи к другой.

Изложение сопровождается анализом сложности большого числа ал­горитмов арифметики, сортировки и поиска, вычислительной геометрии, теории графов и др.

Для студентов, специализирующихся в области математики и инфор­матики.

ББК 22.12

© Абрамов С. А., 2009.
ISBN 978 -5- 94057 - 433 -0 © МЦНМО, 2009.

Предисловие

Предлагаемая книга основана на курсе лекций, читаемых автором на факультете вычислительной математики и кибернетики (ВМК) МГУ им. М.В.Ломоносова. Ее цель — обсуждение основных понятий тео­рии сложности и некоторых методов анализа сложности алгорит­мов. Это обсуждение сопровождается подробным рассмотрением со сложностной точки зрения ряда алгоритмов арифметики, сортировки и поиска, вычислительной геометрии, теории графов и др. Матери­ал группируется по главам и параграфам в соответствии с раздела­ми самой теории сложности—сложность в худшем случае, сложность в среднем, нижние границы сложности и т.д., а не по тематической принадлежности рассматриваемых алгоритмов — сортировка, теория графов, арифметика и т. д. Для того, чтобы сосредоточиться именно на понятиях и подходах теории сложности, при этом не затрачивая слишком много времени на объяснение деталей трудных для понима­ния алгоритмов, в примерах исследуются либо алгоритмы достаточно известные (сложностные характеристики которых менее известны), либо алгоритмы, суть которых может быть изложена коротко. Слож­ностные вопросы рассматриваются в книге довольно подробно, но книга значительно уступает по широте охвата алгоритмического ма­териала книгам Д. Кнута [18, 19, 20], А. Ахо, Дж.Хопкрофта и Дж.Уль­мана [5], Т.Кормена, Ч. Лейзерсона, Р. Ривеста [21], С.Баасе и А.ван Гелдера [43], Ж.Брассара и П.Берли [46], в той или иной мере отра­жающих весь спектр вопросов построения алгоритмов, и книгам по специальным алгоритмическим разделам математики—вычислитель­ной геометрии (Ф. Препарата, М. Шеймос [30]), алгоритмической тео­рии чисел (Э.Бах, Дж. Шаллит [44]), комбинаторики (Э.Рейнгольд, Ю. Нивергельт, H.Део [31]) и др. Здесь надо сказать, что названная литература, как и некоторые другие издания, послужила источником ряда примеров и задач, предлагаемых в этой книге.

В последних трех параграфах, касающихся классов P и NP, по­нятия NP-полноты и т.д., ряд фактов дается без доказательства. Это объясняется тем, что в книге используются менее формальные мо­дели вычислений, чем, скажем, машина Тьюринга, а доказательства упомянутых фактов опираются на полностью формализованные мо-

Предисловие

дели. Недостающие доказательства могут быть найдены, например, в [4], [10], [13], [23].

В приложениях даются дополнительные сведения по затрагивае­мым в основном тексте вопросам. Исключение составляют приложе­ния A, G: в первом из них содержатся необходимые сведения о ряде алгоритмов сортировки и поиска, во втором — о методе решения ли­нейных рекуррентных уравнений с постоянными коэффициентами; эти два приложения носят характер напоминания.

Библиографические комментарии даются в сносках.

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

Автор благодарен своим коллегам по ВМК МГУ В. Б. Алексееву и В. П. Иванникову, а также Е. В. Зиме (университет Вилфрид Лауэр, Ва­терлоо, Канада) и М. Петковшеку (университет Любляны, Словения), беседы и дискуссии с которыми существенно помогли в отборе ма­териала и выработке общей схемы курса лекций и этой книги, при этом надо особо отметить, что Е. В. Зима принял участие в написании главы 6 и приложения D. Большая благодарность и А. В. Бернштей-ну (ИСА РАН), А.А.Васину (ВМК МГУ), В.А.Серебрякову (ВЦ РАН), сделавшим полезные замечания по ряду разделов книги. Автор при­знателен рецензентам М. H. Вялому (ВЦ РАН) и С. Б. Гашкову (мехмат МГУ) —их пометки на полях рукописи оказали значительную помощь на заключительном этапе работы над книгой. Особая благодарность за советы и многочисленные конструктивные замечания Е. А. Борда-ченковой (ВМК МГУ)—научному редактору книги.

Дата добавления: 2014-01-11