(см. сложность) Элементы теории сложности алгоритмов и вычислений. Хахаян (2010) ((см. сложность) Элементы теории сложности алгоритмов и вычислений. Хахаян (2010).pdf), страница 6

Схематическое Язобрадаине датерЩгаироваиио'й («яшшочмоймашины Тьюринга (ДМТ),управляющего устройства с конечным числом состояний, читающей/пишущей головки, которая может считывать изаписывать символы, и неограниченной в обе стороны ленты,разделенной на бесконечное число одинаковых ячеек,занумерованных целыми числами ...,-2,-1,ОД,2,3....Программа для ДМТ, или ДМТпрограмма,определяется следующими компонентами:(1) конечным множеством Г символов, записываемых наленте,подмножеством Z с:Г входных символов ивыделенным пустым множеством b с Г\Б;(2) конечным множеством состояний Q, в котором выделеныначальное состояние q0 и два заключительных состоянияqy,qN I(3) функцией перехода 3: W \ {Чг> <?.v}) X I -»• QX Г X {” 1.

1}.Таким образом, для пары состояния q, и слова с, определено,какой символ надо записать вместо с„ в какое состояниеперейти и куда передвинуться головке: вправо или влево.Работа программы определяется так. Входом длядетерминированной программы является слово x e l* . Словозаписывается на ленте в ячейках с номерами I, 2, , \х\ поодному символу в ячейке. Все другие ячейки в начальныймомент времени содержат пустой символ и называютсяпустыми. Программа начинает работу, находясь в состоянииq0, при этом читающая/пишущая головка находится надячейкой с номером 1 .Далее процесс вычислений осуществляется шаг за шагом.Если текущее состояние q есть qY или q^, то процессвычисления заканчивается, при этом результатом будет «да»,если <7 = qY и «нет», если q = qN В противном случае текущеесостояние принадлежит множеству Q\{qY9N,}, при этомголовка читает на ленте некоторый символ seF и определенозначение 5(q, s).

Предположим, что 5(q, s) = (q’, s'. Д). В этомслучае головка стирает s, пишет на этом месте s' и сдвигаетсяна одну ячейку влево, если Д= П, или на одну ячейку вправо,если Д=+1. Одновременно управляющее устройство переходитиз состояния q в q'. На этом заканчивается один шаг процессавычисления и программа готова" к выполнению следующегошага.Пример простой ДМТ - программы М представлен на рис.2.2. Функция перехода 8 определена таблицей, где величина,записанная в у-й строке и s-м столбце, есть значение 5(q , s ).Рис.

2.3 иллюстрирует вычисление по программе Мпри входех=10100. Здесь указаны состояние, расположение головки исодержимое непустых ячеек ленты до и после каждого шага.Заметим, что это вычисление после восьми шаговоканчивается в состоянии q ^, поэтому на входе 10100 ответомбудет «да». В общем случае будем говорить, что программа М ,имеющая входной алфавит £, п р и н и м а е т хеЕ* в том и тольков том случае, когда, будучи примененной ко входу х онаостанавливается в состоянии q Y. Язык L y , р а с п о з н а в а е м ы йпрограммой М, задаётся следующим образом:1м={хшТ: М принимает х).£?“■I1U r ,* -ir(енчй,—1)Ъ'< Я и Ь %~ 1)>-ч1.ч*О,&(94.0#-f1)19Шm9tЩЧ\> Чг .

f t . в п 9м)Рис. 2,2. Пример зДМТ-программы Ж » » (Г,д).Нетрудно видеть, что программа, представленная на рис.2.2, распознаёт язык***два последних символа 1слова х являются нулями уОтметим, что это определение распознавания языка нетребует, чтобы программа М останавливалась при всех входахиз £*; М обязана останавливаться лишь при входах из L M .Если х принадлежит £*\ L M , то работа программы М на хможет либо закончиться в состоянии q N, либо можетбесконечно продолжаться без остановки. ДМТ-программа,соответствующая нашему пониманию алгоритма, должнаостанавливаться на всех словах входного алфавита. В этомсмысле программа на рис.

2.2 является алгоритмической, таккак, начиная работать на любом слове из символов 0, 1 онабудет останавливаться.Соответствие между распознаванием языков и решениемзадач распознавания определяется следующим образом. Будемговорить,что ДМТ-программа Мреш аетзадачураспознавания П при кодировании е , если М останавливаетсяна всех словах, составленных из букв входного алфавита, и L M= L [ H , е \. Программа на рис. 2.2 иллюстрирует этосоответствие.

Рассмотрим следующую задачу распознаванияиз теории чисел.ДЕЛИМОСТЬ НА ЧЕТЫРЕУСЛОВИЕ. Дано положительное целое число N .ВОПРОС. Существует ли положительное целое число т ,такое, что N = 4 т ?При стандартном кодировании целое число Nпредставляется словом из 0 и 1, т. е. двоичной записью этогочисла. Так как положительное целое число делится на 4 тогдаи только тогда, когда последние две цифры двоичной записиэтого числа являются нулями, то программа, изображенная нарис. 2.2, «решает» при нашем стандартном кодированиизадачу ДЕЛИМОСТЬ НА ЧЕТЫРЕ.i j 0T F t it f :■” i *1 1! -1 mVЧо ■ - | Ь ] I ! о 1 i | 0 f o T T FVЧо ; - 1 * \1 1 1 о 1 1 1i * T T T T ~ RVЧь :1 1 ! о i J !1 0V'■ - ! ь 1 » П Т i j10 | 0 | b | VПо ■ - 1 Н ! » | о | "Пi 0 1 6.

