Jump to content

Идемпотентность

(Перенаправлено с оператора «Идемпотент» )
Кнопки включения / выключения поезда панели управления знаками назначения . Нажатие кнопки «Вкл» (зеленой) является идемпотентной операцией, поскольку она имеет одинаковый эффект независимо от того, выполняется ли она один или несколько раз. Аналогично, нажатие кнопки Off является идемпотентным.

Идемпотентность ( Великобритания : / ˌ ɪ d ɛ m ˈ p t ən s / , [1] США : / ˈ d ə m -/ ) [2] — это свойство определенных операций в математике и информатике , благодаря которому их можно применять многократно, не изменяя результат за пределами первоначального применения. Понятие идемпотентности возникает в ряде мест в абстрактной алгебре (в частности, в теории проекторов и операторов замыкания ) и функциональном программировании (в котором оно связано со свойством ссылочной прозрачности ).

Этот термин был введен американским математиком Бенджамином Пирсом в 1870 году. [3] [4] в контексте элементов алгебр, которые остаются инвариантными при возведении в положительную целочисленную степень и буквально означает «(качество обладания) той же силой» от idem + potence (та же + мощность).

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

Элемент из набора оснащен бинарным оператором называется идемпотентным относительно если [5] [6]

.

Бинарная операция называется идемпотентным, если [7] [8]

для всех .

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

  • В моноиде натуральных чисел с умножением , только и являются идемпотентными. Действительно, и .
  • В моноиде натуральных чисел со сложением , только является идемпотентным. Действительно, 0 + 0 = 0 .
  • В магме , элемент идентификации или поглощающий элемент , если он существует, идемпотентен. Действительно, и .
  • В группе , идентификационный элемент единственный идемпотентный элемент. Действительно, если является элементом такой, что , затем и наконец умножив слева на элемент обратный .
  • В моноидах и из силового набора из набора с установленным объединением и установить пересечение соответственно, и являются идемпотентными. Действительно, для всех , и для всех .
  • В моноидах и с булевой области логической дизъюнкцией и логическое соединение соответственно, и являются идемпотентными. Действительно, для всех , и для всех .
  • В домене GCD (например, в ), операции НОД и НОК идемпотентны.
  • В булевом кольце умножение идемпотентно.
  • В тропическом полукольце сложение идемпотентно.
  • В кольце квадратичных матриц определитель равен идемпотентной матрицы 0 или 1. Если определитель равен 1, матрица обязательно является единичной матрицей . [ нужна ссылка ]

Идемпотентные функции [ править ]

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

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

— общее количество возможных идемпотентных функций на множестве. Целочисленная последовательность количества идемпотентных функций, заданная приведенной выше суммой для n = 0, 1, 2, 3, 4, 5, 6, 7, 8, ... начинается с 1, 1, 3, 10, 41. , 196, 1057, 6322, 41393, ... (последовательность A000248 в OEIS ).

Ни свойство быть идемпотентным, ни свойство не быть не сохраняется при композиции функций. [10] В качестве примера для первого, мод 3 и оба идемпотентны, но нет, [11] хотя бывает. [12] В качестве примера последнего можно привести функцию отрицания в булевой области не идемпотентен, но является. Аналогично, унарное отрицание действительных чисел не идемпотентно, но является. В обоих случаях композиция представляет собой просто тождественную функцию , которая является идемпотентной.

Значение информатики [ править ]

В информатике термин идемпотентность может иметь разное значение в зависимости от контекста, в котором он применяется:

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

информатики Примеры

Функция поиска имени и адреса клиента в базе данных обычно является идемпотентной, поскольку это не приводит к изменению базы данных. Аналогично, запрос на изменение адреса клиента на XYZ обычно является идемпотентным, поскольку окончательный адрес будет одинаковым независимо от того, сколько раз будет отправлен запрос. Однако запрос клиента на размещение заказа обычно не является идемпотентным, поскольку несколько запросов приводят к размещению нескольких заказов. Запрос на отмену определенного заказа является идемпотентным, поскольку независимо от того, сколько запросов было сделано, заказ остается отмененным.

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

int x = 3;
void inspect() { printf("%d\n", x); }
void change() { x = 5; }
void sequence() { inspect(); change(); inspect(); }

int main() {
  sequence();  // prints "3\n5\n"
  sequence();  // prints "5\n5\n"
  return 0;
}

В протоколе передачи гипертекста (HTTP) идемпотентность и безопасность являются основными атрибутами, разделяющими методы HTTP . Из основных методов HTTP GET, PUT и DELETE должны быть реализованы идемпотентным образом в соответствии со стандартом, но POST не обязательно. [13] GET извлекает состояние ресурса; PUT обновляет состояние ресурса; и DELETE удаляет ресурс. Как и в примере выше, чтение данных обычно не имеет побочных эффектов, поэтому оно идемпотентно (фактически нуллипотентно ). Обновление и удаление данных данных обычно идемпотентны, если запрос однозначно идентифицирует ресурс и только этот ресурс снова в будущем. PUT и DELETE с уникальными идентификаторами сводятся к простому случаю присвоения переменной значения или нулевого значения соответственно и являются идемпотентными по той же причине; конечный результат всегда тот же, что и результат первоначального выполнения, даже если ответ отличается. [14]

