Dans cette thèse nous étudierons des problématiques de graphes. Nous proposons deux études théoriques sur la recherche et l'énumération de cliques et quasi-cliques. Ensuite nous proposons une étude appliquée sur la propagation d'information dans un graphe d'entités nommées. Premièrement, nous étudierons la recherche de cliques dans des graphes compressés. Les problèmes MCE et MCP sont des problèmes rencontrés dans l'analyse des graphes. Ce sont des problèmes difficiles, pour lesquels des solutions adaptées doivent être conçues pour les grands graphes. Nous proposons de travailler sur une version compressée du graphe. Nous montrons les bons résultats obtenus par notre méthode pour l'énumération de cliques maximales. Secondement, nous étudierons l'énumération de quasi-cliques maximales. Nous proposons un algorithme distribué qui énumère l'ensemble des quasi-cliques maximales. Nous proposons aussi une heuristique qui liste des quasi-cliques plus rapidement. Nous montrons l'intérêt de l'énumération de ces quasi-cliques par une évaluation des relations en regardant la co-occurrence des noeuds dans l'ensemble des quasi-cliques énumérées. Troisièmement, nous travaillerons sur la diffusion d'événements dans un graphe d'entités nommées. De nombreux modèles existent pour simuler des problèmes de diffusion de rumeurs ou de maladies dans des réseaux sociaux ou des problèmes de propagation de faillites dans les milieux bancaires. Nous proposons de répondre au problème de diffusion d'événements dans des réseaux hétérogènes représentant un environnement économique du monde. Nous proposons un problème de diffusion, nommé problème de classification de l'infection, qui consiste à déterminer quelles entités sont concernées par un événement. Pour ce problème, nous proposons deux modèles inspirés du modèle de seuil linéaire auxquels nous ajoutons différentes fonctionnalités. Finalement, nous testons et validons nos modèles sur un ensemble d'événements / In this thesis we will study graph problems. We will study theoretical problems in pattern research and applied problems in information diffusion. We propose two theoretical studies on the identification/detection and enumeration of dense subgraphs, such as cliques and quasi-cliques. Then we propose an applied study on the propagation of information in a named entities graph. First, we will study the identification/detection of cliques in compressed graphs. The MCE and MCP are problems that are encountered in the analysis of data graphs. These problem are difficult to solve (NP-Hard for MCE and NP-Complete for MCP), and adapted solutions must be found for large graphs. We propose to solve these problems by working on a compressed version of the initial graph. We show the correct results obtained by our method for the enumeration of maximal cliques on compressed graphs. Secondly, we will study the enumeration of maximal quasi-cliques. We propose a distributed algorithm that enumerates the set of maximal quasi-cliques of the graph. We show that this algorithm lists the set of maximal quasi-cliques of the graph. We also propose a heuristic that lists a set of quasi-cliques more quickly. We show the interest of enumerating these quasi-cliques by an evaluation of relations by looking at the co-occurrence of nodes in the set of enumerated quasi-cliques. Finally, we work on the event diffusion in a named entities graph. Many models exist to simulate diffusion problems of rumors or diseases in social networks and bankruptcies in banking networks. We address the issue of significant events diffusion in heterogeneous networks, representing a global economic environment. We propose a diffusion problem, called infection classification problem, which consists to dertemine which entities are concerned by an event. To solve this problem we propose two models inspired by the linear threshold model to which we add different features. Finally, we test and validate our models on a set of events

