Logowanie

Języki

  • Polski
  • English

Seminarium ZZOiA: Gianluca de Marco o "Determining the majority by color comparisons"  

Na seminarium ZOiAA w dniu 8 października 2015 (godz. 12:15, sala 119) wystąpi Gianluca de Marco z Uniwersytetu w Salerno. Tytuł jego wystąpienia: Determining the majority by color comparisons.

Streszczenie
We are given n balls, each of them colored with one of two possible colors. Suppose that at each step we can choose two balls and ask an oracle whether they are of the same color or not. The oracle (without revealing the colors of the balls) is allowed to answer either 'yes' or 'no'. The process ends when, based on the sequence of queries and answers, the questioner is able to produce a ball a of the majority color (meaning that the number of balls colored like a exceeds those of the other color), or when it is possible to claim that there is no majority (in case of a tie between the two colors). The goal is to
minimize the number of questions that allow to end the process.

We will survey on results and open problems on this classical combinatorial problem and some interesting variants and generalizations, providing also some of the main arguments used.

Adres:
Instytut Informatyki
Uniwersytetu Wroclawskiego
ul. Joliot-Curie 15
50-383 Wroclaw
Sekretariat
tel.: 71 375 7800
tel.: 71 325 1271
fax: 71 375 7801
sekretariat@ii.uni.wroc.pl
Dziekanat
tel.: 71 375 7892
dziekan@ii.uni.wroc.pl
sprawy studenckie:
dziekanat@ii.uni.wroc.pl
Portiernia
tel.: 71 375 7958
Redaktor strony WWW
redaktor@ii.uni.wroc.pl
Projekt
MAKOS