Каноническая форма

This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Canonical form" – news · newspapers · books · scholar · JSTOR (December 2007) (Learn how and when to remove this message)

В математике и информатике каноническая , нормальная или стандартная форма математического объекта — это стандартный способ представления этого объекта в виде математического выражения . Часто это тот, который обеспечивает простейшее представление объекта и позволяет идентифицировать его уникальным образом. Различие между «канонической» и «нормальной» формами варьируется от подполя к подполю. В большинстве областей каноническая форма определяет уникальное представление для каждого объекта, тогда как нормальная форма просто определяет его форму без требования уникальности. ^[1]

Каноническая форма положительного целого числа в десятичном представлении — это конечная последовательность цифр, которая не начинается с нуля. В более общем смысле, для класса объектов, на котором определено отношение эквивалентности , каноническая форма состоит в выборе конкретного объекта в каждом классе. Например:

• Нормальная форма Жордана является канонической формой для подобия матриц .
• Ступенчатая форма строк является канонической формой, если рассматривать как эквивалентные матрицу и ее левое произведение на обратимую матрицу .

В информатике, а точнее в компьютерной алгебре , при представлении математических объектов в компьютере обычно существует много разных способов представления одного и того же объекта. В этом контексте каноническая форма — это представление, при котором каждый объект имеет уникальное представление (при этом канонизация — это процесс, посредством которого представление приводится к своей канонической форме). ^[2] Таким образом, равенство двух объектов можно легко проверить, проверив равенство их канонических форм.

Несмотря на это преимущество, канонические формы часто зависят от произвольного выбора (например, упорядочивания переменных), что создает трудности для проверки равенства двух объектов, полученных в результате независимых вычислений. Поэтому в компьютерной алгебре нормальная форма является более слабым понятием: нормальная форма — это представление, в котором ноль представлен уникально. Это позволяет проверять равенство, помещая разницу двух объектов в нормальную форму.

Каноническая форма может также означать дифференциальную форму , которая определяется естественным (каноническим) образом.

Если задано множество объектов S с отношением эквивалентности R на S , каноническая форма задается путем обозначения некоторых объектов S как находящихся «в канонической форме», так что каждый рассматриваемый объект эквивалентен ровно одному объекту в канонической форме. Другими словами, канонические формы в S представляют классы эквивалентности, один и только один раз. Чтобы проверить, эквивалентны ли два объекта, достаточно проверить равенство их канонических форм. Таким образом, каноническая форма обеспечивает теорему классификации и даже больше, поскольку она не только классифицирует каждый класс, но и дает выдающегося (канонического) представителя для каждого объекта в классе.

Формально канонизация относительно отношения эквивалентности R на множестве S — это отображение c : S → S такое, что для всех s , s ₁ , s ₂ ∈ S :

1. c ( s ) = c ( c ( s )) ( идемпотентность ),
2. s ₁ R s ₂ тогда и только тогда, когда c ( s ₁ ) = c ( s ₂ ) (решительность), и
3. s R c ( s ) (репрезентативность).

Свойство 3 избыточно; оно следует из применения 2 к 1.

С практической точки зрения часто бывает полезно уметь распознавать канонические формы. Также есть практический алгоритмический вопрос для рассмотрения: как перейти от заданного объекта s в S к его канонической форме s *? Канонические формы обычно используются для повышения эффективности работы с классами эквивалентности. Например, в модульной арифметике каноническая форма для класса остатков обычно берется как наименьшее неотрицательное целое число в нем. Операции над классами выполняются путем объединения этих представителей и последующего сведения результата к его наименьшему неотрицательному остатку. Требование уникальности иногда ослабляется, позволяя формам быть уникальными вплоть до некоторого более тонкого отношения эквивалентности, например, допуская переупорядочивание членов (если нет естественного упорядочения членов).

Каноническая форма может быть просто соглашением или глубокой теоремой. Например, многочлены традиционно записываются с членами в убывающих степенях: более привычно писать x ² + x + 30, чем x + 30 + x ² , хотя эти две формы определяют один и тот же многочлен. Напротив, существование канонической формы Жордана для матрицы является глубокой теоремой.

