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

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

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

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

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

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

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

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

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

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

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

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

Таблица 12.1.

КомандаДействиеЛогарифмический вес








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

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

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

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

Пример.

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

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

Таблица 12.2.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

Когда команда выполняется -й раз, сумматор содержит , а содержит . Эта команда выполняется раз. При равномерном весовом критерии суммарное время — . При логарифмическом весовом критерии суммарное время равно , где суммирование ведется по . Поскольку , получаем

Емкостная сложность программы при равномерном критерии равна , при логарифмическом — .

Содержание раздела