Персональные инструменты
 

Random Access Machine — различия между версиями

Материал из CustisWiki

Перейти к: навигация, поиск
м (реплицировано из внутренней CustisWiki)
 
м (Содержимое страницы заменено на «#REDIRECT [[discopal:{{PAGENAME}}]]»)
 
(не показаны 3 промежуточные версии 2 участников)
Строка 1: Строка 1:
==Определение==
+
#REDIRECT [[discopal:{{PAGENAME}}]]
'''Random Access Machine''' («машины со произвольным доступом») — теоретическая модель вычислителя (см. например [[машина Тьюринга]]),
+
напоминающая современный компьютер, программируемый непосредственно в терминах инструкций процессора (или на языке Assembler) (в теории сложности вычислений под ''машинами'' традиционно понимают ''single-purpose machines''), т. е. машины, созданные для решения какой-либо одной фиксированной задачи, а в терминах программиста это скорее программы).
+
 
+
RAM-машина состоит из (См. Рисунок):
+
* Конечная входная read-only лента, куда записываются входные данные.
+
* Полубесконечная выходная write-only лента, куда записываются результат работы машины.
+
* Бесконечное число регистров <math>r_0,r_1,r_2,\ldots,</math>, каждый из которых может хранить целое число, причем регистр <math>r_0</math> является выделенным, и называется «сумматором» — этот регистр используется при арифметических операциях как накопитель, т. е. как второй операнд и место хранения результата.
+
* Программа, состоящая из конечного числа инструкций, каждая из которых содержит адрес и команду с операндом. Таблица со списком команд приведена ниже.
+
Важный, характеристический момент — в качестве операнда можно использовать как произвольный регистр, так и регистр, номер которого храниться в другом регистре — так называемая косвенная адресация.
+
* Регистр-счетчик «PC», указывающий на текущую команду.
+
 
+
Обратите внимание, что несмотря на «примитивный ассемблер», RAM-машины потенциально мощней любых существующих компьютеров, и физически нереализуемы — т. к. оперируют бесконечной памятью, доступ к любой ячейке-регистру которой осуществляется мгновенно, при выполнении соответствующей инструкции, и каждая ячейка этой памяти может содержать произвольное целое число (т. е. неограниченна по размеру). Но эта модель уже дает возможность вводить более-менее формальные определения времени выполнения программы, и соответственно, сложности алгоритма.
+
 
+
==Иллюстрация==
+
<latex>
+
%Created by jPicEdt 1.x
+
%Standard LaTeX format (emulated lines)
+
%Wed Aug 24 21:22:49 MSD 2005
+
\unitlength 1.3mm
+
\begin{picture}(120.31,90.00)(0,0)
+
 
+
\linethickness{0.15mm}
+
%Rectangle(10.00,10.00)(90.00,20.00) 
+
\put(10.00,10.00){\line(1,0){80.00}}
+
\put(10.00,10.00){\line(0,1){10.00}}
+
\put(90.00,10.00){\line(0,1){10.00}}
+
\put(10.00,20.00){\line(1,0){80.00}}
+
%End Rectangle
+
 
+
\linethickness{0.15mm}
+
%Polygon 0 0(20.00,20.00)(20.00,10.00)
+
\put(20.00,10.00){\line(0,1){10.00}}
+
%End Polygon
+
 
+
\linethickness{0.15mm}
+
%Polygon 0 0(30.00,20.00)(30.00,10.00)
+
\put(30.00,10.00){\line(0,1){10.00}}
+
%End Polygon
+
 
+
\linethickness{0.15mm}
+
%Polygon 0 0(40.00,20.00)(40.00,10.00)
+
\put(40.00,10.00){\line(0,1){10.00}}
+
%End Polygon
+
 
+
\linethickness{0.15mm}
+
%Polygon 0 0(50.00,20.00)(50.00,10.00)
+
\put(50.00,10.00){\line(0,1){10.00}}
+
%End Polygon
+
 
+
\linethickness{0.15mm}
+
%Polygon 0 0(60.00,20.00)(60.00,10.00)
+
\put(60.00,10.00){\line(0,1){10.00}}
+
%End Polygon
+
 
+
\linethickness{0.15mm}
+
%Polygon 0 0(70.00,20.00)(70.00,10.00)
+
\put(70.00,10.00){\line(0,1){10.00}}
+
%End Polygon
+
 
