Zaawansowane struktury danych

From Studia Informatyczne

Spis treści

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(mn log n), drzewa Eulera (ET trees) i dynamiczna spójność w czasie O(log^2 n), struktury danych przechowujące informacje o najkrótszych ścieżkach w grafie, PQ drzewa i testowanie planarności.

Literatura

Moduły

  1. Struktury danych dla liczb całkowitych I
  2. Struktury danych dla liczb całkowitych II
  3. Sortowanie liczb całkowitych