Le Web caché (également appelé Web profond ou Web invisible), c'est-à-dire la partie du Web qui n'est pas directement accessible par des hyperliens, mais à travers des formulaires HTML ou des services Web, est d'une grande valeur, mais difficile à exploiter. Nous présentons un processus pour la découverte, l'analyse syntaxique et sémantique, et l'interrogation des services du Web caché, le tout de manière entièrement automatique. Nous proposons une architecture générale se basant sur un entrepôt semi-structuré de contenu imprécis (probabiliste). Nous fournissons une analyse détaillée de la complexité du modèle d'arbre probabiliste sous-jacent. Nous décrivons comment une combinaison d'heuristiques et de sondages du Web peut être utilisée pour comprendre la structure d'un formulaire HTML. Nous présentons une utilisation originale des champs aléatoires conditionnels (une méthode d'apprentissage supervisé) de manière non supervisée, sur une annotation automatique, imparfaite et imprécise, basée sur la connaissance du domaine, afin d'extraire l'information pertinente de pages de résultat HTML. Afin d'obtenir des relations sémantiques entre entrées et sorties d'un service du Web caché, nous étudions la complexité de l'obtention d'une correspondance de schémas à partir d'instances de bases de données, en se basant uniquement sur la présence des constantes dans ces deux instances. Nous décrivons enfin un modèle de représentation sémantique et d'indexation en compréhension de sources du Web caché, et débattons de la manière de traiter des requêtes de haut niveau à l'aide de telles descriptions.

Avec le développement des réseaux de communications comme Internet, le besoin d'assurer la sécurité des échanges a considérablement augmenté. Les communications " sécurisées " sont réalisées par l'utilisation de petits programmes appelés protocoles cryptographiques qui peuvent être attaqués même en présence d'un chiffrement parfait. De telles failles, qualifiées de " failles logiques ", sont souvent subtiles et difficiles à déceler à la simple vue du texte du protocole. Dans cette thèse, nous poussons les limites de l'analyse des protocoles au delà de cette hypothèse. En particulier, nous proposons des procédures de décision, pour le problème de la recherche d'attaques en présence d'opérateurs satisfaisant des propriétés algébriques.

Les systèmes dynamiques continus permettent de modéliser de nombreux<br />systèmes physiques, biologiques, ou issus de l'informatique<br />distribuée. Nous nous intéressons à leur pouvoir de modélisation, et à<br />leurs propriétés en tant que systèmes de calculs, et plus généralement<br />aux propriétés calculatoires des modèles continus.<br /><br />Les deux premiers chapitres ne visent pas à produire des résultats<br />nouveaux, mais à motiver ce travail, et à le mettre en<br />perspectives. Le chapitre 3 constitue un survol. Les chapitres 4, 5 et<br />l'annexe A présentent un panorama de quelques-uns de nos résultats<br />personnels en relations avec cette problématique.<br /><br />Plus précisément, le chapitre 1 présente les systèmes dynamiques, avec<br />un point de vue classique et mathématique. Il vise d'une part à<br />souligner la richesse, et la subtilité des comportements possibles des<br />systèmes dynamiques continus, et d'autre part à mettre en évidence que<br />différents dispositifs sont intrinsèquement continus, et utilisables<br />comme tels pour réaliser des calculs. En outre nous insistons sur la<br />puissance de modélisation d'une classe de systèmes dynamiques, que<br />nous nommons les problèmes de Cauchy polynomiaux.<br /><br />Les exemples du chapitre 2, issus de la bioinformatique, des modèles<br />de la biologie des populations, de la virologie biologique et de la<br />virologie informatique, et de l'algorithmique distribuée, se<br />distinguent de ceux du chapitre 1 par le fait qu'ils mettent<br />explicitement en jeu une certaine notion de concurrence entre agents.<br />Nous présentons la théorie des jeux, et ses modèles, en nous<br />focalisant sur certains de ses modèles du dynamisme. Ces modèles<br />continus deviennent naturels pour parler d'algorithmique distribuée,<br />en particulier dès que l'on a affaire à des systèmes de grandes<br />tailles, ou dont on ne contrôle pas les interactions. Nous pointons<br />quelques modèles de l'algorithmique distribuée qui intègrent ces<br />considérations, et le potentiel de l'utilisation des systèmes continus<br />pour l'algorithmique distribuée.<br /><br />Le chapitre 3 constitue un survol de la théorie des calculs pour les<br />modèles à temps continu. La puissance des modèles de calculs à temps<br />et espace discrets est relativement bien comprise grâce à la thèse de<br />Church, qui postule que tous les modèles raisonnables et suffisamment<br />puissants ont la même puissance, celle des machines de Turing. On peut<br />aussi considérer des modèles où le temps est continu. Certaines<br />grandes classes de modèles ont été considérées dans la<br />littérature. Nous les reprenons dans ce chapitre, en présentant un<br />panorama de ce qui est connu sur leurs propriétés calculatoires.<br /><br />Le chapitre 4 présente un résumé de quelques-uns de nos résultats<br />personnels à propos de la comparaison de la puissance de plusieurs<br />modèles à temps continu, en relations avec la thèse de Emmanuel<br />Hainry. Claude Shannon a introduit en 1941 le GPAC comme un modèle des<br />dispositifs de calculs analogiques. Les résultats de Shannon ont<br />longtemps été utilisés pour argumenter que ce modèle était plus faible<br />que l'analyse récursive, et donc que les machines analogiques sont<br />prouvablement plus faibles que les machines digitales. Avec Manuel<br />Campagnolo, Daniel Graça, et Emmanuel Hainry, nous avons prouvé<br />récemment que le GPAC et l'analyse récursive calculent en fait les<br />mêmes fonctions. Ce résultat prend toute sa perspective si l'on<br />comprend que les fonctions calculées par le GPAC correspondent aux<br />problèmes de Cauchy polynomiaux, dont le pouvoir de modélisation est<br />discuté dans le chapitre 1.<br /><br />D'autre part, nous avons montré qu'il était possible de caractériser<br />algébriquement les fonctions élémentairement calculables et<br />calculables au sens de l'analyse récursive. Cela signifie d'une part<br />qu'il est possible de les caractériser en termes d'une sous-classe des<br />fonctions R-récursives à la Moore, ce qui étend les résultats de<br />Campagnolo, Costa, Moore, de la calculabilité discrète à l'analyse<br />récursive, mais aussi d'autre part, qu'il est possible de caractériser<br />ces fonctions de façon purement continue, par l'analyse, sans<br />référence à de la calculabilité.<br /><br />Dans le chapitre 5, nous reprenons certains de nos résultats à propos<br />de caractérisations logiques de classes de complexité dans le modèle<br />de Blum Shub et Smale, en relations avec la thèse de Paulin Jacobé de<br />Naurois. Le modèle de Blum Shub et Smale constitue un modèle de calcul<br />à temps discret et à espace continu. Le modèle, défini initialement<br />pour parler de complexité algébrique de problèmes sur le corps des<br />réels, ou plus généralement sur un anneau, a été par la suite été<br />étendu par Poizat en un modèle de calculs sur une structure logique<br />arbitraire. Avec Paulin Jacobé de Naurois, Felipe Cucker et Jean-Yves<br />Marion, nous avons caractérisé syntaxiquement les classes de<br />complexité majeures dans ce modèle sur une structure arbitraire, à la<br />Bellantoni et Cook 1992.<br /><br />Le chapitre 6 est consacré à une conclusion, dans laquelle nous<br />reprenons plusieurs questions et perspectives qui nous semblent<br />intéressantes.<br /><br />Dans l'annexe A, nous discutons un point de vue sur les<br />hypercalculs. La question de l'existence de systèmes capables de<br />réaliser des hypercalculs, c'est-à-dire d'effectuer des calculs<br />exploitables qui ne seraient pas réalisables par aucune machine de<br />Turing, fait encore couler de l'encre et des controverses. Nous avons<br />été invité à exprimer notre point de vue dans un numéro spécial sur le<br />sujet, que nous reprenons en annexe A. Nous y rappelons plusieurs<br />mauvaises compréhensions fréquentes de la thèse de Church, et nous<br />présentons un panorama de plusieurs classes de systèmes mathématiques,<br />avec la caractérisation de leur puissance.

Les réseaux réflecteurs imprimés connaissent un fort développement depuis la fin des années 80. Ce type d'antenne offre la possibilité de former des diagrammes de rayonnement complexes avec une relative simplicité, un faible coût de réalisation, de faibles pertes et un volume réduit. Cependant, il souffre encore de quelques défauts : - La non régularité de la géométrie de la cellule sur la surface du réseau, dans le cas d'une antenne passive, peut engendrer des dégradations sur le diagramme de rayonnement, surtout à la transition entre deux géométries extrêmes, lorsqu'un nouveau cycle de phase commence. - Le nombre relativement élevé de composants utilisés pour contrôler la phase de l'onde réfléchie, dans le cas d'une antenne reconfigurable, augmente le coût de fabrication de l'antenne et complexifie le circuit de commande des éléments reconfigurables. - La limitation en bande passante, qui a longtemps cantonné ce type d'antenne à des applications bande étroite, est principalement liée au comportement de la cellule unitaire constitutive du réseau. Dans cette thèse, nous nous intéressons donc à la conception de nouvelles topologies de cellules déphaseuses, passives et surtout reconfigurables, qui permettent, tout en conservant une relative simplicité de réalisation, d'offrir une large bande passante. De plus, le contrôle de la phase, dans le cas des cellules reconfigurables, doit être réalisé avec un nombre réduit de composants afin de respecter la contrainte de faible coût de fabrication.

La théorie de la complexité permet de classifier les problèmes en fonction de leur difficulté. Le cadre classique dans lequel elle s'applique est celui d'un algorithme centralisé qui dispose de toutes les informations. Avec l'essor des réseaux et des architectures décentralisées, l'algorithmique distribuée a été etudiee. Dans un grand nombre de problèmes, en optimisation et en économie, les décisions et les calculs sont effectu'es par des agents indépendants qui suivent des objectifs diff'erents dont la réalisation dépend des décisions des autres agents. La théorie des jeux est un cadre naturel pour analyser les solutions de tels problèmes. Elle propose des concepts de stabilité, le plus classique étant l'équilibre de Nash.Une manière naturelle de calculer de telles solutions est de " faire réagir " les agents ; si un agent voit quelles sont les décisions des autres joueurs ou plus généralement un " état du jeu ", il peut décider de changer sa décision pour atteindre son objectif faisant ainsi 'évoluer l'etat du jeu. On dit que ces algorithmes sont des " dynamiques " On sait que certaines dynamiques convergent vers un concept de solution. On s'intéresse 'a la vitesse de convergence des dynamiques. Certains concepts de solutions sont même complets pour certaines classes de complexité ce qui rend peu vraisemblable l'existence de dynamiques simples qui convergent rapidement vers ces solutions. On a utilisé alors trois approches pour obtenir une convergence rapide : améliorer la dynamique (en utilisant par exemple des bits aléatoires), restreindre la structure du problème, et rechercher une solution approchée.Sur les jeux de congestion, on a étendu les résultats de convergence rapide vers un équilibre de Nash approche aux jeux négatifs. Cependant, on a montré que sur les jeux sans contrainte de signe, calculer un équilibre de Nash approche est PLS-complet. Sur les jeux d'appariement, on a étudie la vitesse de dynamiques concurrentes lorsque les joueurs ont une information partielle paramétrée par un reseau social. En particulier, on a améliore des dynamiques naturelles afin qu'elles atteignent un équilibre enO(log(n)) tours (avec n le nombre de joueurs).

Nous détaillons dans cette thèse des algorithmes modérément exponentiels pour l'approximation du problème MAX SAT. Nous discutons d'une méthode générique pour la conception d'algorithmes exponentiels réalisant des schémas d'approximation dans un cadre plus général. Enfin, nous présentons des résultats paramétrés pour des problèmes de coupe à cardinalité contrainte.

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.

Un fasciagraphe de taille n et de fibre F est constitué de n copies consécutives du graphe F, chaque copie étant reliée à la suivante selon le même schéma. Les rotagraphes sont définis similairement, mais selon une structure circulaire. Dans cette thèse nous caractérisons un ensemble de problèmes combinatoires qui peuvent être résolus de façon efficace dans la classe des fasciagraphes et rotagraphes. Dans ce contexte, nous définissons les (d,q,w)-propriétés closes et stables, et présentons pour de telles propriétés un algorithme pour calculer une solution optimale en temps constant pour l'ensemble des fasciagraphes ou rotagraphes de fibre fixée. Nous montrons que plusieurs problèmes communément étudiés dans la théorie des graphes et NP-complets dans le cas général sont caractérisés par des (d,q,w)-propriétés closes ou stables. Dans une seconde partie de la thèse, nous adaptons cet algorithme générique à trois problèmes spécifiques caractérisés par des (d,q,w)-propriétés stables : le problème du code identifiant minimum, et deux problèmes proches, celui de dominant-localisateur minimum et celui du dominant-total-localisateur minimum. Nous présentons alors une implémentation de l'algorithme qui nous a permis de répondre à des questions ouvertes dans certains rotagraphes particuliers : les bandes circulaires de hauteur bornée. Nous en déduisons d'autres résultats sur les bandes infinies de hauteur bornée. Enfin, nous explorons le problème du code identifiant dans une autre classe de graphes à structure répétitive : les graphes fractals de cycle.

Si l'Ingénieur s'efforce de coordonner sur les territoires les deux facettes de son activité : d'un côté la gestion des fonctions urbaines, de l'autre celle des risques, il hésite à se démarquer de celles-ci comme il le devrait, pour affronter la complexité spatiale. Or notre pratique des espaces urbanisés comme notre engagement dans la prévention des risques montrent que la complexité se manifeste à lui, tant dans la réalisation des projets que dans la survenue des catastrophes. En proposant un outil d'analyse spatiale : le territoire-étagé, en le dotant d'une fonction - le monitorage - nous proposons une voie qui permette à l'ingénierie d'anticiper du plus possible le développement de processus dommageables. En permettant une plus grande compréhension des mécanismes à l'œuvre au sein des espaces métapolitains [Ascher, 1995], l'ingénierie du territoire-étagé offre la possibilité d'agir en retour sur les pratiques de gestion pour espérer réduire, par la résilience, les perturbations ou leurs effets de différentes natures et intensités.

The intended goal of this manuscript is to build bridges between two definitions of complexity. One of them, called the algorithmic complexity is well-known to any computer scientist as the difficulty of performing some task such as sorting or optimizing the outcome of some system. The other one, etymologically closer from the word "complexity" is about what happens when many parts of a system are interacting together. Just as cells in a living body, producers and consumers in some non-planned economies or mathematicians exchanging ideas to prove theorems. On the algorithmic side, the main objects that we are going to use are two models of computations, one called communication protocols, and the other one circuits. Communication protocols are found everywhere in our world, they are the basic stone of almost any human collaboration and achievement. The definition we are going to use of communication reflects exactly this idea of collaboration. Our other model, circuits, are basically combinations of logical gates put together with electrical wires carrying binary values, They are ubiquitous in our everyday life, they are how computers compute, how cell phones make calls, yet the most basic questions about them remain widely open, how to build the most efficient circuits computing a given function, How to prove that some function does not have a circuit of a given size, For all but the most basic computations, the question of whether they can be computed by a very small circuit is still open. On the other hand, our main object of study, cellular automata, is a prototype of our second definition of complexity. What "does" a cellular automaton is exactly this definition, making simple agents evolve with interaction with a small neighborhood. The theory of cellular automata is related to other fields of mathematics, such as dynamical systems, symbolic dynamics, and topology. Several uses of cellular automata have been suggested, ranging from the simple application of them as a model of other biological or physical phenomena, to the more general study in the theory of computation.