İdempotans - Idempotence

Bir trenin hedef işareti kontrol panelinin Açma / Kapama düğmeleri . Açık düğmesine (yeşil) basmak, bir veya birden çok kez yapıldığında aynı etkiye sahip olduğundan, önemsiz bir işlemdir. Aynı şekilde, Off'a basmak da yetersizdir.

Idempotence ( UK : / ˌ ɪ d ɛ m p t ən s / , ABD : / ˌ d ə m - / ), belirli bir özellik olan işlemler de matematik ve bilgisayar biliminin bunlar değiştirmeden birden fazla kez uygulanabilir ve böylece ilk uygulamanın ötesinde sonuç. Bağımsızlık kavramı, soyut cebirde (özellikle projektörler ve kapatma operatörleri teorisinde ) ve işlevsel programlamada (gösterge şeffaflığının özelliğine bağlı olduğu ) birçok yerde ortaya çıkar.

Terim Benjamin Peirce tarafından pozitif bir tamsayı gücüne yükseltildiğinde değişmez kalan cebir öğeleri bağlamında tanıtıldı ve kelimenin tam anlamıyla idem + potence (aynı + güç) ' den "aynı güce (sahip olma niteliği)" anlamına gelir .

Tanım

Bir eleman X bir dizi S ikili bir motor sayesinde • olduğu söylenir idempotent • eğer altında

xx = x .

İkili işlem • olduğu söylenir İdempotent eğer

xS , xx = x .

Örnekler

  • Gelen Monoid arasında (ℕ, x) doğal sayılar ile çarpımı , sadece 0 ve 1 İdempotent vardır. Gerçekten de, 0 × 0 = 0 ve 1 × 1 = 1 , diğer doğal sayılar için geçerli değildir.
  • Bir magmada ( M , •), bir özdeşlik öğesi e veya bir soğurucu öğe a , eğer varsa, idempotenttir. Gerçekten de, ee = e ve aa = a .
  • Bir grupta ( G , •), kimlik öğesi e tek idempotent öğedir. Gerçekten de, eğer X bir elemanıdır G , öyle ki xx = x , o zaman Xx = xe ve son olarak x = E ile sol çarparak ters elemanının bir x .
  • Monoids (𝒫 (içinde E ), ∪) ve (𝒫 ( E arasında), ∩) güç grubu seti E ile resim birlik ∪ ve resim kesişme sırasıyla ∩, ∪ ve ∩ İdempotent vardır. Gerçekten de, x , xx = x ve x , xx = x .
  • Sırasıyla mantıksal ayrılma ∨ ve mantıksal bağlaç ∧ ile Boole alanının monoidlerinde ({0, 1}, ∨) ve ({0, 1}, ∧) , ∨ ve ∧ idempotenttir. Gerçekten de, x , xx = x ve x , xx = x .
  • Bir de Boole halkası , çarpma İdempotent olduğunu.
  • Bir de Tropikal semiring , ekleme İdempotent olduğunu.

Idempotent fonksiyonlar

Fonksiyon bileşimi ∘ olan bir E kümesinden kendisine fonksiyonların monoidinde ( E E , ∘) , idempotent elemanlar f : EE fonksiyonlarıdır, öyle ki ff = f , yani x , f ( f ( x )) = f ( x ), (her bir elemanın görüntü E a, sabit nokta arasında f ). Örneğin:

Set halinde E sahiptir n elemanları, biz içine bölmek k seçilen sabit noktaları ve n - k altında olmayan sabit noktaları f ve sonra k , n - k farklı İdempotent fonksiyonlarının sayısıdır. Bu nedenle, olası tüm bölümleri dikkate alarak,

kümedeki olası idempotent fonksiyonların toplam sayısıdır. Tam sayı dizisi İdempotent fonksiyonlarının sayısı yukarıda toplamı ile verilen için n = 0, 1, 2, 3, 4, 5, 6, 7, 8, ... başlar 1, 1, 3, 10, 41, 196 ile birlikte , 1057, 6322, 41393, ... (dizi A000248 olarak OEIS ).

İşlev bileşimi altında ne bağımsız olma, ne de olmama özelliği korunur. Birincisine örnek olarak, f ( x ) = x mod 3 ve g ( x ) = max( x , 5) ikisi de bağımsızdır, ancak gf olmasına rağmen fg değildir . İkincisi için bir örnek olarak, Boole etki alanındaki olumsuzlama işlevi ¬ idempotent değildir, ancak ¬ ∘ ¬ öyledir . Benzer şekilde, gerçek sayıların −( ) tekli olumsuzlaması idempotent değildir, ancak −( ) ∘ −( ) idempotenttir .

bilgisayar bilimi anlamı

Gelen bilgisayar bilimleri , terim idempotence o uygulamalı olduğu bağlama göre farklı bir anlamı olabilir:

Bu, bir işlemin istenmeyen etkilere neden olmadan gerektiği kadar tekrarlanabileceği veya yeniden denenebileceği anlamına geldiğinden, birçok durumda çok yararlı bir özelliktir. İdempotent olmayan işlemlerde, algoritmanın işlemin daha önce gerçekleştirilip gerçekleştirilmediğini takip etmesi gerekebilir.

Bilgisayar bilimi örnekleri

Bir veritabanında müşterinin adını ve adresini arayan bir işlev , veritabanının değişmesine neden olmayacağından genellikle önemsizdir. Benzer şekilde, bir müşterinin adresini XYZ olarak değiştirme talebi genellikle önemsizdir, çünkü talep kaç kez gönderilirse gönderilsin nihai adres aynı olacaktır. Bununla birlikte, birden çok istek birden çok siparişin verilmesine yol açacağından, bir müşterinin sipariş verme isteği genellikle önemsiz değildir. Belirli bir siparişi iptal etme talebi geçersizdir çünkü ne kadar istek yapılırsa yapılsın sipariş iptal edilmiş olarak kalır.

