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

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

25. 04. 2017 14.30 hod.
Od: Rastislav Královič

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

Názov: Hľadanie pokladu - randomizácia verzus komunikácia

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

Abstrakt:
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 khľadačov, pričom nikto z nich nepozná x a každý z nich môže vkaždom kroku otvoriť jednu krabicu. Zaujíma nás, ako dlho (vzávislosti od x) trvá, kým niektorý zhľ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). Vnaš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

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