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

В теория сложности вычислений, а точнее в анализ алгоритмов с целое число данные, трансдихотомическая модель это вариант машина с произвольным доступом в котором машина размер слова предполагается, что он соответствует размеру проблемы. Модель была предложена Майкл Фредман и Дэн Уиллард,[1] который выбрал его название, «потому что дихотомия между моделью машины и размером проблемы разумно пересекается».[2]

В такой проблеме, как целочисленная сортировка в котором есть п целые числа для сортировки, трансдихотомическая модель предполагает, что каждое целое число может храниться в одном слове памяти компьютера, что операции с отдельными словами занимают постоянное время на операцию и что количество битов, которые могут быть сохранены в одном слове, составляет наименее бревно2п. Цель анализа сложности в этой модели - найти временные рамки, которые зависят только от п а не от фактического размера входных значений или машинных слов.[3][4] При моделировании целочисленных вычислений необходимо предположить, что машинные слова ограничены по размеру, поскольку модели с неограниченной точностью неоправданно мощны (способны решать PSPACE-полный задачи за полиномиальное время).[5] Трансдихотомическая модель делает минимальное допущение этого типа: что есть некоторый предел, и что предел достаточно велик, чтобы позволить произвольную индексацию входных данных.[3]

Помимо применения к целочисленной сортировке, трансдихотомическая модель также применялась к проектированию приоритетные очереди[6] и к проблемам в вычислительная геометрия[3] и графовые алгоритмы.[7]

Смотрите также

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

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