Добірка наукової літератури з теми "Structures algébriques finies"

Cette thèse contribue à une recherche de modèles finis et à la démonstration automatisée de théorèmes, en se concentrant principalement, mais sans s'y limiter, sur les méthodes d'intelligence artificielle. Dans la première partie, nous résolvons une question de recherche ouverte à partir de l'algèbre abstraite en utilisant une recherche automatisée de modèles finis massivement parallèles, en utilisant l'assistant de preuve Isabelle. À savoir, nous établissons l'indépendance de certaines lois de distributivité abstraites dans les binaires résiduels dans le cas général. En tant que sous-produit de cette découverte, nous apportons un client Python au serveur Isabelle. Le client a déjà trouvé son application dans les travaux d'autres chercheurs et de l'enseignement supérieur. Dans la deuxième partie, nous proposons une architecture de réseau neuronal génératif pour produire des modèles finis de structures algébriques appartenant à une variété donnée d'une manière inspirée des modèles de génération d'images tels que les GAN (réseaux antagonistes génératifs) et les autoencodeurs. Nous contribuons également à un paquet Python pour générer des semi-groupes finis de petite taille comme implémentation de référence de la méthode proposée. Dans la troisième partie, nous concevons une architecture générale de guidage des vérificateurs de saturation avec des algorithmes d'apprentissage par renforcement. Nous contribuons à une collection d'environnements compatibles OpenAI Gym pour diriger Vampire et iProver et démontrons sa viabilité sur des problèmes sélectionnés de la bibliothèque TPTP (Thousand of Problems for Theorem Provers). Nous contribuons également à une version conteneurisée d'un modèle ast2vec existant et montrons son applicabilité à l'incorporation de formules logiques écrites sous la forme clausal-normale. Nous soutenons que l'approche modulaire proposée peut accélérer considérablement l'expérimentation de différentes représentations de formules logiques et de schémas de génération de preuves synthétiques à l'avenir, résolvant ainsi le problème de la rareté des données, limitant notoirement les progrès dans l'application des techniques d'apprentissage automatique pour la démonstration automatisée de théorèmes
This thesis contributes to a finite model search and automated theorem proving, focusing primarily but not limited to artificial intelligence methods. In the first part, we solve an open research question from abstract algebra using an automated massively parallel finite model search, employing the Isabelle proof assistant. Namely, we establish the independence of some abstract distributivity laws in residuated binars in the general case. As a by-product of this finding, we contribute a Python client to the Isabelle server. The client has already found its application in the work of other researchers and higher education. In the second part, we propose a generative neural network architecture for producing finite models of algebraic structures belonging to a given variety in a way inspired by image generation models such as GANs (generative adversarial networks) and autoencoders. We also contribute a Python package for generating finite semigroups of small size as a reference implementation of the proposed method. In the third part, we design a general architecture of guiding saturation provers with reinforcement learning algorithms. We contribute an OpenAI Gym-compatible collection of environments for directing Vampire and iProver and demonstrate its viability on select problems from the Thousands of Problems for Theorem Provers (TPTP) library. We also contribute a containerised version of an existing ast2vec model and show its applicability to embedding logical formulae written in the clausal-normal form. We argue that the proposed modular approach can significantly speed up experimentation with different logic formulae representations and synthetic proof generation schemes in future, thus addressing the data scarcity problem, notoriously limiting the progress in applying the machine learning techniques for automated theorem proving

