- •1. Понятие сложности алгоритма. Верхняя, нижняя и средняя оценки сложности.
- •2 . Основные правила вычисления сложности алгоритма (сложность линейного алгоритма, ветвления, цикла). Примеры
- •3. Реккурентные соотношения с постоянными коэффициентами
- •4. Анализ сложности рекурсивных алгоритмов. Примеры.
- •9. Понятие полиномиальной сводимости. Класс npc. Примеры np-полных задач.
- •12. Задачи оптимизации и задачи принятия решения (распознавания). Задачи, np-полные в сильном и слабом смыслах. Примеры.
- •13. Приближенные алгоритмы для задачи об упаковке в контейнеры.
- •14. Приближенный алгоритм для евклидовой задачи коммивояжера.
- •15. Разрешимые и неразрешимые проблемы, невычислимые функции. Примеры.
- •17. Задача о максимальном паросочетании. Волновой алгоритм.
- •19. Задача о нахождении минимального расстояния между всеми парами вершин. Алгоритм Флойда.
- •20. Задача о максимальном потоке. Остаточная сеть. Аугментальный (увеличивающий) путь. Алгоритм Форда-Фалкерсона.
- •21. Задача о максимальном потоке минимальной стоимости (МаПМиС). Алгоритм решения.
- •22. Метод ветвей и границ. Решение задачи «о рюкзаке» методом ветвей и границ.
- •23. Метод ветвей и границ. Решение задачи коммивояжера.
4. Анализ сложности рекурсивных алгоритмов. Примеры.
Алг(х)
if(условие)
thenрекурсивная ветка
elseтривиальная ветка
рекурсивная ветка – алг(y), гдеy=f(x)
вызов + доп. операции
Пусть tα(x) – сложность алгоритма на входных данныхx.
Пусть тривиальная ветка выполняется при входных данных s:
Пример:
n!=n(n-1)!
function F(n: integer): integer;
begin
if n>1
then F:=n* F(n-1)
else F:=1;
end;
;
s=1;
;
Ответ:
6. Решение рекуррентных соотношений вида T(n)=aT(n/d)+bnk, T(1)=C0 (без вывода). Сложность рекурсивного алгоритма быстрой сортировки.
, вместоперейдем к
Быстрая сортировка
procedure Qsort (m: mas; n, l, r: integer);
var mid, t, i, j: unteger;
begin
i:=l; j:=r;
mid:=m[(l+r) div 2];
while i<=j do
begin
while m[i]<mid
do i:=i+1;
while m[j]>mid
do j:=j-1;
if i<=j then
begin
t:=m[i];
m[i]:=m[j];
m[j]:=t;
i:=i+1; j:=j-1;
end;
end;
if j>l then Qsort(m,n,l,j);
if i<r then Qsort(m,n,i,r);
end;
-------------------------------------
1. нижняя оценка сложности
Недетерминированная машина Тьюринга. Класс NP (два определения).
Машина Тьюринга состоит:
Бесконечная лента
Головка, которая двигается по ленте
Программа МТ
Каждой паре q(i)a(j) ставится в соответствииq(k)a(s)d(r) (d- направление), причем однозначно (свойство детерминированности)
НМТ: каждой паре q(i)a(j) ставится в соответствии множество троек:
Заранее невозможно сказать по какому правилу пойдет. В каждой момент некоторым образом выбирается одна тройка из множества.
Условие задачи: выбирать вариант, который приведет к правильному решению. Необходимо, чтобы какой-то механизм подсказывал для выбора правильного варианта.
Механизм должен показать цепочку, чтобы был правильный результат.
Определение класса NP:
Задача Т принадлежит классу NP, если Т может быть решена за полиномиальное время на НМТ.
NP– недетерминированный, полиномиальное время.
Задача T, если ее можно подставить в виде:, гдеq() – полином;R(x,y);y- дополнительные данные.
Пример задач, принадлежащих классу NP:
Задача коммивояжера
Задача «об упаковке в контейнеры»
9. Понятие полиномиальной сводимости. Класс npc. Примеры np-полных задач.
Пусть есть задача А с входными данными из множества х1 и выходными данными из множества у1 и есть задача В, которая переводит х2 в у2
Если существует задачи Т1: х1->x2;T2:y2->y1, такие что:
Для любых х x1T2(B(T1(x)))=A(x)
T1,T2, то говорят, что задача А полиноминально сводима к задаче В:
Свойства полиномиальной сводимости:
Если Ви, то А. Доказательство из определения п.1
Если АPи, то ВР. Доказательство от противного.
Если Bи, то А. Верно обратное, доказательство аналогично.
Если ,, то
Пример: НОК (a,b)
Задача:
А – нахождение НОК
В – нахождение НОД
Т1- тождественное преобразование
Т2 – вычисление по формуле
Класс NPC
Задача Т , если:
T
Для любых T’
P<>NP
Если Р=NP=NPC
Принадлежность задачи к Р: алгоритм, решающий эту задачу за полиномиальное время.
Принадлежность к классу NPC:
Утверждение: Пусть есть задача T0, если задачаTи задача, то задачаT
T0 =>=> T
Доказательство принадлежности к NP:
Из определения
Строго говоря, понятие класса NPвводится только для задач принятия решений
Примеры NP-полных задач:
Задача о минимальном вершинном покрытии
Задача о рюкзаке