En basant l'analyse des modèles épidémiologiques sur leur représentation graphique plutôt que sur leurs équations différentielles, il est possible de mettre en évidence plusieurs concepts importants à l'aide des composantes d'un hypergraphe. On décrit une manière formelle de créer automatiquement un système d'équations différentielles à partir de ces composantes et on adapte ensuite la définition du produit cartésien pour les hypergraphes décrits, ce qui permet la fusion de modèles. À l'aide d'un algorithme qui ajoute automatiquement de nouvelles composantes à l'hypergraphe, il est possible d'isoler virtuellement certains individus, afin d'expliciter le calcul de nombres de reproduction. On montre ensuite que la forme des équations différentielles créées admettent une solution unique et que l'algorithme d'ajout aux hypergraphes est stable au niveau de la structure et de la dynamique des hypergraphes. On trouve que la méthode décrite pour le calcul des nombres de reproduction permet une meilleure prédiction de la croissance de l'épidémie que le calcul standard \(\mathcal{R}_t = \mathcal{R}_0 \cdot S / N\) et que le calcul de \(\mathcal{R}_0\) est très similaire aux résultats trouvés à l'aide de la matrice de prochaine génération, en plus d'être plus simple à mettre en place et d'offrir une justification plus robuste. On conclue ce mémoire en décrivant sommairement un processus d'apprentissage automatique des paramètres dans les modèles à compartiments, afin de permettre une calibration de modèles plus rapide. L'apprentissage machine peut être intégré en faisant appel à la librarie torchdiffeq, qui implémente les équations différentielles ordinaires neuronales en utilisant Pytorch. / By basing the analysis of epidemiological models on their graphical representation rather than on their differential equations, it is possible to highlight a few key concepts by using the components of a hypergraph. We give a formal way to automatically create a system of differential equations by using these components and we then adapt the definition of the cartesian product for the defined hypergraphs, which permits the merging of models. Using an algorithm which automatically adds new components to the graph, we can virtually isolate a few individuals to explicitly compute the reproduction numbers. We then show that the resulting differential equations allow for a unique solution and that the modification algorithm is stable for the structure and dynamics of the hypergraphs. We find that the described method for the computation of reproduction numbers gives a more accurate prediction of the growth of the epidemic than the standard computation \(\mathcal{R}_t = \mathcal{R}_0 \cdot S/N\) and that the computation of \(\mathcal{R}_0\) is very similar to the results found using the next generation matrix method, as well as being simpler to integrate into models and offering a more robust justification. We conclude this thesis with a brief outline of an automatic learning process for the parameters in compartmental models, which allows a faster calibration of epidemiological models. The implementation of machine learning can be done through the torchdiffeq library, which applies the theory of neural ordinary differential equations using Pytorch.

Tableau d'honneur de la Faculté des études supérieures et postdoctorales, 2006-2007 / Une solution de plus en plus courante pour appuyer les forces militaires déployées en milieu urbain consiste à utiliser des plates-formes robotisées pour la réalisation des tâches présentant un niveau de risque important. Dans cette optique, les travaux de recherche présentés dans ce mémoire ont permis de développer un système exploitant un capteur volumétrique 3D pour effectuer la modélisation d'environnements urbains et l'exploration efficace de ceux-ci à l'aide d'une plate-forme mobile autonome. Un aspect important de ce projet est que, le modèle 3D de l'environnement étant préservé sous forme d'octree multirésolution tout au long du processus, les modules de cartographie, d'exploration et de navigation qui composent la plate-forme mobile peuvent y avoir accès en tout temps afin d'effectuer leurs tâches respectives. À partir des résultats obtenus pour des tests effectués en simulation et dans un environnement réel, il a été possible de valider que le système développé permet d'explorer un environnement de façon autonome tout en générant de façon simultanée un modèle 3D complet de l'espace parcouru.

