Abstract FR:

Cette thèse est une contribution à l'étude de problèmes de pavages par des dominos. Nous montrons comment élargir au cas d'un polyomino avec des trous la méthode de Thurston qui permet de paver en temps linéaire un polyomino sans trous par des dominos. Nous présentons un algorithme de pavage de complexité O(kn) pour un polyomino avec n cellules et k trous. En particulier, cet algorithme est linéaire pour un polyomino avec un nombre borné de trous. Nous exposons aussi l'état de nos recherches sur le problème du pavage de cardinalité maximale et, plus généralement, sur celui du couplage maximum dans un graphe biparti plan. Nous présentons un algorithme original de couplage dont la complexité reste encore à déterminer. Nous considérons enfin le problème de la reconstruction du pavage d'un rectangle à partir de ses projections orthogonales. Ce problème connu depuis une dizaine d'années restait non résolu. Nous présentons un algorithme polynomial qui réalise cette reconstruction.