Original title: Komunikační složitost
Translated title: Communication complexity
Authors: Wagner, Vojtěch ; Krajíček, Jan (advisor) ; Koucký, Michal (referee)
Document type: Bachelor's theses
Year: 2012
Language: cze
Abstract: [cze] [eng]
Název práce: Komunikační složitost Autor: Vojtěch Wagner Katedra: Katedra algebry Vedoucí bakalářské práce: prof. RNDr. Jan Krajíček, DrSc. Abstrakt: Práce se zabývá teorií komunikační složitosti, která uvažuje model dvou (popř. více) hráčů, každý z nich vlastní binární vstup (x, resp. y), o němž má informaci pouze on sám. Jejich společným cílem je spočítat hodnotu něja- ké funkce f(x, y) na daných vstupech. Komunikační složitost pak měří množství informace vyměněné mezi hráči při jejich snaze spočítat f(x, y). Práce zkoumá především dva hlavní modely - deterministický model, v němž je rozhodování hráčů vždy jednoznačné a hráči spočítají vždy správnou hodnotu a pravděpo- dobnostní přístup, ve kterém je povolena náhodnost a snahou hráčů je spočítat hodnotu f(x, y) s dostatečně velkou pravděpodobností. Jsou uvedeny základní pojmy modelů a metody spodních odhadů pro dokazování komunikační složitosti funkcí. Vše je ilustrováno na příkladech několika základních funkcí. Další část je věnována příkladům náročnějším a v praxi použitelným, u nichž je řešena otázka jejich komunikačí složitosti jak deterministické, tak pravděpodobnostní. Klíčová slova: komunikační složitost, deterministický model, pravděpodobnost- ní model, spodní odhady komunikační složitosti. 1 Title: Communication Complexity Author: Vojtěch Wagner Department: Department of Algebra Supervisor: prof. RNDr. Jan Krajíček, DrSc. Abstract: This work deals with communication complexity, which considers mo- del of two (or more) parties, each holding its own binary input (let's say x and y). Each of players has information only about his own input. Their common goal is to compute value of some function f(x, y) of these inputs. Communicati- on complexity measures amount of information communicated between players in order to compute f(x, y). This work especially concerns two main models - deterministic, in which all decision made by players is deterministic and they compute the right value in all cases and probabilistic model which allows ran- domized fashion and the goal of the players is to compute the right value with high enough probability. We present some basic concepts and methods to lower bound communication complexity of functions, all ilustrated on some examples of basic functions. In the end we present some complex and practically relevant examples, on which presented methods are demonstrated. Keywords: communication complexity, deterministic communication model, ran- domized model, lower bounds on communication complexity. 1
Keywords: communication complexity; deterministic model; lower bounds on communication complexity; randomized model; deterministický model; komunikační složitost; pravděpodobnostní model; spodní odhady komunikační složitosti

Institution: Charles University Faculties (theses) (web)
Document availability information: Available in the Charles University Digital Repository.
Original record: http://hdl.handle.net/20.500.11956/40309

Permalink: http://www.nusl.cz/ntk/nusl-488124


The record appears in these collections:
Universities and colleges > Public universities > Charles University > Charles University Faculties (theses)
Academic theses (ETDs) > Bachelor's theses