1 b | ...Ча ■Ч) ;"■ 1 k 1i i. 1 0 t i 1 0 T o T T T -Чг : _2_LLj1 i р г]- t |! 0 t * i * FЧг 'V- 1V И P T 1 L tЗ ЖРРис. 2.3. Вычисление . но программе Л],(см. рис. 2,2), при входе 10100.Заметим, что ДМТ-программой можно пользоватьсятакже и для вычисления функций. Пусть программа М,имеющая входной алфавит Z и ленточный алфавит Г,останавливается при любом входе из Г*.

Тогда М вычисляетфункцию / м:которая для каждого х-з2 ’* определяетсяследующим образом. Если М, начиная работать при входе х,останавливается, то в качестве f jx ) берется слово,составленное из символов, записанных после остановкимашины в ячейках с номерами 1 , 2 , 3, ..., включая последнююнепустую ячейку. Программа М, представленная на рис. 2.2,вычисляет функцию{ОД}*—►{0,1,6}*, которая отображает,каждое слово х<з{0 , 1 }* в слово / ы(х), получаемое из худалением двух крайних справа символов (если |х|<2, то Мвыдает в качестве f jx ) пустое слово). Хорошо известно, чтоDMT-программы способны решать задачи гораздо болеесложные, чем в рассмотренном примере.Создание ДМТ-программ, реализующих более сложныеалгоритмы, достигается за счёт увеличения числа состояний ичисла символов в алфавите.

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

Во-вторых, схему работы машины Тьюринга легкосебе представить без получения специальных знаний, чегонельзя сказать о компьютерах и программном обеспечении.Соответственно, несложно понять, какие алгоритмы могутбыть реализованы на машине Тьюринга и к каким результатамможет привести работа любой ДМТ-программы, т.е. любогоалгоритма для машины Тьюринга.Определим понятие «временная сложность». Время,требуемое ДМТ-программой М для вычисления при входе х,есть число шагов, выполняемых до момента остановки. Еслипрограмма М останавливается на всех входах х&Е*, товременную сложность Тм:Z+—*Z+ этой программы можноопределить так:Гсуществует такое слово хеТ,\х\=п,Тм(я)— m ax j in: что вьтслеяце т программе М на вхоiд$ х требует времени mДетерминированная программа М называется полиномиальнойДМТ-программой, если существует такой полином р, что длявсех weZ+, Ту(п)<р(п).Определим первый важный класс языков - класс Р.

Онопределяется следующим образом:р f г. существует полиномиальная ДМТщограмма)rдля которой L = LM'}Будем говорить, что задача распознавания П принадлежитклассу Р при кодировании е, если ЦП,е]е Р, т. е. существуетполиномиальная ДМТ-программа, которая решает задачу Ппри кодировании е. Мы не будем приводить конкретныесхемы кодирования и будем просто говорить, что задачараспознавания П принадлежит классу Р.Приведём теперь примеры (см. также Введение) задач изкласса Р и некоторые общие методы получения алгоритмовдля доказательства того, что задача принадлежит классу Р.МИНИМАЛЬНОЕ ОСТОВНОЕ ДЕРЕВОУСЛОВИЕ Заданы п вершин и положительные целые веса дугмежду ними.ВОПРОС Чему равен наименьший возможный вес остовногодерева?Замечание.

Переформулируйте эту задачу в виде задачираспознавания.Сначала кажется (см. задачу КОММИВОЯЖЕР), чтозадача МИНИМАЛЬНОЕ ОСТОВНОЕ ДЕРЕВО толькоусугубляет трудности задачи КОММИВОЯЖЕР: перебор помножеству всех замкнутых путей заменяется перебором поеще более необозримому множеству произвольных остовныхдеревьев. Тем не менее, эта интуиция в данном случае в корнеошибочна:эффективныеалгоритмыдлязадачиМИНИМАЛЬНОЕ ОСТОВНОЕ ДЕРЕВО существуют.Алгоритм 6 Упрощенный алгоритм Прима______________ ___________Вход: т > О , > 0, Vi, j € (1,..., п) {Список ребер задается матрицей связности{щ} ~ не оптимальный вариант}Выход: Остов А минимального веса..4 <- {1} {можно выбрать произвольную вершину}for all iteration g l.jido {достаточно, чтобы процесс сошелся}ЬооVbest.

tMtWfor all i 6 {l..n: i £ A} do {no всем не включенным в А узлам}for all j g A do {no всем включенным в А узлам}1 if щ > Wbea then {wij более дешевая дорога из остова}W'test *- и>у {улучшаем оценку}Vlcst = i {выбираем v( для добавления}end ifend forend forA *- A UVt,eet {добавляем вершину с самым дешевым путемдо остова}end forreturn А {Индексы вершин минимального остова G}Опишем один из них, так называемый алгоритм Прима. Вэтом алгоритме минимальный остов строится постепенно,сначала выбираетсяпроизвольная вершина, котораявключается в остов, затем, на каждой итерации, к текущемуостову добавляетсянаиболее дешевое ребро (u,v),соединяющее какую-либо вершину из остова и, с какой-либовершиной v не из остова.

Попробуйте доказать корректностьалгоритма Прима, приводимого выше. Нетрудно заметить,что сложность приведённого алгоритма Прима есть 0 (п ).Можно ли уменьшить сложность этого алгоритма (см. (2), стр.13)?.КРАТЧАЙШИЙ ПУТЬ В ГРАФЕУСЛОВИЕ Заданы п вершин в графе и длины дуг междуними.ВОПРОС Найти наименьшую длину пути, ведущего из однойзаданной вершины в другую заданную вершину?Замечание. Сформулируйте и эту задачу как задачураспознавания.Конечно, существует переборный алгоритм, решающийэту задачу.