Cette thèse porte sur la théorie des modèles des structures pseudo-finies en mettant l’accent sur les groupes et les corps. Le but est d'approfondir notre compréhension des interactions entre les dimensions de comptage pseudo-finies et les propriétés algébriques de leurs structures sous-jacentes, ainsi que de la classification de certaines classes de structures en fonction de leurs dimensions. Notre approche se fait par l'étude d'exemples. Nous avons examiné trois classes de structures. La première est la classe des H-structures, qui sont des expansions génériques. Nous avons donné une construction explicite de H-structures pseudo-finies comme ultraproduits de structures finies. Le deuxième exemple est la classe des corps aux différences finis. Nous avons étudié les propriétés de la dimension pseudo-finie grossière de cette classe. Nous avons montré qu'elle est définissable et prend des valeurs entières, et nous avons trouvé un lien partiel entre cette dimension et le degré de transcendance transformelle. Le troisième exemple est la classe des groupes de permutations primitifs pseudo-finis. Nous avons généralisé le théorème classique de classification de Hrushovski pour les groupes stables de permutations d'un ensemble fortement minimal au cas où une dimension abstraite existe, cas qui inclut à la fois les rangs classiques de la théorie des modèles et les dimensions de comptage pseudo-finies. Dans cette thèse, nous avons aussi généralisé le théorème de Schlichting aux sous-groupes approximatifs, en utilisant une notion de commensurabilité
This thesis is about the model theory of pseudofinite structures with the focus on groups and fields. The aim is to deepen our understanding of how pseudofinite counting dimensions can interact with the algebraic properties of underlying structures and how we could classify certain classes of structures according to their counting dimensions. Our approach is by studying examples. We treat three classes of structures: The first one is the class of H-structures, which are generic expansions of existing structures. We give an explicit construction of pseudofinite H-structures as ultraproducts of finite structures. The second one is the class of finite difference fields. We study properties of coarse pseudofinite dimension in this class, show that it is definable and integer-valued and build a partial connection between this dimension and transformal transcendence degree. The third example is the class of pseudofinite primitive permutation groups. We generalise Hrushovski's classical classification theorem for stable permutation groups acting on a strongly minimal set to the case where there exists an abstract notion of dimension, which includes both the classical model theoretic ranks and pseudofinite counting dimensions. In this thesis, we also generalise Schlichting's theorem for groups to the case of approximate subgroups with a notion of commensurability

Étant donné un ensemble fini de tuiles carrés, le problème du domino est la question : «est-il possible de paver le plan entier en utilisant ces tuiles ?» Ce problème est connu pour être indécidable dans le cas des pavages du plan, et est très fortement lié à la question de la périodicité des pavages. Dans cette thèse nous abordons ce problème de deux point de vue différents:en regardant le cas particulier des pavages de faible complexité et en le généralisant aux structures plus généra les des groupes.Un pavage du plan est dit de faible complexité s'il y apparait moins de mn rectangles de taille m x n. Nivat conjecture en 1997 qu'un tel pavage est nécessairement périodique, avec comme conséquence que le problème du domino serait décidable pour les pavages de faible complexité. En continuant de développer des outils algébriques introduits par Kari et Szabados, nous prouvons une version généralisée de la conjecture de Nivat pour une classe de pavages particuliers (certains des sous-décalage algébrique). Nous parvenons également à montrer que la conjecture de Nivat est vraie pour tout pavage uniformément récurrent, avec comme conséquence que le problème du domino est effectivement décidable pour les pavages de faible complexité.Le problème du domino peut se formuler dans le cadre plus général des graphes de Cayley de groupes. Dans cette thèse nous développons de nouvelles techniques permettant de relier les graphes de Cayley de certains groupes à des graphes de substitutions.Une première technique nous permet de montrer qu'il existe à la fois des pavages fortement apériodiques et faiblement-non-fortement apériodiques pour les groupes de Baumslag-Solitar BS(l,n). Une seconde nous permet de montrer que le problème du domino est indécidable pour les groupes de surface, ce qui fourni une nouvelle classe de groupe vérifiant la conjecture disant que que le problème du domino d'un groupe est décidable si et seulement si le groupe est virtuellement libre
Given a finite set of square tiles, the domino problem is the question of whether is it possible ta tile the plane using these tiles.This problem is known to be undecidable in the planar case, and is strongly linked ta the question of the periodicity of the tiling.ln this thesis we look at this problem in two different ways: we look at the particular case of low complexity tilings and we generalize it to more general structures than the plane: groups.A tiling of the plane is sa id of low complexity if there are at most mn rectangles of size m x n appearing in it. Nivat conjectured in 1997 that any such tiling must be periodic, with the consequence that the domino problem would be decidable for low complexity tilings. Using algebraic tools introduced by Kari and Szabados, we prove a generalized version of Nivat's conjecture for a particular class of tilings (a subclass of what is called of algebraic subshifts). We also manage to prove that Nivat's conjecture holds for uniformly recurrent tilings, with the consequence that the domino problem is indeed decidable for low-complexity tilings.The domino problem can be formulated in the more general context of Cayley graphs of groups. ln this thesis, we develop new techniques allowing to relate the Cayley graph of some groups with graphs of substitutions on words.A first technique allows us to show that there exists bath strongly periodic and weakly-but-not­ strongly a periodic tilings of the Baumslag-Solitar groups BS(l,n).A second technique is used to show that the domino problem is undecidable for surface groups. Which provides yet another class of groups verifying the conjecture saying that the domino problem of a group is decidable if and only if the group is virtually free

