Реальная оперативная память

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

Модель

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

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

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

Выполнение

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

Сравнение с другими вычислительными моделями

В модели машины Тьюринга базовая единица вычислений включает один бит. Следовательно, временная и пространственная сложность числовых алгоритмов зависит от количества битов, необходимых для представления чисел. Напротив, в модели Real RAM базовая единица вычислений включает в себя действительное число, независимо от того, сколько битов требуется для его представления. Это различие важно при анализе таких алгоритмов, как исключение Гаусса : этот алгоритм требует полиномиального числа арифметических операций над действительными числами, поэтому он является полиномиальным в модели Real RAM; однако числа, используемые в промежуточных вычислениях, могут (если реализованы наивно) расти экспоненциально, поэтому время их выполнения в модели машины Тьюринга является экспоненциальным. ^[5]^{: Раздел 1.4}
Настоящее ОЗУ очень напоминает более позднюю машину Блюма-Шаба-Смейла . ^[6] Однако реальная оперативная память обычно используется для анализа конкретных алгоритмов вычислительной геометрии , в то время как машина Блюма-Шаба-Смейла вместо этого формирует основу для расширения теории NP-полноты до вычислений с действительными числами.
Альтернативой реальному ОЗУ является слово RAM , в котором входные данные задачи и значения, хранящиеся в памяти и регистрах, считаются целыми числами с фиксированным количеством бит. Модель словесного ОЗУ может выполнять некоторые операции быстрее, чем реальная ОЗУ; например, он позволяет использовать быстрые алгоритмы сортировки целых чисел , тогда как сортировка в реальной оперативной памяти должна выполняться с помощью более медленных алгоритмов сортировки сравнения . Однако некоторые задачи вычислительной геометрии имеют входные или выходные данные, которые невозможно точно представить с использованием целочисленных координат; см., например, конфигурацию Perles , расположение точек и отрезков линий, не имеющее представления в целочисленных координатах.

Ссылки

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

Внешние ссылки

[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, doi : 10.1007/978-3-7091-6280-4_16 , ISBN 978-3-211-83593-7 , МР 1832422 .

[5] Гретшель, М.; Ловас, Л.; Шрийвер, А. (1 июня 1981 г.). «Метод эллипсоидов и его последствия в комбинаторной оптимизации» . Комбинаторика . 1 (2): 169–197. дои : 10.1007/BF02579273 . ISSN 1439-6912 . S2CID 43787103 .

[6] Блюм, Ленор ; Шуб, Майк ; Смейл, Стив (1989), «К теории вычислений и сложности над действительными числами: NP-полнота, рекурсивные функции и универсальные машины», Бюллетень Американского математического общества , 21 (1): 1–46, doi : 10.1090 /S0273-0979-1989-15750-9 , Збл 0681.03020 .

[1]

[2]

[3]

[4]

[5]

[6]