Auswahl der wissenschaftlichen Literatur zum Thema „Forme algébrique normale“

Dans ce document, nous étudions les représentations efficaces, en termes de taille, d'un contenu sémantique donné. Nous étendons tout d'abord une spécification équationnelle du domaine des fonctions Booléennes à celui des polynômes latticiels sur des treillis distributifs, domaines cruciaux en intelligence artificielle. Cette spécification est correcte et complète : elle nous permet de simplifier des formules médianes de manière algébrique en des formes normales médianes (MNF), que nous définissons comme des formules médianes minimales par rapport à un ordre structurel sur les expressions. Nous explorons la complexité de certaines questions connexes, et montrons que le problème qui consiste à décider si une formule est en MNF, c'est-à-dire, à simplifier la formule médiane d'une fonction Booléenne monotone, est dans sigmaP, au second niveau de la hiérarchie polynomiale : nous montrons également ce résultat pour les fonctions Booléennes arbitraires. Nous étudions ensuite d'autres systèmes de formes normales (NFSs), considérés, plus généralement, comme des ensembles de termes stratifiés selon une suite de connecteurs fixée, telle que (m, NOT) pour la MNF. Pour un NFS fixé A, la complexité d'une fonction Booléenne f par rapport à A est le minimum des tailles des termes de A qui représentent f. Cela induit un préordre sur les NFSs : un NFS A est polynomialement plus efficace qu'un NFS B s'il existe un polynôme P à coefficients entiers strictement positifs tel que la complexité de toute fonctions Booléenne f par rapport à A est majorée par la valeur de P pris en la complexité de « f » par rapport à « B ». Nous étudions les NFSs monotones, c'est-à-dire les NFSs dont les connecteurs sont croissants ou décroissants en chaque argument. Nous décrivons les NFSs monotones optimaux, qui sont minimaux par rapport au préordre ci-dessus. Nous montrons qu'ils sont tous équivalents. Nous montrons que les NFSs monotones optimaux sont exactement ceux qui ne comportent qu'un seul connecteur ou un seul connecteur et la négation. Finalement, nous montrons que l'optimalité ne dépend pas de l'arité du connecteur
In this document, we study efficient representations, in term of size, of a given semantic content. We first extend an equational specification of median forms from the domain of Boolean functions to that of lattice polynomials over distributive lattices, both domains that are crucial in artificial intelligence. This specification is sound and complete: it allows us to algebraically simplify median forms into median normal forms (MNF), that we define as minimal median formulas with respect to a structural ordering of expressions. We investigate related complexity issues and show that the problem of deciding if a formula is in MNF, that is, minimizing the median form of a monotone Boolean function, is in sigmaP, at the second level of the polynomial hierarchy; we show that this result holds for arbitrary Boolean functions as well. We then study other normal form systems (NFSs), thought of, more generally, as a set of stratified terms over a fixed sequence of connectives, such as (m, NOT) in the case of the MNF. For a fixed NFS A, the complexity of a Boolean function f with respect to A is the minimum of the sizes of terms in A that represent f. This induces a preordering of NFSs: an NFS A is polynomially as efficient as an NFS B if there is a polynomial P with nonnegative integer coefficients such that the complexity of any Boolean function f with respect to A is at most the value of P in the complexity of f with respect to B. We study monotonic NFSs, i.e., NFSs whose connectives are increasing or decreasing in each argument. We describe optimal monotonic NFSs, that are minimal with respect to the latter preorder. We show that they are all equivalent. We show that optimal monotonic NFSs are exactly those that use a single connective or one connective and the negation. Finally, we show that optimality does not depend on the arity of the connective

