Tesi sul tema "Données algébriques"

Il est étudié l'extension du formalisme des types abstraits algébriques à la spécification de systèmes concurrents. Le concept clé de "process spécification" est introduit. Dans une telle spécification, des processus agissent sur des données au moyen d'un opérateur d'application. Les processus sont définis par composition d'action atomiques et d'action non-atomiques. Les opérateurs sont la composition non-déterministe, séquentielle ou parallèle. L'auteur s'intéresse à l'implémentation d'une "process spécification" par une autre et donne à cet effet une méthode de preuve

Les deux dernières décennies ont été marquées par l’apparition de nouveaux concepts architecturaux entraînant une évolution vers les systèmes distribués. C’est une conséquence de l’augmentation de la capacité de stockage des mémoires et de calcul et de l’arrivée de réseaux à haut débit, notamment locaux à 1Gb/s. La tendance dominante est le développement de nouveaux systèmes, dits d’abord: multi-ordinateur, Réseau de Stations de Travail et plus récemment, « Peer-to-Peer Computing » ou « Grid Computing ». Afin de tirer le meilleur profit des potentialités offertes, de nouvelles structures de données spécifiques aux données réparties sont nécessaires. Dans ce contexte, Les Structures de Données Distribuées et Scalables (SDDS) sont une nouvelle classe de structures introduites spécifiquement pour la gestion de fichiers sur un multi¬ ordinateur. Un fichier SDDS peut s'étendre dynamiquement, au fur et à mesure des insertions, d'un seul site de stockage à tout nombre de sites interconnectés disponibles en pratique. Les algorithmes d'adressages d'une SDDS sont conçus spécifiquement pour être scalables, notamment par absence d'un répertoire ou index central. La répartition de données est transparente pour l'application. Les données manipulées peuvent être entièrement en RAM distribuée afin d’être accessibles bien plus vite qu’à partir des disques. Plusieurs SDDS ont été proposées. Les plus connues sont celles basées sur le hachage, celui linéaire (LH*) notamment, et celles utilisant le partitionnement par intervalle (RP*). Un prototype appelé SDDS-2000a été construit vers l’année 2000 au CERIA pour expérimenter avec les SDDS sur les réseaux locaux des PC sous Windows. Dans ce système, on retrouve les fonctions de base de gestion de données telles que la création de fichiers, l’insertion d’enregistrements ou encore la possibilité de requêtes parallèles. En se basant sur SDDS-2000, notre Thèse a pour objectif la conception et l’implantation de nouvelles fonctions pour celui ci. Ces fonctions sont destinées à la sauvegarde de données sur le disque, un traitement plus efficace de mises à jour, le traitement de concurrence ainsi que celui de la recherche par le contenu (scans). Enfin, pour mieux répondre au contexte P2P, il nous fallait introduire une certaine protection de données stockées, au moins contre une découverte accidentelle de leurs valeurs. Ceci nous a conduit au problème intéressant de recherche de données par l’exploration directe de leur contenu encodé, sans décodage local. Nous avons basé l’ensemble de nos fonctions sur une technique nouvelle dite de signatures algébriques. Nous détaillons la théorie et notre pratique de signatures algébriques tout au long de cette Thèse. Ainsi, une sauvegarde sur disque n’écrit que les parties de la RAM modifiées depuis la dernière sauvegarde. Le contrôle de concurrence est optimiste, sans verrouillage, pour de meilleures performances d’accès. L’enregistrement mis à jour n’est envoyé au serveur que si la donnée est réellement modifiée. Puis, les données stockées sont suffisamment encodées pour rendre impossible toute découverte accidentelle de leurs valeurs réelles sur les serveurs. Nous les encodons à l’aide d’une variante de signatures algébriques, les signatures cumulatives. Notre encodage possède notamment des propriétés accélérant diverses recherches de chaînes de caractères, par rapport à celles explorant les mêmes données sans encodage. D’une manière un peu surprenante, certaines recherches se révèlent expérimentalement plus rapides que par des algorithmes fondamentaux bien connus, tels que celui de Karp-Rabin. Nous présentons des mesures de performance prouvant l’efficacité de notre approche. Notre système, appelé SDS-2005, a été dès lors annoncé sur DbWorld. Il est disponible sur le site du CERIA pour les téléchargements non commerciaux. Les détails de nos travaux ont fait l’objet de cinq publications dans des conférences internationales [LMS03, LMS05a, LMS05b, M06, LMRS06]. Notre prototype a également été montré à de nombreux visiteurs chercheurs. Il a fait l’objet d’une démonstration vidéo, diffusée notamment à Microsoft Research (Montain View, USA) et d’une présentation lors des journées académiques Microsoft. Dans notre mémoire, nous présentons d’abord l'état de l'art sur les SDDSs, en se basant sur celui de systèmes de fichiers distribués. Puis nous discutons l'architecture système de SDDS-2005. Celle-ci emploie notamment des structures de données spécifiques pour RAM, ainsi que des processus légers qui gèrent les traitements répartis à travers des files d'attente asynchrones. On présente ensuite le concept de signatures algébriques. Puis on détaille l’usage pour la sauvegarde d’un fichier SDDS et la mise à jour d’enregistrements. Nous discutons ensuite les signatures cumulatives. On décrit l’encodage de nos enregistrements. On présente les différents types de recherche par contenu non-clé (scans) dans notre système notamment la recherche par le préfixe et celle partielle d’une chaîne de caractère (ang pattern matching ou string search…) à travers plusieurs algorithmes alternatifs. Nous présentons un nouvel algorithme dit par n-Gramme semblant particulièrement simple d’usage et rapide On décrit aussi la recherche du plus grand préfixe et de la plus grande chaîne commune. Nous montrons que les signatures cumulatives sont particulièrement efficaces pour la recherche de longues chaînes telles que les images, les empreintes, les codes DNA…En réflexion sur les perspectives, on discute l’utilisation de ces signatures pour la compression différentielles lors des mises à jour distribuées des données ainsi que la protection contre la corruption silencieuse de données stockées. Puis nous discutons l’analyse expérimentale de notre système. Les mesures montrent la scalabilité de notre système ainsi que les temps d’exécution de nos différentes fonctions. On finit par des conclusions, perspectives et les références bibliographiques. Les annexes montrent nos principales publications (pour la convenance des membres anglophones de notre jury tout particulièrement). On y montre aussi la description de l’interface offerte aux applications par SDDS-2005, annoncée sur DbWorld
Recent years saw emergence of new architectures, involving multiple computers. New concepts were proposed. Among most popular are those of a multicomputer or of a Network of Worksattion and more recently, of Peer to Peer and Grid Computing. This thesis consists on the design, implementation and performance measurements of a prototype SDDS manager, called SDDS-2005. It manages key based ordered files in distributed RAM of Windows machines forming a grid or P2P network. Our scheme can backup the RAM on each storage node onto the local disk. Our goal is to write only the data that has changed since the last backup. We interest also to update records and non key search (scans). Their common denominator was some application of the properties of new signature scheme based that we call algebraic signatures, which are useful in this context. Ones needs then to find only the areas that changed in the bucket since the last buckup. Our signature based scheme for updating records at the SDDS client should prove its advantages in client-server based database systems in general. It holds the promise of interesting possibilities for transactional concurrency control, beyond the mere avoidance of lost updates. We also update only data have been changed because of the using the algebraic signatures. Also, partly pre-computed algebraic signature of a string encodes each symbol by its cumulative signatures. They protect the SDDS data against incidental viewing by an unauthorized server’s administrator. The method appears attractive, it does not amply any storage overhead. It is also completly transparent for servers and occurs in client. Next, our cheme provide fast string search (match) directly on encoded data at the SDDS servers. They appear an alternative to known Karp-Rabin type schemes. Scans can explore the storage nodes in parallel. They match the records by entire non-key content or by its substring, prefix, longest common prefix or longest common string. The search complexity is almost O (1) for prefix search. One may use them also to detect and localize the silent corruption. These features should be of interest to P2P and grid computing. Then, we propose novel string search algorithm called n-Gramme search. It also appears then among the fastest known, e. G, probably often the faster one we know. It cost only a small fraction of existing records match, especially for larger strings search. The experiments prove high efficiency of our implementation. Our buckup scheme is substantially more efficient with the algebraic signatures. The signature calculus is itself substantially faster, the gain being about 30 %. Also, experiments prove that our cumulative pre-computing notably accelerates the string searchs which are faster than the partial one, at the expense of higher encoding/decoding overhead. They are new alternatives to known Karp-Rabin type schemes, and likely to be usually faster. The speed of string matches opens interesting perspectives for the popular join, group-by, rollup, and cube database operations. Our work has been subject of five publications in international conferences [LMS03, LMS05a, LMS05b, ML06, l&al06]. For convenience, we have included the latest publications. Also, the package termed SDDS-2005 is available for non-commercial use at http://ceria. Dauphine. Fr/. It builds up on earlier versions of the prototype, a cumulative effort of several folks and n-Gramme algorithm implementation. We have also presented our proposed prototype, SDDS-2005, at the Microsoft Research Academic Days 2006

