С.А. Абрамов - Лекции о сложности алгоритмов (pdf) (1123764)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

С. А. АбрамовЛекции о сложностиалгоритмовДопущено учебно-методическим советом по прикладной математикеи информатике УМО по классическому университетскомуобразованию в качестве учебного пособия для студентов высшихучебных заведений, обучающихся по специальности и направлению«Прикладная математика и информатика» и по направлению«Информационные технологии»МоскваИздательство МЦНМОУДК .ББК .AНаучный редакторЕ. А.

БордаченковаAАбрамов С. А.Лекции о сложности алгоритмов. — М.:. —  с.ISBN ----МЦНМО,В книге излагаются основные (начальные) разделы теории сложностиалгоритмов. Различаются алгебраическая и битовая сложности, каждая изкоторых рассматривается в худшем случае и в среднем. Ряд основных понятий теории сложности, как-то: оценки снизу и сверху, нижняя границасложности алгоритмов некоторого класса, оптимальный алгоритм и т.

д.,рассматривается не только в обычном функциональном, но и в асимптотическом смысле: асимптотические оценки, асимптотическая нижняя граница, оптимальность по порядку сложности и т. д. Показывается, что приисследовании существования алгоритма решения задачи, имеющего «неочень высокую» сложность, важную роль может играть сводимость однойзадачи к другой.Изложение сопровождается анализом сложности большого числа алгоритмов арифметики, сортировки и поиска, вычислительной геометрии,теории графов и др.Для студентов, специализирующихся в области математики и информатики.ББК .ISBN ----© Абрамов С. А., .© МЦНМО, .ПредисловиеПредлагаемая книга основана на курсе лекций, читаемых автором нафакультете вычислительной математики и кибернетики (ВМК) МГУим.

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

д., а не по тематическойпринадлежности рассматриваемых алгоритмов — сортировка, теорияграфов, арифметика и т. д. Для того, чтобы сосредоточиться именнона понятиях и подходах теории сложности, при этом не затрачиваяслишком много времени на объяснение деталей трудных для понимания алгоритмов, в примерах исследуются либо алгоритмы достаточноизвестные (сложностные характеристики которых менее известны),либо алгоритмы, суть которых может быть изложена коротко. Сложностные вопросы рассматриваются в книге довольно подробно, нокнига значительно уступает по широте охвата алгоритмического материала книгам Д.

Кнута [, , ], А. Ахо, Дж. Хопкрофта и Дж. Ульмана [], Т. Кормена, Ч. Лейзерсона, Р. Ривеста [], С. Баасе и А. ванГелдера [], Ж. Брассара и П. Берли [], в той или иной мере отражающих весь спектр вопросов построения алгоритмов, и книгам поспециальным алгоритмическим разделам математики — вычислительной геометрии (Ф. Препарата, М. Шеймос []), алгоритмической теории чисел (Э. Бах, Дж.

Шаллит []), комбинаторики (Э. Рейнгольд,Ю. Нивергельт, H. Део []) и др. Здесь надо сказать, что названнаялитература, как и некоторые другие издания, послужила источникомряда примеров и задач, предлагаемых в этой книге.В последних трех параграфах, касающихся классов P и NP, понятия NP-полноты и т. д., ряд фактов дается без доказательства. Этообъясняется тем, что в книге используются менее формальные модели вычислений, чем, скажем, машина Тьюринга, а доказательстваупомянутых фактов опираются на полностью формализованные мо-Предисловиедели.

Недостающие доказательства могут быть найдены, например,в [], [], [], [].В приложениях даются дополнительные сведения по затрагиваемым в основном тексте вопросам. Исключение составляют приложения A, G: в первом из них содержатся необходимые сведения о рядеалгоритмов сортировки и поиска, во втором — о методе решения линейных рекуррентных уравнений с постоянными коэффициентами;эти два приложения носят характер напоминания.Библиографические комментарии даются в сносках.Каждая из глав снабжена задачами для самостоятельного решения, среди которых помимо легких имеются и такие, которые углубляют материал главы, поэтому полезно по крайней мере прочитыватьусловия всех задач. Задача содержит указание к решению в тех, например, случаях (довольно редких), когда в основном тексте имеетсяотсылка к этой задаче.

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

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

А. Бордаченковой (ВМК МГУ) — научному редактору книги.ВведениеИсследование сложности алгоритма помогает понять степень егопрактической приемлемости. Сравнительный анализ сложности нескольких алгоритмов решения одной и той же задачи позволяет делатьобоснованный выбор лучшего из них. Например, если для решениязадачи предлагается новый алгоритм, то необходимы доводы, говорящие о его преимуществах в сравнении с известными ранее алгоритмами, и анализ сложности может предоставить такие доводы.Слово «сложность» в этом контексте является математическимтермином, а не общим обозначением препятствия к выполнению замысла.

С понятием сложности связываются затраты времени или памяти, соответствующие худшему случаю, либо затраты в среднем;при этом, чтобы обсуждать худший или «средний» случай, нужно,прежде всего, договориться, как определяется размер входа (размервходных данных) алгоритма и в чем измеряются затраты при работеалгоритма над фиксированным входом.Часто размер входа определяют как общее число символов в представлении входа, но возможны и другие пути.

В задачах сортировкии поиска размер входа — это, как правило, количество элементов nвходного массива, в задачах на графах — число вершин | V | или число ребер | E | входного графа G = (V , E), но, с другой стороны, | V |и | E | могут рассматриваться и совместно как два параметра размера входа.

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

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

В обоих случаях сложность алгоритма — это функцияразмера входа или, соответственно, нескольких параметров размеравхода. Для этого понятия иногда используется термин вычислительная сложность, чтобы избежать путаницы с описательной сложностью, которая тем или иным способом определяется исходя из самойзаписи (текста) алгоритма; одним из видов описательной сложностиявляется длина записи алгоритма, и именно так понятие сложноститрактуется в некоторых теориях  . Мы будем рассматривать тольковычислительную сложность, называя ее просто сложностью.Понятие сложности является математическим уточнением довольно расплывчатого термина «трудоемкость», с помощью которого, наряду с не более ясными «быстродействием» и «эффективностью», иногда пытаются характеризовать алгоритмы.

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

Характеристики

Тип файла PDF

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

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов лекций