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

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

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

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

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

использованная литература

^ Фредман, Майкл Л .; Willard, Dan E. (1993), "Превосходя информационно-Теоретико связаны с слитых деревьев", журнал компьютерных и системных наук , 47 (3): 424-436, DOI : 10.1016 / 0022-0000 (93) 90040-4 , Руководство по ремонту 1248864.
↑ Бенуа, Дэвид; Демейн, Эрик Д .; Манро, Дж. Ян; Раман, Венкатеш, "Представление деревьев более высокой степени", Алгоритмы и структуры данных: 6-й международный семинар, WADS'99 , с. 170.
^ ^a ^b ^c Чан, Тимоти М .; Pǎtraşcu Михай (2009), "Transdichotomous Результаты в вычислительной геометрии, I: Точка Место в Sublogarithmic времени" (PDF) , SIAM журнал по вычислениям , 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.
^ Раман, Раджив, «Приоритетные очереди: маленькие, монотонные и транс-дихотомические», Труды четвертого ежегодного европейского симпозиума по алгоритмам (ESA '96) , конспекты лекций по компьютерным наукам, 1136 , Springer-Verlag, стр. 121–137 , DOI : 10.1007 / 3-540-61680-2_51.
^ Фредман, Майкл Л .; Willard, Dan E. (1994), "Транс-дихотомические алгоритмы минимальных остовных деревьев и кратчайшие пути", журнал компьютерных и системных наук , 48 (3): 533-551, DOI : 10.1016 / S0022-0000 (05) 80064 -9.

P ≟ NP

Эта статья по теоретической информатике незавершена . Вы можете помочь Википедии, расширив ее .

[1] Фредман, Майкл Л .; Willard, Dan E. (1993), "Превосходя информационно-Теоретико связаны с слитых деревьев", журнал компьютерных и системных наук , 47 (3): 424-436, DOI : 10.1016 / 0022-0000 (93) 90040-4 , Руководство по ремонту 1248864.

[2] Бенуа, Дэвид; Демейн, Эрик Д .; Манро, Дж. Ян; Раман, Венкатеш, "Представление деревьев более высокой степени", Алгоритмы и структуры данных: 6-й международный семинар, WADS'99 , с. 170.

[cp1-3] Чан, Тимоти М .; Pǎtraşcu Михай (2009), "Transdichotomous Результаты в вычислительной геометрии, I: Точка Место в Sublogarithmic времени" (PDF) , SIAM журнал по вычислениям , 39 (2): 703-729, DOI : 10,1137 / 07068669X .

[4] Чан, Тимоти М .; Путраску, Михай (2010), Трансдихотомические результаты в вычислительной геометрии, II: автономный поиск , arXiv : 1010.1948 , Bibcode : 2010arXiv1010.1948C.

[5] Бертони, Альберто; Маури, Джанкарло; Сабадини, Николетта (1981), «Характеристика класса функций, вычислимых за полиномиальное время на машинах с произвольным доступом», Труды тринадцатого ежегодного симпозиума ACM по теории вычислений (STOC '81) , стр. 168–176, doi : 10.1145 / 800076.802470.

[6] Раман, Раджив, «Приоритетные очереди: маленькие, монотонные и транс-дихотомические», Труды четвертого ежегодного европейского симпозиума по алгоритмам (ESA '96) , конспекты лекций по компьютерным наукам, 1136 , Springer-Verlag, стр. 121–137 , DOI : 10.1007 / 3-540-61680-2_51.

[7] Фредман, Майкл Л .; Willard, Dan E. (1994), "Транс-дихотомические алгоритмы минимальных остовных деревьев и кратчайшие пути", журнал компьютерных и системных наук , 48 (3): 533-551, DOI : 10.1016 / S0022-0000 (05) 80064 -9.

[1]