Структуры данных и модели вычислений



             

Равнодоступная адресная машина


Равнодоступная адресная машина (РАМ) — это числовая модель вычислительного устройства. Эта модель является наиболее близкой из рассмотренных к реальным вычислительным машинам и позволяет наиболее реалистично применять теоретические оценки сложности алгоритмов к реальным вычислениям.

Память машины состоит из регистров (ячеек). Каждый регистр имеет адрес и может содержать произвольное число. Регистр с номером 0 называется сумматором.

Программа — последовательность пронумерованных команд. Команда имеет вид

Коды операций

Операнд может быть одного из трех видов

где — натуральное число.

Содержимое регистра с номером обозначим через . Значение операнда определяется в зависимости от его вида следующим образом.

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

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

Основание логарифма при получении асимптотических оценок не имеет существенного значения.

Вес операнда определяется в зависимости от его вида следующим образом:

Таблица 12.1.

КомандаДействиеЛогарифмический вес
очередное число
очередное число
печать
переход на команду с номером 1
переход на команду с номером , если
переход на команду с номером , если
конец вычислений1

Например, команда имеет логарифмический вес

Временная сложность программы определяется как сумма весов всех выполненных команд с учетом их многократного выполнения.

Емкостная сложность программы определяется как сумма по всем регистрам длин максимальных чисел, побывавших в этих регистрах.

Пример.

Рассмотрим вычисление :

Этот псевдокод легко может быть заменен РАМ-программой, представленной в таблице 12.2.




Содержание  Назад  Вперед