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

Материал из WEGA
Перейти к навигации Перейти к поиску
(Создана новая страница размером Равнодоступная адресная машина }{Random access machine, RAM} {универсальная математиче...)
 
Нет описания правки
 
(не показано 9 промежуточных версий 2 участников)
Строка 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>\,W(n)</math>, которое ''хранится (содержится)'' в ячейке с адресом <math>\,n</math>.
двоичные слова, сопоставляющее с каждым адресом <math>n</math> то
 
слово <math>W(n)</math>, которое ''хранится (содержится)'' в
Программа —  это конечная последовательность команд, занумерованных числами <math>1,2,3,\ldots</math>. Счетчик команд — это переменная, принимающая значение из множества неотрицательных целых чисел.
ячейке с адресом <math>n</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>, является первой (начальной), а каждая следующая конфигурация, если она имеется, получается из текущей выполнением команды, номер которой указан в текущей конфигурации. Конфигурация, в которой счетчик команд равен нулю (ошибочная конфигурация) или номеру команды останова, может быть только последней (заключительной) конфигурацией протокола выполнения. Если выполнение '''равнодоступной адресной машины''' нормально завершается, то его результат — запись на выходной ленте, находящейся слева от печатающей головки.


Программа ---  это конечная последовательность
Каждая команда '''равнодоступной адресной машины''' имеет имя (код операции) и операнд. Операнд может быть одного из следующих типов: "<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>1,2,3,\ldots</math> . Счетчик
команд --- это переменная, принимающая значение из
множества неотрицательных целых чисел.


Состояние вычисления (конфигурация) --- это четверка
Модель вычислительной машины, получившая название [[равнодоступной адресной машины с хранимой программой|''равнодоступной адресной машины с хранимой программой'']] (или  [[РАСП]]), отличается от '''равнодоступной адресной машины''' лишь тем, что ее программа находится в памяти и может изменять себя.
<math>(x, W, k, y)</math>, где <math>x</math> --- непрочитанная часть входной
ленты, <math>W</math>--- состояние памяти, <math>k</math>~--- значение счетчика
команд, а <math>y</math> --- заполненная часть входной ленты.


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


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


Другие названия --- {\it
[[Файл:РАМ.png|700px]]
Машина с произвольным доступом к памяти,
РАМ.}


\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ложность РАМ|''Cложность РАМ'']].
* ''[[Сложность РАМ]]''.


==Литература==
==Литература==
[Ахо-Хопкрофт-Ульман],
* Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. —  М.: Мир, 1979.
 
* Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев. — Новосибирск: Наука. Сиб. отд-ние, 1994.
 
* Касьянов В.Н. Оптимизирующие преобразования программ. — М.: Наука, 1988.
 
* Касьянов В.Н.  Лекции по теории формальных языков, автоматов и сложности вычислений. — Новосибирск: НГУ, 1995.
 


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


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


[Касьянов/95]
[[Категория: Теория вычислений]]

Текущая версия от 13:41, 13 июля 2011

Равнодоступная адресная машина (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], является первой (начальной), а каждая следующая конфигурация, если она имеется, получается из текущей выполнением команды, номер которой указан в текущей конфигурации. Конфигурация, в которой счетчик команд равен нулю (ошибочная конфигурация) или номеру команды останова, может быть только последней (заключительной) конфигурацией протокола выполнения. Если выполнение равнодоступной адресной машины нормально завершается, то его результат — запись на выходной ленте, находящейся слева от печатающей головки.

Каждая команда равнодоступной адресной машины имеет имя (код операции) и операнд. Операнд может быть одного из следующих типов: "[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], что найдется эквивалентная РАСП (соответственно РАМ ), временная сложность которой не превосходит [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]

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


РАМ.png

См. также

Литература

  • Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. — М.: Мир, 1979.
  • Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев. — Новосибирск: Наука. Сиб. отд-ние, 1994.
  • Касьянов В.Н. Оптимизирующие преобразования программ. — М.: Наука, 1988.
  • Касьянов В.Н. Лекции по теории формальных языков, автоматов и сложности вычислений. — Новосибирск: НГУ, 1995.