Pengguna:Klasüo/bak pasir/khusus/3

Pengujian algoritma anagram menggunakan multiset sebagai bentuk kanonik: String "madam curie" dan "radium come" diberikan sebagai array C. Masing-masing diubah menjadi bentuk kanonik dengan menyortir. Karena kedua string yang diurutkan secara harfiah setuju, string asli adalah anagram satu sama lain.

Dalam matematika dan ilmu komputer, bentuk kanonik, normal, atau standar dari objek matematika adalah cara standar untuk menampilkan objek tersebut sebagai ekspresi matematika. Seringkali, itu adalah salah satu yang memberikan representasi paling sederhana dari suatu objek dan yang memungkinkannya untuk diidentifikasi dengan cara unik. Perbedaan antara bentuk "kanonik" dan "normal" bervariasi dari subbidang ke subbidang. Di sebagian besar bidang, bentuk kanonik menentukan representasi unik untuk setiap objek, sedangkan bentuk normal hanya menentukan bentuknya, tanpa persyaratan keunikan.

Bentuk kanonik dari bilangan bulat positif dalam representasi desimal adalah barisan digit berhingga yang tidak dimulai dengan nol. Secara umum, untuk kelas objek yang dimana relasi ekuivalensi didefinisikan, sebuah bentuk kanonik terdiri dari pilihan objek tertentu di setiap kelas. Misalnya:

• Bentuk normal Jordan adalah bentuk kanonik untuk keserupaan matriks.
• Bentuk baris eselon adalah bentuk kanonik, ketika menganggap matriks ekuivalen dan hasil kali kirinya dengan matriks invers.

Dalam ilmu komputer, dan secara umum dalam aljabar komputer, ketika mewakili objek matematika di komputer, biasanya ada banyak cara berbeda untuk mewakili objek yang sama. Dalam konteks ini, bentuk kanonik adalah representasi sedemikian rupa sehingga setiap objek memiliki representasi unik (dengan kanonikalisasi menjadi proses yang dimana representasi dimasukkan ke dalam bentuk kanoniknya). Jadi, kesetaraan dua objek dapat dengan mudah diuji dengan menguji kesetaraan bentuk kanoniknya.

Terlepas dari keuntungan ini, bentuk kanonik sering bergantung pada pilihan arbitrer (seperti mengurutkan variabel), yang menimbulkan kesulitan untuk menguji kesetaraan dua objek yang menghasilkan perhitungan yang independen. Oleh karena itu, dalam aljabar komputer, bentuk normal adalah gagasan yang lebih lemah: Sebuah bentuk normal adalah representasi sedemikian rupa sehingga nol direpresentasikan secara unik. Ini memungkinkan pengujian kesetaraan dengan menempatkan perbedaan dua objek dalam bentuk normal.

Bentuk kanonik juga bisa berarti bentuk diferensial yang didefinisikan secara alamiah (kanonik).

Definisi

Diberikan himpunan S objek dengan relasi ekuivalen R pada S, sebuah bentuk kanonik diberikan dengan menunjuk beberapa objek S menjadi "dalam bentuk kanonik", sedemikian rupa sehingga setiap objek yang dipertimbangkan setara dengan tepat satu objek dalam bentuk kanonik. Dengan kata lain, bentuk-bentuk kanonik dalam “S” mewakili kelas-kelas ekuivalen yang hanya sekali. Untuk menguji apakah dua objek ekuivalen, maka cukup menguji kesetaraan pada bentuk kanoniknya. Sebuah bentuk kanonik dengan demikian menyediakan teorema klasifikasi dan sebagainya, dalam hal ini tidak hanya mengklasifikasikan setiap kelas, tetapi juga memberikan perbedaan (kanonik) perwakilan untuk setiap objek di kelas.

Secara formal, kanonikalisasi sehubungan dengan suatu relasi ekuivalensi R pada suatu himpunan S merupakan pemetaan c:S→S sehingga untuk semua s, s₁, s₂ ∈ S:

1. c(s) = c(c(s))   (idempotensi),
2. s₁ R s₂ jika dan hanya jika c(s₁) = c(s₂)   (penegasan), dan
3. s R c(s)   (keterwakilan).

Properti 3 adalah; berikut dengan penerapan 2 ke 1.

