Forma kanoniczna - Canonical form

Algorytmiczny test anagramów przy użyciu wielu zbiorów jako form kanonicznych: ciągi znaków " pani curie " i " radium przyszedł " są podane jako tablice C . Każda z nich jest przekształcana w formę kanoniczną przez sortowanie. Ponieważ oba posortowane ciągi dosłownie się zgadzają, oryginalne ciągi były anagramami siebie nawzajem.

W matematyce i informatyce , wykorzystując kanoniczne , normalny lub standardowy formularz z matematycznego obiektu jest standardowym sposobem prezentacji tego obiektu jako wyrażenie matematyczne . Często jest to taki, który zapewnia najprostszą reprezentację obiektu i pozwala na jego identyfikację w unikalny sposób. Rozróżnienie między formami „kanonicznymi” i „normalnymi” różni się w zależności od podpola. W większości dziedzin forma kanoniczna określa unikalną reprezentację dla każdego obiektu, podczas gdy forma normalna po prostu określa jego formę, bez wymogu unikalności.

Kanoniczna postać dodatniej liczby całkowitej w reprezentacji dziesiętnej jest skończoną sekwencją cyfr, która nie zaczyna się od zera. Bardziej ogólnie, dla klasy przedmiotów, na których zdefiniowana jest relacja równoważności , forma kanoniczna polega na wyborze określonego przedmiotu w każdej klasie. Na przykład:

• Postać normalna Jordana jest postacią kanoniczną dla podobieństwa macierzowego .
• Tworzą szereg rzut ma postać kanoniczną, gdy weźmie się pod uwagę jako równoważna matrycy a jej lewy produktu przez odwracania sygnału matrycy .

W informatyce, a dokładniej w algebrze komputerowej , podczas reprezentowania obiektów matematycznych w komputerze, istnieje zwykle wiele różnych sposobów reprezentowania tego samego obiektu. W tym kontekście forma kanoniczna jest reprezentacją taką, że każdy obiekt ma unikalną reprezentację (przy czym kanonizacja jest procesem, w którym reprezentacja jest wprowadzana do formy kanonicznej). W ten sposób równość dwóch obiektów można łatwo przetestować, testując równość ich form kanonicznych.

Pomimo tej przewagi formy kanoniczne często zależą od arbitralnych wyborów (np. uporządkowanie zmiennych), co utrudnia testowanie równości dwóch obiektów w wyniku niezależnych obliczeń. Dlatego w algebrze komputerowej forma normalna jest słabszym pojęciem: forma normalna jest reprezentacją taką, że zero jest reprezentowane jednoznacznie. Umożliwia to testowanie równości poprzez umieszczenie różnicy dwóch obiektów w postaci normalnej.

Forma kanoniczna może również oznaczać formę różniczkową, która jest zdefiniowana w sposób naturalny (kanoniczny).

Definicja

Dany zbiór S obiektów o relacji równoważności R do S , forma kanoniczna jest dana przez oznaczenie niektórych obiektów S jako „w formie kanonicznej”, tak że każdy rozważany obiekt jest równoważny dokładnie jednemu obiektowi w formie kanonicznej. Innymi słowy, formy kanoniczne w S reprezentują klasy równoważności, raz i tylko raz. Aby sprawdzić, czy dwa obiekty są równoważne, wystarczy przetestować równość w ich formach kanonicznych. Forma kanoniczna dostarcza zatem twierdzenia klasyfikacyjnego i nie tylko, ponieważ nie tylko klasyfikuje każdą klasę, ale także daje wyróżniającego (kanonicznego) przedstawiciela dla każdego przedmiotu w klasie.

Formalnie kanonizacja ze względu na relację równoważności R na zbiorze S jest odwzorowaniem c : S → S takim, że dla wszystkich s , s ₁ , s ₂ ∈ S :

1. c ( s ) = c ( c ( s )) ( idempotencja ),
2. s ₁ R s ₂ wtedy i tylko wtedy, gdy c ( s ₁ ) = c ( s ₂ ) (decydowanie) oraz
3. s R c ( s ) (reprezentatywność).

Właściwość 3 jest zbędna; wynika z zastosowania 2 do 1.

Z praktycznego punktu widzenia często korzystne jest rozpoznanie form kanonicznych. Należy również rozważyć praktyczne, algorytmiczne pytanie: jak przejść z danego obiektu s w S do jego postaci kanonicznej s *? Formy kanoniczne są zwykle używane w celu zwiększenia efektywności operowania klasami równoważności. Na przykład w arytmetyce modularnej forma kanoniczna klasy reszt jest zwykle przyjmowana jako najmniejsza nieujemna liczba całkowita. Operacje na klasach przeprowadza się łącząc tych przedstawicieli, a następnie sprowadzając wynik do najmniejszej nieujemnej reszty. Wymóg jednoznaczności jest czasami złagodzony, pozwalając formom na unikalność aż do jakiejś subtelniejszej relacji równoważności, takiej jak umożliwienie zmiany kolejności terminów (jeśli nie ma naturalnego uporządkowania terminów).

