Méthodes récursives d'énumération et application aux polycubes-arbres

Bouallagui, Lotfi (2018). « Méthodes récursives d'énumération et application aux polycubes-arbres » Mémoire. Montréal (Québec, Canada), Université du Québec à Montréal, Maîtrise en mathématiques.

Fichier(s) associé(s) à ce document :
[img]
Prévisualisation
PDF
Télécharger (8MB)

Résumé

Ce mémoire se situe dans le cadre de la combinatoire énumérative et s'intéresse particulièrement aux approches basées sur les constructions récursives. Une application est effectuée pour la génération exhaustive des polycubes-arbres, une classe particulière de polycubes multidimensionnels dont le graphe dual, graphe d'adjacence des cellules dans le réseau hypercubique, est connexe et acyclique. La génération est restreinte aux dimensions 2, 3 et 4 et à la forme libre de ces objets. On explore les développements les plus récents pour trois méthodes qui partagent la même approche récursive, qui sont la méthode symbolique, les grammaires d'objets et la méthode ECO. La méthode symbolique fournit un dictionnaire pour la traduction systématique de la majorité des constructions discrètes en opérations algébriques sur les fonctions génératrices. C'est un outil simple et formel qui réduit l'étude d'une classe d'objets à la tâche plus facile de lui trouver une spécification en termes de constructions combinatoires de base. Les grammaires d'objets sont aussi des constructions récursives des objets, et sous certaines conditions, elles se traduisent en équations sur les fonctions génératrices. Quant à la méthode ECO, elle construit les objets par expansion locale d'objets plus petits, ce qui se traduit aussi par des équations sur la fonction génératrice de la classe énumérée. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : polyomino-arbre, polycube-arbre, énumération, fonction génératrice, grammaire d'objets, méthode ECO

Type: Mémoire accepté
Informations complémentaires: Le mémoire a été numérisé tel que transmis par l'auteur.
Directeur de thèse: Blondin Massé, Alexandre
Mots-clés ou Sujets: Problèmes combinatoires d'énumération / Fonctions génératrices / Polyominos / Polycubes / Arbres
Unité d'appartenance: Faculté des sciences > Département de mathématiques
Déposé par: Service des bibliothèques
Date de dépôt: 17 oct. 2018 10:55
Dernière modification: 17 oct. 2018 10:55
Adresse URL : http://archipel.uqam.ca/id/eprint/11735

Statistiques

Voir les statistiques sur cinq ans...