Равнодоступная адресная машина: различия между версиями

Материал из WEGA
Перейти к навигации Перейти к поиску
Нет описания правки
Строка 1: Строка 1:
Равнодоступная адресная машина
'''Равнодоступная адресная машина''' ([[Random access machine|''Random access machine, RAM'']]) - универсальная математическая модель вычислений, которая является хорошим приближением к классу обычных, традиционных вычислительных машин с точки зрения отражения затрат времени и памяти при представлении данных и алгоритмов, целиком помещающихся в оперативной памяти.
}{Random access machine, RAM}
{универсальная математическая модель вычислений, которая
является хорошим приближением к классу обычных, традиционных
вычислительных машин с точки зрения отражения затрат времени
и памяти при представлении данных и алгоритмов, целиком
помещающихся в оперативной памяти.


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


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


Память --- это последовательность подряд пронумерованных
Память --- это последовательность подряд пронумерованных ячеек, каждая из которых способна хранить двоичную запись произвольного целого числа. Обращение к значению, хранимому в некоторой ячейке, осуществляется по адресу (номеру) этой
ячеек, каждая из которых способна хранить двоичную запись
ячейки. Ячейка с номером 0 называется ''сумматором''. Адресация может быть не только ''абсолютной'', когда явно
произвольного целого числа. Обращение к значению, хранимому
указывается номер ячейки, но и косвенной. При ''косвенной адресации'' указывается адрес некоторой другой ячейки
в некоторой ячейке, осуществляется по адресу (номеру) этой
(называемой ''ссылкой'', или ''указателем''), содержимое которой рассматривается в качестве абсолютного
ячейки. Ячейка с номером 0 называется ''сумматором''.
Адресация может быть не только ''абсолютной'', когда явно
указывается номер ячейки, но и косвенной. При ''косвенной
адресации'' указывается адрес некоторой другой ячейки
(называемой ''ссылкой'', или ''указателем''),
содержимое которой рассматривается в качестве абсолютного
адреса адресуемой ячейки.
адреса адресуемой ячейки.


Состояние памяти --- это отображение <math>W</math> адресов в
Состояние памяти --- это отображение <math>W</math> адресов в двоичные слова, сопоставляющее с каждым адресом <math>n</math> то
двоичные слова, сопоставляющее с каждым адресом <math>n</math> то
слово <math>W(n)</math>, которое ''хранится (содержится)'' в ячейке с адресом <math>n</math>.
слово <math>W(n)</math>, которое ''хранится (содержится)'' в
ячейке с адресом <math>n</math>.


Программа ---  это конечная последовательность
Программа ---  это конечная последовательность команд, занумерованных числами <math>1,2,3,\ldots</math> . Счетчик
команд, занумерованных числами <math>1,2,3,\ldots</math> . Счетчик
команд --- это переменная, принимающая значение из множества неотрицательных целых чисел.
команд --- это переменная, принимающая значение из
множества неотрицательных целых чисел.


Состояние вычисления (конфигурация) --- это четверка
Состояние вычисления (конфигурация) --- это четверка <math>(x, W, k, y)</math>, где <math>x</math> --- непрочитанная часть входной ленты, <math>W</math>--- состояние памяти, <math>k</math>~--- значение счетчика команд, а <math>y</math> --- заполненная часть входной ленты.
<math>(x, W, k, y)</math>, где <math>x</math> --- непрочитанная часть входной
ленты, <math>W</math>--- состояние памяти, <math>k</math>~--- значение счетчика
команд, а <math>y</math> --- заполненная часть входной ленты.


Выполнение '''Р.а.м.''' начинается с выполнения первой
Выполнение '''Р.а.м.''' начинается с выполнения первой команды программы, нормально завершается выполнением команды
команды программы, нормально завершается выполнением команды
останова и описывается протоколом выполнения --- последовательностью конфигураций, в которой конфигурация <math>(x, W, 1, e)</math>, где <math>x</math> --- вход, <math>e</math> --- пустая цепочка и <math>W(k) = 0</math> для любого <math>k</math>, является первой (начальной), а каждая следующая конфигурация, если она имеется, получается из текущей выполнением команды, номер которой указан в текущей конфигурации. Конфигурация, в которой счетчик команд равен нулю (ошибочная конфигурация) или номеру команды останова, может быть только последней (заключительной) конфигурацией протокола выполнения. Если выполнение {\bf
останова и описывается протоколом выполнения ---
Р.а.м.} нормально завершается, то его результат --- запись на выходной ленте, находящейся слева от печатающей головки.
последовательностью конфигураций, в которой конфигурация
<math>(x, W, 1, e)</math>, где <math>x</math> --- вход, <math>e</math> --- пустая цепочка и
<math>W(k) = 0</math> для любого <math>k</math>, является первой (начальной), а
каждая следующая конфигурация, если она имеется, получается
из текущей выполнением команды, номер которой указан в
текущей конфигурации. Конфигурация, в которой счетчик команд
равен нулю (ошибочная конфигурация) или номеру команды
останова, может быть только последней (заключительной)
конфигурацией протокола выполнения. Если выполнение {\bf
Р.а.м.} нормально завершается, то его результат --- запись
на выходной ленте, находящейся слева от печатающей головки.


Каждая команда
Каждая команда '''Р.а.м.''' имеет имя (код операции) и операнд. Операнд может быть одного из следующих типов: "<math>=i</math>" --- означает само число <math>i</math> и называется литералом; "<math>i</math>" --- содержимое ячейки <math>i</math>; <math>*i</math>" --- используется для косвенной адресации, т.е. значением операнда служит содержимое ячейки, адрес которой имеется в ячейке с номером <math>i</math>. Обозначая через <math>V(a)</math> значение операнда <math>a</math>, получаем: <math>V(=i)=i</math>; <math>V(i) =W(i)</math> и <math>V(*i)=W(W(i))</math>, где <math>W</math> --- текущее состояние памяти. Набор команд '''Р.а.м.''' традиционен для реальных ЭВМ и состоит из команд считывания и запоминания, арифметических и логических команд, команд перехода, команд ввода и вывода и команды останова.
'''Р.а.м.'''
имеет имя (код операции) и
операнд. Операнд может быть одного из следующих типов:
"<math>=i</math>" --- означает само число <math>i</math> и называется литералом;
"<math>i</math>" --- содержимое ячейки <math>i</math>; "<math>*i</math>" --- используется для
косвенной адресации, т.е. значением операнда служит
содержимое ячейки, адрес которой имеется в ячейке с номером
<math>i</math>. Обозначая через <math>V(a)</math> значение операнда <math>a</math>, получаем:
<math>V(=i)=i</math>; <math>V(i) =W(i)</math> и <math>V(*i)=W(W(i))</math>, где <math>W</math> ---
текущее состояние памяти. Набор команд '''Р.а.м.''' традиционен для
реальных ЭВМ и состоит из команд считывания и запоминания,
арифметических и логических команд, команд перехода, команд
ввода и вывода и команды останова.


Модель вычислительной машины, получившая название {\it
Модель вычислительной машины, получившая название [[равнодоступной адресной машины с хранимой программой|''равнодоступной адресной машины с хранимой программой'']] (или ''РАСП''), отличается от '''Р.а.м.''' лишь тем, что ее программа находится в памяти и может изменять себя.
равнодоступной адресной машины с хранимой программой} (или
''РАСП''), отличается от '''Р.а.м.''' лишь тем, что ее
программа находится в памяти и может изменять себя.


Как при равномерном, так и при логарифмическом весах команд
Как при равномерном, так и при логарифмическом весах команд для любой '''Р.а.м.''' (соответственно ''РАСП'') с временной сложностью <math>T(n)</math> существует такая постоянная <math>k</math>, что найдется эквивалентная ''РАСП'' (соответственно {\bf Р.а.м.} ), временная сложность которой не превосходит <math> kT(n)</math>.
для любой '''Р.а.м.''' (соответственно ''РАСП'') с
временной сложностью <math>T(n)</math> существует такая постоянная <math>k</math>,
что найдется эквивалентная ''РАСП'' (соответственно {\bf
Р.а.м.} ), временная сложность которой не превосходит <math>
kT(n)</math>.


''Недетерминированная'' '''Р.а.м.''' (или ''НРАМ'')
''Недетерминированная'' '''Р.а.м.''' (или ''НРАМ'') получается из '''Р.а.м.''' добавлением команды ВЫБОР<math> (L_1,
получается из '''Р.а.м.''' добавлением команды <math>ВЫБОР (L_1,
L_2,\ldots, L_r)</math>, означающей, что недетерминированы выбор и последующее выполнение одного из операторов <math>L_1,
L_2,\ldots, L_r)</math>, означающей, что недетерминированы выбор и
L_2,\ldots,L_r.</math>  
последующее выполнение одного из операторов <math>L_1,
L_2,\ldots,L_r.</math>


Другие названия --- {\it
Другие названия --- ''Машина с произвольным доступом к памяти, РАМ.''
Машина с произвольным доступом к памяти,
РАМ.}


\begin{figure}[h]\begin{center}\unitlength=1mm
\begin{figure}[h]\begin{center}\unitlength=1mm

Версия от 11:37, 22 мая 2009

Равнодоступная адресная машина (Random access machine, RAM) - универсальная математическая модель вычислений, которая является хорошим приближением к классу обычных, традиционных вычислительных машин с точки зрения отражения затрат времени и памяти при представлении данных и алгоритмов, целиком помещающихся в оперативной памяти.

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

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

Память --- это последовательность подряд пронумерованных ячеек, каждая из которых способна хранить двоичную запись произвольного целого числа. Обращение к значению, хранимому в некоторой ячейке, осуществляется по адресу (номеру) этой ячейки. Ячейка с номером 0 называется сумматором. Адресация может быть не только абсолютной, когда явно указывается номер ячейки, но и косвенной. При косвенной адресации указывается адрес некоторой другой ячейки (называемой ссылкой, или указателем), содержимое которой рассматривается в качестве абсолютного адреса адресуемой ячейки.

Состояние памяти --- это отображение [math]\displaystyle{ W }[/math] адресов в двоичные слова, сопоставляющее с каждым адресом [math]\displaystyle{ n }[/math] то слово [math]\displaystyle{ W(n) }[/math], которое хранится (содержится) в ячейке с адресом [math]\displaystyle{ n }[/math].

Программа --- это конечная последовательность команд, занумерованных числами [math]\displaystyle{ 1,2,3,\ldots }[/math] . Счетчик команд --- это переменная, принимающая значение из множества неотрицательных целых чисел.

Состояние вычисления (конфигурация) --- это четверка [math]\displaystyle{ (x, W, k, y) }[/math], где [math]\displaystyle{ x }[/math] --- непрочитанная часть входной ленты, [math]\displaystyle{ W }[/math]--- состояние памяти, [math]\displaystyle{ k }[/math]~--- значение счетчика команд, а [math]\displaystyle{ y }[/math] --- заполненная часть входной ленты.

Выполнение Р.а.м. начинается с выполнения первой команды программы, нормально завершается выполнением команды останова и описывается протоколом выполнения --- последовательностью конфигураций, в которой конфигурация [math]\displaystyle{ (x, W, 1, e) }[/math], где [math]\displaystyle{ x }[/math] --- вход, [math]\displaystyle{ e }[/math] --- пустая цепочка и [math]\displaystyle{ W(k) = 0 }[/math] для любого [math]\displaystyle{ k }[/math], является первой (начальной), а каждая следующая конфигурация, если она имеется, получается из текущей выполнением команды, номер которой указан в текущей конфигурации. Конфигурация, в которой счетчик команд равен нулю (ошибочная конфигурация) или номеру команды останова, может быть только последней (заключительной) конфигурацией протокола выполнения. Если выполнение {\bf Р.а.м.} нормально завершается, то его результат --- запись на выходной ленте, находящейся слева от печатающей головки.

Каждая команда Р.а.м. имеет имя (код операции) и операнд. Операнд может быть одного из следующих типов: "[math]\displaystyle{ =i }[/math]" --- означает само число [math]\displaystyle{ i }[/math] и называется литералом; "[math]\displaystyle{ i }[/math]" --- содержимое ячейки [math]\displaystyle{ i }[/math]; [math]\displaystyle{ *i }[/math]" --- используется для косвенной адресации, т.е. значением операнда служит содержимое ячейки, адрес которой имеется в ячейке с номером [math]\displaystyle{ i }[/math]. Обозначая через [math]\displaystyle{ V(a) }[/math] значение операнда [math]\displaystyle{ a }[/math], получаем: [math]\displaystyle{ V(=i)=i }[/math]; [math]\displaystyle{ V(i) =W(i) }[/math] и [math]\displaystyle{ V(*i)=W(W(i)) }[/math], где [math]\displaystyle{ W }[/math] --- текущее состояние памяти. Набор команд Р.а.м. традиционен для реальных ЭВМ и состоит из команд считывания и запоминания, арифметических и логических команд, команд перехода, команд ввода и вывода и команды останова.

Модель вычислительной машины, получившая название равнодоступной адресной машины с хранимой программой (или РАСП), отличается от Р.а.м. лишь тем, что ее программа находится в памяти и может изменять себя.

Как при равномерном, так и при логарифмическом весах команд для любой Р.а.м. (соответственно РАСП) с временной сложностью [math]\displaystyle{ T(n) }[/math] существует такая постоянная [math]\displaystyle{ k }[/math], что найдется эквивалентная РАСП (соответственно {\bf Р.а.м.} ), временная сложность которой не превосходит [math]\displaystyle{ kT(n) }[/math].

Недетерминированная Р.а.м. (или НРАМ) получается из Р.а.м. добавлением команды ВЫБОР[math]\displaystyle{ (L_1, L_2,\ldots, L_r) }[/math], означающей, что недетерминированы выбор и последующее выполнение одного из операторов [math]\displaystyle{ L_1, L_2,\ldots,L_r. }[/math]

Другие названия --- Машина с произвольным доступом к памяти, РАМ.

\begin{figure}[h]\begin{center}\unitlength=1mm \begin{picture}(99,24) \put(0,31){\special{em: graph 68.pcx}} \end{picture}\end{center}\end{figure}

См. также

Cложность РАМ.

Литература

[Ахо-Хопкрофт-Ульман],

[Касьянов/88],

[Евстигнеев-Касьянов/94],

[Касьянов/95]