Forma canônica - Canonical form

Teste de anagrama algorítmico usando multiconjuntos como formas canônicas: As strings " madam curie " e " radium came " são fornecidas como matrizes C. Cada um é convertido em uma forma canônica por classificação. Como as duas strings classificadas concordam literalmente, as strings originais eram anagramas uma da outra.

Em matemática e ciência da computação , uma canônica , normais ou padrão forma de um objeto matemático é uma maneira padrão de apresentar esse objeto como uma expressão matemática . Muitas vezes, é aquele que fornece a representação mais simples de um objeto e que permite que ele seja identificado de uma maneira única. A distinção entre formas "canônicas" e "normais" varia de subcampo para subcampo. Na maioria dos campos, uma forma canônica especifica uma representação única para cada objeto, enquanto uma forma normal simplesmente especifica sua forma, sem a exigência de exclusividade.

A forma canônica de um número inteiro positivo na representação decimal é uma sequência finita de dígitos que não começa com zero. Mais geralmente, para uma classe de objetos na qual uma relação de equivalência é definida, uma forma canônica consiste na escolha de um objeto específico em cada classe. Por exemplo:

• A forma normal de Jordan é uma forma canônica de semelhança de matriz .
• A forma escalonada de linha é uma forma canônica, quando se considera como equivalente uma matriz e seu produto esquerdo por uma matriz invertível .

Na ciência da computação, e mais especificamente na álgebra computacional , ao representar objetos matemáticos em um computador, geralmente existem muitas maneiras diferentes de representar o mesmo objeto. Nesse contexto, uma forma canônica é uma representação tal que cada objeto tem uma representação única ( sendo a canonicalização o processo pelo qual uma representação é colocada em sua forma canônica). Assim, a igualdade de dois objetos pode ser facilmente testada testando a igualdade de suas formas canônicas.

Apesar dessa vantagem, as formas canônicas freqüentemente dependem de escolhas arbitrárias (como ordenar as variáveis), que apresentam dificuldades para testar a igualdade de dois objetos resultando em cálculos independentes. Portanto, em álgebra computacional, a forma normal é uma noção mais fraca: uma forma normal é uma representação tal que o zero é representado de forma única. Isso permite testar a igualdade colocando a diferença de dois objetos na forma normal.

A forma canônica também pode significar uma forma diferencial definida de forma natural (canônica).

Definição

Dado um conjunto S de objetos com uma relação de equivalência R em S , uma forma canônica é dada ao designar alguns objetos de S como "na forma canônica", de modo que todo objeto em consideração é equivalente a exatamente um objeto na forma canônica. Em outras palavras, as formas canônicas em S representam as classes de equivalência, uma e apenas uma vez. Para testar se dois objetos são equivalentes, basta testar a igualdade em suas formas canônicas. Uma forma canónica proporciona assim um teorema de classificação e mais, na medida em que não só classifica cada classe, mas também dá um distinguidos (canónica) representativo para cada objecto na classe.

Formalmente, uma canonicalização em relação a uma relação de equivalência R em um conjunto S é um mapeamento c : S → S tal que para todos os s , s ₁ , s ₂ ∈ S :

1. c ( s ) = c ( c ( s )) ( idempotência ),
2. s ₁ R s ₂ se e somente se c ( s ₁ ) = c ( s ₂ ) (decisão), e
3. s R c ( s ) (representatividade).

A propriedade 3 é redundante; segue aplicando 2 a 1.

Em termos práticos, muitas vezes é vantajoso ser capaz de reconhecer as formas canônicas. Há também uma questão prática e algorítmica a ser considerada: como passar de um dado objeto s em S para sua forma canônica s *? As formas canônicas geralmente são usadas para tornar mais eficaz a operação com classes de equivalência. Por exemplo, na aritmética modular , a forma canônica para uma classe de resíduo é geralmente considerada como o menor número inteiro não negativo nela. As operações nas classes são realizadas combinando esses representantes e, em seguida, reduzindo o resultado ao seu menor resíduo não negativo. O requisito de exclusividade às vezes é relaxado, permitindo que as formas sejam exclusivas até alguma relação de equivalência mais fina, como permitir a reordenação dos termos (se não houver ordenação natural dos termos).

