Un réseau complexe est un réseau d'interactions entre entités dont on ne peut pas déduire le comportement global à partir des comportements individuels desdites entités, d'où l'émergence de nouvelles propriétés. Notre problème est l'analyse et la modélisation de ces réseaux. L' analyse nécessite un formalisme englobant à la fois structure (approche statique) et fonction (approche dynamique), afin d'avoir une meilleure compréhension des caractéristiques de ces réseaux. En premier lieu, nous présentons dans cette thèse les modélisations utilisées jusqu'à présent et basées sur la théorie des graphes, sensées simuler le comportement des réseaux complexes. En analysant les faiblesses de ces modèles quant à une représentation convaincante des réseaux du monde réel (réseaux sociaux, informatiques, biologiques, ...), nous apportons une définition formelle générale d'un réseau par le biais de la théorie de la prétopologie, laquelle permet d'exprimer au mieux la dynamique de ces systèmes. Associée à cette définition, nous proposons une série de structures de données permettant de développer toute une algorithmique autour du modèle. En second lieu, nous proposons de nouveaux algorithmes d'analyse basés sur la classification d'éléments et la recherche d'éléments centraux, afin de fournir des outils d'aide à la décision puissants. Enfin nous présentons une librairie logicielle permettant la mise en oeuvre de simulations efficaces de tout modèle basé sur la théorie de la prétopologie.

Abstract : A lossless compression algorithm often applies the same coding scheme on the whole sequence to be compressed. Therefore, some factors of the sequence are shortened while others are lengthened. In this work, we propose an optimization algorithm of compression methods which breaks off the coding where it is not profitable, so that some segments of the initial sequence are copied as they are instead of being coded. The achieved compression is said modular, meaning that the compressed sequence is a sequel of compressed segments and copied segments. Under specific hypotheses, our algorithm computes an optimal modular compression in time O(n log n) where n is the length of the sequence. We show that our optimization method can be advantageously used to analyze data, and particularly genetic sequences. The Kolmogorov complexity theory brings to light the usefulness of compression when analyzing sequences. The work consists of three parts. The first one introduces the classical concepts of compression and coding, as well as the new concept of ICL codes for the integers. The second one presents the compression optimization algorithm by liftings that uses ICL codes. Finally, the third part presents applications of the compression optimization by liftings, especially in the context of genetic sequence analysis. With the specific problem of the localization of approximate tandem repeats, we show how the compression optimization algorithm by liftings can be used to localize regular segments and irregular segments of a sequence in a precise and optimal way. This comeback to experimentation makes it possible to analyze sequences that contain several thousands of symbols within the space of a few seconds. /Résumé : Une méthode de compression sans perte d'informations applique souvent le même schéma de codage d'un bout à l'autre de la séquence à comprimer. Certains facteurs de la séquence sont ainsi raccourcis mais malheureusement d'autres sont rallongés. Dans ce travail, nous proposons un algorithme d'optimisation de compression qui rompt le codage là ou il n'est pas intéressant en recopiant des morceaux de la séquence initiale. La compression obtenue est dite modulaire : la séquence comprimée est une succession de morceaux comprimés et de morceaux recopiés tels quels. Sous certaines hypothèses, notre algorithme fournit une compression modulaire optimale en temps O(n log n) où n est la longueur de la séquence. Nous montrons que notre méthode de compression peut avantageusement être utilisée pour analyser des données et plus particulièrement des séquences génétiques. La théorie de la complexité de Kolmogorov éclaire l'idée d'analyse de séquences par compression. Le travail comporte trois parties. La première introduit les concepts classiques de compression et de codage, ainsi que le concept nouveau de codage ICL d'entiers. La seconde développe l'algorithme d'optimisation de compression par liftings qui utilise les codes ICL. La dernière partie présente des applications de l'optimisation de compression par liftings, plus particulièrement dans le domaine de l'analyse de séquences génétiques. Nous montrons, à l'aide du problème spécifique de localisation de répétitions en tandem approximatives, comment l'algorithme d'optimisation par liftings peut être utilisé pour localiser précisément et de manière optimale les segments réguliers et les segments non réguliers des séquences. Il s'agit d'un retour à l'expérience qui permet l'analyse de séquences de plusieurs centaines de milliers de bases en quelques secondes.

