1.5. МОДИФИКАЦИЯ РАМ

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

1. Неветвящиеся программы

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

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

обычный алгоритм умножения матриц содержит циклы, которые следует выполнить точно раз, при этом от команд разветвления требуется только сравнение параметра цикла с

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

Кроме того, поскольку каждая неветвящаяся программа может обращаться только к конечному числу регистров памяти, удобно присвоить этим регистрам имена. Потому при ссылке на регистры мы будем употреблять символические адреса (символы или цепочки букв), а не целые числа.

Устранив потребность в командах READ, JUMP, JGTZ и JZERO, мы остаемся с командами и арифметическими операциями из системы команд РАМ. Нам не нужна команда ибо на остановку указывает конец программы. Можно обойтись и без назначив в качестве выходных переменных определенные символические адреса; выходом программы будет значение, принимаемое этими переменными к окончанию работы программы.

Наконец, можно "встроить" и в арифметические операции, заменяя последовательности вида

на Весь набор команд неветвящейся программы выглядит так:

где х, у и z - символические адреса (или переменные), постоянная. Легко видеть, что любую последовательность команд

и арифметических операций в сумматоре можно заменить последовательностью, составленной из пяти выписанных выше команд.

С неветвящейся программой связаны два выделенных набора переменных — входы и выходы. Функцией, вычисляемой данной неветвящейся программой, называется множество значений выходных переменных (в определенном порядке), выраженных через значения ее входных переменных.

Пример 1.4. Рассмотрим вычисление полинома

Входными переменными служат коэффициенты и неопределенная переменная х Выходной переменной будет По правилу Горнера вычисляется так:

На рис. 1.16 приведены неветвящиеся программы, соответствующие этим выражениям. Правило Горнера для произвольного теперь должно быть понятно. Для каждого нас есть неветвящаяся программа из шагов, вычисляющая полином степени. В гл. 12 мы покажем, что для вычисления произвольного полинома степени по его коэффициентам требуется умножений и сложений. Таким образом, если в качестве модели брать неветвящиеся программы, правило Горнера оптимально.

Если брать в качестве модели вычислений неветвящуюся программу, то временная сложность последовательности программ равна числу шагов программы как функции от Например, правило Горнера порождает последовательность с временной

Рис. 1.16. Неветвящиеся программы, соответствующие правилу Горнера.

сложностью Заметим, что измерение временной сложности есть не что иное, как подсчет числа арифметических операций. Емкостная сложность последовательности программ равна числу переменных, участвовавших в программе, снова как функции от Программы примера 1.4 имеют емкостную сложность

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

2. Битовые вычисления

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

1) все переменные принимают значения или 1, т. е. это биты,

2) используются логические операции вместо арифметических обозначается через через через через

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

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

Другое применение битовой модели — логические сети (схемы). Неветвящиеся программы с двоичными входами и операциями

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

Пример 1.5. На рис. 1.17,а приведена программа для сложения двух двуразрядных чисел и Выходные переменные — это такие числа что Неветвящаяся программа на рис. 1.17, а вычисляет

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

Рис. 1.17, (см. скан) а — битовая программа для сложения; б — эквивалентная логическая сеть

3. Операции с двоичными векторами

Можно было бы не ограничивать значения переменных символами и 1, а разрешить переменным принимать в качестве значения любой вектор из и 1. Фактически двоичные векторы фиксированной длины очевидным образом соответствуют целым числам, так что здесь не допускается ничего такого, что не допускалось бы в РАМ, т. е., когда это удобно, просто разрешаются регистры неограниченного размера.

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

Хотя это сравнение и бросает некоторую тень на вычисления о двоичными векторами, большинство вычислительных машин выполняют логические операции на двоичных векторах, составляющих полное машинное слово, за одну команду. Поэтому двоичные векторы длины 100 можно было бы обрабатывать за три или четыре шага (вместо одного для чисел). Тем не менее на результаты о временной и емкостной сложностей алгоритмов при применении модели с двоичными векторами, мы должны смотреть cum grano salis, ибо размер задачи, при котором модель становится нереалистичной, в этом случае много меньше, чем в случае моделей РАМ и неветвящихся программ. Порядок величин при применении модели с двоичными векторами мы будем обозначать через

4. Деревья решений

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

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

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

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

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

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