SHARE
TWEET

Untitled

a guest Dec 9th, 2019 162 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
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top