UQAM - Université du Québec à Montréal
Archive de publications électroniques
UQAM ›  Archive de publications électroniques ›  Les codes Gray pour les idéaux d'un poset et pour d'autres objets combinatoires

Les codes Gray pour les idéaux d'un poset et pour d'autres objets combinatoires

Abdo, Mohamed (2006). « Les codes Gray pour les idéaux d'un poset et pour d'autres objets combinatoires » 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
3024Kb

Résumé

Pruesse et Ruskey ont trouvé un code Gray pour les idéaux d'un ensemble partiellement ordonné (poset) et un algorithme récursif pour les engendrer. Dans ce mémoire, un algorithme non-récursif qui engendre la même liste d'idéaux est présenté. De plus, plusieurs autres codes Gray classiques majoritairement reliés aux posets et leurs implantations sont étudiés. Plus particulièrement, les codes Gray de Chase et de Ruskey pour les combinaisons, celui de Ruskey et Proskurowski pour les mots de Dyck et celui de Walsh pour les involutions sans point fixe sont étudiés. Le code Gray de Chase est présenté sous forme d'un programme FORTRAN. Vajnovszki et Walsh ont trouvé une implantation plus simple sans en donner une preuve formelle; une telle preuve est présentée dans ce mémoire. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Code Gray, Idéal, Ensemble partiellement ordonné (poset), Extension linéaire, Poset forêt, Algorithme, Non-récursif, Sans-boucle, Temps constant amorti (CAT).

Type de document : Mémoire accepté
État du document : Non publié
Informations complémentaires : Le mémoire a été numérisé tel que transmis par l'auteur.
Mots-clés : Idéaux (Algèbre), Ensemble partiellement ordonné, Algorithme, Code Gray
Unité d'appartenance : Faculté des sciences > Département de mathématiques
Code ID : 2109
Déposé par : RB Service des bibliothèques
Déposé le : 14 sept. 2009 11:34
Dernière modification : 08 déc. 2010 15:55

Modifier les métadonnées de ce document.

Voir les statistiques sur cinq ans...