Cette thèse contribue à l’effort de cryptanalyse de primitives symétriques comme les chiffrements par bloc ou les générateurs pseudo-aléatoires. Elle étudie en particulier une famille de distingueurs fondés sur la propagation de sous-espaces vectoriels différentiels dans les chiffrements par bloc de construction SPN. Cette thèse propose également des méthodes permettant aux cryptographes de modéliser un problème de cryptanalyse de primitive symétrique en problème MILP (Mixed-Integer Linear Programming), afin d’exploiter certains logiciels solutionneurs de problèmes MILP très performants. Enfin, elle présente des techniques d’analyse algébrique des primitives symétriques, fondées sur le calcul d’une partie de leur forme algébrique normale, et utiles dans les attaques de type cube
This thesis contributes to the cryptanalysis effort needed to trust symmetric-key primitives like block-ciphers or pseudorandom generators. In particular, it studies a family of distinguishers based on subspace trails against SPN ciphers. This thesis also provides methods for modeling frequent cryptanalysis problems into MILP (Mixed-Integer Linear Programming) problems to allow cryptographers to benefit from the existence of very efficient MILP solvers. Finally, it presents techniques to analyze algebraic properties of symmetric-key primitives which could be useful to mount cube attacks

Cette thèse se rattache à l'algèbre linéaire formelle. Elle est composée de deux parties: la première, consacrée à l'étude des formes normales de matrices, constitue un ensemble d'outils utilisés dans la seconde qui, pour sa part, présente des méthodes matricielles de résolution de deux types de systèmes différentiels: les systèmes différentiels à coefficients constants et les systèmes différentiels ayant un point singulier régulier isolé. Dans la première partie, nous avons étudié, implémentés dans le système de calcul formel AXIOM, et comparés tant de manière théorique qu'expérimentale des algorithmes de calcul de diverses formes normales (Frobenius, Smith, Jordan) de matrices à coefficients rationnels. Dans la seconde, nous avons montré quels sont les avantages et les inconvénients de l'utilisation de ces algorithmes pour trois applications: le calcul de l'exponentielle d'une matrice, la résolution d'équations matricielles et la résolution matricielle de systèmes différentiels ayant une singularité régulière isolée. En particulier, nous avons abordé le problème épineux de la manipulation des nombres algébriques apparaissant nécessairement lorsque l'on calcule formellement, la forme de Jordan d'une matrice à coefficients rationnels

Depuis quelques années, l'extension de l'utilisation de l'informatique dans tous les domaines de recherche scientifique et technique se traduit par un besoin croissant de puissance de calcul. Il est donc vital d'employer les microprocesseurs en parallèle. Le problème principal que nous cherchons à résoudre dans cette thèse est le calcul d'une forme canonique de très grandes matrices creuses à coefficients entiers, la forme normale de Smith. Par "très grandes", nous entendons un million d'inconnues et un million d'équations, c'est-à-dire mille milliards de variables. De tels systèmes sont même, en général, impossibles à stocker actuellement. Cependant, nous nous intéressons à des systèmes dans lesquels beaucoup de ces variables sont identiques et valent zéro; on parle dans ce cas de système creux. Enfin, nous voulons résoudre ces systèmes de manière exacte, c'est-à-dire que nous travaillons avec des nombres entiers ou dans une structure algébrique plus petite et autorisant toutes les opérations classiques, un corps fini. La reconstruction de la solution entière à partir des solutions plus petites est ensuite relativement aisée.

Dans cette thèse, nous introduisons et étudions une nouvelle représentation implicite des hypersurfaces rationelles et des courbes rationnelles plongées dans un espace projectif de dimension arbitraire. Nous illustrons les avantages de cette représentation matricielle en abordant plusieurs problèmes importants intervenant en conception géométriqueassistée par ordinateur: les problèmes d'intersection entre deux courbes, entre une courbe et une surface ou bien encore entre deux surfaces, le problème d'appartenance d'un point à une courbe ou une surface, le problème du calcul de la pré-image d'un point donné par une paramétrisation et enfin le problème du calcul des singularités d'une courbe rationnelle. L'approche développée dans ce travail de thèse est basée sur la combinaison de méthodes symboliques et numériques. En effet, un première étape symbolique consiste à transformer le problème considérer en un pinceau de matrices. La deuxième étape consiste alors à calculer les valeurs propres généralisées de ce pinceau à l'aide de méthodes numériques. Pour cela, un algorithme d'extraction de la partie régulière d'un pinceau univarié, respectivement bivarié, de matrices non carrées est présenté. Une implémentation de ces travaux dans les systèmes de calcul formel Mathemagix et Maple est présentée en appendice. Le dernier chapitre est conscré à un algorithme qui, étant donné un ensemble de polynômes univariés f1 , ..., fs construit un ensemble de polynômes u1 , ..., us dont les degrés sont prescrits, tels que le degré du pgcd(f1 + u1 , ..., fs + us ) est supérieur ou égal à un entier donné sous des hypothèses de généricité.

