Idempotencja - Idempotence
Idempotentność ( UK : / ˌ ɪ d ɛ m P oʊ t ən s / , USA : / ˌ aɪ d ə m - / ) jest właściwością niektórych operacji w matematyce oraz informatyce przy czym mogą one być stosowane kilka razy, bez zmieniania wynik wykraczający poza początkowe zastosowanie. Pojęcie idempotencji pojawia się w wielu miejscach w algebrze abstrakcyjnej (w szczególności w teorii rzutników i operatorów domknięcia ) oraz w programowaniu funkcjonalnym (w którym wiąże się z właściwością przezroczystości referencyjnej ).
Termin ten został wprowadzony przez Benjamina Peirce'a w kontekście elementów algebr, które pozostają niezmienne po podniesieniu do dodatniej potęgi całkowitej i dosłownie oznacza „( cecha posiadania) tej samej potęgi”, od idem + moc (ta sama + potęga).
Definicja
Elementem x zestawu S wyposażony operatora binarnego • mówi się idempotentnych pod • jeżeli
- x • x = x .
Operacja binarna • mówi się, że jest idempotentna, jeśli
- ∀ x ∈ S , x • x = x .
Przykłady
- W monoidzie (ℕ, ×) liczb naturalnych z mnożeniem tylko 0 i 1 są idempotentne. Rzeczywiście, 0 × 0 = 0 i 1 × 1 = 1 , co nie obowiązuje dla innych liczb naturalnych.
- W magmie ( M , •) element tożsamościowy e lub element absorbujący a , jeśli istnieje, jest idempotentny. Rzeczywiście, e • e = e i a • a = a .
- W grupie ( G , •) element tożsamości e jest jedynym idempotentnym elementem. W istocie, jeśli x jest elementem G w taki sposób, x • x = x , a x • x = x • e a wreszcie x = e , mnożąc po lewej stronie przez elementu odwrotnym od x .
- W monoidach (𝒫( E ), ∪) i (𝒫( E ), ∩) zbioru potęgowego zbioru E z sumą zbioru ∪ i przecięciem zbioru ∩ odpowiednio ∪ i ∩ są idempotentne. Rzeczywiście, ∀ x , x ∪ x = x i ∀ x , x ∩ x = x .
- W monoidach ({0, 1}, ∨) i ({0, 1}, ∧) domeny Boole'a z logiczną alternatywą ∨ i logiczną koniunkcją ∧ odpowiednio, ∨ i ∧ są idempotentne. Rzeczywiście, ∀ x , x ∨ x = x i ∀ x , x ∧ x = x .
- W pierścieniu logicznym mnożenie jest idempotentne.
- W semiringu Tropical dodatek jest idempotentny.
Funkcje idempotentne
W monoidzie ( E E , ∘ ) funkcji ze zbioru E do siebie ze złożeniem funkcji ∘ , elementami idempotentnymi są funkcje f : E → E takie, że f ∘ f = f , czyli takie, że ∀ x , f ( f ( x )) = f ( x ) (obraz każdego elementu E jest punktem stałym w f ). Na przykład:
- wartość bezwzględna jest idempotent. Rzeczywiście, abs ∘ abs = abs , czyli ∀ x , abs(abs( x )) = abs( x ) ;
- funkcje stałe są idempotentne;
- funkcja tożsamości jest idempotent;
- funkcje podłogi , sufitu i części ułamkowej są idempotentne;
- funkcja generowana przez podgrupę z zestawu mocy grupy do siebie jest idempotentna;
- wypukłe kadłuba funkcja ze zbioru mocy w przestrzeń afiniczna ciągu liczb rzeczywistych do siebie jest idempotent;
- z zamknięcia i wewnętrzne funkcje zestawu zasilającego z przestrzeni topologicznej do siebie są idempotent;
- na domknięcie kleene'ego i Kleene plus funkcje zestawu zasilającego z monoid do siebie są idempotent;
- z idempotent endomorfizm o przestrzeni wektorowej są jego występy .
Jeśli zbiór E ma n elementów, możemy podzielić go na k wybranych punktów stałych i n − k punktów niestałych pod f , a wtedy k n − k jest liczbą różnych funkcji idempotentnych. Stąd biorąc pod uwagę wszystkie możliwe podziały,
to całkowita liczba możliwych idempotentnych funkcji na zestawie. Sekwencja całkowitą od liczby funkcji idempotentnych podaną przez sumę powyżej dla n = 0, 1, 2, 3, 4, 5, 6, 7, 8, ... rozpoczyna się 1, 1, 3, 10, 41, 196 , 1057, 6322, 41393, … (sekwencja A000248 w OEIS ).
Ani właściwość bycia idempotentnym, ani bycia nie jest zachowana w kompozycji funkcji. Na przykład w przypadku pierwszego f ( x ) = x mod 3 i g ( x ) = max ( x , 5) są idempotent, ale F ∘ g nie jest jednak g ∘ F zdarza się. Jako przykład dla tego ostatniego, funkcja negacji ¬ w domenie Boole'a nie jest idempotentna, ale ¬ ∘ ¬ jest. Podobnie, jednoargumentowa negacja −( ) liczb rzeczywistych nie jest idempotentna, ale −( ) ∘ −( ) jest.
Znaczenie informatyki
W informatyce termin idempotencja może mieć różne znaczenie w zależności od kontekstu, w jakim jest stosowany:
- w programowaniu bezwzględnej , o podprogram z efektów ubocznych jest idempotent jeśli wielokrotne wywołania podprogramu mają taki sam wpływ na stan systemu jako jednego połączenia, innymi słowy, jeśli funkcja z przestrzeni stanu systemu do siebie związanego z podprogramu jest idempotent w sens matematyczny podany w definicji ;
- w programowania funkcyjnego , A czysta funkcja jest idempotent jeśli jest idempotent w sensie matematycznym podanym w definicji .
Jest to bardzo przydatna właściwość w wielu sytuacjach, ponieważ oznacza, że operację można powtarzać lub ponawiać tak często, jak to konieczne, bez powodowania niezamierzonych skutków. W przypadku operacji nieidempotentnych algorytm może być zmuszony do śledzenia, czy operacja została już wykonana, czy nie.
Przykłady informatyki
Funkcja wyszukująca nazwę i adres klienta w bazie danych jest zazwyczaj idempotentna, ponieważ nie spowoduje to zmiany bazy danych. Podobnie prośba o zmianę adresu klienta na XYZ jest zazwyczaj idempotentna, ponieważ ostateczny adres będzie taki sam bez względu na to, ile razy zostanie złożone żądanie. Jednak prośba klienta o złożenie zamówienia zazwyczaj nie jest idempotentna, ponieważ wiele żądań doprowadzi do złożenia wielu zamówień. Prośba o anulowanie konkretnego zamówienia jest idempotentna, ponieważ bez względu na to, ile żądań zostanie złożonych, zamówienie pozostaje anulowane.
Sekwencja idempotentnych podprogramów, w których co najmniej jeden podprogram różni się od pozostałych, nie musi być jednak koniecznie idempotentna, jeśli późniejszy podprogram w sekwencji zmienia wartość, od której zależy wcześniejszy podprogram — idempotentność nie jest zamykana przy składaniu sekwencyjnym . Załóżmy na przykład, że początkowa wartość zmiennej to 3 i istnieje sekwencja podprogramu, która odczytuje zmienną, następnie zmienia ją na 5, a następnie ponownie ją odczytuje. Każdy krok w sekwencji jest idempotentny: oba kroki odczytu zmiennej nie mają skutków ubocznych, a krok zmieniający zmienną na 5 będzie zawsze miał ten sam efekt, bez względu na to, ile razy zostanie wykonany. Niemniej jednak wykonanie całej sekwencji raz daje wynik (3, 5), ale wykonanie go po raz drugi daje wynik (5, 5), więc sekwencja nie jest idempotentna.
int x = 3;
void read() { printf("%d\n", x); }
void change() { x = 5; }
void sequence() { read(); change(); read(); }
int main() {
sequence(); // prints "3\n5\n"
sequence(); // prints "5\n5\n"
return 0;
}
W protokole Hypertext Transfer Protocol (HTTP) idempotencja i bezpieczeństwo to główne atrybuty, które oddzielają metody HTTP . Z głównych metod HTTP, GET, PUT i DELETE powinny być zaimplementowane w sposób idempotentny zgodnie ze standardem, ale POST nie musi. GET pobiera stan zasobu; PUT aktualizuje stan zasobu; a DELETE usuwa zasób. Tak jak w powyższym przykładzie, odczytywanie danych zwykle nie ma skutków ubocznych, więc jest idempotentne (w rzeczywistości nullipotentne ). Aktualizowanie i usuwanie danych danych jest zwykle idempotentne, o ile żądanie jednoznacznie identyfikuje zasób i tylko ten zasób w przyszłości. PUT i DELETE z unikalnymi identyfikatorami ograniczają się do prostego przypadku przypisania do zmiennej odpowiednio wartości lub wartości null i są idempotentne z tego samego powodu; wynik końcowy jest zawsze taki sam jak wynik początkowego wykonania, nawet jeśli odpowiedź jest inna.
Naruszenie wymogu unikatowej identyfikacji podczas przechowywania lub usuwania zazwyczaj powoduje naruszenie idempotencji. Na przykład przechowywanie lub usuwanie danego zestawu treści bez określenia unikalnego identyfikatora: żądania POST, które nie muszą być idempotentne, często nie zawierają unikalnych identyfikatorów, więc utworzenie identyfikatora jest delegowane do systemu odbierającego, który następnie tworzy odpowiedni nowy rekord. Podobnie żądania PUT i DELETE z nieokreślonymi kryteriami mogą skutkować różnymi wynikami w zależności od stanu systemu - na przykład żądanie usunięcia najnowszego rekordu. W każdym przypadku kolejne wykonania będą dalej modyfikować stan systemu, więc nie są idempotentne.
W przetwarzaniu strumienia zdarzeń idempotencja odnosi się do zdolności systemu do generowania tego samego wyniku, nawet jeśli ten sam plik, zdarzenie lub komunikat są odbierane więcej niż raz.
W architekturze load-store instrukcje, które mogą spowodować błąd strony, są idempotentne. Jeśli więc wystąpi błąd strony, system operacyjny może załadować stronę z dysku, a następnie po prostu ponownie wykonać błędną instrukcję. W procesorze, w którym takie instrukcje nie są idempotentne, radzenie sobie z błędami stron jest znacznie bardziej złożone.
Podczas ponownego formatowania wydruku oczekuje się , że ładne drukowanie będzie idempotentne. Innymi słowy, jeśli wydruk jest już „ładny”, nie powinno być nic do roboty dla ładnej drukarki.
W architekturze zorientowanej na usługi (SOA) wieloetapowy proces orkiestracji składający się wyłącznie z idempotentnych kroków może zostać odtworzony bez skutków ubocznych, jeśli jakakolwiek część tego procesu zawiedzie.
Wiele operacji, które są idempotentne, często ma sposoby na „wznowienie” procesu, jeśli zostanie on przerwany – sposoby, które kończą się znacznie szybciej niż rozpoczynanie wszystkiego od początku. Na przykład wznawianie transferu plików , synchronizowanie plików , tworzenie kompilacji oprogramowania , instalowanie aplikacji i wszystkich jej zależności za pomocą menedżera pakietów itp.
Zastosowane przykłady
Przykładami, z którymi wiele osób może się spotkać w swoim codziennym życiu, są przyciski wywołania windy i przyciski przejścia dla pieszych . Początkowa aktywacja przycisku przenosi system w stan żądania, aż żądanie zostanie spełnione. Kolejne aktywacje przycisku między początkową aktywacją a spełnieniem żądania nie przynoszą efektu, chyba że system jest zaprojektowany tak, aby dostosować czas realizacji żądania na podstawie liczby aktywacji.
Zobacz też
- Zestaw dwukierunkowy
- Operator zamknięcia
- Punkt stały (matematyka)
- Idempotentny kod
- Idempotentna analiza
- Idempotentna macierz
- Relacja idempotentna – uogólnienie idempotencji na relacje binarne
- Inwolucja (matematyka)
- Funkcja iterowana
- Lista macierzy
- Nilpotentny
- Czysta funkcja
- Przejrzystość referencyjna
Bibliografia
Dalsza lektura
- „ Idempotentny ” w FOLDOC
- Goodearl, KR (1991), pierścienie regularne von Neumanna (2 wyd.), Malabar, FL: Robert E. Krieger Publishing Co. Inc., s. xviii + 412, ISBN 978-0-89464-632-4, MR 1150975
- Gunawardena, Jeremy (1998), "Wprowadzenie do idempotencji" (PDF) , w Gunawardena, Jeremy (red.), Idempotentność. Na podstawie warsztatów, Bristol, Wielka Brytania, 3-7 października 1994 , Cambridge: Cambridge University Press , s. 1-49, Zbl 0898.16032
- "Idempotent" , Encyklopedia Matematyki , EMS Press , 2001 [1994]
- Hazewinkel, Michiel ; Gubareni, Nadija; Kirichenko, VV (2004), Algebry, pierścienie i moduły. Tom. 1 , Mathematics and its Applications, 575 , Dordrecht: Kluwer Academic Publishers, s. xii+380, ISBN 978-1-4020-2690-4, MR 2106764
- Lam, TY (2001), A first course in noncommutative rings , Graduate Texts in Mathematics, 131 (2 wyd.), New York: Springer-Verlag, s. xx+385, doi : 10.1007/978-1-4419-8616 -0 , ISBN 978-0-387-95183-6, MR 1838439
- Lang, Serge (1993), Algebra (wyd. trzecie), Reading, Mass .: Addison-Wesley, ISBN 978-0-201-55540-0, Zbl 0848.13001P. 443
- Peirce, Benjamin. Algebra liniowa asocjacyjna 1870.
- Polcino Milies, César; Sehgal, Sudarshan K. (2002), Wprowadzenie do pierścieni grupowych , Algebras and Applications, 1 , Dordrecht: Kluwer Academic Publishers, s. XII+371, doi : 10.1007/978-94-010-0405-3 , ISBN 978-1-4020-0238-0, MR 1896125