Littérature scientifique sur le sujet « Données algébriques »

Une conséquence de la classification des théories complètes d'algèbres de Boole par Tarski [5] est que la théorie élémentaire d'une algèbre de Boole A est déterminée par le type d'isomorphisme du treillis de ses idéaux définissables et, pour chacun de ces idéaux, par le nombre d'atomes du quotient de A par cet idéal lorsque ce nombre est fini. Une remarque analogue peut être faite à propos des cas particuliers d'algèbres de Boole munies d'un idéal distingué étudiés par Ershov [1] et par Jurie et Touraille [3]; dans to us ces cas, c'est la simplicité des treillis possibles qui permet la classification des théories complètes. Le résultat principal de cet article est que, dans le cas général d'une algèbre de Boole munie d'une famille quelconque d'idéaux distingués, la théorie d'un modèle peut encore être caractérisée grâce à une structure algébrique sur l'ensemble de ses idéaux définissables. Il s'agit d'une structure d'algèbre de Heyting munie d'une opération unaire sa définie par sa(K) = {a: a/K est sans atome}, et cette structure s'avère être engendrée par les idéaux distingués du modèle. La méthode utilisée est l'élimination directe des quantificateurs, par réductions successives des formules. Elle nécessite des propriétés algébriques et topologiques qui sont données aux §§1 et 2: on introduit au §1 la notion d'algèbre de Heyting étoilée, c'est-à-dire d'algèbre de Heyting munie d'une opération unaire * vérifiant des égalités qui permettent de rendre compte, d'une certaine façon, de la dérivation de Cantor-Bendixon; le §2 est consacré à des propriétés topologiques qui, dans le cas de l'espace de Stone d'une algèbre de Boole A, permettent d'éclaircir les relations possibles entre les atomes des quotients de A par des idéaux différents.

On sait que par le choix d’ un langage suffisamment complexe, toute structure peut admettre une élimination des quantificateurs, malheureusement cette extension du langage peut nous éloigner des phénomènes algébriques. Nous allons nous intéresser à l’ élimination des quantificateurs pour des paires de corps. Dans le cas des paires de corps algébriquement clos et des paires denses de corps réel clos, on obtient une élimination en ajoutant au langage des prédicats ayant une signification algébrique: on peut les exprimer en disant que pour deux ensembles algébriques et donnés, il existe des points du sous-corps rationnels pour et pas pour , ou qu’ un ensemble semi-algébrique donné a des points rationnels sur le sous-corps. Robinson avait déjà abordé de façon informelle le cas des paires denses de corps réel-clos (cf. [Ro 2, p. 198]). Partant du langage des paires de corps ordonnés, enrichi de symboles de relations correspondant à l’ indépendance algébrique, il proposait d’ ajouter pas à pas des fonctions de Skolem Herbrand pour faire disparaitre les quantificateurs existentiels des formules, mais sans préciser le langage obtenu. Ici nous approchons le problème différemment en explicitant dès le départ le langage utilisé.Grâce à ces résultats nous pourrons étudier le cas des paires séparées de corps réels clos ainsi que des paires de corps valués henseliens. En élargissant la définition d’ ensemble algébrique à tous les symboles du langage, les prédicats relationnels ajoutés ont la même signification que dans le cas des paires de corps algébriquement clos.En comparant les techniques employées ici avec celles déjà utilisées dans [K], [B], [D 1] et [L], on remarque qu’il est possible de traîter une grande partie de l’ étude (complétude, modèle complétude, élimination des quantificateurs) des paires de corps algébriquement clos, réel-clos ou henseliens en se basant sur des prolongements d’ isomorphismes entre sous-structures dénombrables où l’ une des deux est contenue dans une structure ω1-saturée.

RésuméCet article vise à restituer la doctrine du « signe du manifeste au caché » d'Abū Hāšim al-Ğubbāʾī (888-933). Il montre qu'Abū Hāšim a tendu à interpréter ce signe comme une inférence, dont il a reconnu deux types principaux : le type-1 (la « communauté de preuve », al-ištirāk fī al-dalāla) procède par déduction analytique de concepts en neutralisant les conditions de réalisation de ces derniers, c'est-à-dire leur soubassement ontologique. C'est, typiquement, la procédure la plus directement consonante avec l'ontologie modale d'Abū Hāšim. Le type-2 (la « communauté de cause », al-ištirāk fī al-ʿilla) exhibe un même rapport de causalité au plan du connu et au plan de l'inconnu et considère que la causalité au plan du connu est elle-même la cause de la causalité au plan de l'inconnu. Cette partition parfaitement inédite dans la philosophie et le kalām est en revanche préfigurée dans la doctrine de la preuve exposée par al-Ḫwārizmī dans son Algèbre. Al-Ḫwārizmī distingue en effet entre la preuve « par la cause » (bi-al-ʿilla), qui consiste à transférer une certaine déduction géométrique au plan de l'algèbre et la preuve « par l'expression » (bi-al-lafẓ) qui opère directement sur les expressions algébriques, qu'elle réduit analytiquement. En se fondant sur un texte d'Abū Hāšim consacré à la connaissance humaine qui paraît se référer à l’œuvre d'al-Ḫwārizmī, l'article suggère pour finir que le parallèle conceptuel étroit entre la doctrine de la preuve d'al-Ḫwārizmī et la doctrine du signe d'Abū Hāšim pourrait ne pas être une simple coïncidence. Deux appendices ont été ajoutés. Le premier traite de la lecture par al-Fārābī de la théorie de l'inférence d'Abū Hāšim. Le second, en s'appuyant sur toutes les données disponibles, établit pour la première fois les dates correctes et précises de la vie d'Abū Hāšim.

