Поиск предков: различия между версиями

Перейти к навигации Перейти к поиску
(Новая страница: «== Ключевые слова и синонимы == Задача о поиске предков, задача о поиске потомков, просмотр…»)
 
Строка 3: Строка 3:


== Постановка задачи ==
== Постановка задачи ==
Рассмотрим упорядоченную совокупность U и множество T С U с jTj = n. Целью является предварительная обработка T таким образом, чтобы можно было эффективно отвечать на следующий запрос: пусть дано x 2 U, требуется вывести предка x, т. е. maxfy 2 T j y < xg. Также можно рассмотреть динамическую задачу, когда элементы вставляются в T и удаляются из него. Пусть tq – время запроса, а tu – время обновления.
Рассмотрим упорядоченную совокупность U и множество T <math> \subset</math> U, |T| = n. Целью является предварительная обработка T таким образом, чтобы можно было эффективно отвечать на следующий запрос: пусть задан элемент <math>x \in U</math>, требуется найти предка x, т. е. <math>max \{ y \in T | y < x \}</math>. Также можно рассмотреть динамическую задачу, когда элементы вставляются в T и удаляются из него. Обозначим за <math>t_q</math> время запроса, а за <math>t_u</math> – время обновления.




Строка 12: Строка 12:




Модель сравнения: задача может быть решена с помощью бинарного поиска за @(lg n) сравнений. Существует множество работ по адаптивным границам, которые могут быть сублогарифмическими. Такие границы могут зависеть от расстояния между пальцами, рабочего множества, энтропии и т. д.
'''Модель сравнения''': задача может быть решена с помощью бинарного поиска за <math>\Theta(lg \; n)</math> сравнений. Существует множество работ по адаптивным границам, которые могут быть сублогарифмическими. Такие границы могут зависеть от расстояния между пальцами, рабочего множества, энтропии и т. д.




Бинарные деревья поиска: поиск предков является одним из фундаментальных мотивов для бинарных деревьев поиска. В рамках этой ограничивающей модели можно рассчитывать на оптимальный (конкурентный) алгоритм. Попытки достичь этого описаны в работе по ссылке
'''Бинарные деревья поиска''': поиск предков является одним из фундаментальных мотивов для бинарных деревьев поиска. В рамках этой ограничивающей модели можно рассчитывать на оптимальный (конкурентный) алгоритм. Попытки достичь этого описаны в работе ''O(log log n)-конкурентные бинарные деревья поиска (2004; Demaine, Harmon, Iacono, P˘atra¸scu)''.


1O(loglogn)-конкурентные бинарные деревья поиска (2004; Demaine, Harmon, Iacono, Patrascu)


'''Пословная RAM-машина''': память организована в виде слов из b бит, доступ к которым может осуществляться через косвенную адресацию. В число операций со константным временем выполнения входят стандартные операции в таком языке, как C (сложение, умножение, сдвиг и битовые операции).


Пословная RAM-машина: память организована в виде слов из b бит, доступ к которым может осуществляться через косвенную адресацию. В число операций со константным временем выполнения входят стандартные операции в таком языке, как C (сложение, умножение, сдвиг и битовые операции).
Традиционно принято считать, что совокупность имеет вид <math>U = \{ 1, ..., 2^{\ell} \}</math>, т. е. мы имеем дело с <math>\ell</math>-битными целыми числами. Представление с плавающей точкой было разработано таким образом, что порядок сохраняется, когда значения интерпретируются как целые числа, поэтому любой алгоритм будет работать и для <math>\ell</math>-битных чисел с плавающей точкой.


Традиционно принято считать, что совокупность имеет вид U = f1...: ; 2 }, т. е. мы имеем дело с £-битными целыми числами. Представление с плавающей точкой было разработано таким образом, что порядок сохраняется, когда значения интерпретируются как целые числа, поэтому любой алгоритм будет работать и для £-разрядных чисел с плавающей точкой.
Стандартное трансдихотомическое предположение состоит в том, что <math>b = \ell</math>, так что входное целое число представляется в виде слова. Из этого следует <math>b \ge lg \; n</math>.


Стандартное трансдихотомическое предположение состоит в том, что b = I, так что входное целое число представляется в виде слова. Из этого следует b > lg n.


 
'''Модель клеточного зонда''': это неоднородная модель, более сильная, чем пословная RAM-машина, в которой операции являются произвольными функциями от слов памяти (ячеек), которые уже были прозондированы. Таким образом, <math>t_q</math> подсчитывает только количество зондирований ячеек. Это идеальная модель с точки зрения нижних границ, поскольку она не зависит от операций, реализуемых конкретным компьютером.
Модель клеточного зонда: это неоднородная модель, более сильная, чем пословная RAM-машина, в которой операции являются произвольными функциями от слов памяти (ячеек), которые уже были прозондированы. Таким образом, tq подсчитывает только количество зондирований ячеек. Это идеальная модель с точки зрения нижних границ, поскольку она не зависит от операций, реализуемых конкретным компьютером.




Коммуникативные игры: предположим, что у Алисы есть запрос x, а у Боба – множество T. Они пытаются найти предка x в результате т раундов коммуникации, где в каждом раунде Алиса посылает mA бит, а Боб отвечает с помощью raj бит.
Коммуникативные игры: предположим, что у Алисы есть запрос x, а у Боба – множество T. Они пытаются найти предка x в результате т раундов коммуникации, где в каждом раунде Алиса посылает mA бит, а Боб отвечает с помощью raj бит.


Этот подход может имитировать модель клеточного зонда, когда mB = b, а mA – логарифм объема памяти. Тогда т < tq и можно использовать коммуникационную сложность для получения нижних границ клеточного зонда.
Этот подход может имитировать модель клеточного зонда, когда mB = b, а mA – логарифм объема памяти. Тогда т < <math>t_q</math> и можно использовать коммуникационную сложность для получения нижних границ клеточного зонда.




Источник — http://pco.iis.nsk.su/wega/index.php/Поиск_предков