L’estimation des matrices origine-destination (OD) est un sujet de recherche important depuis les années 1950. En effet, ces tableaux à deux entrées recensent la demande de transport d'une zone géographique donnée et sont de ce fait un élément clé de l'ingénierie du trafic. Historiquement, les seules données disponibles pour leur estimation par les statistiques étaient les comptages de véhicules par les boucles magnétiques. Ce travail s'inscrit alors dans le contexte de l'installation à Brisbane de plus de 600 détecteurs Bluetooth qui ont la capacité de détecter et d'identifier les appareils électroniques équipés de cette technologie.Dans un premier temps, il explore la possibilité offerte par ces détecteurs pour les applications en ingénierie du transport en caractérisant ces données et leurs bruits. Ce projet aboutit, à l'issue de cette étude, à une méthode de reconstruction des trajectoires des véhicules équipés du Bluetooth à partir de ces seules données. Dans un second temps, en partant de l'hypothèse que l'accès à des échantillons importants de trajectoires va se démocratiser, cette thèse propose d'étendre la notion de matrice OD à celle de matrice OD par lien afin de combiner la description de la demande avec celle de l'utilisation du réseau. Reposant sur les derniers outils méthodologies développés en optimisation convexe, nous proposons une méthode d'estimation de ces matrices à partir des trajectoires inférées par Bluetooth et des comptages routiers.A partir de peu d'hypothèses, il est possible d'inférer ces nouvelles matrices pour l'ensemble des utilisateurs d'un réseau routier (indépendamment de leur équipement en nouvelles technologies). Ce travail se distingue ainsi des méthodes traditionnelles d'estimation qui reposaient sur des étapes successives et indépendantes d'inférence et de modélisation. / Origin Destination matrix estimation is a critical problem of the Transportation field since the fifties. OD matrix is a two-entry table taking census of the zone-to-zone traffic of a geographic area. This traffic description tools is therefore paramount for traffic engineering applications. Traditionally, the OD matrix estimation has solely been based on traffic counts collected by networks of magnetic loops. This thesis takes place in a context with over 600 Bluetooth detectors installed in the City of Brisbane. These detectors permit in-car Bluetooth device detection and thus vehicle identification.This manuscript explores first, the potentialities of Bluetooth detectors for Transport Engineering applications by characterising the data, their noises and biases. This leads to propose a new methodology for Bluetooth equipped vehicle trajectory reconstruction. In a second step, based on the idea that probe trajectories will become more and more available by means of new technologies, this thesis proposes to extend the concept of OD matrix to the one of link dependent origin destination matrix that describes simultaneously both the traffic demand and the usage of the network. The problem of LOD matrix estimation is formulated as a minimisation problem based on probe trajectories and traffic counts and is then solved thanks to the latest advances in nonsmooth convex optimisation.This thesis demonstrates that, with few hypothesis, it is possible to retrieve the LOD matrix for the whole set of users in a road network. It is thus different from traditional OD matrix estimation approaches that relied on successive steps of modelling and of statistical inferences.

Les circuits intégrés (CI) devenant de plus en plus complexes et vulnérables face aux décharges électrostatiques (ESD pour ElectroStatic Discharge), la capacité à vérifier de manière fiable la présence de défauts de conception ESD sur des puces comptant plusieurs milliards de transistors avant tout envoi en fabrication est devenu un enjeu majeur dans l’industrie des semi-conducteurs. Des outils commerciaux automatisés de dessin électronique (EDA pour Electronic Design Automation) et leur flot de vérification associé permettent d’effectuer différents types de contrôles qui se sont révélés être efficaces pour des circuits avec une architecture classique. Cependant, ils souffrent de limitations lorsqu’ils sont confrontés à des architectures inhabituelles, dites custom. De plus, ces méthodes de vérification sont généralement effectuées tard dans le flot de conception, rendant toute rectification de dessin coûteuse en termes d’efforts correctifs et de temps. Cette thèse de doctorat propose une méthodologie de vérification ESD systématique et multi-échelle introduite dans un outil appelé ESD IP Explorer qui a été spécifiquement implémenté pour couvrir le flot de conception dans sa globalité et pour adresser des circuits dits custom. Il est composé d’un module de reconnaissance et d’un module de vérification. Le module de reconnaissance identifie tout d’abord et de manière automatisée les structures de protection ESD, embarquées sur silicium dans le circuit intégré pour améliorer leur robustesse ESD, selon un mécanisme de reconnaissance topologique. Le module de vérification convertit ensuite le réseau de protection ESD, formé des structures de protection ESD, en un graphe dirigé. Finalement, une analyse ESD quasi-statique reposant sur des algorithmes génériques issus de la théorie des graphes est effectuée sur la globalité du circuit à vérifier. Des algorithmes d’apprentissage automatique ont été employés pour prédire les comportements quasi-statiques des protections ESD à partir des paramètres d’instance de leurs composants élémentaires sous la forme d’une liste d’interconnexions. L’avantage ici est qu’aucune simulation électrique n’est requise pendant toute la durée d’exécution d’ESD IP Explorer, ce qui simplifie l’architecture de l’outil et accélère l’analyse. Les efforts d’implémentation ont été concentrés sur la compatibilité d’ESD IP Explorer avec le nœud technologique 28nm FD-SOI (pour Fully Depleted Silicon On Insulator). L’outil de vérification développé a été utilisé avec succès pour l’analyse d’un circuit incorporant des parties numériques et à signaux mixtes et comprenant plus de 1,5 milliard de transistors en seulement quelques heures. Des circuits custom qui n’ont pas pu être vérifiés au moyen d’outils de vérification traditionnels du fait de problèmes d’incompatibilité ont également pu être soumis à analyse grâce à ESD IP Explorer. / As Integrated Circuits (ICs) become more complex and susceptible to ElectroStatic Discharges (ESD), the ability to reliably verify the presence of ESD design weaknesses over a multi-billion transistor chip prior to the tape-out is a major topic in the semiconductor industry. Commercial tools dedicated to Electronic Design Automation (EDA) and related verification flows are in charge of providing checks that have been proven to be efficient for circuits with a mainstream architecture. However, they suffer limitations when confronted with custom designs. Moreover, these verification methods are often run late in the design flow, making any design re-spin costly in terms of corrective efforts and time. This Ph. D. thesis proposes a systematic and scalable ESD verification methodology embodied in a tool called ESD IP Explorer that has been specifically implemented to cover the entire design flow and to comply with custom circuit architectures. It is composed of a recognition module and a verification module. The recognition module first automatically identifies ESD protection structures, embedded in integrated circuits to enhance their ESD hardness, according to a topology-aware recognition mechanism. The verification module then converts the ESD protection network that is formed by ESD protection structures into a directed graph. There, technology-independent and graph-based verification mechanisms perform a chip-scale quasistatic ESD analysis. Machine learning algorithms have been used in order to infer the quasistatic behavior of ESD IPs from the netlist instance parameters of their primary devices. This approach has the advantage that no simulation is required during the execution of ESD IP Explorer, which makes the tool architecture simpler and improves execution times. Implementation efforts pertained to the compliance of ESD IP Explorer with the 28nm Fully Depleted Silicon On Insulator (FD-SOI) technology node. The developed verification tool has been used to successfully analyze a digital and mixed-signal circuit prototype counting more than 1.5 billion transistors in several hours, as well as custom designs that could not be analyzed by means of traditional verification tools due to incompatibility issues.

