Logowanie

Języki

  • Polski
  • English

Seminarium ZZOiA: 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:

  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ę.

Adres:
Instytut Informatyki
Uniwersytetu Wroclawskiego
ul. Joliot-Curie 15
50-383 Wroclaw
Sekretariat
tel.: 71 375 7800
tel.: 71 325 1271
fax: 71 375 7801
sekretariat@ii.uni.wroc.pl
Dziekanat
tel.: 71 375 7892
dziekan@ii.uni.wroc.pl
sprawy studenckie:
dziekanat@ii.uni.wroc.pl
Portiernia
tel.: 71 375 7958
Redaktor strony WWW
redaktor@ii.uni.wroc.pl
Projekt
MAKOS