Инвариант (математика)

редактировать
A обои - инвариант при бесконечном количестве переводов, члены группы , из которых операция, обозначенная ∘ {\ displaystyle \ circ}\ circ , является композицией функций.

в математика, инвариант - это свойство математического объекта (или класса математических объектов), которое остается неизменным после операций или к объектам применяются преобразования определенного типа. Конкретный класс объектов и тип преобразований обычно указываются контекстом, в котором используется этот термин. Например, площадь треугольника является инвариантом относительно изометрий евклидовой плоскости. Используются оба выражения «инвариантный относительно» и «инвариантный» преобразованию. В более общем смысле, инвариант по отношению к отношению эквивалентности - это свойство, которое является постоянным для каждого класса эквивалентности.

Инварианты используются в различных областях математики, таких как геометрия, топология, алгебра и дискретная математика. Некоторые важные классы преобразований определяются инвариантом, который они не изменяют. Например, конформные карты определяются как преобразования плоскости, которые сохраняют углы. Обнаружение инвариантов - важный шаг в процессе классификации математических объектов.

Содержание
  • 1 Примеры
    • 1.1 Загадка MU
  • 2 Инвариантный набор
  • 3 Формальное утверждение
    • 3.1 Без изменений в группе действие
    • 3.2 Независимо от представления
    • 3.3 Не изменяется при возмущении
  • 4 Инварианты в информатике
    • 4.1 Автоматическое обнаружение инвариантов в императивных программах
  • 5 См. также
  • 6 Примечания
  • 7 Ссылки
  • 8 Внешние ссылки
Примеры

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

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

Расстояние между двумя точками на числовой строке не изменяется при добавлении одинаковой величины к обоим числам. С другой стороны, умножение не обладает этим же свойством, поскольку расстояние не инвариантно относительно умножения.

Углы и отношения расстояний неизменны при масштабах, вращениях, перемещениях и отражениях. Эти преобразования создают аналогичные формы, которые являются основой тригонометрии. Напротив, углы и соотношения не являются инвариантными при неравномерном масштабировании (например, при растяжении). Сумма внутренних углов треугольника (180 °) инвариантна при всех перечисленных выше операциях. В качестве другого примера, все окружности похожи: они могут быть преобразованы друг в друга, а отношение длины окружности к диаметру является неизменным (обозначается греческой буквой pi ).

Несколько более сложных примеров:

Загадка MU

Задача MU - хороший пример логическая проблема, когда определение инварианта используется для доказательства невозможности. Головоломка просит начать со слова MI и преобразовать его в слово MU, используя на каждом шаге одно из следующих правил преобразования:

  1. Если строка заканчивается на I, можно добавить U (xI → xIU)
  2. Строка после M может быть полностью дублирована (Mx → Mxx)
  3. Любые три последовательных I (III) могут быть заменены одним U (xIIIy → xUy)
  4. Любые два последовательных U могут быть удалены (xUUy → xy)

Пример вывода (с верхними индексами, указывающими применяемые правила):

MI → MII → MIIII → MUI → MUIUI → MUIUIU → MUIUIUUIUIU → MUIUIIUIU →...

В свете этого можно задаться вопросом, возможно ли преобразовать MI в MU, используя только эти четыре правила преобразования. На применение этих правил преобразования к строкам можно потратить много часов. Однако было бы быстрее найти свойство , которое инвариантно ко всем правилам (то есть не изменяется ни одним из них) и демонстрирует, что добраться до MU невозможно. Рассматривая головоломку с логической точки зрения, можно понять, что единственный способ избавиться от любых «я» - это иметь в строке три последовательных «я». Это делает интересным следующий инвариант:

Число I в строке не кратно 3.

Это инвариант проблемы, если для каждого из правил преобразования выполняется следующее: если инвариант сохранялся до применения правила, он будет сохраняться и после его применения. Глядя на чистый эффект применения правил к количеству I и U, можно увидеть, что это действительно так для всех правил:

Правило#I's# U'sВлияние на инвариант
1+0+1Число "I" не изменилось. Если инвариант соблюдается, он все равно остается.
2×2×2Если n не делится на 3, то 2 × n тоже не делится. Инвариант остается в силе.
3−3+1Если n не делится на 3, n − 3 тоже. Инвариант остается в силе.
4+0−2Количество "I" не изменилось. Если инвариант соблюдается, он все равно остается.

Приведенная выше таблица ясно показывает, что инвариант выполняется для каждого из возможных правил преобразования, что в основном означает, что какое бы правило ни было выбрано, в любом состоянии, если число I не было кратным трем до применения правила, то потом тоже не будет.

Учитывая, что в исходной строке MI есть один I, и тот, который не кратен трем, можно сделать вывод, что перейти от MI к MU невозможно (поскольку число I будет никогда не быть кратным трем).

Инвариантное множество