Cette thèse, qui relève de la philosophie de l'esprit, consiste en la défense d'une version de la théorie auto-représentationnelle de la conscience. En acceptant d'une part la notion d'état mental possédant un certain contenu qui peut être conscient ou inconscient, et d'autre part l'hypothèse plausible que le contenu de tout état mental consiste en une représentation, alors le problème de la manifestation de la conscience s'appliquant au contenu de CERTAINS états mentaux acquiert intelligibilité dans ce cadre. Il peut être compris comme la recherche d'une structure de représentation qui donne lieu à cette manifestation. Pour certains auteurs (Fred Dretske, Michael Tye et dautres), des conditions particulières dans la représentation directe de l'objet y suffisent, pour d'autres (en particulier David Rosenthal) il y faut une méta-représentation de l'objet sous certaines conditions. Ni l'une ni l'autre de ces structures ne s'avère cependant suffisante pour justifier la démarcation entre états mentaux conscients et inconscients, et pour caractériser la phénoménalité de la conscience. En prenant alors au sérieux l'intuition forte d'auto-référentialité de la conscience (présente déjà chez Aristote - suivant certaines interprétations -, reprise par Brentano, Sartre, et ces dernières années, par Uriah Kriegel et plusieurs autres), on est conduit à proposer, pour les états mentaux conscients, une structure d'auto-représentation (de la représentation) de l'objet qui sous-tend une intentionnalité consciente duale dirigée vers l'objet et en même temps vers elle-même. on résout ainsi les problèmes de la théorie méta-représentationnelle, mais il faut monter que ce schéma est intelligible, que le risque de régression à l'infini dans les capacités repésentationnelles de la conscience n'existe pas, et que de robustes intuitions sont ainsi éclairées, telles que la structuration du champ conscient entre premier plan et arrière-plan, et le lien entre conscience d'arrière plan, ou marginale, et conscience de soi. Ce lien dérive du fait que la conscience marginale, dans la perspective de l'auto-représentation, est la conscience de la conscience d'objet, et se qualifie aussi comme conscience subjective, c'est à dire conscience "pour moi" de l'objet. Et la conscience de soi se construit à partir des épisodes de conscience subjective. L'étude du rapport entre structures de représentation mentale consciente et configurations neuronales spatio-temporelles qui les produisent dans le cerveau est hors du domaine du présent travail, mais la présence nécessaire de ces relations demeure à l'arrière-plan, et affleure dans la réflexion quand cela peut être éclairant. / This work illustrates a version of the self-representational theory of consciousness. If one accepts on the one hand the notion of mental states that have a given content - conscious or unconscious - and on the other hand the plausible hypothesis that the content of all mental states consists in a representation, then the problem of the manifestation of consciousness for (the content of) SOME states becomes intelligible within this frame. This problem can be understood as the research of the representational structure which gives rise to this manifestation. For some authors ( Fred Dretske, Michael Tye, and others) certain particular conditions in the direct representation of the object are sufficient, for others (particularly David Rosenthal) a meta-representation is necessary, under given conditions. However neither of those structures results sufficient to justify the demarcation between conscious and unconscious states and to characterize the phenomenality of consciousness. If one then takes seriously into account the strong intuition of self-referentiality of consciousness (already present in Aristotle - following some interpretations -, taken up again by Brentano, Sartre, and lately by Uriah Kriegel and several others) one is conducted to propose a self-representational structure for conscious mental states which involves a dual conscious intentionality targeting the object and itself at the same time. The problems of the meta-representational theory are thus resolved, but it remains to be shown that this scheme is intelligible, that the risk of infinite regress of the representing capacity of consciousness does not exist, and that strong intuitions are thus acknowledged : such as the distinction in the conscious field between foreground and background, and the link between background, or marginal consciousness, and self consciousness. Within the self-representational view, this link originates from the fact that marginal consciousness is the consciousness of the consciousness of the object, and qualifies itself as subjective consciousness, that is to say, consciousness "for me" of the object. Self consciousness is then constructed from the episodes of subjective consciousness. The relationship between conscious mental representational structures and the spatio-temporal neuronal configurations which produce them in the brain, is outside the domain of the present work, but it is necessarily present in the background, and it is considered when useful for the argument.

