Cet exposé sera constitué de deux parties portant sur des problèmes de mathématiques discrètes et utilisant des techniques de combinatoire des mots, de géométrie discrète et de pavages du plan.
Dans la première partie, nous présenterons une introduction aux techniques de la tomographie discrète. Ce domaine a pour objet la reconstruction de matrice à valeurs dans {0,1} connaissant un petit nombre de projections (les projections ou contraintes tomographiques sont des vecteurs donnant par exemple le nombre de 1 sur chaque ligne et le nombre de 1 sur chaque colonne). Nous présenterons l’algorithme de Ryser pour la reconstruction de matrices connaissant les projections verticale et horizontale, puis la reconstruction de polyominos horizontalement et verticalement convexes avec contraintes tomographiques. Les méthodes utilisées font appel à la géométrie discrète mais aussi à des réductions à 2-SAT. Enfin, nous aborderons des résultats récents sur la reconstruction de matrices avec périodicité et contraintes tomographiques.
Dans la deuxième partie, nous montrerons que la complexité d’un mot de coupures u dans un pavage régulier par un polyomino Q est égale à Pn(u)=(p+q-1)n +1, pour tout n > 0 où Pn(u) compte le nombre de facteurs distincts de longueur n du mot infini u et où le mot de contour du polyomino Q est donné par 2p segments horizontaux et 2q segments verticaux. Nous reviendrons dans cet exposé sur le théorème de Beauquier-Nivat donnant une caractérisation par mots de contour des polyominos qui pavent le plan par translations.