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
Télécharger (3MB)

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: Mémoire accepté
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
Déposé par: RB Service des bibliothèques
Date de dépôt: 14 sept. 2009 15:34
Dernière modification: 01 nov. 2014 02:09
Adresse URL : http://www.archipel.uqam.ca/id/eprint/2109

Statistiques

Voir les statistiques sur cinq ans...