Подмножество S области U отображения T: U → U является инвариантным множеством относительно отображения, когда x ∈ S ⇒ T (x) ∈ S. {\ displaystyle x \ in S \ Rightarrow T (x) \ in S.}x \ in S \ Rightarrow T (x) \ in S. Обратите внимание, что элементы из S не фиксированы, даже если набор S фиксируется в наборе степеней U. (Некоторые авторы используют терминологию множественный инвариант и поточечный инвариант, чтобы различать эти случаи.) Например, круг - это инвариантное подмножество плоскости при вращении вокруг центра окружности. Кроме того, коническая поверхность инвариантна как множество относительно гомотетии пространства.

Инвариантный набор операции T также называется стабильным относительно T. Например, нормальные подгруппы, которые так важны в теории групп, - это те подгруппы, которые стабильны при внутренних автоморфизмах окружающего группа. В линейной алгебре , если линейное преобразование T имеет собственный вектор v, то прямая, проходящая через 0 и v является инвариантным множеством относительно T, и в этом случае собственные векторы охватывают инвариантное подпространство, которое устойчиво относительно T.

Когда T представляет собой смещение винта, ось винта является инвариантной линией, хотя, если шаг шаг не равен нулю, T не имеет фиксированных точек.

Формальное утверждение

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

Не изменяется при групповом действии

Во-первых, если у кого-то есть группа G, действующая на математический объект (или набор объектов) X, тогда можно спросить, какие точки x остаются неизменными, «инвариантными» под действием группы или под элементом g группы.

Часто у кого-то есть группа, действующая на множестве X, что оставляет возможность определять, какие объекты в ассоциированном множестве F (X) являются инвариантными. Например, вращение в плоскости вокруг точки оставляет точку, относительно которой он вращается, неизменной, в то время как перенос в плоскости не оставляет неизменными никакие точки, но оставляет все прямые, параллельные направлению перемещения, неизменными как линии. Формально, определим множество прямых на плоскости P как L (P); тогда жесткое движение плоскости превращает линии в линии - группа жестких движений действует на множество линий - и можно спросить, какие линии не изменяются действием.

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

двойственны понятию инвариантов коинварианты, также известные как орбиты, которые формализуют понятие конгруэнтности : объекты, которые могут быть приняты друг к другу группой действие. Например, для группы жестких движений плоскости периметр треугольника является инвариантом, а множество треугольников, конгруэнтных данному треугольнику, является коинвариантом.

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

Например, треугольники, у которых все три стороны равны, конгруэнтны при жестких движениях посредством SSS-конгруэнции, и, таким образом, длины всех трех сторон образуют полный набор инвариантов для треугольников. Три угловые меры треугольника также инвариантны относительно жестких движений, но не образуют полного набора, поскольку несовместимые треугольники могут иметь одинаковые угловые меры. Однако, если в дополнение к жестким движениям допускается масштабирование, то критерий сходства AAA показывает, что это полный набор инвариантов.

Независимо от представления

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

Наиболее распространенные примеры:

Не изменяются при возмущении

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

Инварианты в компьютерных науках

В компьютерных науках можно встретить инварианты, истинность которых может быть положена во время выполнения программы или во время некоторой части Это. Это логическое утверждение, которое всегда считается истинным на определенном этапе выполнения. Например, инвариант цикла - это условие, которое выполняется в начале и в конце каждого выполнения цикла.

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

Программисты часто используют утверждения в своем коде, чтобы сделать инварианты явными. Некоторые объектно-ориентированные языки программирования имеют специальный синтаксис для указания инвариантов классов.

Автоматическое обнаружение инвариантов в императивных программах

Абстрактная интерпретация инструменты могут вычислять простые инварианты данных императивных компьютерных программ. Тип свойств, которые можно найти, зависит от используемых абстрактных доменов. Типичными примерами свойств являются диапазоны одиночных целочисленных переменных, например 0<=x<1024, отношения между несколькими переменными, например 0 <=i-j<2*n-1, и информация о модуле, например y% 4 == 0. В прототипах академических исследований также учитываются простые свойства структур указателей.

Более сложные инварианты обычно необходимо вводить вручную. В частности, при проверке императивной программы с использованием исчисления Хоара инвариант цикла должен быть предоставлен вручную для каждого цикла в программе, что является одной из причин того, что этот подход в целом непрактичен для большинства программ.

В контексте приведенного выше примера MU puzzle в настоящее время не существует общего автоматизированного инструмента, который мог бы обнаружить, что переход от MI к MU невозможен, используя только правила 1–4. Однако после того, как абстракция от строки до числа ее «I» была сделана вручную, что привело, например, к следующей программе на C, инструмент абстрактной интерпретации сможет обнаружить, что ICount% 3не может быть 0, и, следовательно, цикл while никогда не завершится.

void MUPuzzle (void) {volatile int RandomRule; int ICount = 1, UCount = 0; while (ICount% 3! = 0) // переключение без завершения цикла (RandomRule) {case 1: UCount + = 1; перемена; случай 2: ICount * = 2; UCount * = 2; перемена; случай 3: ICount - = 3; UCount + = 1; перемена; случай 4: UCount - = 2; перемена; } // вычисляемый инвариант: ICount% 3 == 1 || ICount% 3 == 2}
См. Также
Примечания
Ссылки
Внешние ссылки
Последняя правка сделана 2021-05-24 05:35:42
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте