Chacun d'entre nous s'est déjà essayé à un jeu combinatoire, tel que les dames ou les échecs. Les jeux les plus connus présentent le double avantage de mêler plaisir ludique et réflexion. L'intérêt que les mathématiciens leur porte réside souvent autour de la recherche d'une stratégie gagnante pour l'un des deux joueurs. Du jeu de Nim jusqu'aux échecs, la complexité de cette recherche est très variable. Dans cette thèse, nous donnons tout d'abord un aperçu des principales étapes du développement de ce domaine, qui a commencé au début des années 1900, et soulignons son étroite corrélation avec des domaines connexes tels que la théorie des nombres, des codes correcteurs d'erreur ou des graphes. Nous nous intéressons ensuite à des variantes de jeux bien connus : le Wythoff's game et le Dots and Boxes. Nous présentons et expliquons les stratégies et positions de jeu favorables au premier et au second joueur. Enfin, nous regardons une version solitaire d'un jeu récent à deux joueurs : le Clobber. Il s'agit d'un casse-tête qui se joue en posant des pierres sur les sommets d'un graphe, et dont le but est de détruire le plus de pierres possibles. Nous donnons des résultats structurels et algorithmiques sur les grilles, les arbres, ou encore les hypercubes.

Cette thèse s'inscrit dans l'étude de familles de graphes infinis de présentation finie, de leurs propriétés structurelles, ainsi que des comparaisons entre ces familles. Étant donné un alphabet fini Σ, un graphe infini étiqueté par Σ peut être caractérisé par un ensemble fini de relations binaires (Ra )a∈Σ sur un domaine dénombrable V quelconque. De multiples caractérisations finies de tels ensembles de relations existent, soit de façon explicite grâce à des systèmes de réécriture ou à divers formalismes de la théorie des automates, soit de façon implicite. Après un survol des principaux résultats existants, nous nous intéressons plus particulièrement à trois problèmes. Dans un premier temps, nous définissons trois familles de systèmes de réécriture de termes dont nous démontrons que la rela- tion de dérivation peut être représentée de façon finie. De ces résultats découlent plusieurs questions sur les familles de graphes infinis correspondantes. Dans un se- cond temps, nous étudions deux familles de graphes dont les ensembles de traces forment la famille des langages contextuels, à savoir les graphes rationnels et les graphes linéairement bornés. Nous nous intéressons en particulier au cas des langages contextuels déterministes, ainsi qu'à la comparaison structurelle de ces deux familles. Enfin, d'un point de vue plus proche du domaine de la vérifica- tion, nous proposons un algorithme de calcul des prédécesseurs pour une famille d'automates à pile d'ordre supérieur.

Soit un langage composé par tous les mots d'une longueur donnée $n$. Un cycle de de Bruijn d'ordre $n$ est un mot cyclique tel que tous les mots du langage apparaissent exactement une fois comme facteurs de ce cycle. Un algorithme pour construire le cycle de de Bruijn lexicographiquement minimal est dû à Fredricksen et Maiorana, il utilise les mots de Lyndon du langage. Cette thèse étudie comment généraliser le concept de cycles de de Bruijn pour un langage composé par un sous-ensemble de mots de longueur $n$, en particulier les langages de tous les mots de longueur $n$ sans facteurs dans une liste de facteurs interdits. Premièrement, nous étudions le cas des mots sans le facteur 11. Nous fournissons de nouvelles preuves de l'algorithme de Fredricksen et Maiorana qui nous permettent de prolonger ce resultat au cas des mots sans le facteur $1^i$ pour n'importe quel $i$. Nous caractérisons pour quels langages de mots de longueur $n$ existe un cycle de de Bruijn, et nous étudions également quelques propriétés de la dynamique symbolique de ces langages, en particulier des langages définis par des facteurs interdits. Pour ces genres de langages, nous présentons un algorithme pour produire un cycle de de Bruijn, en utilisant les mots de Lyndon du langage. Ces résultats utilisent la notion du graphe de de Bruijn et réduit le problème à construire un cycle eulérien dans ce graphe. Nous étudions le problème de la construction du cycle minimal dans un langage avec des facteurs interdits en employant le graphe de de Bruijn. Nous étudions deux algorithmes, un algorithme glouton simple et efficace qui fonctionne avec quelques familles de langages, et un algorithme plus complexe qui résout ce problème pour n'importe quel graphe eulérien.

