Datové struktury 2

Sylabus

Statické slovníky:

• perfektní hešování FKS

• deterministické slovníky (Hagerup, Miltersen, Pagh)

• redukce universa

Celočíselné datové struktury:

• van Emde-Boasovy stromy

• x-fast a y-fast stromy

• Fusion trees

Grafové datové struktury:

• dekompozice stromů na lehké a těžké hrany

• aktualizace cest pomocí líného vyhodnocování

• Link-Cut stromy (Sleator, Tarjan)

• inkrementální komponenty souvislosti (Union-Find)

Obecné techniky transformace struktur:

• semidynamizace a dynamizace

• persistence

Cache-oblivious struktury:

• Ordered File Maintenance

• B-stromy

Úsporné datové struktury:

• řetězce nad nebinární abecedou

• úsporná reprezentace stromů

Výpočty v proudovém modelu:

• deterministické hledání častých prvků

• randomizované hledání častých prvků

• odhad počtu různých prvků

Anotace

Přednáška navazuje na přednášku NTIN066 Datové struktury I. Bude věnována pokročilejším technikám návrhu a analýzy datových struktur: deterministická reprezentace statických množin, datové struktury pro celočíselné universum, základní grafové datové struktury, dynamické cache-oblivious vyhledávací stromy, dynamizace a persistence, úsporné datové struktury, výpočty v proudovém modelu.