Алгоритмы Маркова(АМ)
Правила подстановки одних символов вместо других
a->bc
ab->bc     			abc -> bcbc -> bac -> ba -> bbc -> bb
c->ε
cb->a
Нормальный алгоритм Маркова позволяет решать задачу демермизированно.Нормальный алгоритм Маркова предполагает четкое упорядочивание правил подстановки. Для подстановки всегда выбирается первое подходящее правило.
Среди правил должно быть такое с правой части которого имеется (●). Правила без точки – простые правила замены(подстановки), а правила с точками – конечные правила подстановки. Работа алгоритма заканчивается в след. cлучаях: 1)если на каком-то шаге замен применилось правило с (●) в правой части (α->.β). Это называется результативный останов;2)входное слово просмотрено до конца и не удалось применить ни одно из правил – нерезультативный останов;3)зацикливание алгоритма Маркова.
	Доказано, что машина Тьюринга и нормальные алгоритмы Маркова близки и их использование приводит к одинаковым результатам.
Состояние МТ Q0aba
Q0a->Q1bR			ba1ba
Q0a->Q1bR
Q0a->bQ1
Q0b->Q2aU
Q0b->Q2a
Q1b->Q2aL
Тюринг: (Q0)ab->(Q1)bb->Q2ba
Марков: Q0ab->bQ1b->b1a->ba
		Самоприменимость алгоритмов Маркова
-набор правил можно поедставить в виде входного слова.
Если процесс обработки вх.слова(который явл. Описанием алг-ма Маркова) останавливается,то такой алгоритм называется самоприменимым. Доказано: задача – является ли алгоритс самоприм. или несамоприм. -неразрешима.

Рекурсивные функции и эффективная вычислимость.
ЧФ(частичная функция) является вычислимой , если её значения можно определить посредством некого алгоритма.
Если нек.элем.мн-ва Х ставится в соотвествие однозначно определённых элементов мн-ва У,то говорят , что задана частичная функция из Х в У.Совокупность эл мн-ва Х, у которых есть соотв. им элементы в мн-ве У называют областью определения функции из Х в У. А совокупность соответств.знач. У называются областью значений функции из Х в У.
Если обл.определения совпадает с мн-вом Х,то функция называется всюду определённой функцией .
Весь набор входных слов можно представить как мн-во Х, а выходных – У. И если поставить эти мн-ва в соответствие , то задаётся функция y=f(x)
Рекурсия – способ задания функции , при котором значение определяемой функции для произвольных значений её элементов определяется известным образом через значение определ. функции для меньших значений аргумента.
(n+1)! = 1 * 2 * 3 * 4 * 5 * … * k * … * (n-2) * (n-1) * n * (n+1) = (n+1) * n!
Вводятся понития элементарных первичных функций . Первичную нельзя получить из других функций . Из первичных функций путём комбинаций можно строить другие функции.
Всего выделяют 3 первичные функции:1)Ф.тождественно = 0(Ф.константы “ноль”)O^n=f(x1,x2)=0; 2)Ф. Тожденства,повторяющ. Значения своих аргументов(выбора арг.,проекции) (I^n)i {итое} = f(x1,x2…xn)=xi ||| Частный случай ||| (I^1)I {итое} = f(x) = x; 3) Функции непосредственного следования (“последователь”) S^1 = f(x) = x+1
				Операции для построения новых функций:
1)	Суперпозиции(подстановки)
2)	Примитивной рекурсии
3)	Минимизации
Операция подстановки(1)
Заключается в том, что вместо каких-то переменных функций подставляются другие функции от тех же или иных переменных. Пусть заданы n Ф: f1,f2,f3…fn от m переменных каждая. Операцией суперпозиции f1…fn с функцией f будет порождена новая. А также функция f от n переменных (x1,x2…xn).
Функция g(x1,x2,x3,…,xm)=f(f1(x1,x2,…,xm),…fn(x1,…,xm))
Пример 1.Суперпозиция   				Пример 2: f(x) = x + 1;
f(x) = 0   g(x)=x+1					g(y) = y+1;
h(x) = g(f(x)) = g(0) = 0 + 1 = 1;				h(y)=f(g(y))=f(y+1)=(y+1)+1=y+2;
Суперп. F(x)=x+1 с самой собой : h(y) = y +2;
	Операция примитивной рекурсии и определ. примитивно рекурсивной Ф
