(см. сложность) Элементы теории сложности алгоритмов и вычислений. Хахаян (2010) ((см. сложность) Элементы теории сложности алгоритмов и вычислений. Хахаян (2010).pdf)

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТПУТЕЙ СООБЩЕНИЯ (МИИТ)Кафедра «Прикладная математика-2»В.Х. ХАХАНЯНЭЛЕМЕНТЫ ТЕОРИИ СЛОЖНОСТИАЛГОРИТМОВ И ВЫЧИСЛЕНИЙРекомендовано редакционно-издательским советомУниверситетав качестве учебного пособия для студентовспециальности АКБМОСКВА - 2010УДК510.633510.635510.557X 27Хаханян В.Х. Элементы теории сложностиалгоритмов и вычислений. Учебное пособие для студентовспециальности АКБ. Изданиевторое, сокращённое иисправленное, - М.: МИИТ, 2010. - 146 с.В пособии даётся изложение основных результатов по теориисложности алгоритмов и приводятся классификация классаразрешимых массовых проблем и примеры задач класса Р, класса NPи класса NP-полных задач.

Пособие рассчитано на студентовспециальности АКБ и соответствует программе читаемого по даннойспециальности курса «Сложность алгоритмов и вычислений».Рецензенты:кандидат физико-математических наук, доцент кафедрыматематической логики и теории алгоритмов механико­математического факультета МГУ им. М.В.ЛомоносоваВ.Н.Крупский и кандидат физико-математических наук,заведующий кафедрой «Вычислительная математика»(МИИТ) В.Н.

Деснянский.© Московский государственныйуниверситет путей сообщения(МИИТ), 2010ПРЕДИСЛОВИЕНастоящее учебное пособие имеет целью обеспечениеучебной литературой курса «Сложность алгоритмов»,читаемого для студентов специальности АКБ в V семестре.Пособие состоит из предисловия, введения и 6-ти глав, вкоторые входят основные понятия теории сложностиалгоритмов и вычислений. Необходимость написания данногопособия вызвана тем, что достаточно богатая литература потеории сложности содержит изучаемые сведения в оченьразбросанном для курса виде (переводные учебники явно неучитываютспецификии часовчитаемогокурса,отечественные же учебники и пособия не согласуются как счасами, выделенными на изучение курса, так и по программеи их изложение рассчитано в первую очередьнауниверситеты и пединституты).

Всё это вызывает серьёзныетрудности у студентов специальности АКБ при изученииданного курса, вызванные ещё и тем, что соответствующейучебной литературы по изучаемому курсу в библиотекеучебных пособий нет.Кратко содержание пособия можно описать так: вначалеидёт введение в специфику изучаемого предмета (Введение иГлава 1), затем определяются класс Р задач, решаемых заполиномиальное время на детерминированной машинеТьюринга (Глава 2) , класс NP труднорешаемых задач (Глава3), класс NP-полных задач (Глава 4), примеры NP-полныхзадач (Глава 5) и методы доказательства NP-полноты (Глава6). В конце пособия приводится список литературы,использованной автором при написании данного пособия.Необходимо отметить, что при написании пособия автор всильной степени использовал замечательную переводнуюкнигу (1), которая почти не устарела (из этой книги автор взялбольшие фрагменты цитат), пособия (4) и (5), написанные дляфакультета ВМК МГУ им.

Ломоносова, а также книгу (3)курса лекций, читаемых на механико-математическомфакультете МГУ им. Ломоносова и препринт (2).Содержание курса «Сложность алгоритмов» связано как сизучаемым в IV семестре курсом «Математическая логика итеория алгоритмов», так и с курсом по теории чисел,изучаемым в одном из последних семестров,которыйнепосредственновыводитизучающегоспециальностьстудентанасовременныйуровенькриптографии(криптосистема без передачи ключей, криптосистема соткрытымключом,электроннаяподписьи затемэкспоненциальный открытый ключ, дискретный логарифм;подробности см.

в (6)), при овладении которым необходимознать оценки сложности используемых алгоритмов.Автор надеется, что данное пособие закроет пробел встуденческой литературе по курсу «Сложность алгоритмов» ибудет полезно изучающим данный курс студентам.Во втором издании были исправлено ошибки и опечатки,расширены рисунки и сокращен текст для более полногосоответствия пособия часам читаемого курса.ВВЕДЕНИЕМатематика разрабатывает эффективные методы решенияшироких классов задач. Развитие теории и практики решениядискретных и комбинаторных задач показали, что общностьметода и его эффективность находятся в известномпротиворечии. Важно знать, можно ли в принципе надеятьсяна создание достаточно общих и эффективных методов илинужно идти по пути разбиения задач на всё более узкиеклассы и для этих классов разрабатывать эффективныеалгоритмы.Неудачи исследователей на этом пути привели кнеобходимостианализасложностизадач.Возниклоинтенсивно развивающееся «сложностное» направлениеисследований.

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

