Algorithmes, jeux et graphes

Ne votez pas, jugez !

Le scrutin majoritaire n’est pas une méthode démocratique. Pourquoi ? Le but d’une élection est de mesurer les rapports de pouvoir entre les candidats (et leurs partis) et d’élire celui qui est le plus soutenu. Mais le scrutin majoritaire mesure mal les opinions… et peut théoriquement élire un candidat autre que celui voulu par l’électorat. D’après les travaux de M. Balinski et R. Laraki.
Jean-Baptiste Caillau McTAO

La théorie des jeux: petits paradoxes et grandes interrogations.

La théorie des jeux : sous ce titre se cache un vaste domaine de recherche né à la frontière de l’économie et des mathématiques, qui a trouvé des applications jusqu’en biologie et dans l’analyse de l’Internet. De quels jeux s’agit-il ici ? Rien à voir avec les jeux vidéos, mais plutôt avec toutes les situations où des acteurs, appelés « joueurs», sont amenés à prendre « au mieux » des décisions dont les effets dépendent de ce que font les autres. Il s’agit alors de déterminer ce qu’on va appeler « solution », ou « équilibre », qui dépend des circonstances, et de calculer cet équilibre. On verra que cette théorie est aujourd’hui incontournable, mais très imparfaite. On pourra au choix développer une ou deux applications de la théorie des jeux en trafic urbain (analyser la répartition du trafic entre divers itinéraires possibles), ou en économie (la non unicité de l’équilibre de Nash), ou encore en écologie comportemantale (utilisation de parasitoïdes pour lutter contre la pyrale du maïs). Pierre Bernhard BIOCORE

Puzzles combinatoires

Quelques puzzles combinatoires simples sont présentés : comment dessiner une figure sans lever le crayon ? le problème des 3 maisons et des 3 services et des problèmes de coloration de cartes. Après avoir laissé chercher les enfants on leur donne la solution et surtout un algorithme permettant de trouver une solution (ou de décider qu’il n’y en a pas) est donné. Ceci introduit la notion d;algorithmes. Pour les plus grands, on effleure les notions de complexité et d’optimalité des algorithmes. Frédéric Havet COATI

Pavage : art, preuves et jeux.

Une exposition sur les différents types de pavages du plan sont présentés, ainsi quelques-unes de leur utilisation en mathématiques et en art. Elle est complétée par des ateliers :
– puzzles correspondant aux preuves de certains théorèmes, comme celui de Pythagore.
– jeu consistant à déterminer le type de pavage de plusieurs oeuvres d’Escher.
– jeux de pavages permettant de se familiariser avec rotation symétries (Tangram) mais aussi de la combinatoire (Pentomino).
Frédéric Havet COATI

Comment gagner au jeu de Nim (et à d’autres jeux combinatoires).

La théorie des jeux combinatoires est une théorie mathématique qui étudie les jeux à deux joueurs comportant un concept de position, et où les joueurs jouent à tour de rôle un coup d’une façon définie par les règles (le hasard n’intervient pas), dans le but d’atteindre une certaine condition de victoire. Le jeu de Nim est un exemple bien connu de tels jeux. Par le biais de la théorie des graphes, nous expliquons comment gagner à coup sûr (quand cela est possible). Il est remarquable que dans certains cas, on peut prouver mathématiquement que le premier participant à jouer « doit » gagner, mais on ne sait pas comment.
Nicolas Nisse COATI

Pas besoin de réfléchir, les ordinateurs calculent tellement vite ?
Théorie des graphes et algorithmique pour les réseaux.

Les réseaux de télécommunication mais aussi les réseaux routiers, sociaux ou biologiques se modélisent bien avec des graphes. Les sommets représentent les routeurs, les abonnés, les villes, les individus ou les protéines. Les arêtes représentent des liaisons ou des relations. Au cours de cette conférence, nous présentons divers problèmes qui se posent dans ces réseaux. Pour certains d’entre eux, nous ne savons pas calculer une solution autrement que « tester toutes les solutions potentielles ». Cette question est d’une importance majeure car un grand nombre de problèmes ne peuvent pas être résolus (en un temps raisonnable) même si les ordinateurs effectuent un très très grand nombre d’opérations par seconde. De nombreux chercheurs réfléchissent à améliorer ces temps de calcul prohibitifs. Nous présentons certains de ces problèmes difficiles à résoudre (par exemple le problème du voyageur de commerce) et montrons également des problèmes pour lesquels des solutions efficaces existent.
Dorian Mazauric ABS

Le nombre d’Or, mythes et curiosités.

Le nombre d’or est connu depuis l’antiquité. Mais s’il a quelques propriétés amusantes, il n’a ni le caractère quasi magique qu’on lui prête, ni connu l’usage antique, ni même moderne, qu’on prétend.
Pierre Bernhard BIOCORE