Dalam istilah praktis, seringkali menguntungkan untuk dapat mengenali bentuk-bentuk kanonik. Ada juga pertanyaan algoritmik praktis yang perlu dipertimbangkan: bagaimana cara berpindahnya dari suatu objek tertentu s dalam S pada bentuk kanoniknya s*? Bentuk kanonik umumnya digunakan untuk membuat operasi dengan kelas ekuivalen menjadi sangat efektif. Misalnya, dalam aritmetika modular, bentuk kanonik untuk kelas residu biasanya diambil sebagai bilangan bulat non-negatif terkecil di dalamnya. Operasi pada kelas secara dilakukan dengan menggabungkan perwakilan ini, dan kemudian mengurangi hasilnya menjadi residu non-negatif yang menjadi sedikit. Persyaratan keunikan terkadang dilonggarkan, memungkinkan bentuk menjadi unik hingga beberapa relasi ekuivalen yang lebih baik, seperti memungkinkan untuk menyusun ulang istilah (jika tidak ada pengurutan alami pada istilah).

Bentuk kanonik mungkin hanya berupa konvensi, atau sebuah teorema dalam. Misalnya, polinomial secara konvensional ditulis dengan istilah dalam pangkat menurun: itu biasanya ditulis x² + x + 30 dibanding x + 30 + x², meskipun kedua bentuk tersebut mendefinisikan polinomial yang sama. Sebaliknya, keberadaan bentuk kanonik Jordan untuk sebuah matriks adalah sebuah teorema dalam.

Sejarah

Menurut OED dan LSJ, istilah dalam bahasa Inggris canonical berasal dari kata Yunani Kuno kanonikós (κανονικός, "beraturan, menurut aturan") dari kanṓn (κᾰνών, "tongkat, aturan"). Pengertian norm, standard, atau pola dasar telah digunakan dalam banyak disiplin ilmu. Penggunaan matematis dibuktikan dalam surat tahun 1738 dari Logan. Istilah dalam bahasa Jerman: kanonische Form dibuktikan dalam makalah tahun 1846 oleh Eisenstein, kemudian pada tahun yang sama Richelot menggunakan istilah Normalform dalam sebuah makalah, and in 1851 Sylvester writes:

"Saya sekarang melanjutkan ke [...] cara mereduksi fungsi Aljabar menjadi yang paling sederhana dan paling simetris, atau sebagai teman saya yang mengagumkan M. Pertapa mengusulkan untuk memanggil mereka, Canonical forms (bahasa Indonesia: Bentuk kanonik.")

Pada periode yang sama, penggunaan dibuktikan dengan Hesse ("Normalform"), Hermite ("forme canonique"), Borchardt ("forme canonique"), dan Cayley ("canonical form").

Pada tahun 1865, Kamus Sains, Sastra, dan Seni mendefinisikan bentuk kanonis sebagai:

"Dalam matematika, menunjukkan suatu bentuk, biasanya yang paling sederhana atau paling simetris, yang tanpa kehilangan keumumannya, semua fungsi dari kelas yang sama dapat direduksi."

Examples

Note: in this section, "up to" some equivalence relation E means that the canonical form is not unique in general, but that if one object has two different canonical forms, they are E-equivalent.

Large number notation

Standard form is used by many mathematicians and scientists to write extremely large numbers in a more concise and understandable way, the most prominent of which being the scientific notation.

Number theory

• Canonical representation of a positive integer
• Canonical form of a continued fraction

Linear algebra

Objects	A is equivalent to B if:	Normal form	Notes
Normal matrices over the complex numbers	$A=U^{*}BU$ for some unitary matrix U	Diagonal matrices (up to reordering)	This is the Spectral theorem
Matrices over the complex numbers	$A=UBV^{*}$ for some unitary matrices U and V	Diagonal matrices with real positive entries (in descending order)	Singular value decomposition
Matrices over an algebraically closed field	$A=P^{-1}BP$ for some invertible matrix P	Jordan normal form (up to reordering of blocks)
Matrices over an algebraically closed field	$A=P^{-1}BP$ for some invertible matrix P	Weyr canonical form (up to reordering of blocks)
Matrices over a field	$A=P^{-1}BP$ for some invertible matrix P	Frobenius normal form
Matrices over a principal ideal domain	$A=P^{-1}BQ$ for some invertible matrices P and Q	Smith normal form	The equivalence is the same as allowing invertible elementary row and column transformations
Matrices over the integers	$A=UB$ for some unimodular matrix U	Hermite normal form
Matrices over the integers modulo n		Howell normal form
Finite-dimensional vector spaces over a field K	A and B are isomorphic as vector spaces	$K^{n}$, n a non-negative integer

Algebra

