Constellation, le dépôt institutionnel de l'Université du Québec à Chicoutimi

Résumé

Ce mémoire de maîtrise se consacre à l’étude des figures discrètes, un sujet à l’intersection de la combinatoire des mots et la géométrie digitale. Décrite simplement, une figure discrète est un assemblage fini de pixels joints côté par côté. Toute figure discrète se décompose en composantes connexes appelées polyominos, un objet très connu en combinatoire et en théorie des jeux. Dans sa thèse, en 2008, Provençal propose quelques problèmes ouverts sur les polyominos et introduit ainsi le concept de polyominos premiers et composés. Jusqu’à maintenant, on en sait très peu sur cette notion de primalité. En effet, à notre connaissance, le seul document qui y fait référence est un article publié en 2012 par Blondin Massé, Garon et Labbé dans lequel les auteurs résolvent une conjecture de Provençal en s’appuyant sur la notion de polyominos premiers et composés. Dans ce mémoire, nous explorons plus en détails ce sujet. En plus de fournir une définition et un cadre plus formel, nous proposons un algorithme polynomial (par rapport au périmètre du polyomino) permettant de décomposer celui-ci en un produit de polyominos premiers. Nous discutons également des implications potentielles de ces idées en cryptographie.