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

-     CUSTIS
    
    
     
     
    
    
     
     
      Сайт CUSTIS →
     
    
    
     
     
    
    
     
     
      Вакансии
     
    
    
     
     
    
    
     
     
      Блог команды
     
    
    
     
     
    
    
     
     
      Архив событий
     
    
    
     
     
    
    
     
     
      Архив публикаций
     
    
    
     
     
    
  
     
     Навигация
    
    
     
     
    
    
     
     
      Заглавная страница
     
    
    
     
     
    
    
     
     
      Свежие правки
     
    
    
     
     
    
    
     
     
      Случайная статья
     
    
    
     
     
    
    
     
     
      Справка
     
    
    
     
     
    
  
     
     Поиск
    
    
     
     
    
    
     
     
    
        
         
    


    
    
     
     
    
  
     
     Инструменты
    
    
     
     
    
    
     
     
      Ссылки сюда
     
    
    
     
     
    
    
     
     
      Связанные правки
     
    
    
     
     
    
    
     
     
      Спецстраницы
     
    
    
     
     
    
    
     
     
      Версия для печати
     
    
    
     
     
    

Чистый HTML



→M$WORD



→OOffice
+    Random Access Machine — различия между версиями
   
      
    Материал из CustisWiki
    
            Перейти к: навигация, поиск
    
    

				
				
				
				
				
				Версия 19:47, 23 октября 2008 (просмотреть исходный код)
WikiSysop (обсуждение | вклад)
м (1 версия)
← Предыдущая правка
				Текущая версия на 20:32, 13 июня 2011 (просмотреть исходный код) 
StasFomin (обсуждение | вклад) 
м (Содержимое страницы заменено на «#REDIRECT [[discopal:{{PAGENAME}}]]»)
 
				
Строка 1:
Строка 1:
− ==Определение== + #REDIRECT [[discopal:{{PAGENAME}}]]
− '''Random Access Machine''' («машины со произвольным доступом») — теоретическая модель вычислителя (см. например [[машина Тьюринга]]), + 
− напоминающая современный компьютер, программируемый непосредственно в терминах инструкций процессора (или на языке Assembler) (в теории сложности вычислений под ''машинами'' традиционно понимают ''single-purpose machines''), т. е. машины, созданные для решения какой-либо одной фиксированной задачи, а в терминах программиста это скорее программы). + 
−   + 
− RAM-машина состоит из (См. Рисунок): + 
− * Конечная входная read-only лента, куда записываются входные данные. + 
− * Полубесконечная выходная write-only лента, куда записываются результат работы машины. + 
− * Бесконечное число регистров <m>r_0,r_1,r_2,\ldots,</m>, каждый из которых может хранить целое число, причем регистр <m>r_0</m> является выделенным, и называется «сумматором» — этот регистр используется при арифметических операциях как накопитель, т. е. как второй операнд и место хранения результата. + 
− * Программа, состоящая из конечного числа инструкций, каждая из которых содержит адрес и команду с операндом. Таблица со списком команд приведена ниже. + 
− Важный, характеристический момент — в качестве операнда можно использовать как произвольный регистр, так и регистр, номер которого храниться в другом регистре — так называемая косвенная адресация. + 
− * Регистр-счетчик «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
REDIRECT discopal:Random Access Machine







Источник — «http://lib.custis.ru/index.php?title=Random_Access_Machine&oldid=27249»
 CUSTIS
       Сайт CUSTIS →
       Вакансии
       Блог команды
       Архив событий
       Архив публикаций
 Навигация
       Заглавная страница
       Свежие правки
       Случайная статья
       Справка
 Поиск
 Инструменты
       Ссылки сюда
       Связанные правки
       Спецстраницы
       Версия для печати
 Чистый HTML
 →M$WORD
 →OOffice
@@ Строка 1: / Строка 1: @@
-==Определение==
+#REDIRECT [[discopal:{{PAGENAME}}]]
-'''Random Access Machine''' («машины со произвольным доступом») — теоретическая модель вычислителя (см. например [[машина Тьюринга]]),
-напоминающая современный компьютер, программируемый непосредственно в терминах инструкций процессора (или на языке Assembler) (в теории сложности вычислений под ''машинами'' традиционно понимают ''single-purpose machines''), т. е. машины, созданные для решения какой-либо одной фиксированной задачи, а в терминах программиста это скорее программы).
-RAM-машина состоит из (См. Рисунок):
-* Конечная входная read-only лента, куда записываются входные данные.
-* Полубесконечная выходная write-only лента, куда записываются результат работы машины.
-* Бесконечное число регистров <m>r_0,r_1,r_2,\ldots,</m>, каждый из которых может хранить целое число, причем регистр <m>r_0</m> является выделенным, и называется «сумматором» — этот регистр используется при арифметических операциях как накопитель, т. е. как второй операнд и место хранения результата.
-* Программа, состоящая из конечного числа инструкций, каждая из которых содержит адрес и команду с операндом. Таблица со списком команд приведена ниже.
-Важный, характеристический момент — в качестве операнда можно использовать как произвольный регистр, так и регистр, номер которого храниться в другом регистре — так называемая косвенная адресация.
-* Регистр-счетчик «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}}

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

Просмотры

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

Материал из CustisWiki

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