it-swarm-tr.com

Değişmeyen döngü nedir?

CLRS tarafından "Algoritmaya Giriş" okuyorum. 2. bölümde, yazarlar "döngü değişmezlerinden" bahseder. Değişmeyen döngü nedir?

240
Attilah

Basit bir deyişle, bir döngü değişmezi, döngünün her yinelemesi için geçerli olan bir koşuldur (koşul). Örneğin, şuna benzeyen basit bir for döngüsüne bakalım:

int j = 9;
for(int i=0; i<10; i++)  
  j--;

Bu örnekte, doğru (her yineleme için) i + j == 9. Doğru olan daha zayıf bir değişmez de, i >= 0 && i <= 10.

308
Tomas Petricek

Bu çok basit tanımı seviyorum: ( kaynak )

Bir döngü değişmezi [program değişkenleri arasında] mutlaka bir döngünün her yinelemesinden hemen önce ve hemen sonra doğru olan bir durumdur. (Bunun yinelemenin bir yolu gerçeği veya sahtekarlığı hakkında hiçbir şey söylemediğine dikkat edin.)

Kendi başına, bir döngü değişmez fazla yapmaz. Bununla birlikte, uygun bir değişmez verildiğinde, bir algoritmanın doğruluğunu kanıtlamaya yardımcı olmak için kullanılabilir. CLRS'deki basit örnek muhtemelen sıralama ile ilgili. Örneğin, döngünüzün değişmez olmasına izin verin, döngünün başında bu dizinin ilk i girdileri sıralanır. Bunun gerçekten bir döngü değişmez olduğunu kanıtlayabilirseniz (yani, her döngü yinelemesinden önce ve sonra tuttuğunu), bunu bir sıralama algoritmasının doğruluğunu kanıtlamak için kullanabilirsiniz: döngünün sonunda, döngü değişmez yine de tatmin olur , ve i sayacı dizinin uzunluğudur. Bu nedenle, ilk i girdileri sıralanır; tüm dizinin sıralandığı anlamına gelir.

Daha basit bir örnek: Değişkenler Döngüleri, Düzeltme ve Program Türetme .

Değişmeyen bir döngü anlama şeklim, programlar hakkında düşünmek için sistematik ve resmi bir araçtır. Doğruyu kanıtlamaya odaklandığımız konusunda tek bir ifade veriyoruz ve buna değişmez döngü diyoruz. Bu mantığımızı düzenler. Bazı algoritmaların doğruluğu hakkında gayrı resmi bir şekilde tartışabilirken, değişmez bir döngü kullanmak bizi çok dikkatli düşünmeye zorlar ve mantığımızın hava geçirmez olmasını sağlar.

105
TNi

Birçok insanın döngüler ve değişmezlerle uğraşırken hemen farketmediği bir şey var. Döngü değişmezleri ile koşullu döngü (döngünün sonlandırılmasını kontrol eden koşul) arasında karışıklığa neden olurlar. 

İnsanların işaret ettiği gibi, döngü değişmezinin doğru olması gerekir 

  1. döngü başlamadan önce
  2. döngünün her yinelemesinden önce
  3. döngü sona erdikten sonra 

(Her ne kadar döngü boyunca geçici olarak yanlış olabilirse de). Diğer taraftan, döngü koşullu _ ​​must, döngü sona erdikten sonra yanlıştır, aksi takdirde döngü asla sona ermez. 

Böylece değişmeyen döngü ve koşullu must döngüsü farklı koşullar olabilir.

Değişmeyen karmaşık bir değişmeze iyi bir örnek, ikili arama içindir.

bsearch(type A[], type a) {
start = 1, end = length(A)

    while ( start <= end ) {
        mid = floor(start + end / 2)

        if ( A[mid] == a ) return mid
        if ( A[mid] > a ) end = mid - 1
        if ( A[mid] < a ) start = mid + 1

    }
    return -1

}

Bu yüzden döngü koşullu görünüyor oldukça yalındır - başlangıç> sonlandığında döngü sonlanır. Fakat döngü neden doğru? Doğruluğunu kanıtlayan döngü değişkeni nedir?

Değişmeyen mantıksal ifadedir:

if ( A[mid] == a ) then ( start <= mid <= end )

Bu ifade mantıklı bir totolojidir - kanıtlamaya çalıştığımız belirli döngü/algoritma bağlamında her zaman doğrudur. Ve sonlandırıldıktan sonra döngünün doğruluğu hakkında yararlı bilgiler sağlar.