Dans la première partie de cette thèse, nous étudions les équations différentielles algébriques (en abrégé EDA) linéaires et les systèmes de contrôles linéaires associés (en abrégé SCEDA). Les problèmes traités et les résultats obtenus sont résumés comme suit : 1. Relations géométriques entre les EDA linéaires et les systèmes de contrôles génériques SCEDO. Nous introduisons une méthode, appelée explicitation, pour associer un SCEDO à n'importe quel EDA linéaire. L'explicitation d'une EDA est une classe des SCEDO, précisément un SCEDO défini, à un changement de coordonnées près, une transformation de bouclage près et une injection de sortie près. Puis nous comparons les « suites de Wong » d'une EDA avec les espaces invariants de son explicitation. Nous prouvons que la forme canonique de Kronecker FCK d'une EDA linéaire et la forme canonique de Morse FCM d'un SCEDO, ont une correspondance une à une et que leurs invariants sont liés. De plus, nous définissons l'équivalence interne de deux EDA et montrons sa particularité par rapport à l'équivalence externe en examinant les relations avec la régularité interne, i.e., l'existence et l'unicité de solutions. 2. Transformation d'un SCEDA linéaire vers sa forme canonique via la méthode d'explicitation avec des variables de driving. Nous étudions les relations entre la forme canonique par bouclage FCFB d'un SCEDA proposée dans la littérature et la forme canonique de Morse pour les SCEDO. Premièrement, dans le but de relier SCEDA avec les SCEDO, nous utilisons une méthode appelée explicitation (avec des variables de driving). Cette méthode attache à une classe de SCEDO avec deux types d'entrées (le contrôle original et le vecteur des variables de driving) à un SCEDA donné. D'autre part, pour un SCEDO linéaire classique (sans variable de driving) nous proposons une forme de Morse triangulaire FMT pour modifier la construction de la FCM. Basé sur la FMT nous proposons une forme étendue FMT et une forme étendue de FCM pour les SCEDO avec deux types d'entrées. Finalement, un algorithme est donné pour transformer un SCEDA dans sa FCFB. Cet algorithme est construit sur la FCM d'un SCEDO donné par la procédure d'explicitation. Un exemple numérique illustre la structure et l'efficacité de l'algorithme. Pour les EDA non linéaires et les SCEDA (quasi linéaires) nous étudions les problèmes suivants : 3. Explicitations, analyse externe et interne et formes normales des EDA non linéaires. Nous généralisons les deux procédures d'explicitation (avec ou sans variables de driving) dans le cas des EDA non linéaires. L'objectif de ces deux méthodes est d'associer un SCEDO non linéaire à une EDA non linéaire telle que nous puissions l'analyser à l'aide de la théorie des EDO non linéaires. Nous comparons les différences de l'équivalence interne et externe des EDA non linéaires en étudiant leurs relations avec l'existence et l'unicité d'une solution (régularité interne). Puis nous montrons que l'analyse interne des EDA non linéaire est liée à la dynamique nulle en théorie classique du contrôle non linéaire. De plus, nous montrons les relations des EDAS de forme purement semi-explicite avec les 2 procédures d'explicitations. Finalement, une généralisation de la forme de Weierstrass non linéaire FW basée sur la dynamique nulle d'un SCEDO non linéaire donné par la méthode d'explicitation est proposée
In the first part of this thesis, we study linear differential-algebraic equations (shortly, DAEs) and linear control systems given by DAEs (shortly, DAECSs). The discussed problems and obtained results are summarized as follows. 1. Geometric connections between linear DAEs and linear ODE control systems ODECSs. We propose a procedure, named explicitation, to associate a linear ODECS to any linear DAE. The explicitation of a DAE is a class of ODECSs, or more precisely, an ODECS defined up to a coordinates change, a feedback transformation and an output injection. Then we compare the Wong sequences of a DAE with invariant subspaces of its explicitation. We prove that the basic canonical forms, the Kronecker canonical form KCF of linear DAEs and the Morse canonical form MCF of ODECSs, have a perfect correspondence and their invariants (indices and subspaces) are related. Furthermore, we define the internal equivalence of two DAEs and show its difference with the external equivalence by discussing their relations with internal regularity, i.e., the existence and uniqueness of solutions. 2. Transform a linear DAECS into its feedback canonical form via the explicitation with driving variables. We study connections between the feedback canonical form FBCF of DAE control systems DAECSs proposed in the literature and the famous Morse canonical form MCF of ODECSs. In order to connect DAECSs with ODECSs, we use a procedure named explicitation (with driving variables). This procedure attaches a class of ODECSs with two kinds of inputs (the original control input and the vector of driving variables) to a given DAECS. On the other hand, for classical linear ODECSs (without driving variables), we propose a Morse triangular form MTF to modify the construction of the classical MCF. Based on the MTF, we propose an extended MTF and an extended MCF for ODECSs with two kinds of inputs. Finally, an algorithm is proposed to transform a given DAECS into its FBCF. This algorithm is based on the extended MCF of an ODECS given by the explication procedure. Finally, a numerical example is given to show the structure and efficiency of the proposed algorithm. For nonlinear DAEs and DAECSs (of quasi-linear form), we study the following problems: 3. Explicitations, external and internal analysis, and normal forms of nonlinear DAEs. We generalize the two explicitation procedures (with or without driving variable) proposed in the linear case for nonlinear DAEs of quasi-linear form. The purpose of these two explicitation procedures is to associate a nonlinear ODECS to any nonlinear DAE such that we can use the classical nonlinear ODE control theory to analyze nonlinear DAEs. We discuss differences of internal and external equivalence of nonlinear DAEs by showing their relations with the existence and uniqueness of solutions (internal regularity). Then we show that the internal analysis of nonlinear DAEs is closely related to the zero dynamics in the classical nonlinear control theory. Moreover, we show relations of DAEs of pure semi-explicit form with the two explicitation procedures. Furthermore, a nonlinear generalization of the Weierstrass form WE is proposed based on the zero dynamics of a nonlinear ODECS given by the explicitation procedure