L'analyse régionale est une investigation délicate puisqu'une région est un ensemble hétéroclite et complexe d'invariants et de paramètres, visibles ou invisibles, mobiles ou inertes, en relation continue et interdépendante. Cerner toutes les composantes spatiales d'une région donnée est presque du domaine de l'impossible; seulement, il faut que les facteurs pris en considération soient essentiels et déterminants et permettent donc de mettre en relief les principaux écarts et décalages qui caractérisent une région quelconque.<br />C'est ainsi que l'objectif qui a déterminé la démarche de notre étude a été d'essayer de dépeindre la configuration spatiale antérieure et actuelle de l'Algérie à travers sa partie orientale qui est "l'Est Algérien". Pour tenter d'y parvenir, nous avons pris en considération trois types de maillages qui sont les territoires (wilayas et communes), le réseau urbain (toute taille confondue) et le réseau des voies de communication avec la trame routière et le réseau ferroviaire. Pour chaque type de réseau (territoires, réseau urbain et voies de communication), il a été à chaque fois nécessaire de présenter son évolution depuis presque l'antiquité, d'étudier sa configuration actuelle puis de la confronter avec des modèles théoriques en utilisant des outils d'analyse et d'investigation mis au point dans ce contexte.<br />Il ressort cependant que quel que soit le réseau ou le maillage pris en considération, l'Est Algérien s'est toujours montré comme un exemple typique d'un espace qui présente des formes opposées identifiables quelle que soit la méthode d'analyse utilisée. Il en résulte ainsi que la région, c'est à dire l'Est Algérien, est dominée par deux systèmes spatiaux dualistes :<br />+ un système classique traditionnel caractérisant les régions périphériques (partie occidentale du Tell, sud des Hautes Plaines ou la Steppe, les Nememcha, la région du Hodna et l'Atlas Saharien) qui accusent souvent des retards et des décalages négatifs dans tous les domaines;<br />+ un système spatial hérité légué principalement par le pouvoir colonial et qui se présente globalement comme une région polarisée linéairement le long des principales voies de communication en reliant les villes les plus importantes.<br />Il s'agit en fait du modèle de la région anisotropique qui se présente sous la forme d'une succession de sous-régions polarisées autour de grands centres urbains et bien connectés par les voies de communication suivant un axe préferentiel. De part et d'autre de ce premier système hérité subsistent des sous-systèmes spatiaux marginaux.