Представим эту операцию в общем виде : она позволяет строить n+1-мест. Функцию на основании известных n-местных и n+2-местной функции .
Пусть задана n-местная функция g и n+2-местная функция h. Говорят , что n+1-местная функция f возникает примитивной рекурсией из g и h , если для всех натуральных значений (х1,х2...хn,y) справедливы соотношения:
f(x1,x2,…xn,0)=g(x1,x2…xn)
f(x1,x2,…xn,y+1)=h(x1,x2…xn,y,f(x1,x2…xn,y))
Доказано , что для каждых g и h существует функция f и она является единственной , что записывается Rn(g,h)
При этом для вычисления значения f в конкретной точке является чисто механической процедурой , выполняемой по строго определённым правилам . Т.е. для нахождения значений достаточно последовательно найти числа
   b0 = g(a,a2,…,an) b1=h(a1,a2…an,0,b0) b2= h(a,a2,…,an,1,b1)
    		bm+1 = h(a,a2,…,an,m,bm)
Заметим , что если считать const – функцией от нуля переменных , то можно определить одноместную функцию f , которая возникает примитивной рекурсией из a и двуместной частичной функцией h в виде f(□,y+1)=h(□,y,f(□,y)) или , сокращая :
f(0) = a
f(y+1) = h (y,f(y))
Это и есть примитивное определение функции через операцию рекурсии. Примитивная рекурсия , т.к. по одной переменной с шагом 1.
Пример 1: Построить с помощью рекурсии двуместную функцию суммирования.
f+( x , y ) = x + y;
Отметим , что прибавить y к x – то же , что прибавить 1 к x y-раз.
Искомая функция определ. на основе тождеств. функц. g(x) = x и функций непосредственного следования h(x,y,z) , которая вычисл. как z+1
Результат: (ПОРЯДОК)
1f+(x,0) = g(x) = x; 			     4f+(x,y-1) = h(x , y-2 , f+(x,y-2)) = h(x , y-2 , x+y-2) = x + y -1;
2f+(x,1) = h(x , 0 , f+(x,0)) = h(x , 0 , x) = x+1;5f+(x,y) = h(x , y-1 , f+(x,y-1)) = h(x , y-1 , x + y – 1) = x + y;
3f+(x,2) =h(x,1 ,f+(x,1)) =h(x,1,x+1)=x+2;6f+(x,y+1)=h(x,y,f+(x,y)) = h(x,y,x+y)=(x+y)+1=f+(x,y)+1=S’(f+(x,y))

Определение
Функции , которые могут быть построены из первичных с помощью операций суперпозиции и\или примитивной рекурсии , примененных любое кол-во раз в произвольной последовательности , называются примитивно-рекурсивными функциями.
Эти же операции , прим. К всюду определённым Ф , дают также всюду опр. Ф
Для того , чтобы показать , что Ф является примитивно-рекурс. , достаточно построить её согласно определению. Однако такое построение получается слишком сложным , поэтому в большинстве случаев вункцию пытаются выразить с помощью операций суперпозиции и примитивной рекурсии , через другие функции , притивно рекурсивноть которых уже доказана.
РФ составляюь большую часть арифм. Ф, но не исчерпывают её.
Операция минимизации.

X1 v X2 v X3 v X4 v X5 дизъюнкты (V-лог. Или)
- сверху – это отрицание
Интерпретация – набор переменных
Выполняющая интерпретация – это та , при котором принимает значение 1