Но число шагов переборногометода растет экспоненциально в зависимости от размеровзадачи. Для ряда задач удаётся построить эффективныеметоды решения. Приведём несколько примеров.1. Арифметика остатков. Операции сложение и умножение вкольцах вычетов по модулю m вычисляются заполиномиальноевремя спомощьюцелочисленнойарифметики (для соответствующих доказательств см. (3)).2. Связность в графе.

В графе, заданном матрицей смежнос­ти, по заданным двум вершинам выяснить, связаны ли они.Нетрудно видеть, что задача сводится к вычислению степени пматрицысмежностей, аэтовычислениеимеетполиномиальную сложность, (для доказательства см. (3)).3. Вычисление степени числа (см. (2)).Алгоритм 1Тривиальное вычислениеу = хп mod mВход; Натуральные n, х, т > 1Выход: у = хп modm■У*~ 1for all i е l. ndoу <- у хх mod т {Деление по модулют каждый раз "не вредит"конечному резултату, т.к. кольцо Zmзамкнуто относительно умножения.}end forreturn уПриведённый алгоритм слишком прямолинеен и егоможно улучшить (сложность приведенного алгоритма есть0(п)). Для этого достаточно рассмотреть двоичное разложениечисла п:п=а*2? да а* е {0,1},и теперь заметить, чтокИтак, достаточно провести k < (logn + 1) итераций подвоичному разложению п, чтобы на каждой i-й итерации, взависимости от i-ro бита в разложении, проводить умножение,2®результата на сомножитель х, который легко получить изсомножителя предыдущей итерации (ключевое соотношение):Анализ же этого алгоритма показывает сложность 0(logп).

Разница в сложности экспоненциальна! Самостоятельноприведите алгоритм для вычисления степени числа (см. (2)).4. Аналогичная задача для вычисления п! имеет сложностьО(п) и неизвестно, можно ли улучшить (и на сколько!) этусложность(попробуйтесамостоятельнопривестисоответствующий алгоритм, см. также (2)).Следует отметить, что число таких задач, решаемых заполиномиальное «время», невелико. Как мы увидим далее,большинство встречающихся задач не удаётся решить спомощью полиномиальных алгоритмов.

Приведем примертакой задачи5. Дискретный логарифм. Пусть р - нечетное простое числои пусть для заданных а и Ъ выполняется соотношениеof = Ь mod р . Найти х.Эта задача обратная к задаче возведения в степень помодулю. Можем ли мы опять ожидать легкого решения?Оказывается нет, вычисление дискретного алгоритма являетсяочень сложной задачей. На этом важном свойстве (свойствеодностороннейвычислимостимодульнойэкспоненты)основано множество современных алгоритмов ассиметричнойкриптографии (также см.

(2) и (6)).6. Умножение 0-1 матриц. Для заданных матриц А и В,состоящих из 0 и 1, нужно вычислить их произведение. Если вкачестве операций разрешить только любые битовые, тосуществует алгоритм, перемножающий матрицы порядка п счислом таких операций 0(nl0g7log2n) (см., например, (4),стр.22-24, Теорема 3.1).Анализ трудностей, встретившихся на пути созданияэффективных методов решения дискретных задач, привел кпостановкецентральнойтеоретико-методологическойпроблемы - можно ли исключить перебор при решениидискретных задач? Речь идет о принципиальной возможностинайти нужное решение, не перебирая всех или почти всехвариантов в задаче.

Эта проблема имеет не только чистоматематическое, но и глубокое познавательное значение. Онозаключается в том, что при поиске эффективных точныхметодов решения широкого класса дискретных задач надоучитывать возможность отсутствия таких методов признав,что существуют «труднорешаемые задачи». До настоящеговремени эта проблема остается открытой.Феномен труднорешаемых задач не нов для математики.После уточнения понятия алгоритма было обнаруженоналичие алгоритмически неразрешимых проблем. В качествеизвестного примера укажем десятую проблему Гильберта:«Существует ли алгоритм, который по данному многочленур(хь ...,хп) с целыми коэффициентами распознает, имеет лиуравнение р = 0 решение в целых числах».

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

Роль основного инструмента играет понятиесводимости задач, возникшее в математической логике.Переборная задача П 1 сводится к переборной задаче П2, еслиметод решения задачи Г12 можно преобразовать в методрешения задачи Г1]. Сводимость называется полиномиальной,если подобное преобразование можно осуществить заполиномиальное время. Главными объектами теорииявляются: класс NP всех переборных задач и класс Рпереборных задач, разрешимых за полиномиальное время намашине Тьюринга. Очевидно, что Р с NP.

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