Ce travail porte sur les propriétés algébriques des groupes de tresses d'Artin et des systèmes autodistributifs à gauche, des objets intimement liés. La première partie est une analyse syntaxique de la forme normale de Bressaud pour les tresses. Le principal résultat est une traduction en termes de systèmes de réécriture de l'existence de la forme normale, initialement établie par des méthodes géométriques. La seconde partie est centrée sur la conjecture de plongement pour l'autodistributivité, un des énoncés ouverts principaux du domaine. On discute les multiples approches (y compris calculatoires) pouvant mener à cette conjecture, et on établit des résultats positifs partiels
In this work, we investigate algebraic properties for Artin's braid groups and self-distributive systems on the left, two objets which are linked. The first part is a syntactic analysis of Bressaud's normal formal for braids. The principal result is a translation in terms of rewriting systems of the existence of Bressaud's normal form, initially established by geometric methods. The second part deals with the embedding conjecture for self-distributivity, one of the principal open statements of the field. We discuss the various ways (including the computing ones) which could lead to this conjecture, and we establish some partial positive results

Les problèmes d'optimisation sur l'ensemble des courbes apparaissent dans de nombreux domaines d'applications industrielles comme la robotique, la planification de mouvements et l'aérospatiale. Dans cette thèse, nous étudions l'ensemble des courbes et proposons une méthode générale pour problèmes d'optimisation de trajectoires, équations différentielles ordinaires autonomes et commande des équations différentielles ordinaires autonomes. Dans la première partie, nous fournissons une normalisation des courbes paramétrées sous l'action des difféomorphismes croissants et nous utilisons cette normalisation pour définir une distance entre les courbes paramétrées. Nous étudions ensuite la topologie et la structure différentielle sur l'ensemble des courbes. Dans la seconde partie nous définissons une norme sur l'espace des courbes de Bézier cubique par morceaux et nous estimons quelques constantes d'équivalence pour cette norme et certaines normes classiques. Dans la dernière partie de cette thèse est proposée une méthode générale pour approximer des trajectoires optimales en utilisant des courbes de Bézier cubiques par morceaux. Cette idée est appliquée aux équations différentielles autonomes et au contrôle des équations différentielles autonomes
Optimization problems on the set of curves appear in many fields of applications such as industry, robotic, path-planning and aerospace. This thesis is devoted to study the set of curves and propose a general method for trajectory optimization problems, autonomous ODEs and control of autonomous ODEs. In the first part, we provide a normalization of parametrized curves up to increasing diffeomorphism and use it to define a distance between curves. Then, we study topologies and differential structures on the set of curves. The second part defines a norm on spaces of piecewise cubic Bézier curves and estimates equivalence constants for this norm and some classical norms. The last part proposes a general method to approximate optimal trajectories using piecewise cubic Bézier curves. This idea is applied to autonomous ODEs and control of autonomous ODEs

