Na obowiązkowym wykładzie z Algorytmów i Struktur Danych zapoznajemy się głównie z klasycznymi strukturami danych, które w dość ograniczony sposób operują na danych wejściowych. Na przykład, do zaimplementowania słownika opartego na dowolnych drzewach przeszukiwań binarnych potrzebujemy być w stanie tylko porównywać dwa elementy. Ale czy na pewno dobrze modeluje to działanie prawdziwego komputera?
Głównym celem wykładu będzie przedstawienie słuchaczom szeregu wyników w tak zwanym modelu Word RAM, w którym pozwalamy na wykonywanie operacji takich jak dodawanie, odejmowanie, przesunięcia bitowe, mnożenie czy też dzielenie na elementach (liczbach) przechowywanych w strukturze. Dla wspomnianego powyżej przykładu pozwala to na skonstruowanie słownika przechowującego zbiór liczb z przedziału [1,n^2] tak, aby każda operacja działała w czasie O(loglogn).
Przez większość wykładu będziemy zajmować się problemem poprzednika (gdzie celem jest skonstruowanie struktury danych przechowującej zbiór liczb, dla której chcemy szybko znajdować najmniejszy element większy niż dana liczba) oraz deterministycznym słownikom (czyli strukturom danych, które przechowują zbiór liczb i pozwalają na szybkie sprawdzenie, czy dana liczba należy do tego zbioru).
