The thesis applies the ICC tecniques to the probabilistic polinomial complexity classes in order to get an implicit characterization of them. The main contribution lays on the implicit characterization of PP (which stands for Probabilistic Polynomial Time) class, showing a syntactical characterisation of PP and a static complexity analyser able to recognise if an imperative program computes in Probabilistic Polynomial Time. The thesis is divided in two parts. The first part focuses on solving the problem by creating a prototype of functional language (a probabilistic variation of lambda calculus with bounded recursion) that is sound and complete respect to Probabilistic Prolynomial Time. The second part, instead, reverses the problem and develops a feasible way to verify if a program, written with a prototype of imperative programming language, is running in Probabilistic polynomial time or not. This thesis would characterise itself as one of the first step for Implicit Computational Complexity over probabilistic classes. There are still open hard problem to investigate and try to solve. There are a lot of theoretical aspects strongly connected with these topics and I expect that in the future there will be wide attention to ICC and probabilistic classes.

L'étude que nous proposons s'inscrit dans le cadre de la complexité implicite des calculs. Selon Daniel Leivant, il s'agit de donner des caractérisations de la complexité sans faire de référence explicite à un modèle de calcul. Nous montrons que les interprétations de programmes sont un bon outil d'analyse dans ce contexte. Les aspects théoriques et pratiques sont abordés.

Cette thèse porte sur l'étude des propriétés structurelles de graphes dont la compréhension permet de concevoir des algorithmes efficaces pour résoudre des problèmes d'optimisation. Nous nous intéressons plus particulièrement aux méthodes de décomposition des graphes, aux jeux de poursuites et à la notion de convexité. Le jeu de Processus a été défini comme un modèle de la reconfiguration de routage. Souvent, ces jeux où une équipe de chercheurs doit effacer un graphe non orienté sont reliés aux décompositions de graphes. Dans les digraphes, nous montrons que le jeu de Processus est monotone et nous définissons une nouvelle décomposition de graphes que lui est équivalente. Ensuite, nous étudions d'autres décompositions de graphes. Nous proposons un algorithme FPT-unifiée pour calculer plusieurs paramètres de largeur de graphes. En particulier, ceci est le premier FPT-algorithme pour la largeur arborescente q-branché et spéciale d'un graphe. Nous étudions ensuite un autre jeu qui modélise les problèmes de pré-chargement. Nous introduisons la variante en ligne du jeu de surveillance. Nous étudions l'écart entre le jeu de surveillance classique et ses versions connecté et en ligne, en fournissant de nouvelles bornes. Nous définissons ensuite un cadre général pour l'étude des jeux poursuite-évasion. Cette méthode nous permet de donner les premiers résultats d'approximation pour certains de ces jeux. Finalement, nous étudions un autre paramètre lié à la convexité des graphes et à la propagation d'infection dans les réseaux, le nombre enveloppe. Nous fournissons plusieurs résultats de complexité en fonction des structures des graphes et en utilisant des décompositions de graphes.

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.

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é.

Les automates cellulaires ont été introduits il y a une soixantaine d'années par von Neumann et Ulam qui cherchaient à définir les caractéristiques d'un système formel apte au calcul universel et à l'auto-reproduction. Leur utilité a été rapidement reconnue dans des domaines variés comme la physique et la biologie, pour modéliser des phénomènes complexes. En informatique, ils offrent un cadre privilégié pour l'étude du parallélisme massif. Leur description est simple et bien formalisée. Ils ont a la même puissance de calcul que les machines de Turing et de plus la richesse algorithmique propre aux machines parallèles tout en restant un modèle physiquement réaliste. Dans le cadre unificateur de la reconnaissance de langages, je m'intéresse aux questions de complexité sur les automates cellulaires, avec une attention particulière aux petites classes de complexité : calcul en temps réel (i.e. temps minimal) et en temps linéaire; en effet, c'est pour ces classes que l'apport du parallélisme est remarquable par rapport au mode séquentiel. Avec pour objectif de préciser les capacités de ce modèle et de mieux comprendre ce qu'est un calcul parallèle, trois tendances majeures se dégagent de mes travaux : l'étude des limites de ce modèle, la comparaison avec d'autres modèles de calcul et la question de l'influence de certains paramètres comme la dimension ou le voisinage sur ses capacités de reconnaissance.

La comparaison de réseaux biologiques est actuellement l'une des approches les plus prometteuses pour aider à la compréhension du fonctionnement des organismes vivants. Elle apparaît comme la suite attendue de la comparaison de séquences biologiques dont l'étude ne représente en réalité que l'aspect génomique des informations manipulées par les biologistes. Dans cette thèse, nous proposons une approche innovante permettant de comparer deux réseaux biologiques modélisés respectivement par un graphe orienté D et un graphe non-orienté G, et dotés d'une fonction f établissant la correspondance entre les sommets des deux graphes. L'approche consiste à extraire automatiquement une structure dans D, biologiquement significative, dont les sommets induisent dans G, par f, une structure qui soit aussi biologiquement significative. Nous réalisons une étude algorithmique du problème issu de notre approche en commençant par sa version dans laquelle D est acyclique (DAG). Nous proposons des algorithmes polynomiaux pour certains cas, et nous montrons que d'autres cas sont algorithmiquement difficiles (NP-complets). Pour résoudre les instances difficiles, nous proposons une bonne heuristique et un algorithme exact basé sur la méthode branch-and-bound. Pour traiter le cas où D est cyclique, nous introduisons une méthode motivée par des hypothèses biologiques et consistant à décomposer D en DAGs tels que les sommets de chaque DAG induisent dans G un sous-graphe connexe. Nous étudions également dans cette thèse, l'inférence des voies de signalisation en combinant les informations sur les causes et sur les effets des événements extra-cellulaires. Nous modélisons ce problème par un problème d'orientation de graphes mixtes et nous effectuons une étude de complexité permettant d'identifier les instances faciles et celles difficiles.