Согласно OED и LSJ , термин канонический происходит от древнегреческого слова kanonikós ( κανονικός , «регулярный, согласно правилу») от kanṓn ( κᾰνών , «стержень, правило»). Значение нормы, стандарта или архетипа использовалось во многих дисциплинах. Математическое использование засвидетельствовано в письме Логана 1738 года . ^[3] Немецкий термин kanonische Form засвидетельствован в статье Эйзенштейна 1846 года , ^[4] позже в том же году Ришело использует термин Normalform в своей статье, ^[5] а в 1851 году Сильвестр пишет: ^[6]

«Теперь я перехожу к [...] способу сведения алгебраических функций к их простейшим и наиболее симметричным, или, как мой замечательный друг М. Эрмит удачно предлагает их назвать, к их каноническим формам ».

В тот же период использование засвидетельствовано Гессе («Нормальная форма»), ^[7] Эрмитом («каноническая форма»), ^[8] Борхардтом («форма каноническая»), ^[9] и Кэли («каноническая форма»). ^[10]

В 1865 году «Словарь по науке, литературе и искусству» определил каноническую форму следующим образом:

«В математике обозначает форму, обычно самую простую или симметричную, к которой, без потери общности, могут быть сведены все функции одного и того же класса».

Примечание: в этом разделе « до » некоторого отношения эквивалентности E означает, что каноническая форма в общем случае не является единственной, но если один объект имеет две различные канонические формы, то они являются E-эквивалентными.

Стандартная форма используется многими математиками и учеными для записи чрезвычайно больших чисел более кратким и понятным способом, наиболее известным из которых является научная запись . ^[11]

• Каноническое представление положительного целого числа
• Канонической формой цепной дроби для представления числа является простая цепная дробь

Объекты	A эквивалентно B, если:	Нормальная форма	Примечания
Нормальные матрицы над комплексными числами	${\displaystyle A=U^{*}BU}$для некоторой унитарной матрицы U	Диагональные матрицы (с точностью до переупорядочения)	Это спектральная теорема.
Матрицы над комплексными числами	${\displaystyle A=UBV^{*}}$для некоторых унитарных матриц U и V	Диагональные матрицы с действительными положительными элементами (в порядке убывания)	Разложение по сингулярным значениям
Матрицы над алгебраически замкнутым полем	${\displaystyle A=P^{-1}BP}$для некоторой обратимой матрицы P	Нормальная форма Жордана (с точностью до переупорядочивания блоков)
Матрицы над алгебраически замкнутым полем	${\displaystyle A=P^{-1}BP}$для некоторой обратимой матрицы P	Каноническая форма Вейра (до перестановки блоков)
Матрицы над полем	${\displaystyle A=P^{-1}BP}$для некоторой обратимой матрицы P	Нормальная форма Фробениуса
Матрицы над областью главных идеалов	${\displaystyle A=P^{-1}BQ}$для некоторых обратимых матриц P и Q	Нормальная форма Смита	Эквивалентность такая же, как и при разрешении обратимых элементарных преобразований строк и столбцов.
Матрицы над целыми числами	${\displaystyle A=UB}$для некоторой унимодулярной матрицы U	Нормальная форма Эрмита
Матрицы над целыми числами по модулю n		Нормальная форма Хауэлла
Конечномерные векторные пространства над полем K	A и B изоморфны как векторные пространства	${\displaystyle K^{n}}$, n — неотрицательное целое число

В аналитической геометрии :

• Уравнение прямой: Ax  +  By  =  C , где A ²  +  B ²  = 1 и C  ≥ 0
• Уравнение окружности:${\displaystyle (x-h)^{2}+(y-k)^{2}=r^{2}}$

Напротив, существуют альтернативные формы записи уравнений. Например, уравнение линии может быть записано как линейное уравнение в форме точка-наклон и наклон-пересечение .

Выпуклые многогранники можно привести к каноническому виду таким образом:

• Все лица плоские,
• Все ребра касаются единичной сферы, и
• Центроид многогранника находится в начале координат. ^[12]

Каждое дифференцируемое многообразие имеет кокасательное расслоение . Это расслоение всегда можно наделить некоторой дифференциальной формой , называемой канонической одноформой . Эта форма придает кокасательному расслоению структуру симплектического многообразия и позволяет интегрировать векторные поля на многообразии с помощью уравнений Эйлера-Лагранжа или с помощью гамильтоновой механики . Такие системы интегрируемых дифференциальных уравнений называются интегрируемыми системами .