Le travail présenté dans cette thèse porte sur l'étude et la modélisation en turbulence anisotrope. L'étude se divise en deux parties concernant respectivement le développement théorique de modèles algébriques anisotropes, ainsi que la mise en œuvre de ces modèles dans le cas d'écoulements cisaillés simples. Le premier chapitre définit le cadre de l'étude en présentant une revue bibliographique des modélisations concernées. Le second chapitre rappelle les équations de base utilisées pour la résolution numérique, ce qui comprend : les équations moyennes turbulentes de Navier-Stokes, ainsi que les équations de transport du modèle k-epsilon. Le chapitre 3, attaché à la modélisation des phénomènes d'anisotropie, présente, à partir de leur hypothèse de base des modélisations représentatives des efforts effectués dans ce domaine ; le but poursuivi n'étant pas une compilation exhaustive de tous ces modèles, mais plutôt une réduction de l'ensemble à quelques formulations significatives. Dans la continuité de cette étude, le chapitre 4 porte sur le développement d'un nouveau modèle algébrique qui fait l'objet d'une formulation détaillée, abordant de nombreux points relatifs à ce type de fermeture. Dans le chapitre 5, une classification des modèles étudiés est alors entreprise. Le chapitre 6 traite plus particulièrement de la méthode numérique prédicteur correcteur, volumes finis, de Maccormack qui a été utilisée. Le septième chapitre regroupe l'analyse et l'exploitation des résultats numériques. Le dernier chapitre présente les conclusions et les perspectives.

La compréhension des comportements des hommes préhistoriques nécessite la mise au point de méthodologies appropriées étudiant la nature et le fonctionnement des structures de combustion préhistoriques. Ce travail présente alors des outils numériques pour résoudre le problème de diffusion de la chaleur dans un milieu poreux saturé d'eau et pour déterminer les propriétés physiques du milieu par problème inverse. La première partie est consacrée à la résolution de problèmes de changement de phase utilisant deux approches, LHA (accumulation de chaleur latente) et AHC (capacité apparente), cette dernière étant retenue pour la suite. On utilise systématiquement la méthode des lignes qui consiste à discrétiser d'abord spatialement, soit par volumes finis avec un schéma en temps implicite et une variante de la méthode de Newton pour traiter la non linéarité, soit par une méthode d'éléments finis mixtes hybrides avec un schéma en temps semi-implicite. De plus, on étudie aussi le couplage diffusion-convection qui conduit à un système d'équations différentielles algébriques qu'on résout par un solveur approprié. Lors de comparaisons avec les expériences réalisées sur le site archéologique de Pincevent, les méthodes utilisées se sont montrées intéressantes et les résultats sont concluants. La deuxième partie de la thèse porte sur la détermination des propriétés physiques du sol archéologique par une méthode inverse. La méthode de Gauss Newton est utilisée pour résoudre ce problème. Les résultats obtenus montrent une bonne convergence vers la solution désirée
Abstract In order to understand the ancient human behavior, it was necessary to find an appropriate methodology to study the nature and the mechanism of the prehistoric fires. This work presents numerical methods to solve the problem of heat diffusion in water saturated porous media and to determine the physical properties of the medium by inverse method. However, the first part of this work concerns the resolution of phase change problems using two approaches LHA (latent heat accumulation) and AHC (apparent heat capacity); this last one is used in what follows. We use systematically the method of lines which consists first on discretizing in space, by finite volume method with an implicit scheme and a modified Newton method to deal with the non linearity, or by hybrid mixed finite element with a semi-implicit scheme in time. In addition, the coupling diffusion-convection model has been studied leading to a system of differential algebraic equations solved by an appropriate solver. After the comparisons with the results of the real experiments realized at the archaeological site of Pincevent, the shown methods look interesting and the results are promissing. The second part of my Ph. D work is about the estimation of thermophysical properties of the archaeological soil by inverse problem. The Gauss-Newton method is used to solve the problem. The obtained results show a good convergence to the desired solution