Uma forma canônica pode ser simplesmente uma convenção ou um teorema profundo. Por exemplo, polinômios são convencionalmente escritos com os termos em potências descendentes: é mais comum escrever x ² + x + 30 do que x + 30 + x ² , embora as duas formas definam o mesmo polinômio. Em contraste, a existência da forma canônica de Jordan para uma matriz é um teorema profundo.

Exemplos

Nota: nesta seção, " até " alguma relação de equivalência E significa que a forma canônica não é única em geral, mas que se um objeto tem duas formas canônicas diferentes, elas são E-equivalentes.

Notação de grande número

A forma padrão é usada por muitos matemáticos e cientistas para escrever números extremamente grandes de uma forma mais concisa e compreensível, sendo a mais proeminente a notação científica .

Teoria dos Números

• Representação canônica de um número inteiro positivo
• Forma canônica de uma fração contínua

Álgebra Linear

Objetos	A é equivalente a B se:	Forma normal	Notas
Matrizes normais sobre os números complexos	${\ displaystyle A = U ^ {*} BU}$para alguma matriz unitária U	Matrizes diagonais (até reordenamento)	Este é o teorema espectral
Matrizes sobre os números complexos	${\ displaystyle A = UBV ^ {*}}$para algumas matrizes unitárias U e V	Matrizes diagonais com entradas reais positivas (em ordem decrescente)	Decomposição de valor singular
Matrizes sobre um campo algébricamente fechado	${\ displaystyle A = P ^ {- 1} BP}$para alguma matriz invertível P	Forma normal de Jordan (até reordenamento de blocos)
Matrizes sobre um campo algébricamente fechado	${\ displaystyle A = P ^ {- 1} BP}$para alguma matriz invertível P	Forma canônica Weyr (até reordenação de blocos)
Matrizes sobre um campo	${\ displaystyle A = P ^ {- 1} BP}$para alguma matriz invertível P	Forma normal de Frobenius
Matrizes sobre um domínio ideal principal	${\ displaystyle A = P ^ {- 1} BQ}$para algumas matrizes invertíveis P e Q	Smith forma normal	A equivalência é a mesma que permitir transformações elementares invertíveis de linha e coluna
Matrizes sobre inteiros	${\ displaystyle A = UB}$para alguma matriz unimodular U	Forma normal de hermite
Espaços vetoriais de dimensão finita sobre um campo K	A e B são isomórficos como espaços vetoriais	${\ displaystyle K ^ {n}}$, n um inteiro não negativo

Álgebra

Geometria

Em geometria analítica :

• A equação de uma linha: Ax  +  By  =  C , com A ²  +  B ²  = 1 e C  ≥ 0
• A equação de um círculo: ${\ displaystyle (xh) ^ {2} + (yk) ^ {2} = r ^ {2}}$

Em contraste, existem formas alternativas para escrever equações. Por exemplo, a equação de uma linha pode ser escrita como uma equação linear na forma de ponto-inclinação e inclinação-interceptação .

Os poliedros convexos podem ser colocados na forma canônica de modo que:

• Todos os rostos são planos,
• Todas as arestas são tangentes à esfera unitária, e
• O centróide do poliedro está na origem.

Sistemas integráveis

Cada variedade diferenciável tem um feixe cotangente . Esse feixe pode sempre ser dotado de uma certa forma diferencial , chamada de forma única canônica . Esta forma dá ao feixe cotangente a estrutura de uma variedade simplética e permite que campos de vetores na variedade sejam integrados por meio das equações de Euler-Lagrange ou por meio da mecânica hamiltoniana . Esses sistemas de equações diferenciais integráveis são chamados de sistemas integráveis .

Sistemas dinâmicos

O estudo de sistemas dinâmicos se sobrepõe ao de sistemas integráveis ; aí se tem a ideia de uma forma normal (sistemas dinâmicos) .

Geometria tridimensional

No estudo de variedades em três dimensões, tem-se a primeira forma fundamental , a segunda forma fundamental e a terceira forma fundamental .

Análise funcional

