Le codage de l'information environnementale par le cerveau est sujet à d'intenses débats tant au niveau de son implémentation biologique (propriété fonctionnelles) qu'au niveau de sa variabilité et de sa précision. Cette étude se base sur des enregistrements intracellulaires in-vivo des réponses des neurones du cortex visuel primaire à des stimuli de complexité variable incluant des images naturelles animées par des mouvements oculaires. Nous montrons que les propriétés fonctionnelles sont générées par la récurrence corticale, notamment par la balance excitation/inhibition exprimée au travers d'une grande diversité de combinatoire de sélectivité fonctionnelle des entrées synaptiques. En condition naturelle avec mouvement des yeux, nous montrons que le code est reproductible, binaire/temporel et que l'analyse corticale se traduit par une réduction des redondances présentes dans les entrées. Les interactions ou contrôles de gain corticaux, dont le profile temporel biphasique sculpte temporellement les réponses corticales, augmentent la précision temporelle et la reproductibilité du code. Nous proposons (en discussion) une ébauche de modèle statistique général d'adaptation et d'auto-organisation consistant en la maximisation de l'information mutuelle entre le système et son environnement. Ce modèle, basé sur une décomposition microscopique de l'entropie en ordre de redondance, est suffisant pour rendre compte des propriétés singulières de l'organisation du vivant (incluant la cognition) tel que sa reproductibilité, sa diversité, et son optimalité (en terme de codage).

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.