Настоящая оперативная память - Real RAM

В вычислениях, особенно вычислительная геометрия, а реальная оперативная память (машина с произвольным доступом ) - математическая модель компьютера, способная производить вычисления с точными действительные числа вместо двоичного фиксированная точка или же плавающая точка числа, используемые большинством реальных компьютеров. реальная RAM была сформулирована Майкл Ян Шамос в его докторской степени 1978 г. диссертация.[1]

Модель

Часть "RAM" в названии реальной модели RAM означает "машина с произвольным доступом ". Это модель вычислений, которая напоминает упрощенную версию стандартной компьютерной архитектуры. Она состоит из сохраненная программа, а память компьютера блок, состоящий из массива ячеек, и центральное процессорное устройство с ограниченным числом регистры. Каждая ячейка памяти или регистр может хранить действительное число. Под управлением программы реальная RAM может передавать действительные числа между памятью и регистрами и выполнять арифметические операции со значениями, хранящимися в регистрах.

Разрешенные операции обычно включают сложение, вычитание, умножение и деление, а также сравнения, но не по модулю или округлению до целых чисел. Причина, по которой следует избегать операций с целочисленным округлением и модулем, заключается в том, что разрешение этих операций может дать реальной ОЗУ неоправданно большие вычислительные мощности, позволяя решать PSPACE-полный задачи за полиномиальное время.[2]

При анализе алгоритмов для реальной оперативной памяти предполагается, что каждая разрешенная операция требует постоянное время.

Выполнение

Программные библиотеки Такие как LEDA были разработаны, которые позволяют программистам писать компьютерные программы, которые работают так, как если бы они работали в реальной оперативной памяти. Эти библиотеки представляют реальные значения с использованием структуры данных которые позволяют им выполнять арифметические операции и сравнения с теми же результатами, что и в реальном ОЗУ. Например, в LEDA действительные числа представлены с помощью leda_real тип данных, который поддерживает корни k-й степени для любого натурального числа k, рациональные операторы и операторы сравнения.[3] Временной анализ базового алгоритма реального ОЗУ с использованием этих реальных типов данных можно интерпретировать как подсчет количества вызовов библиотеки, необходимых для данного алгоритма.[4]

Связанные модели

Настоящая оперативная память очень похожа на более позднюю Машина Блюма – Шуба – Смейла..[5] Однако реальная оперативная память обычно используется для анализа конкретных алгоритмов в вычислительная геометрия, а машина Блюма – Шуба – Смейла вместо этого составляет основу для расширений теории NP-полнота к вычислению действительных чисел.

Альтернативой реальной оперативной памяти является слово RAM, в котором предполагается, что как входные данные для задачи, так и значения, хранящиеся в памяти и регистрах, являются целыми числами с фиксированным числом битов. Модель слова RAM может выполнять некоторые операции быстрее, чем реальная RAM; например, позволяет быстро целочисленная сортировка алгоритмов, в то время как сортировка в реальной RAM должна выполняться с более медленными сравнительная сортировка алгоритмы. Однако некоторые задачи вычислительной геометрии имеют входные и выходные данные, которые нельзя точно представить с помощью целочисленных координат; см., например, Конфигурация Perles, расположение точек и отрезков линии, которое не имеет представления в целочисленных координатах.

Рекомендации

  1. ^ Шамос, Майкл Ян (1978), Вычислительная геометрия, Кандидат наук. диссертация, Йельский университет.
  2. ^ Шёнхаге, Арнольд (1979), «О мощности машин с произвольным доступом», Труды Шестого Международного коллоквиума по автоматам, языкам и программированию (ICALP '79), Конспект лекций по информатике, 71, Springer, стр. 520–529, Дои:10.1007/3-540-09510-1_42, ISBN  978-3-540-09510-1, МИСТЕР  0573259.
  3. ^ Мельхорн, Курт; Нэхер, Стефан (1999). Платформа комбинаторных и геометрических вычислений LEDA. Издательство Кембриджского университета. Получено 12 ноября 2019.
  4. ^ Мельхорн, Курт; Ширра, Стефан (2001), "Точный расчет с leda_real- теория и геометрические приложения » (PDF), Символьные алгебраические методы и методы проверки (Dagstuhl, 1999), Springer, стр. 163–172, Дои:10.1007/978-3-7091-6280-4_16, ISBN  978-3-211-83593-7, МИСТЕР  1832422.
  5. ^ Блюм, Ленора; Шуб, Майк; Смейл, Стив (1989), «К теории вычислений и сложности над действительными числами: NP-полнота, рекурсивные функции и универсальные машины», Бюллетень Американского математического общества, 21 (1): 1–46, Дои:10.1090 / S0273-0979-1989-15750-9, Zbl  0681.03020.

внешняя ссылка