Kanonikus alak

A matematika és a számítástudomány területén valamely kifejezés kanonikus alakja, kanonikus formája, illetve normál- vagy standard alakja alatt az a szabványos mód értendő, ahogy azt az objektumot matematikai kifejezésként leírjuk. A „kanonikus” és „normál” alakok közti különbségtétel az egyes tudományterületeken más és más lehet. A legtöbb területen a kanonikus alak egyfajta unikális, egyedi reprezentációja az adott objektumnak, míg a normál alak meghatározza a formai követelményeket, de nem követeli meg az unikalitást.

Például egy pozitív egész szám tízes számrendszerbeli kanonikus alakja számjegyek véges sorozata, mely nem kezdődik nullával.

Általánosabban olyan objektumosztályra, amin ekvivalenciarelációt definiálunk, minden egyes osztályból egy specifikus objektum kiválasztásával határozható meg a kanonikus alak. Például a mátrixok Jordan-féle normálformája a mátrixok hasonlósága szerinti kanonikus alak, a mátrix lépcsős alakja pedig akkor kanonikus alak, ha ekvivalensnek tekintjük a mátrixot egy invertálható mátrixszal való balszorzatával.

A számítástudományban, főként annak a szimbolikus számításokkal foglalkozó területén általában ugyanazt az objektumot számos különböző módon ki lehet fejezni. Ebben a kontextusban egy reprezentáció kanonikus alakja olyan ábrázolás, ahol minden objektum egyedi reprezentációval rendelkezik. Így két objektum azonossága könnyen vizsgálható kanonikus alakjaik egyezésének vizsgálatával. A kanonikus alakok azonban gyakran önkényes választásoktól függenek (pl. a változók sorrendjétől), ami nehézséget okoz különböző számításokban szereplő objektumok egyenlőségének tesztelésében. Ezért a számítógépes algebrában használatos a gyengébb, „normál alak”. A normál alak olyan reprezentáció, melyben a nulla egyedi módon jeleníthető meg. Ez megengedi az egyenlőség tesztelését két objektum különbsége normálalakjának tesztelésével.

A számítástudományban a többfajta módon reprezentálható adatok unikális, kanonikus alakba való átalakítását kanonikalizációnak nevezik.

Meghatározás

Tegyük fel, hogy létezik objektumok egy S halmaza, egy rajtuk értelmezett ekvivalenciarelációval. Az S-ben lévő elemek akkor tekinthetők úgy, hogy kanonikus alakban vannak, ha minden szóba jövő elem pontosan egy kanonikus alakban lévő elemmel ekvivalens. Másképpen, az S-ben lévő kanonikus alakok az ekvivalenciaosztályoknak feleltethetők meg. Két elem ekvivalenciájának ellenőrzéséhez elegendő kanonikus alakjaik egyenlőségét vizsgálni. A kanonikus alak így meghatároz egy osztályozási tételt és ennél tovább is megy, nemcsak minden osztályt besorol, hanem hozzájuk rendel egy megkülönböztetett (kanonikus) reprezentációt is.

A gyakorlatban nyilván szeretnénk, ha a kanonikus alakok felismerhetőek lennének. Egy praktikus, algoritmikus kérdés is felmerül: hogyan lehet átalakítani az S-ben lévő s objektumot kanonikus s* alakba? A kanonikus alakok általában arra jók, hogy az ekvivalenciaosztályokkal való műveletvégzést hatékonyabbá tegyék. Például a moduláris aritmetika területén egy maradékosztály kanonikus alakja általában a legkisebb nemnegatív egész szám. A maradékosztályokon végzett műveletek ezekkel a kanonikus alakokkal történnek, majd az eredményt újból redukálják a legkisebb nemnegatív maradékra. Az egyediség követelményét néha kevésbé szigorúan értelmezik, megengedve, hogy az alakok valamilyen finomabb ekvivalenciareláció szerint legyenek csak egyediek, például megengedhetjük a kifejezés tagjainak átrendezését (ha nincs valamilyen természetes sorba rendezési lehetőség közöttük).

Egy kanonikus alak lehet egyszerűen egy kényelmes konvenció, vagy egy mély tétel eredménye.

Például a polinomokat hagyományosan kitevő szerinti csökkenő sorrendben szokás felírni: szokásosabb az x² + x + 30 alak, mint az x + 30 + x², bár mindkettő ugyanazt a polinomot határozza meg. Ezzel ellentétben a mátrixok Jordan-féle normálformáját nem csak megszokás, hanem egy mély elméleti tétel alapozza meg.

Példák

Megjegyzés: ebben a szakaszban a valamely E ekvivalenciareláció „erejéig” kifejezés azt jelenti, hogy a kanonikus alak nem teljesen unikális, de ha egy objektumnak lét különböző kanonikus alakja lehet, azok E-ekvivalensek.

Lineáris algebra

Objektumok	A ekvivalens B-vel, ha:	Normálalak	Jegyzet
Normális mátrixok komplex számok fölött	$A=U^{*}BU$ valamely U unitér mátrixra	Diagonális mátrixok (átrendezés erejéig)	Ez a spektráltétel.
Mátrixok komplex számok fölött	$A=UBV^{*}$ valamely U és V unitér mátrixokra	Diagonálmátrixok pozitív valós értékekkel (csökkenő sorrendben)	Szinguláris érték szerinti felbontás (SVD)
Mátrixok algebrailag zárt test fölött	$A=P^{-1}BP$ valamely P invertálható mátrixra	Jordan-féle normálforma (a blokkok átrendezésének erejéig)
Mátrixok algebrailag zárt test fölött	$A=P^{-1}BP$ valamely P invertálható mátrixra	Weyr-féle kanonikus forma (a blokkok átrendezésének erejéig)
Mátrixok test fölött	$A=P^{-1}BP$ valamely P invertálható mátrixra	Frobenius-normálforma
Mátrixok főideálgyűrű fölött	$A=P^{-1}BQ$ valamely P és Q invertálható mátrixokra	Smith-normálforma	Az ekvivalencia szerint megengedjük az invertálható elemi sor- és oszloptranszformációkat
K test fölötti véges dimenziós vektorterek	A és B izomorf vektorterek	$K^{n}$, n nem negatív egész szám

