Počet záznamů: 1  

KAM-DIMATIA Series 2005-722 and ITI Series 2005-238

  1. 1.
    0027511 - MÚ 2006 RIV CZ eng V - Výzkumná zpráva
    Král´, D. - Tichý, Tomáš - Sgall, Jiří
    KAM-DIMATIA Series 2005-722 and ITI Series 2005-238.
    [Katedra aplikované matematiky-Diskrétní matematika a teoretická informatika Serie 2005-722 a Institut teoretické informatiky Serie 2005-238.]
    Praha: Charles University, 2005. 16 s.
    Grant CEP: GA ČR(CZ) GA201/05/0124; GA MŠk(CZ) 1M0545
    Výzkumný záměr: CEZ:AV0Z10190503
    Klíčová slova: concrete complexity * randomized algorithms
    Kód oboru RIV: BA - Obecná matematika

    We give asymptotically tight bounds both for randomized algorithms for the plurality problem in the case of two colors and many colors. For the balls colored by $k$ colors, we prove a lower bound $/Omega(kn)$ on the expected number of questions.

    Článek studuje pravděpodobnostní strategie pro problém plurality.
    Trvalý link: http://hdl.handle.net/11104/0117608
     
Počet záznamů: 1