Коммуникационная сложность, 25 марта - 2 апреля. ПОМИшка
Простейшая модель в теории коммуникационной сложности такова. Имеются два участника (компьютера или человека), которые совместно хотят решить некоторую задачу. Ни один из них самостоятельно решить задачу не может (например, у каждого из них недостаточно данных или ресурсов). Поэтому им необходимо общаться. Коммуникационная сложность измеряет минимально возможное количество битов, которым необходимо обменяться участникам, чтобы решить задачу. Время, необходимое для проведения локальных вычислений каждым из участников, не принимается во внимание — в этом принципиальное отличие от теории сложности вычислений.
Николай Константинович Верещагин, МГУ, http://lpcs.math.msu.su/~ver/
http://compsciclub.ru/courses/communicationcomplexity/2017-spring/
Простейшая модель в теории коммуникационной сложности такова. Имеются два участника (компьютера или человека), которые совместно хотят решить некоторую задачу. Ни один из них самостоятельно решить задачу не может (например, у каждого из них недостаточно данных или ресурсов). Поэтому им необходимо общаться. Коммуникационная сложность измеряет минимально возможное количество битов, которым необходимо обменяться участникам, чтобы решить задачу. Время, необходимое для проведения локальных вычислений каждым из участников, не принимается во внимание — в этом принципиальное отличие от теории сложности вычислений.
Николай Константинович Верещагин, МГУ, http://lpcs.math.msu.su/~ver/
http://compsciclub.ru/courses/communicationcomplexity/2017-spring/
Communication complexity, March 25 - April 2. WELCOME
The simplest model in the theory of communication complexity is as follows. There are two participants (a computer or a person) who together want to solve a certain problem. None of them can solve the problem on their own (for example, each of them does not have enough data or resources). Therefore, they need to communicate. Communication complexity measures the minimum possible number of bits that participants need to exchange in order to solve a problem. The time required for performing local calculations by each of the participants is not taken into account - this is a fundamental difference from the theory of complexity of calculations.
Nikolai Konstantinovich Vereshchagin, Moscow State University, http://lpcs.math.msu.su/~ver/
http://compsciclub.ru/courses/communicationcomplexity/2017-spring/
The simplest model in the theory of communication complexity is as follows. There are two participants (a computer or a person) who together want to solve a certain problem. None of them can solve the problem on their own (for example, each of them does not have enough data or resources). Therefore, they need to communicate. Communication complexity measures the minimum possible number of bits that participants need to exchange in order to solve a problem. The time required for performing local calculations by each of the participants is not taken into account - this is a fundamental difference from the theory of complexity of calculations.
Nikolai Konstantinovich Vereshchagin, Moscow State University, http://lpcs.math.msu.su/~ver/
http://compsciclub.ru/courses/communicationcomplexity/2017-spring/
У записи 4 лайков,
0 репостов,
376 просмотров.
0 репостов,
376 просмотров.
Эту запись оставил(а) на своей стене Наима Джошуа
