Главная Промышленная автоматика.

1) Это список, а не множество из-за возможных повторений.

) Как мы увидим, способ кодирования данных задачи очень важен. Нетрудно показать, что если для распознавания используется ДМТ, то время решения задачи из примера 10.1 составляет в действительности Oj.j.(n2),

где п - длина входа. Но если вход закодировать двоичными числами, то длина входа будет равна сумме логарифмов чисел il, i; и та же стратегия даст алгоритм сложности Ojj(c"), где и - это уже длина двоичного входа и с>1.

. . ., ttj) содержит (где-то внутри себя) символ заключительного состояния q. Языком L{M), допускаемым машиной М, называют множество всех цепочек, допускаемых М.

Пример 10.1. Построим НТМ, допускающую такие цепочки вида

10>10>.. .10*,

что ЧЩч ДЛЯ некоторого множества /е{1,2,. . ., /г}. Иными

словами, цепочка w должна допускаться, если список ) целых чисел iu ii,. . ifc, представленный ею, можно разбить на два подсписка так, чтобы суммы чисел в них были равны. Эта задача известна как задача о разбиении. Доказано, что она NP-полна, если целые числа ij представлены своими двоичными кодами и размером задачи считается длина списка этих двоичных целых чисел

Мы построим трехленточную НМТ М, распознающую этот язык. Она просматривает свою входную ленту слева направо, и каждый раз, когда она доходит до блока вида OV, на вторую или третью ленту добавляются эти ij нулей, причем выбор ленты недетермини-рован. После того как машина дойдет до конца входа, она проверит, совпадают ли числа нулей на лентах 2 и 3, и, если да, допустит вход. Поэтому, если какая-нибудь последовательность выборов, указывающая, в какое из множеств помещать очередное число ij - в первое (на ленту 2) или во второе (на ленту 3), приводит к равным суммам, то эта НТМ допустит вход. Последовательности шагов, приводящие к неравным цепочкам на лентах 2 и 3, не принимаются во внимание, если хотя бы одна последовательность выборов срабатывает. Формально пусть

M = ({q„ qi.....q,}, {О, 1, b, $}, {О, 1}, б, b, q„ q,),

где функция переходов б задана на рис. 10.1.

На рис. 10.2 показаны две из многих последовательностей шагов, которые может сделать на входе 1010010 эта НМТ. Первая приводит к допускающему состоянию, вторая нет. Поскольку по крайней мере одна последовательность шагов приводит к допускающему состоянию, эта НМТ принимает 1010010. □

Определение. Говорят, что НМТ М имеет временную сложность Т(п), если для всякой допускаемой входной цепочки длины п найдется последовательность, состоящая не более чем из Т{п) шагов.



Состояние

Текущий символ на ленте

1 2 3

Новый символ, сдвиг головки на ленте

Новое состояние

Примечания

1, S

$, R

<7i

Машина помечает левые концы лент 2 и 3 знаком S и переходит в состояние q.

1,R 1,R

b, S b, S

b, s b, s

Здесь машина выбирает, писать очередной блок на ленте 2 (q) или 3 (9з).

0, R

1, S Ь, S

О, R Ь, S Ь, L

b.S b,S b,L

0, R

1. s b, S

b,S b,S b, L

0,R b,S b, L

«74

Машина переписывает блок из нулей на ленту 2, затем по достижении единицы на ленте 1 возвращается в состояние q. Если же на ленте 1 достигнут символ Ь,она переходит в состояние q, чтобы сравнить длины лент 2 и 3.

То же, что в состоянии q, но запись на ленту 3.

b,S b,S

0,L $,S

Сравнение длин лент 2 и 3.

Машина допускает вход.

Рис. 10.1. Переходы (шаги) НМТ. Каждая строка представляет один вариант

выбора.



((7„1010010, д,) 1010010, $q„ $q,) Н(1?2010010, $q„ $q,) h-(10(?al0010, Щ„ $q,) (-(10(7il0010, $0q, iq,) Ь(101<7з0010, $0q„ $q,) Ь{1010(7з010, $0q„ $Oqs) b( 10100(7310, $0(7з, $00<7з) h-(10100<7,10, $0q„$00q,) Ь (101001(7,0, $0(7a, $00<7,)

H (10100102, $002, $002)

b(1010010(7„ $0(7,0, $0(7,0) h-(1010010(74, $(/,00, $qfiO) h-(1010010(7,, (7,$00, 9.$00) h-(1010010(7,, (7,$00, ЯЛЩ Вход допускается

((7„ 1010010, (7„, (7„) b(?il010010, $q„ $q,) Н(1<7з010010, $(7з, $(7з) Н(10(7з10010, $<7з, $0(7з) -(10<7il0010, $q„ $0(7J Ь(101(7з0010, $(7з, $0<7з) Ь(1010(7з010, $(7з, $00(7з) Ь(10100(7з10, $(7з, $О00(7з) h-(10100(7,10, $(/„ $000(7i) Ь-(101001(7зО, $(7з. $000(7з) Ь(1010010<7з, $7з,$0000(7з) Н (1010010(7,, ?4$. $000(7,0) Остановка -нет следую-ш,его МО

Рис. 10.2. Две возможные последовательности шагов для НМТ.

которая приводит в допускающее состояние, и емкостную сложность S{n), если для всякой допускаемой входной цепочки длины п найдется последовательность шагов, приводящая в допускающее состояние, в которой число просмотренных головкой клеток на каждой ленте не превосходит S{n).

Пример 10.2. НМТ из примера 10.1 имеет временную сложность 2п+2 (худший случай - вход из п единиц) и емкостную сложность п+1. Другие разумные кодирования задачи о разбиении также дают эту сложность. Например, пусть В (i) - двоичное представление целого числа i и

Lj = #В (iJ #S (fj).. .#В (i) I существует такое множество

/S{1,2.....fe. что Si,= 2]t,l,

iel til f

где # - разделительный маркер. Чтобы распознать Lj, можно построить новую НМТ Mi, работа которой аналогична работе НМТ с рис. 10.1. Отличие состоит в том, что вместо копирования нулей на ленту 2 или 3 Mi запоминает на лентах двоичные числа. Каждое новое двоичное число, встречающееся во входной цепочке, прибавляется к числу на той или другой ленте.





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 [132] 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174

0.0037