Komunikační složitost

• Název práce v češtině: Komunikační složitost
• Název v anglickém jazyce: Communication complexity
• Klíčová slova: komunikační složitost, deterministický model, pravděpodobnostní model, spodní odhady komunikační složitosti
• Klíčová slova anglicky: communication complexity, deterministic model, randomized model, lower bounds on communication complexity
• Akademický rok vypsání: 2011/2012
• Typ práce: bakalářská práce
• Jazyk práce: čeština
• Ústav: Katedra algebry (32-KA)
• Vedoucí / školitel: prof. RNDr. Jan Krajíček, DrSc.
• Řešitel: skrytý - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 06.10.2011
• Datum zadání: 18.10.2011
• Datum potvrzení stud. oddělením: 02.12.2011
• Datum a čas obhajoby: 22.06.2012 00:00
• Datum odevzdání elektronické podoby: 24.05.2012
• Datum odevzdání tištěné podoby: 24.05.2012
• Datum proběhlé obhajoby: 22.06.2012
• Oponenti: prof. Mgr. Michal Koucký, Ph.D.

Zásady pro vypracování

Komunikační složitost měří obtížnost booleovské funkce
minimálním počtem bitů, které si musejí strany - dvě či více
- sdělit aby vypočítali hodnotu funkce na vstupu, zná-li káždá
strana jen jeho část. Toto je jeden ze základních pojmů
teorie složitosti. Předmětem práce je shrnout některé ze
základních definic a známých faktů, a navrhnout vlastní
komunikační protokol pro několik jednoduchých funkcí.

Seznam odborné literatury

Kushilevitz, E. and N. Nisan. Communication complexity. Cambridge University Press, 1997.

Předběžná náplň práce

Nastudovat základní pojmy komunikační složitosti a navrhnout
pár komunikačních protokolu.

Předběžná náplň práce v anglickém jazyce

To learn a few basic concepts of communication complexity
and to propose a few communication protocols.