Нарушение требования уникальной идентификации при хранении или удалении обычно приводит к нарушению идемпотентности. Например, сохранение или удаление заданного набора контента без указания уникального идентификатора: POST-запросы, которым не обязательно быть идемпотентными, часто не содержат уникальных идентификаторов, поэтому создание идентификатора делегируется принимающей системе, которая затем создает соответствующую новую запись. Аналогично, запросы PUT и DELETE с неопределенными критериями могут привести к разным результатам в зависимости от состояния системы — например, к запросу на удаление самой последней записи. В каждом случае последующие выполнения будут дополнительно изменять состояние системы, поэтому они не являются идемпотентными.

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

В архитектуре загрузки-сохранения инструкции, которые могут вызвать ошибку страницы, являются идемпотентными. Таким образом, если происходит ошибка страницы, операционная система может загрузить страницу с диска, а затем просто повторно выполнить ошибочную инструкцию. В процессоре, где такие инструкции не идемпотентны, обработка ошибок страниц гораздо сложнее. [15] [16]

Ожидается , что при переформатировании вывода симпатичная печать будет идемпотентной. Другими словами, если результат уже «красивый», симпатичному принтеру делать нечего. [ нужна ссылка ]

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

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

Прикладные примеры [ править ]

Типичная кнопка пешеходного перехода является примером идемпотентной системы.

Прикладные примеры, с которыми многие люди могут столкнуться в повседневной жизни, включают кнопки вызова лифта и кнопки пешеходного перехода . [17] Первоначальное нажатие кнопки переводит систему в состояние запроса до тех пор, пока запрос не будет удовлетворен. Последующие активации кнопки между первоначальной активацией и удовлетворением запроса не имеют никакого эффекта, если только система не предназначена для корректировки времени удовлетворения запроса в зависимости от количества активаций.

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

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

  1. ^ «идемпотентность» . Оксфордский словарь английского языка (3-е изд.). Издательство Оксфордского университета. 2010.
  2. ^ «идемпотент» . Мерриам-Вебстер . Архивировано из оригинала 19 октября 2016 г.
  3. ^ Оригинал рукописи лекции 1870 года перед Национальной академией наук (Вашингтон, округ Колумбия, США): Пирс, Бенджамин (1870) «Линейная ассоциативная алгебра». Со страниц 16–17: «Когда выражение, возведенное в квадрат или любую более высокую степень исчезает, его можно назвать нильпотентным , но при возведении в квадрат или более высокую степень он дает себя в результате, его можно назвать идемпотентным ;
    Определяющим уравнением нильпотентных и идемпотентных выражений являются соответственно A н = 0 и А н = А; но относительно идемпотентных выражений всегда будет предполагаться, что они имеют вид A н = A, если не указано иное».
  4. ^ Полчино и Сегал 2002 , с. 127 .
  5. ^ Валенца, Роберт (2012). Линейная алгебра: введение в абстрактную математику . Берлин: Springer Science & Business Media. п. 22. ISBN  9781461209010 . Элемент s магмы такой, что ss = s, называется идемпотентным .
  6. ^ Донедду, Альфред (1976). Полиномы и линейная алгебра (на французском языке). Париж: Вюиберт. п. 180. Пусть М магма, отмеченная мультипликативно. Мы называем из M каждый элемент a идемпотентом M такой, что a 2 = а .
  7. ^ Джордж Гретцер (2003). Общая теория решеток . Базель: Биркхойзер. Здесь: Раздел 1.2, п.5.
  8. ^ Гаррет Биркгоф (1967). Теория решетки . Публикации коллоквиума. Том. 25. Провиденс: Ам. Математика. Соц. . Здесь: Раздел I.5, стр.8.
  9. ^ Это уравнение между функциями. Две функции равны, если их области определения и диапазоны совпадают, а их выходные значения совпадают во всей области определения.
  10. ^ Если и коммутировать под композицией (т.е. если ) тогда идемпотентность обоих и подразумевает, что , с , используя ассоциативность композиции.
  11. ^ например , но
  12. ^ также показано, что коммутация и не является необходимым условием сохранения идемпотентности
  13. ^ IETF, Протокол передачи гипертекста (HTTP/1.1): семантика и контент, заархивированные 8 июня 2014 г. на Wayback Machine . См. также Протокол передачи гипертекста .
  14. ^ «Идемпотентные методы» . Протокол передачи гипертекста (HTTP/1.1): семантика и содержание . сек. 4.2.2. дои : 10.17487/RFC7231 . РФК 7231 . Он знает, что повторение запроса будет иметь тот же запланированный эффект, даже если исходный запрос был успешным, хотя ответ может отличаться.
  15. ^ Джон Оустерхаут . «Пейджинг по требованию» .
  16. ^ Марк А. де Круйф. «Компиляторное построение идемпотентных областей и приложения в архитектурном проектировании» . 2012. п. 10.
  17. ^ «Информация/инструкции по техническим характеристикам пассажирского лифта с тяговым механизмом» (PDF) . Департамент труда Северной Каролины, Лифтовое бюро . 2002. Архивировано из оригинала (PDF) 23 мая 2011 г. Например, эта проектная спецификация включает подробный алгоритм того, когда кабины лифта будут реагировать на последующие вызовы службы поддержки.

Дальнейшее чтение [ править ]

Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 485959584ca229403b5e1608ee72b9c2__1717610400
URL1:https://arc.ask3.ru/arc/aa/48/c2/485959584ca229403b5e1608ee72b9c2.html
Заголовок, (Title) документа по адресу, URL1:
Idempotence - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)