Nous étudions des aspects combinatoires et algorithmiques relatifs aux codes identifiants dans les graphes. Un code identifiant est un ensemble de sommets d'un graphe tel que, d'une part, chaque sommet hors du code a un voisin dans le code et, d'autre part, tous les sommets ont un voisinage distinct à l'intérieur du code. Nous caractérisons tout d'abord les graphes orientés et non-orientés atteignant les bornes supérieures connues pour la taille minimum d'un code identifiant. Nous donnons également de nouveaux majorants et minorants sur ce paramètre pour les graphes de degré maximum donné, les graphes de maille au moins 5, les graphes d'intervalles et les graphes adjoints. Nous étudions ensuite la complexité algorithmique des problèmes de décision et d'optimisation associés à la notion de code identifiant. Nous montrons que ces problèmes restent algorithmiquement difficiles, même quand on les restreint aux graphes bipartis, co-bipartis, split, d'intervalles ou adjoints. Enfin, nous donnons un algorithme PTAS pour les graphes d'intervalles unitaires.

Deux défis de la théorie du codage algébrique sont traités dans cette thèse. Le premier est le décodage efficace (dur et souple) de codes de Reed--Solomon généralisés sur les corps finis en métrique de Hamming. La motivation pour résoudre ce problème vieux de plus de 50 ans a été renouvelée par la découverte par Guruswami et Sudan à la fin du 20ème siècle d'un algorithme polynomial de décodage jusqu'au rayon Johnson basé sur l'interpolation. Les premières méthodes de décodage algébrique des codes de Reed--Solomon généralisés faisaient appel à une équation clé, c'est à dire, une description polynomiale du problème de décodage. La reformulation de l'approche à base d'interpolation en termes d'équations clés est un thème central de cette thèse. Cette contribution couvre plusieurs aspects des équations clés pour le décodage dur ainsi que pour la variante décodage souple de l'algorithme de Guruswami--Sudan pour les codes de Reed--Solomon généralisés. Pour toutes ces variantes un algorithme de décodage efficace est proposé. Le deuxième sujet de cette thèse est la formulation et le décodage jusqu'à certaines bornes inférieures sur leur distance minimale de codes en blocs linéaires cycliques. La caractéristique principale est l'intégration d'un code cyclique donné dans un code cyclique produit (généralisé). Nous donnons donc une description détaillée du code produit cyclique et des codes cycliques produits généralisés. Nous prouvons plusieurs bornes inférieures sur la distance minimale de codes cycliques linéaires qui permettent d'améliorer ou de généraliser des bornes connues. De plus, nous donnons des algorithmes de décodage d'erreurs/d'effacements [jusqu'à ces bornes] en temps quadratique.

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.

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.

Un très grand nombre de problèmes combinatoires appartient à la famille des problèmes de satisfaction de contraintes (Constraint Satisfaction Problem ou CSP) : configuration, ordonnancement, affectation de ressources... Ces problèmes partagent une description commune qui autorise en général une modélisation claire et intuitive. Dans cette thèse, nous avons proposé et étudié une nouvelle méthode de résolution hybride pour les CSPs. Nous avons nommé cette méthode Tabu-NG pour Tabu Search based on NoGood. Le nom est un peu réducteur car il s'agit d'une hybridation d'algorithme de filtrage, de propagation de contraintes, de Recherche Tabou et de gestion de nogoods. La méthode a été appliquée sur deux types de problèmes. Le premier est l'affectation des fréquences (FAP) dans les réseaux de radiocommunications militaires, en particulier les problèmes proposés de 1993 (instances du projet européen CALMA) jusqu'à 2010 (instances d'un projet DGA). Le deuxième est le problème académique de k-coloration de graphes sur les instances DIMACS. La méthode a amélioré quelques meilleurs scores connus actuellement. Dans les deux problèmes nous avons traité des contraintes unaires et binaires, ainsi que des contraintes n-aires et de l'optimisation de fonction sous contraintes pour le FAP. Les principes de Tabu-NG sont généraux et elle peut s'appliquer sur d'autres CSP. Elle peut par ailleurs accueillir des heuristiques spécifiques aux problèmes, nous l'avons pratiqué sur les problèmes cités, et en ce sens nous pensons pouvoir qualifier la méthode de métaheuristique sans abuser de cette définition.

Les questions <EM>"Qu'est-ce qu'une preuve?"</EM> et <EM>"Quand deux preuves sont-elles identiques?"</EM> sont fondamentales pour la théorie de la preuve. Mais pour la logique classique propositionnelle --- la logique la plus répandue --- nous n'avons pas encore de réponse satisfaisante. C'est embarrassant non seulement pour la théorie de la preuve, mais aussi pour l'informatique, où la logique classique joue un rôle majeur dans le raisonnement automatique et dans la programmation logique. De même, l'architecture des processeurs est fondée sur la logique classique. Tous les domaines dans lesquels la recherche de preuve est employée peuvent bénéficier d'une meilleure compréhension de la notion de preuve en logique classique, et le célèbre problème NP-vs-coNP peut être réduit à la question de savoir s'il existe une preuve courte (c'est-à-dire, de taille polynomiale) pour chaque tautologie booléenne. Normalement, les preuves sont étudiées comme des objets syntaxiques au sein de systèmes déductifs (par exemple, les tableaux, le calcul des séquents, la résolution, ...). Ici, nous prenons le point de vue que ces objets syntaxiques (également connus sous le nom d'arbres de preuve) doivent être considérés comme des représentations concrètes des objets abstraits que sont les preuves, et qu'un tel objet abstrait peut être représenté par un arbre en résolution ou dans le calcul des séquents. Le thème principal de ce travail est d'améliorer notre compréhension des objets abstraits que sont les preuves, et cela se fera sous trois angles différents, étudiés dans les trois parties de ce mémoire: l'algèbre abstraite (chapitre 2), la combinatoire (chapitres 3 et 4), et la complexité (chapitre 5).

Organiser le secteur du transport pour offrir des solutions de déplacement efficaces est aujourd'hui un enjeu capital pour nos sociétés. La flexibilité, tendant à augmenter la qualité de service, constitue un des leviers pour améliorer les transports. Diverses formes de flexibilité apparaissent en effet dans l'offre actuelle. Dans cette thèse, nous appréhendons plus particulièrement des services opérant dans deux contextes sociétaux distincts :* d'une part, dans un pays industrialisé (la France) où le recours aux transports publics reste minoritaire car la dépendance à l'automobile est toujours très forte ;* d'autre part, dans un pays en voie de développement (le Sénégal) possédant des moyens financiers limités, mais où l'usage des transports collectifs est généralisé, impliquant une grande diversité des modes et une atomisation de l'offre.Nous proposons ainsi d'analyser et de comparer le fonctionnement des transports informels et artisanaux sénégalais (tels que les taxis collectifs) avec celui des systèmes considérés comme plus modernes en France, pour lesquels les capacités d'auto-organisation des individus ont été progressivement remplacées par des systèmes d'information et de communication de haut niveau technologique et logistique. Ces innovations semblent apporter plus d'immédiateté au transport flexible, mais nécessitent en contrepartie un encadrement fort de la part des autorités publiques générant des contraintes réglementaires et spatiales. À l'opposé, les services spontanés et dérégulés qui sont proposés au Sénégal bénéficient d'une plus grande souplesse, au détriment de la sécurité des passagers.L'objectif de la thèse est d'analyser ces services, les modéliser et les simuler afin d'évaluer les apports de la flexibilité. D'un point de vue méthodologique, notre recherche est basée sur un ensemble de modèles inspirés des transports observés en France et au Sénégal, puis implémentés en Systèmes Multi-Agents (SMA) dans l'environnement Netlogo. Certains modèles sont issus d'une analyse fonctionnelle de terrain et d'autres sont plus théoriques. Par l'analyse du comportement d'agents réalisant ces services en concurrence et/ou en coopération, nous identifions d'abord des seuils et des conditions de mise en œuvre en termes d'efficacité et de couverture spatiale. En simulant les modèles sur plusieurs configurations spatiales, nous explorons ensuite leur fonctionnement et nous analysons les atouts et les faiblesse de chacun. Nous les simulons ensuite simultanément pour évaluer leur capacité de complémentarité. Cela nous permet in fine de confronter des systèmes de transports analogues à ceux observés dans les deux contextes sociétaux et d'établir une grille de comparaison en fonction des niveaux de flexibilité identifiés..

