Zaawansowane struktury danych/Struktury danych dla liczb całkowitych I

Modele obliczeń

Kilka kolejnych wykładów poświęcimy strukturom danych które umożliwiają wykonanywanie różnego rodzaju operacji na zbiorach liczb całkowitych.

Okazuje się, że jeśli ograniczymy się do przypadku liczb całkowitych (a nie, na przykład, elementów dowolnego liniowego porządku), to tradycyjnie używane modele, take jak RAM, czy drzewa decyzyjne, nie mają zbyt wiele sensu.

Przypomnijmy, że w modelu drzew decyzyjnych, algorytm jest drzewem porównań (można też rozpatrywać bogatsze modele, które umożliwiają wykonywanie operacji arytmetycznych na elementach danych wejściowych, tzw. algebraiczne drzewa decyzyjne). Z jednej strony ten model jest bardzo silny, ponieważ ignorujemy strukturalny aspekt algorytmu, w Szczególności program może mieć wykładniczy rozmiar (!!). Z drugiej strony w modelu tym brakuje dostępu do lokacji w pamięci adresowanej przez zmienną (kluczowe w hashowaniu). Co więcej, gdybyśmy chcieli uwzględnić w tym modelu operacje możliwe tylko w dziedzinie liczb całkowitych, np. przesunięcia bitowe, tracimy najważniejszą zaletę tego modelu, tzn. względną łatwość uzyskiwania dolnych granic.

Model RAM jest jakby przeciwieństwem modelu drzew decyzyjnych. Bardzo dobrze oddaje on strukturalny aspekt algorytmów, dostępne w nim są wszystkie naturalne operacje, także te możliwe tylko w dziedzinie liczb całkowitych. Ceną, jaką za to płacimy jest oczywiście ogromna komplikacja modelu, a w konsekwencji problemy z dowodzeniem dolnych granic. Nawet model RAM nie opisuje jednak realistycznych obliczeń idealnie. Podstawowym zarzutem jaki można mu postawić jest jednostkowy czas wykonywania operacji arytmetycznych na argumentach dowolnych (!!) rozmiarów.

Przykład/Ćwiczenie 1:

Pokaż, że w modelu RAM można posortować n liczb całkowitych w czasie O(n).

Wskazówka

Używając operacji przesunięcia bitowego, spróbuj zakodować wszystkie liczby w jednej wielkiej liczby, a następnie obliczyć rangi wszystkich elementów wejściowych.

Ten przykład pokazuje, że jeśli interesują nas liczby całkowite, musimy w jakiś sposób ograniczyć rozmiar argumentów, przy którym operacje arytmetyczne wykonują się w czasie jednostkowym. Problem ten z reguły rozwiązuje się następująco. Zakładamy, że nasz "komputer" może wykonywać operacje arytmetyczne w czasie stałym tylko na liczbach w-bitowych, dla pewnego ustalonego w, które będziemy nazywali długością słowa. Arytmetykę większych liczb musimy sobie sami zaimplementować, co oznacza, że jest ona odpowiednio droższa. Ten model nazywamy w-bitowym WordRAM. Zwróćmy uwagę, że zdefiniowaliśmy tu całą rodzinę modeli, sparametryzowaną przez w. Rozwiązując w modelu WordRAM konkretny problem, złożoność naszego algorytmu będziemy uzależniać zarówno od rozmiaru danych n jak i długości słowa w. Zakładamy przy tym, że w >= log n, co ma sens, bo musimy przecież jakoś adresować dane.

Uwaga Wiekszość znanych algorytmów, na przykład grafowych, ma w tym modelu złożoność taką samą jak w modelu RAM, niezależnie od parametru w. Perwersyjny algorytm z Ćwiczenia 1 jest tu wyjątkiem.

Niekiedy rozpatruje się także nieco bardziej ograniczone modele. W szczególności, bardzo naturalnym modelem jest tzw. AC₀RAM. Model ten jest identyczny z WordRAM z jednym wyjątkiem, w czasie jednostkowym wykonują się w nim jedynie operacje typu AC₀, tzn. takie, które można zrealizować przy pomocy obwodów logicznych stałej głębokości i wielomianowego (względem w) rozmiaru (bramki mogą mieć dowolnie duży stopień wejściowy). Pozostałe, tzn. przede wszystkim mnożenie, musimy zrealizować sami. Dlaczego nakładamy takie ograniczenie? W jakimś sensie jest ono podyktowane przez rzeczywiste ograniczenia architektury komputerów. Rozmiar obwodów realizujących operacje typu AC₀ jest stały, niezależny od w. Tylko dla takich operacji ma sens założenie, że wykonują się one w czasie jednostkowym. Gdybyśmy budowali komputer 1.000.000-bitowy, to dodawanie liczb nie byłoby na nim czasowo dużo kosztowniejszy niż na komputerze 64-bitowym, ale już mnożenie tak.

Problem poprzednika

W problemie poprzednika (ew. następnika), chcemy realizować następujące operacje na zbiorze liczb całkowitych S:

1. INSERT(x) -- dodaje x do S,
2. DELETE(x) -- usuwa x z S,
3. FIND(x) -- sprawdza, czy x należy do S,
4. PREDECESSOR(x)/PRED(x) -- zwraca poprzednik x w S,
5. SUCCESOR(x)/SUCC(x) -- zwraca następnik x w S.

Uwaga: W operacjach PRED i SUCC argument x nie musi być elementem zbioru S.

Można powiedzieć, że problem poprzednika to uporządkowana wersja problemu słownika. Zwróćmy uwagę, że "wolne" zrównoważone drzewa BST pozwalają na wykonywanie operacji PRED w czasie O(log n), ale już "szybkie" tablice hashujące potrzebują czasu O(n).

My będziemy zajmować się problemem poprzednika w modelu WordRAM/AC₀RAM, a zatem założymy, że nasze elementy są liczbami w-bitowymi, tzn. liczbami z przedziału U=[0,...,2^w-1]. Jeśli zakładamy, że elementy S pochodzą ze skończonego uniwersum, tak jak w naszym przypadku, to mamy do czynienia z problemem poprzednika dla skończonego uniwersum (ang. FUP = finite universe predecessor). Jak zwykle, możemy też rozważać statyczną wersję problemu, w której nie realizujemy operacji modyfikujących S, tzn. INSERT i DELETE.