683
правки
KEV (обсуждение | вклад) Нет описания правки |
KVN (обсуждение | вклад) Нет описания правки |
||
(не показана 1 промежуточная версия 1 участника) | |||
Строка 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> | ||
Другие названия — [[Машина с произвольным доступом к памяти]], [[РАМ]]. | Другие названия — [[Машина с произвольным доступом к памяти]], [[РАМ]]. | ||
Строка 36: | Строка 36: | ||
==См. также== | ==См. также== | ||
[[Сложность РАМ | * ''[[Сложность РАМ]]''. | ||
==Литература== | ==Литература== |