Cette thèse est une étude de la géométrie de l'interaction dans le facteur hyperfini (GdI5), introduite par Jean-Yves Girard, et de ses liens avec les constructions plus anciennes. Nous commençons par montrer comment obtenir des adjonctions purement géométriques comme une identité entre des ensembles de cycles apparaissant entre des graphes. Il est alors possible, en choisis- sant une fonction qui mesure les cycles, d'obtenir une adjonction numérique. Nous montrons ensuite comment construire, sur la base d'une adjonction numérique, une géométrie de l'interaction pour la logique linéaire multiplicative additive où les preuves sont interprétées par des graphes. Nous expliquons également comment cette construction permet de définir une sémantique dénotationnelle de MALL, et une notion de vérité. Nous étudions finalement une généralisation de ce cadre utilisant des outils de théorie de la mesure afin d'interpréter les exponentielles et le second ordre. Les constructions sur les graphes étant paramétrées par une fonction de mesure des cycles, nous entreprenons ensuite l'étude de deux cas particuliers. Le premier s'avère être une version combinatoire de la GdI5, et nous obtenons donc une interprétation géométrique de l'orthogonalité basée sur le déterminant de Fuglede-Kadison. Le second cas particulier est une version combinatoire des constructions plus anciennes de la géométrie de l'interaction, où l'orthogonalité est basée sur la nilpotence. Ceci permet donc de comprendre le lien entre les différentes versions de la géométrie de l'interaction, et d'en déduire que les deux adjonctions -- qui semblent à première vue si différentes -- sont des conséquences d'une même identité géométrique. Nous étudions ensuite la notion de vérité subjective. Nous commençons par considérer une version légè- rement modifiée de la GdI5 avec une notion de vérité dépendant du choix d'une sous-algèbre maximale commutative (masa). Nous montrons qu'il existe une correspondance entre la classification des masas introduite par Dixmier (regulière, semi-régulière, singulière) et les fragments de la logique linéaire que l'on peut interpréter dans cette géométrie de l'interaction. Nous étudions alors la vérité subjective de la GdI5, qui dépends du choix d'une représentation du facteur hyperfini de type II1, à la lumière de ce résultat. Finalement, nous détaillerons une proposition de Girard pour étudier les classes de complexité et dé- taillons la caractérisation obtenue par ce dernier de la classe de complexité co-NL, en montrant comment coder un problème complet pour cette classe à l'aide d'opérateurs.

Ce document est divisé en deux parties principales. La première partie concerne les résultats que nous avons obtenu au travers de diverses collaborations sur les communications dans les réseaux. Afin de ne pas multiplier les chapitres dans cette partie, nous avons choisi en premier lieu de présenter l'évolution du contexte des réseaux sur lesquels j'ai travaillé durant ces 10 dernières années. En particulier, nous montrons plusieurs facettes que peut recouvrir l'expression \textbf{communications optiques}. Dans un deuxième temps, nous avons regroupé les problèmes abordés en deux chapitres: - le premier s'intéresse à des aspects structurels des graphes utiles pour la construction de protocoles de communication dans les réseaux. - le second aborde une problématique importante dans le contexte actuel de la recherche de la compétitivité: l'optimisation de ressources. La deuxième partie s'intéresse à deux représentations de graphes qui s'avèrent pertinentes pour les problèmes considérés. Elle présente deux problèmes principaux donnant deux chapitres indépendants. Le premier problème abordé dans cette partie concerne un très vieux (au sens informatique) problème issu de la théorie de flots: les flots multi-terminaux. Nous nous sommes attachés à montrer la puissance d'un outil permettant de représenter ces types de flots: les arbres de Gomory-Hu, ainsi que leur utilité dans une version paramétrée du problème. Le second problème présente au travers du calcul du polynôme chromatique une représentation des graphes sous la forme d'arbre de cliques augmenté.

Nous nous intéressons dans cette thèse à des problèmes d'aménagement de satellites. Le but est de développer des algorithmes efficaces et robustes menant à des outils simples pour aider l'ingénieur du bureau d'études dans ses tâches répétitives d'aménagement. Nous proposons un algorithme optimal qui calcule une section plane de la somme de Minkowski de deux polyèdres convexes et un algorithme efficace qui calcule l'union d'un ensemble de polygones par division et fusion. Nous avons soigneusement analysé la précision numérique nécessitée pour 1e fonctionnement correct de ces deux algorithmes et le traitement des dégénérescences géométriques qui peuvent apparaître. Nous avons conçu le logiciel GEOTOOLS pour le placement d'une suite d'équipements et en particulier des antennes qui ont un champ de vision. GEOTOOLS permet le placement interactif d'un objet dans un aménagement partiel en visualisant les contraintes imposées par cet aménagement (l'espace admissible). La deuxième partie de cette thèse consiste en une expérimentation de GEOTOOLS sur des modèles réalistes de satellites en plaçant des séquences d'antennes ínteractivement et automatiquement.

Les travaux effectués lors de cette thèse portent sur 1a construction d'algorithmes géométriques dit adaptatifs dans 1e sens ou leur temps de calcul s'adapte a la solution construite. Nous décrivons tout d'abord les principaux paradigmes qui permettent d'obtenir des algorithmes adaptatifs. Puis , nous proposons un algorithme quasi-optimal adaptatif pour le calcul d'enveloppe convexe d'objets planaires dont la complexité de l'enveloppe convexe de toute paire soit bornée. L'algorithme est basé sur une approche composite combinant 1e paradigme mariage avant conquête et 1a méthodologie du groupement en paquets. Nous considérons également le calcul de l'enveloppe supérieure de fonctions et la décomposition convexe partielle d'un ensemble de points. Finalement, nous nous sommes intéressés aux problèmes de perçabílíté d'objets qui ont été montré NP-difficiles. En premier lieu, nous avons étudié le cas de boîtes ísothétíques en donnant une heuristique adaptative dont 1a précision soit elle-même adaptative. Ensuite, nous avons étudié les propriétés combinatoires des objets convexes pour 1a perçabílíté. Nous obtenons une batterie d'algorithmes pour des classes variées d'objets dont certains prouvent l'exístence de théorèmes de type Helly.