Dizideki öğeyi bulduğumuz için dönersek, deyim açıkça doğrudur, çünkü A[mid] == a sonra a dizidedir ve mid başlangıç ​​ve bitiş arasında olmalıdır. Ve eğer döngü start > end nedeniyle sonlanırsa, start <= midvemid <= end şeklinde bir sayı olamaz ve bu nedenle A[mid] == a ifadesinin yanlış olması gerektiğini biliyoruz. Ancak, sonuç olarak, genel mantıksal ifade boş anlamıyla hala doğrudur. (Mantıkta, eğer (false) ifadesi, sonra (bir şey) her zaman doğrudur.)

Şimdi, döngü sona erdiğinde şartlı olarak mutlaka hatalı olmasından dolayı döngü hakkında söylediklerim ne olacak? Öğe dizide bulunduğunda, döngü sona erdiğinde koşullu döngü doğru olur !? Bu aslında değil, çünkü koşullu döngü gerçekten while ( A[mid] != a && start <= end ) işlevidir, ancak ilk bölüm ima edildiğinden beri gerçek testi kısaltırız. Bu koşul, döngünün sonlandırılmasından bağımsız olarak döngüden sonra açıkça yanlıştır.

35
Robert S. Barnes

Önceki cevaplar bir Döngü Değişmezini çok iyi bir şekilde tanımlamıştır.

Şimdi CLRS yazarlarının nasıl Loop Invariants kullandığını doğruluğunu Ekleme Sıralamasını kanıtladığını açıklamaya çalışayım.

Ekleme Sıralama algoritması (Kitapta verilen şekilde):

INSERTION-SORT(A)
    for j ← 2 to length[A]
        do key ← A[j]
        // Insert A[j] into the sorted sequence A[1..j-1].
        i ← j - 1
        while i > 0 and A[i] > key
            do A[i + 1] ← A[i]
            i ← i - 1
        A[i + 1] ← key

Döngü Değişmez Bu durumda (Kaynak: CLRS kitabı): Alt dizilim [1 - j-1] her zaman sıralanır.

Şimdi bunu kontrol edelim ve algoritmanın doğru olduğunu ispatlayalım.

Başlatma : İlk yinelemeden önce j = 2. Yani Alt Dizi [1: 1] test edilecek dizidir. Yalnızca bir öğeye sahip olduğu için sıralanır.

Bakım : Bu, her yinelemeden sonra değişmeyenleri kontrol ederek kolayca doğrulanabilir. Bu durumda tatmin olur.

Sonlandırma : Bu, algoritmanın doğruluğunu kanıtlayacağımız adımdır.

Döngü sona erdiğinde, j = n + 1'in değeri. Yine Döngü değişmez tatmin edicidir.

Algoritmamızla yapmak istediğimiz şey bu. Algoritmamız doğru.

30
Tushar Kathuria

Tüm iyi cevapların yanında, Algoritmalar Nasıl Düşünülür, Jeff Edmonds 'in harika bir örneği olduğunu düşünüyorum.

ÖRNEK 1.2.1 "Find-Max İki Parmak Algoritması"

1) Özellikler: Bir giriş örneği, .__ L(1..n) listesinden oluşur. elementler. Çıktı, L(i) maksimum .__ 'a sahip olacak şekilde i indeksinden oluşur. değer. Aynı değerde birden fazla giriş varsa, o zaman herhangi bir bunlardan biri iade edildi.

2) Temel Adımlar: İki parmak yöntemine karar veriyorsunuz. Sağ parmağın. liste aşağı çalışır.

3) İlerlemenin Ölçülmesi: İlerlemenin ölçüsü, sağ parmağını listele.

4) Döngü Değişmez: Döngü değişmezi, sol parmağınızın, bugüne kadar karşılaştığınız en büyük girişlerden birini işaret ettiğini belirtir. sağ parmak.

5) Ana Adımlar: Her yineleme, sağ parmağınızı bir aşağı hareket ettirirsiniz. Listeye giriş yapın. Sağ parmağınız şimdi bir girişi işaret ediyorsa, Sol parmak girişinden sonra daha büyük, sonra sola hareket ettirin. parmağınızı sağ parmağınızla olmak.

6) İlerleme Yap: İlerlemişsin çünkü sağ parmağın hareket ediyor. bir giriş.

7) Döngü Değişmez Tutar: Döngü değişmezinin aşağıdaki gibi tutulduğunu biliyorsunuz. Her adım için, yeni sol parmak elemanı Max (eski sol parmak elemanı, yeni eleman). Değişmeyen döngü tarafından, bu Max (Max (kısa liste), yeni eleman). Matematiksel olarak, bu, Max (daha uzun liste).