Изучение динамических систем пересекается с изучением интегрируемых систем ; здесь имеется идея нормальной формы (динамических систем) .

При изучении многообразий в трех измерениях имеются первая фундаментальная форма , вторая фундаментальная форма и третья фундаментальная форма .

Объекты	A эквивалентно B, если:	Нормальная форма
Гильбертовы пространства	Если A и B являются гильбертовыми пространствами бесконечной размерности, то A и B изометрически изоморфны.	${\displaystyle \ell ^{2}(I)}$ пространства последовательностей (вплоть до замены набора индексов I на другой набор индексов той же мощности )
Коммутативные C*-алгебры с единицей	A и B изоморфны как C*-алгебры	Алгебра непрерывных функций на компактном хаусдорфовом пространстве с точностью до гомеоморфизма базового пространства.${\displaystyle C(X)}$

• Нормальная форма отрицания
• Конъюнктивная нормальная форма
• Дизъюнктивная нормальная форма
• Алгебраическая нормальная форма
• Нормальная предварительная форма
• Сколемская нормальная форма
• Каноническая форма Блейка , также известная как полная сумма простых импликант, полная сумма или дизъюнктивная простая форма

• Нормальная форма Кантора порядкового числа

• Игра в нормальной форме

• Нормальная форма (естественный вывод)

Символическое преобразование формулы из одной формы в другую называется «переписыванием» этой формулы. Можно изучать абстрактные свойства переписывания общих формул, изучая набор правил, по которым формулы могут быть допустимо обработаны. Это «правила переписывания» — неотъемлемая часть абстрактной системы переписывания . Распространенный вопрос заключается в том, можно ли привести некоторое общее выражение к единой, общей форме, нормальной форме. Если различные последовательности переписываний по-прежнему приводят к одной и той же форме, то эту форму можно назвать нормальной формой, а переписывание — конфлюэнтным. Не всегда возможно получить нормальную форму.

• Лямбда-терм находится в бета-нормальной форме , если бета-редукция невозможна; лямбда-исчисление является частным случаем абстрактной системы переписывания. В нетипизированном лямбда-исчислении, например, терм не имеет нормальной формы. В типизированном лямбда-исчислении каждый правильно сформированный терм может быть переписан в его нормальную форму.${\displaystyle (\lambda x.(xx)\;\lambda x.(xx))}$

В теории графов , разделе математики, канонизация графов — это проблема нахождения канонической формы заданного графа G. Каноническая форма — это помеченный граф Canon( G ), который изоморфен G , такой, что каждый граф, изоморфный G , имеет ту же каноническую форму, что и G . Таким образом, из решения проблемы канонизации графов можно также решить проблему изоморфизма графов : чтобы проверить, являются ли два графа G и H изоморфными, вычислить их канонические формы Canon( G ) и Canon( H ), и проверить, идентичны ли эти две канонические формы.

В вычислительной технике приведение данных к какой-либо канонической форме обычно называется нормализацией данных .

Например, нормализация базы данных — это процесс организации полей и таблиц реляционной базы данных для минимизации избыточности и зависимости. ^[13]

В области безопасности программного обеспечения распространенной уязвимостью является непроверенный вредоносный ввод (см. Внедрение кода ). Смягчением этой проблемы является правильная проверка ввода . Перед выполнением проверки ввода ввод обычно нормализуется путем устранения кодировки (например, кодировки HTML ) и сведения входных данных к одному общему набору символов .

Другие формы данных, обычно связанные с обработкой сигналов (включая аудио и изображения ) или машинным обучением , могут быть нормализованы для предоставления ограниченного диапазона значений.

В управлении контентом применима концепция единого источника истины (SSOT), как и в нормализации баз данных в целом и в разработке программного обеспечения . Компетентные системы управления контентом предоставляют логические способы ее получения, такие как трансклюзия .

• Канонизация
• Каноническая основа
• Канонический класс
• Нормализация (разрешение неоднозначности)
• Стандартизация

• Шилов, Георгий Э. (1977), Сильверман, Ричард А. (ред.), Линейная алгебра , Довер, ISBN 0-486-63518-X.
• Хансен, Вагн Лундсгаард (2006), Функциональный анализ: вход в гильбертово пространство , World Scientific Publishing, ISBN 981-256-563-9.