Constellation, le dépôt institutionnel de l'Université du Québec à Chicoutimi

Énumération de transversaux de circuits de cardinalité minimale à l'aide d'arbres et/ou

Bouklab Raouf. (2016). Énumération de transversaux de circuits de cardinalité minimale à l'aide d'arbres et/ou. Mémoire de maîtrise, Université du Québec à Chicoutimi.

[thumbnail of Bouklab_uqac_0862N_10188.pdf] PDF
1MB

Résumé

Le problème de trouver un transversal de circuits de cardinalité minimale dans un graphe orienté est l’un des problèmes NP-difficiles classiques définis par Karp en 1972. Il consiste à identifier un sous-graphe acyclique à partir d’un graphe donné en enlevant le moins de sommets possible. L’ensemble de sommets enlevés constitue alors un transversal de circuits de cardinalité minimale (TCCM). Un graphe peut posséder plusieurs transversaux de circuits de même cardinalité minimale. Pour pouvoir énumérer et enregistrer la famille de tous les ensembles de solutions (TCCM) d’un graphe, il est indispensable d’utiliser une structure de données permettant de les stocker implicitement et de manière compacte afin d’optimiser l’espace mémoire occupé par la famille et de bien gérer les sommets redondants. Dans cette perspective, nous introduisons une structure de données notée arbre et/ou, qui est un arbre dans lequel les noeuds internes sont des connecteurs logiques (, et -) et les feuilles sont des valeurs de l’ensemble de solutions. Dans ce mémoire, nous présentons la définition et l’implémentation de la structure de base des arbres et/ou, ainsi que la description et la mise en oeuvre des différents modificateurs, requêtes et opérations qui peuvent être appliqués à cette structure dans un contexte d’énumération. Nous terminons notre travail par l’introduction d’un algorithme permettant la construction efficace d’un arbre et/ou représentant tous les TCCM d’un graphe orienté.

Type de document:Thèse ou mémoire de l'UQAC (Mémoire de maîtrise)
Date:Janvier 2016
Lieu de publication:Chicoutimi
Programme d'étude:Maîtrise en informatique
Nombre de pages:110
ISBN:Non spécifié
Sujets:Sciences naturelles et génie > Sciences mathématiques > Informatique
Département, module, service et unité de recherche:Départements et modules > Département d'informatique et de mathématique > Programmes d'études de cycles supérieurs en informatique
Directeur(s), Co-directeur(s) et responsable(s):Hallé, Sylvain
Blondin Massé, Alexandre
Mots-clés:algorithmique, arbre et/ou, problèmes de graphes, problèmes NP-complet, structures de données, transversal de circuits minimal, complexité, NP-complétude, diagramme binaire de décision, fonction booléenne, transversal de circuits de cardinalité minimale
Déposé le:13 juill. 2016 08:34
Dernière modification:05 déc. 2017 00:38
Afficher les statistiques de telechargements

Éditer le document (administrateurs uniquement)

Creative Commons LicenseSauf indication contraire, les documents archivés dans Constellation sont rendus disponibles selon les termes de la licence Creative Commons "Paternité, pas d'utilisation commerciale, pas de modification" 2.5 Canada.

Bibliothèque Paul-Émile-Boulet, UQAC
555, boulevard de l'Université
Chicoutimi (Québec)  CANADA G7H 2B1
418 545-5011, poste 5630