15 avril 2011 de 16 h 00 à 18 h 00 (heure de Montréal/HNE) Sur place
In July 2010 a team of four researchers led by Tomas Rokicki of Palo Alto announced that "God's Number" for the Rubik's Cube is 20, that is, any scramble can be solved in at most 20 moves (where a 90-degree or 180-degree twist counts as one move). Stated in group theory language, the problem asked for the diameter of the Cayley graph of the Rubik's Cube group using the so-called half-turn metric. The speaker had the privilege of being part of its solution, ultimately achieved through Rokicki's adaptation of Herbert Kociemba's two-step solution algorithm together with the solution of an auxiliary set cover problem and the help of Google's computing infrastructure. In this talk we will outline the thirty-year history of the problem and discuss the primary mathematical and computational breakthroughs that led to its solution.
Adresse
CRM, UdeM, Pav. André-Aisenstadt, 2920, ch. de la Tour, salle 1360