Forma kanoniczna może być po prostu konwencją lub głębokim twierdzeniem. Na przykład wielomiany są konwencjonalnie zapisywane z terminami w potęgach malejących: częściej zapisuje się x ² + x + 30 niż x + 30 + x ² , chociaż te dwie formy definiują ten sam wielomian. Natomiast istnienie formy kanonicznej Jordana dla macierzy jest głębokim twierdzeniem.

Przykłady

Uwaga: w tej sekcji „ do ” pewna relacja równoważności E oznacza, że ​​forma kanoniczna nie jest ogólnie unikalna, ale jeśli jeden obiekt ma dwie różne formy kanoniczne, są one E-równoważne.

Notacja z dużą liczbą

Standardowa forma jest używana przez wielu matematyków i naukowców do zapisywania bardzo dużych liczb w bardziej zwięzły i zrozumiały sposób, z których najbardziej widocznym jest notacja naukowa .

Teoria liczb

• Kanoniczna reprezentacja dodatniej liczby całkowitej
• Kanoniczna forma ułamka łańcuchowego

Algebra liniowa

Obiekty	A jest równoważne B, jeżeli:	Forma normalna	Uwagi
Macierze normalne nad liczbami zespolonymi	${\ Displaystyle A = U ^ {*} BU}$dla pewnej macierzy unitarnej U	Macierze diagonalne (do zmiany kolejności)	To jest twierdzenie o widmie
Macierze nad liczbami zespolonymi	${\ Displaystyle A = UBV ^ {*}}$dla niektórych macierzy unitarnych U i V	Macierze przekątne z rzeczywistymi wpisami dodatnimi (w porządku malejącym)	Rozkład według wartości osobliwych
Macierze nad ciałem algebraicznie domkniętym	${\ Displaystyle A = P ^ {-1} BP}$dla jakiejś odwracalnej macierzy P	Postać normalna Jordana (do zmiany kolejności bloków)
Macierze nad ciałem algebraicznie domkniętym	${\ Displaystyle A = P ^ {-1} BP}$dla jakiejś odwracalnej macierzy P	Forma kanoniczna Weyru (do zmiany kolejności bloków)
Macierze nad polem	${\ Displaystyle A = P ^ {-1} BP}$dla jakiejś odwracalnej macierzy P	Postać normalna Frobeniusa
Macierze nad główną idealną domeną	${\ Displaystyle A = P ^ {-1} BQ}$dla niektórych macierzy odwracalnych P i Q	Smith postać normalna	Równoważność jest taka sama, jak przy dopuszczaniu odwracalnych elementarnych przekształceń wierszy i kolumn
Macierze nad liczbami całkowitymi	${\ Displaystyle A = UB}$dla jakiejś unimodularnej macierzy U	Pustelnik normalna forma
Skończenie wymiarowe przestrzenie wektorowe nad ciałem K	A i B są izomorficzne jako przestrzenie wektorowe	${\ Displaystyle K ^ {n}}$, n nieujemna liczba całkowita

Algebra

Geometria

W geometrii analitycznej :

• Równanie prostej: Ax  +  By  =  C , gdzie A ²  +  B ²  = 1 i C  ≥ 0
• Równanie koła: ${\ Displaystyle (xh) ^ {2} + (yk) ^ {2} = r ^ {2}}$

Dla kontrastu istnieją alternatywne formy pisania równań. Na przykład, równanie linii może być zapisane jako równanie liniowe w postaci punkt-slope i slope-intercept .

Wielościany wypukłe można nadać postaci kanonicznej w taki sposób, że:

• Wszystkie twarze są płaskie,
• Wszystkie krawędzie są styczne do sfery jednostkowej i
• Początkiem jest środek ciężkości wielościanu.

Systemy integrowalne

Każdy rozmaitość różniczkowa ma wiązkę kostyczną . Wiązce tej można zawsze nadać pewną formę różniczkową , zwaną jednopostacią kanoniczną . Forma ta nadaje wiązce kostycznej strukturę rozmaitości symplektycznej i umożliwia całkowanie pól wektorowych na rozmaitości za pomocą równań Eulera-Lagrange'a lub za pomocą mechaniki hamiltonowskiej . Takie układy równań różniczkowych całkowalnych nazywamy układami całkowalnymi .

Układy dynamiczne

Badanie układów dynamicznych pokrywa się z badaniem układów całkowalnych ; tam pojawia się idea formy normalnej (układy dynamiczne) .

Geometria trójwymiarowa

W badaniu rozmaitości w trzech wymiarach mamy pierwszą formę podstawową , drugą formę podstawową i trzecią formę podstawową .

Analiza funkcjonalna