La problèmatique dont nous nous occupons dans cette thèse est la classification automatique d'images bidimensionnelles, ainsi que la détection d'objets génériques dans des images. Les avancées de ce champ de recherche contribuent à l'élaboration de systèmes intelligents, tels que des robots autonomes et la création d'un web sémantique. Dans ce contexte, la conception de représentations d'images et de classificateurs appropriés constituent des problèmes ambitieux. Notre travail de recherche fournit des solutions à ces deux problèmes, que sont la représentation et la classification d'images. Afin de générer notre représentation d'image, nous extrayons des attributs visuels de l'image et construisons une structure de graphe basée sur les propriétés liées au relations de proximités entre les points d'intérêt associés. Nous montrons que certaines propriétés spectrales de ces graphes constituent de bons invariants aux classes de transformations géométriques rigides. Notre représentation d'image est basée sur ces propriétés. Les résultats expérimentaux démontrent que cette représentation constitue une amélioration par rapport à d'autres représentations similaires, mais qui n'intègrent pas les informations liées à l'organisation spatiale des points d'intérêt. Cependant, un inconvénient de cette méthode est qu'elle fait appel à une quantification (avec pertes) de l'espace des attributs visuels afin d'être combinée avec un classificateur Support Vecteur Machine (SVM) efficace. Nous résolvons ce problème en créant un nouveau classificateur, basé sur la distance au plus proche voisin, et qui permet la classification d'objets assimilés à des ensembles de points. La linéarité de ce classificateur nous permet également de faire de la détection d'objet, en plus de la classification d'images. Une autre propriété intéressante de ce classificateur est sa capacité à combiner différents types d'attributs visuels de manière optimale. Nous utilisons cette propriété pour formuler le problème de classification de graphes de manière différente. Les expériences, menées sur une grande variété de jeux de données, montrent les bénéfices quantitatifs de notre approche.

Nous étudions les décompositions arborescentes de graphes et les paramètres de largeur associés (largeur arborescente, largeur linéaire) sous plusieurs aspects. Nous proposons des algorithmes pour le calcul de la largeur arborescente des graphes ayant une quantité polynomiale de séparateurs minimaux et des algorithmes exacts et d'approximation dans le cas général. Nous abordons le problème de la largeur linéaire à travers une approche heuristique basée sur les complétions d'intervalles minimales, mais aussi avec des algorithmes polynomiaux pour certaines classes de graphes.

Dans cette thèse, nous nous intéressons à trois problèmes issus de l'informatique théorique, à savoir le placement de formes rectangulaires dans un conteneur (OPP), la coloration dite "forte" d'arêtes des graphes et les codes identifiants dans les graphes. L'OPP consiste à décider si un ensemble d'items rectangulaires peut être placé sans chevauchement dans un conteneur rectangulaire et sans dépassement des bords de celui-ci. Une contrainte supplémentaire est prise en compte, à savoir l'interdiction de rotation des items. Le problème est NP-difficile même dans le cas où le conteneur et les formes sont des carrés. Nous présentons un algorithme de résolution efficace basé sur une caractérisation du problème par des graphes d'intervalles, proposée par Fekete et Schepers. L'algorithme est exact et utilise les MPQ-arbres - structures de données qui encodent ces graphes de manière compacte tout en capturant leurs propriétés remarquables. Nous montrons les résultats expérimentaux de notre approche en les comparant aux performances d'autres algorithmes existants. L'étude de la coloration forte d'arêtes et des codes identifiants porte sur les aspects structurels et de calculabilité de ces deux problèmes. Dans le cas de la coloration forte d'arêtes nous nous intéressons plus particulièrement aux familles des graphes planaires et des graphes subcubiques. Nous montrons des bornes optimales pour l'indice chromatique fort des graphes subcubiques en fonction du degré moyen maximum et montrons que tout graphe planaire subcubique sans cycles induits de longueur 4 et 5 est coloriable avec neuf couleurs. Enfin nous confirmons la difficulté du problème de décision associé, en prouvant qu'il est NP-complet dans des sous-classes restreintes des graphes planaires subcubiques. La troisième partie de la thèse est consacrée aux codes identifiants. Nous proposons une caractérisation des graphes identifiables dont la cardinalité du code identifiant minimum est n − 1, où n est l'ordre du graphe. Nous étudions la classe des graphes adjoints et nous prouvons des bornes inférieures et supérieures serrées pour la cardinalité du code identifiant minimum dans cette classe. Finalement, nous montrons qu'il existe un algorithme linéaire de calcul de ce paramètre dans la classe des graphes adjoints L(G) où G a une largeur arborescente bornée par une constante. En revanche nous nous apercevons que le problème est NP-complet dans des sous-classes très restreintes des graphes parfaits.

