7.Полиноминальные и экспоненциальные алгоритмы. Np-полные и np-трудные задачи.

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

Полиноминальным алгоритмом (­или алгоритмом полиноминальной временной сложности) называется алгоритм, у которого временная сложность определяется на основании полиноминальной функции, где n – входная длина. Остальные алгоритмы экспоненциальные. Различие указанных типов алгоритмов становится особенно заметно при решении задач большого размера.

NP-полные и NP-трудные задачи (not proof): Принцип деления алгоритмов на экспоненциальные и полиноминальные является выявлением сложно решаемых задач. Полиноминальные задачи – «хорошие», но некоторые задачи целочисленного прог-ия невозможно решить такими «хорошими» алгоритмами. Экспоненциальные алгоритмы нельзя считать «хорошими». Большинство экспоненциальных алгоритмов – это варианты полного перебора, в то время как полиноминальные алгоритмы обычно сложно построить лишь тогда, когда удается более глубоко проникнуть в сущность задачи. Имеется известное соглашение о том, что задача не считается решенной до тех пор, пока для нее не получен полиноминальный алгоритм. Поэтому задача называется трудно решаемой, если для ее решения нет полиноминального алгоритма. Это одна из трактовок трудно решаемая задача. Различие между алгоритмами может иметь другой характер, когда размеры решаемой задачи невелики, известны экспоненциальные алгоритмы, которые зарекомендовали себя на практике хорошо.

9.Наибольший общий делитель (нод). Алгоритм Евклида для нахождения нод.

Всякое целое, делящее 2 числа A и B называется их общим делителем. Наибольший из общих делителей для чисел А и В называется НОД. Ввиду конечного числа делителей данного числа существование и единственность НОД очевидны. Если НОД a и b =1, то a и b взаимнопростые. Найдем НОД для а и b:

Лемма 1: b/a  (a,b)=b {очевидно}.

Лемма 2: a=bq+r  (a,b)=(b,r).

Эти леммы лежат в основе алгоритма Евклида для нахождения НОД. Т.о. НОД – последний отличный от нуля остаток в алгоритме Евклида.

(175, 77)

175=77*2+21, 77=21*3+14, 21=14*1+7, 14=7*2 => r=7.

10.Взаимно-простые числа. Наименьшее общее кратное (нок).

Теорема (критерий взаимной простоты чисел): Два целых числа будут взаимно-простыми тода и только тогда, когда любой u и v, что au+bv=1. Доказательства: {Док-во вытекает из алг. Евклида. Необходимость:

r_n-2=r_n-1q_n+r_n

r_n=r_n-1q_n+r_n-2

r_n-1=…

В итоге получаем линейное разложение НОД: d=au+bv.

Достаточность вытекает из свойств делимости: (a,b)/a, (a,b)/b  (a,b)/au+bv=1  (a,b)=1. }

Из доказанного критерия взаимной простоты вытекают следующие свойства:

1. (a/b)=1, (a,c)=1  (a,b,c)=1;

2. a/bc, (a,b)=1  a/c;

3. a/c, b/c, (a,b)=1  ab/c.

НОК: Если a/M и b/M, то число MϵN называют общим кратным чисел a и b ϵ Z. НОК чисел a и b обозначается как [a,b]. Теорема 1: Если M – общее кратное чисел a и b, то НОК [a,b]/M. Доказательство: {Разделим с остатком M на [a,b]  M=[a,b]q+r. Ввиду того, что r=M-[a,b]q, имеем a[a,b]a/r, аналогично b/r. Поскольку 0≤r≤[a,b], то это возможно, только если r=0 }

Теорема 2: Справедливо следующее соотношение: [a,b]=ab/(a,b).