UQAM - Université du Québec à Montréal
Archive de publications électroniques
UQAM ›  Archive de publications électroniques ›  Efficient generation of the ideals of a poset in Gray code order

Efficient generation of the ideals of a poset in Gray code order

Abdo, Mohamed (2010). « Efficient generation of the ideals of a poset in Gray code order » Thèse. Montréal (Québec, Canada), Université du Québec à Montréal, Doctorat en mathématiques.

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

[img]
Prévisualisation
PDF
3373Kb

Résumé

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

Type de document : Thèse ou essai doctoral accepté
Directeur de thèse : Walsh, TimothyR.
État du document : Non publié
Informations complémentaires : La thèse a été numérisée telle que transmise par l'auteur.
Mots-clés : Ensemble partiellement ordonné, Code Gray, Complexité algorithmique, Idéaux (Algèbre), Algorithme, Programmation générative
Unité d'appartenance : Faculté des sciences > Département de mathématiques
Code ID : 2849
Déposé par : RB Service des bibliothèques
Déposé le : 22 avr. 2010 08:30
Dernière modification : 30 nov. 2010 11:35

Modifier les métadonnées de ce document.

Voir les statistiques sur cinq ans...