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

摘要

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 implantationsudsont é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).