8) Döngü Değişmezinin Kurulması: Başlangıçta her iki parmağınızı da birinci elemana doğru yönlendirerek değişmez döngüyü kurarsınız.

9) Çıkış Koşulu: Sağ parmağınız bittiğinde yapılır. listeyi dolaşıyor.

10) Bitiş: Sonunda sorunun şu şekilde çözüldüğünü biliyoruz. Tarafından Çıkış koşulunda sağ parmağınız tüm harflerle karşılaştı. girdileri. Değişmeyen döngüde, sol parmağınız maksimum .__ işaret eder. bunların. Bu girişi döndür.

11) Fesih ve Çalışma Süresi: Gerekli zaman biraz sabit. listenin uzunluğunu.

12) Özel Durumlar: Birden fazla giriş olduğunda ne olduğunu kontrol edin aynı değerde veya n = 0 veya n = 1 olduğunda.

13) Kodlama ve Uygulama Detayları: ...

14) Resmi Kanıt: Algoritmanın doğruluğu yukarıda.

16
Vahid Rafiei

Bir Döngü Değişmezinin, her yinelemenin başlangıcında ve döngü sona erdiğinde doğru olması gereken değişkenler arasındaki önemli ilişkileri ifade eden bir iddia olarak değerlendirildiğinde yinelemeli algoritmaların tasarımında yardımcı olabileceği belirtilmelidir. Bu durum geçerliyse, hesaplama etkinliğe giden yoldadır. False olursa, algoritma başarısız olmuştur.

6
Eric Steen

Bu durumda değişmez, her döngü yinelemesinde belirli bir noktada doğru olması gereken bir koşul anlamına gelir.

Sözleşmeli programlamada değişmez, herhangi bir genel yöntemin çağrılmasından önce ve sonra (sözleşmeyle) doğru olması gereken bir durumdur.

5
Mark Rushakoff

Değişmezliğin anlamı asla değişmez

Burada döngü değişmez "Döngüdeki değişkenin meydana geldiği değişim (artan veya azalan) döngü koşulunu değiştirmiyor yani koşul tatmin edici" anlamına geliyor, böylece döngü değişmeyen kavramı ortaya çıkıyor 

4
sasidhar

Üzgünüm yorum yapma iznim yok.

Bahsettiğiniz gibi @Tomas Petricek

Ayrıca doğru olan daha zayıf bir değişmez: i> = 0 && i <10 (çünkü bu devam koşulu!) " 

Değişmeyen döngü nasıl?

Umarım yanlış değilim, anladığım kadarıyla[1], Döngü değişmez, döngünün başında (Başlatma) doğru olacak, her yinelemeden (Bakım) önce ve sonra doğru olacak ve döngünün sona ermesinden sonra da geçerli olacaktır (Sonlandırma). Ancak son yinelemeden sonra i, 10 olur. Böylece, i> = 0 && i <10 koşulu yanlış olur ve döngüyü sonlandırır. Değişmeyen döngünün üçüncü özelliğini (Sonlandırma) ihlal eder.

[1] http://www.win.tue.nl/~kbuchin/teaching/JBP030/notebooks/loop-invariants.html

1
Mahmudul Haque

Döngülerde neler olup bittiğini takip etmek zor. Hedef davranışlarına ulaşmadan sonlandırmayan veya sonlanmayan döngüler bilgisayar programlamasında sık karşılaşılan bir sorundur. Döngü değişmezleri yardım eder. Döngü değişmezi, programınızdaki, döngü hiç çalıştırılmadan hemen önce geçerli olan (değişmezi oluşturan) değişkenler arasındaki ilişkiye dair resmi bir ifadedir ve döngünün altında, döngü boyunca her zaman (değişmezliği koruyarak) ) . Kodunuzda Döngü Değişmezlerinin kullanımının genel örneği:

... // Loop Invariant burada doğru olmalı
while (TEST DURUMU) {
// döngünün üstü
...
// döngünün alt
// Loop Invariant burada doğru olmalı
}
// Fesih + Döngü Değişmez = Hedef
...
Döngünün üst ve altı arasında, döngünün hedefine ulaşmak için büyük olasılıkla ilerleme sağlanmıştır. Bu değişmezi rahatsız edebilir (yanlış yapabilir). Döngü Değişmezlerinin amacı değişmezin, her seferinde döngü gövdesini tekrar etmeden önce restore edileceği vaadidir. __ Bunun iki avantajı vardır:

