Forme canonique - Canonical form

Test d' anagramme algorithmique utilisant des multi-ensembles comme formes canoniques : Les chaînes " madame curie " et " radium came " sont données sous forme de tableaux C. Chacun est converti en une forme canonique par tri. Étant donné que les deux chaînes triées concordent littéralement, les chaînes d'origine étaient des anagrammes l'une de l'autre.

En mathématiques et en informatique , une canonique , normale ou norme sous forme d'un objet mathématique est un moyen standard de présenter cet objet comme une expression mathématique . Souvent, c'est celui qui fournit la représentation la plus simple d'un objet et qui permet de l'identifier de manière unique. La distinction entre les formes « canoniques » et « normales » varie d'un sous-domaine à l'autre. Dans la plupart des domaines, une forme canonique spécifie une représentation unique pour chaque objet, tandis qu'une forme normale spécifie simplement sa forme, sans exigence d'unicité.

La forme canonique d'un entier positif en représentation décimale est une séquence finie de chiffres qui ne commence pas par zéro. Plus généralement, pour une classe d'objets sur laquelle une relation d'équivalence est définie, une forme canonique consiste en le choix d'un objet spécifique dans chaque classe. Par exemple:

En informatique, et plus particulièrement en algèbre informatique , lors de la représentation d'objets mathématiques dans un ordinateur, il existe généralement de nombreuses façons différentes de représenter le même objet. Dans ce contexte, une forme canonique est une représentation telle que chaque objet a une représentation unique (la canonisation étant le processus par lequel une représentation est mise dans sa forme canonique). Ainsi, l'égalité de deux objets peut être facilement testée en testant l'égalité de leurs formes canoniques.

Malgré cet avantage, les formes canoniques dépendent fréquemment de choix arbitraires (comme l'ordre des variables), qui introduisent des difficultés pour tester l'égalité de deux objets résultant de calculs indépendants. Par conséquent, en calcul formel, la forme normale est une notion plus faible : une forme normale est une représentation telle que zéro est représenté de manière unique. Cela permet de tester l'égalité en mettant la différence de deux objets sous forme normale.

La forme canonique peut également signifier une forme différentielle définie de manière naturelle (canonique).

Définition

Étant donné un ensemble S d'objets avec une relation d'équivalence R sur S , une forme canonique est donnée en désignant certains objets de S comme étant « sous forme canonique », de sorte que chaque objet considéré est équivalent à exactement un objet sous forme canonique. En d'autres termes, les formes canoniques dans S représentent les classes d'équivalence, une et une seule fois. Pour tester si deux objets sont équivalents, il suffit alors de tester l'égalité sur leurs formes canoniques. Une forme canonique fournit ainsi un théorème de classification et plus, en ce qu'elle classe non seulement toutes les classes, mais donne aussi un distingué (canonique) représentant pour chaque objet dans la classe.

Formellement, une forme canonique par rapport à une relation d'équivalence R sur un ensemble S est une application c : SS tel que pour tous s , s 1 , s 2S :

  1. c ( s ) = c ( c ( s )) ( idempotence ),
  2. s 1 R s 2 si et seulement si c ( s 1 ) = c ( s 2 ) (décision), et
  3. s R c ( s ) (représentativité).

La propriété 3 est redondante ; il suit en appliquant 2 à 1.

Concrètement, il est souvent avantageux de pouvoir reconnaître les formes canoniques. Il y a aussi une question algorithmique pratique à considérer : comment passer d'un objet donné s dans S à sa forme canonique s * ? Les formes canoniques sont généralement utilisées pour rendre plus efficace le fonctionnement avec des classes d'équivalence. Par exemple, en arithmétique modulaire , la forme canonique d'une classe de résidus est généralement considérée comme l'entier le moins non négatif de celle-ci. Les opérations sur les classes sont effectuées en combinant ces représentants, puis en réduisant le résultat à son moindre résidu non négatif. L'exigence d'unicité est parfois assouplie, permettant aux formes d'être uniques jusqu'à une relation d'équivalence plus fine, telle que la réorganisation des termes (s'il n'y a pas d'ordre naturel des termes).