Soient $K$ un corps commutatif et $G$ un groupe abélien totalement ordonné. Nous donnons des moyens de construction d'éléments algébriques sur le corps $K((G))$ des séries fomelles généralissées à supports bien ordonnés.

Le rêve secret de tout logicien, c’est de prouver un résultat mathématique significatif avec des moyens de fortune; ce rêve se réalise parfois de manière quelque peu biaisée, le théorème obtenu n’étant qu’une version trop simplifiée, ou bien trop adaptée aux besoins de la logique, pour convaincre un mathématicien normal. C’est pour cela que j’annonce d’emblée la couleur, et que je précise les règles du jeu: la version du théorème de Borel-Tits que je vais montrer, concernant les groupes algébriques simples sur un corps de base algébriquement clos, sera considérée comme pratiquement évidente par un géomètre; mais c’est, à mon avis, la seule qui ait un intérêt pour un théoricien des modèles.Quand on entreprend ainsi de redémontrer une version simple d’un résultat par ailleurs bien connu, le seul intérêt est dans la méthode: ce que je veux, ici, c’est présenter une preuve qui n’utilise aucune information, ou presque, sur la structure algébrique de ces groupes; il est même souhaitable d’oublier qu’il s’agit de groupes linéaires! Elle repose sur des résultats généraux concernant les groupes de rang de Morley fini, dus à divers auteurs, dont le principal, Boris Iosifovič Zil′ber, a déjà fait une tentative similaire [Zil′ber 1984]; je poursuis ici cette tentative, mais en me limitant à des arguments encore moins spécifiques au contexte de la géométrie.Si je fais ainsi, ce n’est pas pour donner l’impression que l’unique ambition de la théorie des modèles est de montrer des résultats triviaux par des méthodes triviales.

L’objectif de ce travail a été d’analyser les interactions verbales élèves-enseignantes mettant en évidence le rôle du langage dans le développement de la pensée algébrique dans une perspective historico-culturelle. Les interactions ont eu lieu grâce à des tâches dont la construction se basait sur la perception des régularités dans des suites non numériques. Cette recherche a été réalisée dans le cadre d’un partenariat entre des enseignantes de l’école primaire et des chercheurs associés à un master académique. Elle a été développée en contexte réel avec 29 élèves (8-9 ans) de 3e année de l’école primaire. Les données recueillies montrent que les interactions verbales élèves-enseignantes favorisent le développement de la pensée algébrique sans l’introduction du langage mathématique (Mason, 2007; Radford, 2013, 2014).

Nous prouvons que tout semigroupe fini est quotient d'un semigroupe fini dans lequel les stabilisateurs droits satisfont les identités x = x2 et xy = xyx. Ce resultat a plusieurs consé-quences. Tout d'abord, nous l'utilisons, en même temps qu'un résultat de I. Simon sur les congruences de chemins, pour obtenir une preuve purement algébrique d'un théorème profond de McNaughton sur les mots infinis. Puis, nous donnons une preuve algébrique d'un théorème de Brown sur des conditions de finitude pour les semigroupes. We show that every finite semigroup is a quotient of a finite semigroup in which every right stabilizer satisfies the identities x = x2 and xy = xyx. This result has several consequences. We first use it together with a result of I. Simon on congruences on paths to obtain a purely algebraic proof of a deep theorem of McNaughton on infinite words. Next, we give an algebraic proof of a theorem of Brown on a finiteness condition for semigroups.

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 problème d'identification de systèmes inconnus à partir d'échantillons de comportement est complexe car sa solution n'est pas unique et dépend des données. Les informations préalables sur le système facilitent l'identification en restreignant les modèles possibles. Les méthodes s'appuient sur des résultats algébriques et statistiques, notamment le schéma de Frisch, étendu aux systèmes dynamiques.

Abstract Nous donnons ici des minorations de la distance entre des points rationnels distincts d’une variété abélienne. Ces minorations impliquent une majoration de la hauteur des points rationnels de dénominateurs homes sur une courbe algebrique de genre 1 (cf. le théoréme 3.1). Nos résultats donnent alors une version quantitative du theoreme de Siegel sur la finitude des points entiers de telle courbe.