Guest User

Untitled

a guest
Dec 9th, 2019
182
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. Алгоритмы Маркова(АМ)
  2. Правила подстановки одних символов вместо других
  3. a->bc
  4. ab->bc abc -> bcbc -> bac -> ba -> bbc -> bb
  5. c->ε
  6. cb->a
  7. Нормальный алгоритм Маркова позволяет решать задачу демермизированно.Нормальный алгоритм Маркова предполагает четкое упорядочивание правил подстановки. Для подстановки всегда выбирается первое подходящее правило.
  8. Среди правил должно быть такое с правой части которого имеется (●). Правила без точки – простые правила замены(подстановки), а правила с точками – конечные правила подстановки. Работа алгоритма заканчивается в след. cлучаях: 1)если на каком-то шаге замен применилось правило с (●) в правой части (α->.β). Это называется результативный останов;2)входное слово просмотрено до конца и не удалось применить ни одно из правил – нерезультативный останов;3)зацикливание алгоритма Маркова.
  9. Доказано, что машина Тьюринга и нормальные алгоритмы Маркова близки и их использование приводит к одинаковым результатам.
  10. Состояние МТ Q0aba
  11. Q0a->Q1bR ba1ba
  12. Q0a->Q1bR
  13. Q0a->bQ1
  14. Q0b->Q2aU
  15. Q0b->Q2a
  16. Q1b->Q2aL
  17. Тюринг: (Q0)ab->(Q1)bb->Q2ba
  18. Марков: Q0ab->bQ1b->b1a->ba
  19. Самоприменимость алгоритмов Маркова
  20. -набор правил можно поедставить в виде входного слова.
  21. Если процесс обработки вх.слова(который явл. Описанием алг-ма Маркова) останавливается,то такой алгоритм называется самоприменимым. Доказано: задача – является ли алгоритс самоприм. или несамоприм. -неразрешима.
  22.  
  23. Рекурсивные функции и эффективная вычислимость.
  24. ЧФ(частичная функция) является вычислимой , если её значения можно определить посредством некого алгоритма.
  25. Если нек.элем.мн-ва Х ставится в соотвествие однозначно определённых элементов мн-ва У,то говорят , что задана частичная функция из Х в У.Совокупность эл мн-ва Х, у которых есть соотв. им элементы в мн-ве У называют областью определения функции из Х в У. А совокупность соответств.знач. У называются областью значений функции из Х в У.
  26. Если обл.определения совпадает с мн-вом Х,то функция называется всюду определённой функцией .
  27. Весь набор входных слов можно представить как мн-во Х, а выходных – У. И если поставить эти мн-ва в соответствие , то задаётся функция y=f(x)
  28. Рекурсия – способ задания функции , при котором значение определяемой функции для произвольных значений её элементов определяется известным образом через значение определ. функции для меньших значений аргумента.
  29. (n+1)! = 1 * 2 * 3 * 4 * 5 * … * k * … * (n-2) * (n-1) * n * (n+1) = (n+1) * n!
  30. Вводятся понития элементарных первичных функций . Первичную нельзя получить из других функций . Из первичных функций путём комбинаций можно строить другие функции.
  31. Всего выделяют 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
  32. Операции для построения новых функций:
  33. 1) Суперпозиции(подстановки)
  34. 2) Примитивной рекурсии
  35. 3) Минимизации
  36. Операция подстановки(1)
  37. Заключается в том, что вместо каких-то переменных функций подставляются другие функции от тех же или иных переменных. Пусть заданы n Ф: f1,f2,f3…fn от m переменных каждая. Операцией суперпозиции f1…fn с функцией f будет порождена новая. А также функция f от n переменных (x1,x2…xn).
  38. Функция g(x1,x2,x3,…,xm)=f(f1(x1,x2,…,xm),…fn(x1,…,xm))
  39. Пример 1.Суперпозиция Пример 2: f(x) = x + 1;
  40. f(x) = 0 g(x)=x+1 g(y) = y+1;
  41. h(x) = g(f(x)) = g(0) = 0 + 1 = 1; h(y)=f(g(y))=f(y+1)=(y+1)+1=y+2;
  42. Суперп. F(x)=x+1 с самой собой : h(y) = y +2;
  43. Операция примитивной рекурсии и определ. примитивно рекурсивной Ф
  44. Представим эту операцию в общем виде : она позволяет строить n+1-мест. Функцию на основании известных n-местных и n+2-местной функции .
  45. Пусть задана n-местная функция g и n+2-местная функция h. Говорят , что n+1-местная функция f возникает примитивной рекурсией из g и h , если для всех натуральных значений (х1,х2...хn,y) справедливы соотношения:
  46. f(x1,x2,…xn,0)=g(x1,x2…xn)
  47. f(x1,x2,…xn,y+1)=h(x1,x2…xn,y,f(x1,x2…xn,y))
  48. Доказано , что для каждых g и h существует функция f и она является единственной , что записывается Rn(g,h)
  49. При этом для вычисления значения f в конкретной точке является чисто механической процедурой , выполняемой по строго определённым правилам . Т.е. для нахождения значений достаточно последовательно найти числа
  50. b0 = g(a,a2,…,an) b1=h(a1,a2…an,0,b0) b2= h(a,a2,…,an,1,b1)
  51. bm+1 = h(a,a2,…,an,m,bm)
  52. Заметим , что если считать const – функцией от нуля переменных , то можно определить одноместную функцию f , которая возникает примитивной рекурсией из a и двуместной частичной функцией h в виде f(□,y+1)=h(□,y,f(□,y)) или , сокращая :
  53. f(0) = a
  54. f(y+1) = h (y,f(y))
  55. Это и есть примитивное определение функции через операцию рекурсии. Примитивная рекурсия , т.к. по одной переменной с шагом 1.
  56. Пример 1: Построить с помощью рекурсии двуместную функцию суммирования.
  57. f+( x , y ) = x + y;
  58. Отметим , что прибавить y к x – то же , что прибавить 1 к x y-раз.
  59. Искомая функция определ. на основе тождеств. функц. g(x) = x и функций непосредственного следования h(x,y,z) , которая вычисл. как z+1
  60. Результат: (ПОРЯДОК)
  61. 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;
  62. 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;
  63. 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))
  64.  
  65. Определение
  66. Функции , которые могут быть построены из первичных с помощью операций суперпозиции и\или примитивной рекурсии , примененных любое кол-во раз в произвольной последовательности , называются примитивно-рекурсивными функциями.
  67. Эти же операции , прим. К всюду определённым Ф , дают также всюду опр. Ф
  68. Для того , чтобы показать , что Ф является примитивно-рекурс. , достаточно построить её согласно определению. Однако такое построение получается слишком сложным , поэтому в большинстве случаев вункцию пытаются выразить с помощью операций суперпозиции и примитивной рекурсии , через другие функции , притивно рекурсивноть которых уже доказана.
  69. РФ составляюь большую часть арифм. Ф, но не исчерпывают её.
  70. Операция минимизации.
  71.  
  72. X1 v X2 v X3 v X4 v X5 дизъюнкты (V-лог. Или)
  73. - сверху – это отрицание
  74. Интерпретация – набор переменных
  75. Выполняющая интерпретация – это та , при котором принимает значение 1
  76.  
  77. R
  78. E(k=1,k<=R)nk O(n*R) n=max(nk)
  79. 2¬n
  80.  
  81. Сводимость задач и теорема С.Кука.
  82.  
  83. Опр. Задача А эффективна сводится к задаче B , если
  84. 1. Решение задачи В даёт решение задачи А;
  85. 2. Сложность сведения ограничена полиномиальной функцией.
  86. Такая сводимость называется полиномиальной и обозначается А ≤ pB ( A α B)
  87. Задача ВЫПОЛНИМОСТЬ эффективно сводится к задаче три-выполнимость. Задача три-выполнимость – это задача выполнимость , каждый дизъюнкт которой содержит не более трёх переменных.
  88. Пусть имеется система вида:
  89. x1 v x2 v x3
  90. x1 v x2 v x3 v x5 v x11
  91. x1 v x2 v x3
  92.  
  93. S = x1- v x2 v x3- v x5 v x11
  94. Заменим второй дизъюнкт системой дизъюнктов , которую обозначим S1:
  95. x1-v x2v y1
  96. S1 = y1- v x3- v y2
  97. y2- v x5 v x11
  98. При замене используются след. Приёмы.
  99. В начале дизъюнкта , содержащего более трёх переменных , вводятся доп. переменная . Отсчитываем три первые переменные и формируем из них дизъюнкт в тройку . В начало оставшегося дизъюнкта добавляется та же переменная , но уже с отрицанием . Если в полученном в результате содержится более трёх переменных , то вводятся следующая новая переменная. И процесс формирования циклически продолжается.
  100. Для доказательство того , что системы S и S1 эквиваленты обычно используют таблицы истинности.
  101. N = 5, 2N = 25 = 32. 32 * 4 = 128.
  102. В данном случае таблицу можно сократить до вида таблицы 2.6
  103. Y1 Y2
  104. 0 0
  105. 0 1
  106. 1 0
  107. 1 1
  108. Возьмём любую строку из этой таблицу и подставим её в строку S1. Ясно , что из выполнимости полученной новой системы автоматически будет следовать выполнимость системы S(так как при 0 для дополнительных переменных всегда должна быть не нулевая основная переменная , хотя бы в одном дизъюнкте).
  109. Теперь рассмотрим наооборот , допустим S выполнимо , может ли при этом S1 невыполнимой? Предположим , что S1 невыполнимо. В этом случае в S1 должен быть хотя бы один невыполнимый дизъюнкт, то есть такой, что при любом значении входящей в него дополнительной переменной, он остаётся невыполнимым. Допустим , что эта переменная есть y1. Предположим , что невыполним первый дизъюнкт. Дадим y1 значение 1. Видим , что предположение неверно, потому что при значении 1 он выполним. Предположим , что невыполним второй дизъюнкт , однако при y1 = 0, это неверно. Тогда проверяем по второй переменной . Допустим невыполним второй дизъюнкт , это неверно при y2 = 1 , а для третьего при = 0. Значит исходное предположение о невыполнимости S1 было неверно.
  110. Пример 2. Задача о паросочетании.
  111. Пусть имеется 5 девушек и 5 парней.
  112. A0 B0 C0 D0 Q0
  113. X0 10 1
  114. Z0 10 1
  115. Y0 1 10
  116. U0 10 1
  117. W0 1 10
  118. В таблице 1 означает взаимную симпатию. Можно ли подобрать 5 независимых пар лиц, симпатизирубщих друг к другу. 10 – совпадения.
  119. В 1971 году Кук доказал следующую теорему. К задаче выполнимость полиномиально сводима любая задача из класса NP. Определение . Задачи из класса NP , к которой можно свести любую другую задачу из этого класса за полиномиальное время называется NP-полной(NP-complete).
  120. Таким образом класс NP включает NP-полные задачи и задачи , которые легче их. То есть те , которые сводятся к NP полным задачам. В теории алгоритмов также используется термин NP-трудные задачи(NP-hard). Класс NP-трудных задач включает NP-полные задачи и задачи, которые сложнее их, то есть те задачи , к которым могут сведены NP-полные задачи.
  121. Вывод: задачи ВЫПОЛНИМОСТЬ является NP-полной. Если бы для неё существовал полиномиальный детерминировнный алгоритм решения , то и любую другую задачу из NP можно было бы решить с помощью полиномиального детерминированного алгоритма. Однако до сих пор никто не нашёл полиномиального детерминированного алгоритма решения. Полагает , что такого алгоритма вовсе нет.
  122.  
  123.  
  124.  
  125. Методы решения задачи выполнимость.
  126. Дерево решения задачи выполнимость и поиск решения на основе эвристической оценовчной функции.
  127. Существенной чертой решения NP-полных задач является переборный характер алгоритма их решения. В связи с этим вопрос о стратегии решения , который может сократить перебор , является актуальным и важным.
  128. Рассмотрим одну из наиболее распространённых стратегий , а именно стратегию на основе поиска на дереве состояния задач. Рассмотрим задачу выполнимость.
  129. D1=x1 v x2- v x3
  130. D2= x1- v x2-v x3-
  131. D3= x1 v x3- v x4
  132. D4= x1 v x2- v x4¬-
  133. D5= x2- v x3- v x4-
  134. Чтобы ускорить процедуру поиска , можно начать формировать дерево поиска из двух начальных гипотез. ( x1 = 1, x1 = 0 ).
  135.  
  136.  
  137.  
  138.  
  139.  
  140.  
  141.  
  142. По первой гипотезе мы попадаем в вершину S1 , приняв x1 = 1, по второй в S2 , приняв x1 = 0. Соответственно изменяются и сами дизъюнкты
  143. D2 = x2- v x3- D1 = x2- v x3
  144. D5 = x2- v x3- v x4- D3 = x3- v x4
  145. D4 = x2- v x4-
  146. D5 = x2- v x3- v x4-
  147. F = k1 / m + (n – k2) / n -> 0, где m – кол-во дизъюнктов, n – число разноименных переменных в исходной системе дизъюнктов, k1 – кол-во дизъюнктов в рассматриваемой вершине, k2 – среднее значение числа дизъюнктов в данной вершине.
  148. F1 = 0.775 F2 > 1.5
  149.  
  150. D1 = x3 v x4-
  151. X3+ (1 – x4) >= 1
  152. 0<=X3<=1
  153. 0<=X4<=1;
  154. (a v b) = (a + b>=1)
  155. a- = (1 – a)
  156.  
  157. ===================================================================
  158. 2a1 + 4a2 >=0;
  159. -a1 + 3a2 >=0;
  160. 0a1 + 1a2 >=0;
  161. 2a1 + 5a2 >=0;
  162. -3a1 - 2a2 >=1;
  163. -6a1 - 3a2 >=1;
  164. -1a1 - 1a2 >=1;
  165. -4a1 - 3a2 >=1;
  166. Неравентсво с положительной правой частью называется невязкой. Если в системе нет невязок, то её решение достигается нулевыми значениями переменных. В противном случае используется алгоритм, который обеспечивает устранение имеющихся невязок. При этом выделяется две фазы. На первой фазе нужно получить систему базисных неравенств: ai >= 0; Вторая фаза выполняется так же, как и первая, но уже при наличии базисных неравенств. Если на второй фазе в процессе итерации встречается невязка, причём все коэффициенты в левой части неположительные, то устанавливается факт неразрешимости (несовместности) системы неравенств.
  167. Для начала решения можно выбрать любую невязку. Выбираем первую невязку.
  168. -3a1 >= 1 + 2a2,
  169. A1 <= -1/3 – 2/3a2,
  170. A1 = -1/3 – 2/3a2 – z1; z1 – новая неотрицательная переменная.
  171. Выражения для a1 – это первая подстановка. Подставим вместо a1 её подстановку. Получим новую систему.
  172. 8/3a2 – 2z1 >= 2/3,
  173. 11/3a2 + z1 >= -1/3,
  174. A2 >=0;
  175. 11/3a2 – 2z1 >= 2/3,
  176. Z1 >=0,
  177. A2 + 6z1 >= -1,
  178. -1/3a2 + z1 >= 2/3,
  179. -1/3a2 + 4z1 >= -1/3.
  180. Имеются 2 базисных неравенства. A2 >= 0 и Z1 >= 0.
  181. Вторая фаза. Выполняется с небольшим отличием от первой: из невязки выражаем переменную с положительным коэффициентом. Получаем:
  182. A2 >= ¼ + ¾ z1;
  183. A2 = ¼ + ¾ z1 + z2;
  184. Подставляем a2 в систему.
  185. Z2 >=0;
  186. 15/4 z1 + 11/3 z2 >= -5/4;
  187. ¾ z1 + z2 >= -1/4;
  188. ¾ z1 + 11/3 z2 >= -1/4;
  189. Z1 >= 0;
  190. 27/4 z1 + z2 >= -5/4;
  191. ¾ z1 – 1/3 z2 >= 3/4;
  192. 15/4 z1 – 1/3 z2 >= -1/4;
  193. Осталась одна невязка. Обработаем её как следует. Выражаем переменную с положительным коэффициентом.
  194. ¾ z1 – 1/3 z2 >= ¾;
  195. Z1 = 1 + 4/9 z2 + z3;
  196. Подстановка z1 приводит к системе без невязок. Отсюда в силу произведённых подстановок найдём z1 = 1, a1 = -2, a2 = 1;
  197. Метод Евклида для решения в целых числах линейных уравнений и систем линейных уравнений.
  198. Пусть задано линейное уравнение вида:
  199. 27x – 17y + 11z = 12;
  200.  
  201. Делим все коэффициенты на наименьший по модулю из всех коэффициентов, записанных в левой части. Используется целочисленное деление.
  202. 2x – y + z = u;
  203. Умножаем опять на 11 и вычитаем из исходного уравнения полученное.
  204. Получаем:
  205. 5x – 6y + 11u = 12;
  206. Повторяем процесс по аналогии. Производим деление на наименьший коэффициент.
  207. Получаем:
  208. x – y + 2u = v;
  209. Опять умножаем на 5 и вычитаем из исходного.
  210. Получаем:
  211. -y + u +5v = 12;
  212. Y = -12 + u + 5v;
  213. Получили подстановку для всех x,y,z; u , v – произвольные целые числа.
  214. Найдём любое решение, например, когда u = 1 , v = 2;
  215. Y = -1, x = -1, z = 2;
  216. Теперь для системы уравнений:
  217. 2x + 7y – 5z = 12;
  218. 9x – 5y + 2z = 4;
  219. Сначала выражаем из первого уравнения, потом из второго.
  220. Делим на 2;
  221. X + 3y – 2z = v;
  222. X = v – 3y + 2z;
  223.  
  224. Y – z + 2v = 12;
  225. Y = 12 + z – 2v;
  226. Переменная z, как и v, может принимать любые значения. Подставим найденные подставновки во второе уравнение.
  227. Получим:
  228. 9(v-3y+2z) – 5(12+z-2v) +2z=4
  229. 9v – 27y + 18z – 60 – 5z + 10v +2z=4
  230. 19v – 27y + 15z =64
  231. 19v – 27(12+z-2v) +15z = 64
  232. 19v – 324 – 27z + 54v + 15z = 64
  233. 73v – 12z = 388
  234. 73v – 12z = 388.
  235. Делим на 12 и выражаем z, как показано.
  236. 6v – z = w;
  237. Z= 6v – w;
  238. Умножаем первое уравнение на 12. Результат вычитаем из прошлого. Получаем:
  239. V = 388 – 12w;
  240. Примеры NP полных задач:
  241. Задачи “Вершинное покрытие”
  242.  
  243. Вершина i покрывает некоторое ребро, если данная вершина является концевой вершиной рассматриваемого ребра.
  244. Множество вершин П называется вершинным покрытием, если для каждого ребра графа найдётся хотя бы одна вершина из П, которая её покрывает.
  245. Ответ (1,2,5)
  246.  
  247.  
  248.  
  249. Задача о “Клике”
  250. Для произвольного графа определить n вершин, никакие 2 из которых не соединены ребром.
  251. Ответ (3,4,6)
  252. Задача о “Гомельтоновом Цикле”
  253. Имеется ли в графе путь по рёбрам, проходящий через каждую вершину ровно 1 раз, который бы завершался в той же вершине, из которой он стартует.
  254. Задача “Коммивояжёра”
  255. Суть задачи: ему КОММУ нужно посетить каждый город в пределах некоторой территории и возвратиться в пункт отправления. Требуется, чтобы его путь был минимальным из возможных.
  256. Задача “о ранце”
  257. В задаче определяется, какое количество xi ( целое число) каждого из объектов i(от 1 до N), имеющего ценность Ci следует положить в ранец, чтобы суммарная ценность содержимого ранца была максимальной. Объём единицы объекты равен bi. Объём ранца равен B0.
RAW Paste Data