Le but de ma thèse est d’étudier l’optimisation et la distribution de requêtes, principalement de requêtes récursives, qui manipulent de larges volumes dedonnées. Premièrement, je passe en revue différents langages de requêtes ainsi que différentes approches formelles liées aux représentations intermédiaires de ces langages. Les langages et les approches formelles sont examinés à la lumière d’un nombre d’aspects tels que l’expressivité, la distribution, les optimisations automatiques, la manipulation des données complexes, le requêtage de graphes, l’incompatibilité d’impédence, avec une attention particulière portée à la capacité à exprimer des requêtes récursives. Dans un second temps, je propose des extensions d’approches formelles suivant deux axes de travaux de recherche: (1) les algèbres basées sur le modèle de données relationnel et pour lesquels je propose Dist-μ-RA, ainsi que (2) les algèbres basées sur les collections de types arbitraires, et pour lesquels je propose μ-monoids.Dist-μ-RA est un système qui étend l’algèbreμ-RA au contexte distribué.Concernant l’aspect algébrique, il s’intègre bien avec l’algèbre relationnelle et hérite de ses avantages tels que sa capacité à optimiser les requêtes quelles que soient leur forme initiale et leur traduction vers l’algèbre. Concernant l’aspect de distribution, différentes stratégies d’évaluation de termes algébriques récursifs dans un contexte distribué ont été étudiées. Ces stratégies sont implémentées sous forme de plans physiques avec des techniques qui automatisent la distribution des données afin de réduire les coûts de communication. Les résultats expérimentaux sur des graphes réels et synthétiques montrent l’efficacité de l’approche proposée par rapport aux systèmes existants.μ-monoids est une extension de l’algèbre de monoides avec un opérateur de point fixe qui modélise la récursion. L’algèbre μ-monoids est capable de modéliser des calculs récursifs sur des collections distribuées similaires à ceux effectués sur les plateformes Big Data. L’intérêt principal de l’opérateur de point fixe “μ” est que, sous réserve de conditions souvent remplies en pratique, il peut-être considéré comme un homomorphisme de monoides et peut donc être évalué avec des boucles parallèles avec une fusion finale plutôt qu’avec une boucle globale nécessitant des transferts réseau supplémentaires à chaque itération. Des règles de réécritures pour optimiser les termes récursifs, telles que le poussage de filtres, ont été proposées.Je propose en particulier une condition suffisante sur le terme évalué en boucle(φ) quelque soit sa forme, ainsi qu’une méthode qui utilise les types polymorphes et un système de types comme celui de Scala pour vérifier si cette condition est remplie. Je propose également une règle qui préfiltre les points fixes avant les jointures. La troisième règle permet de pousser des fonctions d’agrégation dans les points fixes. Les expériences menées sur la plateforme Spark montre les gains en performances apportés par ces optimisations systématiques
The goal of my PhD is to study the optimization and the distribution of queries, especially recursive queries, handling large amounts of data. I start by reviewing different query languages as well as formal approaches to intermediate representations of these languages. Languages and formal approaches are reviewed in the light of a number of aspects such as expressivity, distribution, automatic optimizations, manipulating complex data, graph querying, and impedence mismatch, with a special focus on the ability to express recursion. I then propose extensions to formal approaches along two main lines of work: (1) algebras based on the relational model, for which I propose Dist-μ-RA, and (2) algebras based on generic collections of arbitrary types, for which I propose μ-monoids.Dist-μ-RA is a system that extends theμ-RA algebra to the distributed setting. Regarding the algebraic aspect, it integrates well with the relational algebra and inherits its advantages including the fact that queries are optimized regardless of their initial shape and translation into the algebra. With respect to distribution, different strategies for evaluating recursive algebraic terms in a distributed setting have been studied. These strategies are implemented as plans with automated techniques for distributing data in order to reduce communication costs. Experimental results on both real and synthetic graphs show the effectiveness of the proposed approach compared to existing systems.μ-monoids is an extension of the monoid algera with a fixpoint operator that models recursion. The extended μ-monoids algebra is suitable for modeling recursive computations with distributed data collections such as the ones found in Big Data frameworks. The major interest of the “μ” fixpoint operator is that, under prerequisites that are often met in practice, it can be considered as a monoid homomorphism and thus can be evaluated by parallel loops with one final merge rather than by a global loop requiring network overhead after each iteration. Rewriting rules for optimizing fixpoint terms, such as pushing filters, are proposed. In particular, I propose a sufficient condition on the repeatedly evaluated term (φ) regardless of its shape, as well as a method using polymorphic types and a type system such as Scala’s to check whether this condition holds. I also propose a rule to prefilter a fixpoint before a join. The third rule allows for pushing aggregation functions inside a fixpoint. Experiments with the Spark platform illustrate performance gains brought by these systematic optimizations

L’essor des méthodes d’analyse de données dans des contextes toujours plus variés nécessite la conception de nouveaux outils permettant la gestion et la manipulation des données extraites. La construction de résumés est alors couramment structurée sous la forme de partitions d’ensembles dont la manipulation dépend à la fois du contexte applicatif et de leurs propriétés algébriques. Dans un premier temps, nous proposons de modéliser la gestion des résultats de requêtes d’agrégation dans un cube OLAP à l’aide d’un calcul algébrique sur des partitions. Nous mettons en évidence l’intérêt d’une telle démarche par le gain de temps et d’espace observé pour produire ces résultats. Nous traitons par la suite le cas de la modélisation du consensus de partitions où nous soulignons les difficultés propres à sa construction en l’absence de propriétés qui régissent la combinaison des partitions. Nous proposons donc d’approfondir l’étude des propriétés algébriques de la structure du treillis des partitions, en vue d’en améliorer la compréhension et par conséquent de produire de nouvelles procédures pour l’élaboration du consensus. En guise de conclusion, nous proposons la modélisation et une mise en œuvre concrète d’opérateurs sur des partitions génériques et nous livrons diverses expériences, propres à souligner l’intérêt de leur usage conceptuel et opérationnel
The rise of data analysis methods in many growing contexts requires the design of new tools, enabling management and handling of extracted data. Summarization process is then often formalized through the use of set partitions whose handling depends on applicative context and inherent properties. Firstly, we suggest to model the management of aggregation query results over a data cube within the algebraic framework of the partition lattice. We highlight the value of such an approach with a view to minimize both required space and time to generate those results. We then deal with the consensus of partitions issue in which we emphasize challenges related to the lack of properties that rule partitions combination. The idea put forward is to deepen algebraic properties of the partition lattice for the purpose of strengthening its understanding and generating new consensus functions. As a conclusion, we propose the modelling and implementation of operators defined over generic partitions and we carry out some experiences allowing to assert the benefit of their conceptual and operational use