Une forme canonique peut être simplement une convention ou un théorème profond. Par exemple, les polynômes s'écrivent classiquement avec les termes en puissances décroissantes : il est plus courant d'écrire x 2 + x + 30 que x + 30 + x 2 , bien que les deux formes définissent le même polynôme. En revanche, l'existence de la forme canonique de Jordan pour une matrice est un théorème profond.

Exemples

Remarque : dans cette section, " jusqu'à " une relation d'équivalence E signifie que la forme canonique n'est pas unique en général, mais que si un objet a deux formes canoniques différentes, elles sont E-équivalentes.

Notation des grands nombres

La forme standard est utilisée par de nombreux mathématiciens et scientifiques pour écrire des nombres extrêmement grands de manière plus concise et compréhensible, la plus importante étant la notation scientifique .

La théorie du nombre

Algèbre linéaire

Objets A est équivalent à B si : Forme normale Remarques
Matrices normales sur les nombres complexes pour une matrice unitaire U Matrices diagonales (jusqu'au réordonnancement) C'est le théorème spectral
Matrices sur les nombres complexes pour certaines matrices unitaires U et V Matrices diagonales avec entrées positives réelles (par ordre décroissant) Décomposition en valeur singulière
Matrices sur un corps algébriquement clos pour une matrice inversible P Jordan forme normale (jusqu'à réorganisation des blocs)
Matrices sur un corps algébriquement clos pour une matrice inversible P Forme canonique du Weyr (jusqu'à réorganisation des blocs)
Matrices sur un champ pour une matrice inversible P forme normale de Frobenius
Matrices sur un domaine idéal principal pour certaines matrices inversibles P et Q Forme normale de Smith L'équivalence revient à autoriser des transformations élémentaires de ligne et de colonne inversibles
Matrices sur les entiers pour une matrice unimodulaire U Hermite forme normale
Espaces vectoriels de dimension finie sur un corps K A et B sont isomorphes en tant qu'espaces vectoriels , n un entier non négatif

Algèbre

Objets A est équivalent à B si : Forme normale
De type fini R -modules avec R un principal domaine idéal A et B sont isomorphes en tant que R -modules Décomposition primaire (jusqu'au réordonnancement) ou décomposition factorielle invariante

Géométrie

En géométrie analytique :

  • L'équation d'une droite : Ax  +  By  =  C , avec A 2  +  B 2  = 1 et C  ≥ 0
  • L'équation d'un cercle :

En revanche, il existe des formes alternatives pour écrire des équations. Par exemple, l'équation d'une ligne peut être écrite sous la forme d'une équation linéaire sous forme de point-pente et d' intersection de pente .

Les polyèdres convexes peuvent être mis sous forme canonique telle que :

  • Tous les visages sont plats,
  • Toutes les arêtes sont tangentes à la sphère unité, et
  • Le centre de gravité du polyèdre est à l'origine.

Systèmes intégrables

Chaque variété différentiable a un fibré cotangent . Ce faisceau peut toujours être doté d'une certaine forme différentielle , appelée la forme unique canonique . Cette forme donne au fibré cotangent la structure d'une variété symplectique , et permet aux champs de vecteurs sur la variété d'être intégrés au moyen des équations d'Euler-Lagrange , ou au moyen de la mécanique hamiltonienne . De tels systèmes d' équations différentielles intégrables sont appelés systèmes intégrables .

Systèmes dynamiques

L'étude des systèmes dynamiques recoupe celle des systèmes intégrables ; on a là l'idée d'une forme normale (systèmes dynamiques) .

Géométrie tridimensionnelle

Dans l'étude des variétés en trois dimensions, on a la première forme fondamentale , la deuxième forme fondamentale et la troisième forme fondamentale .

Analyse fonctionnelle

Objets A est équivalent à B si : Forme normale
Espaces Hilbert Si A et B sont tous deux des espaces de Hilbert de dimension infinie, alors A et B sont isométriquement isomorphes. espaces de séquence (jusqu'à échanger l'ensemble d'index I avec un autre ensemble d'index de même cardinalité )
-algèbres commutatives avec unité A et B sont isomorphes en tant que -algèbres L'algèbre des fonctions continues sur un espace de Hausdorff compact , à homéomorphisme près de l'espace de base.

Logique classique

Théorie des ensembles

La théorie des jeux

Théorie de la preuve

Systèmes de réécriture

La manipulation symbolique d'une formule d'une forme à une autre s'appelle une « réécriture » de cette formule. On peut étudier les propriétés abstraites de la réécriture de formules génériques, en étudiant l'ensemble des règles par lesquelles les formules peuvent être valablement manipulées. Ce sont les "règles de réécriture"—une partie intégrante d'un système de réécriture abstrait . Une question courante est de savoir s'il est possible d'apporter une expression générique à une seule forme commune, la forme normale. Si différentes séquences de réécritures aboutissent toujours à la même forme, alors cette forme peut être qualifiée de forme normale, la réécriture étant appelée confluente. Il n'est pas toujours possible d'obtenir une forme normale.

Calcul lambda

  • Un terme lambda est sous forme bêta normale si aucune réduction bêta n'est possible ; le lambda calcul est un cas particulier de système de réécriture abstraite. Dans le calcul lambda non typé, par exemple, le terme n'a pas de forme normale. Dans le lambda calcul typé, chaque terme bien formé peut être réécrit sous sa forme normale.

La théorie des graphes

Dans la théorie des graphes , une branche des mathématiques, la canonisation des graphes est le problème de trouver une forme canonique d'un graphe donné G . Une forme canonique est un graphe étiqueté Canon( G ) qui est isomorphe à G , tel que chaque graphe isomorphe à G a la même forme canonique que G . Ainsi, à partir d'une solution au problème de canonisation des graphes, on pourrait aussi résoudre le problème de l' isomorphisme des graphes : pour tester si deux graphes G et H sont isomorphes, calculer leurs formes canoniques Canon( G ) et Canon( H ), et tester si ces deux formes canoniques sont identiques.

L'informatique

En informatique , la réduction des données à n'importe quel type de forme canonique est communément appelée normalisation des données .

Par exemple, la normalisation de la base de données est le processus d'organisation des champs et des tables d'une base de données relationnelle pour minimiser la redondance et la dépendance.

Dans le domaine de la sécurité logicielle , une vulnérabilité courante est l'entrée malveillante non contrôlée (voir Injection de code ). L'atténuation de ce problème est une validation d'entrée appropriée . Avant que la validation d'entrée ne soit effectuée, l'entrée est généralement normalisée en éliminant l'encodage (par exemple, l' encodage HTML ) et en réduisant les données d'entrée à un seul jeu de caractères commun .

D'autres formes de données, généralement associées au traitement du signal (y compris l' audio et l' imagerie ) ou à l'apprentissage automatique , peuvent être normalisées afin de fournir une plage de valeurs limitée.

Voir également

Remarques

  1. ^ "Le glossaire définitif du jargon mathématique supérieur — Canonique" . Coffre de maths . 2019-08-01 . Récupéré le 2019-11-20 .
  2. ^ Dans certaines occasions, les termes « canonique » et « normal » peuvent également être utilisés de manière interchangeable, comme dans la forme canonique de la Jordanie et la forme normale de la Jordanie (voir la forme normale de la Jordanie sur MathWorks ).
  3. ^ Le terme « canonisation » est parfois utilisé à tort pour cela.
  4. ^ "Grands nombres et notation scientifique" . Enseignement de l'alphabétisation quantitative . Récupéré le 2019-11-20 .
  5. ^ Ziegler, Günter M. (1995), Conférences sur les polytopes , Textes d'études supérieures en mathématiques, 152 , Springer-Verlag, pp. 117-118, ISBN 0-387-94365-X
  6. ^ "Description des bases de normalisation de base de données" . support.microsoft.com . Récupéré le 2019-11-20 .

Les références

  • Shilov, Georgi E. (1977), Silverman, Richard A. (éd.), Algèbre linéaire , Douvres, ISBN 0-486-63518-X.
  • Hansen, Vagn Lundsgaard (2006), Analyse fonctionnelle : Entrer dans l'espace Hilbert , World Scientific Publishing, ISBN 981-256-563-9.