Objects	A is equivalent to B if:	Normal form
Finitely generated R-modules with R a principal ideal domain	A and B are isomorphic as R-modules	Primary decomposition (up to reordering) or invariant factor decomposition

Geometry

In analytic geometry:

• The equation of a line: Ax + By = C, with A² + B² = 1 and C ≥ 0
• The equation of a circle: $(x-h)^{2}+(y-k)^{2}=r^{2}$

By contrast, there are alternative forms for writing equations. For example, the equation of a line may be written as a linear equation in point-slope and slope-intercept form.

Convex polyhedra can be put into canonical form such that:

• All faces are flat,
• All edges are tangent to the unit sphere, and
• The centroid of the polyhedron is at the origin.

Integrable systems

Every differentiable manifold has a cotangent bundle. That bundle can always be endowed with a certain differential form, called the canonical one-form. This form gives the cotangent bundle the structure of a symplectic manifold, and allows vector fields on the manifold to be integrated by means of the Euler-Lagrange equations, or by means of Hamiltonian mechanics. Such systems of integrable differential equations are called integrable systems.

Dynamical systems

The study of dynamical systems overlaps with that of integrable systems; there one has the idea of a normal form (dynamical systems).

Three dimensional geometry

In the study of manifolds in three dimensions, one has the first fundamental form, the second fundamental form and the third fundamental form.

Functional analysis

Objects	A is equivalent to B if:	Normal form
Hilbert spaces	If A and B are both Hilbert spaces of infinite dimension, then A and B are isometrically isomorphic.	$\ell ^{2}(I)$ sequence spaces (up to exchanging the index set I with another index set of the same cardinality)
Commutative C*-algebras with unit	A and B are isomorphic as C*-algebras	The algebra $C(X)$ of continuous functions on a compact Hausdorff space, up to homeomorphism of the base space.

Classical logic

Artikel utama: Canonical form (Boolean algebra)

• Negation normal form
• Conjunctive normal form
• Disjunctive normal form
• Algebraic normal form
• Prenex normal form
• Skolem normal form
• Blake canonical form, also known as the complete sum of prime implicants, the complete sum, or the disjunctive prime form

Set theory

• Cantor normal form of an ordinal number

Game theory

• Normal form game

Proof theory

• Normal form (natural deduction)

Rewriting systems

Artikel utama: Normal form (abstract rewriting)

The symbolic manipulation of a formula from one form to another is called a "rewriting" of that formula. One can study the abstract properties of rewriting generic formulas, by studying the collection of rules by which formulas can be validly manipulated. These are the "rewriting rules"—an integral part of an abstract rewriting system. A common question is whether it is possible to bring some generic expression to a single, common form, the normal form. If different sequences of rewrites still result in the same form, then that form can be termed a normal form, with the rewrite being called a confluent. It is not always possible to obtain a normal form.

Lambda calculus

• A lambda term is in beta normal form if no beta reduction is possible; lambda calculus is a particular case of an abstract rewriting system. In the untyped lambda calculus, for example, the term $(\lambda x.(xx)\;\lambda x.(xx))$ doesn't have a normal form. In the typed lambda calculus, every well-formed term can be rewritten to its normal form.

Graph theory

Artikel utama: Graph canonization

In graph theory, a branch of mathematics, graph canonization is the problem of finding a canonical form of a given graph G. A canonical form is a labeled graph Canon(G) that is isomorphic to G, such that every graph that is isomorphic to G has the same canonical form as G. Thus, from a solution to the graph canonization problem, one could also solve the problem of graph isomorphism: to test whether two graphs G and H are isomorphic, compute their canonical forms Canon(G) and Canon(H), and test whether these two canonical forms are identical.

Computing

In computing, the reduction of data to any kind of canonical form is commonly called data normalization.

For instance, database normalization is the process of organizing the fields and tables of a relational database to minimize redundancy and dependency.

In the field of software security, a common vulnerability is unchecked malicious input (see Code injection). The mitigation for this problem is proper input validation. Before input validation is performed, the input is usually normalized by eliminating encoding (e.g., HTML encoding) and reducing the input data to a single common character set.

Other forms of data, typically associated with signal processing (including audio and imaging) or machine learning, can be normalized in order to provide a limited range of values.

In content management, the concept of a single source of truth (SSOT) is applicable, just as it is in database normalization generally and in software development. Competent content management systems provide logical ways of obtaining it, such as transclusion.

See also

• Canonicalization
• Canonical basis
• Canonical class
• Normalization (disambiguation)
• Standardization

References

• 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 .