Pruesse et Ruskey ont présenté un algorithme pour la génération de leur code Gray pour les idéaux d'un poset (ensemble partiellement ordonné) où deux idéaux adjacents diffèrent par un ou deux éléments. Leur algorithme fonctionne en temps amorti de O(n) par idéal. Squire a présenté une récurrence pour les idéaux d'un poset qui lui a permis de trouver un algorithme pour générer ces idéaux en temps amorti de O(log n) par idéal, mais pas en code Gray. Nous utilisons la récurrence de Squire pour trouver un code Gray pour les idéaux d'un poset, où deux idéaux adjacents diffèrent par un ou deux éléments. Dans le pire des cas, notre algorithme a la même complexité que celle de l'algorithme de Pruesse et Ruskey et dans les autres cas, sa complexité est meilleure que celle de leur algorithme et se rapproche de celle de l'algorithme de Squire. Squire a donné une condition pour obtenir cette complexité. Nous avons trouvé une condition moins restrictive que la sienne. Cette condition nous a permis d'améliorer la complexité de notre algorithme. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Poset, Extension linéaire, Cycle hamiltonien, Code Gray, Algorithme, Complexité.
| Identifer | oai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:QMUQ.2849 |
| Date | January 2010 |
| Creators | Abdo, Mohamed |
| Source Sets | Library and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada |
| Detected Language | French |
| Type | Thèse acceptée, NonPeerReviewed |
| Format | application/pdf |
| Relation | http://www.archipel.uqam.ca/2849/ |
Page generated in 0.0021 seconds