Le travail de cette thèse porte sur une modélisation cinématique des distributions K-drapeaux spéciaux et la classification de leurs singularités. Ces distributions sont obtenues localement par prolongement de Cartan généralisés successifs à partir du fibre tangent à une variété de dimension K+1. Elles constituent une généralisation des distributions de Goursat. On dispose pour les distributions de Goursat d'une classification complète décrivant tous les types de singularités qui admettent également une interprétation géométrique. Ces distributions admettent une sorte de modèle cinématique universel, celui de la voiture avec n remorques. Ce modèle contient toutes les classes de germes possibles, et la stratification de son lieu singulier décrit toutes les classes géométriques de singularités. L'objectif de cette thèse est de proposer un modèle cinématique appelé bras articulé qui jouerait le même rôle, pour les distributions multi drapeaux spéciaux, que la voiture tirant n remorques pour les distributions de Goursat. Nous montrons que ce modèle définit bien une distribution K-drapeau spécial. Nous déterminons les premières strates du lieu singulier singulier, décrivant ainsi les classes géométriques de la plupart des formes normales. Cette classification, quoiqu'incomplète, recouvre déjà toutes les classes de singularités de la voiture
The work of this thesis concerns a kinematic modeling of special multi-flags distributions and the classification of their singularities. These distributions are obtained locally by successive generalized Cartan prolongations starting from fibre tangent to a K+1-dimensional space. They constitute a generalization of Goursat distributions. Goursat distributions possess a complete classification describing all their types of singularities which also admit a geometrical interpretation. These distributions admit kind of universal kinematic model, the car with n trailers. This model contains all the possible classes of germs, and the stratification of its singular locus describes all geometric classes of singularities. The purpose of this thesis is to show that the problem of modeling car with n trailers can be generalized to the problem of modeling kinematic problem for an articulated arm, such that to this model is naturally associated a special K-flag distribution. We build a first type of singularities which is characterized in terms of kinematic properties. Then we refine some singularities into geometric classes which can be considered as a generalization of F. Jean's results. In fact these singularities correspond to those defined by P. Mormul for special multi-flags distributions