Le blog-notes mathématique du coyote

 

Extra

Editorial

Ce blog a pour sujet les mathématiques et leur enseignement au Lycée. Son but est triple.
Premièrement, ce blog est pour moi une manière idéale de classer les informations que je glâne au cours de mes voyages en Cybérie.
Deuxièmement, ces billets me semblent bien adaptés à la génération zapping de nos élèves. Ces textes courts et ces vidéos, privilégiant le côté ludique des maths, pourront, je l'espère, les intéresser et leur donner l'envie d'en savoir plus.
Enfin, c'est un bon moyen de communiquer avec des collègues de toute la francophonie.

mardi 22 juin 2010

Un ballon de foot fractal

Un ballon de foot fractal... et d’autres objets étranges.

Un superbe article de Jos Leys, paru dans Images des Mathématiques, avec des illustrations d'une beauté toute... mathématique.

samedi 5 juin 2010

Le problème des n dames pour illustrer les méta-heuristiques

Le but du problème des huit dames est de placer huit dames d'un jeu d'échecs sur un échiquier de 8×8 cases sans que les dames se menacent mutuellement, conformément aux règles du jeu d'échecs. Par conséquent, deux dames ne devront jamais partager la même rangée, colonne, ou diagonale.
Le problème des n dames est une généralisation de ce problème classique : on considère un échiquier nxn au lieu d'un échiquier 8x8. Bien que ce ne soit pas à proprement parlé un problème d'optimisation, il présente de nombreux avantages :

  • il est visuel et facile à comprendre ;
  • on peut coder la position des dames très simplement : pour chaque colonne, on note sur quelle ligne se trouve la dame. Par exemple, une position sera notée [2, 4, 6, 8, 3, 1, 7, 5] ;
  • on passe très facilement d'une configuration à une configuration voisine : il suffit d'échanger deux colonnes. Une position voisine (mais qui ne satisfait pas forcément les contraintes) de celle ci-dessus est par exemple [2, 1, 6, 8, 3, 4, 7, 5].
On peut le traiter comme un problème d'optimisation si l'on considère qu'il faut minimiser le nombre de conflits (on parlera de conflit quand deux dames se menacent mutuellement). Il s'agira ici de placer n dames sur l'échiquier nxn, sans aucun conflit, en partant d'une solution avec une seule dame par ligne et par colonne (par exemple toutes les dames sur la diagonale) et en échangeant deux colonnes. On ne cherchera pas toutes les solutions possibles : une seule nous suffira. Notons que dans un problème d'optimisation classique, il n'y a en général qu'une seule meilleure solution. Ici il y en a plusieurs.

Lire mon article complet : "Le problème des n dames pour illustrer les méta-heuristiques", Bulletin no 113 de la SSPMP, juin 2010