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

янную, чем малый порядок роста сложности другого алгоритма. В таком случае алгоритм с быстро растущей сложностью может оказаться предпочтительнее для задач с малым размером - возможно, даже для всех задач, которые нас интересуют. Например, предположим, что временные сложности алгоритмов Ль Л а, Л з, Л 4 и Ai в действительности равны соответственно 1000«, ЮОп log п, 10п, и 2". Тогда Л 5 будет наилучшим для задач размера 2</г<9, Лз-для задач размера 10</г<58, Ла-при 59</г<1024, а Ах- при п>1024.

Прежде чем продолжать обсуждение алгоритмов и их сложностей, мы должны точно определить модель вычислительного устройства, используемого для реализации алгоритмов, а также условиться, что понимать под элементарным шагом вычисления. К сожалению, нет такой вычислительной модели, которая была бы хороша во всех ситуациях. Одна из основных трудностей связана с размером машинных слов. Например, если допустить, что машинное слово может быть целым числом произвольной длины, то всю задачу можно закодировать одним числом в виде одного машинного слова. Если же допустить, что машинное слово имеет фиксированную длину, то возникают трудности даже просто запоминания произвольно больших чисел, не говоря уже о других проблемах, которые часто удается обойти, если решаются задачи скромного размера. Для каждой задачи надо выбирать подходящую модель, которая точно отразит действительное время вычисления на реальной вычислительной машине.

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

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

Для описания алгоритмов желательно иметь обозначения, более естественные и легче понимаемые, чем программа для машины с произвольным доступом к памяти, машины с произвольным доступом к памяти и хранимой программой или машины Тьюринга. Поэтому мы введем также язык высокого уровня, называемый Упрощенным Алголом. Именно этот язык будет использоваться во всей книге для



Входная лента (то/1бно читатб)

Счетчик номанд

Программа

Сумматор

Память

Выходная лента (томно писать)

Рис. 1.3. Машина с произвольным доступом к памяти.

описания алгоритмов. Однако, чтобы понимать вычислительную сложность алгоритма, написанного на Упрощенном Алголе, мы должны соотнести Упрощенный Алгол с более формальными моделями. Это будет сделано в последнем разделе настоящей главы.

1.2. МАШИНЫ С ПРОИЗВОЛЬНЫМ ДОСТУПОМ к ПАМЯТИ

Машина с произвольным доступом к памяти (или, иначе, равнодоступная адресная машина - сокращенно рАм) моделирует вычислительную машину с одним сумматором, в которой команды программы не могут изменять сами себя.

РАМ состоит из входной ленты, с которой она может только считывать, выходной ленты, на которую она может только записывать, и памяти (рис. 1.3). Входная лента представляет собой последовательность клеток, каждая из которых может содержать целое число (возможно, отрицательное). Всякий раз, когда символ считывается с входной ленты, ее читающая головка сдвигается на одну клетку вправо. Выход представляет собой ленту, на которую машина может только записывать; она разбита на клетки, которые вначале все пусты. При выполнении команды записи в той клетке выходной ленты, которую в текущий момент обозревает ее головка, печатается целое число и головка затем сдвигается на одну клетку вправо. Как только выходной символ записан, его уже нельзя изменить.

Память состоит из последовательности регистров г, г,, . . ., /j, .... каждый из которых способен хранить произвольное целое



ЧИСЛО. На число регистров, которые можно использовать, мы не устанавливаем верхней границы. Такая идеализация допустима в случаях, когда

1) размер задачи достаточно мал, чтобы она поместилась в основную память вычислительной машины,

2) целые числа, участвующие в вычислении, достаточно малы, чтобы их можно было помещать в одну ячейку.

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

В принципе можно было бы добавить к нашему набору любые другие команды, встречающиеся в реальных вычислительных машинах, такие, как логические или литерные операции, и при этом порядок сложности задач не изменится. Читателю разрешается думать, что набор команд дополнен так, как это его устраивает.

Операнд может быть одного из следующих типов:

1) =i означает само целое число i и называется литералом,

2) i - содержимое регистра i (i должно быть неотрицательным),

3) и означает косвенную адресацию, т. е. значением операнда служит содержимое регистра /, где / - целое число, находящееся в регистре i; если /<;0, машина останавливается.

Эти команды хорошо знакомы всякому, кто программировал на языке ассемблера. Можно определить значение программы Р с помощью двух объектов: отображения с из множества неотрицательных целых чисел в множество целых чисел и «счетчика команд», который определяет очередную выполняемую команду. Функция с есть отображение памяти, а именно с (i) - целое число, содержащееся в регистре i {содержимое регистра i).

Вначале c(t)=0 для всех iO, счетчик команд установлен на первую команду в Р, а выходная лента пуста. После выполнения k-и команды из Р счетчик команд автоматически переходит на А+1 (т. е. на очередную команду), если k-я команда не была командой вида JUMP, HALT, JGTZ или JZERO.





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