Klasszikus logika

• Negációs normálforma
• Konjunktív normálforma
• Diszjunktív normálforma
  • Blake-féle kanonikus alak vagy diszjunktív prímforma
• Algebrai normálforma
• Prenex-normálforma
• Skolem-normálforma

Funkcionálanalízis

Objektumok	A ekvivalens B-vel, ha:	Normálalak
Hilbert-terek	Ha A és B mindkettő elválasztható, végtelen dimenziós Hilbert-terek, akkor A és B izometrikusan izomorf.	$\ell ^{2}(I)$ Hilbert-féle sorozattér (az I indexhalmaz ugyanolyan számosságú indexhalmazra cserélésének erejéig)
Kommutatív $C^{*}$-algebrák	A és B izomorfak mint $C^{*}$-algebrák	A kompakt Hausdorff-tér folytonos függvényeinek $C(X)$ algebrája, az alaptér homeomorfizmusának erejéig.

Számelmélet

Pozitív egész szám kanonikus alakja 1-nél nagyobb természetes számok prímfelbontása során létrejött szorzat, prímszámok (prímhatványok) szorzata (megengedve az egytényezős szorzatot).

Bármely 1-nél nagyobb természetes szám felbontható prímszámok szorzatára. A számelmélet alaptétele szerint minden ilyen számnak – a prímtényezők sorrendjétől eltekintve – egyértelműen megadható a kanonikus alakja.

A $n=\prod p_{i}^{\alpha _{i}}$ prímfelbontást nevezik a szám kanonikus alakjának (pl. $12=2^{2}\cdot 3$).

Az 1 nem prímszám és nem bontható fel prímszámok szorzatára, így kanonikus alakja nincs. A prímszámok kanonikus alakja megegyezik önmagukkal (önmaguk első hatványával).

Lásd még: Kanonikus alakok listája (1–1000)

Lánctörtek

• Lánctörtek kanonikus alakja: egyszerű vagy reguláris

Algebra

Objektumok	A ekvivalens B-vel, ha:	Normálalak
R-főideálgyűrű felett végesen generált R-modulusok	A és B izomorf R-modulusok	Prímfelbontás (átrendezés erejéig) vagy invariáns faktorfelbontás

Geometria

• Az egyenes egyenlete: Ax + By = C, ahol A² + B² = 1 és C ≥ 0
• A kör egyenlete: $(x-h)^{2}+(y-k)^{2}=r^{2}\,$

Léteznek persze a fenti egyenleteknek alternatív formái is. Például az egyenes egyenlete egy lineáris egyenlet, ami felírható például pont–meredekség ($y-y_{1}=m(x-x_{1})$), illetve Y tengellyel való metszéspont–meredekség ($y=mx+b$) alapján is.

Túl nagy, illetve túl kicsi számok normálalakja

A matematikusoknak és természettudósoknak gyakran extrém nagy számokat, vagy reciprokértékben extrém nagy számokat kell leírniuk. Ekkor a normálalak tömörebb és érthetőbb megoldás lehet. Például 0,009 = 9 · 10⁻³.

Halmazelmélet

• Rendszámok Cantor-féle normálalakja

Játékelmélet

• Játék normálalakja

Bizonyításelmélet

• Természetes levezetés normálalakja

Kifejezés-újraíró rendszerek

• Egy absztrakt kifejezés-újraíró rendszerben a normálalak egy irreducibilis objektum.

Lambda-kalkulus

• Béta-normálalak, ha nem érhető el további β-redukció; a Lambda-kalkulus az absztrakt kifejezés-újraíró rendszerek speciális esete.

Dinamikus rendszerek

• Bifurkáció normálalakja

Differenciális alakok

A kanonikus differenciális alakok közé tartozik a tautologikus 1-forma és a kanonikus szimplektikus forma, melyek fontos szerepet játszanak a Hamilton-féle mechanika és a szimplektikus sokaságok tanulmányozásában.

Számítástudomány

A számítástudomány területén a bemeneti adatok valamely kanonikus alakra történő redukálását adatnormalizációnak nevezik.

Például az adatbázis-normalizáció során egy relációs adatbázis mezőinek és tábláinak olyan átszervezése, ami az adatok redundanciáját és függőségét minimalizálja.

Az alkalmazásbiztonság területén gyakori oka a sebezhetőségeknek az ellenőrizetlen, rosszindulatú bemeneti adat. Ez ellen leghatékonyabban a megfelelő adatvalidációval lehet fellépni. Az adatvalidáció előtt a bemeneti adatokat normalizálni kell, például a különböző karakterkódolásokat egy közös karakterkészletre kell konvertálni stb.

A jelfeldolgozás területén (ideérve a hang- és képfeldolgozás mellett a gépi tanulási módszereket is) az adatok normalizálásán egy értéktartományra való korlátozásukat kell érteni.

Kapcsolódó szócikkek

• Kanonikalizáció
  • Gráfok kanonikalizációja
• Kanonikus bázis
• Normalizáció
• Szabványosítás

Források

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