R
E(k=1,k<=R)nk 			O(n*R) n=max(nk)
2¬n

Сводимость задач и теорема С.Кука.

Опр. Задача А эффективна сводится к задаче B , если
1.	Решение задачи В даёт решение задачи А;
2.	Сложность сведения ограничена полиномиальной функцией.
Такая сводимость называется полиномиальной и обозначается А ≤ pB ( A α B)
Задача ВЫПОЛНИМОСТЬ эффективно сводится к задаче три-выполнимость. Задача три-выполнимость – это задача выполнимость , каждый дизъюнкт которой содержит не более трёх переменных.
Пусть имеется система вида:
x1 v x2 v x3
x1 v x2 v x3 v x5 v x11
x1 v x2 v x3

S = x1- v x2 v x3- v x5 v x11
Заменим второй дизъюнкт системой дизъюнктов , которую обозначим S1:
         x1-v x2v y1
S1 = y1- v x3- v y2
         y2- v x5 v x11
При замене используются след. Приёмы.
В начале дизъюнкта , содержащего более трёх переменных , вводятся доп. переменная  . Отсчитываем три первые переменные и формируем из них дизъюнкт в тройку . В начало оставшегося дизъюнкта добавляется та же переменная , но уже с отрицанием . Если в полученном в результате содержится более трёх переменных , то вводятся следующая новая переменная. И процесс формирования циклически продолжается.
Для доказательство того , что системы S и S1 эквиваленты обычно используют таблицы истинности.
N = 5, 2N = 25 = 32. 32 * 4 = 128.
В данном случае таблицу можно сократить до вида таблицы 2.6
Y1	Y2
0	0
0	1
1	0
1	1
Возьмём любую строку из этой таблицу и подставим её в строку S1. Ясно , что из выполнимости полученной новой системы автоматически будет следовать выполнимость системы S(так как при 0 для дополнительных переменных всегда должна быть не нулевая основная переменная , хотя бы в одном дизъюнкте).
Теперь рассмотрим наооборот , допустим S выполнимо , может ли при этом S1 невыполнимой? Предположим , что S1 невыполнимо. В этом случае в S1 должен быть хотя бы один невыполнимый дизъюнкт, то есть такой, что при любом значении входящей в него дополнительной переменной, он остаётся невыполнимым.  Допустим , что эта переменная есть y1. Предположим , что невыполним первый дизъюнкт. Дадим y1 значение 1. Видим , что предположение неверно, потому что при значении 1 он выполним. Предположим , что невыполним второй дизъюнкт , однако при y1 = 0, это неверно. Тогда проверяем по второй переменной . Допустим невыполним второй дизъюнкт , это неверно при y2 = 1 , а для третьего при = 0. Значит исходное предположение о невыполнимости S1 было неверно.
Пример 2. Задача о паросочетании.
Пусть имеется 5 девушек и 5 парней.
	A0	B0	C0	D0	Q0
X0	10		1
Z0		10			1
Y0	1			10
U0			10	1
W0		1			10
В таблице 1 означает взаимную симпатию. Можно ли подобрать 5 независимых пар лиц, симпатизирубщих друг к другу. 10 – совпадения.
В 1971 году Кук доказал следующую теорему. К задаче выполнимость полиномиально сводима любая задача из класса NP. Определение . Задачи из класса NP , к которой можно свести любую другую задачу из этого класса за полиномиальное время называется NP-полной(NP-complete).
Таким образом класс NP включает NP-полные задачи и задачи , которые легче их. То есть те , которые сводятся к NP полным задачам. В теории алгоритмов также используется термин NP-трудные задачи(NP-hard). Класс NP-трудных задач включает NP-полные задачи и задачи, которые сложнее их, то есть те задачи , к которым могут сведены NP-полные задачи.
Вывод: задачи ВЫПОЛНИМОСТЬ является NP-полной. Если бы для неё существовал полиномиальный детерминировнный алгоритм решения , то и любую другую задачу из NP можно было бы решить с помощью полиномиального детерминированного алгоритма. Однако до сих пор никто не нашёл полиномиального детерминированного алгоритма решения. Полагает , что такого алгоритма вовсе нет.



