Mémoires de Fin d’Etudes
Etablissement
Université d’Oran1 - Ahmed Ben Bella
Affiliation
Département d’Informatique
Auteur
BOUCHAOUR, Hamza Chérif
Directeur de thèse
OUALI M (Maitre de conférence)
Co-directeur
LEBBAH Y (Professeur)
Filière
Informatique
Diplôme
Magister
Titre
Abstraction fonctionnelle des circuits par Isomorphisme de graphes
Mots clés
Circuits numériques; Isomorphisme exact de graphes; Sous-graphes; Programmation par contrainte.
Résumé
Ce travail contribue au développement de méthodes de reconnaissance et de compréhension de circuits, en s’appuyant sur des informations de bas niveau. Les graphes sont utilisés pour représenter mathématiquement la connaissance structurelle. L’intérêt de ce type de représentation est d’autant plus accru quand la taille des données ainsi que la complexité de leur organisation sont élevées. L’isomorphisme de graphes est un problème crucial en théorie et dans beaucoup d’applications. L’isomorphisme exact de graphes est un problème de décision de complexité d’au moins de classe P qui ne s’applique qu’à des graphes exactement identiques. Dans ce travail, nous introduisons une solution d’isomorphisme exact de graphes basée sur la programmation par contrainte. Pour cela, nous proposons un modèle de résolution basé sur le voisinage de premier degré. Nous proposons deux implémentations de ce modèle. Ces implémentations utilisent des opérateurs spécifiques à la programmation par contrainte qui exploitent la structure de donnée représentant les graphes. Nous illustrons la validité de nos implémentations par une application concrète issue du domaine de la microélectronique, qui cherche à trouver un sous-circuit décrit par une Netlist de transistors à l’intérieur d’un ensemble de circuits plus général. Nous comparons ces implémentations en soulignant leurs avantages et inconvénients respectifs.
Date de soutenance
2011
Cote
TH3315
Pagination
X-103F
Format
30 cm
Notes
RESUME ET MOTS CLES EN FRANCAIS ET EN ANGLAIS. GLOSSAIRE.BIBLIOG.101-103F.
Statut
Soutenue