Dans ce mémoire, nous analysons la description de diagrammes structurés dans le domaine des mathématiques discrètes et de l'informatique théorique. Cette analyse s'effectue à partir de méthodes établies du génie logiciel. Nous trouvons un ensemble de propriétés que nous recherchons dans une solution informatique nous permettant de créer ces diagrammes. Nous analysons aussi les outils classiques à partir des propriétés précédentes qui nous permettent de réaliser ces diagrammes dans un environnement LATEX. Nous observons que ces outils ne sont pas aussi puissants qu'ils le pourraient en fonction des propriétés établies par notre analyse. Par la suite, en nous basant sur les méthodes de représentation graphique des courbes et sur la théorie des langages informatiques, nous jetons les bases d'un langage de description. Nous présentons aussi un outil, développé en Java qui nous permet de décrire aisément nos diagrammes d'informatique théorique et de mathématiques discrètes à partir d'une hiérarchie d'objets claire et extensible. Nous avons implémenté les éléments essentiels de notre langage en SDDL (Structured Diagram Description Language). Nous l'avons aussi validé à l'aide d'exemples représentatifs tirés de sources d'autorité. Nous avons finalement présenté notre solution dans le cadre de la conférence TUG 2010. Nous l'avons aussi présenté avec un article dans la revue du TeX Users Groups, TUG. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : diagrammes, informatique théorique, mathématiques discrètes, langage

Les codes identifiants dans les graphes modélisent des systèmes de détection et de localisation à distance de pannes multiples dans les réseaux. Nous abordons dans une première partie différents problèmes de nature algorithmique ou structurelle concernant plusieurs variations autour de ces codes ; en particulier, nous obtenons de nombreux résultats quant à la structure des graphes sans jumeaux. Ces questions nous amènent dans une deuxième partie à considérer une notion de puissance de graphe, que nous étudions plus avant. Nous obtenons en particulier des résultats de type extrémal et nous consacrons l'étude des racines carrées de graphes.

Cette thèse présente différents aperçus de problèmes de mathématiques discrètes en lien avec la théorie des graphes. Elle s'intéresse en particulier à la coloration de graphes, i.e. l'assignation de couleurs aux sommets (ou arêtes) d'un graphes sous certaines contraintes locales, notamment l'exclusion de motifs. Pour différents types de coloration (choisissabilité des sommets, des arêtes, coloration acyclique ou linéaire, ...), un état de l'art est présenté, accompagné de résultats d'existence sur les graphes planaires ou leurs sous-classes, ayant pour but de minimiser le nombre de couleurs nécessaires pour un degré maximum ou un degré moyen maximum (Mad) donnés. Cette thèse traite également de décompositions induites de graphes, et démontre qu'il existe pour tout graphe $H$ une suite infinie de graphes denses dont les arêtes peuvent être partitionnées en copies induites de $H$. Cette preuve requiert le formalisme des hypergraphes, pour lesquels un autre résultat de décomposition est démontré, i.e. une décomposition optimale de l'hypergraphe complet 3-régulier en hypergraphes $\alpha$-acycliques. La troisième parti porte sur des questions algorithmiques. Elles consistent en problèmes d'optimisation ou d'existence, motivés par le routage d'information dans les réseaux, analysés par le formalisme classique de complexité algorithmique, ou traitent de la recherche de sous-graphes dans le formalisme de la complexité paramétrée. Dans une quatrième partie sont considérés des problèmes de comptage issus de la chimie, suivis de la présentation de Programmes Linéaires Entiers utilisés dans le logiciel de mathématiques Sage.

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.

Ce manuscrit d'Habilitation à diriger des recherches décrit mes travaux de recherche récents en théorie des graphes et en théorie des jeux combinatoires. Une première partie est consacrée à l'étude de paramètres de graphes en s'intéressant particulièrement aux contraintes structurelles qui permettent d'améliorer les bornes connues. Dans cette partie, nous traitons notamment la paire-domination, la domination indépendante mais aussi les partitions en cographes et les colorations quasi propres. Une deuxième partie traite de la domination de puissance, une forme itérative de la domination au sujet de laquelle nous proposons un début de synthèse des résultats existants. Enfin, une troisème partie parle de jeux. Nous y traitons d'abord le travail réalisé sur quelques conjectures portant sur un jeu de domino, puis au sujet des jeux en version misère. Nous y parlons enfin du jeu de domination, qui est à l'interface entre le paramètre de graphe et le jeu combinatoire.

Cette HDR présente mes travaux récents en combinatoire (énumérative et algébrique) autour du groupe symétrique, et répartis sur trois axes principaux : les co-quasi-invariants polynomiaux, les matrices à signes alternants et les tableaux boisés.

