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

Порядок а<д<с


Ь<с

Порядок

Порядок

Порядок

Порядок

а<с<Ь

с<а<Ь

Ь<с <а

с<д<а

Рис. 1.18. Дерево решений.

со входами с точностью до порядка. Поэтому разумно рассматривать модель, в которой все шаги дают разветвления, возникаюш,ие в результате сравнения двух величин.

Обычно программу, состоящую из разветвлений, представляют в виде двоичного дерева называемого деревом решений. Каждый внутренний узел представляет один из шагов решения. Тест, представленный корнем, выполняется первым, и затем "управление" передается одному из его сыновей в зависимости от исхода теста. В общем случае управление переходит от узла к одному из его сыновей (причем выбор в каждом случае зависит от исхода теста в этом узле), до тех пор пока не будет достигнут лист. Нужный выход находится на достигнутом листе.

Пример 1.6. На рис. 1.18 изображено дерево решений для программы, сортирующей три числа а, b и с. Тесты указаны заключенными в овал сравнениями в узлах; управление переходит влево, если ответ на тест - "да", и вправо, если - "нет". □

Временная сложность дерева решений равна высоте этого дерева как функции размера задачи. Обычно мы хотим измерить наибольшее число сравнений, которые приходится делать, чтобы найти нужный путь от корня к листу. Порядок величин при использовании модели деревьев решений (сравнений) мы будем обозначать через Ос. Заметим, что общее число узлов в дереве может значительно превосходить его высоту. Например, дерево решений для сортировки п чисел должно содержать по крайней мере и! листьев, хотя его высота может быть п log п.

) По поводу определений, касающихся деревьев, см. разд. 2.4.



1.6. ПРОСТЕЙШАЯ МОДЕЛЬ ВЫЧИСЛЕНИЙ: МАШИНА ТЬЮРИНГА

1.6. ПРОСТЕЙШАЯ МОДЕЛЬ ВЫЧИСЛЕНИЙ: МАШИНА ТЬЮРИНГА

Для доказательства того, что для вычисления данной функции требуется какое-то минимальное время, нужна некоторая модель, столь же общая, как те модели, которые у нас были, но более простая. Система команд должна быть ограничена, насколько возможно, хотя эта модель должна быть в состоянии не только вычислить все то, что может вычислить РАМ, но и сделать это "почти" так же быстро. Под словом "почти" мы будем подразумевать "полиномиальную связанность".

Определение. Говорят, что неотрицательные функции fi(n) и /а(п) полиномиально связаны (эквивалентны), если найдутся такие полиномы pi{x) и pt{x), что для всех п справедливы неравенства /,(«)<Р1 (/.{«)) и(/,(«)).

Пример 1.7. Две функции ft(n)=2n и ft{n)=n полиномиально связаны: можно взять pi{x)=2x, ибо 2п*<2п, и р{х)=х, ибо п{2пу. Но и* и 2" не являются полиномиально связанными, так как нет такого полинома р{х), что р(п)2" для всех п. □

В настоящее время единственный класс функций, для которых мы можем применить такие общие вычислительные модели, как машины Тьюринга, чтобы получить нижние оценки вычислительной сложности, составляют "быстро растущие" функции. Например, в гл. 11 будет показано, что некоторые задачи требуют экспоненциальные время и память. (Функция /(п) называется экспоненциальной, если существуют такие постоянные Ci>0, fti>l, С2>0 и kC>\, что Ciftf/(яХса/г? для всех, кроме конечного числа, значений п.) Относительно полиномиальной связанности все экспоненциальные функции, по существу, одинаковы; любая функция, полиномиально связанная с экспоненциальной, сама экспоненциальна.

Таким образом, это побуждает нас использовать простую модель, для которой временная сложность задач полиномиально связана с их сложностью на РАМ. В частности, модель, которую мы будем применять, а именно многоленточная машина Тьюринга, может потребовать (/(п))* шагов чтобы сделать то, что РАМ при логарифмической весовой функции делает за / (п) шагов, но не больше. Итак, временные сложности на РАМ и машинах Тьюринга, как мы увидим, полиномиально связаны.

Определение. Многоленточная машина Тьюринга (МТ) изображена на рис. 1.19. Она состоит из нескольких, скажем к, лент.

На самом деле верна более низкая оценка 0([f{n)\ogf{n) log log/(я)]"), но мы интересуемся оценками с точностью до полиномов и нас вполне устроит результат с четвертой степенью (см. разд. 7.5).



/< лент <

Управ/гяющее устройство с конечным чис/том состоянии


Рис. 1.19. Многоленточная машина Тьюринга.

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

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

1) изменить состояние управляющего устройства,

2) напечатать новые символы на лентах вместо старых в каких-нибудь или во всех клетках под головками,

3) сдвинуть какие-нибудь или все головки независимо друг от друга на одну клетку влево (L) или вправо (R) либо оставить на месте (S).

Формально Л-ленточная машина Тьюринга задается семеркой (Q, Т, I, б, Ь, q„, qi),

1) Q - множество состояний,

2) Т - множество символов на лентах,

3) / - множество входных символов, IsT,

4) b - пустой символ, Ъ б T-I,

5) - начальное состояние,





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.0019