La compréhension des mécanismes cognitifs est un défi que les prouesses technologiques en imagerie par résonance magnétique fonctionnelle et de diffusion permettent de relever. Les réseaux neuronaux, ensembles de régions interconnectées anatomiquement et fonctionnellement, sont à l'ori- gine des processus cognitifs. Nous nous sommes intéressés à la relation entre la structure anatomique et la fonction de ces réseaux, au travers des deux principes fondamentaux du fonctionnement céré- bral que sont la ségrégation et l'intégration, ainsi que via la notion d'intégrité. En premier lieu, nous nous sommes penchés sur la ségrégation anatomique des noyaux gris centraux et son interprétation fonctionnelle. Puis, nous avons abordé le principe d'intégration, d'un point de vue descriptif par le biais de la théorie des graphes, puis explicatif par l'utilisation du modèle spatial autorégressif. Enfin, nous avons étudié l'intégrité structurelle du cerveau en présence de déficits neurocomportementaux suite à un traumatisme crânien léger. Nous avons ainsi mis en évidence l'existence d'un substrat ana- tomique sous-jacent aux réseaux fonctionnels. Nos résultats suggèrent que la structure anatomique des réseaux cérébraux est un substrat complexe optimisant les processus fonctionnels. De plus, une perte d'intégrité de ce substrat anatomique lors d'un traumatisme crânien léger se répercute sur le comportement et les performances cognitives. Ceci démontre que le fonctionnement cérébral, traduit par les réseaux neuronaux, est intimement lié à la structure anatomique de ces réseaux.

