Kanonická forma - Canonical form
![]() | tento článek potřebuje další citace pro ověření.Prosinec 2007) (Zjistěte, jak a kdy odstranit tuto zprávu šablony) ( |
v matematika a počítačová věda, a kanonický, normálnínebo Standard formulář a matematický objekt je standardní způsob prezentace tohoto objektu jako matematické vyjádření. Často je to ten, který poskytuje nejjednodušší reprezentaci objektu a který umožňuje jeho jedinečnou identifikaci.[1] Rozdíl mezi „kanonickými“ a „normálními“ formami se liší od podpole k podpole. Ve většině polí kanonický formulář určuje a unikátní reprezentace pro každý objekt, zatímco normální forma jednoduše specifikuje jeho formu, bez požadavku jedinečnosti.[2]
Kanonická forma a kladné celé číslo v desetinné vyjádření je konečná posloupnost číslic, která nezačíná nulou. Obecněji řečeno, pro třídu objektů, na kterých vztah ekvivalence je definováno, a kanonická forma spočívá ve výběru konkrétního objektu v každé třídě. Například:
- Jordan normální forma je kanonická forma pro podobnost matice.
- The řádkový sled je kanonická forma, když se za ekvivalent považuje matice a její levý součin pomocí invertibilní matice.
V počítačové vědě a konkrétněji v počítačová algebra, když představují matematické objekty v počítači, obvykle existuje mnoho různých způsobů, jak reprezentovat stejný objekt. V této souvislosti a kanonická forma je reprezentace taková, že každý objekt má jedinečnou reprezentaci (s kanonizace což je proces, jehož prostřednictvím se reprezentace uvádí do kanonické podoby).[3] Rovnost dvou objektů lze tedy snadno otestovat testováním rovnosti jejich kanonických forem.
Navzdory této výhodě kanonické formy často závisí na libovolných volbách (jako je objednávání proměnných), což přináší potíže s testováním rovnosti dvou objektů, které jsou výsledkem nezávislých výpočtů. Proto v počítačové algebře normální forma je slabší pojem: A normální forma je reprezentace taková, že nula je jedinečně reprezentována. To umožňuje testování rovnosti vložením rozdílu dvou objektů do normální formy.
Kanonická forma může také znamenat a diferenciální forma který je definován přirozeným (kanonickým) způsobem.
Definice
Vzhledem k sadě S předmětů s vztah ekvivalence R na S, a kanonická forma je dáno určením některých objektů S být „v kanonické formě“, takže každý uvažovaný objekt je ekvivalentní přesně jednomu objektu v kanonické formě. Jinými slovy, kanonické formy v S představují třídy ekvivalence, jednou a pouze jednou. Chcete-li otestovat, zda jsou dva objekty ekvivalentní, stačí otestovat rovnost na jejich kanonických formách. Kanonický formulář tak poskytuje věta o klasifikaci a další v tom, že nejen klasifikuje každou třídu, ale také poskytuje rozlišujícího (kanonického) zástupce pro každý objekt ve třídě.
Formálně kanonizace s ohledem na vztah ekvivalence R na setu S je mapování C:S→S takové, že pro všechny s, s1, s2 ∈ S:
- C(s) = C(C(s)) (idempotence ),
- s1 R s2 kdyby a jen kdyby C(s1) = C(s2) (rozhodnost) a
- s R C(s) (reprezentativnost).
Vlastnost 3 je nadbytečná; z toho vyplývá použití 2 na 1.
Z praktického hlediska je často výhodné rozeznávat kanonické formy. Zvažovat lze také praktickou algoritmickou otázku: jak projít z daného objektu s v S do kanonické podoby s*? K zefektivnění práce s třídami ekvivalence se obecně používají kanonické formy. Například v modulární aritmetika, kanonická forma pro třídu zbytků se v ní obvykle bere jako nejmenší nezáporné celé číslo. Operace na třídách se provádějí kombinací těchto zástupců a následným snížením výsledku na jeho nejméně nezáporné reziduum. Požadavek jedinečnosti je někdy uvolněný, což umožňuje jedinečnost forem až po jemnější vztah ekvivalence, například umožnění přeskupení podmínky (pokud neexistuje přirozené řazení podle podmínek).
Kanonickou formou může být jednoduše konvence nebo hluboká věta. Například polynomy jsou běžně psány s termíny v sestupných silách: je běžnější psát X2 + X + 30 než X + 30 + X2, ačkoli obě formy definují stejný polynom. Naproti tomu existence Jordan kanonická forma protože matice je hluboká věta.
Příklady
Poznámka: v této části „až do „nějaký vztah ekvivalence E znamená, že kanonická forma není obecně jedinečná, ale že pokud má jeden objekt dvě různé kanonické formy, jsou ekvivalentem E.
Velké číslo
Standardní forma je používána mnoha matematiky a vědci k extrémnímu psaní vysoká čísla výstižnějším a srozumitelnějším způsobem, z nichž nejvýznamnější je věděcký zápis.[4]
Teorie čísel
- Kanonické vyjádření kladného celého čísla
- Kanonická forma a pokračující zlomek
Lineární algebra
Objekty | A je ekvivalentní k B li: | Normální forma | Poznámky |
---|---|---|---|
Normální matice nad komplexní čísla | pro některé unitární matice U | Diagonální matice (do objednání) | To je Spektrální věta |
Matice nad komplexními čísly | pro některé unitární matice U a PROTI | Diagonální matice se skutečnými kladnými údaji (v sestupném pořadí) | Rozklad singulární hodnoty |
Matice nad algebraicky uzavřené pole | pro některé invertibilní matice P | Jordan normální forma (až do nového pořadí bloků) | |
Matice nad algebraicky uzavřené pole | pro některé invertibilní matice P | Weyr kanonická forma (až do nového pořadí bloků) | |
Matice nad polem | pro některé invertibilní matice P | Frobeniova normální forma | |
Matice nad a hlavní ideální doména | pro některé invertibilní Matice P a Q | Smith normální forma | Ekvivalence je stejná jako povolení invertovatelných elementárních transformací řádků a sloupců |
Matice nad celými čísly | pro některé unimodulární matice U | Poustevník normální forma | |
Konečně-dimenzionální vektorové prostory přes pole K. | A a B jsou izomorfní jako vektorové prostory | , n nezáporné celé číslo |
Algebra
Objekty | A je ekvivalentní k B li: | Normální forma |
---|---|---|
Konečně vygenerováno R-moduly s R A hlavní ideální doména | A a B jsou izomorfní jako R- moduly | Primární rozklad (až do nového pořadí) nebo invariantní rozklad faktoru |
Geometrie
- Rovnice přímky: Sekera + Podle = C, s A2 + B2 = 1 a C ≥ 0
- Rovnice kružnice:
Naproti tomu existují alternativní formy pro psaní rovnic. Například rovnici přímky lze napsat jako a lineární rovnice v bodový sklon a forma sklonu.
Konvexní mnohostěn lze dát do kanonická forma takové, že:
- Všechny tváře jsou ploché,
- Všechny hrany jsou tečny k jednotkové kouli a
- Těžiště mnohostěnu je na počátku.[5]
Integrovatelné systémy
Každý rozlišitelný potrubí má kotangenský svazek. Ten svazek může být vždy vybaven určitým diferenciální forma, volal kanonický jeden formulář. Tato forma dává kotangensému svazku strukturu a symplektické potrubí, a umožňuje integraci vektorových polí na potrubí pomocí Euler-Lagrangeovy rovnice, nebo prostřednictvím Hamiltoniánská mechanika. Takové systémy jsou integrovatelné diferenciální rovnice jsou nazývány integrovatelné systémy.
Dynamické systémy
Studium dynamické systémy se překrývá s tím integrovatelné systémy; tam má člověk představu o normální forma (dynamické systémy).
Trojrozměrná geometrie
Při studiu rozdělovačů ve třech rozměrech má jeden první základní forma, druhá základní forma a třetí základní forma.
Funkční analýza
Objekty | A je ekvivalentní k B li: | Normální forma |
---|---|---|
Hilbertovy prostory | Li A a B jsou tedy oba Hilbertovy prostory nekonečné dimenze A a B jsou izometricky izomorfní. | posloupnosti mezer (až do výměny sady indexů Já s jinou stejnou sadou indexů mohutnost ) |
Komutativní -algebry s jednotkou | A a B jsou izomorfní jako -algebry | Algebra spojitých funkcí na a kompaktní Hausdorffův prostor, až do homeomorfismus základního prostoru. |
Klasická logika
- Negativní normální forma
- Spojovací normální forma
- Disjunktivní normální forma
- Algebraická normální forma
- Prenex normální forma
- Skolem normální forma
- Blake kanonická forma, známý také jako úplný součet prvočíselných implikantů, úplný součet nebo disjunktní prvočíslo
Teorie množin
Herní teorie
Teorie důkazů
Přepisovací systémy
Symbolická manipulace s vzorcem z jedné formy do druhé se nazývá „přepisování“ tohoto vzorce. Lze studovat abstraktní vlastnosti přepisování obecných vzorců studiem kolekce pravidel, pomocí kterých lze se vzorci platně manipulovat. Toto jsou „pravidla přepisování“ - nedílná součást normy abstraktní přepisovací systém. Častou otázkou je, zda je možné vnést nějaký obecný výraz do jediné společné formy, normální formy. Pokud různé sekvence přepisů stále vedou ke stejné formě, pak lze tuto formu nazvat normální formou, přičemž přepis se nazývá konfluentní. Normální formu není vždy možné získat.
Lambda kalkul
- Termín lambda je v normální forma beta pokud není možné beta snížení; lambda kalkul je zvláštní případ abstraktního přepisovacího systému. V netypovém lambda kalkulu, například výraz nemá normální formu. V zadaném lambda kalkulu lze každý dobře vytvořený výraz přepsat do normální formy.
Teorie grafů
v teorie grafů, obor matematiky, kanonizace grafů je problém najít kanonickou formu daného grafu G. Kanonická forma je a označený graf Kánon(G) to je izomorfní na G, takže každý graf, který je izomorfní G má stejnou kanonickou podobu jako G. Od řešení problému s kanonizací grafů by tedy bylo možné vyřešit také problém izomorfismus grafu: otestovat, zda dva grafy G a H jsou izomorfní, počítají jejich kanonické formy Canon (G) a Canon (H) a otestujte, zda jsou tyto dvě kanonické formy totožné.
Výpočetní
v výpočetní se běžně nazývá redukce dat na jakýkoli druh kanonické formy normalizace dat.
Například, normalizace databáze je proces organizace pole a tabulky a relační databáze minimalizovat nadbytek a závislost.[6]
V oblasti zabezpečení softwaru, běžný zranitelnost není zaškrtnuto škodlivé zadání (viz Vložení kódu ). Zmírnění tohoto problému je správné ověření vstupu. Před provedením ověření vstupu je vstup obvykle normalizován vyloučením kódování (např. Kódování HTML ) a snížení vstupních dat na jediný společný znaková sada.
Jiné formy dat, obvykle spojené s zpracování signálu (počítaje v to Zvuk a zobrazování ) nebo strojové učení, lze normalizovat za účelem poskytnutí omezeného rozsahu hodnot.
Viz také
Poznámky
- ^ „Definitivní glosář vyššího matematického žargonu - kanonický“. Matematický trezor. 2019-08-01. Citováno 2019-11-20.
- ^ V některých případech lze termín „kanonický“ a „normální“ použít také zaměnitelně, jako v Jordanské kanonické formě a Jordanské normální formě (viz Jordan normální forma na MathWorks ).
- ^ Pojem „svatořečení“ se k tomu někdy nesprávně používá.
- ^ „Velká čísla a vědecká notace“. Výuka kvantitativní gramotnosti. Citováno 2019-11-20.
- ^ Ziegler, Günter M. (1995), Přednášky na Polytopech, Postgraduální texty z matematiky, 152, Springer-Verlag, str. 117–118, ISBN 0-387-94365-X
- ^ "Popis základů normalizace databáze". support.microsoft.com. Citováno 2019-11-20.
Reference
- Shilov, Georgi E. (1977), Silverman, Richard A. (ed.), Lineární algebraDover, ISBN 0-486-63518-X.
- Hansen, Vagn Lundsgaard (2006), Funkční analýza: Vstup do Hilbertova prostoru, World Scientific Publishing, ISBN 981-256-563-9.