Cette thèse traite des systèmes paramétrés. Ils modélisent des applications dans divers domaines, comme la robotique ou la calibration. Soit S un système paramétré. Nous cherchons à décrire les ouverts connexes U de l'espace des paramètres tels que S restreint à U admet un nombre constant de solutions réelles. En robotique, nous détectons les positions cuspidales des robots plan 3-RPR. En calibration photographique, nous décrivons le nombre de solutions réalisables du problème Perspective-3- Points. D'un point de vue théorique, nous montrons que sous certaines hypothèses, le calcul de la variété discriminante d'un système paramétré peut se réduire à un calcul de projection. Dans le cas des systèmes quelconques, nous introduisons la décomposition équidimensionnelle régulière. Notre algorithme possède de bonnes performances en pratique et nous permet par ailleurs de déduire un nouvel algorithme pour le calcul du radical d'un idéal.

Soit S un ensemble de points pris sur une surface F d'équation z = f(x,y) ; on projette S dans le plan (xOy), et on désire construire une triangulation de l'enveloppe convexe de la projection de S qui déterminera une approximation linéaire par morceaux de F, dont la qualité sera liée à une mesure de l'erreur d'approximation de la surface. Il a été récemment prouvé que la triangulation de Delaunay était optimale pour des critères de normes Lp, lorsqu'il s'agissait d'approcher linéairement toute fonction quadratique convexe, dans un espace de dimension quelconque. En revanche, très peu de recherches ont été menées lorsque la surface n'est pas convexe. Ce mémoire propose donc d'étudier l'approximation par une tri- angulation, pour des critères de normes L1 et L2, d'une surface non convexe d'équation la plus simple possible : le paraboloïde hyperbolique défini par z = x2 − y2. Une construction est ainsi donnée pour déterminer, de manière naturelle, les courbes de séparation d'un triangle ∆, c'est-à-dire les limites du plan pour lesquelles ∆ doit être conservé dans une triangulation localement op- timale du paraboloïde hyperbolique. Des algorithmes de triangulation qui font appel à diverses heuristiques fondées sur les courbes de séparation ont été abon- damment testés ; une amélioration significative par rapport à la triangulation de Delaunay a été mise en évidence. Une comparaison avec des triangulations glob- alement optimales, dont l'obtention n'est possible qu'au moyen de programmes de complexité exponentielle, prouve que ces algorithmes rendent finalement de "bonnes" triangulations. Les recherches montrent qu'un tel procédé peut facile- ment être généralisé à toutes les surfaces définies par des fonctions quadratiques, de la forme z = αx2 + βy2 + γxy + δ1x + δ2y + δ3.

Dans le contexte des réseaux à grande échelle, la prise en compte des pannes est une nécessité évidente. Ce document s'intéresse à l'approche auto-stabilisante qui vise à concevoir des algorithmes se ''réparant d'eux-même ' en cas de fautes transitoires, c'est-à-dire de pannes impliquant la modification arbitraire de l'état des processus. Il se focalise sur deux contextes différents, couvrant la majeure partie de mes travaux de recherche ces dernières années. La première partie du document est consacrée à l'algorithmique auto-stabilisante pour les réseaux de processus. La seconde partie du document est consacrée quant à elle à l'algorithmique auto-stabilisante pour des entités autonomes (agents logiciels, robots, etc.) se déplaçant dans un réseau.

Pruesse et Ruskey ont présenté un algorithme pour la génération de leur code Gray pour les idéaux d'un poset (ensemble partiellement ordonné) où deux idéaux adjacents diffèrent par un ou deux éléments. Leur algorithme fonctionne en temps amorti de O(n) par idéal. Squire a présenté une récurrence pour les idéaux d'un poset qui lui a permis de trouver un algorithme pour générer ces idéaux en temps amorti de O(log n) par idéal, mais pas en code Gray. Nous utilisons la récurrence de Squire pour trouver un code Gray pour les idéaux d'un poset, où deux idéaux adjacents diffèrent par un ou deux éléments. Dans le pire des cas, notre algorithme a la même complexité que celle de l'algorithme de Pruesse et Ruskey et dans les autres cas, sa complexité est meilleure que celle de leur algorithme et se rapproche de celle de l'algorithme de Squire. Squire a donné une condition pour obtenir cette complexité. Nous avons trouvé une condition moins restrictive que la sienne. Cette condition nous a permis d'améliorer la complexité de notre algorithme. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Poset, Extension linéaire, Cycle hamiltonien, Code Gray, Algorithme, Complexité.