11. Использование метода ми для исследования алгоритмов (на примере обобщенного алгоритма Евклида).

Приведем общий алгоритм Евклида (EV)

Даны два числа m и n – целые положит-ные числа. Найти d=нод и а, b такие что а*m+b*n=d

Алгоритм пошаговой записи

EV1: [Начальная установка]

Положить а^|←b←1; а← b^|←0; c← m; d←n;

EV2: [разделить] Пустьq и ч являются соответственно: частное от деления c/d и остаток (имеем c=q*d+r, 0≤ч<d)

EV3: [r=0?] Если r=0, то алгоритм зак, раб, am+bn=d, если r≠0 то EV4

EV4: [Повторение цикла]

c← d; d← r; t← a^|; a^|←a; a←t-да; t←b^|; b^|←b; b←t-qb

Вернуться в EV2

Этот алгоритм похож на алгоритм Е, но дает больше возможностей, положит. коэффициент а,b.

Рассмотрим алгоритм Евклида для нахождения наибольшего общего делителя 2-х целых положительных чисел. Даны два целых положительных числа m и n.

Найти наибольший общий делитель:

Ш1. [Нахождение остатка]

Разделим m на n. Пусть остаток равен r (У нас получится 0≤r≤n)

Ш2. [остаток равен 0?]. Если r=0, то алгоритм заканчивается и n-является наибольшим делителем

Ш3. [Замещение]. Положим m←n, n←r и вернемся на Ш1

Пример. Пусть m=1769, n=551, найти a и b. am+bn=d. d- это НОД. Выполним все установки и проследим, как будут изменяться все переменные в алг-ме после шага EV2

a^’	a	b^’	b	c	d	q	r
1	0	0	1	1769	551	3	116
0	1	1	-3	551	116	4	87
1	-4	-3	13	116	87	1	29
-4	5	13	-16	87	29	3	0

am+bn=d=5*1769-16*551=29=d, a=5, b=-16, d=29

12. Недетерминированные и детерминированные алгоритмы.

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

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

Детерминированный алгоритм исследовал бы одну альтернативу, затем возвращался бы для исследования другой альтернативы и т.д.

Нд алгоритм:

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

Очевидно, что никакое физическое устройство не способно на неограниченную Нд работу.

Д етерминированный алгоритм (Дд)

Дд. алгоритмы являются абстракцией, которая позволяет игнорировать некоторые проблемы решения задач поиска с возвращением

Определяем класс NP как класс всех задач, которые можно решить Дд алгоритмами за полиномиальное время. Очевидно, что P NP т.к. путей может быть экспоненциально много, то алгоритмы, допустимые в этом случае намного сильнее, чем детерминированные алгоритмы, допустимые для задач класса Р.

NP-трудные и NP-полные задачи

Различные задачи, которые относятся и классу NP могут быть эквивалентными относительно некоторого отношения, которые определяем => обр.:

Опр. Задача Q полиномиально сводится к задаче R <=> выполн => условие

1. существует функция g(x) и f(x), вычисляемые за полиномиальное время

2. любого входа х частного случая задания Q значение g(x) является входом частного случая задания R

3. любые решения (выхода) у задания R значения f(y) является решением задачи Q

Т.о. для решения одной задачи (в данном случае Q) используется алгоритм решения другой задачи (в данном случае R)

Таким приемом часто пользуются при защите докторской диссертации

Опр. Если одновременно задача Q полиномиально сводится к задаче R и R полиномиально сводится к задаче Q, то Q и R полиномиально эквивалентны.

Опр. Задача называется NP – трудной (NP – сложной), если всякая задача из NP полиномиально сводится к данной.

Опр. Задача называется NP – полной, если она входит в NP и является NP – трудной