Ugrás a tartalomhoz

Kanonikus alak

Ellenőrzött
A Wikipédiából, a szabad enciklopédiából

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(wd) 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.[1]

Meghatározás

[szerkeszté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 x2 + x + 30 alak, mint az x + 30 + x2, 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

[szerkesztés]

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

[szerkesztés]
Objektumok A ekvivalens B-vel, ha: Normálalak Jegyzet
Normális mátrixok komplex számok fölött valamely U unitér mátrixra Diagonális mátrixok (átrendezés erejéig) Ez a spektrálfelbontási tétel(wd)
Mátrixok komplex számok fölött 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 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 valamely P invertálható mátrixra Weyr-féle kanonikus forma (a blokkok átrendezésének erejéig)
Mátrixok test fölött valamely P invertálható mátrixra Frobenius-normálforma
Mátrixok főideálgyűrű fölött 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 , n nem negatív egész szám

Klasszikus logika

[szerkesztés]

Funkcionálanalízis

[szerkesztés]
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. Hilbert-féle sorozattér (az I indexhalmaz ugyanolyan számosságú indexhalmazra cserélésének erejéig)
Kommutatív -algebrák A és B izomorfak mint -algebrák A kompakt Hausdorff-tér folytonos függvényeinek algebrája, az alaptér homeomorfizmusának erejéig.

Számelmélet

[szerkesztés]

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 prímfelbontást nevezik a szám kanonikus alakjának (pl. ).

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).[2]

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

Lánctörtek

[szerkesztés]

Algebra

[szerkesztés]
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

[szerkesztés]
  • Az egyenes egyenlete: Ax + By = C, ahol A2 + B2 = 1 és C ≥ 0
  • A kör egyenlete:

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 (), illetve Y tengellyel való metszéspont–meredekség () alapján is.

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

[szerkesztés]

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−3.

Halmazelmélet

[szerkesztés]

Játékelmélet

[szerkesztés]

Bizonyításelmélet

[szerkesztés]

Kifejezés-újraíró rendszerek

[szerkesztés]

Lambda-kalkulus

[szerkesztés]

Dinamikus rendszerek

[szerkesztés]

Gráfelmélet

[szerkesztés]

Differenciális alakok

[szerkesztés]

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

[szerkesztés]

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

[szerkesztés]

Jegyzetek

[szerkesztés]
  1. Gyakran és tévesen a kanonizáció kifejezést alkalmazzák erre.
  2. Bege Antal: Bevezetés a számelméletbe. Kolozsvár: Scientia. 2002. 38–40. o. ISBN 973-85750-7-9

Források

[szerkesztés]
  • 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.