Sylabus
- přibližné počítadlo s méně než log(n) bity
- počítání různých prvků a frekvenční momenty
- odhad kvantilů a distribučních funkcí
- hledání náhodných vzorků na základě frekvencí položek
- dolní odhady pomocí komunikační složitosti
- proudové algoritmy pro grafy: párování, počítání trojúhelníků, atd.
- geometrické proudové algoritmy: odhad průměru, clustering pomocí jádrových množin (coresets)
- redukce dimenze pomocí Johnsonovy-Lindenstraussovy transformace
- proudové algoritmy pro vektory a matice
- proudové algoritmy robustní vůči útokům
Anotace
Obsahem této přednášky budou tzv. proudové (streaming) algoritmy, které se používají k sekvenčnímu zpracování velkých dat s malou pamětí. Zaměříme se na základní problémy, např. počítání různých prvků, odhad kvantilů a náhodné vzorkování (sampling), probereme algoritmy pro grafové nebo geometrické proudy dat a také si ukážeme, jak lze dokazovat dolní odhady v tomto výpočetním modelu. Jelikož proudové algoritmy jsou
často pravděpodobnostní, předpokládají se znalosti na úrovni předmětu
NTIN022 Pravděpodobnostní techniky.