Seminár z teoretickej informatiky - Rastislav Královič (13.10.2017)

v piatok 13.10.2017 o 11:00 hod. v miestnosti M/213

11. 10. 2017 09.25 hod.
Od: Rastislav Královič

Prednášajúci: Rasťo Královič

Názov: Streaming algorithms: old results and new problems

Termín: 13.10.2017, 11:00 hod., M/213

Abstrakt:
V prednáške predstavíme model prúdových (streaming) algoritmov. Ako príklad uvedieme problém určenia počtu rôznych prvkov: na vstupe je postupnosť n prvkov, pričom každý z nich je z rozsahu 1 až m. Cieľom je zistiť počet rôznych prvkov pomocou algoritmu, ktorý číta vstup iba raz a má pamäť nezávislú od n. Uvedieme klasické výsledky pre deterministické a randomizované algoritmy a predstavíme niekoľko nových pozorovaní a otvorených problémov.

web: http://kedrigern.dcs.fmph.uniba.sk/STI2
rss: http://kedrigern.dcs.fmph.uniba.sk/STI2/rss.php