Seminár z teoretickej informatiky organizuje Katedra informatiky FMFI UK. Prezentuje sa na ňom predovšetkým vlastný výskum v oblasti informatiky, ale aj zásadné nové výsledky, ktoré by nemali uniknúť pozornosti informatickej komunity. Seminár sa koná počas semestra, vždy v piatok o 11:00 v miestnosti M213 v budove FMFI UK v Mlynskej doline a je otvorený pre každého.

najbližší seminár

28. 4. 2017, 11:00

Rasťo Královič

(KI FMFI UK)

   Hľadanie pokladu - randomizácia verzus komunikácia.

Budeme sa zaoberať jednoduchým vyhľadávacím problémom: máme nekonečnú postupnosť krabíc očíslovaných prirodzenými číslami. V jednej z nich, x, je ukrytý poklad. Poklad hľadá skupina k hľadačov, pričom nikto z nich nepozná x a každý z nich môže v každom kroku otvoriť jednu krabicu. Zaujíma nás, ako dlho (v závislosti od x) trvá, kým niektorý z hľadačov nájde poklad. Problém začne byť netriviálny, keď pripustíme, že niektorí hľadači môžu zlyhať. Fraigniaud, Korman a Rodeh našli efektívny randomizovaný algoritmus, ktorý nevyžaduje nijakú komunikáciu medzi hľadačmi (takže napr. nevedia zistiť, kto z nich zlyhal). V našom príspevku ukážeme, ako sa situácia zmení, keď randomizáciu vymeníme za veľmi slabú formu komunikácie: ak nejaký hľadač otvorí krabicu, táto už ostane otvorená a ďalší hľadači, ktorí by ju chceli otvoriť neskôr, túto skutočnosť zistia.

spoločná práca so Stefanom Dobrevom a Danou Pardubskou

pozvánka

5. 5. 2017, 11:00

Filip Mišún

(KI FMFI UK)

   Alternating Weighted Automata over Commutatiove Semirings

TBA

pozvánka