Çalışma, karmaşık, veriye bağlı şekillerde bir sonraki geçişte ilerletilmez. Her biri döngüden diğerlerinden bağımsız olarak geçişi yapar, değişmezlerin geçişleri birlikte çalışan bir bütüne bağlamak için hizmet ederler. Bu, döngünün karmaşık genel davranışını, her biri ayrı ayrı ele alınabilecek küçük basit adımlara böler .. __ Döngünün test durumu değişmezin bir parçası değildir. Döngüyü sonlandıran şey budur. Ayrı olarak iki şeyi göz önünde bulundurursunuz: döngünün neden hiç sona ermemesi ve döngünün sona erdiğinde neden hedefine ulaşması gerektiğini. Döngü boyunca her seferinde sonlandırma koşulunu yerine getirmeye yaklaştığınızda döngü sona erer. Bunu sağlamak genellikle kolaydır: ör. Bir sayaç değişkenini sabit bir üst sınıra ulaşana kadar bir adım atmak. Bazen sonlandırmanın ardındaki sebep daha zordur.

Döngü değişmezi, fesih koşuluna ulaşıldığında ve değişmez doğru olduğunda, hedefe ulaşılması için yaratılmalıdır.

değişmez + sonlandırma => hedef
.__ Fesih dışındaki tüm hedeflere ulaşmayı hedefleyen basit ve ilgili değişmezler yaratmak pratik gerektirir. Döngü değişmezlerini ifade etmek için matematiksel semboller kullanmak en iyisidir, ancak bu aşırı karmaşık durumlara yol açtığında, açık bir düzene ve sağduyuya güveniriz.

1
Tilak raj

Döngü Değişmez Özelliği, bir döngü uygulamasının her adımı için geçerli olan bir durumdur (örneğin, döngüler, döngüler vb. İçin)

Bu, bir döngü algoritmasının, yürütmenin her aşamasında bu döngü değişmez özelliğini tutarsa ​​doğru şekilde çalıştığını gösterebilen bir Döngü Değişmez Kanıtı için önemlidir.

Bir algoritmanın doğru olması için, Döngü Değişmezinin aşağıdakileri tutması gerekir:

Başlatma (başlangıç)

Bakım (sonraki her adım)

Fesih (bittiğinde)

Bu, bir çok şeyi değerlendirmek için kullanılır, ancak en iyi örnek, ağırlıklı grafik geçişi için açgözlü algoritmalardır. Açgözlü bir algoritmanın optimum bir çözüm (grafik boyunca bir yol) vermesi için, mümkün olan en düşük ağırlık yolundaki tüm düğümleri birbirine bağlaması gerekir.

Böylece, döngü değişmez özelliği, alınan yolun en az ağırlığa sahip olmasıdır. başında hiçbir kenar eklemedik, bu nedenle bu özellik doğru (bu durumda yanlış değil). Her adımda , en düşük ağırlıklı kenarı (açgözlü adım) takip ediyoruz, bu yüzden yine en düşük ağırlık yolunu izliyoruz. sonunda , en düşük ağırlıklı yolu bulduk, bu yüzden mülkümüz de doğru.

Bir algoritma bunu yapmazsa, optimal olmadığını ispatlayabiliriz.

1
Alex Mapley

Döngü değişmez, (x=y+1) gibi matematiksel bir formüldür. Bu örnekte, x ve y, bir döngü içindeki iki değişkeni temsil eder. Bu değişkenlerin kodun yürütülmesi sırasındaki değişen davranışları göz önüne alındığında, olası tüm x ve y değerlerini test etmek ve herhangi bir hata üretip üretmediklerini görmek neredeyse imkansızdır. Diyelim ki x bir tamsayıdır. Tamsayı bellekte 32 bit boşluk tutabilir. Bu sayı aşarsa, arabellek taşması oluşur. Bu nedenle, kodun yürütülmesi sırasında, bu alanı asla aşmadığından emin olmamız gerekir. Bunun için değişkenler arasındaki ilişkiyi gösteren genel bir formülü anlamamız gerekir. Zaten, programın davranışını anlamaya çalışıyoruz.

0
Mehmet YILMAZ

Basit bir deyişle, her döngü yinelemesinde geçerli olan bir LOOP koşuludur:

for(int i=0; i<10; i++)
{ }

Bu biz i söyleyebiliriz diyebiliriz i<10 and i>=0

0
i.maddy

Bir döngü değişmezi, döngü yürütmeden önce ve sonra doğru bir iddiadır.

0
timkofu