Génération exhaustive de polyominos

Tremblay, Jérôme (2016). « Génération exhaustive de polyominos » Mémoire. Montréal (Québec, Canada), Université du Québec à Montréal, Maîtrise en informatique.

Fichier(s) associé(s) à ce document :

Prévisualisation	PDF Télécharger (6MB)

Résumé

La géométrie digitale est un domaine d'études développé récemment, à cause du développement des outils numériques. Ce mémoire examine deux problèmes importants dans le domaine de la géométrie digitale, à savoir le calcul de l'enveloppe extérieure d'un chemin discret et également la génération exhaustive de polyominos. Les deux reposent sur le codage des objets dans le plan discret, assimilé à la grille carrée Z x Z, par des mots sur l'alphabet de Freeman F = {0, 1, 2, 3}, correspondant aux déplacements élémentaires sur la grille carrée. Pour le problème de l'enveloppe extérieure d'un chemin quelconque (se recoupant ou pas), on utilise une structure de données utilisant deux arbres quaternaires superposés, introduite par Brlek, Provençal et Koskas. Utilisant un parcours mimant l'algorithme de la main droite dans un labyrinthe on obtient un algorithme linéaire en temps et en espace pour effectuer le calcul de l'enveloppe extérieure. Dans le cas de la génération de polyominos codés par un chemin décrivant leurs périmètres de site, on utilise une adaptation du jeu de go pour construire à partir de l'origine et dans le sens antihoraire le chemin qui les borne. L'algorithme est exhaustif, et génère un polyomino chaque fois que le joueur noir gagne. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : polyominos, gominas, périmètre de site, chemins, enveloppe externe, génération exhaustive, algorithme, mots, arbre radix.

Type:	Mémoire accepté
Informations complémentaires:	Le mémoire a été numérisé tel que transmis par l'auteur.
Directeur de thèse:	Brlek, Srecko
Mots-clés ou Sujets:	Polyominos / Génération exhaustive / Enveloppes (Géométrie) / Algorithmes / Géométrie discrète / Géométrie -- Informatique
Unité d'appartenance:	Faculté des sciences > Département d'informatique
Déposé par:	Service des bibliothèques
Date de dépôt:	02 sept. 2016 18:41
Dernière modification:	02 sept. 2016 18:41
Adresse URL :	http://archipel.uqam.ca/id/eprint/8783

Modifier les métadonnées (propriétaire du document)

Statistiques