Bununla birlikte, en az bir alt rutinin diğerlerinden farklı olduğu bir idempotent alt yordam dizisi, dizideki sonraki bir alt yordam, daha önceki bir alt yordamın bağlı olduğu bir değeri değiştirirse, zorunlu olarak bağımsız değildir - sıralı bileşim altında impotans kapatılmaz . Örneğin, bir değişkenin başlangıç ​​değerinin 3 olduğunu ve değişkeni okuyan, sonra onu 5 olarak değiştiren ve sonra tekrar okuyan bir alt rutin dizisi olduğunu varsayalım. Dizideki her adım önemsizdir: değişkeni okuyan her iki adımın da yan etkisi yoktur ve değişkeni 5'e değiştiren adım, kaç kez yürütülürse çalıştırılsın her zaman aynı etkiye sahip olacaktır. Bununla birlikte, dizinin tamamını bir kez yürütmek çıktıyı (3, 5) üretir, ancak ikinci kez yürütmek çıktıyı (5, 5) üretir, bu nedenle dizi önemsiz değildir.

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;
}

Gelen Köprü Transferi Protokolü (HTTP), idempotence ve güvenlik önemli nitelikler olduğu ayrıdır HTTP yöntemleri . Başlıca HTTP yöntemlerinden GET, PUT ve DELETE, standarda göre bağımsız bir şekilde uygulanmalıdır, ancak POST'un olması gerekmez. GET, bir kaynağın durumunu alır; PUT, bir kaynağın durumunu günceller; ve DELETE bir kaynağı siler. Yukarıdaki örnekte olduğu gibi, verileri okumanın genellikle hiçbir yan etkisi yoktur, bu nedenle idempotenttir (aslında nullipotent ). Belirli bir verinin güncellenmesi ve silinmesi, istek kaynağı ve gelecekte yalnızca o kaynağı benzersiz bir şekilde tanımladığı sürece genellikle önemsizdir. Benzersiz tanımlayıcılara sahip PUT ve DELETE, sırasıyla bir değer veya boş değerden oluşan bir değişkene atamanın basit durumuna indirgenir ve aynı nedenle bağımsızdır; yanıt farklı olsa bile, sonuç her zaman ilk yürütmenin sonucuyla aynıdır.

Depolamada veya silmede benzersiz tanımlama gereksiniminin ihlali, tipik olarak bağımsızlığın ihlaline neden olur. Örneğin, benzersiz bir tanımlayıcı belirtmeden belirli bir içerik kümesini depolamak veya silmek: bağımsız olması gerekmeyen POST istekleri, genellikle benzersiz tanımlayıcılar içermez, bu nedenle tanımlayıcının oluşturulması, daha sonra oluşturan alıcı sisteme devredilir. karşılık gelen yeni bir kayıt. Benzer şekilde, belirli olmayan kriterlere sahip PUT ve DELETE istekleri, sistemin durumuna bağlı olarak farklı sonuçlarla sonuçlanabilir - örneğin, en son kaydı silme talebi. Her durumda, sonraki yürütmeler sistemin durumunu daha da değiştirecektir, bu nedenle bunlar önemsiz değildir.

Olarak olay akışı işleme , idempotence aynı dosya, olay veya mesaj birden çok kez alındığında bile, aynı sonucu elde etmek için bir sistem yeteneğini ifade eder.

Bir yükleme-depolama mimarisinde , muhtemelen bir sayfa hatasına neden olabilecek yönergeler önemsizdir. Bu nedenle, bir sayfa hatası meydana gelirse, işletim sistemi sayfayı diskten yükleyebilir ve ardından hatalı talimatı yeniden yürütebilir. Bu tür talimatların yetersiz olmadığı bir işlemcide, sayfa hatalarıyla uğraşmak çok daha karmaşıktır.

Çıktıyı yeniden biçimlendirirken, güzel yazdırmanın yetersiz olması beklenir. Başka bir deyişle, çıktı zaten "güzel" ise, güzel yazıcı için yapacak bir şey olmamalıdır.

Olarak Servis Odaklı Mimari bu sürecin bir parçası başarısız olursa (SOA) tamamen İdempotent adımlardan oluşan bir çok-aşamalı düzenleme işlemi yan etkiler olmaksızın yeniden gönderilebilir.

Belirsiz olan birçok işlem, kesintiye uğradığında genellikle bir süreci "devam ettirme" yollarına sahiptir - baştan başlamaktan çok daha hızlı biten yollar. Örneğin, bir dosya aktarımını sürdürmek , dosyaları senkronize etmek , bir yazılım derlemesi oluşturmak , bir uygulama ve onun tüm bağımlılıklarını bir paket yöneticisi ile kurmak , vb.

Uygulamalı örnekler

Tipik bir yaya geçidi düğmesi, idempotent bir sistemin bir örneğidir

Birçok insanın günlük yaşamlarında karşılaşabileceği uygulamalı örnekler arasında asansör çağrı düğmeleri ve yaya geçidi düğmeleri sayılabilir . Düğmenin ilk etkinleştirilmesi, istek karşılanana kadar sistemi istek durumuna geçirir. Sistem, aktivasyon sayısına dayalı olarak talebi karşılama süresini ayarlamak üzere tasarlanmadıkça, ilk aktivasyon ile talebin karşılanması arasındaki düğmenin müteakip aktivasyonlarının hiçbir etkisi yoktur.

Ayrıca bakınız

Referanslar

daha fazla okuma