LiveZilla Live Chat Software

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

Sur l'arithmétique des polyominos

Tall Amadou Makhtar. (2015). Sur l'arithmétique des polyominos. Mémoire de maîtrise, Université du Québec à Chicoutimi.

[img] PDF
2MB

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.

Type de document:Thèse ou mémoire de l'UQAC (Mémoire de maîtrise)
Date:Janvier 2015
Lieu de publication:Chicoutimi
Programme d'étude:Maîtrise en informatique
Nombre de pages:72
ISBN:Non spécifié
Sujets:Sciences naturelles et génie > Génie > Génie informatique et génie logiciel
Sciences naturelles et génie > Sciences mathématiques > Informatique
Sciences naturelles et génie > Sciences mathématiques > Mathématiques appliquées
Sciences naturelles et génie > Sciences mathématiques > Mathématiques fondamentales
Département, module, service et unité de recherche:Départements et modules > Département d'informatique et de mathématique > Programmes d'études de cycles supérieurs en informatique
Directeur(s), Co-directeur(s) et responsable(s):Blondin Massé, Alexandre
Mots-clés:algorithmique, combinatoire, figures discrètes, pavage, polyominos, primalité, cryptographie
Déposé le:10 févr. 2016 16:22
Dernière modification:11 févr. 2016 23:20
Afficher les statistiques de telechargements

Éditer le document (administrateurs uniquement)

Creative Commons LicenseSauf indication contraire, les documents archivés dans Constellation sont rendus disponibles selon les termes de la licence Creative Commons "Paternité, pas d'utilisation commerciale, pas de modification" 2.5 Canada.

Bibliothèque Paul-Émile-Boulet, UQAC
555, boulevard de l'Université
Chicoutimi (Québec)  CANADA G7H 2B1
418 545-5011, poste 5630