Menu

Oct. 6, 2015, noon

Na seminarium ZOiAA w dniu 11 czerwca 2015 (godz. 12:15) wystąpi Paweł Gawrychowski i opowie o kilku uogólnieniach klasycznego problemu RMQ.

Streszczenie:
Opowiem o kilku uogólnieniach klasycznego problemu range minimum query (RMQ), w którym chcemy wzbogacić daną tablicę A[1..n] o strukturę danych umożliwiającą szybkie znajdowanie minimum na danym przedziale. Naturalne jest rozważanie dwóch wersji problemów tego typu:

  1. indeksowanie, w którym podczas odpowiadania na zapytania mamy dostęp do oryginalnych danych,
  2. kodowanie, w którym odpowiadamy na zapytania tylko i wyłącznie na podstawie zbudowanej struktury.

Jak zwykle interesuje nas czas odpowiedzi i rozmiar struktury (w bitach). Dla klasycznego 1D RMQ wiadomo, że w tym pierwszym modelu istnieje struktura danych rozmiaru O(n/c), która pozwala odpowiadać na pytania w czasie O(c) (i wiadomo, że nie da się lepiej). Dla drugiej wersji problemu wiadomo, że każda struktura musi składać się z 2n bitów oraz istnieje struktura złożona z 2n+o(n) bitów, która pozwala odpowiadać na pytania w czasie stałym. Sytuacja robi się ciekawsza, gdy rozważymy tablicę dwuwymiarową lub gdy interesuje nas nie tylko znalezienie minimum, a k najmniejszych elementów. Można rozważać także uogólnienie, w którym zamiast minimum wyznaczamy dowolną półgrupę.