Objetos	A é equivalente a B se:	Forma normal
Espaços de Hilbert	Se A e B são ambos espaços de Hilbert de dimensão infinita, então A e B são isomorficamente isomórficos.	${\ displaystyle \ ell ^ {2} (I)}$ espaços de sequência (até a troca do conjunto de índices I por outro conjunto de índices da mesma cardinalidade )
-Álgebras comutativas com unidade ${\ displaystyle C ^ {*}}$	A e B são isomórficos como -álgebras ${\ displaystyle C ^ {*}}$	A álgebra de funções contínuas em um espaço de Hausdorff compacto , até o homeomorfismo do espaço de base. ${\ displaystyle C (X)}$

Lógica clássica

• Forma normal de negação
• Forma normal conjuntiva
• Forma normal disjuntiva
• Forma normal algébrica
• Forma normal Prenex
• Skolem forma normal
• Forma canônica de Blake , também conhecida como a soma completa dos implicantes primos, a soma completa ou a forma primária disjuntiva

Teoria de conjuntos

• Cantor forma normal de um número ordinal

Teoria do jogo

• Jogo de forma normal

Teoria da Prova

• Forma normal (dedução natural)

Sistemas de reescrita

A manipulação simbólica de uma fórmula de uma forma para outra é chamada de "reescrita" dessa fórmula. Pode-se estudar as propriedades abstratas de reescrever fórmulas genéricas, estudando o conjunto de regras pelas quais as fórmulas podem ser manipuladas de forma válida. Essas são as "regras de reescrita" - uma parte integrante de um sistema de reescrita abstrato . Uma pergunta comum é se é possível trazer alguma expressão genérica a uma única forma comum, a forma normal. Se sequências diferentes de reescritas ainda resultam na mesma forma, então essa forma pode ser chamada de forma normal, com a reescrita sendo chamada de confluente. Nem sempre é possível obter uma forma normal.

Cálculo lambda

• Um termo lambda está na forma normal beta se nenhuma redução beta for possível; cálculo lambda é um caso particular de sistema de reescrita abstrata. No cálculo lambda não digitado, por exemplo, o termo não tem uma forma normal. No cálculo lambda digitado, cada termo bem formado pode ser reescrito em sua forma normal.${\ displaystyle (\ lambda x. (xx) \; \ lambda x. (xx))}$

Teoria dos grafos

Em teoria dos grafos , um ramo da matemática, gráfico canonização é o problema de encontrar uma forma canônica de um dado grafo G . Uma forma canónica é um gráfico marcado Canon ( L ) que é isomorfa a L , de tal modo que cada gráfico que é isomorfa a L tem a mesma forma canónica como L . Assim, a partir de uma solução para o problema de canonização de grafos, também se poderia resolver o problema de isomorfismo de grafos : para testar se dois grafos G e H são isomórficos, calcule suas formas canônicas Canon ( G ) e Canon ( H ), e teste se estas duas formas canônicas são idênticas.

Informática

Na computação , a redução de dados a qualquer tipo de forma canônica é comumente chamada de normalização de dados .

Por exemplo, a normalização do banco de dados é o processo de organização dos campos e tabelas de um banco de dados relacional para minimizar a redundância e a dependência.

No campo da segurança de software , uma vulnerabilidade comum é a entrada mal-intencionada não verificada (consulte Injeção de código ). A mitigação para este problema é a validação de entrada adequada . Antes de a validação de entrada ser realizada, a entrada é normalmente normalizada eliminando a codificação (por exemplo, codificação HTML ) e reduzindo os dados de entrada a um único conjunto de caracteres comum .

Outras formas de dados, normalmente associadas ao processamento de sinal (incluindo áudio e imagem ) ou aprendizado de máquina , podem ser normalizadas a fim de fornecer uma faixa limitada de valores.

Veja também

• Canonização
• Base canônica
• Aula canônica
• Normalização (desambiguação)
• estandardização

Notas

Referências

• Shilov, Georgi E. (1977), Silverman, Richard A. (ed.), Linear Algebra , Dover, ISBN 0-486-63518-X.
• Hansen, Vagn Lundsgaard (2006), Functional Analysis: Entering Hilbert Space , World Scientific Publishing, ISBN 981-256-563-9.