Кузнецов О.П., Адельсон-Вельский Г.М. - Дискретная математика для инженеров (1048837), страница 73
Текст из файла (страница 73)
Для любой системы т логических функций и переменных существует бинарная программа, вычисляющая ее за время, не превосходящее а+и. (В отличие от оценок времени для вычисления одной функции здесь число команд аида у:=о не меньше т и входит в опенку.) Как уже отмечалось, число команд в бинарных и операторных программах асимптотически равно 2л/а. Если же в программе использовать и операторы, и условные переходы, то, как показано в 1551, эта оценка понижается вдвое. Более подробные сведения об оценках сложности и методах программной реализации логических функций и автоматсв можно получить в [531. Здесь отметим лишь, что логический автомат всегда может быть реализован бинарной программой, не требующей промежуточной памяти. ГЛАВА ДЕВЯТАЯ КОМБИНАТОРНЫЕ ЗАДАЧИ И ТРУДОЕМКОСТЬ ВЫЧИСЛЕНИЙ вл. ТРУДОЕМКОСТЬ ОТНОСИТЕЛЬНО РАЗНЫХ МАШИН В классической теории алгоритмов (см.
гл. 5) задача считается разрешимой, если существует решающий ее алгоритм. Однако для реализации некоторых алгоритмов при любых разумных с точки зрения физики предположениях о скорости выполнения элементарных шагов может потребоваться больше времени, чем по современным воззрениям существует вселенная. Поэтому возникает потребность конкретизировать понятие разрешимости и придать ему оценочный, количественный характер, введя такие характеристики алгоритмов, которые позволяли бы судить о возможности и целесообразности их практического применения.
95! Среди различных возможных характеристик алгоритмов наиболее важными с прикладной точки зрения являются две: время и память, расходуемые при вычислении. Физическое время вычисления алгоритма характеризуется произведением тг, где г' — число действий (шагов) вычисления, а т — среднее физическое время реализации одного шага. Число шагов г определяется описанием алгоритма в данной алгоритмической модели, это — величина математическая, не зависящая от особенностей физической реализации модели.
Напротив, т зависит от реализации и определяется скоростью обработки сигналов в элементах, записи и считывания информации и т, д. Поэтому число дейатвий т можно считать математическим временем вычисления алгоритма, определяющим физическое время вычисления с точностью до константы т, зависящей от реализации. Память как количественная характеристика алгоритма определяется количеством з единиц памяти (ячеек ленты машины Тьюринга или машинных слов в современных ЭВМ), используемых в процессе вычисления алгоритма. Ясно, что эта величина по порядку не может превосходить числа шагов вычисления: з(р(, где р — максимальное число единиц памяти, используемых в данной машине на одном шаге. Напротив, г может существенно превосходить з, например, возможно соотношение Г)з'.
С этой точки зрения время более тонко отражает сложность алгоритма, чем память; н это — одна из причин, по которой исследованию временных характеристик алгоритма уделяется большее внимание. Существуют и другие, прикладные причины (в частности, то, что, грубо говоря, память дешевле времени), которые здесь обсуждаться не будут. Так или иначе, здесь будет идти речь о трудоемкости' алгоритмов и задач, решаемых алгоритмами. Итак, трудоемкость алгоритма — это число элементарных действий, выполненных при его вычислении.
Полной характеристикой конкретного варианта задачи является его формальное описание. Характеристикой сложности описания можно считать его объем, который иногда называют размерностью задачи (например, для изоморфизма графов размерностью задачи можно считать число символов в матрицах смежности графов); тогда исследование ' Епге одни терман ддя этого понятия — распоостраненаый, но менее удачный — временная сложность.
352 трудоемкости алгоритма рассматривается как исследование зависимости трудоемкости вычисления от размерности задачи, решаемой алгоритмом. И в математике, и на практике в конечном счете нас интересуют не алгоритмы сами по себе, а задачи, которые они решают. Одна и та же задача может решаться различными алгоритмами и на разных машинах. Если машина М зафиксирована, то трудоемкостью данной задачи относительно машины М называется минимальная из трудоемкостей алгоритмов, решающих задачу на машине М. Задач, трудоемкость которых была бы определена точно, довольно мало; хорошим результатом считается определение ее по порядку, т. е.
с точностью до множителя, ограниченного некоторой константой. Чаще удается оценить ее сверху или снизу. Оценку сверху получают, указав конкретный алгоритм решения задачи: по определению, трудоемкость задачи не превосходит трудоемкости любого из решающих ее алгоритмов. Оценки трудоемкости снизу — гораздо более трудное дело; их получают обычно из некоторых общих соображений (например, мощностных или информационных). О них здесь говорить не будем. Можно ли говорить об инвариантности теории трудоемкости вычислений? Иначе говоря, возможны ли утверждения о трудоемкости вычислений, сохраняющиеся при переходе к любой алгоритмической модели? Что касается прямых количественных оценок, то инвариантамн не являются не только константы, но и степени.
Например, доказано, чтотрудоемкость распознавания симметричности слова длины и относительно его середины на машине Тьюринга не меньше, чем са', тогда как для любой ЭВМ, имеющей доступ к памяти по адресу, допускающей операции над адресами, легко написать программу, решающую эту задачу с линейной трудоемкостью. Таким образом, скорости вычислений на разных моделях различны. Однако строить теорию трудоемкости вычислений, привязываясь к некоторым конкретным моделям, неудобно ни для теории, ни для практики. Для теории— потому, что такая привязка не дает достаточно объективных характеристик трудоемкости задачи, т. е. не позволяет отделить влияние особенностей выбранной модели от специфики самой задачи; для практики — потому, что разнообразие реальных машин растет, и нужны общие понятия и методы оценки трудоемкости решения задач, которые сохраняют свою силу при любых изменениях в мире компью- 23 — 750 353 теров.
Поэтому инвариантная теория трудоемкости нужна, и вопрос ие в том, возможна ли она, а в том, как ее построить (т. е. какие инварианты найти). Для того чтобы обсуждать этот вопрос, прежде всего следует посмотреть, как меняется трудоемкость при переходе от одной машины к другой. Это рассмотрение мы начнем с некоторого краткого обзора парка абстрактных машин, о которых будет идти речь. До сих пор в явном ниде была описана только одна абстрактная машина — машина Тьюринга ($5.2).
Однако в $8.4 неявно использовалась машина другого типа, гораздо более близкая к современным ЭВМ, в которой возможен доступ к памяти по адресам. Такая машина, называемая машиной с произвольным доступом к памяти, может на следующем шаге переходить к любой ячейке с указанным адресом (команды условного и безусловного переходов) и реализовать команды-операторы (см. 5 8.4) вида Ь: ((аь ам ..., ар) (выполнить операцию ) над содержимым ячеек а„аэ,...,а, и результат положить в ячейку Ь). Возможны различные варианты моделей машины с произвольным доступом к памяти (см., например, (13)); в более сложных вариантах допускаются операции над адресами.
Здесь мы не будем рассматривать все эти варианты, ограничившись фиксацией лишь одной простой модели — машины элементарных логических операций, или кратко Ь-машины. Относительно других моделей абстрактных машин ограничимся констатацией нх основных свойств, которых будет достаточно при последующих рассмотрениях.
Будем считать, что каждая машина имеет конечное число устройств (головок, устройств управления головками, процессоров — устройств, выполняющих элементарные операции, и т.д.), каждое устройство и каждая ячейка памяти могут находиться в одном из конечного числа возможных состояний (состояние ячейки памяти — этозависанный в ней символ), и выполнение любого элементарного действия -(шага) зависит от информации из конечного числа ячеек памяти, ограниченного некоторой константой р. Будем говорить, что все ячейки читаются на данном шаге, Полное состояние машины, т.
е. набор состояний устройств, состояний ячеек памяти и указание ячеек, читаемых в настоящий момент, называется, как и в $5.2, конфигурацией машины. И наконец, еще одно вступительное замечание. Алгоритм, осуществляемый машиной, может быть реализован двояким образом: он может быть «встроен» в управляю- щее устройство или записан в памяти машины. В первом случае машина является специализированной и может выполнять только данный алгоритм; чтобы изменить алгоритм, надо поменять управляющее устройство. Таковы машины Тьюринга в примерах 5.2 — 5.9.
Во втором случае запись алгоритма в памяти называется программой, а сама машина — программируемой; алгоритм, встроенный в управляющее устройство, решает задачу исполнения программ, записанных в памяти машины. Такова универсальная машина Тьюринга (см. 9 5.2) и все реальные универсальные ЭВМ. В обоих случаях начальная конфигурация машины — состояния всей памяти и всех устройств — полностью определяет процесс вычисления.
Машина элементарных логических операций (В-маши. на) — это машина с произвольным доступом к памяти, имеющая следующую систему команд: х:=0; Х: — - Д; х:= 1у; х:=уйг; х: = у '/ г; „конец", где х, у, г — адреса ячеек памяти;:= — знак присвоения (см. в 8.4). Программа элементарных логических операций (Е:программа) с однократной записью — это программа (в смысле $8,4), состоящая нз указанных команд, в которой запись в каждую ячейку памяти производится не более одного раза (читать ячейку можно неоднократно). Можно было бы дополнить систему команд А-машины командами ввода информации в ячейки памяти для данных, ввода программ и вывода результатов решения задач, однако будем считать, что эти элементы памяти доступны для ввода информации и обозрения извне (трудоемкость этих действий следует считать пропорциональной количеству элементов памяти, куда надо ввести или откуда надо вывести информацию). Пусть программа и данные (значения двоичных переменных) находятся в разных секциях памяти, и каждая секция имеет свою адресацию.
Тогда можно так перекодировать программу с однократной записью Ззз (изменить адреса данных), что номера команд программы и адреса ячеек памяти, в которых эти команды производят запись, станут одинаковыми, т. е. будут иметь внд: 1:1: = =Уг(1=1,2, ..., 1 — 1), где выражения У~ имеют вид либо О, либо 1, либо 1, либо ) у, либо )дй, либо у'и'А (только в конце п ограммы стоит команда «конец»;). В. осле того как программа с однократной записью кончит работу, переменные гы ге, ..., гг ь хранящиеся в ячейках памяти с адресами 1, 2,...,г — 1, будут удовлетворять системе уравнений г,=Рс (1=1, 2,...,1 — 1), где )7~ имеют соответственно вид О, 1, Яу, )гь зрхга или гт'~' гю Если во всех командах адреса аргументов меньше адресов результатов, т, е. справа от знака:= стоят меньшие числа, чем слева, то предопределены значения всех переменных вн гш ..., гг ы В противном случае программа читает не то, что сама записала.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
