Слово ОЗУ

В теоретической информатике модель слов RAM (словной машины с произвольным доступом) представляет собой модель вычислений , в которой машина с произвольным доступом выполняет арифметические и побитовые операции над словом из $w$ битов. Майкл Фредман и Дэн Уиллард создали его в 1990 году для моделирования таких языков программирования, C. как ^[1]

Модель

Модель словесной оперативной памяти представляет собой абстрактную машину, похожую на машину с произвольным доступом , но с конечной памятью и длиной слова. Он работает со словами размером до $w$ бит, то есть может хранить целые числа до $2^{w}-1$ . Поскольку модель предполагает, что размер слова соответствует размеру задачи, то есть для задачи размера $n$ , $w\geq \log n$ Модель слова RAM является трансдихотомической моделью . ^[2] Модель позволяет как арифметические операции, так и побитовые операции, включая логические сдвиги выполнять , за постоянное время (точный набор команд, предполагаемый алгоритмом или доказательством с использованием модели, может варьироваться).

Алгоритмы и структуры данных

В модели словесной оперативной памяти целочисленная сортировка может выполняться довольно эффективно. Йиджи Хан и Миккель Торуп создали рандомизированный алгоритм для сортировки целых чисел за ожидаемое время (в нотации Big O ) $O(n{\sqrt {\log \log n}})$ , ^[3] в то время как Хан также создал детерминированный вариант с временем выполнения $O(n\log \log n)$ . ^[4]

Проблема динамического предшественника также обычно анализируется в словесной модели RAM и была первоначальной мотивацией для этой модели. Дэн Уиллард использовал быстрые попытки решить эту проблему в $O(\log w)$ время, или, точнее, $O(\log \log U)$ где $U$ — граница хранимых значений. ^[5] Майкл Фредман и Уиллард также решили проблему, используя деревья слияния в $O(\log _{w}n)$ время. ^[1] Используя экспоненциальные деревья поиска , запрос можно выполнить в $O({\sqrt {\log n/\log \log n}})$ . ^[6]

Дополнительные результаты в словесной модели RAM приведены в статье о поиске по диапазону .

Нижние границы, применимые к алгоритмам словного ОЗУ, часто доказываются в модели ячейки-зонда .

См. также

Трансдихотомическая модель

Ссылки

^ Jump up to: ^а ^б Фредман, Майкл ; Уиллард, Дэн (1990). «Прорыв через теоретический барьер с помощью термоядерных деревьев». Симпозиум по теории вычислений : 1–7.
^ На самом деле обычно предполагается, $что n$ меньше, чем $2^{w}$ , так что рассматриваемая структура данных может быть проиндексирована $w$ -битными адресами.
^ Хан, Ицзе; Торуп, М. (2002), «Целочисленная сортировка в $ожидаемом времени O(n \sqrt log log n)$ и линейном пространстве», Труды 43-го ежегодного симпозиума по основам информатики (FOCS 2002) , Компьютерное общество IEEE, стр. 135 –144, CiteSeerX 10.1.1.671.5583 , doi : 10.1109/SFCS.2002.1181890 , ISBN 978-0-7695-1822-0
^ Хан, Ицзе (2004), «Детерминированная сортировка во $времени O (n log log n)$ и линейном пространстве», Journal of Algorithms , 50 (1): 96–105, doi : 10.1016/j.jalgor.2003.09.001 , MR 2028585
^ Уиллард, Дэн Э. (1983). «Лог-логарифмические запросы диапазона наихудшего случая возможны в пространстве Θ (N)». Письма об обработке информации . 17 (2): 81–84.
^ Андерссон, Арне; Торуп, Миккель (2007). «Динамические упорядоченные множества с экспоненциальными деревьями поиска». Журнал АКМ . 54 (3): 1–40. arXiv : cs/0210006 . дои : 10.1145/1236457.1236460 .

[Fredman90-1] Jump up to: ^а ^б Фредман, Майкл ; Уиллард, Дэн (1990). «Прорыв через теоретический барьер с помощью термоядерных деревьев». Симпозиум по теории вычислений : 1–7.

[2] На самом деле обычно предполагается, $что n$ меньше, чем $2^{w}$ , так что рассматриваемая структура данных может быть проиндексирована $w$ -битными адресами.

[Han02-3] Хан, Ицзе; Торуп, М. (2002), «Целочисленная сортировка в $ожидаемом времени O(n \sqrt log log n)$ и линейном пространстве», Труды 43-го ежегодного симпозиума по основам информатики (FOCS 2002) , Компьютерное общество IEEE, стр. 135 –144, CiteSeerX 10.1.1.671.5583 , doi : 10.1109/SFCS.2002.1181890 , ISBN 978-0-7695-1822-0

[Han04-4] Хан, Ицзе (2004), «Детерминированная сортировка во $времени O (n log log n)$ и линейном пространстве», Journal of Algorithms , 50 (1): 96–105, doi : 10.1016/j.jalgor.2003.09.001 , MR 2028585

[5] Уиллард, Дэн Э. (1983). «Лог-логарифмические запросы диапазона наихудшего случая возможны в пространстве Θ (N)». Письма об обработке информации . 17 (2): 81–84.

[6] Андерссон, Арне; Торуп, Миккель (2007). «Динамические упорядоченные множества с экспоненциальными деревьями поиска». Журнал АКМ . 54 (3): 1–40. arXiv : cs/0210006 . дои : 10.1145/1236457.1236460 .

[1]

[2]

[3]

[4]

[5]

[6]