Un homomorphisme est une fonction entre deux structures, par exemple des graphes, qui respecte certaines contraintes. Dans ce mémoire, on étudie la complexité des problèmes d'homomorphisme, c'est-à-dire des problèmes où l'on doit décider s'il existe une telle fonction entre deux structures. On présentera des propriétés sur ces structures qui permettent de déterminer cette complexité. On s'intéressera particulièrement aux problèmes d'homomorphisme qui appartiennent à la classe de complexité NL, une classe contenant des problèmes dont la résolution par un algorithme non déterministe nécéssite peu d'espace mémoire.

Ce mémoire porte sur le problème de décision CSP (de l'anglais Constraint Satisfaction Problem, c'est-à-dire problème de satisfaction de contraintes), soit le problème pour lequel nous devons assigner des valeurs à des variables de telle sorte que toutes les conditions portant sur ces variables soient remplies. De surcroît, ce mémoire porte sur les problèmes de détection d'homomorphisme entre structures relationelles qui sont équivalents à CSP. Pour être plus précis, nous nous intéressons à l'algorithme de cohérence d'arc pour les instances de CSP, soit ArcjConsistency. Celui-ci suffit à solutionner un certain sous-ensemble de CSP. Or nous étudions quelques-unes de ses variantes qui sont des algorithmes plus coûteux, mais plus puissants, c'est-à-dire que le sous-ensemble de CSP qu'ils solutionnent est plus grand. La nouveauté de ce mémoire est de décrire et d'étudier une variante de ArcjConsistency, soit NLjCohérence, qui est un algorithme moins puissant mais plus efficace. L'objectif pour nous est de trouver des caractéristiques intéressantes au sujet de ce nouvel algorithme, qui se veut être une version « espace logarithmique » de ArcjConsistency. De plus, nous travaillons sur un sous-ensemble de CSP dit implicatif. Nous démontrons que NL_Cohérence solutionne les instances de ce sous-ensemble en espace logarithmique non-déterministe.

