Содержание
- 2. Структура курса Введение. Основные понятия теории автоматов. Конечные автоматы. Регулярные выражения и регулярные языки. Контекстно-свободные грамматики
- 3. Объём курса 5 семестр: 16 часов лекций 16 часов практики Расчётно-графическая работа Зачёт
- 4. Список литературы Джон Хопкрофт и др. Введение в теорию автоматов, языков и вычислений Ахо А., Сети
- 5. История конечных автоматов Теория автоматов занимается изучением абстрактных вычислительных устройств, или "машин". В 1930-е годы, задолго
- 6. История конечных автоматов В 1969 году С. Кук развил результаты Тьюринга о вычислимости и невычислимости. Ему
- 7. Введение в теорию конечных автоматов Основы теории формальных доказательств Конечные автоматы являются моделью для многих компонентов
- 8. Простейший нетривиальный автомат Простейшим нетривиальным конечным автоматом является переключатель "включено-выключено". Это устройство помнит свое текущее состояние,
- 9. Конечный автомат, распознающий слово Входным сигналам соответствуют буквы. Можно считать, что данный лексический анализатор всякий раз
- 10. Структурные представления автоматов Следующие системы записи не являются автоматными, но играют важную роль в теории автоматов
- 11. Основные понятия теории автоматов Алфавиты и цепочки Языки Проблемы
- 12. Алфавит Алфавитом называют конечное непустое множество символов. Условимся обозначать алфавиты символом ∑. Наиболее часто используются следующие
- 13. Цепочки Цепочка, или иногда слово, — это конечная последовательность символов некоторого алфавита. Например, 01101 — это
- 14. Степени алфавита
- 16. Конкатенация цепочек
- 17. Языки
- 18. Примеры языков из теории автоматов
- 19. Проблемы
- 20. Проблемы
- 21. Конечные автоматы – задача-пример Рассмотрим развернутый пример реальной проблемы, в решении которой важную роль играют конечные
- 22. Основные участники задачи Есть три участника: клиент, магазин и банк. Для простоты предположим, что есть всего
- 23. Протокол работы с деньгами Во избежание недоразумений участники должны вести себя осторожно. В нашем случае можно
- 24. Конечные автоматы участников
- 25. Возможность игнорирования действий Типы игнорируемых действий: Действия, не затрагивающие данного участника. Действия, которые не следует допускать
- 26. Правило построения дуг Чтобы правильно построить дуги в автомате-произведении, нужно проследить "параллельную" работу автоматов банка и
- 27. Автомат, определяющий систему в целом Обычный способ изучения взаимодействия подобных автоматов состоит в построении так называемого
- 28. Проверка протокола при помощи автомата Из автомата-произведения можно узнать кое-что интересное. Так, из начального состояния (1,
- 29. Детерминированные конечные автоматы (ДКА)
- 30. Обработка цепочек при помощи ДКА "Язык" ДКА— это множество всех его допустимых цепочек. Пусть а1а2...аn —
- 31. Пример обработки цепочек слайд 1/3 Пример. Определить формально ДКА, допускающий цепочки из 0 и 1, которые
- 32. Пример обработки цепочек слайд 2/3 Что можно сказать об автомате, допускающем цепочки данного языка L? Во-первых,
- 33. Пример обработки цепочек слайд 3/3
- 34. Способы представления ДКА Диаграмма переходов, которая представляет собой граф. Таблица переходов, дающая табличное представление функции δ.
- 35. Диаграмма переходов Диаграмма переходов для ДКА вида A=(Q, ∑, δ,q0, F) есть граф, определяемый следующим образом:
- 36. Таблица переходов Таблица переходов представляет собой обычное табличное представление функции, подобной δ, которая двум аргументам ставит
- 37. Расширенная функция переходов
- 38. Пример
- 39. Построение расширенной функции переходов
- 40. Язык ДКА
- 41. Недетерминированный конечный автомат (НКА) "Недетерминированный" конечный автомат, или НКА (NFA — Nondeterministic Finite Automaton), обладает свойством
- 42. Неформальное описание НКА НКА, как и ДКА, имеют конечное множество состояний, конечное множество входных символов, одно
- 43. Пример НКА
- 44. Обработка цепочек НКА
- 45. Определение НКА
- 46. Таблица переходов для НКА
- 47. Расширенная функция переходов НКА
- 48. Язык НКА
- 49. Эквивалентность ДКА и НКА
- 50. Конструкция подмножеств
- 51. Пример конструкции подмножеств
- 52. Пример конструкции подмножеств
- 53. Пример конструкции подмножеств
- 54. Пример конструкции подмножеств
- 55. Пример конструкции подмножеств Итак, конструкция подмножеств сошлась; известны все допустимые состояния и соответствующие им переходы. Полностью
- 56. Теоремы конструкции подмножеств
- 57. Плохая конструкция подмножеств слайд 1
- 58. Плохая конструкция подмножеств слайд 2
- 59. Плохая конструкция подмножеств слайд 3
- 60. Пример использования автомата: поиск цепочек в тексте В век Internet и электронных библиотек с непрерывным доступом
- 61. Недетерминированный поисковый автомат
- 62. Пример такого автомата
- 63. ДКА распознавания слов
- 64. Конечный автомат с ε – переходом Рассмотрим еще одно обобщение понятия конечного автомата. Придадим автомату новое
- 65. Использование ε – переходов На слайде изображен ε -НКА, допускающий десятичные числа, которые состоят из следующих
- 66. Упрощение поискового автомата НКА, распознающий ключевые слова web и ebay, можно реализовать и с помощью ε
- 67. Формальная запись ε-НКА
- 68. ε-замыкание
- 69. Пример ε-замыкания Для данного в нем набора состояний, который может быть частью некоторого ε -НКА, мы
- 70. Расширенные переходы и языки ε –НКА
- 71. Пример
- 72. Устранение ε-переходов
- 73. Пример Удалим ε -переходы из ε -НКА (см. слайд 69), который далее называется Е. По Е
- 74. Регулярные выражения Перейдем от "машинного" задания языков с помощью ДКА и НКА к алгебраическому описанию языков
- 75. Операторы регулярных выражений слайд 1 Регулярные выражения обозначают (задают, или представляют) языки. В качестве простого примера
- 76. Операторы регулярных выражений слайд 2
- 77. Пример итерации слайд 1
- 78. Пример итерации слайд 2
- 79. Построение регулярных выражений Все алгебры начинаются с некоторых элементарных выражений. Обычно это константы и/или переменные. Применяя
- 80. Определение регулярного выражения
- 81. Пример регулярного выражения слайд 1
- 82. Пример регулярного выражения слайд 2
- 83. Пример регулярного выражения слайд 3
- 84. Приоритеты операторов регулярных выражений Для операторов регулярных выражений определен следующий порядок приоритетов: Оператор "звездочка" имеет самый
- 85. Связь конечных автоматов и регулярных выражений Связь конечных автоматов и регулярных выражений показана в соответствующей презентации
- 86. Минимизация НКА регулярными выражениями слайд 1/5 Рассмотрим НКА, допускающий цепочки из нулей и единиц, у которых
- 87. Минимизация НКА регулярными выражениями слайд 2/5 Вначале преобразуем этот автомат в автомат с регулярными выражениями в
- 88. Минимизация НКА регулярными выражениями слайд 3/5
- 89. Минимизация НКА регулярными выражениями слайд 4/5
- 90. Минимизация НКА регулярными выражениями слайд 5/5 Теперь снова нужно вернуться к исходному автомату и исключить состояние
- 91. Построение автомата на основе регулярного выражения слайд 1/3 Все конструируемые автоматы представляют собой ε-НКА с одним
- 92. Построение автомата на основе регулярного выражения слайд 2/3 Базис. Базис состоит из трех частей, представленных на
- 93. Построение автомата на основе регулярного выражения слайд 3/3
- 94. Пример построения автомата Преобразуем регулярное выражение (0 + 1)*1(0 + 1) в ε-НКА. Построим сначала автомат
- 95. Алгебра регулярных выражений В примере выше возникла необходимость упрощения регулярных выражений для того, чтобы их размер
- 96. Коммутативность и ассоциативность Коммутативность— это свойство операции, заключающееся в том, что при перестановке ее операндов результат
- 97. Нулевые и единичные элементы
- 98. Дистрибутивные законы
- 99. Идемпотентность
- 100. Законы оператора итерации
- 101. Установление законов для регулярных выражений
- 102. Теорема законов регулярных выражений
- 103. Свойства регулярных языков Одними из важнейших свойств регулярных языков являются "свойства замкнутости". Эти свойства позволяют создавать
- 104. Доказательство нерегулярности В предыдущих разделах было установлено, что класс языков, известных как регулярные, имеет не менее
- 105. Лемма о накачке для регулярных языков
- 106. Формулировка леммы
- 107. Игровое представление леммы
- 108. Пример доказательства нерегулярности
- 109. Пример доказательства нерегулярности 2
- 110. Свойства замкнутости регулярных языков Свойства замкнутости регулярных языков позволяют создавать новые регулярные языки при помощи определённых
- 111. Свойства разрешимости регулярных языков Сформируем важные вопросы, связанные с регулярными языками. Сначала нужно разобраться, что значит
- 112. Преобразования типов представлений языков Выше было показано, что каждое из четырех представлений регулярных языков можно преобразовать
- 113. Преобразование НКА в ДКА слайд 1/2
- 114. Преобразование НКА в ДКА слайд 2/2
- 115. Преобразование ДКА в НКА
- 116. Преобразование автомата в регулярное выражение
- 117. Преобразование регулярного выражения в автомат
- 118. Проверка пустоты регулярных языков На первый взгляд ответ на вопрос "является ли регулярный язык L пустым?"
- 119. Алгоритм проверки слайд 1/2
- 120. Алгоритм проверки слайд 2/2
- 121. Проверка принадлежности регулярному языку слайд 1/2
- 122. Проверка принадлежности регулярному языку слайд 2/2
- 123. Эквивалентность и минимизация автоматов В отличие от предыдущих вопросов — пустоты и принадлежности, алгоритмы решения которых
- 124. Контекстно-свободные грамматики Выше в презентации были рассмотрены регулярные языки. В этом разделе рассмотрим более широкий класс
- 125. Неформальный пример КС-грамматики слайд 1/2
- 126. Неформальный пример КС-грамматики слайд 2/2
- 127. Определение КС-грамматики
- 128. КС-грамматика для выражений, слайд 1/2
- 129. Сокращённая запись продукций
- 130. Порождения с использованием грамматики Для того чтобы убедиться, что данные цепочки принадлежат языку некоторой переменной, применяются
- 131. Пример рекурсивного вывода Результаты этих выводов показаны ниже. Например, строчка (i) говорит, что в соответствии с
- 132. Отношение порождения
- 133. Пример порождения
- 134. Левые и правые порождения слайд 1/2
- 135. Левые и правые порождения слайд 2/2
- 136. Обозначения для порождений
- 137. Язык грамматики и выводимые цепочки
- 138. Деревья разбора Для порождений существует чрезвычайно полезное представление в виде дерева. Это дерево наглядно показывает, каким
- 139. Построение дерева разбора
- 140. Пример дерева разбора
- 141. Крона дерева разбора
- 142. Пример кроны На рисунке представлен пример дерева с терминальной цепочкой в качестве кроны и стартовым символом
- 143. Вывод, порождения и деревья разбора
- 144. Переход от выводов к деревьям разбора Теорема. Пусть G = (V, Т, P,S) — КС-грамматика. Если
- 145. Переход от деревьев к порождениям слайд 1/2
- 146. Переход от деревьев к порождениям слайд 2/2
- 147. Порождения и рекурсивные выводы слайд 1/2
- 148. Порождения и рекурсивные выводы слайд 2/2
- 149. Приложения КС-грамматик Контекстно-свободные грамматики были придуманы Н. Хомским (N. Chomsky) как способ описания естественных языков, но
- 150. Синтаксические анализаторы
- 151. Оператор if - then – else слайд 1/2
- 152. Оператор if - then – else слайд 2/2 Пример. Рассмотрим цепочку iee. Первое е соответствует i
- 153. Генератор синтаксических анализаторов YACC Генерация синтаксического анализатора (функция, создающая деревья разбора по исходным программам) воплощена в
- 154. Особенности нотации YACC
- 155. Языки описания документов: HTML, XML Рассмотрим семейство "языков", которые называются языками описания документов (markup languages). "Цепочками"
- 156. Фрагмент грамматики HTML Text (текст) — это произвольная цепочка символов, которая может быть проинтерпретирована буквально, т.е.
- 157. Язык XML и определения типа документа Цель XML состоит не в описании форматирования документа; это работа
- 158. Определение элемента DTD Определение элемента, в свою очередь, имеет вид Описания элементов являются, по существу, регулярными
- 159. DTD для компьютера, упрощенное
- 160. XML-документ, соответствующий DTD 4560 $2295 Intel Pentium 800mhZ 256 Maxtor Diamond 30.5Gb 32x … …
- 161. Соответствие между КС и DTD
- 162. Переход от КС-грамматик с рег. выражениями к обычным слайд 1/2
- 163. Переход от КС-грамматик с рег. выражениями к обычным слайд 2/2
- 164. Неоднозначности в грамматиках и языках Как было показано, в приложениях КС-грамматики часто служат основой для обеспечения
- 165. Неоднозначные грамматики
- 166. Различие между деревьями разбора Разница между этими двумя порождениями значительна. Когда рассматривается структура выражений, порождение 1
- 167. Неоднозначность грамматики выражений
- 168. Исключение неоднозначности В идеальном мире можно было бы дать алгоритм исключения неоднозначности из КС-грамматик, почти как
- 169. Причины неоднозначности грамматики слайда 128 Не учитываются приоритеты операторов. В то время как на рис. слайда
- 170. Установление приоритетов Решение проблемы установления приоритетов состоит в том, что вводится несколько разных переменных, каждая из
- 171. Однозначная грамматика выражений
- 172. Сложности однозначной грамматики
- 173. Выражение неоднозначности через левые порождения
- 174. Существенная неоднозначность
- 175. КС-грамматика языка L
- 176. Доказательство неоднозначности L
- 177. Автоматы с магазинной памятью
- 178. Неформальное определение автомата с магазинной памятью
- 179. Конечное управление
- 180. Пример
- 181. Формальное определение автомата с магазинной памятью
- 182. Пример создания МП-автомата
- 183. Графическое представление МП-автомата
- 184. Конфигурации МП-автомата
- 185. Определение перехода
- 186. Соглашения по записи МП-автоматов
- 187. Пример работы МП-автомата
- 188. Важные принципы МП-автоматов
- 189. Языки МП-автоматов Выше предполагалось, что МП-автомат допускает свой вход, прочитывая его и достигая заключительного состояния. Такой
- 190. Допустимость по заключительному состоянию
- 191. Допустимость по пустому магазину
- 192. Переход от пустого магазина к заключительному состоянию
- 193. Пример перехода слайд 1/3 Пример. Построим МП-автомат, который обрабатывает последовательности слов if и else в С-программе,
- 194. Пример перехода слайд 2/3
- 195. Пример перехода слайд 3/3
- 196. Переход от заключительного состояния к пустому магазину слайд 1/2
- 197. Переход от заключительного состояния к пустому магазину слайд 2/2
- 198. Эквивалентность МП-автоматов и КС-грамматик Ниже будет показано, что МП-автоматы определяют КС-языки. План доказательства изображен на слайде.
- 199. Детерминированные автоматы с магазинной памятью Хотя МП-автоматы по определению недетерминированы, их детерминированный случай чрезвычайно важен. В
- 200. Определение ДМП-автомата слайд 1/2
- 201. Определение ДМП-автомата слайд 2/2
- 202. Регулярные языки и ДМП
- 203. ДМП и КС-языки
- 204. ДМП и неоднозначные грамматики
- 205. Свойства контекстно-свободных языков Вначале определяются ограничения на структуру продукций КС-грамматик и доказывается, что всякий КС-язык имеет
- 206. Нормальные формы КС-грамматик
- 207. Свойства замкнутости КС-языков Операции, порождающие контекстно-свободные языки, представлены в соответствующей презентации
- 208. Свойства разрешимости КС-языков Теперь рассмотрим, на какие вопросы о контекстно-свободных языках можно дать ответ. По аналогии
- 209. Преобразование КС-грамматики и МП-автоматов слайд 1/4 Прежде чем приступать к алгоритмам разрешения вопросов о КС-языках, рассмотрим
- 210. Преобразование КС-грамматики и МП-автоматов слайд 2/4
- 211. Преобразование КС-грамматики и МП-автоматов слайд 3/4
- 212. Преобразование КС-грамматики и МП-автоматов слайд 4/4
- 213. Преобразование к НФХ слайд 1/2
- 214. Преобразование к НФХ слайд 2/2
- 215. Проверка пустоты КС-языков слайд 1\4
- 216. Проверка пустоты КС-языков слайд 2\4 Структура данных (см. рисунок) начинает с массива, индексированного переменными, как показано
- 217. Проверка пустоты КС-языков слайд 3\4
- 218. Проверка пустоты КС-языков слайд 4\4
- 219. Проверка принадлежности КС-языку слайд 1/4
- 220. Проверка принадлежности КС-языку слайд 2/4
- 221. Проверка принадлежности КС-языку слайд 3/4
- 222. Проверка принадлежности КС-языку слайд 4/4
- 223. Пример проверки принадлежности слайд 1/2
- 224. Пример проверки принадлежности слайд 2/2
- 225. Неразрешимые проблемы КС-языков
- 226. Машина Тьюринга и теория неразрешимых проблем Цель теории неразрешимых проблем состоит не только в том, чтобы
- 227. Решение математических вопросов В начале XX столетия математик Д. Гильберт поставил вопрос о поисках алгоритма, который
- 228. Описание машины Тьюринга Машина Тьюринга изображена на рисунке. Машина состоит из конечного управления, которое может находиться
- 229. Элементы машины Тьюринга Изначально на ленте записан вход, представляющий собой цепочку символов конечной длины. Символы выбраны
- 230. Формальное описание машины Тьюринга
- 231. Конфигурации машины Тьюринга слайд 1/2
- 232. Конфигурации машины Тьюринга слайд 2/2
- 233. Пример машины Тьюринга слайд 1/4
- 234. Пример машины Тьюринга слайд 2/4
- 235. Пример машины Тьюринга слайд 3/4
- 236. Пример машины Тьюринга слайд 4/4
- 237. Диаграмма переходов для машины Тьюринга
- 238. Пример диаграммы переходов Ниже представлена диаграмма переходов для машины Тьюринга из рассмотренного выше примера. Ее функция
- 239. Машина Тьюринга для усечённой разности слайд 1/4
- 240. Машина Тьюринга для усечённой разности слайд 2/4
- 241. Машина Тьюринга для усечённой разности слайд 3/4
- 242. Машина Тьюринга для усечённой разности слайд 4/4
- 243. Язык машины Тьюринга Способ допускания языка машиной Тьюринга уже описан интуитивно. Входная цепочка помещается на ленту,
- 244. Допустимость по останову
- 245. Программирование машины Тьюринга Цель данного раздела состоит в обосновании того, что машину Тьюринга можно использовать для
- 246. Память в состоянии слайд 1/3
- 247. Память в состоянии слайд 2/3
- 248. Память в состоянии слайд 3/3
- 249. Многодорожечные ленты
- 250. Пример многодорожечной ленты слайд 1/4
- 251. Пример многодорожечной ленты слайд 2/4
- 252. Пример многодорожечной ленты слайд 3/4
- 253. Пример многодорожечной ленты слайд 4/4
- 254. Подпрограммы Машины Тьюринга — это программы, и их полезно рассматривать как построенные из набора взаимодействующих компонентов,
- 255. Подпрограмма Copy слайд 1/2
- 256. Подпрограмма Copy слайд 2/2
- 257. Машина Тьюринга и Copy слайд 1/2
- 258. Машина Тьюринга и Copy слайд 2/2
- 259. Расширения машины Тьюринга Ниже представлены некоторые вычислительные модели, связанные с машинами Тьюринга и имеющие такую же
- 260. Многоленточные машины Тьюринга Многоленточная машина Тьюринга представлена на рисунке Устройство имеет конечное управление (состояния) и некоторое
- 261. Переход многоленточной МТ Переход многоленточной МТ зависит от состояния и символа, обозреваемого каждой головкой. За один
- 262. Эквивалентность одноленточных и многоленточных МТ Напомним, что рекурсивно перечислимые языки определяются как языки, допускаемые одноленточными МТ.
- 263. Время работы и «много лент к одной»
- 264. Недетерминированные МТ
- 265. Языки НМТ
- 266. Ограниченные МТ Выше были показаны обобщения машин Тьюринга, которые в действительности не добавляют никакой мощности в
- 267. Односторонняя лента
- 268. Усиленное ограничение
- 269. Мультистековые МТ слайд 1/2 Теперь рассмотрим несколько вычислительных моделей, основанных на обобщениях магазинных автоматов. Вначале рассмотрим,
- 270. Мультистековые МТ слайд 2/2
- 271. Счётчиковые машины
- 272. Мощность счётчиковых машин О языках счетчиковых машин стоит сделать несколько очевидных замечаний. Каждый язык, допускаемый счетчиковой
- 273. Машина Тьюринга и компьютеры Связь между компьютерами и машинами Тьюринга, а также структура универсальной машины Тьюринга
- 274. Неразрешимость и МТ В разделе выше были приведены рассуждения, которые неформально обосновывали существование проблем, не разрешимых
- 275. Неперечислимый язык
- 276. Двоичное представление МТ слайд 1/3
- 277. Двоичное представление МТ слайд 2/3
- 278. Двоичное представление МТ слайд 3/3
- 279. Язык диагонализации слайд 1/2
- 280. Язык диагонализации слайд 2/2
- 281. Неразрешимая РП-проблема
- 282. Рекурсивные языки слайд 1/2 Язык L называется рекурсивным, если L = L(M) для некоторой машины Тьюринга
- 283. Рекурсивные языки слайд 2/2
- 284. Дополнение рекурсивных и РП-языков
- 285. Пример дополнения
- 286. Универсальный язык слайд 1/3
- 287. Универсальный язык слайд 2/3
- 288. Универсальный язык слайд 3/3
- 289. Неразрешимость универсального языка
- 290. Неразрешимые проблемы и машины Тьюринга
- 291. Сведение проблем
- 292. Теорема о сведении
- 293. Машина Тьюринга и пустой язык
- 294. Теорема Райса и свойства РП-языков слайд 1/2
- 295. Теорема Райса и свойства РП-языков слайд 2/2
- 296. Проблемы описания языка машиной Тьюринга Согласно теореме, приведённой выше, все проблемы, связанные только с языками машин
- 297. Проблема соответствий Поста
- 298. Определение ПСП
- 299. Пример ПСП 1
- 300. Пример ПСП 2
- 301. Неразрешимость ПСП 2
- 302. Модифицированная ПСП
- 303. Пример МПСП
- 304. Формализация МПСП
- 305. Сведение к МПСП слайд 1/4
- 306. Сведение к МПСП слайд 2/4
- 307. Сведение к МПСП слайд 3/4
- 308. Сведение к МПСП слайд 4/4 5. Наконец, если допускающее состояние поглотило все ленточные символы, то оно
- 309. Проблемы, связанные с программами Прежде всего, отметим, что на любом привычном языке можно написать программу, которая
- 310. Неразрешимость неоднозначности КС-грамматик слайд 1/3
- 311. Неразрешимость неоднозначности КС-грамматик слайд 2/3
- 312. Неразрешимость неоднозначности КС-грамматик слайд 3/3
- 313. Дополнение списка языка
- 314. Неразрешимость КС-грамматики и регулярного выражения
- 315. Трудноразрешимые задачи Обсуждение вычислимости переносится на уровень ее эффективности или неэффективности. Предметом изучения становятся разрешимые проблемы,
- 316. Состав раздела
- 317. Краткое введение в трудноразрешимость Итак, предполагается, что класс проблем, разрешимых недетерминированными МТ за полиномиальное время, содержит,
- 318. Определение класса P
- 319. Алгоритм Краскала и МТ: проблемы Выход алгоритмов разрешения различных проблем может иметь много разных форм, например,
- 320. Пример кодирования графа Рассмотрим код для графов и предельных весов, который может быть входом для проблемы
- 321. Оценка кодирования
- 322. Дополнительные ленты МТ Дополнительные ленты используются для выполнения нескольких вспомогательных задач. На одной из лент можно
- 323. Оценка сложности алгоритма Краскала Теперь нетрудно завершить доказательство, что на многоленточной МТ каждый этап работы алгоритма
- 324. Недетерминированное полиномиальное время Фундаментальный класс проблем в изучении труднорешаемости образован проблемами, разрешимыми с помощью недетерминированной МТ
- 325. Проблема (задача) коммивояжера
- 326. Сложность решения НМТ
- 327. Полиномиальные сведения слайд 1/3 Основной метод доказательства того, что проблему Р2 нельзя решить за полиномиальное время
- 328. Полиномиальные сведения слайд 2/3
- 329. Полиномиальные сведения слайд 3/3
- 330. NP-полные проблемы
- 332. Скачать презентацию