+
\linethickness{0.15mm}
+
%Polygon 0 0(80.00,20.00)(80.00,10.00)
+
\put(80.00,10.00){\line(0,1){10.00}}
+
%End Polygon
+
 
+
\linethickness{0.15mm}
+
%Polygon 0 0(90.00,20.00)(95.00,20.00)
+
\put(90.00,20.00){\line(1,0){5.00}}
+
%End Polygon
+
 
+
\linethickness{0.15mm}
+
%Polygon 0 0(90.00,10.00)(95.00,10.00)
+
\put(90.00,10.00){\line(1,0){5.00}}
+
%End Polygon
+
 
+
\linethickness{0.15mm}
+
%Polygon 0 0(95.00,20.00)(95.00,20.00)
+
 
+
 
+
%End Polygon
+
 
+
\linethickness{0.15mm}
+
%Bezier 0 0(95.00,20.00)(98.75,13.28)(98.75,13.13)
+
\qbezier(95.00,20.00)(98.75,13.28)(98.75,13.13)
+
%End Bezier
+
 
+
\linethickness{0.15mm}
+
%Bezier 0 0(98.75,13.13)(98.75,12.97)(95.00,10.00)
+
\qbezier(98.75,13.13)(98.75,12.97)(95.00,10.00)
+
%End Bezier
+
 
+
\linethickness{0.15mm}
+
%Rectangle(50.00,30.00)(90.00,60.00) 
+
\put(50.00,30.00){\line(1,0){40.00}}
+
\put(50.00,30.00){\line(0,1){30.00}}
+
\put(90.00,30.00){\line(0,1){30.00}}
+
\put(50.00,60.00){\line(1,0){40.00}}
+
%End Rectangle
+
 
+
\linethickness{0.15mm}
+
%Rectangle(10.00,50.00)(40.00,60.00) 
+
\put(10.00,50.00){\line(1,0){30.00}}
+
\put(10.00,50.00){\line(0,1){10.00}}
+
\put(40.00,50.00){\line(0,1){10.00}}
+
\put(10.00,60.00){\line(1,0){30.00}}
+
%End Rectangle
+
 
+
\linethickness{0.15mm}
+
%Rectangle(20.00,70.00)(50.00,80.00) 
+
\put(20.00,70.00){\line(1,0){30.00}}
+
\put(20.00,70.00){\line(0,1){10.00}}
+
\put(50.00,70.00){\line(0,1){10.00}}
+
\put(20.00,80.00){\line(1,0){30.00}}
+
%End Rectangle
+
 
+
\linethickness{0.15mm}
+
%Polygon 0 0(40.00,80.00)(40.00,70.00)
+
\put(40.00,70.00){\line(0,1){10.00}}
+
%End Polygon
+
 
+
\linethickness{0.15mm}
+
%Polygon 0 0(50.00,80.00)(55.00,80.00)
+
\put(50.00,80.00){\line(1,0){5.00}}
+
%End Polygon
+
 
+
\linethickness{0.15mm}
+
%Polygon 0 0(50.00,70.00)(55.00,70.00)
+
\put(50.00,70.00){\line(1,0){5.00}}
+
%End Polygon
+
 
+
\linethickness{0.15mm}
+
%Polygon 0 0(105.00,90.00)(105.00,90.00)
+
 
+
 
+
%End Polygon
+
 
+
\linethickness{0.15mm}
+
%Bezier 0 0(55.00,80.00)(58.75,73.28)(58.75,73.13)
+
\qbezier(55.00,80.00)(58.75,73.28)(58.75,73.13)
+
%End Bezier
+
 
+
\linethickness{0.15mm}
+
%Bezier 0 0(58.75,73.13)(58.75,72.97)(55.00,70.00)
+
\qbezier(58.75,73.13)(58.75,72.97)(55.00,70.00)
+
%End Bezier
+
 
+
\linethickness{0.15mm}
+
%Rectangle(70.00,70.00)(80.00,80.00) 
+
\put(70.00,70.00){\line(1,0){10.00}}
+
\put(70.00,70.00){\line(0,1){10.00}}
+
\put(80.00,70.00){\line(0,1){10.00}}
+
\put(70.00,80.00){\line(1,0){10.00}}
+
%End Rectangle
+
 
+
\linethickness{0.15mm}
+
%Bezier 0 0(65.00,80.00)(65.47,73.28)(66.88,73.13)
+
\qbezier(65.00,80.00)(65.47,73.28)(66.88,73.13)
+
%End Bezier
+
 
