PředmětyPředměty(verze: 953)
Předmět, akademický rok 2023/2024
   Přihlásit přes CAS
Proudové algoritmy pro velká data - NTIN114
Anglický název: Streaming algorithms for Big Data
Zajišťuje: Informatický ústav Univerzity Karlovy (32-IUUK)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2023 do 2023
Semestr: letní
E-Kredity: 3
Rozsah, examinace: letní s.:2/0, Zk [HT]
Počet míst: neomezen
Minimální obsazenost: neomezen
4EU+: ne
Virtuální mobilita / počet míst pro virtuální mobilitu: ne
Stav předmětu: vyučován
Jazyk výuky: čeština
Způsob výuky: prezenční
Způsob výuky: prezenční
Garant: Mgr. Pavel Veselý, Ph.D.
Třída: Informatika Mgr. - Teoretická informatika
Kategorizace předmětu: Informatika > Teoretická informatika
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.
Poslední úprava: Pangrác Ondřej, RNDr., Ph.D. (15.05.2023)
Literatura - angličtina
  • Graham Cormode, Ke Yi: Small summaries for Big Data, 2020.
  • Amit Chakrabarti: Lecture Notes on Data Stream Algorithms, 2020.
  • Jelani Nelson: Sketching Algorithms (lecture notes), 2020.

Poslední úprava: Pangrác Ondřej, RNDr., Ph.D. (15.05.2023)
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

Poslední úprava: Pangrác Ondřej, RNDr., Ph.D. (15.05.2023)
 
Univerzita Karlova | Informační systém UK