Cette thèse traite de certains aspects particuliers de la résolution des systèmes algébriques. Dans un premier temps, nous présentons une façon de minimiser le nombres de variables additives apparaissant dans un système algébrique. Nous utilisons pour cela deux invariants de variété introduits par Hironaka : le faîte et la directrice. Dans un second temps, nous proposons une arithmétique rapide, dite détendue, pour les entiers p-adiques. Cette arithmétique nous permet ensuite de résoudre efficacement un système algébrique à coefficients rationnels localement, c'est-à-dire sur les entiers p-adiques. En quatrième partie, nous nous intéressons à la factorisation d'un polynôme à deux variables qui est une brique élémentaire pour la décomposition en composantes irréductibles des hypersurfaces. Nous proposons un algorithme réduisant la factorisation du polynôme donné en entrée à celle d'un polynôme dont la taille dense est essentiellement équivalente à la taille convexe-dense de celui donné en entrée. Dans la dernière partie, nous considérons la résolution en moyenne des systèmes algébriques réels. Nous proposons un algorithme probabiliste calculant un zéro approché complexe du système algébrique réel donné en entrée.

Cette thèse traite de certains aspects particuliers de la résolution des systèmes algébriques. Dans un premier temps, nous présentons une façon de minimiser le nombres de variables additives apparaissant dans un système algébrique. Nous utilisons pour cela deux invariants de variété introduits par Hironaka : le faîte et la directrice. Dans un second temps, nous proposons une arithmétique rapide, dite détendue, pour les entiers p-adiques. Cette arithmétique nous permet ensuite de résoudre efficacement un système algébrique à coefficients rationnels localement, c'est-à-dire sur les entiers p-adiques. En quatrième partie, nous nous intéressons à la factorisation d'un polynôme à deux variables qui est une brique élémentaire pour la décomposition en composantes irréductibles des hypersurfaces. Nous proposons un algorithme réduisant la factorisation du polynôme donné en entrée à celle d'un polynôme dont la taille dense est essentiellement équivalente à la taille convexe-dense de celui donné en entrée. Dans la dernière partie, nous considérons la résolution en moyenne des systèmes algébriques réels. Nous proposons un algorithme probabiliste calculant un zéro approché complexe du système algébrique réel donné en entrée.

Les décompositions de graphes, lorsqu'elles sont de petite largeur, sont souvent utilisées pour résoudre plus efficacement des problèmes étant difficiles dans le cas de graphes quelconques. Dans ce travail de thèse, nous nous intéressons aux limites liées à ces décompositions, et à la construction d'obstructions certifiant leur grande largeur. Dans une première partie, nous donnons un algorithme généralisant et unifiant la construction d'obstructions pour différentes largeurs de graphes, en temps XP lorsque paramétré par la largeur considérée. Nous obtenons en particulier le premier algorithme permettant de construire efficacement une obstruction à la largeur arborescente en temps O^{tw+4}. La seconde partie de notre travail porte sur l'étude du problème Ensemble [Sigma,Rho]-Dominant, une généralisation des problèmes de domination sur les graphes et caractérisée par deux ensembles d'entiers Sigma et Rho. Les diverses études de ce problème apparaissant dans la littérature concernent uniquement les cas où le problème est FPT, lorsque paramétré par la largeur arborescente. Nous montrons que ce problème ne l'est pas toujours, et que pour certains cas d'ensembles Sigma et Rho, il devient W[1]-difficile lorsque paramétré par la largeur arborescente. Dans la dernière partie, nous étudions la complexité d'un nouveau problème de coloration appelé k-Coloration Additive, combinant théorie des graphes et théorie des nombres. Nous montrons que ce nouveau problème est NP-complet pour tout k >= 4 fixé, tandis qu'il peut être résolu en temps polynomial sur les arbres pour k quelconque et non fixé.