Nous considérons la résolution de très grands systèmes linéaires creux à l'aide d'une méthode de factorisation directe appelée méthode multifrontale. Bien que numériquement robustes et faciles à utiliser (elles ne nécessitent que des informations algébriques : la matrice d'entrée A et le second membre b, même si elles peuvent exploiter des stratégies de prétraitement basées sur des informations géométriques), les méthodes directes sont très coûteuses en termes de mémoire et d'opérations, ce qui limite leur applicabilité à des problèmes de taille raisonnable (quelques millions d'équations). Cette étude se concentre sur l'exploitation des approximations de rang-faible dans la méthode multifrontale, pour réduire sa consommation mémoire et son volume d'opérations, dans des environnements séquentiel et à mémoire distribuée, sur une large classe de problèmes. D'abord, nous examinons les formats rang-faible qui ont déjà été développé pour représenter efficacement les matrices denses et qui ont été utilisées pour concevoir des solveur rapides pour les équations aux dérivées partielles, les équations intégrales et les problèmes aux valeurs propres. Ces formats sont hiérarchiques (les formats H et HSS sont les plus répandus) et il a été prouvé, en théorie et en pratique, qu'ils permettent de réduire substantiellement les besoins en mémoire et opération des calculs d'algèbre linéaire. Cependant, de nombreuses contraintes structurelles sont imposées sur les problèmes visés, ce qui peut limiter leur efficacité et leur applicabilité aux solveurs multifrontaux généraux. Nous proposons un format plat appelé Block Rang-Faible (BRF) basé sur un découpage naturel de la matrice en blocs et expliquons pourquoi il fournit toute la flexibilité nécéssaire à son utilisation dans un solveur multifrontal général, en terme de pivotage numérique et de parallélisme. Nous comparons le format BRF avec les autres et montrons que le format BRF ne compromet que peu les améliorations en mémoire et opération obtenues grâce aux approximations rang-faible. Une étude de stabilité montre que les approximations sont bien contrôlées par un paramètre numérique explicite appelé le seuil rang-faible, ce qui est critique dans l'optique de résoudre des systèmes linéaires creux avec précision. Ensuite, nous expliquons comment les factorisations exploitant le format BRF peuvent être efficacement implémentées dans les solveurs multifrontaux. Nous proposons plusieurs algorithmes de factorisation BRF, ce qui permet d'atteindre différents objectifs. Les algorithmes proposés ont été implémentés dans le solveur multifrontal MUMPS. Nous présentons tout d'abord des expériences effectuées avec des équations aux dérivées partielles standardes pour analyser les principales propriétés des algorithms BRF et montrer le potentiel et la flexibilité de l'approche ; une comparaison avec un code basé sur le format HSS est également fournie. Ensuite, nous expérimentons le format BRF sur des problèmes variés et de grande taille (jusqu'à une centaine de millions d'inconnues), provenant de nombreuses applications industrielles. Pour finir, nous illustrons l'utilisation de notre approche en tant que préconditionneur pour la méthode du Gradient Conjugué.

Les travaux présentés ont trait à la réalisation d'un progiciel pour le traitement informatique des procédés chimiques et parachimiques en régime permanent. L'auteur présente la conceptin d'un simulateur de procédés, élément de base de l'ensemble en insistant particulièrement sur la structure du produit. Après une analyse des besoins, les caractéristiques d'un programme général de simulation sont définies et la stratégie de traitement numérique choisie. Les critères sont ensuite exploités pour créer une structure arborescente ouverte, articulée autour d'une base de données. La conception d'un langage de simulation est présentée et mise en oeuvre sur des exemples industriels. Les qualités essentielles liées à la structure du système développé sont démontrées par le traitement complet d'exemples tests.

Le but de cette thèse est de présenter un nouveau formalisme de traitement d'exceptions dans le cadre des types abstraits algébriques, et de l'utiliser pour traiter l'implémentation abstraite en présence d'exceptions. La première partie développe une nouvelle sémantique pour l'implémentation abstraite, et permet d'exprimer la correction d'une implémentation en terme de suffisante complétude et consistance hiérarchique. Ainsi les preuves de correction d'une implémentation abstraite peuvent être traitées par des méthodes classiques telles que les techniques de réécriture ou d'induction structurelle. L'idée majeure de cette approche repose sur une distinction fondamentale entre spécifications descriptives et spécifications constructives. Des conditions simples et peu restrictives sont fournies pour que la composition d'implémentations correctes reste correcte. La seconde partie développe un nouveau formalisme de traitement d'exceptions : les exception-algèbres. Ce formalisme autorise toutes les formes de traitement d'exceptions (messages d'erreur, propagation implicite des exceptions et des erreurs, récupérations d'exceptions), tout en préservant l'existence des modèles initiaux et une approche fonctorielle simple. Nous définissons en particulier une sémantique fonctorielle des enrichissements, munie des notions de consistance hiérarchique et de suffisante complétude. Pius généralement, la plupart des primitives de structuration des spécifications algébriques peuvent être étendues sans difficulté aux exception-algèbres car les résultats fondamentaux relatifs aux exception-algèbres sont analogues à celles des types abstraits algébriques "classiques". La troisième partie démontre en particulier que le formalisme d'implémentation abstraite peut être étendu aux exception-algèbres sans difficulté. Plusieurs exemples d’exception-spécifications et d'implémentations abstraites sont donnés en annexe.

La première partie de ma thèse est la description d'un modèle algébrique pour la gestion des séquences temporelles synchronisées. Ce modèle est une extension du modèle relationnel classique auquel on ajoute un type nouveau, le type séquence temporelle. L'algèbre relationnelle est augmentée de trois opérateurs dédiés à ce nouveau type. Ces opérateurs permettent de retrouver toutes les opérations classiquement conduites sur des séquences temporelles. Le langage utilisateur correspondant est exposé, ainsi que de nombreux exemples, puisés notamment dans le domaine de la gestion des partitions symboliques. La seconde partie est la description d'un index permettant de réaliser plusieurs types de recherches dans des partitions symboliques (exacte, transposée, avec ou sans rythme et approchée). Il repose notamment sur la notion de signature algébrique. Dans la dernière partie, je décris une plateforme dédiée à la gestion du contenu musical symbolique qui est une application des deux précédentes parties.

Cette thèse débute par la minimisation des automates non-déterministes. Je fournis la preuve d'une technique présentée sans démonstration par Sengoku ainsi que différentes heuristiques, basées sur le calcul de simulations d'états, combinant langages gauches et droits. Ce travail débouche sur une technique de réduction des automates de Büchi. Parallèlement, je m'intéresse à la maîtrise de la complexité en espace de la déterminisation en optimisant la déterminisation partielle. Les thèmes suivants sont plus applicatifs. Le premier concerne la recherche approchée d'expressions secondaires dans le génome au moyen de grammaires algébriques. Je présente une adaptation de l'algorithme de Valiant, puis un algorithme de type CYK pour la recherche approchée d'une hélice simple. Je termine par la recherche d'équipes de gènes communes entre différents génomes, dont un problème sous-jacent est la recherche de composantes connexes communes à plusieurs graphes. J'y présente notre nouvel algorithme traitant le cas de graphes d'intervalles
The initial topic of this thesis is automata minimization. I prove a technique for full minimization that was given unproved by Sengoku, together with heuristics based on state simulations, that combine left and right languages. This work provides a reduction technique for B\"uchi automata. On the other hand, I focus on managing the space complexity of determinisation by an optimized partial determinization. The following is more involved in practical applications. First, I focus on secondary expression search in genome, based on context-free grammars. I give an adaptation of Valiant's algorithm, and a CYK algorithm for single hairpin approximate search. Finally, I investigate gene-team search between several genomes. An underlying problem is the common connected set search between several graphs. I describe our new algorithm that is specific to interval graphs

De nombreux formalismes existent pour modéliser et résoudre des problèmes de décision séquentielle. Certains, comme les réseaux de contraintes, permettent de formuler des problèmes de décision "simples" alors que d’autres peuvent prendre en compte des données plus complexes telles que des incertitudes, des infaisabilités sur les décisions et des utilités. Diverses extensions d’un même formalisme sont de plus souvent introduites de manière à représenter l'incertain et les préférences sous des formes variées (probabilités, possibilités. . . ; utilités additives ou non. . . ). Chacun de ces formalismes est généralement équipé d’algorithmes dédiés. La première partie de cette thèse définit un cadre de représentation général qui englobe de nombreux formalismes de décision séquentielle dans l'incertain. Ce cadre, nommé cadre PFU pour "Plausibilités-Faisabilité-Utilité", repose sur trois éléments clés : (1) une structure algébrique spécifiant comment combiner et synthétiser des informations ; (2) des fonctions locales portant sur certaines variables et exprimant des incertitudes, des faisabilités ou des utilités; (3) une classe de requêtes sur ces fonctions locales, qui permet de modéliser des scénarios décisionnels variés en termes d’observabilité et de controlabilité. Ce travail de représentation de la connaissance est complété, dans la seconde partie de la thèse, par un travail algorithmique. Les deux types d’algorithmes développés sont des algorithmes de type élimination de variables et de type recherche arborescente avec bornes et techniques de mémorisation. Nous montrons également qu’il est possible d’utiliser une architecture de calcul générale qui exploite la structure des requêtes considérées pour les décomposer en calcul locaux. En unifiant des formalismes variés, le cadre PFU apporte une meilleure compréhension des liens entre certains formalismes. Il n’est pas qu’un cadre unificateur étant donné que certaines de ces intanciations correspondent à de nouveaux formalismes. Enfin, il permet de définir des algorithmes génériques qui sont soit des généralisations d'algorithmes existants soit des techniques nouvelles applicables directement aux formalismes couverts.

Le but de cette thèse est d'étudier différents exemples des variétés de caractères régulières et sauvages des courbes complexes.La première partie est consacrée à l'étude d'un exemple de variété de caractères de la sphère avec quatre trous et groupe exotique G₂ comme son groupe de structure. On démontre que pour un choix particulier de classes de conjugaison du groupe G₂ , la variété obtenue est de dimension complexe deux et isomorphe à la surface cubique de Fricke—Klein. Cette surface apparaît déjà dans le cas classique comme la variété de caractères de cette surface avec le groupe de structure SL₂ (C). De plus, on interprète les orbites de groupe de tresses de taille 7 dans cette surface comme les droites passant par les triplés de points dans le plan de Fano P² (F₂).Dans la deuxième partie, on établit plusieurs cas de la „conjecture d'écho”, correspondant aux équations différentielles de Painlevé I, II et IV. On montre que sur la sphère de Riemann avec un point singulier, pour des choix particuliers de la singularité il y a trois familles infinies de variétés de caractères sauvages de dimension complexe deux. Dans ces familles, le rang du groupe de structure n'est pas borné et augmente jusqu'à l'infini. Le résultat principal de cette partie démontre que tous les membres de ces trois familles de variétés sont isomorphes aux espaces de phase des équations de Painlevé associées. En calculant les quotients de la théorie géométrique des invariants, on fournit des isomorphismes explicites entre les anneaux de fonctions des variétés affines qui apparaissent et relie les paramètres des surfaces cubiques.Dans la dernière partie, avec des outils de la géométrie quasi-Hamiltonienne, on étudie une famille des espaces généralisant les hiérarchies de Painlevé I et II pour les groupes linéaires de rang supérieur. En particulier, pour toute variété Bk dans la hiérarchie il y a une application moment, prenant ses valeurs dans un groupe, qui s'avère être un polynôme continuant d'Euler. Ces polynômes admettent des factorisations en continuants plus courts et on montre que les factorisations d'un polynôme continuant de longueur k en termes de longueur un sont énumérées par le nombre de Catalan Ck. De plus, chaque factorisation fournit un plongement du produit de fusion de k copies de GLn (C) sur un ouvert dense de Bk et on démontre que ces plongements relient les structures quasi-Hamiltoniennes. Finalement, on utilise ce résultat pour dériver une formule explicite pour la 2-forme quasi-Hamiltonienne sur Bk, généralisant la formule connue dans le cas de B₂
The aim of this thesis is to study various examples of tame and wild character varieties of complex curves.In the first part, we study an example of a tame character variety of the four-holed sphere with simple poles and exotic group G₂ as the structure group. We show that for a particular choice of conjugacy classes in G₂, the resulting affine symplectic variety of complex dimension two is isomorphic to the Fricke-Klein cubic surface, known from the classical case of the character variety for the group SL₂(C). Furthermore, we interpret the braid group orbits of size 7 in this affine surface as lines passing through triples of points in the Fano plane P²(F₂).In the second part, we establish multiple cases of the so-called „echo conjecture”, corresponding to the cases of Painleve I, II and IV differential equations. We show that for the Riemann sphere with one singular point and suitably chosen behavior at the singularity, there are three infinite families of wild character varieties of complex dimension two. In these families, the rank of the structure group is not bounded and goes to infinity. The main result of this part shows that in each family all the members are affine cubic surfaces, isomorphic to the phase spaces of the aforementioned Painleve equations. By computing the geometric invariat theory quotients, we provide explicit isomorphisms between the rings of functions of the arising affine varieties and relate the coefficients of the affine surfaces.The last part is dedicated to the study of a family of spaces generalizing the Painleve I and II hierarchies for higher rank linear groups, which is done by the means of quasi-Hamiltonian geometry. In particular, for each variety Bk in the hierarchy there is a group-valued moment map and they turn out to be the Euler's continuant polynomials. These in turn admit factorisations into products of shorter continuants and we show that for a continuant of length k, the distinct factorisations into continuants of length one are counted by the Catalan number Ck. Moreover, each such factorisation provides an embedding of the fusion product of k copies of GLn(C) onto a dense open subset of B_k and the quasi-Hamiltonian structures do match up. Finally, using this result we derive the formula for the quasi-Hamiltonian two form on the space Bk, which generalises the formula known for the case of B₂

Cette thèse porte sur la preuve automatique de propriétés concernant la relation entrée/sortie de programmes fonctionnels manipulant des types de données algébriques (ADT). De récents résultats montrent comment approximer un programme fonctionnel en utilisant un automate d'arbre. Bien qu'expressives, ces techniques ne peuvent pas prouver de propriété reliant l'entrée et la sortie d'une fonction, par exemple qu'inverser une liste préserve sa longueur. Dans cette thèse, nous nous appuyons sur ces résultats et définissons une procédure pour calculer ou sur-approximer une telle relation. Formellement, le problème de la vérification de programmes se réduit à la satisfiabilité de clauses, que nous résolvons en exhibant un modèle. Dans cette thèse, nous proposons deux représentations relationnelles de ces modèles de Herbrand : les automates d'arbres convolués et les shallow Horn clauses. Les automates d'arbres convolués généralisent les automates d'arbres et sont généralisés par les shallow Horn clauses. Le problème d'inférence du modèle de Herbrand découlant de la vérification relationnelle étant indécidable, nous proposons une procédure d'inférence incomplète mais correcte. Les expériences montrent que cette procédure est performante en pratique par rapport aux outils actuels, à la fois pour la vérification des propriétés et pour la recherche de contre-exemples
This thesis is concerned with automatically proving properties about the input/output relation of functional programs operating over algebraic data types. Recent results show how to approximate the image of a functional program using a regular tree language. Though expressive, those techniques cannot prove properties relating the input and the output of a function, e.g., proving that the output of a function reversing a list has the same length as the input list. In this thesis, we build upon those results and define a procedure to compute or over-approximate such a relation, thereby allowing to prove properties that require a more precise relational representation. Formally, the program verification problem reduces to satisfiability of clauses over the theory of algebraic data types, which we solve by exhibiting a Herbrand model of the clauses. In this thesis, we propose two relational representations of these Herbrand models: convoluted tree automata and shallow Horn clauses. Convoluted tree automata generalize tree automata and are in turn generalized by shallow Horn clauses. The Herbrand model inference problem arising from relational verification is undecidable, so we propose an incomplete but sound inference procedure. Experiments show that this procedure performs well in practice w.r.t. state of the art tools, both for verifying properties and for finding counterexamples

Dans des structures non associatives du type arbres binaires, parenthésages, magmas binaires, on étudie un certain nombre de transformations définies par des règles de réécriture, d'un point de vue combinatoire (caractérisation, dénombrements), d'un point de vue algébrique (structure d'ordre engendrée, métrique) et d'un point de vue algorithmique (calcul effectif de certains objets et de la métrique). Dans une certaine famille de magmas binaires dits exponentiatifs, on aborde des problèmes du mot. Enfin on propose deux modelés permettant de résoudre rationnellement de façon virtuelle des systèmes linéaires de séries formelles définies dans un cadre non associatif ; l'un de ces modèles procède par plongement dans un magma pseudo-associatif

Malgré l’efficacité des réseaux pour représenter les systèmes complexes, de récents travaux ont montré que leur structure limite parfois le pouvoir explicatif des modèles théoriques, puisqu’elle n’encode que des relations par paire. Si une interaction plus complexe existe dans le système représenté, elle est automatiquement réduite à un groupe d’interactions par paire, c’est-à-dire d’ordre un. Il faut alors utiliser des structures qui prennent en compte les interactions d’ordre supérieur. Cependant, qu’elles soient ou non d’ordre supérieur, les interactions entre les éléments d’un système sont rarement explicites dans les jeux de données. C’est notamment le cas des données de présence/absence qui indiquent quelles espèces (animales, végétales ou autres) se retrouvent (ou non) sur un site d’observation sans indiquer les relations entre elles. L’objectif de ce mémoire est alors de développer une technique d’inférence pour dénicher les interactions d’ordre supérieur au sein de données de présence/absence. Ici, deux cadres théoriques sont explorés. Le premier est basé sur la comparaison entre la topologie des données, obtenue grâce à une hypothèse souple, et celle d’un ensemble aléatoire. Le second utilise plutôt les modèles log-linéaire et les tests d’hypothèses pour inférer les interactions une à une jusqu’à l’ordre désiré. Ce cadre a permis d’élaborer plusieurs méthodes d’inférence qui génèrent des complexes simpliciaux (ou des hypergraphes) qui peut être analysés grâce aux outils standards de la science des réseaux en plus de l’homologie. Afin de valider ces méthodes, nous avons développé un modèle génératif de données de présence/absence dans lesquelles les véritables interactions sont connues. Des résultats concrets ont également été obtenus pour des jeux de données réelles. Notamment, à partir de données de présence/absence d’oiseaux nicheurs du Québec, nous avons réussi à inférer des cooccurrences d’ordre deux.
Despite the effectiveness of networks to represent complex systems, recent work has shownthat their structure sometimes limits the explanatory power of the theoretical models, sinceit only encodes dyadic interactions. If a more complex interaction exists in the system, it isautomatically reduced to a group of pairwise interactions that are of the first order. We thusneed to use structures that can take higher-order interactions into account. However, whetherrelationships are of higher order or not is rarely explicit in real data sets. This is the case ofpresence/absence data, that only indicate which species (of animals, plants or others) can befound (or not) on a site without showing the interactions between them.The goal of this project is to develop an inference method to find higher-order interactionswithin presence/absence data. Here, two frameworks are examined. The first one is based onthe comparison of the topology of the data, obtained with a non-restrictive hypothesis, andthe topology of a random ensemble. The second one uses log-linear models and hypothesistesting to infer interactions one by one until the desired order. From this framework, we havedevelopped several inference methods to generate simplicial complexes (or hypergraphs) thatcan be studied with regular tools of network science as well as homology. In order to validatethese methods, we have developed a generative model of presence/absence data in which thetrue interactions are known. Results have also been obtained on real data sets. For instance,from presence/absence data of nesting birds in Québec, we were able to infer co-occurrencesof order two

Ces dernières années, le besoin de cadres rigoureux pour traiter des données non-linéaires s'est développé considérablement en imagerie médicale. Ici, nous avons proposé plusieurs cadres généraux pour traiter certains de ces types de données, qui appartiennent à des groupes de Lie. Pour ce faire, nous nous sommes appuyés sur les propriétés algébriques de ces espaces. Ainsi, nous avons présenté un cadre de traitement général pour les matrices symétriques définies positives, appelé log-euclidien, très simple à utiliser et avec d'excellentes propriétés théoriques ; il est particulièrement adapté au traitement des images de tenseurs de diffusion. Nous avons également proposé des cadres, dits polyaffines, pour paramétrer les transformations localement rigides ou affines, en garantissant leur inversibilité avec d'excellentes propriétés théoriques. Leur utilisation est illustrée avec succès dans le cas du recalage localement rigide de coupes histologiques et du recalage 3D localement affine d'IRMs du cerveau humain. Ce travail nous a menés à proposer deux cadres généraux nouveaux pour le calcul de statistiques dans les groupes de Lie en dimension finie : d'abord le cadre log-euclidien, qui généralise notre travail sur les tenseurs, et un cadre basé sur la notion nouvelle de moyenne bi-invariante, dont les propriétés généralisent celles de la moyenne arithmétique des espaces euclidiens. Enfin, nous avons généralisé notre cadre log-euclidien aux déformations géométriques difféomorphes afin de permettre un calclul simple des statistiques sur ces transformations, ce qui ouvre la voie à un cadre général et cohérent pour les statistiques en anatomie computationnelle.

Cette étude consiste à élaborer des algorithmes, bases sur des critères géométriques, permettant de reconstruire une courbe ou une surface, à partir d'une représentation sous forme ponctuelle. Il s'agit, connaissant uniquement les coordonnées d'un ensemble de n points, de déterminer soit une ligne polygonale, soit une surface polyedrale a faces triangulaires, ayant pour sommets ces points, et qui converge uniformément vers la courbe ou la surface initiale, lorsque le nombre de points n tend vers l'infini. L’originalité de cette étude réside à la fois dans le fait qu'aucune structure sur les données n'est connue initialement, et dans l'approche théorique développée pour valider les méthodes proposées. De nombreuses applications pratiques en reconnaissant de forme, en vision par ordinateur, en imagerie médicale, ont suscité de l'intérêt pour ce type d'étude, qui peut également constituer une étape préliminaire à des problèmes d'interpolation de données. Dans le cas où les points sont situés sur une courbe, ce problème revient à déterminer un ordre sur ces données. Nous présentons deux critères qui nous permettent d'obtenir les résultats de convergence souhaites, pour une grande variété de courbes. Nous démontrons également que ces deux algorithmes, dont la complexité temporelle moyenne est en o(n log n), permettent de séparer les points selon chaque composante connexe de la courbe sur laquelle ils se trouvent et de déterminer ses éventuelles extrémités. Ces deux algorithmes sont illustres par de nombreux exemples et diverses applications pratiques, dont deux ont été réalisées en collaboration avec l’aérospatiale et le centre d'étude et de recherche de Toulouse. Dans une seconde partie, nous étendons cette étude au cas où les points initiaux sont situés sur une surface connexe. Nous présentons un premier algorithme, qui consiste a maximiser l'angle dièdre situe entre deux faces adjacentes de la surface polyedrale, et qui permet de traiter le cas de surfaces fermées convexes. Puis nous adaptons ce critère au cas de surfaces fermées non convexes et nous présentons une heuristique permettant de traiter le cas de surfaces a bord. La complexité temporelle moyenne de ces algorithmes, qui ont été illustres par divers exemples numériques, est en o(n log n)

Les algorithmes de résolution polynomiale sont impliqués dans des outils sophistiqués de calcul en géométrie algébrique aussi bien quen ingénierie. Les plus populaires dentre eux reposent sur des bases de Gröbner, des matrices de Macaulay ou des décompositions triangulaires. Dans tous ces algorithmes, les polynômes sont développés dans une base des monômes et les calculs utilisent essentiellement des routines dalgèbre linéaire. L'inconvénient majeur de ces méthodes est lexplosion exponentielle du nombre de monômes apparaissant dans des polynômes éliminants. De manière alternative, lalgorithme Kronecker manie des polynômes codés comme la fonction qui calcule ses valeurs en tout point.
Dans cette thèse, nous donnons une présentation concise de ce dernier algorithme, ainsi qu'une preuve autonome de son bon fonctionnement. Toutes nos démonstrations sont intimement liées aux algorithmes, et ont pour conséquence des résultats classiques en géométrie algébrique, comme un théorème de Bézout. Au delà de leur intérêt pédagogique, ces preuves permettent de lever certaines hypothèses de régularité, et donc d'étendre l'algorithme au calcul des multiplicités sans coût supplémentaire.
Ensuite, nous présentons un algorithme de décomposition primaire pour les idéaux de polynômes de dimension nulle. Nous en donnerons également une étude de complexité précise, complexité qui est polynomiale en le nombre de variables, en le coût dévaluation du système, et en un nombre de Bézout.

Les algorithmes de résolution polynomiale sont impliqués dans des outils sophistiqués de calcul en géométrie algébrique aussi bien qu’en ingénierie. Les plus populaires d’entre eux reposent sur des bases de Gröbner, des matrices de Macaulay ou des décompositions triangulaires. Dans tous ces algorithmes, les polynômes sont développés dans une base des monômes et les calculs utilisent essentiellement des routines d’algèbre linéaire. L’inconvénient majeur de ces méthodes est l’explosion exponentielle du nombre de monômes apparaissant dans des polynômes éliminants. De manière alternative, l’algorithme Kronecker manie des polynômes codés comme la fonction qui calcule ses valeurs en tout point. Dans cette thèse, nous donnons une présentation concise de ce dernier algorithme, ainsi qu’une preuve autonome de son bon fonctionnement. Toutes nos démonstrations sont intimement liées aux algorithmes, et ont pour conséquence des résultats classiques en géométrie algébrique, comme un théorème de Bézout. Au delà de leur intérêt pédagogique, ces preuves permettent de lever certaines hypothèses de régularité, et donc d’étendre l’algorithme au calcul des multiplicit és sans coût supplémentaire. Enfin, nous présentons un algorithme de décomposition primaire pour les idéaux de polynômes de dimension nulle. Nous en donnons également une étude de complexité précise, complexité qui est polynomiale en le nombre de variables, en le coût d’évaluation du système, et en un nombre de Bézout. Mots clefs : algorithme, résolution polynomiale, décomposition primaire, complexité, géométrie algébrique effective
Nowadays, polynomial system solvers are involved in sophisticated computations in algebraic geometry as well as in practical engineering. The most popular algorithms are based on Gr¨obner bases, resultants, Macaulay matrices, or triangular decompositions. In all these algorithms, multivariate polynomials are expanded in a monomial basis, and the computations mainly reduce to linear algebra. The major drawback of these techniques is the exponential explosion of the size of eliminant polynomials. Alternatively, the Kronecker solver uses data structures to represent the input polynomials as the functions that compute their values at any given point. In this PhD thesis we give a concise presentation of the Kronecker solver, with a self-contained proof of correctness. Our proofs closely follow the algorithms, and as consequences, we obtain some classical results in algebraic geometry such as a B´ezout Theorem. Beyond their pedagogical interest, these new proofs allow us to discard some regularity hypotheses, and so to enhance the solver in order to compute the multiplicities of the zeros without any extra cost. At last, we design a new algorithm for primary decomposition of a zero-dimensional polynomial ideal. We also give a cost analysis of this algorithm, which is polynomial in the number of variables, in the evaluation cost of the input system, and in a B´ezout number. Keyword: algorithm, polynomial solving, primary decomposition, complexity, effective algebraic geometry

La notion de données semi-structureées est liée au monde du web. On appelle donnée semi-structurée une donnée dont le schéma n'est pas défini a priori. Par exemple, il peut s'agir d'une page HTML, d'un site Web tout entier ou encore d'un document XML. Cette thèse étudie les requêtes sur les données modélisées par des graphes. Plus précisément, on s'intéresse à différents langages de requêtes associés. Dans le cas des graphes orientés, on utilise des techniques de réécriture et d'automates pour étudier - à des fins d'optimisation de requêtes - les contraintes d'inclusions. Elles portent sur les chemins qui permettent de naviguer dans la donnée. Par ailleurs, on génère un index d'une donnée qui préserve toutes les contraintes d'inclusions. Ensuite, on étend cette étude pour obtenir le concept de requête graphe. Appliqué au cas des documents "XML coloré", elles permettent d'étudier formellement l'expressivité et la complexité de langages de requêtes inspirés de XPath et de XQuery. Enfin, les résultats théoriques sont validés par des expérimentations.

L’analyse de données topologique est un domaine de recherche récent qui vise à employer les techniques de la topologie algébrique pour concevoir des descripteurs de jeux de données. Pour être utiles en pratique, ces descripteurs doivent être calculables, et posséder une notion de métrique, afin de pouvoir exprimer leur stabilité vis à vis du bruit inhérent à toutes données réelles. La théorie de la persistance a été élaborée au début des années 2000 commeun premier cadre th éorique permettant de définir detels descripteurs - les désormais bien connus codebarres. Bien que très bien adaptée à un contexte informatique, la théorie de la persistance possède certaines limitations théoriques. Dans ce manuscript,nous établissons des liens explicites entre la théorie dérivée des faisceaux munie de la distance de convolution(d’après Kashiwara-Schapira) et la théorie de la persistance.Nous commençons par montrer un théorème d’isométrie dérivée pour les faisceaux constructibles sur R, c’est à dire, nous exprimons la distance deconvolution comme une distance d’appariement entreles code-barres gradués de ces faisceaux. Cela nous permet de conclure dans ce cadre que la distance de convolution est fermée, ainsi que la classe des faisceaux constructibles sur R munie de la distance de convolution forme un espace topologique localement connexe par arcs. Nous observons ensuite que la collection desmodules de persistance zig-zag associée à une fonction à valeurs réelle possède une structure supplémentaire, que nous appelons systèmes de Mayer-Vietoris. Sous des hypothèses de finitude, nous classifions tous les systèmes de Mayer-Vietoris. Cela nous permet d’établir une correspondence fonctorielle et isométrique entre la catégorie dérivée des faisceaux constructibles sur R équipée de la distance de convolution, et la catégorie des systèmes de Mayer-Vietoris fortement finis munie de la distance d’entrelacement. Nous en déduisons une méthode de calcul des code-barres gradués faisceautiques à partir de programmes informatiques déjà implémentés par la communauté de la persistance. Nous terminons par donner une définition purement faisceautique de la notion de module de persistance éphémère. Nous établissons que la catégorie observable des modules de persistance (le quotient de la catégorie des modules de persistance par la sous catégorie des modules de persistance éphémères)est équivalente à la catégorie bien connue des -faisceaux
Topological data analysis is a recent field of research aiming at using techniques coming from algebraic topology to define descriptors of datasets. To be useful in practice, these descriptors must be computable, and coming with a notion of metric, in order to express their stability properties with res-pect to the noise that always comes with real world data. Persistence theory was elaborated in the early 2000’s as a first theoretical setting to define such des-criptors - the now famous so-called barcodes. Howe-ver very well suited to be implemented in a compu-ter, persistence theory has certain limitations. In this manuscript, we establish explicit links between the theory of derived sheaves equipped with the convolu-tion distance (after Kashiwara-Schapira) and persis-tence theory.We start by showing a derived isometry theorem for constructible sheaves over R, that is, we express the convolution distance between two sheaves as a matching distance between their graded barcodes. This enables us to conclude in this setting that the convolution distance is closed, and that the collec-tion of constructible sheaves over R equipped with the convolution distance is locally path-connected. Then, we observe that the collection of zig-zag/level sets persistence modules associated to a real valued function carry extra structure, which we call Mayer-Vietoris systems. We classify all Mayer-Vietoris sys-tems under finiteness assumptions. This allows us to establish a functorial isometric correspondence bet-ween the derived category of constructible sheaves over R equipped with the convolution distance, and the category of strongly pfd Mayer-Vietoris systems endowed with the interleaving distance. We deduce from this result a way to compute barcodes of sheaves from already existing software.Finally, we give a purely sheaf theoretic definition of the notion of ephemeral persistence module. We prove that the observable category of persistence mo-dules (the quotient category of persistence modules by the sub-category of ephemeral ones) is equivalent to the well-known category of -sheaves

La recherche et les questions abordées dans cette thèse sont de type inverse : la reconstitution d'une source ponctuelle ou la complétion d'une donnée à la limite inconnue à l'extrémité du domaine dans les modèles paraboliques de transport de contaminants. La modélisation mathématique des problèmes de pollution des eaux fait intervenir deux traceurs, l'oxygène dissous (OD) et la demande biochimique en oxygène (DBO) qui est la quantité d'oxygène nécessaire à la biodégradation de la matière organique. En effet, au cours des procédés d'autoépuration, certaines bactéries aérobies jouent un rôle principal. Ces micro-organismes décomposent les matières organiques polluantes en utilisant l'oxygène dissous dans le milieu. Afin de compenser ces données manquantes, les champs, solutions du problème, sont observés directement ou indirectement. Les problèmes inverses qui en résultent sont quasi certainement mal-posés voire même sévèrement mal-posés pour la plupart. Dans cette thèse, nous proposons justement une analyse aussi poussée que possible sur la question de l'identifiabilité pour les deux problèmes inverses décrits ci-dessus. Nous avons démontré un résultat d'unicité pour des sources fixes dans le cas d'observations décalées. La réalité pour l'observation est nuancée et l'idéal n'est pas acquis ; des mesures directes sur la DBO sont difficiles à obtenir. En revanche collecter des données sur l'OD est possible en temps réel et avec un faible coût. La DBO est donc observée de façon indirecte, grâce au couplage dans le système de Streeter et Phelps, l'information passe de l'OD à la DBO. Pour ce problème aussi, nous avons produit un résultat d'unicité pour la reconstruction de la source ou puits ponctuel qui serait présent dans l'équation de transport sur l'OD. Nous avons ensuite examiné des questions annexes à l'identifiabilité telles que le degré d'instabilité des équations à résoudre. De ce type d'informations dépendent le comportement des méthodes numériques et des algorithmes de calcul à utiliser
The research and the questions approached on this thesis are inverse type : the reconstruction of point-wise source or the data completion problem in parabolic models of transport of contaminants. The mathematical modelling of the problems of water pollution includes two tracers, the dissolved oxygen (DO) and the biochemical demand in oxygen (BDO) which is the quantity of oxygen necessary for the biodegradation of organic matter. Indeed, during the biodegradation process, aerobic bacteria play a leading part. These micro-organisms decompose polluting organic matters by using the dissolved oxygen in the middle. To compensate these missing data, fields, solutions of the problem, are observed directly or indirectly. The resulting inverse problems are ill-posed. Their mathematical study rises big complications and their numerical treatment isn't easy. We demonstrated a uniqueness result for fixed sources in the case of moved observations. The reality for the observation is qualified and the ideal is not acquired; direct measures on the BOD are difficult to obtain. On the Other hand to collect data on the DO is possible in real time With a moderate cost. The BOD is thus observed in indirect way, thanks to the coupling in the system of Streeter and Phelps, the information passes from the DO to the BOD. For this problem, we produced a uniqueness result for the reconstruction of source. Then, we examined the degree of instability of the equation to be solved. The behaviour of numerical methods depend on this type of information

La quantité de données disponibles n'a jamais été aussi grande. Se poser les bonnes questions, c'est-à-dire des questions qui soient à la fois pertinentes et dont la réponse est accessible est difficile. L'analyse topologique de données tente de contourner le problème en ne posant pas une question trop précise mais en recherchant une structure sous-jacente aux données. Une telle structure est intéressante en soi mais elle peut également guider le questionnement de l'analyste et le diriger vers des questions pertinentes. Un des outils les plus utilisés dans ce domaine est l'homologie persistante. Analysant les données à toutes les échelles simultanément, la persistance permet d'éviter le choix d'une échelle particulière. De plus, ses propriétés de stabilité fournissent une manière naturelle pour passer de données discrètes à des objets continus. Cependant, l'homologie persistante se heurte à deux obstacles. Sa construction se heurte généralement à une trop large taille des structures de données pour le travail en grandes dimensions et sa robustesse ne s'étend pas au bruit aberrant, c'est-à-dire à la présence de points non corrélés avec la structure sous-jacente.Dans cette thèse, je pars de ces deux constatations et m'applique tout d'abord à rendre le calcul de l'homologie persistante robuste au bruit aberrant par l'utilisation de la distance à la mesure. Utilisant une approximation du calcul de l'homologie persistante pour la distance à la mesure, je fournis un algorithme complet permettant d'utiliser l'homologie persistante pour l'analyse topologique de données de petite dimension intrinsèque mais pouvant être plongées dans des espaces de grande dimension. Précédemment, l'homologie persistante a également été utilisée pour analyser des champs scalaires. Ici encore, le problème du bruit aberrant limitait son utilisation et je propose une méthode dérivée de l'utilisation de la distance à la mesure afin d'obtenir une robustesse au bruit aberrant. Cela passe par l'introduction de nouvelles conditions de bruit et l'utilisation d'un nouvel opérateur de régression. Ces deux objets font l'objet d'une étude spécifique. Le travail réalisé au cours de cette thèse permet maintenant d'utiliser l'homologie persistante dans des cas d'applications réelles en grandes dimensions, que ce soit pour l'inférence topologique ou l'analyse de champs scalaires
Massive amounts of data are now available for study. Asking questions that are both relevant and possible to answer is a difficult task. One can look for something different than the answer to a precise question. Topological data analysis looks for structure in point cloud data, which can be informative by itself but can also provide directions for further questioning. A common challenge faced in this area is the choice of the right scale at which to process the data.One widely used tool in this domain is persistent homology. By processing the data at all scales, it does not rely on a particular choice of scale. Moreover, its stability properties provide a natural way to go from discrete data to an underlying continuous structure. Finally, it can be combined with other tools, like the distance to a measure, which allows to handle noise that are unbounded. The main caveat of this approach is its high complexity.In this thesis, we will introduce topological data analysis and persistent homology, then show how to use approximation to reduce the computational complexity. We provide an approximation scheme to the distance to a measure and a sparsifying method of weighted Vietoris-Rips complexes in order to approximate persistence diagrams with practical complexity. We detail the specific properties of these constructions.Persistent homology was previously shown to be of use for scalar field analysis. We provide a way to combine it with the distance to a measure in order to handle a wider class of noise, especially data with unbounded errors. Finally, we discuss interesting opportunities opened by these results to study data where parts are missing or erroneous

La plupart des processus informatiques mettent en jeu la notion de transformation, en particulier la compilation. Nous nous intéressons dans cette thèse à fournir des outils et des méthodes, utilisant la réécriture, permettant d'accroître la confiance que l'on peut placer dans ces processus. Nous développons dans un premier temps un cadre permettant de valider la compilation de constructions de filtrage, produisant une preuve formelle de la validité de la compilation, ainsi qu'un témoin de cette preuve, à chaque exécution du compilateur. Afin de permettre l'écriture sûre de transformations complexes, nous proposons un générateur de structures de données efficaces intégrant des invariants algébriques, et un langage de stratégies permettant de contrôler l'application des transformations. Ces résultats constituent donc une avancée vers la constitution de methodes génériques sûres pour le développement de transformations de confiance
Most computer processes involve the notion of transformation, in particular the compilation processes. We interest in this thesis in providing tools and methods, based on rewriting, giving the opportunity to increase the confidence we can place into those processes. We develop first a framework used to validate the compilation of matching constructs, building a formal proof of the validity of the compilation process along with a witness of this proof, for each run of the compiler. Then, in order to allow one to write safely complex transformations, we propose a tool that generates an efficient data structure integrating algebraic invariants, as well as a strategy language that enables to control the application of transformations. Those results can be seen as a first step towards the constitution of generic and safe methods for the development of trustworthy transformations

Dans le cadre de l'apprentissage automatique, l'utilisation de représentations alternatives, ou descripteurs, pour les données est un problème fondamental permettant d'améliorer sensiblement les résultats des algorithmes. Parmi eux, les descripteurs topologiques calculent et encodent l'information de nature topologique contenue dans les données géométriques. Ils ont pour avantage de bénéficier de nombreuses bonnes propriétés issues de la topologie, et désirables en pratique, comme par exemple leur invariance aux déformations continues des données. En revanche, la structure et les opérations nécessaires à de nombreuses méthodes d'apprentissage, comme les moyennes ou les produits scalaires, sont souvent absents de l'espace de ces descripteurs. Dans cette thèse, nous étudions en détail les propriétés métriques et statistiques des descripteurs topologiques les plus fréquents, à savoir les diagrammes de persistance et Mapper. En particulier, nous montrons que le Mapper, qui est empiriquement un descripteur instable, peut être stabilisé avec une métrique appropriée, que l'on utilise ensuite pour calculer des régions de confiance et pour régler automatiquement ses paramètres. En ce qui concerne les diagrammes de persistance, nous montrons que des produits scalaires peuvent être utilisés via des méthodes à noyaux, en définissant deux noyaux, ou plongements, dans des espaces de Hilbert en dimension finie et infinie
In the context of supervised Machine Learning, finding alternate representations, or descriptors, for data is of primary interest since it can greatly enhance the performance of algorithms. Among them, topological descriptors focus on and encode the topological information contained in geometric data. One advantage of using these descriptors is that they enjoy many good and desireable properties, due to their topological nature. For instance, they are invariant to continuous deformations of data. However, the main drawback of these descriptors is that they often lack the structure and operations required by most Machine Learning algorithms, such as a means or scalar products. In this thesis, we study the metric and statistical properties of the most common topological descriptors, the persistence diagrams and the Mappers. In particular, we show that the Mapper, which is empirically instable, can be stabilized with an appropriate metric, that we use later on to conpute confidence regions and automatic tuning of its parameters. Concerning persistence diagrams, we show that scalar products can be defined with kernel methods by defining two kernels, or embeddings, into finite and infinite dimensional Hilbert spaces

La plupart des processus informatiques mettent en jeu la notion de transformation, en particulier la compilation. Nous nous intéressons dans cette thèse à fournir des outils et des méthodes, utilisant la réécriture, permettant d'accroître la confiance que l'on peut placer dans ces processus. Nous développons dans un premier temps un cadre permettant de valider la compilation de constructions de filtrage, produisant une preuve formelle de la validité de la compilation, ainsi qu'un témoin de cette preuve, à chaque exécution du compilateur. Afin de permettre l'écriture sûre de transformations complexes, nous proposons un générateur de structures de données efficaces intégrant des invariants algébriques, et un langage de stratégies permettant de contrôler l'application des transformations. Ces résultats constituent donc une avancée vers la constitution de methodes génériques sûres pour le développement de transformations de confiance
Most computer processes involve the notion of transformation, in particular the compilation processes. We interest in this thesis in providing tools and methods, based on rewriting, giving the opportunity to increase the confidence we can place into those processes. We develop first a framework used to validate the compilation of matching constructs, building a formal proof of the validity of the compilation process along with a witness of this proof, for each run of the compiler. Then, in order to allow one to write safely complex transformations, we propose a tool that generates an efficient data structure integrating algebraic invariants, as well as a strategy language that enables to control the application of transformations. Those results can be seen as a first step towards the constitution of generic and safe methods for the development of trustworthy transformations

Cette thèse explore deux territoires distincts de l’informatique fondamentale : la complexité et la compression. Plus précisément, dans une première partie, nous étudions la puissance des circuits arithmétiques non commutatifs, qui calculent des polynômes non commutatifs en plusieurs indéterminées. Pour cela, nous introduisons plusieurs modèles de calcul, restreints dans leur manière de calculer les monômes. Ces modèles en généralisent d’autres, plus anciens et largement étudiés, comme les programmes à branchements. Les résultats sont de trois sortes. Premièrement, nous donnons des bornes inférieures sur le nombre d’opérations arithmétiques nécessaires au calcul de certains polynômes tels que le déterminant ou encore le permanent. Deuxièmement, nous concevons des algorithmes déterministes fonctionnant en temps polynomial pour résoudre le problème du test d’identité polynomiale. Enfin, nous construisons un pont entre la théorie des automates et les circuits arithmétiques non commutatifs, ce qui nous permet de dériver de nouvelles bornes inférieures en utilisant une mesure reposant sur le rang de la matrice dite de Hankel, provenant de la théorie des automates. Une deuxième partie concerne l’analyse de l’algorithme de compression sans perte Lempel-Ziv. Pourtant très utilisé, sa stabilité est encore mal établie. Vers la fin des années 90s, Jack Lutz popularise la question suivante, connue sous le nom de « one-bit catastrophe » : « étant donné un mot compressible, est-il possible de le rendre incompressible en ne changeant qu’un seul bit ? ». Nous montrons qu’une telle catastrophe est en effet possible. Plus précisément, en donnant des bornes optimales sur la variation de la taille de la compression, nous montrons qu’un mot « très compressible » restera toujours compressible après modification d’un bit, mais que certains mots « peu compressibles » deviennent en effet incompressibles
This thesis explores two territories of computer science: complexity and compression. More precisely, in a first part, we investigate the power of non-commutative arithmetic circuits, which compute multivariate non-commutative polynomials. For that, we introduce various models of computation that are restricted in the way they are allowed to compute monomials. These models generalize previous ones that have been widely studied, such as algebraic branching programs. The results are of three different types. First, we give strong lower bounds on the number of arithmetic operations needed to compute some polynomials such as the determinant or the permanent. Second, we design some deterministic polynomial-time algorithm to solve the white-box polynomial identity problem. Third, we exhibit a link between automata theory and non-commutative arithmetic circuits that allows us to derive some old and new tight lower bounds for some classes of non-commutative circuits, using a measure based on the rank of a so-called Hankel matrix. A second part is concerned with the analysis of the data compression algorithm called Lempel-Ziv. Although this algorithm is widely used in practice, we know little about its stability. Our main result is to show that an infinite word compressible by LZ’78 can become incompressible by adding a single bit in front of it, thus closing a question proposed by Jack Lutz in the late 90s under the name “one-bit catastrophe”. We also give tight bounds on the maximal possible variation between the compression ratio of a finite word and its perturbation—when one bit is added in front of it

La programmation bi-niveau désigne une classe de problèmes d'optimisation emboîtés impliquant deux joueurs.Un joueur meneur annonce une décision à un joueur suiveur qui détermine sa réponse parmi l'ensemble des solutions d'un problème d'optimisation dont les données dépendent de la décision du meneur (problème de niveau bas).La décision optimale du meneur est la solution d'un autre problème d'optimisation dont les données dépendent de la réponse du suiveur (problème de niveau haut).Lorsque la réponse du suiveur n'est pas unique, on distingue les problèmes bi-niveaux optimistes et pessimistes,suivant que la réponse du suiveur soit respectivement la meilleure ou la pire possible pour le meneur.Les problèmes bi-niveaux sont souvent utilisés pour modéliser des problèmes de tarification. Dans les applications étudiées ici, le meneur est un vendeur qui fixe un prix, et le suiveur modélise le comportement d'un grand nombre de clients qui déterminent leur consommation en fonction de ce prix. Le problème de niveau bas est donc de grande dimension.Cependant, la plupart des problèmes bi-niveaux sont NP-difficiles, et en pratique, il n'existe pas de méthodes générales pour résoudre efficacement les problèmes bi-niveaux de grande dimension.Nous introduisons ici une nouvelle approche pour aborder la programmation bi-niveau.Nous supposons que le problème de niveau bas est un programme linéaire, en variables continues ou discrètes,dont la fonction de coût est déterminée par la décision du meneur.Ainsi, la réponse du suiveur correspond aux cellules d'un complexe polyédral particulier,associé à une hypersurface tropicale.Cette interprétation est motivée par des applications récentes de la géométrie tropicale à la modélisation du comportement d'agents économiques.Nous utilisons la dualité entre ce complexe polyédral et une subdivision régulière d'un polytope de Newton associé pour introduire une méthode dedécomposition qui résout une série de sous-problèmes associés aux différentes cellules du complexe.En utilisant des résultats portant sur la combinatoire des subdivisions, nous montrons que cette décomposition mène à un algorithme permettant de résoudre une grande classe de problèmes bi-niveaux en temps polynomial en la dimension du problème de niveau bas lorsque la dimension du problème de niveau haut est fixée.Nous identifions ensuite des structures spéciales de problèmes bi-niveaux pour lesquelles la borne de complexité peut être améliorée.C'est en particulier le cas lorsque la fonction coût du meneur ne dépend que de la réponse du suiveur.Ainsi, nous montrons que la version optimiste du problème bi-niveau peut être résolue en temps polynomial, notammentpour des instancesdans lesquelles les données satisfont certaines propriétés de convexité discrète.Nous montrons également que les solutions de tels problèmes sont des limites d'équilibres compétitifs.Dans la seconde partie de la thèse, nous appliquons cette approche à un problème d'incitation tarifaire dans les réseaux mobiles de télécommunication.Les opérateurs de données mobiles souhaitent utiliser des schémas de tarification pour encourager les différents utilisateurs à décaler leur consommation de données mobiles dans le temps, et par conséquent dans l'espace (à cause de leur mobilité), afin de limiter les pics de congestion.Nous modélisons cela par un problème bi-niveau de grande taille.Nous montrons qu'un cas simplifié peut être résolu en temps polynomial en utilisant la décomposition précédente,ainsi que des résultats de convexité discrète et de théorie des graphes.Nous utilisons ces idées pour développer une heuristique s'appliquant au cas général.Nous implémentons et validons cette méthode sur des données réelles fournies par Orange
Bilevel programming deals with nested optimization problems involving two players. A leader annouces a decision to a follower, who responds by selecting a solution of an optimization problem whose data depend on this decision (low level problem). The optimal decision of the leader is the solution of another optimization problem whose data depend on the follower's response (high level problem). When the follower's response is not unique, one distinguishes between optimistic and pessimistic bilevel problems, in which the leader takes into account the best or worst possible response of the follower.Bilevel problems are often used to model pricing problems.We are interested in applications in which the leader is a seller who announces a price, and the follower models the behavior of a large number of customers who determine their consumptions depending on this price.Hence, the dimension of the low-level is large. However, most bilevel problems are NP-hard, and in practice, there is no general method to solve efficiently large-scale bilevel problems.In this thesis, we introduce a new approach to tackle bilevel programming. We assume that the low level problem is a linear program, in continuous or discrete variables, whose cost function is determined by the leader. Then, the follower responses correspond to the cells of a special polyhedral complex, associated to a tropical hypersurface. This is motivated by recent applications of tropical geometry to model the behavior of economic agents.We use the duality between this polyhedral complex and a regular subdivision of an associated Newton polytope to introduce a decomposition method, in which one solves a series of subproblems associated to the different cells of the complex. Using results about the combinatorics of subdivisions, we show thatthis leads to an algorithm to solve a wide class of bilevel problemsin a time that is polynomial in the dimension of the low-level problem when the dimension of the high-level problem is fixed.Then, we identify special structures of bilevel problems forwhich this complexity bound can be improved.This is the case when the leader's cost function depends only on the follower's response. Then, we showthe optimistic bilevel problem can be solved in polynomial time.This applies in particular to high dimensional instances in which the datasatisfy certain discrete convexity properties. We also show that the solutions of such bilevel problems are limits of competitive equilibria.In the second part of this thesis, we apply this approach to a price incentive problem in mobile telecommunication networks.The aim for Internet service providers is to use pricing schemes to encourage the different users to shift their data consumption in time(and so, also in space owing to their mobility),in order to reduce the congestion peaks.This can be modeled by a large-scale bilevel problem.We show that a simplified case can be solved in polynomial time by applying the previous decomposition approach together with graph theory and discrete convexity results. We use these ideas to develop an heuristic method which applies to the general case. We implemented and validated this method on real data provided by Orange

Le but de ce travail est d’étendre la théorie de Bruhat-Tits au cas des groupes de Kac-Moody sur des corps locaux. Il s’agit donc de définir un espace géométrique sur lequel un tel groupe agit, semblable à l’immeuble de Bruhat-Tits d’un groupe réductif. En fait, la première partie reste dans le cadre de la théorie de Bruhat-Tits puisqu’on y définit une famille de compactification des immeubles affines. C’est dans la seconde partie qu’en s’inspirant de la construction de la première, on aborde le cas des groupes de Kac-Moody. Les espaces obtenus ne vérifient pas toutes les conditions demandées à un immeuble, ils sont donc appelés des masures (bordées)
This work aims at generalizing Bruhat-Tits theory to Kac-Moody groups over local fields. We thus try to construct a geometric space on wich such a group will act, and wich will look like the Bruhat-Tits building of a reductive group. Actually, the first part stays in the field of Bruhat-Tits theory as it exposes a family of compactification of an ordinary affine building. It is in the second part that we move to Kac-Moody theory, using the first part as a guide. The spaces obtained do not satisfy all the requirement for a building,they will be called (bounded) hovels (”masures” in french)

Il est bien connu que des constructions théoriques très simples telles que les structures Either (équivalent type théorique de l'opérateur logique "ou"), State (représentant des transformateurs d'état composables), Applicative (application des fonctions généralisée) et Monad (composition de programmes séquentielles généralisée), nommés structures en Haskell, couvrent une grande partie de ce qui est habituellement nécessaire pour exprimer avec élégance la plupart des idiomes informatiques utilisés dans les programmes classiques. Cependant, il est usuellement admis qu'il existe plusieurs classes d'idiomes couramment utilisés qui ne s'intègrent pas bien à ces structures, les exemples les plus remarquables étant les transformations entre arbres (types de données, dont l'utilisation doit s'appuyer soit sur les motifs généralisés soit sur une infrastructure de méta programmation lourde) et traitement des exceptions (qui sont d'habitude supposés nécessiter un langage spécial et une prise en charge de l'exécution). Ce travail a pour but de montrer que beaucoup de ces idiomes peuvent, en fait, être exprimés en réutilisant ces structures bien connues avec des modifications mineures (le cas échéant). En d'autres termes, le but de ce travail est d'appliquer les principes du rasoir KISS (Keep It Stupid Simple) et/ou d'Occam aux structures algébriques utilisées pour résoudre des problèmes de programmation courants. Techniquement parlant, ce travail a pour but de montrer que les généralisations naturelles de classes de types Applicative et Monad de Haskell, associées à la possibilité d'en faire des produits cartésiens, en produisent un cadre commun très simple pour exprimer de nombreuses choses pratiques, dont certaines sont des nouvelles méthodes très commodes pour exprimer des idées de programmation communes, tandis que les autres peuvent être vues comme systèmes d'effets. Sur ce dernier point, si l'on veut généraliser des exemples présentés dans une approche de la conception de systèmes d'effets en général, on peut alors considérer la structure globale de cette approche comme un cadre quasi syntaxique qui permet d'ériger une structure générale du cadre "mariage" au dessus de différents systèmes d'effets adhérant aux principes de base. (Bien que ce travail ne soit pas trop approfondi dans la dernière, car il est principalement motivé par des exemples qui peuvent être immédiatement appliqués à la pratique de Haskell.) Il convient toutefois de noter qu'en fait, ces observations techniques n'ont rien d'étonnant: Applicative et Monad sont respectivement des généralisations de composition fonctionnelle et linéaire des programmes; ainsi, naturellement, les produits cartésiens de ces deux structures doivent couvrir en grande partie ce que les programmes font habituellement
It is well-known that very simple theoretic constructs such as Either (type-theoretic equivalent of the logical "or" operator), State (composable state transformers), Applicative (generalized function application), and Monad (generalized sequential program composition) structures (as they are named in Haskell) cover a huge chunk of what is usually needed to elegantly express most computational idioms used in conventional programs. However, it is conventionally argued that there are several classes of commonly used idioms that do not fit well within those structures, the most notable examples being transformations between trees (data types, which are usually argued to require ether generalized pattern matching or heavy metaprogramming infrastructure) and exception handling (which are usually argued to require special language and run-time support). This work aims to show that many of those idioms can, in fact, be expressed by reusing those well-known structures with minor (if any) modifications. In other words, the purpose of this work is to apply the KISS (Keep It Stupid Simple) and/or Occam's razor principles to algebraic structures used to solve common programming problems. Technically speaking, this work aims to show that natural generalizations of Applicative and Monad type classes of Haskell combined with the ability to make Cartesian products of them produce a very simple common framework for expressing many practically useful things, some of the instances of which are very convenient novel ways to express common programming ideas, while others are usually classified as effect systems. On that latter point, if one is to generalize the presented instances into an approach to design of effect systems in general, then the overall structure of such an approach can be thought of as being an almost syntactic framework which allows different effect systems adhering to the general structure of the "marriage" framework to be expressed on top of. (Though, this work does not go into too much into the latter, since this work is mainly motivated by examples that can be immediately applied to Haskell practice.) Note, however, that, after the fact, these technical observation are completely unsurprising: Applicative and Monad are generalizations of functional and linear program compositions respectively, so, naturally, Cartesian products of these two structures ought to cover a lot of what programs usually do

Cette thèse s’adresse au problème du maillage d’une variété donnée dans une dimension arbitraire. Intuitivement, on peut supposer que l’on s'est donné une variété — par exemple l’intérieur d’un tore plongé dans R9, et notre objectif est de construire un maillage de cette variété (par exemple une triangulation). Nous proposons trois contributions principales. La première est l’algorithme du tracé des variétés qui reconstruit un complexe cellulaire approchant une variété compacte et lisse de dimension m dans l’espace Euclidien Rd, pour m et d arbitraires. L’algorithme proposé utilise une triangulation T qui est supposé être une transformation linéaire de la triangulation de Freudenthal-Kuhn de Rd. La complexité dépend linéairement de la taille de la sortie dont chaque élément est calculé en temps seulement polynomial en la dimension ambiante d. Cet algorithme nécessite que la variété soit connue par un oracle d’intersection qui répond si un simplexe (d−m)-dimensionnel donné intersecte la variété. À ce titre, ce cadre est général et couvre plusieures représentations des variétés populaires, telles que le niveau d’une fonction multivariée ou les variétés données par un nuage de points. Notre deuxième contribution est une structure de données qui représente la triangulation de Freudenthal-Kuhn de Rd. À chaque étape de l’exécution, l’espace utilisé par la structure de données est au plus O(d2). La structure de données supporte plusieurs opérations d’une manière efficace telles que la localisation d’un point dans la triangulation et accès aux faces et cofaces d’un simplexe donné. Les simplexes dans une triangulation de Freudenthal-Kuhn de Rd sont encodés par une nouvelle représentation qui généralise celle de Freudenthal pour les simplexes d-dimensionels. Enfin, nous étudions la géométrie et la combinatoire des deux types de triangulations étroitement liés : des triangulations de Freudenthal-Kuhn et des triangulations de Coxeter. Pour les triangulations de Coxeter, on démontre que la qualité des simplexes d-dimensionels est O(1/ \sqrt{d}) comparé au simplexe régulier. Par ailleurs, nous établissons lesquelles des triangulations sont de Delaunay. Nous considérons aussi l’extension de la propriété d’être Delaunay qui s’appelle la protection et qui mesure la généricité de la triangulation de Delaunay. En particulier, nous montrons qu’une famille de triangulations de Coxeter atteint la protection O(1/d2). Nous proposons une conjecture que les deux bornes sont optimales pour les triangulations de l’espace Euclidien
This thesis addresses the manifold meshing problem in arbitrary dimension. Intuitively, suppose we are given a manifold — such as the interior of a torus — embedded in a space like R9, our goal is to build a mesh of this manifold (for example, a triangulation). We propose three principal contributions. The central one is the manifold tracing algorithm, which constructs a piecewise-linear approximation of a given compact smooth manifold of dimension m in the Euclidean space Rd, for any m and d. The proposed algorithm operates in an ambient triangulation T that is assumed to be an affine transformation of the Freudenthal-Kuhn triangulation of Rd. It is output-sensitive and its time complexity per computed element in the output depends only polynomially on the ambient dimension d. It only requires the manifold to be accessed via an intersection oracle that answers if a given (d − m)-dimensional simplex in Rd intersects the manifold or not. As such, this framework is general, as it covers many popular manifold representations such as the level set of a multivariate function or manifolds given by a point cloud. Our second contribution is a data structure that represents the Freudenthal-Kuhn triangulation of Rd. At any moment during the execution, this data structure requires at most O(d2) storage. With this data structure, we can access in a time-efficient way the simplex that contains a given point, the faces and the cofaces of a given simplex. The simplices in the Freudenthal-Kuhn triangulation of Rd are encoded using a new representation that generalizes the representation of the d-dimensional simplices introduced by Freudenthal. Lastly, we provide a geometrical and combinatorial study of the Freudenthal-Kuhn triangulations and the closely-related Coxeter triangulations. For Coxeter triangulations, we establish that the quality of the simplices in all d-dimensional Coxeter triangulations is O(1/sqrt{d}) of the quality of the d-dimensional regular simplex. We further investigate the Delaunay property for Coxeter triangulations. Finally, we consider an extension of the Delaunay property, namely protection, which is a measure of non-degeneracy of a Delaunay triangulation. In particular, one family of Coxeter triangulations achieves the protection O(1/d2). We conjecture that both bounds are optimal for triangulations in Euclidean space

La théorie des immeubles propose d'associer à certains groupes un espace topologique, appelé immeuble, sur lequel le groupe agit. Ceci permet de traduire les propriétés algébriques du groupe en des propriétés géométriques de l'immeuble, facilitant nombre de raisonnements. Les immeubles dits affines forment une famille importante d'immeubles, ils ont étés introduit par François Bruhat et Jacques Tits. Ils sont associés aux groupes réductifs sur des corps locaux et permettent notamment de caractériser leurs sous-groupes compacts. Le but premier de cette thèse est d'étendre la théorie de Bruhat et Tits à des groupes de Kac-Moody, qui sont une généralisation en dimension infinie des groupes réductifs. Nous essayerons donc, partant d'un tel groupe G sur un corps local de définir un espace topologique I aussi proche que possible d'un immeuble. Il semble impossible d'obtenir véritablement un immeuble affine, les espaces que nous trouverons seront appelés des "masures". Une méthode récurrente lors de ce travail sera d'isoler des sous-groupes de G, dits "paraboliques", qui sont de dimension finie, et auxquels la théorie de Bruhat et Tits s'applique donc. Ils disposent donc de véritables immeubles affines, et ceux-ci peuvent être vus comme un bord à l'infini de la masure. Dans le cas où G est un groupe réductif, la réunion de tous ces immeubles affines à l'infini fournit une compactification de l'immeuble de G appelé compactification polyédrique, ou de Satake. L'étude de cette compactification est l'objet d'une première partie de cette thèse.

La réduction des informations redondantes et/ou non-pertinentes dans la description de données est une étape importante dans plusieurs domaines scientifiques comme les statistiques, la vision par ordinateur, la fouille de données ou l’apprentissage automatique. Dans ce manuscrit, nous abordons la réduction de la taille des signatures des images par une méthode issue de l’Analyse Formelle de Concepts (AFC), qui repose sur la structure du treillis des concepts et la théorie des treillis. Les modèles de sac de mots visuels consistent à décrire une image sous forme d’un ensemble de mots visuels obtenus par clustering. La réduction de la taille des signatures des images consiste donc à sélectionner certains de ces mots visuels. Dans cette thèse, nous proposons deux algorithmes de sélection d’attributs (mots visuels) qui sont utilisables pour l’apprentissage supervisé ou non. Le premier algorithme, RedAttSansPerte, ne retient que les attributs qui correspondent aux irréductibles du treillis. En effet, le théorème fondamental de la théorie des treillis garantit que la structure du treillis des concepts est maintenue en ne conservant que les irréductibles. Notre algorithme utilise un graphe d’attributs, le graphe de précédence, où deux attributs sont en relation lorsque les ensembles d’objets à qui ils appartiennent sont inclus l’un dans l’autre. Nous montrons par des expérimentations que la réduction par l’algorithme RedAttsSansPerte permet de diminuer le nombre d’attributs tout en conservant de bonnes performances de classification. Le deuxième algorithme, RedAttsFloue, est une extension de l’algorithme RedAttsSansPerte. Il repose sur une version approximative du graphe de précédence. Il s’agit de supprimer les attributs selon le même principe que l’algorithme précédent, mais en utilisant ce graphe flou. Un seuil de flexibilité élevé du graphe flou entraîne mécaniquement une perte d’information et de ce fait une baisse de performance de la classification. Nous montrons par des expérimentations que la réduction par l’algorithme RedAttsFloue permet de diminuer davantage l’ensemble des attributs sans diminuer de manière significative les performances de classification
In several scientific fields such as statistics, computer vision and machine learning, redundant and/or irrelevant information reduction in the data description (dimension reduction) is an important step. This process contains two different categories : feature extraction and feature selection, of which feature selection in unsupervised learning is hitherto an open question. In this manuscript, we discussed about feature selection on image datasets using the Formal Concept Analysis (FCA), with focus on lattice structure and lattice theory. The images in a dataset were described as a set of visual words by the bag of visual words model. Two algorithms were proposed in this thesis to select relevant features and they can be used in both unsupervised learning and supervised learning. The first algorithm was the RedAttSansPerte, which based on lattice structure and lattice theory, to ensure its ability to remove redundant features using the precedence graph. The formal definition of precedence graph was given in this thesis. We also demonstrated their properties and the relationship between this graph and the AC-poset. Results from experiments indicated that the RedAttsSansPerte algorithm reduced the size of feature set while maintaining their performance against the evaluation by classification. Secondly, the RedAttsFloue algorithm, an extension of the RedAttsSansPerte algorithm, was also proposed. This extension used the fuzzy precedence graph. The formal definition and the properties of this graph were demonstrated in this manuscript. The RedAttsFloue algorithm removed redundant and irrelevant features while retaining relevant information according to the flexibility threshold of the fuzzy precedence graph. The quality of relevant information was evaluated by the classification. The RedAttsFloue algorithm is suggested to be more robust than the RedAttsSansPerte algorithm in terms of reduction

Os workflows científicos emergiram como uma abstração básica para estruturar experimentos científicos baseados em simulações computacionais. Em muitas situações, estes workflows são intensivos, seja computacionalmente seja quanto em relação à manipulação de dados, exigindo a execução em ambientes de processamento de alto desempenho. Entretanto, paralelizar a execução de workflows científicos requer programação trabalhosa, de modo ad hoc e em baixo nível de abstração, o que torna difícil a exploração das oportunidades de otimização. Visando a abordar o problema de otimizar a execução paralela de workflows científicos, esta tese propõe uma abordagem algébrica para especificar o workflow, bem como um modelo de execução que, juntos, possibilitam a otimização automática da execução paralela de workflows científicos. A tese apresenta uma avaliação ampla da abordagem usando tanto experimentos reais quanto dados sintéticos. Os experimentos foram avaliados no Chiron, um motor de execução de workflows desenvolvido para apoiar a execução paralela de workflows científicos. Os experimentos apresentaram resultados excelentes de paralelização na execução de workflows e evidenciaram, com a abordagem algébrica, diversas possibilidades de otimização de desempenho quando comparados a execuções paralelas de workflow de modo ad hoc.