Dans cette thèse, nous explorons de nouvelles méthodes d'analyse d'images pour la détection précoce des changements métaboliques cérébraux causés par la maladie d'Alzheimer (MA). Nous introduisons deux apports méthodologiques que nous appliquons à un ensemble de données réelles. Le premier est basé sur l'apprentissage automatique pour créer une carte des informations de classification pertinente dans un ensemble d'images. Pour cela nous échantillonnons des blocs de voxels de l'image selon un algorithme de Monte-Carlo. La mise en oeuvre d'une classification basée sur ces patchs 3D a pour conséquence importante la réduction significative du volume de patchs à traiter, et l'extraction de caractéristiques dont l'importance est statistiquement quantifiable. Cette méthode s'applique à différentes caractéristiques de l'image et donc est adaptée à des types d'images très variés. La résolution des cartes produites par cette méthode peut être affinée à volonté et leur contenu informatif est cohérent avec les résultats antérieurs basés sur les statistiques sur les voxels obtenus dans la littérature. Le second apport méthodologique porte sur la conception d'un nouvel algorithme de décomposition de tenseur d'ordre important, adapté à notre application. Cet algorithme permet de réduire considérablement la consommation de mémoire et donc évite la surcharge de la mémoire. Il autorise la décomposition rapide de tenseurs, y compris ceux de dimensions très déséquilibrées. Nous appliquons cet algorithme en tant que méthode d'extraction de caractéristiques dans une situation où le clinicien doit diagnostiquer des stades MA précoce ou MCI (Mild Cognitive Impairment) en utilisant la TEP FDG seule. Les taux de classification obtenus sont souvent au-dessus des niveaux de l'état de l'art. Dans le cadre de ces tâches d'analyse d'images, nous présentons notre source de données, les scans de patients retenus et les pré-traitements réalisés. Les principaux aspects que nous voulons prendre en compte sont la nature volumétrique des données, l'information a priori disponible sur la localisation des changements métaboliques et comment l'identification des zones de changements métaboliques participe à la réduction de la quantité de données à analyser et d'extraire des caractéristiques discriminantes. Les méthodes présentées fournissent des informations précises sur la localisation de ces changements métaboliques. Les taux de classification allant jusqu'à 92,6% pour MA et 83,8% pour MCI. En outre, nous sommes capables de séparer les patients MCI stables des MCI patients évoluant vers la MA dans les 2 ans après l'acquisition du PET-scan avec un taux de classification de 84.7%. Ce sont des étapes importantes vers une détection fiable et précoce de la MA.

Cette these presente les techniques d'optimisation combinatoire et de programmation entiere transversales a nos differents projets de recherche.

Le but de cette thèse est d'établir des résultats énumératifs sur certaines classes de chemins et d'animaux. Ces résultats sont obtenus en appliquant la théorie des empilements de pièces développée par Viennot. Nous étudions les excursions discrètes (ou chemins de Dyck généralisés) de hauteur bornée; nous obtenons des interprétations combinatoires et des extensions de résultats de Banderier, Flajolet et Bousquet-Mélou. Nous décrivons et énumérons plusieurs classes de chemins auto-évitants, dits chemins faiblement dirigés. Ces chemins sont plus nombreux que les chemins prudents qui forment la classe naturelle la plus grande jusqu'alors. Nous calculons le périmètre de site moyen des animaux dirigés, prouvant des conjectures de Conway et Le Borgne. Enfin, nous obtenons des résultats nouveaux sur l'énumération des animaux de Klarner et les animaux multi-dirigés de Bousquet-Mélou et Rechnitzer.

Les modèles géométriques de calcul permettent d'effectuer des calculs à l'aide de primitives géométriques. Parmi eux, le modèle des machines à signaux se distingue par sa simplicité, ainsi que par sa puissance à réaliser efficacement de nombreux calculs. Nous nous proposons ici d'illustrer et de démontrer cette aptitude, en particulier dans le cas de processus massivement parallèles. Nous montrons d'abord à travers l'étude de fractales que les machines à signaux sont capables d'une utilisation massive et parallèle de l'espace. Une méthode de programmation géométrique modulaire est ensuite proposée pour construire des machines à partir de composants géométriques de base -- les modules -- munis de certaines fonctionnalités. Cette méthode est particulièrement adaptée pour la conception de calculs géométriques parallèles. Enfin, l'application de cette méthode et l'utilisation de certaines des structures fractales résultent en une résolution géométrique de problèmes difficiles comme les problèmes de satisfaisabilité booléenne SAT et Q-SAT. Ceux-ci, ainsi que plusieurs de leurs variantes, sont résolus par machines à signaux avec une complexité en temps intrinsèque au modèle, appelée profondeur de collisions, qui est polynomiale, illustrant ainsi l'efficacité et le pouvoir de calcul parallèle des machines à signaux.