Obiekty	A jest równoważne B, jeżeli:	Forma normalna
Przestrzenie Hilberta	Jeśli A i B są obie przestrzeniami Hilberta o nieskończonym wymiarze, to A i B są izometrycznie izomorficzne.	${\displaystyle \ell ^{2}(I)}$ przestrzenie sekwencyjne (aż do zamiany zbioru indeksów I na inny zbiór indeksów o tej samej liczności )
Przemienne -algebry z jednostką ${\ Displaystyle C ^ {*}}$	A i B są izomorficzne jako -algebry ${\ Displaystyle C ^ {*}}$	Algebra funkcji ciągłych na zwartej przestrzeni Hausdorffa aż do homeomorfizmu przestrzeni bazowej. ${\ Displaystyle C (X)}$

Logika klasyczna

• Forma normalna negacji
• Spójna forma normalna
• Rozdzielna forma normalna
• Algebraiczna postać normalna
• Postać normalna Prenex
• Skolem postać normalna
• Forma kanoniczna Blake'a , znana również jako pełna suma implikantów pierwszych, pełna suma lub rozłączna forma pierwsza

Teoria mnogości

• Kantor w postaci normalnej liczby porządkowej

Teoria gry

• Gra w formie normalnej

Teoria dowodu

• Forma normalna (odliczenie naturalne)

Systemy przepisywania

Symboliczne manipulowanie formułą z jednej formy w drugą nazywa się „przepisywaniem” tej formuły. Abstrakcyjne właściwości przepisywania formuł ogólnych można badać, badając zbiór reguł, za pomocą których można prawidłowo manipulować formułami. Są to „zasady przepisywania” — integralna część abstrakcyjnego systemu przepisywania . Częstym pytaniem jest, czy możliwe jest sprowadzenie jakiegoś ogólnego wyrażenia do jednej, wspólnej formy, formy normalnej. Jeśli różne sekwencje przepisywania nadal dają tę samą formę, wówczas formę tę można nazwać formą normalną, przy czym przepisanie nazywa się konfluentną. Nie zawsze jest możliwe uzyskanie normalnego formularza.

Rachunek lambda

• Termin lambda jest w postaci normalnej beta, jeśli nie jest możliwa redukcja beta; rachunek lambda jest szczególnym przypadkiem abstrakcyjnego systemu przepisywania. Na przykład w nieopisanym rachunku lambda termin nie ma postaci normalnej. W typowanym rachunku lambda każdy prawidłowo sformułowany termin może zostać przepisany do jego normalnej postaci.${\ Displaystyle (\ lambda x. (xx) \; \ lambda x. (xx))}$

Teoria grafów

W teorii grafów , gałęzi matematyki, kanonizacja grafów polega na znalezieniu postaci kanonicznej danego grafu G . Postać kanoniczna to graf oznaczony jako Canon( G ), który jest izomorficzny z G , tak że każdy graf, który jest izomorficzny z G ma taką samą formę kanoniczną jak G . Zatem od rozwiązania problemu kanonizacji grafów można również rozwiązać problem izomorfizmu grafów : aby sprawdzić, czy dwa grafy G i H są izomorficzne, obliczyć ich formy kanoniczne Canon( G ) i Canon( H ) i sprawdzić, czy są to dwie formy kanoniczne są identyczne.

Przetwarzanie danych

W informatyce redukcja danych do jakiejkolwiek postaci kanonicznej jest powszechnie nazywana normalizacją danych .

Na przykład, normalizacja bazy danych jest procesem organizowania pola i tabele o relacyjną bazę danych , aby zminimalizować redundancję i zależność.

W dziedzinie bezpieczeństwa oprogramowania , powszechną luką w zabezpieczeniach są niesprawdzone złośliwe dane wejściowe (patrz Wstrzykiwanie kodu ). Rozwiązaniem tego problemu jest właściwa walidacja danych wejściowych . Przed wykonaniem walidacji danych wejściowych dane wejściowe są zwykle normalizowane przez wyeliminowanie kodowania (np. kodowanie HTML ) i zredukowanie danych wejściowych do jednego wspólnego zestawu znaków .

Inne formy danych, zwykle związane z przetwarzaniem sygnału (w tym audio i obrazowanie ) lub uczeniem maszynowym , można znormalizować w celu zapewnienia ograniczonego zakresu wartości.

Zobacz też

• Kanonizacja
• Podstawa kanoniczna
• Klasa kanoniczna
• Normalizacja (ujednoznacznienie)
• Normalizacja

Uwagi

Bibliografia

• Shilov, Georgi E. (1977), Silverman, Richard A. (red.), Algebra Liniowa , Dover, ISBN 0-486-63518-X.
• Hansen, Vagn Lundsgaard (2006), Analiza funkcjonalna: Wejście w przestrzeń Hilberta , World Scientific Publishing, ISBN 981-256-563-9.