Cette dissertation se divise en deux parties, distinctes mais connexes, qui sont le reflet de la cotutelle. Nous étudions et résolvons des problèmes concernant d'une part la combinatoire des mots dans un contexte abélien et d'autre part des problèmes de couverture dans des graphes. Chaque question fait l'objet d'un chapitre. En combinatoire des mots, le premier problème considéré s'intéresse à la régularité des suites au sens défini par Allouche et Shallit. Nous montrons qu'une suite qui satisfait une certaine propriété de symétrie est 2-régulière. Ensuite, nous appliquons ce théorème pour montrer que les fonctions de complexité 2-abélienne du mot de Thue--Morse ainsi que du mot appelé ''period-doubling'' sont 2-régulières. Les calculs et arguments développés dans ces démonstrations s'inscrivent dans un schéma plus général que nous espérons pouvoir utiliser à nouveau pour prouver d'autres résultats de régularité. Le deuxième problème poursuit le développement de la notion de mot de retour abélien introduite par Puzynina et Zamboni. Nous obtenons une caractérisation des mots sturmiens avec un intercepte non nul en termes du cardinal (fini ou non) de l'ensemble des mots de retour abélien par rapport à tous les préfixes. Nous décrivons cet ensemble pour Fibonacci ainsi que pour Thue--Morse (bien que cela ne soit pas un mot sturmien). Nous étudions la relation existante entre la complexité abélienne et le cardinal de cet ensemble. En théorie des graphes, le premier problème considéré traite des codes identifiants dans les graphes. Ces codes ont été introduits par Karpovsky, Chakrabarty et Levitin pour modéliser un problème de détection de défaillance dans des réseaux multiprocesseurs. Le rapport entre la taille optimale d'un code identifiant et la taille optimale du relâchement fractionnaire d'un code identifiant est comprise entre 1 et 2 ln(|V|)+1 où V est l'ensemble des sommets du graphe. Nous nous concentrons sur les graphes sommet-transitifs, car nous pouvons y calculer précisément la solution fractionnaire. Nous exhibons des familles infinies, appelées quadrangles généralisés, de graphes sommet-transitifs pour lesquelles les solutions entière et fractionnaire sont de l'ordre |V|^k avec k dans {1/4, 1/3, 2/5}. Le second problème concerne les (r,a,b)-codes couvrants de la grille infinie déjà étudiés par Axenovich et Puzynina. Nous introduisons la notion de 2-coloriages constants de graphes pondérés et nous les étudions dans le cas de quatre cycles pondérés particuliers. Nous présentons une méthode permettant de lier ces 2-coloriages aux codes couvrants. Enfin, nous déterminons les valeurs exactes des constantes a et b de tout (r,a,b)-code couvrant de la grille infinie avec |a-b|>4. Il s'agit d'une extension d'un théorème d'Axenovich. / This dissertation is divided into two (distinct but connected) parts that reflect the joint PhD. We study and we solve several questions regarding on the one hand combinatorics on words in an abelian context and on the other hand covering problems in graphs. Each particular problem is the topic of a chapter. In combinatorics on words, the first problem considered focuses on the 2-regularity of sequences in the sense of Allouche and Shallit. We prove that a sequence satisfying a certain symmetry property is 2-regular. Then we apply this theorem to show that the 2-abelian complexity functions of the Thue--Morse word and the period-doubling word are 2-regular. The computation and arguments leading to these results fit into a quite general scheme that we hope can be used again to prove additional regularity results. The second question concerns the notion of return words up to abelian equivalence, introduced by Puzynina and Zamboni. We obtain a characterization of Sturmian words with non-zero intercept in terms of the finiteness of the set of abelian return words to all prefixes. We describe this set of abelian returns for the Fibonacci word but also for the Thue-Morse word (which is not Sturmian). We investigate the relationship existing between the abelian complexity and the finiteness of this set. In graph theory, the first problem considered deals with identifying codes in graphs. These codes were introduced by Karpovsky, Chakrabarty and Levitin to model fault-diagnosis in multiprocessor systems. The ratio between the optimal size of an identifying code and the optimal size of a fractional relaxation of an identifying code is between 1 and 2 ln(|V|)+1 where V is the vertex set of the graph. We focus on vertex-transitive graphs, since we can compute the exact fractional solution for them. We exhibit infinite families, called generalized quadrangles, of vertex-transitive graphs with integer and fractional identifying codes of order |V|^k with k in {1/4,1/3,2/5}. The second problem concerns (r,a,b)-covering codes of the infinite grid already studied by Axenovich and Puzynina. We introduce the notion of constant 2-labellings of weighted graphs and study them in four particular weighted cycles. We present a method to link these labellings with covering codes. Finally, we determine the precise values of the constants a and b of any (r,a,b)-covering code of the infinite grid with |a-b|>4. This is an extension of a theorem of Axenovich.

Dans le cadre de la Programmation par Contraintes, les contraintes globales ont amené une évolution majeure tant du point de vue modélisation (en synthétisant des ensembles de contraintes) que du point de vue résolution (grâce à des techniques de filtrage héritées d'autres domaines, comme la Recherche Opérationnelle ou l'Intelligence Artificielle). Par ailleurs, beaucoup de problèmes réels sont sur-contraints (ils ne possèdent pas de solution). Dans ce cas, il est nécessaire de relaxer certaines contraintes. De nombreuses études ont été menées pour traiter le cas des contraintes unaires et binaires, mais très peu pour le cas des contraintes globales. Dans cette thèse, nous étudions la relaxation des contraintes globales dans un cadre permettant l'expression de préférences. Pour plusieurs contraintes globales parmi les plus utilisées (c'est-à-dire AllDifferent, Gcc et Regular), nous proposons différentes sémantiques de violation ainsi que des algorithmes permettant de tester l'existence d'une solution et d'éliminer les valeurs incohérentes (filtrage). Les résultats de cette thèse ont été appliqués avec succès à des problèmes de création d'emplois du temps pour des infirmières, qui sont des problèmes sur-contraints difficiles à modéliser et surtout à résoudre. Mots-clefs : programmation par contraintes, contrainte globale, problème sur-contraints, relaxation de contraintes, contrainte globale relaxée, problème de création d'emplois du temps pour des infirmières.