+
\linethickness{0.15mm}
+
%Bezier 0 0(66.88,73.13)(68.28,72.97)(65.00,70.00)
+
\qbezier(66.88,73.13)(68.28,72.97)(65.00,70.00)
+
%End Bezier
+
 
+
\linethickness{0.15mm}
+
%Polygon 0 0(65.00,70.00)(70.00,70.00)
+
\put(65.00,70.00){\line(1,0){5.00}}
+
%End Polygon
+
 
+
\linethickness{0.15mm}
+
%Polygon 0 0(70.00,80.00)(65.00,80.00)
+
\put(65.00,80.00){\line(1,0){5.00}}
+
%End Polygon
+
 
+
\put(35.00,75.00){\makebox(0,0)[cc]{$x_2$}}
+
 
+
\put(35.00,65.00){\makebox(0,0)[cc]{}}
+
 
+
\put(45.00,75.00){\makebox(0,0)[cc]{$x_3$}}
+
 
+
\put(75.00,75.00){\makebox(0,0)[cc]{$x_n$}}
+
 
+
\put(25.00,55.00){\makebox(0,0)[cc]{Program Counter}}
+
 
+
\put(15.00,55.00){\makebox(0,0)[cc]{}}
+
 
+
\put(15.00,55.00){\makebox(0,0)[cc]{}}
+
 
+
\put(0.00,60.00){\makebox(0,0)[cc]{}}
+
 
+
\linethickness{0.15mm}
+
%Polygon 0 0(30.00,80.00)(30.00,70.00)
+
\put(30.00,70.00){\line(0,1){10.00}}
+
%End Polygon
+
 
+
\put(25.00,75.00){\makebox(0,0)[cc]{$x_1$}}
+
 
+
\put(70.00,55.00){\makebox(0,0)[cc]{{\Large RAM--Program}}}
+
 
+
\put(15.00,15.00){\makebox(0,0)[cc]{$y_1$}}
+
 
+
\put(25.00,15.00){\makebox(0,0)[cc]{$y_2$}}
+
 
+
\put(35.00,15.00){\makebox(0,0)[cc]{$y_3$}}
+
 
+
\put(45.00,15.00){\makebox(0,0)[cc]{$y_4$}}
+
 
+
\put(55.00,15.00){\makebox(0,0)[cc]{$y_5$}}
+
 
+
\put(65.00,15.00){\makebox(0,0)[cc]{$y_6$}}
+
 
+
\put(75.00,15.00){\makebox(0,0)[cc]{$y_7$}}
+
 
+
\put(85.00,15.00){\makebox(0,0)[cc]{$y_8$}}
+
 
+
\put(60.00,80.00){\makebox(0,0)[bc]{входная read-only лента}}
+
 
+
\put(25.00,85.00){\makebox(0,0)[cc]{}}
+
 
+
\put(55.00,10.00){\makebox(0,0)[tc]{выходная write-only лента}}
+
 
+
\linethickness{0.15mm}
+
%Bezier 0 0(40.00,55.00)(43.44,54.38)(45.00,50.00)
+
\qbezier(40.00,55.00)(43.44,54.38)(45.00,50.00)
+
%End Bezier
+
 
+
\linethickness{0.15mm}
+
%Bezier 0 1(45.00,50.00)(46.56,45.63)(50.00,45.00)
+
\qbezier(45.00,50.00)(46.56,45.63)(50.00,45.00)
+
\put(50.00,45.00){\vector(4,-1){0.12}}
+
%End Bezier
+
 
+
\linethickness{0.15mm}
+
%Bezier 0 0(60.00,60.00)(58.44,66.25)(47.50,65.00)
+
\qbezier(60.00,60.00)(58.44,66.25)(47.50,65.00)
+
%End Bezier
+
 
+
\linethickness{0.15mm}
+
%Bezier 0 1(47.50,65.00)(36.56,63.75)(35.00,70.00)
+
\qbezier(47.50,65.00)(36.56,63.75)(35.00,70.00)
+
\put(35.00,70.00){\vector(-1,4){0.12}}
+
%End Bezier
+
 
+
\linethickness{0.15mm}
+
%Bezier 0 0(60.00,30.00)(60.47,24.69)(39.38,28.75)
+
\qbezier(60.00,30.00)(60.47,24.69)(39.38,28.75)
+
%End Bezier
+
 
