Трансдихотомическая модель
В теории сложности вычислений и, более конкретно, в анализе алгоритмов с целочисленными данными, трансдихотомическая модель представляет собой вариант машины с произвольным доступом размер машинного слова , в которой предполагается, что соответствует размеру задачи. Модель была предложена Майклом Фредманом и Дэном Уиллардом . [1] который выбрал это название, «потому что дихотомия между моделью машины и размером проблемы разумным образом пересекается». [2]
В такой задаче, как сортировка целых чисел , в которой необходимо отсортировать n целых чисел, трансдихотомическая модель предполагает, что каждое целое число может храниться в одном слове компьютерной памяти, что операции над отдельными словами занимают постоянное время на каждую операцию и что число количество битов, которые могут быть сохранены в одном слове, составляет не менее log 2 n . Целью анализа сложности в этой модели является нахождение временных границ, которые зависят только от n , а не от фактического размера входных значений или машинных слов. [3] [4] При моделировании целочисленных вычислений необходимо предполагать, что машинные слова ограничены в размере, поскольку модели с неограниченной точностью являются неоправданно мощными (способными решать PSPACE-полные задачи за полиномиальное время). [5] Трансдихотомическая модель делает минимальное предположение такого типа: существует некоторый предел, и что этот предел достаточно велик, чтобы обеспечить индексацию входных данных с произвольным доступом. [3]
Трансдихотомическая модель применяется не только для сортировки целых чисел, но и для проектирования приоритетных очередей. [6] и к задачам вычислительной геометрии [3] и графовые алгоритмы . [7]
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Фредман, Майкл Л .; Уиллард, Дэн Э. (1993), «Преодоление теоретико-информационной связи с объединенными деревьями», Journal of Computer and System Sciences , 47 (3): 424–436, doi : 10.1016/0022-0000(93)90040-4 , МР 1248864 .
- ^ Бенуа, Дэвид; Демейн, Эрик Д .; Манро, Дж. Ян; Раман, Венкатеш, «Представление деревьев высшей степени», Алгоритмы и структуры данных: 6-й международный семинар, WADS'99 , с. 170 .
- ^ Jump up to: Перейти обратно: а б с Чан, Тимоти М .; Путрашку, Михай (2009), «Трансдихотомические результаты в вычислительной геометрии, I: расположение точки в сублогарифмическом времени» (PDF) , SIAM Journal on Computing , 39 (2): 703–729, doi : 10.1137/07068669X .
- ^ Чан, Тимоти М .; Путрашку, Михай (2010), Трансдихотомические результаты в вычислительной геометрии, II: Автономный поиск , arXiv : 1010.1948 , Bibcode : 2010arXiv1010.1948C .
- ^ Бертони, Альберто; Маури, Джанкарло; Сабадини, Николетта (1981), «Характеристика класса функций, вычислимых за полиномиальное время на машинах произвольного доступа», Труды тринадцатого ежегодного симпозиума ACM по теории вычислений (STOC '81) , стр. 168–176, doi : 10.1145/800076.802470 , S2CID 12878381 .
- ^ Раман, Раджив, «Очереди с приоритетами: небольшие, монотонные и трансдихотомические», Труды четвертого ежегодного европейского симпозиума по алгоритмам (ESA '96) , Конспекты лекций по информатике, том. 1136, Springer-Verlag, стр. 121–137, doi : 10.1007/3-540-61680-2_51 .
- ^ Фредман, Майкл Л .; Уиллард, Дэн Э. (1994), «Трансдихотомические алгоритмы для минимальных остовных деревьев и кратчайших путей», Журнал компьютерных и системных наук , 48 (3): 533–551, doi : 10.1016/S0022-0000(05)80064 -9 .