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 :

Prévisualisation	PDF Télécharger (3MB)

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:	Thèse ou essai doctoral accepté
Informations complémentaires:	La thèse a été numérisée telle que transmise par l'auteur.
Directeur de thèse:	Walsh, TimothyR.
Mots-clés ou Sujets:	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
Déposé par:	RB Service des bibliothèques
Date de dépôt:	22 avr. 2010 12:30
Dernière modification:	01 nov. 2014 02:13
Adresse URL :	http://archipel.uqam.ca/id/eprint/2849

Modifier les métadonnées (propriétaire du document)

Statistiques