Cette thèse, proposée dans le cadre du projet W2P1-DECOL (SAS PIVERT), financée par le ministère de l’enseignement supérieur est consacrée à l’étude d’un problème inverse de pressage des matériaux biologiques à structure cellulaire. Le but est d’identifier connaissant les mesures du flux d’huile sortant, le coefficient de consolidation du gâteau de pressage et l’inverse du temps caractéristique de consolidation sur deux niveaux : au niveau de la graine de colza et au niveau du gâteau de pressage. Dans un premier temps, nous présentons un système d’équations paraboliques modélisant le problème de pressage des matériaux biologiques à structure cellulaire, il découle de l’équation de continuité de la loi de Darcy et d’autres hypothèses simplificatrices. Puis l’analyse théorique et numérique du modèle direct est faite dans le cas linéaire. Enfin la méthode des différences finies est utilisée pour le discrétiser. Dans un second temps, nous introduisons le problème inverse du pressage où l’étude de l’identifiabilité de ce problème est résolue par une méthode spectrale. Par la suite, nous nous intéressons à l’étude de stabilité lipschitzienne locale et globale. De plus une estimation de stabilité lipschitzienne globale, pour le problème inverse de paramètres, dans le cas du système d’équations paraboliques, à partir des mesures sur ]0,T[ est établie. Enfin l’identification des paramètres est résolue par deux méthodes, l’une basée sur l’adaptation de la méthode algébrique et l’autre formulée comme la minimisation au sens des moindres carrés d’une fonctionnelle évaluant l’écart entre les mesures et les résultats du modèle direct, la résolution de ce problème inverse se fait en utilisant un algorithme itératif BFGS, l’algorithme est validé puis testé numériquement dans le cas des graines de colza, en utilisant des mesures synthétiques. Il donne des résultats très satisfaisants, malgré les difficultés rencontrés à manipuler et exploiter les données expérimentales
This thesis, proposed in the framework of the W2P1-DECOL project (SAS PIVERT) and funded by the Ministry of Higher Education, is devoted to the study an inverse problem of pressing biological materials with a cellular structure. The aim is to identify, of the outgoing oil flow, the coefficient of consolidation of the pressing cake and the inverse of the characteristic time of consolidation on two levels : at the level of the rapeseed and at the level of the pressing cake. First, we present a system of parabolic equations modeling the pressing problem of biological materials with cellular structure; it follows from the continuity equation of Darcy’s law and other simplifying hypotheses. Then a theoretical and numerical analysis of a direct model is made in the linear case. Finally the finite difference method is usedt o discretize it. In a second step, we introduce the inverse problem of the pressing where the study of the identifiability of this problem is solved by a spectral method. Later we are interested in the study of local and global Lipschitizian stability. Moreover, global Lipschitz stability estimate for the inverse problem of parameters in the case of the system of parabolic equations from the measures on ]0,T[ is established. Finally, the identification of the parameters is solved by two methods; one based on the adaptation of the algebraic method and the other formulated as the minimization in the least squares sense of a functional evaluating the difference between measurements and the results of the direct model; the resolution of this inverse problem is done using an iterative algorithm BFGS, the algorithm is validated and then tested numerically in the case of rapeseeds, using synthetic measures. It gives very satisfactory results, despite the difficulties encountered in handling and exploiting the experimental data

La prévention des risques industriels nécessite de simuler la dispersion turbulente de polluants. Cependant, les outils majoritairement utilisés à ce jour ne permettent pas de traiter les champs proches dans le cas de géométries complexes, et il est nécessaire d'utiliser les outils de CFD (“ Computational Fluid Dynamics ”) plus adaptés, mais plus coûteux. Afin de simuler les écoulements atmosphériques avec dispersion de polluants, les modèles CFD doivent modéliser correctement d'une part, les effets de flottabilité, et d'autre part les effets de la turbulence. Plusieurs approches existent, notamment dans la prise en compte des effets de flottabilité et la modélisation de la turbulence, et nécessitent des méthodes numériques adaptées aux spécificités mathématiques de chacune d'entre elles, ainsi que des schémas numériques précis pour ne pas polluer la modélisation. Une formulation d'ordre élevé en volumes finis, sur maillages non structurés, parallélisée, est proposée pour simuler les écoulements atmosphériques avec dispersion de polluants. L'utilisation de schémas d'ordre élevé doit permettre d'une part de réduire le nombre de cellules et diminuer les temps de simulation pour atteindre une précision donnée, et d'autre part de mieux contrôler la viscosité numérique des schémas en vue de simulations LES (Large Eddy Simulation), pour lesquelles la viscosité numérique des schémas peut masquer les effets de la modélisation. Deux schémas d'ordre élevé ont été étudiés et implémentés dans un solveur 3D Navier Stokes incompressible sur des maillages volumes finis non structurés. Nous avons développé un premier schéma d'ordre élevé, correspondant à un schéma Padé volumes finis, et nous avons étendu le schéma de reconstruction polynomiale de Carpentier (2000) aux écoulements incompressibles. Les propriétés numériques des différents schémas implémentés dans le même code de calcul sont étudiées sur différents cas tests bi-dimensionnels (calcul de flux convectifs et diffusifs sur une solution a-priori, convection d'une tâche gaussienne, décroissance d'un vortex de Taylor et cavité entraînée) et tri-dimensionnel (écoulement autour d'un obstacle cubique). Une attention particulière a été portée à l'étude de la précision et du traitement des conditions limites. L'implémentation proposée du schéma polynomial permet d'approcher, pour un maillage identique, les temps de simulation obtenus avec un schéma décentré classique d'ordre 2, mais avec une précision supérieure. Le schéma compact donne la meilleure précision. En utilisant une méthode de Jacobi sans calcul implicite de la matrice pour calculer le gradient, le temps de simulation devient intéressant uniquement lorsque la précision requise est importante. Une alternative est la résolution du système linéaire par une méthode multigrille algébrique. Cette méthode diminue considérablement le temps de calcul du gradient et le schéma Padé devient performant même pour des maillages grossiers. Enfin, pour réduire les temps de simulation, la parallélisation des schémas d'ordre élevé est réalisée par une décomposition en sous domaines. L'assemblage des flux s'effectue naturellement et différents solveurs proposés par les librairies PETSC et HYPRE (solveur multigrille algébrique et méthode de Krylov préconditionnée) permettent de résoudre les systèmes linéaires issus de notre problème. Le travail réalisé a consisté à identifier et déterminer les paramètres de résolution qui conduisent aux temps de simulation les plus faibles. Différents tests de speed-up et de scale-up ont permis de déterminer la méthode la plus efficace et ses paramètres optimaux pour la résolution en parallèle des systèmes linéaires issus de notre problème. Les résultats de ce travail ont fait l'objet d'une communication dans un congrès international “ parallel CFD juin 2008 ” et d'un article soumis à “ International Journal for Numerical Methods in Fluids ” (Analysis of high-order finite volume schemes for the incompressible Navier Stokes equations)

Cette thèse est consacrée à l'étude des variétés projectives strictement convexes de volume fini. Une telle variété est le quotient G\U d'un ouvert proprement convexe U de l'espace projectif réel RP^(n-1) par un sous-groupe discret sans torsion G de SLn(R) qui préserve U. Dans un premier temps, on étudie l'adhérence de Zariski des holonomies de variétés projectives strictement convexes de volume fini. Pour une telle variété G\U, on montre que, soit G est Zariski-dense dans SLn(R), soit l'adhérence de Zariski de G est conjuguée à SO(1,n-1). On s'intéresse ensuite à l'espace des modules des structures projectives strictement convexes de volume fini. On montre en particulier que cet espace des modules est un fermé de l'espace des représentations
In this thesis, we study strictly convex projective manifolds of finite volume. Such a manifold is the quotient G\U of a properly convex open subset U of the real projective space RP^(n-1) by a discrete torsionfree subgroup G of SLn(R) preserving U. We study the Zariski closure of holonomies of convex projective manifolds of finite volume. For such manifolds G\U, we show that either the Zariski closure of G is SLn(R) or it is a conjugate of SO(1,n-1).We also focuss on the moduli space of strictly convex projective structures of finite volume. We show that this moduli space is a closed set of the representation space