Complexité des homomorphismes de graphes avec listes

Les problèmes de satisfaction de contraintes, qui consistent à attribuer des valeurs à des variables en respectant un ensemble de contraintes, constituent une large classe de problèmes naturels. Pour étudier la complexité de ces problèmes, il est commode de les voir comme des problèmes d'homomorphismes vers des structures relationnelles. Un axe de recherche actuel est la caractérisation des classes de complexité auxquelles appartient le problème d'homomorphisme, ceci dans la perspective de confirmer des conjectures reliant les propriétés algébriques des structures relationelles à la complexité du problème d'homomorphisme. Cette thèse propose dans un premier temps la caractérisation des digraphes pour lesquels le problème d'homomorphisme avec listes appartient à FO. On montre également que dans le cas du problèmes d'homomorphisme avec listes sur les digraphes télescopiques, les conjectures reliant algèbre et complexité sont confirmées. Dans un deuxième temps, on caractérise les graphes pour lesquels le problème d'homomorphisme avec listes est résoluble par cohérence d'arc. On introduit la notion de polymorphisme monochromatique et on propose un algorithme simple qui résoud le problème d'homomorphisme avec listes si le graphe cible admet un polymorphisme monochromatique TSI d'arité k pour tout k ≥ 2.

Système de listes de vérification interactives du niveau de conformité des maquettes avec les recommandations des fabricants de plateformes mobiles

L'ensemble de mon travail a été réalisé grâce a l'utilisation de logiciel libre.

Rupture et continuité : étude comparative du clergé anglo-saxon du Xe siècle issu de la Regularis Concordia avec le clergé anglo-normand des XIe et XIIe siècles

Ce mémoire a pour but de comparer l’état du clergé anglo-saxon de la période de la Regularis Concordia du Xe siècle, avec celui du clergé anglo-normand d’après conquête situé entre 1060 et 1150. La base de cette recherche se fera à partir des sources narratives les plus pertinentes pour cette période. Mais celles-ci ne seront utilisées qu’en support puisque l’essentiel de ce mémoire sera basé sur le dépouillement des listes d’archevêques, d’évêques et d’abbés ayant vécu entre 1060 à 1150. Nous détaillerons leurs origines géographiques, les charges qu’ils ont occupées durant leur vie de même que leurs réseaux sociaux. Nous tenterons de démontrer que contrairement à l’idée reçue, il n’y eut pas de véritable réforme du clergé anglo-normand suite à la conquête, mais davantage une mise à jour de ce dernier, et qu’en fait, le modèle de gouvernance qui fut imposé au clergé anglo-normand au tournant du XIIe siècle fut largement inspiré du fonctionnement de l’Église normande.