683
правки
Равнодоступная адресная машина: различия между версиями
Материал из WikiGrapp
Равнодоступная адресная машина (посмотреть исходный код)
Версия от 16:15, 5 декабря 2012
, 5 декабря 2012нет описания правки
KEV (обсуждение | вклад) Нет описания правки |
KVN (обсуждение | вклад) Нет описания правки |
||
| Строка 27: | Строка 27: | ||
Как при равномерном, так и при логарифмическом весах команд для любой '''равнодоступной адресной машины''' (соответственно ''РАСП'') с временной сложностью <math>\,T(n)</math> существует такая постоянная <math>\,k</math>, что найдется эквивалентная ''РАСП'' (соответственно ''РАМ'' ), временная сложность которой не превосходит <math> \,kT(n)</math>. | Как при равномерном, так и при логарифмическом весах команд для любой '''равнодоступной адресной машины''' (соответственно ''РАСП'') с временной сложностью <math>\,T(n)</math> существует такая постоянная <math>\,k</math>, что найдется эквивалентная ''РАСП'' (соответственно ''РАМ'' ), временная сложность которой не превосходит <math> \,kT(n)</math>. | ||
[[Недетерминированная равнодоступная адресная машина]] (или [[НРАМ]]) получается из '''равнодоступной адресной машины''' добавлением команды ВЫБОР<math> (L_1,L_2,\ldots, L_r)</math>, означающей, что недетерминированы выбор и последующее выполнение | [[Недетерминированная равнодоступная адресная машина]] (или [[НРАМ]]) получается из '''равнодоступной адресной машины''' добавлением команды ВЫБОР<math> (L_1,L_2,\ldots, L_r)</math>, означающей, что недетерминированы выбор и последующее выполнение одной из команд с номерами <math>L_1,L_2,\ldots,L_r.</math> | ||
Другие названия — [[Машина с произвольным доступом к памяти]], [[РАМ]]. | Другие названия — [[Машина с произвольным доступом к памяти]], [[РАМ]]. | ||