Методы решения задачи выполнимость.
Дерево решения задачи выполнимость и поиск решения на основе эвристической оценовчной функции.
Существенной чертой решения NP-полных задач является переборный характер алгоритма их решения. В связи с этим вопрос о стратегии решения , который может сократить перебор , является актуальным и важным.
Рассмотрим одну из наиболее распространённых стратегий , а именно стратегию на основе поиска на дереве состояния задач. Рассмотрим задачу выполнимость.
D1=x1 v x2- v x3
D2= x1- v x2-v x3-
D3= x1 v x3- v x4
D4= x1 v x2- v x4¬-
D5= x2- v x3- v x4-
Чтобы ускорить процедуру поиска , можно начать формировать дерево поиска из двух начальных гипотез. ( x1 = 1, x1 = 0 ).







По первой гипотезе мы попадаем в вершину S1 , приняв x1 = 1, по второй в S2 , приняв x1 = 0. Соответственно изменяются и сами дизъюнкты
D2 = x2- v x3-						D1 = x2- v x3
D5 = x2- v x3- v x4-					D3 = x3- v x4
							D4 = x2- v x4-
							D5 = x2- v x3- v x4-
F = k1 / m + (n – k2) / n -> 0, где m – кол-во дизъюнктов, n – число разноименных переменных в исходной системе дизъюнктов, k1 – кол-во дизъюнктов в рассматриваемой вершине, k2 – среднее значение числа дизъюнктов в данной вершине.
F1 = 0.775 F2 > 1.5

D1 = x3 v x4-
X3+ (1 – x4) >= 1
0<=X3<=1
0<=X4<=1;
(a v b) = (a + b>=1)
a-	= (1 – a)

===================================================================
2a1 + 4a2 >=0;
-a1 + 3a2 >=0;
0a1 + 1a2 >=0;
2a1 + 5a2 >=0;
-3a1 - 2a2 >=1;
-6a1 - 3a2 >=1;
-1a1 - 1a2 >=1;
-4a1 - 3a2 >=1;
Неравентсво с положительной правой частью называется невязкой. Если в системе нет невязок, то её решение достигается нулевыми значениями переменных. В противном случае используется алгоритм, который обеспечивает устранение имеющихся невязок. При этом выделяется две фазы. На первой фазе нужно получить систему базисных неравенств: ai >= 0; Вторая фаза выполняется так же, как и первая, но уже при наличии базисных неравенств. Если на второй фазе в процессе итерации встречается невязка, причём все коэффициенты в левой части неположительные, то устанавливается факт неразрешимости (несовместности) системы неравенств.
Для начала решения можно выбрать любую невязку. Выбираем первую невязку.
-3a1 >= 1 + 2a2,
A1 <= -1/3 – 2/3a2,
A1 = -1/3 – 2/3a2 – z1; z1 – новая неотрицательная переменная.
Выражения для a1 – это первая подстановка. Подставим вместо a1 её подстановку. Получим новую систему.
8/3a2 – 2z1 >= 2/3,
11/3a2 + z1 >= -1/3,
A2 >=0;
11/3a2 – 2z1 >= 2/3,
Z1 >=0,
A2 + 6z1 >= -1,
-1/3a2 + z1 >= 2/3,
-1/3a2 + 4z1 >= -1/3.
Имеются 2 базисных неравенства. A2 >= 0 и Z1 >= 0.
Вторая фаза. Выполняется с небольшим отличием от первой: из невязки выражаем переменную с положительным коэффициентом. Получаем:
A2 >= ¼ + ¾ z1;
A2 = ¼ + ¾ z1 + z2;
Подставляем a2 в систему.
Z2 >=0;
15/4 z1 + 11/3 z2 >= -5/4;
¾ z1 + z2 >= -1/4;
¾ z1 + 11/3 z2 >= -1/4;
Z1 >= 0;
27/4 z1 + z2 >= -5/4;
¾ z1 – 1/3 z2 >= 3/4;
15/4 z1 – 1/3 z2 >= -1/4;
Осталась одна невязка. Обработаем её как следует. Выражаем переменную с положительным коэффициентом.
¾ z1 – 1/3 z2 >= ¾;
Z1 = 1 + 4/9 z2 + z3;
Подстановка z1 приводит к системе без невязок. Отсюда в силу произведённых подстановок найдём z1 = 1, a1 = -2, a2 = 1;
Метод Евклида для решения в целых числах линейных уравнений и систем линейных уравнений.
Пусть задано линейное уравнение вида:
27x – 17y + 11z = 12;

