6 października 2015 12:00
Seminarium ZZOiAA: Paweł Gawrychowski o kilku uogólnieniach klasycznego problemu range minimum query (RMQ).
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:
- indeksowanie, w którym podczas odpowiadania na zapytania mamy dostęp do oryginalnych danych,
- 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ę.