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

Эта статья требует дополнительных ссылок для проверки . Пожалуйста, помогите улучшить эту статью , добавив цитаты из надежных источников . Материал, не полученный от источника, может быть оспорен и удален Найти источники:  «Каноническая форма»  -  новости  · газеты  · книги  · ученый  · JSTOR ( декабрь 2007 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )

Алгоритмический тест анаграммы с использованием мультимножеств в качестве канонических форм: строки « мадам кюри » и « радий пришел » представлены в виде массивов C. Каждый преобразуется в каноническую форму путем сортировки. Поскольку обе отсортированные строки буквально совпадают, исходные строки были анаграммами друг друга.

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

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

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

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

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

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

Определение [ править ]

Принимая во внимание множества S объектов с отношением эквивалентности R на S , A канонической формы задается путем назначения некоторых объектов 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 ² , хотя эти две формы определяют один и тот же многочлен. Напротив, существование жордановой канонической формы для матрицы - глубокая теорема.

Примеры [ править ]

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

Обозначение большого числа [ править ]

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

Теория чисел [ править ]

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

Линейная алгебра [ править ]

Объекты	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	Нормальная форма Эрмита
Конечномерные векторные пространства над полем K	A и B изоморфны как векторные пространства	${\displaystyle K^{n}}$, n неотрицательное целое число

Алгебра [ править ]

Геометрия [ править ]

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

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

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

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

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

Интегрируемые системы [ править ]

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

Динамические системы [ править ]

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

Трехмерная геометрия [ править ]

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

Функциональный анализ [ править ]

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

Классическая логика [ править ]

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

Теория множеств [ править ]

• Кантор нормальная форма из порядкового номера

Теория игр [ править ]

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

Теория доказательств [ править ]

• Нормальная форма (естественная дедукция)

Системы перезаписи [ править ]

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

Лямбда-исчисление [ править ]

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

Теория графов [ править ]

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

Вычисления [ править ]

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

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

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

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

См. Также [ править ]

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

Примечания [ править ]

Ссылки [ править ]

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