Делим все коэффициенты на наименьший по модулю из всех коэффициентов, записанных в левой части. Используется целочисленное деление.
2x – y + z = u;
Умножаем опять на 11 и вычитаем из исходного уравнения полученное.
Получаем:
5x – 6y + 11u  = 12;
Повторяем процесс по аналогии. Производим деление на наименьший коэффициент.
Получаем:
x – y + 2u = v;
Опять умножаем на 5 и вычитаем из исходного.
Получаем:
-y + u +5v = 12;
Y = -12 + u + 5v;
Получили подстановку для всех x,y,z; u , v – произвольные целые числа.
Найдём любое решение, например, когда u = 1 , v = 2;
Y = -1, x = -1, z = 2;
Теперь для системы уравнений:
2x + 7y – 5z = 12;
9x – 5y + 2z = 4;
Сначала выражаем из первого уравнения, потом из второго.
Делим на 2;
X + 3y – 2z = v;
X = v – 3y + 2z;

Y – z + 2v = 12;
Y = 12 + z – 2v;
Переменная z, как и v, может принимать любые значения. Подставим найденные подставновки во второе уравнение.
Получим:
9(v-3y+2z) – 5(12+z-2v) +2z=4
9v – 27y + 18z – 60 – 5z + 10v +2z=4
19v – 27y + 15z =64
19v – 27(12+z-2v) +15z = 64
19v – 324 – 27z + 54v + 15z = 64
73v – 12z = 388
73v – 12z = 388.
Делим на 12 и выражаем z, как показано.
6v – z = w;
Z= 6v – w;
Умножаем первое уравнение на 12. Результат вычитаем из прошлого. Получаем:
V = 388 – 12w;
Примеры NP полных задач:
Задачи “Вершинное покрытие”

Вершина i покрывает некоторое ребро, если данная вершина является концевой вершиной рассматриваемого ребра.
Множество вершин П называется вершинным покрытием, если для каждого ребра графа найдётся хотя бы одна вершина из П, которая её покрывает.
Ответ (1,2,5)



Задача о “Клике”
Для произвольного графа определить n вершин, никакие 2 из которых не соединены ребром.
Ответ (3,4,6)
Задача о “Гомельтоновом Цикле”
Имеется ли в графе путь по рёбрам, проходящий через каждую вершину ровно 1 раз, который бы завершался в той же вершине, из которой он стартует.
Задача “Коммивояжёра”
Суть задачи: ему КОММУ нужно посетить каждый город в пределах некоторой территории и возвратиться в пункт отправления. Требуется, чтобы его путь был минимальным из возможных.
Задача “о ранце”
В задаче определяется, какое количество xi ( целое число) каждого из объектов i(от 1 до N), имеющего ценность Ci следует положить в ранец, чтобы суммарная ценность содержимого ранца была максимальной. Объём единицы объекты равен bi. Объём ранца равен B0.