1294
правки
Равнодоступная адресная машина: различия между версиями
Перейти к навигации
Перейти к поиску
нет описания правки
KVN (обсуждение | вклад) Нет описания правки |
KVN (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Равнодоступная адресная машина''' ([[Random access machine|''Random access machine, RAM'']]) - универсальная математическая модель вычислений, которая является хорошим приближением к классу обычных, традиционных вычислительных машин с точки зрения отражения затрат времени и памяти при представлении данных и алгоритмов, целиком помещающихся в оперативной памяти. | '''Равнодоступная адресная машина''' ([[Random access machine|''Random access machine, RAM'']]) - универсальная математическая модель вычислений, которая является хорошим приближением к классу обычных, традиционных вычислительных машин с точки зрения отражения затрат времени и памяти при представлении данных и алгоритмов, целиком помещающихся в оперативной памяти. | ||
''' | '''Равнодоступная адресная машина''' моделирует вычислительную машину с одним сумматором, в которой команды программы не могут изменять сами себя. | ||
''' | |||
'''Равнодоступная адресная машина''' состоит из входной ленты, с которой она может только считывать, выходной ленты, на которую она может только записывать, и памяти. | |||
Входная лента --- это последовательность клеток, содержащих записи целых чисел и доступных для считывания по одной в соответствии с их упорядоченностью. Она состоит из неограниченной последовательности клеток, которые вначале все пусты; при выполнении команды записи происходит печать целого числа в первой свободной клетке выходной ленты. | Входная лента --- это последовательность клеток, содержащих записи целых чисел и доступных для считывания по одной в соответствии с их упорядоченностью. Она состоит из неограниченной последовательности клеток, которые вначале все пусты; при выполнении команды записи происходит печать целого числа в первой свободной клетке выходной ленты. | ||
| Строка 20: | Строка 21: | ||
Состояние вычисления (конфигурация) --- это четверка <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>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,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> | Другие названия --- [[Машина с произвольным доступом к памяти]], [[РАМ]]. | ||
[[Файл:РАМ.jpg]] | [[Файл:РАМ.jpg]] | ||