Zaawansowane struktury danych

Forma zajęć

Wykład (30 godzin) + ćwiczenia (30 godzin)

Opis

Celem jest przedstawienie aktualnego stanu wiedzy na temat wybranych zagadnień z zakresu struktur danych.

Przedstawimy zarówno struktury danych używane w praktyce (dynamiczne haszowanie, drzewa typu splay, kopce parujące) jak i struktury danych o szokujących implikacjach teoretycznych (jak np. sortowanie liczb całkowitych w czasie $O(n*loglogn))$. W każdym przypadku będzie nas interesowała analiza złożoności czasowej omawianych struktur -- w sensie czasu pesymistycznego, zamortyzowanego lub oczekiwanego.

Sylabus

Autorzy

• Łukasz Kowalik - Uniwersytet Warszawski
• Marcin Mucha - Uniwersytet Warszawski

Wymagania wstępne

brak

Zawartość

1. Haszowanie. Haszowanie uniwersalne; haszowanie w przetrzeni liniowej i ze stałym czasem zapytań (algorytm Fredmana, Komlosa, Semerediego); haszowanie dynamiczne (Cuckoo Hashing); filtry Blooma.
2. Sortowanie i wyszukiwanie liczb całkowitych (z ograniczonego uniwersum). Drzewa van Emde Boas'a, X-szybkie drzewa trie, Y-szybkie drzewa trie, fusion trees; szybkie sortowanie liczb całkowitych; twierdzenie o równoważności problemów sortowania i kolejki priorytetowej; dolne ograniczenia.
3. Drzewa typu splay. Podstawowe własności; twierdzenie o dostępie sekwencyjnym; hipoteza o kolejce dwustronnej i jej częściowe rozwiązanie; hipoteza o dynamicznej optymalności drzew typu splay i jej częściowe rozwiązania (drzewa Tango).
4. Kolejki priorytetowe. Kopce parujące (pairing heaps); kopce miękkie (soft heaphs); wzbogacanie kolejek priorytetowych o operację złączania.
5. Problem najniższego wspólnego przodka (lowest common ancestor) i problem minimum z zakresu (range minimum query).
6. Struktury danych dla dynamicznych algorytmów grafowych. Dynamiczne drzewa (link-cut trees) i algorytm przepływowy w czasie $O(mnlogn)$, drzewa Eulera (ET trees) i dynamiczna spójność w czasie $O(lo{g}^{2}n)$, struktury danych przechowujące informacje o najkrótszych ścieżkach w grafie, PQ drzewa i testowanie planarności.

Literatura

• Notatki do wykladow E. Demaine'a

Moduły

1. Struktury danych dla liczb całkowitych I