+
\linethickness{0.15mm}
+
%Bezier 0 1(39.38,28.75)(18.28,32.81)(15.00,20.00)
+
\qbezier(39.38,28.75)(18.28,32.81)(15.00,20.00)
+
\put(15.00,20.00){\vector(-1,-4){0.12}}
+
%End Bezier
+
 
+
\put(110.00,45.00){\makebox(0,0)[cc]{}}
+
 
+
\put(105.00,85.00){\makebox(0,0)[cc]{}}
+
 
+
\linethickness{0.30mm}
+
%Rectangle(110.00,70.00)(120.00,80.00) 
+
\put(110.00,70.00){\line(1,0){10.00}}
+
\put(110.00,70.00){\line(0,1){10.00}}
+
\put(120.00,70.00){\line(0,1){10.00}}
+
\put(110.00,80.00){\line(1,0){10.00}}
+
%End Rectangle
+
 
+
\put(115.00,75.00){\makebox(0,0)[cc]{$r_0$}}
+
 
+
\linethickness{0.15mm}
+
%Rectangle(110.00,60.00)(120.00,70.00) 
+
\put(110.00,60.00){\line(1,0){10.00}}
+
\put(110.00,60.00){\line(0,1){10.00}}
+
\put(120.00,60.00){\line(0,1){10.00}}
+
\put(110.00,70.00){\line(1,0){10.00}}
+
%End Rectangle
+
 
+
\put(115.00,65.00){\makebox(0,0)[cc]{$r_1$}}
+
 
+
\linethickness{0.15mm}
+
%Rectangle(110.00,50.00)(120.00,60.00) 
+
\put(110.00,50.00){\line(1,0){10.00}}
+
\put(110.00,50.00){\line(0,1){10.00}}
+
\put(120.00,50.00){\line(0,1){10.00}}
+
\put(110.00,60.00){\line(1,0){10.00}}
+
%End Rectangle
+
 
+
\put(115.00,55.00){\makebox(0,0)[cc]{$r_2$}}
+
 
+
\linethickness{0.15mm}
+
%Rectangle(110.00,40.00)(120.00,50.00) 
+
\put(110.00,40.00){\line(1,0){10.00}}
+
\put(110.00,40.00){\line(0,1){10.00}}
+
\put(120.00,40.00){\line(0,1){10.00}}
+
\put(110.00,50.00){\line(1,0){10.00}}
+
%End Rectangle
+
 
+
\put(115.00,45.00){\makebox(0,0)[cc]{$r_3$}}
+
 
+
\linethickness{0.15mm}
+
%Rectangle(110.00,30.00)(120.00,40.00) 
+
\put(110.00,30.00){\line(1,0){10.00}}
+
\put(110.00,30.00){\line(0,1){10.00}}
+
\put(120.00,30.00){\line(0,1){10.00}}
+
\put(110.00,40.00){\line(1,0){10.00}}
+
%End Rectangle
+
 
+
\put(115.00,35.00){\makebox(0,0)[cc]{$r_4$}}
+
 
+
\linethickness{0.15mm}
+
%Rectangle(110.00,20.00)(120.00,30.00) 
+
\put(110.00,20.00){\line(1,0){10.00}}
+
\put(110.00,20.00){\line(0,1){10.00}}
+
\put(120.00,20.00){\line(0,1){10.00}}
+
\put(110.00,30.00){\line(1,0){10.00}}
+
%End Rectangle
+
 
+
\put(115.00,25.00){\makebox(0,0)[cc]{$r_5$}}
+
 
+
\linethickness{0.15mm}
+
%Polygon 0 0(110.00,20.00)(110.00,15.00)
+
\put(110.00,15.00){\line(0,1){5.00}}
+
%End Polygon
+
 
+
\linethickness{0.15mm}
+
%Polygon 0 0(120.00,20.00)(120.00,15.00)
+
\put(120.00,15.00){\line(0,1){5.00}}
+
%End Polygon
+
 
+
\linethickness{0.15mm}
+
%Bezier 0 0(110.00,15.00)(117.19,11.72)(118.75,13.13)
+
\qbezier(110.00,15.00)(117.19,11.72)(118.75,13.13)
+
%End Bezier
+
 
+
\linethickness{0.15mm}
+
%Bezier 0 0(118.75,13.13)(120.31,14.53)(120.00,15.00)
+
\qbezier(118.75,13.13)(120.31,14.53)(120.00,15.00)
+
%End Bezier
+
 
