Методические указания к курсу ”Сложность вычислений” (стр. 18 )

O(n3),  так  что  общее  время  –  O(n 4).

  Построенный  недетерминированный  алгоритм  полиномиален  вдоль  каждой  ветви,  кроме  шага  3.  Рассмотрим  рекурсивное  вычисление  на  шаге  3,  представив  его  в  виде  дерева,  в  корне  которого  находится  n-битовое  число  p,  сыновьями  являются  угаданные  сомножители  числа 

p-1,  под  каждым  q i  угадываемые  сомножители  числа  q i –1,  которые  также  надо  проверить  данной  рекурсивной  процедурой,  и  т. д. -  до  листьев,  состоящих  не  более,  чем  из  2 бит.

  Произведение  сыновей  меньше  самого  узла,  тем  более  меньше  p.

Время  работы,  выполняемой  для  узла,  исключая  работу  в  рекурсив - ных  вызовах,  оценивается  как  a. (log2 i)4,  для  некоторой  константы  a. Верхнюю оценку  для  любого  уровня  j  можно  получить  суммировани ем  по  узлам,  и  так  как  соответствующие  узлам  угаданные  сомножите ли  составляют  произведение,  не  большее  p-1, то  суммы ограничены  сверху  a (log2 p)4,  что  не  превосходит  an4. 

  Итак,  время  работы  на  каждом  уровне  O(n 4),  не  более  n,  общее  время  работы  на  каждой  ветке  O(n5).

Тема 6.  Приближенные  алгоритмы.

Самостоятельные занятия

[5], глава 7, § 37.

  Приближенные  алгоритмы

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

  Система  оценок  приближенных  алгоритмов:

Для  оптимизационных  задач  можно  говорить  о  решении  с  ошибкой  не  более, чем  в  ρ(n)  раз.  Если  C* - оптимальное  решение,  а  C – приближенное,  то  должно  выполняться  неравенство  1≤  max (C/C*, C*/C) ≤  ρ(n).

Иногда  качество  алгоритма  оценивают  через  относительную  ошибку

⎜C – C*⎥ / C ≤  ε (n)  для  входа  длины  n.

Для  некоторых  задач  ρ, ε  не  зависят  от  длины  входа  n,  в  других  случаях  приходится  довольствоваться  алгоритмами,  в  которых  оценка  ошибки  растет  с  ростом  n.

Иногда  можно  улучшить  качество  приближения,  увеличив  время  работы  алгоритма,  которое  будет  ограничено  полиномом  p(n, 1/ε),  где  n - длина  входа  и  ε - оценка  относительной  ошибки.

  Далее  рассматриваются  полиномиальные  приближения  для  трех  NP-полных  задач  с  разными  оценками  качества  приближенных  алгоритмов.

Задача  о  вершинном  покрытии 

  Напомним,  что  вершинным  покрытием  неориентированного  графа 

G = (V, E)  называется  множество  V ’ ⊆ V,  что  для  каждого  ребра  (u, v)  графа  G  по  крайней  мере  один  из  концов  u, v  принадлежит  V ’. Размером  вершинного  покрытия  считается  количество входящих  в него вершин. Задача о вершинном  покрытии  состоит  в нахождении  оптималь ного  вершинного  покрытия,  т. е.  вершинного  покрытия  минимального  размера.  С  алгоритмом  AVC (рис. 37.1) можно  найти  вершинное  покры тие,  которое  хуже  оптимального  не  более  чем  в  2  раза.

AVG (G)

V’ ← ∅ E’  ← ∅ while  E’ ≠ ∅   do  возьмем  произвольное  ребро  {u, v}  из  E’   C ← C ∪ {u, v}   удалим  из  E’  все  ребра,  инцидентные  u  или  v return  C

Работа  алгоритма  AVC: Из  множества  E’,  которое  сначала  совпадает  с  E,  выбирается  ребро  (u, v) и  его  концы  добавляем  в  множество V ’,  которое  сначала  пусто.  После  чего  из  E’  удаляются  все  ребра,  инци - дентные  u  или  v.  Цикл  продолжается,  пока  E’ ≠∅.  Время  работы  алгоритма  O(E). 

Теорема.  Алгоритм  AVG  работает  с  ошибкой  не  более  чем  в  2  раза. 

Доказательство. 

Заключение.  Приложения  теории  сложности  в  практике  программирования  и  в  криптографии. 

Вопросы  сложности  вычислений  лежат  в  основе  криптографических  методов  Надежность  шифров  базируется  на  уверенности, что  дешифро вание  является  труднорешаемой  задачей.  Так  безопасность  шифров,  основанных  на  RSA-схеме,  гарантируется  невозможностью  разложить  целое,  равное  произведению  двух  больших  простых  чисел,  за  полино миальное  время.  Проблема  принадлежит  классу  NP.  Полной  гарантией  безопасности  было  бы  принадлежность  языка  простых  чисел  или  языка  составных  чисел  к  NP-полным  классам,  но  равенство  NP=co-NP  сомнительно.  Более  того,  доказано, что  язык  простых  чисел  принадле - жит  классу  RP,  так  что  NP-полнота  языка  простых  чисел  приводила  бы  к  равенству  RP=NP,  что  тоже  маловероятно.

  Есть  основание считать, что не существует  способа  разложить  состав - ное  число  на  простые  множители  за  полиномиальное  время  даже  с  использованием  рандомизированного  алгоритма.  Если  бы  это  предполо жение  было  неправильным,  основанные  на  таком  разложении  крипто - графические  методы  были  бы  небезопасны  для  применения.

Перечень  основной и дополнительной  литературы

1..  Дж. Хопкрофт, Рад. Мотвани, Дж. Ульман. Введение  в  теорию  автоматов, языков  и  вычислений. Пер. с англ.-М.: Издательский дом “Вильямс”,2002

2.  . Лекции  по  арифметическим  алгоритмам  в  криптографии. М.:МЦНМО,2002.

3. А. Н..Гамова.  Математическая логика  и  теория  алгоритмов.

  Учебное  пособие. Изд-во СГУ,3-е  изд., дополненное. Саратов, 2005.

4.  А. Ахо, Дж. Хопкрофт, Дж. Ульман. Построение и анализ вычислительных алгоритмов. М.:Мир,1979.

5.  Т. Кормен, Ч. Лейзерсон, Р. Ривест. Алгоритмы: построение и анализ.- М.: МЦНМО, 2001.

6.  Н. Катленд. Вычислимость. Введение в теорию вычислимых функций: Пер. с англ.- М.: Мир,1983.

7.  Н. Вирт. Алгоритмы и структуры данных: Пер. с англ.- СПб.: Невский Диалект, 2001.

8  .. С/C++.Программирование на языке высокого уровня.- СПб.:Питер, 2002.

9. , , . Объектно-ориентированное  программирование. М.: Изд-во МГТУ имени ,2000

1) Здесь  не  приводятся