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 struktury słownikowej opartej na dowolnych drzewach przeszukiwań binarnych potrzebujemy być w stanie tylko porównywać dwa elementy. Plusem takiego założenia jest to, że w często nietrudny sposób można udowodnić, że skonstruowana struktura jest optymalna. Należy się jednak zastanowić, czy ograniczenie się do porównywania elementów jest rozsądne.
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). Co ciekawe, pokażemy że nie da się lepiej!