+
\linethickness{0.15mm}
+
%Bezier 0 0(90.00,45.00)(93.13,47.34)(96.25,61.88)
+
\qbezier(90.00,45.00)(93.13,47.34)(96.25,61.88)
+
%End Bezier
+
 
+
\linethickness{0.15mm}
+
%Bezier 0 1(96.25,61.88)(99.38,76.41)(110.00,75.00)
+
\qbezier(96.25,61.88)(99.38,76.41)(110.00,75.00)
+
\put(110.00,75.00){\vector(4,-1){0.12}}
+
%End Bezier
+
 
+
\put(51.25,51.25){\makebox(0,0)[cl]{{\tiny 0: LOAD $r1$}}}
+
 
+
\put(50.00,50.00){\makebox(0,0)[cc]{}}
+
 
+
\put(51.25,48.75){\makebox(0,0)[cl]{{\tiny 1: ADD 3}}}
+
 
+
\put(51.25,46.25){\makebox(0,0)[cl]{{\tiny 2: STORE $r7$}}}
+
 
+
\put(51.25,43.75){\makebox(0,0)[cl]{{\tiny 3: LOAD 77}}}
+
 
+
\put(51.25,41.25){\makebox(0,0)[cl]{{\tiny 4: STORE $*r7$}}}
+
 
+
\put(51.25,38.75){\makebox(0,0)[cl]{{\tiny 5: JUMP 100}}}
+
 
+
\put(60.00,36.25){\makebox(0,0)[cc]{$\ldots$}}
+
 
+
\linethickness{0.30mm}
+
%Rectangle(10.00,10.00)(20.00,20.00) 
+
\put(10.00,10.00){\line(1,0){10.00}}
+
\put(10.00,10.00){\line(0,1){10.00}}
+
\put(20.00,10.00){\line(0,1){10.00}}
+
\put(10.00,20.00){\line(1,0){10.00}}
+
%End Rectangle
+
 
+
\linethickness{0.30mm}
+
%Rectangle(30.00,70.00)(40.00,80.00) 
+
\put(30.00,70.00){\line(1,0){10.00}}
+
\put(30.00,70.00){\line(0,1){10.00}}
+
\put(40.00,70.00){\line(0,1){10.00}}
+
\put(30.00,80.00){\line(1,0){10.00}}
+
%End Rectangle
+
 
+
\end{picture}
+
 
+
</latex>
+
 
+
==Список команд==
+
 
+
<latex>
+
\begin{tabular}{|l|l|l|}
+
\hline
+
  \textbf{LOAD} OP & $r_0 \leftarrow OP$ & Загрузить операнд в сумматор \\
+
\hline
+
  \textbf{STORE} OP & $r_{OP} \leftarrow r_0$ & Сохранить сумматор в регистре\\
+
\hline
+
  \textbf{ADD} OP & $r_0 \leftarrow r_0 + OP$ & Прибавить операнд к сумматору\\
+
\hline
+
  \textbf{SUB} OP & $r_0 \leftarrow r_0 - OP$ & Вычесть операнд из сумматора\\
+
\hline
+
  \textbf{READ} OP & $r_{OP} \leftarrow input $  & Загрузить ячейку из входной ленты в $r_{OP}$ и перейти к следующей.\\
+
\hline
+
  \textbf{WRITE} OP & $OP \rightarrow output $  & Записать $OP$ в текущую ячейку выходной ленты и перейти к следующей.\\
+
\hline
+
  \textbf{JUMP} OP& $PC \leftarrow OP $  & Установить счетчик команд в $OP$.\\
+
\hline
+
  \textbf{JGTZ} OP& $PC \leftarrow OP :r_0>0  $  & Установить счетчик команд в $OP$, если $r_0>0$\\
+
\hline
+
  \textbf{JZERO} OP& $PC \leftarrow OP  :r_0=0 $  & Установить счетчик команд в $OP$, если $r_0=0$\\
+
\hline
+
  \textbf{HALT}& & Остановить работу.\\
+
\hline
+
\end{tabular}
+
</latex>
+
 
+
[[Category:Теория сложности]]
+
{{replicate-from-custiswiki-to-lib}}
+

Текущая версия на 20:32, 13 июня 2011

  1. REDIRECT discopal:Random Access Machine