Dans ce document, nous proposons un algorithme heuristique efficace pour résoudre le problème de partage spectral dynamique dans les réseaux de radios cognitives. Cet algorithme fonctionne selon les principes du paradigme de transmissions cognitives simultanées (en anglais underlay) où des utilisateurs primaires et des utilisateurs secondaires transmettent simultanément sur la même bande spectrale. L'algorithme proposé est basé sur un modèle théorique de graphe. Premièrement., le réseau de radios cognitives est modélisé en un graphe dont les sommets possèdent des poids. Le problème de partage spectral se réduit à colorier les sommets du graphe. Les décisions de partage spectral sont prises au niveau d'un serveur spectral qui coordonne les transmissions secondaires afin de trouver les paires (transmission secondaire/bande spectrale) qui maximisent le débit global du système. Le serveur spectral est aussi responsable de protéger les transmissions des utilisateurs primaires de l'interférence causée par les transmissions des utilisateurs secondaires. La réussite de cette tâche se base sur une allocation appropriée des puissances de transmission pour les utilisateurs secondaires. Grâce à des simulations bien élaborées, nous démontrons que les performances de l'algorithme proposé en terme de débit global sont proches de celles de l'algorithme optimal. Les performances de notre algorithme illustrent le gain en performances dû à une augmentation de la diversité de sélection de bande passante et à une diversité de sélection d'utilisateurs secondaires. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : algorithme de partage spectral, réseau de radios cognitives, théorie des graphes, systèmes de communication sans fil, simulation des réseaux.

Nous étudions les poids de graphes (c'est-à-dire, les invariants de graphes) qui apparaissent naturellement dans la théorie de Mayer et la théorie de Ree-Hoover pour le développement du viriel dans le contexte d'un gaz imparfait. Nous portons une attention particulière au deuxième poids ωM(C) de Mayer et au poids ωRH(C) de Ree-Hoover d'un graphe 2-connexe c dans le cas d'un gaz à noyaux durs et à positions continues en une dimension. Ces poids sont calculés à partir de volumes signés de polytopes convexes associés au graphe c en utilisant la méthode des homomorphismes de graphes, que nous avons aussi adaptée au cas du poids de Ree-Hoover, ainsi que les transformées de Fourier. En faisant appel à l'inversion de Möbius, nous présentons des relations entre les poids de Mayer et de Ree-Hoover. Ces relations nous permettent de donner une définition simple explicite du concept du "star content" introduit par Ree-Hoover et d'analyser certaines de ses propriétés fondamentales. Parmi nos résultats, nous donnons des tables contenant les valeurs du poids de Mayer et du poids de Ree-Hoover pour tous les graphes 2-connexes de taille au plus 8 ainsi que d'autres paramètres descriptifs. Nous développons aussi des formules explicites pour les poids de Mayer et de Ree-Hoover pour certaines familles de graphes 2-connexes simplement, doublement et triplement infinies, incluant par exemple, le poids de Mayer des graphes bipartis complets K m,n. En analysant les tables précédentes à l'aide du logiciel Maple, nous montrons que les poids de Mayer et de Ree-Hoover ne sont pas exprimables comme des fonctions faisant seulement appel à certains paramètres classiques de la théorie des graphes. Finalement, nous présentons une méthode générale pour le calcul du poids de Mayer d'un graphe connexe quelconque basée sur les arborescences couvrantes en utilisant les transformées de Fourier. Nous illustrons cette méthode sur des cas particuliers incluant les particules dures en dimension quelconque d. Cette méthode donne aussi lieu à un algorithme de calcul basé sur les différences divisées pour le cas des particules dures en dimension d = 1. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Poids de Mayer, Poids de Ree-Hoover, Mécanique statistique, Méthode des homomorphismes de graphes, Transformées de Fourier, Gaz imparfaits.

Reproduction de : Thèse de doctorat : Réseaux et télécommunications : Toulouse, INPT : 2005. / Titre provenant de l'écran-titre. Bibliogr. 81 réf.

Thèse doctorat : Informatique : Rennes 1 : 2005. / Bibliogr. p. 193-202.