1626435697-9d9ede204f9baad60159c2d6531787c7 (844297), страница 6
Текст из файла (страница 6)
Адресная лиииила состоит из бесконечного числа регистров, занумерованных двоичными числами. Первые три регистра служат для специальных целей: вход, метод и сумматор. (Мы рассматриваем лишь модель с хранимой программой.) В регистры можно записывать слова в алфавите (О, 1). Агля определенности выберем систему команд 1.ОАР =1, ГОАР 1, ГОАР Ы, ЗТОКЕ 1, ЗТОЙЕ Ы, АРР 4, БРВ („ЗН1ЕТ 1 (сдвиг содержимого сумматора на число разрядов, равное содержимому регистра 1, знак этого содержимого определяет направление сдвига), А(ЧР 1 (поразрядное булево умножение), Ом 1, ЕХСЕРБ(тЕ Ок 1, НАЕТ.
!машиной М будем называть пару (Р, б, где Р=р„..., рь — программа (т. е. список конкретных команд р!), а 1 — функция, ограничивающая длину содержимого регистров: при работе над входом длины и в регистры можно записывать слова длины ровно 1(л). Работа машины М над словом ш определяется, как обычно: программа Р записывается в память машины, начиная с четвертого регистра; прн Л-и срабатывании команды ГОАР вход в сумматор записывается й-я компонента входа; результатам работы (если машина остановилась) считается слово, получаемое последовательным приписыванием всех слов, засылавшихся в выходной регистр; если при выполнении какой-то 3! Из теорем 1.1 и 1.2 следует, что в отношении временной сложности (а также и емкостной — это остается в качестве упражнения) модели РАМ и РАСП эквивалентны с точностью до постоянного множителя, т.
е. порядки величин их сложностей одинаковы для одного и того же алгоритма. Обычно мы будем выбирать из этих двух моделей модель РАМ, поскольку она проще '). гл с, модели вычислении $.5. МОДИФИКйьЦИЯ РДМ РАМ и РАСП вЂ” более сложные модели вычислений, чем это часто бывает необходимо. Поэтому мы введем ряд других моделей, которые наследуют одни черты РАМ и игнорируют другие. Оправданием для них будет то, что суммарный вес игнорируемых команд не превосходит некоторой фиксированной доли веса любого эффективного алгоритма для задач, к которым данная модель применяется. !. Неветвяц(ився программы Первая наша модель — неветвящаяся программа.
Для многих задач разумно ограничиться рассмотрением класса РАМ-программ, в которых команды разветвления используются только для того, чтобы повторить последовательность команд, причем число повторений пропорционально размеру входа и. В этом случае можно "развернуть" программу для каждого размера и, копируя повторяющиеся команды надлежащее число раз. В результате получается последовательность иеветвящихся программ (т. е. программ без циклов), вообще говоря, возрастающей длины — по одной программе для каждого значения и.
Пример 1.3. Рассмотрим умножение двух целочисленных матриц размера ихи. Разумно ожидать, что в РАМ-программе число выполнений цикла не будет зависеть от фактических значений элементов матрицы. Поэтому можно в качестве полезного упрощения считать, что допускаются только такие циклы, у которых проверка конца зависит лишь от и, т. е. от размера задачи. Например, обыч- команды получается слово, не помещающееся в регистр, то переполняющая часть етого слова бесследно исчезает. Пусть !м(ш) н зм(ш) — соответственно чнсло шагов н память прн работе М над щ а 1,:н(л) н зм(л) — время н память в худшем случае, т.
е. 1м(и)= шах 1м(пс), зд,(и)= шах зм(пс). см С К л см(к л Очевидно, что 1ой зм(л)~!(л) (здесь н ниже через 1ой л обозначается длнна двоичного представлення числа л). Разумно ввести ограничение на фуннцню й 1(и)( шах ( шах (р;(, )оп !з, (и)). 1<С<а Первый член, а именно шах(рс1, стоит для того, чтобы программа могла помешаться в память машнны естественным образом — одна команда в один регистр. Поскольку обязательно !(л)а1ойзм(л), то для адресной машины всегда зм(л)~ ~сдс(л).
Если наложить на 1(л) еще н некоторые требования конструнруемостн (см. гл. 10), например считать, что!(л) можно вызволять на машине с !(л) ячейками без переполнений за время, не большее 2плс, то почтн весь материал настоящей кннгн можно будет основать на понятии адресной машины. К числу важных преимушеств адресной машины по сравнению с РАМ, РАСП н машиной Тьюринга относятся возможность в ее терминах точно н достаточно адекватно ставить вопрос о нижних оценках сложностн н для задач с заведомо небольшой, например квадратичной, верхней оценкой. — Прим. перев. 32 ьк модиФикАния глм ный алгоритм умножения матриц содержит циклы, которые следует выполнить точно и раз, при этом от команд разветвления требуется только сравнение параметра цикла с и.
Е) Развертывание циклов в программе позволяет обходиться без команд разветвления. Оправданием служит то, что во многих задачах не более чем постоянная доля сложности работы РАМ- программы приходится на команды, управляющие циклом. Подобным же образом часто можно допускать, что входные операторы образуют лишь постоянную долю сложности работы программы, и мы устраняем их, допуская, что перед началом выполнения программы в памяти находится конечное множество входов, требуемых при данном и.
Действие косвенной адресации можно определить для фиксированного и„ если предполагать, что регистры, используемые для нее, содержат величины, зависящие только от и и не зависящие от значений входных переменных. Поэтому мы будем считать, что наши неветвящиеся программы не имеют косвенных адресаций. Кроме того, поскольку каждая неветвящаяся программа может обращаться только к конечному числу регистров памяти, удобно присвоить этим регистрам имена. Потому при ссылке на регистры мы будем употреблять символические адреса (символы или цепочки букв), а не целые числа. Устранив потребность в командах ЕВАМ, Л)МР, ) ОТО и )УЕЛО, мы остаемся с командами ЬОАР, ВТОЕЕ, %К1ТЕ, НАЬТ и арифметическими операциями из системы команд РАМ.
Нам не нужна команда НАЬТ, ибо на остановку указывает конец программы. Можно обойтись к без%Е1ТЕ, назначив в качестве выходных переменных определенные символические адреса; выходом программы будет значение, принимаемое этими переменными к окончанию работы программы. Наконец, можно "встроить" ЬОА(У и ВТОРОЕ в арифметические операции, заменяя последовательности вида ЬОАВ а А01) Ь ВТОРОЕ с на с а+Ь. Весь набор команд неветвящейся программы выглядит так: х — у+г х — у — г г -уэг г -у/г х З где х, у и г — символические адреса (или переменные), а ~ — постоянная. Легко видеть, что любую последовательность команд 2 л.
хко, дж. хоинрофт, дж. кльман ЗЗ ГЛ. Г. МОДЕЛИ ВЫЧИСЛЕНИЙ (.ОА0, БТРЕ и арифметических операций в сумматоре можно заменить последовательностью, составленной из пяти выписанных выше команд, С неветвящейся программой связаны два выделенных набора переменных — входы и выходы. Функцией, вычисляемой данной неветвящейся программой, называется множество значений выходных переменных (в определенном порядке), выраженных через значения ее входных переменных. а=2 п=З 1 — аеих 1 -1+а, 1 1их р 1+а, г а,их 1 1+а, 1 Гих 1 1+а, 1 1»х р — 1+а, 1 — а,их Р 1+ "е Рис, 1.16. Невегвящиеся программы, соответствующие правилу Гориера.
Пример 1.4. Рассмотрим вычисление полинома р (х) =а„х" +а„,х' '+... +а,х+а,. Входными переменными служат коэффициенты а„а„..., а„ и неопределенная переменная х Выходной переменной будет р. По правилу Горнера р (х) вычисляется так: 1) а,х+а„ для п=!, 2) (а,х+а,) х+а, для п=2, 3) ((а,х+а,) х+а,) х+а, для п=З. На рис. 1.16 приведены неветвящиеся программы, соответствующие этим выражениям. Правило Гориера для произвольного и теперь должно быть понятно. Для каждого п у нас есть неветвящаяся программа из 2п шагов, вычисляющая полинам и-й степени, В гл. 12 мы покажем, что для вычисления произвольного полинома и-й степени по его коэффициентам требуется и умножений и и сложений. Таким образом, если в качестве модели брать неветвящиеся программы, правило Горнера оптимально.
Г) Если брать в качестве модели вычислений неветвящуюся программу, то временная сложность последовательности программ равна числу шагов и-й программы как функции от и. Например, правило Горнера порождает последовательность с временной слож- са. молиоикхция нам постыл 2и. Заметим, что измерение временной сложности есть не что иное, как подсчет числа арифметических операций. Емкостная сложность последовательности программ равна числу переменных, участвовавших в программе, снова как функции от и. Программы примера 1.4 имеют емкостную сложность и+4. Определение. В случае когда в качестве модели вычислений берутся неветвящиеся программы, говорят, что данная задача имеет временную или емкостную сложность О (1(и)), если найдется последовательность программ для ее решения с временной или емкостной сложностью не более с((и) для некоторой постоянной с.
(О„Ц(и)) читается так; "порядка 1(и) ша~ов неветнящейся программы". Индекс Л снизу обозначает "арифметический" — это основная характеристика неветвящнхся программ.) Таким образом, вычисление полинома имеет временную, а также и емкостную сложность О„(и). 2. Битовые вычисления Очевидно, что модель неветвящихся программ основана на равномерной весовой функции. Как мы уже отмечали, этот вес годится в предположении, что все вычисляемые величины имеют "разумный" размер. Существует простая модификация модели неветвящихся программ, которая соответствует логарифмической весовой функции.
Эта модель, называемая битовым вычислениелз, по существу, является той же неветвящейся программой, но то,тько в ней 1) все переменные принимают значения 0 или 1, т. е. это биты, 2) используются логические операции вместо арифметических ') (апс! обозначается через ух, ог — через '„~, ехс!пя не ог — через Я, по1 — через -1). Для битовой модели арифметические операции над целыми числами ! и ! занимают по меньшей мере !(!)+1Ц) шагов, что соответствует логарифмическому весу операндов. В самом деле, умножение и деление с помощью наилучших известных алгоритмов для умножения или деления ( на ! требуют более чем !(!)+!Ц) шагов.
При битовых вычислениях порядок величин обозначается через Он. Битовая модель полезна, когда речь идет об основных операциях, таких, как арифметические, которые нсходны в других моделях. Например, для модели неветвящихся программ умножение двух и-разрядных двоичных целых чисел можно осуществить за Ол(1) шагов, тогда как для битовой модели наилучший известный результат — это Ов(и 1од и 1ой 1ой и) шагов.
Другое применение битовой модели — логические сети (схемы). Неветвящиеся программы с двоичными входами и операциями вза- ') Таким образом, набор команд для наших РАМ должен состоять из этих операций. гл. ь молили вычислвнии имно однозначно соответствуют комбинационным логическим сетям, вычисляющим набор булевых функций. Число шагов такой программы — зто число логических элементов в сети. Пример 1.5, На рис. !.17,а приведена программа для сложения двух двуразрядных чисел [а,а,) и (Ь, Ь,). Выходные переменные— зто такие числа с„с, и с„что (а, а,)+(Ь,Ь,)=(с, с, с,). Неветвящаяся программа на рнс. 1.17, а вычисляет с„=ао®Ь„ с, =((а„ЛЬ„)Яа,)ЯЬ„ с, = ((а, ЛЬ.) Л(а, ~l Ьг)) ~/(аг ЛЬ,). На рис, 1,17,б изображена соответствующая логическая сеть.
В качестве упражнения предлагаем показать, что сложение двух л-разрядных чисел можно выполнить за Ов(л) шагов. Д а, Ь, ао Ь со ~ ао 9 со и аолдо и 9а1 с, аЩб, лг а, д, а илие у-а,л б, са л' ~~у со Рпс. Ь!?, о — битовая программа лля сложения; б — эквивалентная логическая сеть.
кз. модиоиклция влм 3. Операции с двоичными векторами Можно было бы ие ограничивать значения переменных символами 0 и 1, а разрешить переменным принимать в качестве значения любой вектор из 0 и !. Фактически двоичные векторы фиксированной длины очевидным образом соответствуют целым числам, так что здесь не допускается ничего такого, что не допускалось бы в РАМ, т. е., когда это удобно, просто разрешаются регистры неограниченного размера. Однако, как мы увидим, в тех немногих алгоритмах, где применяется модель с двоичными векторамп, длина векторов будет значительно больше числа битов, требуемых для представления размера задачи. Величина большинства целых чисел, фигурирующих в таком алгоритме, будет того же порядка, что и размер задачи.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
