Zaawansowane struktury danych
Z Studia Informatyczne
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 . 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
Autor
- Łukasz Kowalik - Uniwersytet Warszawski
- Marcin Mucha - Uniwersytet Warszawski
Wymagania wstępne
brak
Zawartość
- Haszowanie. Haszowanie uniwersalne; haszowanie w przetrzeni liniowej i ze stałym czasem zapytań (algorytm Fredmana, Komlosa, Semerediego); haszowanie dynamiczne (Cuckoo Hashing); filtry Blooma.
- 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.
- 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).
- Kolejki priorytetowe. Kopce parujące (pairing heaps); kopce miękkie (soft heaphs); wzbogacanie kolejek priorytetowych o operację złączania.
- Problem najniższego wspólnego przodka (lowest common ancestor) i problem minimum z zakresu (range minimum query).
- Struktury danych dla dynamicznych algorytmów grafowych. Dynamiczne drzewa (link-cut trees) i algorytm przepływowy w czasie , drzewa Eulera (ET trees) i dynamiczna spójność w czasie , struktury danych przechowujące informacje o najkrótszych ścieżkach w grafie, PQ drzewa i testowanie planarności.