Soit Σ une surface compacte connexe orientée avec une seule composante du bord. Notons par M le groupe d'homéotopie de Σ. En considérant l'action de M sur le groupe fondamental de Σ, il est possible de définir différentes filtrations de M ainsi que des homomorphismes sur chaque terme de ces filtrations. Le but de cette thèse est double. En premier lieu, nous étudions deux filtrations de M : la " filtration de Johnson-Levine " introduite par Levine et la " filtration de Johnson alternative " introduite recemment par Habiro et Massuyeau. Les définitions de ces deux filtrations prennent en compte un corps en anses bordé par la surface. Nous nous référons à ces filtrations comme " filtrations de type Johnson " et les homomorphismes correspondants sont appelés " homomorphismes de type Johnson " par leur analogie avec la filtration de Johnson originale et les homomorphismes de Johnson usuels. Nous donnons une comparaison de la filtration de Johnson avec la filtration de Johnson-Levine au niveau du monoïde des cobordismes d'homologie de Σ. Nous donnons également une comparaison entre la filtration de Johnson alternative, la filtration Johnson-Levine et la filtration de Johnson au niveau du groupe d'homéotopie. Deuxièmement, nous étudions la relation entre les " homomorphismes de type Johnson" et l'extension fonctorielle de l'invariant perturbatif universel des variétés de dimension trois (l'invariant de Le-Murakami-Ohtsuki ou invariant LMO). Cette extension fonctorielle s'appelle le foncteur LMO et il prend ses valeurs dans une catégorie de diagrammes. Nous démontrons que les "homomorphismes de type Johnson " peuvent être lus dans la réduction arborée du foncteur LMO. En particulier, cela fournit une nouvelle grille de lecture de la réduction arborée du foncteur LMO. / Let Σ be a compact oriented surface with one boundary component and let M denote the mapping class group of Σ. By considering the action of M on the fundamental group of Σ it is possible to define different filtrations of M together with some homomorphisms on each term of the filtrations. The aim of this thesis is twofold. First, we study two filtrations of M : the « Johnson-Levine filtration » introduced by Levine and « the alternative Johsnon filtration » introduced recently by Habiro and Massuyeau. The definition of both filtrations involve a handlebody bounded by Σ. We refer to these filtrations as ≪ Johnson-type filtrations » and the corresponding homomorphisms have referred to as « Johnson-type homomorphisms » by their analogy with the original Johnson filtration and the usual Johnson homomorphisms. We provide a comparison of the Johnson filtration with the Johnson-Levine filtration at the level of the monoid of homology cobordisms of Σ. We also provide a comparison of the alternative Johnson filtration with the Johnson-Levine filtration and the Johnson filtration at the level of the mapping class group. Secondly, we study the relationship between the « Johnson-type homomorphisms » and the functorial extension of the universal perturbative invariant of 3-manifolds (the Le-Murakami-Ohtsuki invariant or LMO invariant). This functorial extension is calling the LMO functor and it takes values in a category of diagrams. We prove that the « Johnson-type homomorphisms » is in the tree reduction of the LMO functor. In particular, this provides a new reading grid of the tree reduction of the LMO functor.

.

Dans cette thèse, nous considérons des questions relatives aux homomorphismes de quatre types distincts de graphes : les graphes orientés, les graphes orientables, les graphes 2-arête colorés et les graphes signés. Pour chacun des ces quatre types, nous cherchons à déterminer le nombre chromatique, le nombre de clique relatif et le nombre de clique absolu pour différentes familles de graphes planaires : les graphes planaires extérieurs, les graphes planaires extérieurs de maille fixée, les graphes planaires et les graphes planaires de maille fixée. Nous étudions également les étiquetages "2-dipath" et "L(p,q)" des graphes orientés et considérons les catégories des graphes orientables et des graphes signés. Nous étudions enfin les différentes relations pouvant exister entre ces quatre types d'homomorphismes de graphes. / An oriented graph is a directed graph with no cycle of length at most two. A homomorphism of an oriented graph to another oriented graph is an arc preserving vertex mapping. To push a vertex is to switch the direction of the arcs incident to it. An orientable graph is an equivalence class of oriented graph with respect to the push operation. An orientable graph [−→G] admits a homomorphism to an orientable graph [−→H] if an element of [−→G] admits a homomorphism to an element of [−→H]. A signified graph (G, Σ) is a graph whose edges are assigned either a positive sign or a negative sign, while Σ denotes the set of edges with negative signs assigned to them. A homomorphism of a signified graph to another signified graph is a vertex mapping such that the image of a positive edge is a positive edge and the image of a negative edge is a negative edge. A signed graph [G, Σ] admits a homomorphism to a signed graph [H, Λ] if an element of [G, Σ] admits a homomorphism to an element of [H, Λ]. The oriented chromatic number of an oriented graph −→G is the minimum order of an oriented graph −→H such that −→G admits a homomorphism to −→H. A set R of vertices of an oriented graph −→G is an oriented relative clique if no two vertices of R can have the same image under any homomorphism. The oriented relative clique number of an oriented graph −→G is the maximum order of an oriented relative clique of −→G. An oriented clique or an oclique is an oriented graph whose oriented chromatic number is equal to its order. The oriented absolute clique number of an oriented graph −→G is the maximum order of an oclique contained in −→G as a subgraph. The chromatic number, the relative chromatic number and the absolute chromatic number for orientable graphs, signified graphs and signed graphs are defined similarly. In this thesis we study the chromatic number, the relative clique number and the absolute clique number of the above mentioned four types of graphs. We specifically study these three parameters for the family of outerplanar graphs, of outerplanar graphs with given girth, of planar graphs and of planar graphs with given girth. We also try to investigate the relation between the four types of graphs and prove some results regarding that. In this thesis, we provide tight bounds for the absolute clique number of these families in all these four settings. We provide improved bounds for relative clique numbers for the same. For some of the cases we manage to provide improved bounds for the chromatic number as well. One of the most difficult results that we prove here is that the oriented absolute clique number of the family of planar graphs is at most 15. This result settles a conjecture made by Klostermeyer and MacGillivray in 2003. Using the same technique we manage to prove similar results for orientable planar graphs and signified planar graphs. We also prove that the signed chromatic number of triangle-free planar graphs is at most 25 using the discharging method. This also implies that the signified chromatic number of trianglefree planar graphs is at most 50 improving the previous upper bound. We also study the 2-dipath and oriented L(p, q)-labeling (labeling with a condition for distance one and two) for several families of planar graphs. It was not known if the categorical product of orientable graphs and of signed graphs exists. We prove both the existence and also provide formulas to construct them. Finally, we propose some conjectures and mention some future directions of works to conclude the thesis.

Les analogies auxquelles nous nous intéressons mettent quatre chaînes de symboles en proportion, par exemple, fable : fabuleux :: miracle : miraculeux ou abc : aabbcc :: a^n.b^n.c^n : a^n+1.b^n+1.c^n+1. Une étude historique de l'analogie en linguistique nous a permis de dégager les deux articulations (conformité et rapport) et les notions constitutives (similarité et contiguïté) de ce type d'analogie. De postulats généraux nous avons tiré une caractérisation formelle (encore partielle) rendant compte de la commutation entre chaînes de symboles. Une application directe est la conjugaison automatique par analogie. Nous avons proposé de définir certains langages formels à l'aide de ce type d'analogie. La grammaticalité, c'est-à-dire l'appartenance à un langage, est testée par égalité avec certaines chaînes attestées après réduction selon des modèles analogiques, eux aussi attestés. L'absence de non-terminaux fait de ce type de grammaires des grammaires par l'exemple. Nous examinons la possible place de tels langages dans le débat sur l'adéquation des langages formels à la description des langues. En forçant la conservation des analogies entre deux langages de chaînes analogiques, on obtient une méthode générale applicable à divers problèmes du traitement automatique des langues, par exemple, l'analyse structurale ou la traduction automatique de phrases.

Les architectures parallèles sont désormais présentes dans tous les matériels informatiques, mais les programmeurs ne sont généralement pas formés à leur programmation dans les modèles explicites tels que MPI ou les Pthreads. Il y a un besoin important de modèles plus abstraits tels que les squelettes algorithmiques qui sont une approche structurée. Ceux-ci peuvent être vus comme des fonctions d’ordre supérieur synthétisant le comportement d’algorithmes parallèles récurrents que le développeur peut ensuite combiner pour créer ses programmes. Les développeurs souhaitent obtenir de meilleures performances grâce aux programmes parallèles, mais le temps de développement est également un facteur très important. Les approches par squelettes algorithmiques fournissent des résultats intéressants dans ces deux aspects. La bibliothèque Orléans Skeleton Library ou OSL fournit un ensemble de squelettes algorithmiques de parallélisme de données quasi-synchrones dans le langage C++ et utilise des techniques de programmation avancées pour atteindre une bonne efficacité. Nous avons amélioré OSL afin de lui apporter de meilleures performances et une plus grande expressivité. Nous avons voulu analyser le rapport entre les performances des programmes et l’effort de programmation nécessaire sur OSL et d’autres modèles de programmation parallèle. La comparaison rigoureuse entre des programmes parallèles dans OSL et leurs équivalents de bas niveau montre une bien meilleure productivité pour les modèles de haut niveau qui offrent une grande facilité d’utilisation tout en produisant des performances acceptables. / Parallel architectures have now reached every computing device, but software developers generally lackthe skills to program them through explicit models such as MPI or the Pthreads. There is a need for moreabstract models such as the algorithmic skeletons which are a structured approach. They can be viewed ashigher order functions that represent the behaviour of common parallel algorithms, and those are combinedby the programmer to generate parallel programs. Programmers want to obtain better performances through the usage of parallelism, but the development time implied is also an important factor. Algorithmic skeletons provide interesting results in both those fields. The Orléans Skeleton Library or OSL provides a set of algorithmic skeletons for data parallelism within the bulk synchronous parallel model for the C++ language. It uses advanced metaprogramming techniques to obtain good performances. We improved OSL in order to obtain better performances from its generated programs, and extended its expressivity. We wanted to analyze the ratio between the performance of programs and the development effort needed within OSL and other parallel programming models. The comparison between parallel programs written within OSL and their equivalents in low level parallel models shows a better productivity for high level models : they are easy to use for the programmers while providing decent performances.

Cette thèse étudie les aspects combinatoires, algorithmiques et la complexité de problèmes de théorie des graphes, et tout spécialement de problèmes liés aux notions de marches, de transitions et de distance dans les graphes. Nous nous intéressons d’abord au problème de traffic monitoring, qui consiste à placer aussi peu de capteurs que possible sur les arcs d’un graphe de façon à pouvoir reconstituer des marches d’objets. La caractérisation d’instances intéressantes dans la pratique nous amène à la notion de transitions interdites, qui renforce le modèle de graphe. Notre travail sur les graphes à transitions interdites comprend aussi l’étude de la notion d’ensemble de transitions connectant, que l’on peut voir comme l’analogue en terme de transitions de la notion d’arbre couvrant. Une partie importante de cette thèse porte sur les graphes géométriques, qui sont des graphes dont les sommets sont des points de l’espace réel et dont les arêtes sont déterminées par les distances géométriques entre les sommets. Ces graphes sont au coeur du célèbre problème de Hadwiger-Nelson et nous sont d’une grande aide dans notre étude de la densité des ensembles qui évitent la distance 1 dans plusieurs types d’espaces normés. Nous développons des outils pour étudier ces problèmes et les utilisons pour prouver la conjecture de Bachoc-Robins sur plusieurs paralléloèdres. Nous nous penchons aussi sur le cas du plan euclidien et améliorons les bornes sur la densité des ensembles évitant la distance 1 et sur son nombre chromatique fractionnaire. Enfin, nous étudions la complexité de problèmes d’homomorphismes de graphes et établissons des théorèmes de dichotomie sur la complexité des homomorphismes localement injectifs vers les tournois réflexifs. / This thesis studies combinatorial, algorithmic and complexity aspects of graph theory problems, and especially of problems related to the notions of walks, transitions and distances in graphs. We first study the problem of traffic monitoring, in which we have to place as few censors as possible on the arcs of a graph to be able to retrace walks of objects. The characterization of instances of practical interests brings us to the notion of forbidden transitions, which strengthens the model of graphs. Our work on forbidden-transition graphs also includes the study of connecting transition sets, which can be seen as a translation to forbidden-transition graphs of the notion of spanning trees. A large part of this thesis focuses on geometric graphs, which are graphs whose vertices are points of the real space and whose edges are determined by geometric distance between the vertices. This graphs are at the core of the famous Hadwiger- Nelson problem and are of great help in our study of the density of sets avoiding distance 1 in various normed spaces. We develop new tools to study these problems and use them to prove the Bachoc-Robins conjecture on several parallelohedra. We also investigate the case of the Euclidean plane and improve the bounds on the density of sets avoiding distance 1 and on its fractional chromatic number. Finally, we study the complexity of graph homomorphism problems and establish dichotomy theorems for the complexity of locally-injective homomorphisms to reflexive tournaments.

Les architectures parallèles sont désormais présentes dans tous les matériels informatiques, mais les pro- grammeurs ne sont généralement pas formés à leur programmation dans les modèles explicites tels que MPI ou les Pthreads. Il y a un besoin important de modèles plus abstraits tels que les squelettes algorithmiques qui sont une approche structurée. Ceux-ci peuvent être vus comme des fonctions d'ordre supérieur synthétisant le comportement d'algorithmes parallèles récurrents que le développeur peut ensuite combiner pour créer ses programmes. Les développeurs souhaitent obtenir de meilleures performances grâce aux programmes parallèles, mais le temps de développement est également un facteur très important. Les approches par squelettes algorithmiques fournissent des résultats intéressants dans ces deux aspects. La bibliothèque Orléans Skeleton Library ou OSL fournit un ensemble de squelettes algorithmiques de parallélisme de données quasi-synchrones dans le langage C++ et utilise des techniques de programmation avancées pour atteindre une bonne efficacité. Nous avons amélioré OSL afin de lui apporter de meilleures performances et une plus grande expressivité. Nous avons voulu analyser le rapport entre les performances des programmes et l'effort de programmation nécessaire sur OSL et d'autres modèles de programmation parallèle. La comparaison rigoureuse entre des programmes parallèles dans OSL et leurs équivalents de bas niveau montre une bien meilleure productivité pour les modèles de haut niveau qui offrent une grande facilité d'utilisation tout en produisant des performances acceptables.