Bölüm 12: Rastgele Algoritmalar

12.1Rastgelelik ve algoritmalar

12.1.1Şansa dayanan kararlar

Algoritma denince çoğunlukla tamamen belirlenmiş bir adımlar dizisi akla gelir. Aynı girdi verilirse algoritma aynı adımları aynı sırayla atar ve aynı sonucu üretir. Bu tür algoritmalara deterministik (belirlenimci) algoritma denir. Bazı problemlerde ise algoritmanın kararlarına bilinçli olarak şans katmak işe yarar. Algoritma bir noktada yazı-tura atar, zar atar ya da bir dizinin öğelerinden birini rastgele seçer ve yoluna bu seçime göre devam eder.

Şans oyunları bu fikrin en tanıdık örneğidir. İki zarın atıldığı bir oyun düşünülsün. Toplam 7 ya da 11 gelirse oyuncu kazanır; gelmezse zarlar yeniden atılır. İki zarın 36 eşit olasılıklı sonucu vardır. Toplamın 7 olduğu sonuçlar (1, 6), (2, 5), (3, 4), (4, 3), (5, 2) ve (6, 1)'dir; sayıları 6'dır. Toplamın 11 olduğu sonuçlar (5, 6) ve (6, 5)'tir; sayıları 2'dir.

P(7) = 6/36,   P(11) = 2/36,   P(kazanma) = 8/36 = 2/9 ≈ 0,22

Bir atışta kazanma olasılığı yaklaşık 0,22'dir. Oyuncu kazanana kadar kaç kez atış yapar? Bu sayı her oyunda farklıdır: bazen ilk atışta kazanılır, bazen on atış gerekir. Ama ortalaması bellidir. Her atışın kazanma olasılığı aynı ve atışlar birbirinden bağımsız olduğu için beklenen atış sayısı 1 / (2/9) = 4,5'tir. Bu sonuç geometrik dağılımdan gelir. Sabit tohumla (random.Random(42)) oynatılan 200.000 oyunda ortalama atış sayısı 4,502 çıktı; formülle uyumludur.

Zar oyunundaki iki gözlem bütün not boyunca tekrar eder. Birincisi, tek bir çalıştırmanın ne kadar süreceği önceden bilinmez; bilinen, sürenin beklenen değeridir. İkincisi, beklenen değer bir olasılık hesabıyla bulunur ve uzun bir benzetimle doğrulanabilir.

12.1.2Rastgele algoritma ve beklenen süre

Şekil 12.2 bu yapıyı gösterir. Algoritmanın iki girişi vardır: problemin girdisi ve bir rastgele bit kaynağı. Girdi aynı kalsa bile rastgele bitler değişir; bu yüzden algoritmanın izlediği yol da değişebilir.

Deterministik bir algoritmanın sabit bir girdi üzerindeki süresi tek bir sayıdır. Rastgele algoritmada ise aynı girdi için süre bir rastgele değişkendir: her çalıştırmada farklı bir değer alabilir. Bu yüzden analizde tek bir sayı yerine sürenin beklenen değeri E[T(n)] incelenir. Burada önemli bir ayrıntı vardır. Beklenen değer algoritmanın kendi yazı-turaları üzerinden alınır, girdi üzerinden alınmaz. Girdi sabittir ve en kötüsü bile olabilir; olasılık yalnız algoritmanın yaptığı rastgele seçimlerden gelir.

Bu tanım ortalama durum analiziyle karıştırılmamalıdır. Ortalama durum analizi deterministik bir algoritmaya uygulanır ve girdiler hakkında bir varsayım yapar: örneğin dizinin her sıralamasının eşit olasılıklı olduğunu varsayar. Varsayım tutmazsa sonuç da geçersiz olur. Gerçek hayatta veriler çoğu zaman sıralı ya da sıralıya yakın gelir, yani eşit olasılık varsayımı sık sık bozulur. Beklenen süre ise hiçbir girdi varsayımı yapmaz. Her girdi için ayrı ayrı geçerlidir; en kötü girdi için bile.

12.1.3Neden rastgelelik?

Rastgelelik ilk bakışta bir belirsizlik kaynağı gibi görünür. Yine de algoritma tasarımında dört önemli kazanç sağlar.

Kötü girdiye karşı koruma. Deterministik hızlı sıralama, pivotu ilk öğe seçiyorsa sıralı dizide O(n²) süreye düşer. Sıralı dizi ise uygulamada çok yaygındır. Bir saldırgan algoritmanın kurallarını biliyorsa en kötü girdiyi bilerek hazırlayabilir. Pivot rastgele seçildiğinde hiçbir girdi sürekli kötü değildir. Kötü durum ancak algoritmanın kendi seçimleri şanssız giderse ortaya çıkar ve bunun olasılığı çok küçüktür.

Basitlik. Rastgele algoritma çoğu zaman bilinen en iyi deterministik algoritmadan çok daha kısa ve anlaşılırdır. Karger'in minimum kesim algoritması birkaç satırlık bir döngüdür. Rastgele seçme algoritması da hızlı sıralamanın küçük bir değişikliğidir. Bu problemlerin deterministik çözümleri ise ya uzun ve incelikli ya da uygulamada yavaştır.

Hız. Miller–Rabin testi yüzlerce basamaklı sayıların asallığını milisaniyeler içinde belirler. Hata olasılığı istenen kadar küçültülebilir. Kriptografide anahtar üretimi bu hıza dayanır.

Örnekleme ve simetri kırma. Bazı işler rastgelelik olmadan ya çok zordur ya da imkânsızdır. Monte Carlo benzetimleri, büyük bir veriden rastgele örneklem alma ve dağıtık sistemlerde birbirinin aynısı olan süreçler arasından bir lider seçme bunlara örnektir. Aynı programı çalıştıran iki özdeş süreç deterministik kurallarla birbirinden ayrılamaz; rastgele bir sayı bu simetriyi bozar.

Bu kazançların bir bedeli vardır. Süre ya da doğruluk artık kesin değil, olasılıksal bir güvencedir. “Bu algoritma her zaman O(n log n)'dir” denemez; “beklenen süresi O(n log n)'dir” ya da “yanılma olasılığı 10⁻¹²'den küçüktür” denir. Ayrıca algoritmanın iyi bir rastgele sayı üretecine ihtiyacı vardır. Üretecin kusurları analizdeki varsayımları bozar.

12.1.4Olasılık araçları

Rastgele algoritmaların analizinde birkaç temel olasılık aracı tekrar tekrar kullanılır. Tablo 12.1 bunları özetler; ardından her biri kısa bir örnekle açıklanır.

Beklenen değer. Bir rastgele değişkenin alabileceği her değer, o değerin olasılığıyla çarpılıp toplanır. Bir zarın her yüzü 1/6 olasılıkla gelir: E[X] = (1 + 2 + 3 + 4 + 5 + 6) / 6 = 3,5. Beklenen değerin kendisi hiç gözlenmeyebilir; hiçbir zar 3,5 göstermez. Beklenen değer, çok sayıda deneme yapıldığında ortalamanın yaklaştığı değerdir.

Doğrusallık. İki rastgele değişkenin toplamının beklenen değeri, beklenen değerlerinin toplamıdır. İki zarın toplamı için 3,5 + 3,5 = 7 bulunur; 36 sonucu tek tek toplamaya gerek kalmaz. Bu kuralın en güçlü yanı bağımsızlık istememesidir. Değişkenler birbirine bağlı olsa bile kural geçerlidir. Hızlı sıralamanın analizi tam olarak bu özelliğe dayanır: karşılaştırmalar birbirinden bağımsız değildir, ama beklenen toplam yine de tek tek beklenen değerlerin toplamıdır.

Gösterge değişkeni. Bir A olayı için X_A, olay gerçekleşirse 1, gerçekleşmezse 0 değerini alır. Beklenen değeri 1 · P(A) + 0 · (1 − P(A)) = P(A)'dır. Bir şeyin kaç kez olduğu sayılacaksa her olası olay için bir gösterge yazılır, sayı göstergelerin toplamı olur, doğrusallıkla beklenen değer olasılıkların toplamına iner. Hızlı sıralamada “zᵢ ile zⱼ karşılaştırıldı mı?” sorusu böyle bir göstergedir.

Geometrik dağılım. Her denemenin başarı olasılığı p olsun ve denemeler bağımsız olsun. İlk başarıya kadar yapılan deneme sayısı X ise P(X = k) = (1 − p)ᵏ⁻¹ p'dir ve E[X] = 1/p'dir. Bu sonuç kısa bir akıl yürütmeyle de görülür. İlk deneme her durumda yapılır. p olasılıkla iş biter; 1 − p olasılıkla süreç baştan başlar ve aynı beklenen değer yeniden harcanır: E = 1 + (1 − p) E, buradan E = 1/p. Zar oyununda p = 2/9 ve beklenen atış 4,5'tir.

Bağımsız tekrar. Bir deneme en çok q olasılıkla başarısız oluyorsa, birbirinden bağımsız k denemenin hepsinin başarısız olma olasılığı en çok qᵏ'dır. q 1'den küçük olduğu sürece bu değer k ile üstel olarak azalır. Monte Carlo algoritmalarının hatası bu yolla küçültülür.

Markov eşitsizliği. Negatif değer almayan bir rastgele değişken, beklenen değerinin c katını en çok 1/c olasılıkla aşar. Gerekçesi basittir: X en az c · E[X] olduğunda beklenen değere en az c · E[X] · P(X ≥ c · E[X]) katkı yapar. Bu katkı E[X]'i aşamaz. Eşitsizlik dağılım hakkında hiçbir şey bilmeden yalnız beklenen değerle bir kuyruk sınırı verir; bu yüzden kaba ama her yerde geçerlidir.

12.2Las Vegas ve Monte Carlo

12.2.1İki tür rastgele algoritma

Rastgele algoritmalar, rastgeleliğin neyi etkilediğine göre iki gruba ayrılır. Birinci grupta sonuç her zaman doğrudur, yalnız süre şansa bağlıdır. İkinci grupta süre sınırlıdır, ama sonuç küçük bir olasılıkla yanlış olabilir. Bu gruplara kumarhaneleriyle ünlü iki şehrin adı verilmiştir.

Rastgele pivotlu hızlı sıralama bir Las Vegas algoritmasıdır. Pivot ne seçilirse seçilsin, sonunda dizi doğru sıralanır. Şanssız pivotlar yalnız işi uzatır. BogoSort da Las Vegas'tır: durduğunda dizi kesinlikle sıralıdır, ama ne zaman duracağı belli değildir. Fisher–Yates karıştırmasının durumu biraz farklıdır. Süresi her çalıştırmada tam n − 1 takastır; rastgele olan, üretilen permütasyondur. Bu algoritmada “doğru sonuç” tek bir dizi değil, istenen olasılık dağılımıdır ve bu dağılım her zaman tam olarak sağlanır. Bu yüzden o da Las Vegas grubuna konur.

Miller–Rabin testi ise Monte Carlo'dur. Tur sayısı baştan bellidir ve her tur sınırlı sayıda çarpma yapar. Ama “asal” yanıtı küçük bir olasılıkla yanlış olabilir. Karger algoritması da sabit sayıda büzme yapar ve bazen minimum olmayan bir kesim döndürür. π tahmini istenen sayıda nokta atar ve gerçek değere yalnız yaklaşır.

12.2.2Tek yönlü ve iki yönlü hata

Monte Carlo algoritmaları hatanın yönüne göre de ayrılır. Bir karar probleminde, yani yanıtı “evet” ya da “hayır” olan bir problemde, algoritma yanıtlardan yalnız birinde yanılabiliyorsa hata tek yönlüdür. Miller–Rabin bunun tipik örneğidir. Test “bileşik” derse bu kesindir, çünkü sayının asal olmadığını gösteren somut bir kanıt bulmuştur. Yalnız “asal” yanıtı yanlış olabilir. Tek yönlü hatanın büyük bir avantajı vardır: tekrarlar sonucunda tek bir “bileşik” yanıtı bile kesin karar verir.

Hata iki yönde de olabiliyorsa iki yönlüdür. π tahmini gibi sayısal benzetimler gerçek değerin hem üstünde hem altında sapabilir. Bu tür algoritmalarda hata payı örnek sayısı arttıkça küçülür, ama tek bir çalıştırmanın sonucunun hangi yönde saptığı bilinmez. Karger algoritmasının hatası da tek yönlüdür, ama yönü farklıdır: bulunan kesim hiçbir zaman minimumdan küçük olamaz, yalnız ondan büyük olabilir. Bu yüzden birkaç çalıştırmanın en küçüğü alınır.

12.2.3Hata olasılığının küçültülmesi

Monte Carlo algoritmasının hata olasılığı tek çalıştırmada büyük olabilir. Ama algoritma bağımsız rastgele seçimlerle birçok kez çalıştırılırsa hata hızla küçülür. Bu tekniğe tekrarla güçlendirme (amplification) denir.

Miller–Rabin'de bileşik bir sayı için bir turun yanılma olasılığı en çok 1/4'tür. Yirmi turda yanılma olasılığı en çok 4⁻²⁰ ≈ 9,1 · 10⁻¹³'e iner. Bu, bilgisayar donanımında kendiliğinden bir bit hatası oluşma olasılığından bile küçüktür. Şekil 12.3 sınırın tur sayısıyla nasıl düştüğünü logaritmik ölçekte gösterir: her yeni tur sınırı 4'e böler.

Karger algoritmasında tek çalıştırmanın başarı olasılığı en az 2/(n(n − 1))'dir. Bu küçük bir sayıdır; 100 düğümlü bir çizgede yaklaşık 0,0002'dir. Ama algoritma n(n − 1)/2 · ln n kez tekrarlanırsa hepsinin başarısız olma olasılığı en çok 1/n'ye iner. Başarı olasılığı küçük de olsa, sıfırdan büyük ve bilinen bir alt sınırı varsa tekrar onu istenen düzeye çıkarır.

12.2.4Türler arası dönüşüm

Las Vegas ve Monte Carlo algoritmaları birbirine dönüştürülebilir. İki dönüşüm de pratikte kullanılır.

Las Vegas'tan Monte Carlo'ya. Beklenen süresi E[T] olan bir Las Vegas algoritması, 2 · E[T] adım sonra durdurulur. Algoritma bu sürede bitmişse yanıtı doğrudur. Bitmemişse “yanıt yok” döndürülür. Markov eşitsizliğine göre P(T ≥ 2 E[T]) ≤ 1/2'dir; yani yeni algoritma en çok 1/2 olasılıkla yanıtsız kalır. Süresi artık kesin olarak sınırlıdır. Sınır c · E[T] alınırsa yanıtsız kalma olasılığı en çok 1/c'dir.

Monte Carlo'dan Las Vegas'a. Monte Carlo algoritmasının yanıtı hızlıca doğrulanabiliyorsa algoritma, doğrulanan bir yanıt bulunana kadar tekrarlanır. Örneğin bir sayıyı çarpanlarına ayırmaya çalışan rastgele bir algoritmanın bulduğu çarpanlar çarpılarak kolayca denetlenir. Tek denemenin başarı olasılığı p ise geometrik dağılımdan beklenen deneme sayısı 1/p'dir. Sonuç her zaman doğru olur, yalnız süre rastgeleleşir. p = 1/3 için beklenen tekrar 3'tür; tohumu 42 olan 100.000 denemelik benzetimde ortalama 2,994 çıktı.

12.3Karıştırma

12.3.1Problem ve doğruluk ölçütü

Bir dizinin öğelerini rastgele bir sıraya sokmak, yani karıştırmak (shuffle), sık karşılaşılan bir iştir. Kart oyunlarında deste karıştırılır, müzik çalarlar şarkı listesini karışık sırayla çalar, algoritma testlerinde rastgele sıralı test verisi üretilir. Rastgele pivotlu hızlı sıralamanın bir başka biçimi de diziyi önce karıştırıp sonra deterministik hızlı sıralamayı çalıştırmaktır.

Karıştırmanın “doğru” olması ne demektir? Zayıf bir ölçüt, her öğenin her konumda eşit olasılıkla bulunmasıdır. Güçlü ve asıl istenen ölçüt ise n öğenin n! farklı sıralamasının, yani permütasyonunun, her birinin tam 1/n! olasılıkla üretilmesidir. Böyle bir karıştırmaya düzgün karıştırma denir. Güçlü ölçüt zayıf olanı da kapsar; tersi doğru değildir. Örneğin bir yöntem [1, 2, 3] dizisini yalnız üç çevrimsel kaydırmasından birine dönüştürsün: [1, 2, 3], [2, 3, 1] ya da [3, 1, 2]. Üç sonuç eşit olasılıklı olsun. Bu yöntem her öğeyi her konuma 1/3 olasılıkla koyar. Ama altı permütasyonun üçünü hiç üretmez.

52 kartlık bir destenin permütasyon sayısı yaklaşık 8 · 10⁶⁷'dir. Bu sayı o kadar büyüktür ki iyi karıştırılmış bir destenin dizilişi büyük olasılıkla daha önce hiçbir destede görülmemiştir. Karıştırma algoritması bu dev kümeden eşit olasılıkla seçim yapmalıdır, ama permütasyonları tek tek listeleyemez. Çözüm, seçimi küçük adımlara bölmektir.

12.3.2Fisher–Yates karıştırması

Fisher–Yates karıştırması (Fisher–Yates shuffle), Knuth karıştırması olarak da anılır. Fikir şudur: dizinin son konumuna gelecek öğe, bütün öğeler arasından rastgele seçilir ve oraya yerleştirilir. Sonra sondan bir önceki konuma gelecek öğe, henüz yerleşmemiş öğeler arasından seçilir. Bu, ilk konuma kadar sürer. Her adımda bir konum kesinleşir ve bir daha değişmez.

static void karistir(int[] a) {
  for (int i = a.length - 1; i > 0; i--) {
    int j = zar.nextInt(i + 1); // 0 ≤ j ≤ i
    int t = a[i]; a[i] = a[j]; a[j] = t;
  }
}

Kodda zar, sınıfta bir kez oluşturulan paylaşılan bir java.util.Random nesnesidir. Döngü i = n − 1'den başlar ve i = 1'e kadar iner. Her turda zar.nextInt(i + 1), 0 ile i arasında (ikisi de dahil) düzgün dağılmış bir tam sayı j üretir. Sonra a[i] ile a[j] takas edilir. j = i de çıkabilir; bu durumda öğe kendisiyle takas edilir ve yerinde kalır. Bu olasılık önemlidir: bir öğenin başladığı yerde kalması da geçerli bir sonuçtur ve karıştırma bu sonucu da doğru olasılıkla üretmelidir.

Döngü i = 0 için çalışmaz. O noktada tek bir öğe kalmıştır ve seçilecek başka bir şey yoktur. Toplam n − 1 takas yapılır ve her takas sabit sürer. Süre her çalıştırmada aynıdır: Θ(n). Ek bellek O(1)'dir; karıştırma dizinin kendi içinde yapılır. Değişen, sürenin değil sonucun kendisidir. Java'nın Collections.shuffle(liste) metodu da bu algoritmayı kullanır.

İlk turda 5 öğenin her biri 1/5 olasılıkla son konuma gelebilirdi; seçilen j = 1, yani 2 değeridir. Takastan sonra a[4] = 2 kesinleşir. İkinci turda j = 3 = i çıktığı için 4 değeri yerinde kalır. Üçüncü turda üç öğe arasından a[0] = 1 seçilir ve a[2]'ye gider; eski a[2] = 3 başa geçer. Son turda yine j = i çıkar. a[0] = 3 kalan tek öğedir ve kendiliğinden yerleşir. Sonuç [3, 5, 1, 4, 2]'dir. Java ile, aynı j değerlerini döndüren bir üreteçle çalıştırılan kod da bu diziyi verir.

12.3.3Doğruluğun kanıtı

Fisher–Yates'in doğru olduğu kısa bir sayma akıl yürütmesiyle gösterilir. Algoritma i = n − 1 turunda n değerden birini, i = n − 2 turunda n − 1 değerden birini seçer. Bu böyle devam eder; son tur i = 1'de 2 değerden biri seçilir. Olası seçim dizilerinin sayısı n · (n − 1) · … · 2 = n!'dir ve her seçim dizisi eşit olasılıklıdır.

Kanıt bir şeyi açıkça gösterir: karıştırmanın düzgünlüğü, eşit olasılıklı yol sayısının permütasyon sayısına eşit olmasından gelir. Beş öğeli örnekte olası çekiliş dizisi sayısı 5 · 4 · 3 · 2 = 120 = 5!'dir; her permütasyon tam bir kez elde edilir. Sabit tohumla (new Random(42)) [1, 2, 3] dizisi 600.000 kez karıştırıldı. Altı permütasyonun her biri 99.754 ile 100.315 arasında çıktı. Beklenen değer 100.000'dir ve sapmalar bu kadar denemede beklenen rastgele dalgalanma düzeyindedir.

12.3.4Saf karıştırma yanlıdır

Karıştırmanın akla ilk gelen yazılışı şudur: her konum, dizinin herhangi bir konumuyla rastgele takas edilir. Kod kısa ve masum görünür.

// YANLI: her i için 0..n-1 arasından seç
for (int i = 0; i < n; i++) {
  int j = zar.nextInt(n);
  takas(a, i, j);
}

Bu kodda her i için j, Fisher–Yates'teki gibi daralan bir aralıktan değil, her zaman bütün dizinin aralığı olan 0..n − 1'den seçilir. Dizi her turda gerçekten karışır, ama sonuç düzgün değildir. Nedeni sayma ile görülür. n çekilişin her biri n farklı değer alabilir. Eşit olasılıklı yol sayısı nⁿ'dir. Permütasyon sayısı ise n!'dir. Her permütasyon eşit olasılıklı olsaydı her biri tam nⁿ / n! yolla üretilirdi ve bu sayı bir tam sayı olurdu.

n = 3 için 3³ = 27 yol ve 3! = 6 permütasyon vardır. 27, 6'ya bölünmez; dolayısıyla permütasyonlar eşit olasılıklı olamaz. Bu akıl yürütme n ≥ 3 için genel olarak geçerlidir. n − 1 sayısı n!'yi böler ama nⁿ ile ortak böleni yoktur; bu yüzden nⁿ / n! hiçbir zaman tam sayı olmaz.

Tablo 12.5'te 132, 213 ve 231 sonuçları beşer yolla, diğer üçü dörder yolla elde edilir. Beklenen sayılar 600.000 · 5/27 ≈ 111.111 ve 600.000 · 4/27 ≈ 88.889'dur; benzetim bu değerlere çok yakındır. Fark küçük görünebilir, ama sistematiktir: deneme sayısı arttıkça kaybolmaz, tersine daha belirgin hâle gelir. Bir kart oyununda ya da bir istatistik deneyinde bu yanlılık sonuçları bozar.

Saf karıştırma zayıf ölçütü de sağlamaz. Tablodan 3 değerinin konumları okunsun: ilk konuma gelme olasılığı (4 + 4)/27 = 8/27, ortadaki konuma 10/27, son konuma 9/27'dir. Üçü de 1/3 olmalıydı. Dört öğeli dizide durum daha da karışıktır: 4⁴ = 256 yol 24 permütasyona dağılır. 256/24 ≈ 10,67 tam sayı değildir; Java ile yapılan tam sayımda en az 8, en çok 15 yolla üretilen permütasyonlar çıktı.

12.3.5Tek karakterlik bir hata: nextInt(i)

Fisher–Yates kodunda zar.nextInt(i + 1) yerine yanlışlıkla zar.nextInt(i) yazıldığında ne olur? Bu durumda j en çok i − 1 olabilir; a[i] her zaman kendinden önceki bir öğeyle takas edilir ve hiçbir öğe yerinde kalamaz. [1, 2, 3] dizisinde i = 2 turunda j ∈ {0, 1}, i = 1 turunda ise j = 0 zorunludur. Yalnız 2 · 1 = 2 yol vardır.

İki sonucun her biri 1/2 olasılıkla çıkar. Diğer dört permütasyon, sıralı [1, 2, 3] dahil, hiç üretilmez. Bu değiştirilmiş yöntemin kendine ait bir adı vardır: Sattolo algoritması. Yalnız tek bir çevrimden oluşan (n − 1)! permütasyonu eşit olasılıkla üretir. Bazı uygulamalarda tam olarak bu istenir; örneğin her öğenin başka bir öğeye gönderildiği ve kimsenin kendine düşmediği bir döngü kurulacaksa. Ama düzgün bir karıştırma değildir. Tek bir karakterlik fark, çıktının olasılık dağılımını tamamen değiştirir.

12.4BogoSort

12.4.1Algoritma

BogoSort, sıralama algoritmaları arasında bilinen en kötü performanslılardan biridir. “Aptal sıralama” ya da permütasyon sıralaması (permutation sort) adlarıyla da anılır. Mantığı tek cümleyle anlatılır: liste sıralı olana kadar rastgele karıştırılır. Gerçek uygulamalarda kullanılmaz. Ama Las Vegas algoritmalarının ve geometrik dağılımın en sade örneğidir; bu yüzden öğreticidir.

1. Liste sıralı mı? Evet ise işlem biter.
2. Hayır ise liste rastgele karıştırılır ve birinci adıma dönülür.

static void bogoSirala(int[] a) {
  while (!siraliMi(a))
    karistir(a);        // Fisher–Yates
}
static boolean siraliMi(int[] a) {
  for (int i = 0; i + 1 < a.length; i++)
    if (a[i] > a[i + 1]) return false;
  return true;
}

siraliMi metodu komşu öğe çiftlerini soldan sağa denetler. Bir çiftte soldaki sağdakinden büyükse dizi sıralı değildir ve metot hemen false döndürür. Bütün çiftler uygunsa true döner. En kötü durumda n − 1 karşılaştırma yapar: O(n). bogoSirala ise sıralı olmayan diziyi Fisher–Yates ile karıştırır ve denetimi tekrarlar. Karıştırma için doğru bir yöntem kullanılması önemlidir; saf karıştırmayla bazı permütasyonlar daha seyrek çıkar ve analiz geçersizleşir.

12.4.2Bir çalıştırma

Bu çalıştırmada 8 karıştırma gerekti. Dört öğenin 24 permütasyonundan yalnız biri sıralıdır; beklenen karıştırma sayısı 24'tür. Bu çalıştırma beklenenden şanslı geçmiştir. Başka bir çalıştırma 3 karıştırmada da bitebilir, 80 karıştırmada da. siraliMi'nin çoğu turda ilk ya da ikinci karşılaştırmada durduğuna da dikkat edilmelidir. Rastgele bir dizide ilk çiftin ters olma olasılığı 1/2'dir; bu yüzden denetim ortalamada n − 1 karşılaştırmadan çok daha kısa sürer. Karıştırma ise her turda tam n − 1 takas yapar.

12.4.3Analiz

Öğeler farklı olsun. Fisher–Yates her permütasyonu 1/n! olasılıkla ürettiği için bir karıştırmanın sıralı çıkma olasılığı p = 1/n!'dir. Karıştırmalar birbirinden bağımsızdır. Sıralı dizi elde edilene kadar yapılan karıştırma sayısı geometrik dağılıma uyar. Beklenen değeri 1/p = n!'dir.

Her tur bir karıştırma (O(n)) ve bir denetim (O(n)) içerir. Beklenen süre bu yüzden Θ(n · n!)'dir. Kaynaklarda bu süre bazen O((n + 1)!) diye de yazılır. İki ifade aynı büyüklüktedir, çünkü (n + 1)! = (n + 1) · n!'dir ve n + 1 ile n arasında sabit bir çarpan farkı vardır.

Tablo, faktöriyel büyümenin pratikte ne anlama geldiğini gösterir. On iki öğe yarım saniyede sıralanırken on beş öğe yirmi dakikadan fazla, yirmi öğe bir insan ömrü kadar sürer. Beklenen değer formülü benzetimle de doğrulandı. Denemeler sabit tohumla (new Random(42)) ve sıralı olmayan karışık bir başlangıçtan yapıldı. Ortalama karıştırma sayıları şöyle çıktı: n = 4 için 23,9 (beklenen 24), n = 5 için 119,7 (beklenen 120), n = 6 için 714,5 (beklenen 720). Her n için 20.000 çalıştırma yapıldı.

En iyi durum. Dizi zaten sıralıysa tek bir denetim yapılır ve algoritma O(n) sürede biter.

En kötü durum. Burada bir üst sınır yoktur. k karıştırmanın hepsinin sırasız çıkma olasılığı (1 − 1/n!)ᵏ'dır. Bu sayı k büyüdükçe sıfıra yaklaşır ama hiçbir k için sıfır olmaz. Demek ki her k için en az k tur süren bir çalıştırma mümkündür. O((n + 1)!) ifadesi yalnız beklenen süre için bir sınırdır, en kötü durum için değildir. Şanssız karıştırmalar sonsuza dek sürebilir; bunun olasılığı sıfıra gider.

12.5Rastgele QuickSort

12.5.1Pivot seçimi ve etkisi

Hızlı sıralama (quick sort, QuickSort) kısaca şöyle çalışır. Diziden bir pivot öğesi seçilir. Dizi, pivottan küçük ya da eşit olanlar solda, büyük olanlar sağda kalacak biçimde parçalanır (partition) ve pivot iki grubun arasına, kalıcı yerine yerleşir. Sonra iki taraf ayrı ayrı, özyinelemeyle sıralanır. Parçalama Θ(n) sürer. Algoritmanın toplam süresi tamamen pivotun ne kadar dengeli böldüğüne bağlıdır.

Pivot her seferinde diziyi iki eşit yarıya bölerse log₂ n düzey oluşur ve süre Θ(n log n) olur. Pivot her seferinde alt dizinin en küçük ya da en büyük öğesiyse parçalardan biri boş, öteki yalnız bir eksik çıkar. Bu durumda n düzey oluşur ve süre Θ(n²)'ye çıkar. Pivot seçme kuralı bu yüzden algoritmanın en önemli tasarım kararıdır. Tablo 12.9 yaygın stratejileri karşılaştırır.

İlk ya da son öğeyi pivot seçmek en basit kuraldır, ama zaten sıralı ya da ters sıralı dizide en kötü durumu doğurur. Bu girdiler uygulamada çok sık görülür. Üçün ortancası (median-of-three) kuralı ilk, orta ve son öğenin ortancasını pivot seçer. Sıralı dizide mükemmel çalışır, ama kuralı bilen biri onu yanıltacak özel diziler hazırlayabilir. Pivot olarak alt dizinin gerçek ortancası bulunursa bölme her zaman dengelidir. Ortancayı doğrusal sürede bulan deterministik bir algoritma vardır; geliştiricilerinin baş harfleriyle BFPRT (Blum, Floyd, Pratt, Rivest, Tarjan) diye anılır. Ama sabitleri büyüktür ve uygulamada yavaş kalır.

Rastgele pivotun farkı ince ama önemlidir. Deterministik stratejilerde O(n log n), girdinin rastgele sıralı olduğu varsayımına dayanır. Rastgele pivotta beklenti algoritmanın kendi seçimleri üzerindendir; bu yüzden her girdi için geçerlidir. Yine de en kötü durum ortadan kalkmaz. Algoritma her seferinde şanssız bir pivot seçerse süre yine O(n²) olur. Değişen şey, bu durumun artık belirli bir girdiye bağlı olmaması ve olasılığının çok küçük olmasıdır. Uygulamada rastgele pivot ya da üçün ortancası tercih edilir.

12.5.2Rastgele pivotla bir çalıştırma

Rastgele pivotlu hızlı sıralama [6, 5, 3, 1, 8, 7, 2, 4] dizisinde çalıştırılsın. Bu çalıştırmada pivotlar sırasıyla 3, 1, 4, 6 ve 8 olarak seçilmiş olsun. İzlemede parçalama iki işaretçiyle yapılır. i soldan ilerler ve pivottan küçük öğeleri atlar; ilk büyük ya da eşit öğede durur. j sağdan ilerler ve pivottan büyük öğeleri atlar; ilk küçük ya da eşit öğede durur. i < j ise iki öğe takas edilir ve arama sürer. İşaretçiler karşılaştığında pivot kalıcı yerindedir. Bu yöntem Hoare'un parçalama fikrine dayanır. Pivot bu sırada kendisi de yer değiştirebilir; konumu izlenir.

İlk parçalama ayrıntılı izlensin. Pivot 3'tür ve indis 2'dedir. i, a[0] = 6'da hemen durur, çünkü 6 pivottan büyüktür. j sağdan başlar: 4 pivottan büyüktür, atlanır; a[6] = 2'de durur. 0 < 6 olduğu için 6 ile 2 takas edilir ve dizi [2, 5, 3, 1, 8, 7, 6, 4] olur. Arama sürer: i, 2'yi atlayıp a[1] = 5'te durur; j, 6, 7 ve 8'i atlayıp a[3] = 1'de durur. 5 ile 1 takas edilir: [2, 1, 3, 5, 8, 7, 6, 4]. Bir sonraki adımda i, 1'i atlayıp pivotun kendisinde (indis 2) durur; j de 5'i atlayıp yine indis 2'ye gelir. İşaretçiler karşılaşmıştır. Pivot 3 kalıcı yerindedir: solunda yalnız küçükler (2, 1), sağında yalnız büyükler var.

Bu çalıştırmada pivotlar oldukça dengeli düştü. İlk pivot 3, sekiz öğeyi 2 ve 5 öğeli iki parçaya ayırdı. Özyineleme ağacının derinliği 4'te kaldı. Pivot olarak sürekli en küçük öğe seçilseydi derinlik 7 olurdu. Bir pivotun kalıcı yeri, dizide ondan küçük öğelerin sayısına eşittir; bu, hangi parçalama yöntemi kullanılırsa kullanılsın böyledir. Örneğin 6'dan küçük beş öğe vardır, bu yüzden 6'nın yeri indis 5'tir.

12.5.3Kod ve parçalama izlemesi

Aşağıdaki kod rastgele pivotlu hızlı sıralamanın tamamıdır. Parçalama için Lomuto yöntemi kullanılır: rastgele seçilen pivot önce alt dizinin sonuna taşınır, sonra tek bir soldan sağa geçişle küçükler sola toplanır. İzlemedeki iki işaretçili yöntemle aynı işi yapar; pivotlar aynı kalıcı yerlere gider, yalnız aradaki takaslar farklıdır.

static Random zar = new Random();

static void hizliSirala(int[] a, int alt, int ust) {
  if (alt < ust) {
    int p = bol(a, alt, ust); // rastgele
    hizliSirala(a, alt, p - 1);
    hizliSirala(a, p + 1, ust);
  }
}

static int bol(int[] a, int alt, int ust) {
  int r = alt + zar.nextInt(ust - alt + 1);
  takas(a, r, ust);             // pivot sona
  int pivot = a[ust], k = alt;
  for (int i = alt; i < ust; i++)
    if (a[i] <= pivot)
      takas(a, i, k++);         // küçükleri sola
  takas(a, k, ust);             // pivot yerine
  return k;
}

hizliSirala metodu standart özyinelemeli iskelettir. Alt dizide en az iki öğe varsa bol çağrılır, dönen pivot konumunun iki yanı ayrı ayrı sıralanır. Rastgelelik yalnız bol'un ilk satırındadır: alt + zar.nextInt(ust - alt + 1) ifadesi alt ile ust arasında (ikisi dahil) düzgün dağılmış bir r indisi verir. Bu öğe a[ust] ile takas edilerek sona taşınır ve pivot olur.

Döngü değişmezi şudur: her turun başında a[alt..k − 1] pivottan küçük ya da eşit öğeleri, a[k..i − 1] ise pivottan büyük öğeleri içerir. a[i] pivottan küçük ya da eşitse a[k] ile takas edilir ve k bir artar; böylece “küçükler” bölgesi bir öğe büyür. Döngü bitince a[k], büyükler bölgesinin ilk öğesidir. Pivot onunla takas edilerek kalıcı yerine konur ve k döndürülür. bol, ust − alt karşılaştırma yapar.

Yedi karşılaştırma yapıldı ve bol 2 döndürdü. Pivot 3 yine indis 2'ye yerleşti; iki işaretçili izlemede de aynı yere gitmişti. Ama dizinin geri kalanı farklıdır: iki işaretçili yöntem [2, 1, 3, 5, 8, 7, 6, 4] üretmişti, Lomuto ise [1, 2, 3, 6, 8, 7, 5, 4] üretir. Parçalamanın sözleşmesi yalnız pivotun yerini ve iki tarafın içeriğini belirler; taraflardaki sıra yönteme göre değişir. Kod Java ile çalıştırıldı ve aynı diziyi verdi. 2000 rastgele dizide hizliSirala'nın sonucu Arrays.sort ile karşılaştırıldı ve hepsi aynı çıktı.

12.5.4En iyi, en kötü ve beklenen durum

Beklenen durum bağıntısı şöyle okunur. Rastgele pivot, alt dizinin n öğesinden her birini 1/n olasılıkla seçer. Pivot sıralı hâlde q. öğeyse (0'dan sayılarak) sol parça q, sağ parça n − 1 − q öğelidir. Bağıntı bütün q değerlerinin ortalamasını alır ve parçalamanın doğrusal maliyetini ekler. Çözümü Θ(n log n)'dir. Bu bağıntıyı doğrudan çözmek yerine karşılaştırma sayısını gösterge değişkenleriyle hesaplamak daha kolaydır.

Önce bir sezgisel gözlem yapılabilir. Pivot, sıralı hâlde ortadaki yarıya düşen öğelerden biriyse (yani ne en küçük çeyrekte ne en büyük çeyrekte ise) iki parçanın büyüğü en çok 3n/4 öğeli olur. Bu “iyi pivot” olayının olasılığı 1/2'dir. Her iyi pivot, öğenin içinde bulunduğu parçayı en az dörtte bir küçültür. Bir öğenin yolunda en çok log_4/3 n iyi pivot olabilir ve iyi pivotlar ortalama iki denemede bir gelir. Her öğe ortalama O(log n) parçalamaya katılır; toplam iş O(n log n)'dir.

En kötü durumun olasılığı. Rastgele pivotta en kötü durum için her parçalamada alt dizinin en küçük ya da en büyük öğesi seçilmelidir. k öğeli bir alt dizide bunun olasılığı 2/k'dır. Seçimler bağımsız olduğundan olasılıklar çarpılır:

P(en kötü) = (2/n) · (2/(n − 1)) · … · (2/2) = 2ⁿ⁻¹ / n!

n = 5 için bu değer 16/120 ≈ 0,133'tür; küçük dizilerde en kötü durum hiç de seyrek değildir. Python'da sabit tohumla (random.Random(42)) 200.000 kez beş öğeli dizi sıralandı. Karşılaştırma sayısının en büyük değer olan 10'a ulaştığı çalıştırmaların oranı 0,134 çıktı. n = 10 için olasılık 1,4 · 10⁻⁴'e, n = 20 için ise 2⁻¹⁹ / 20! ≈ 2 · 10⁻¹³'e düşer. Gerçek boyutlu dizilerde en kötü durum pratikte hiç görülmez.

12.5.5Beklenen karşılaştırma sayısı

Hızlı sıralamanın süresi, yaptığı karşılaştırma sayısıyla orantılıdır: parçalama döngüsünün her turu tam bir karşılaştırma yapar. Bu sayı X olsun. E[X] gösterge değişkenleri ve doğrusallıkla hesaplanır.

Öğeler sıralı hâlleriyle adlandırılsın: z₁ < z₂ < … < zₙ. Burada zᵢ, dizinin i. en küçük öğesidir; dizideki konumuyla ilgisi yoktur. Her i < j çifti için bir gösterge tanımlansın: zᵢ ile zⱼ algoritma boyunca karşılaştırılırsa Xᵢⱼ = 1, karşılaştırılmazsa 0. İki öğe en fazla bir kez karşılaştırılabilir, çünkü karşılaştırmalar yalnız pivotla yapılır ve pivot o parçalamadan sonra bir daha hiçbir alt diziye girmez. Bu yüzden X = Σ_i<j Xᵢⱼ'dir.

Teoremin iki uç sonucu ilginçtir. Sıralı hâlde komşu iki öğe, yani j = i + 1, olasılık 2/2 = 1 ile, yani her zaman karşılaştırılır. Bu doğaldır: aralarında başka öğe yoktur ve onları ayırabilecek bir pivot bulunamaz. En küçük ile en büyük öğe ise ancak ilk pivot ikisinden biriyse karşılaşır: olasılık 2/n. Python ile sekiz öğeli rastgele diziler 100.000 kez sıralandı (tohum 42). z₂–z₆ çiftinin karşılaştırılma oranı 0,399 (beklenen 0,4), z₁–z₈ çiftininki 0,251 (beklenen 0,25), komşu z₃–z₄ çiftininki tam 1 çıktı.

Doğrusallıkla beklenen karşılaştırma sayısı göstergelerin olasılıklarının toplamıdır:

E[X] = Σ_i<j 2 / (j − i + 1)

Toplam, k = j − i + 1 uzaklığına göre gruplanarak kapalı biçime getirilir. Uzaklığı k olan çift sayısı n − k + 1'dir (2 ≤ k ≤ n). Böylece

E[X] = Σ_k=2..n (n − k + 1) · 2/k = 2(n + 1)(Hₙ − 1) − 2(n − 1) = 2(n + 1)Hₙ − 4n

elde edilir. Burada Hₙ = 1 + 1/2 + … + 1/n, n. harmonik sayıdır ve yaklaşık ln n + 0,577'dir. Kaba bir üst sınır da kolayca görülür: her i için iç toplam 2(1/2 + 1/3 + …)'den küçüktür, dolayısıyla E[X] < 2n Hₙ'dir. 2n ln n = 2 ln 2 · n log₂ n olduğundan bu sınır yaklaşık 1,39 n log₂ n'dir. Rastgele pivotlu hızlı sıralama, mükemmel dengeli bölmenin n log₂ n karşılaştırmasından yalnız yaklaşık %39 fazla karşılaştırma yapar. Kapalı formülün n ≤ 30 için tam kesirli aritmetikle toplamın kendisine eşit olduğu Python ile denetlendi.

Benzetimde her seferinde sıralı bir dizi (1, 2, …, n) sıralandı. Bu, deterministik ilk öğe pivotunun en kötü girdisidir; rastgele pivot için ise sıradan bir girdidir. Ortalamalar formüle çok yakındır; küçük farklar sınırlı sayıda tekrardan gelen rastgele dalgalanmadır. Son sütun n(n − 1)/2'dir: ilk öğe sıralı dizide hep en küçük öğedir, her düzeyde parça yalnız bir küçülür. n = 1000'de fark yaklaşık 45 kattır, n = 10⁶'da ise yaklaşık 20.000 kat.

12.5.6Bellek ve tekrarlı anahtarlar

Hızlı sıralama diziyi yerinde sıralar; ek bellek yalnız özyineleme yığınıdır. Yığın derinliği özyineleme ağacının yüksekliğidir. Rastgele pivotta beklenen derinlik O(log n)'dir, ama en kötü durumda n'ye çıkabilir. Bunu önlemek için basit bir teknik vardır. Önce küçük parçaya özyinelemeyle inilir, büyük parça ise bir döngüyle işlenir. Küçük parça en çok yarı boyutta olduğu için her özyinelemeli çağrıda boyut en az yarıya iner. Yığın derinliği en kötü durumda da O(log n)'de kalır.

Dizide çok sayıda eşit anahtar varsa Lomuto parçalaması kötü davranır. Bütün öğeleri eşit bir dizide her öğe “≤ pivot” koşulunu sağlar, pivot hep sona yerleşir ve parçalardan biri hep boş kalır. Pivot rastgele olsa bile süre Θ(n²)'dir. Çözüm üç yollu parçalamadır: dizi pivottan küçükler, pivota eşitler ve pivottan büyükler olarak üçe ayrılır. Eşitler bölgesi kalıcı yerindedir ve özyinelemeye girmez.

12.6Rastgele seçme (QuickSelect)

12.6.1Problem ve kod

Seçme problemi, dizinin s. en küçük öğesini bulmaktır. Ortanca, en küçük ya da en büyük on öğenin sınırı gibi sorular bu problemin örnekleridir. Diziyi sıralayıp s. konumu okumak O(n log n) sürer. Ama sıralamanın büyük kısmı gereksizdir: yalnız tek bir öğenin yeri soruluyor. Rastgele seçme (quickselect) algoritması hızlı sıralamanın parçalamasını kullanır, ama her seferinde yalnız aranan öğenin bulunduğu tarafa iner.

static int sec(int[] a, int alt, int ust, int s) {
  if (alt == ust) return a[alt];
  int p = bol(a, alt, ust);
  if (s == p) return a[p];
  if (s < p) return sec(a, alt, p - 1, s);
  return sec(a, p + 1, ust, s);
}

s, 0 tabanlı bir sıra numarasıdır: s = 0 en küçük öğe, s = n − 1 en büyük öğedir. Metot önce taban durumunu denetler. Aralıkta tek öğe kalmışsa (alt = ust) aranan odur. Değilse aynı rastgele bol çağrılır ve pivotun kalıcı yeri p öğrenilir. Pivotun kalıcı yeri, sıralı dizideki yeridir. s = p ise aranan pivottur. s < p ise aranan öğe pivotun solundadır; s > p ise sağındadır. Hangi tarafa inilirse inilsin s değişmez, çünkü indisler dizinin tamamına göredir. Öteki taraf bir daha hiç incelenmez.

Algoritma da bir Las Vegas algoritmasıdır. Sonuç her zaman doğrudur; rastgele olan yalnız ne kadar parçalama yapılacağıdır. Bir yan etkisi de vardır: metot diziyi yerinde değiştirir. Dönüşten sonra a[s] aranan öğedir; solundakiler ondan küçük ya da eşit, sağındakiler büyüktür.

12.6.2Kod izleme

İlk çağrıda pivot 3, Lomuto parçalamasıyla indis 2'ye yerleşir. Aranan konum 5, pivotun sağındadır; bu yüzden yalnız [3, 7] aralığına inilir. Sol taraftaki iki öğe (1 ve 2) bir daha incelenmez. İkinci çağrıda pivot 7'dir; 3..7 aralığında 7'den küçük üç öğe (6, 5, 4) olduğu için 7, indis 6'ya gider. Aranan konum 5 artık pivotun solundadır. Üçüncü çağrıda üç öğelik [6, 4, 5] aralığında pivot 5 seçilir ve indis 4'e yerleşir. Son çağrıda aralıkta tek öğe kalır: alt = ust = 5. Metot a[5] = 6 döndürür ve bu değer çağrı zincirinden olduğu gibi geri gelir.

Java ile, bol'un aynı pivotları seçmesini sağlayan betikli bir üreteçle çalıştırılan kod 6 döndürdü; ara diziler de tablodakilerle aynı çıktı. Ayrıca 2000 rastgele dizide ve rastgele s değerlerinde sec'in sonucu, sıralanmış dizinin s. öğesiyle karşılaştırıldı; hepsi eşit çıktı.

12.6.3Analiz

Rastgele seçmenin beklenen süresi O(n)'dir. Hızlı sıralamadan farkı, özyinelemenin iki değil tek kola inmesidir. İyi bir pivot, yani ortadaki yarıya düşen bir pivot, aralığı en çok 3/4'üne indirir ve 1/2 olasılıkla gelir. Ortalama iki parçalamada bir aralık en az dörtte bir küçülür. Aralık boyutu n'den 3n/4'e, sonra 9n/16'ya iner. Her aşamanın beklenen maliyeti en çok iki parçalama, yani o aşamadaki boyutun iki katı kadardır. Toplam beklenen iş bir geometrik seriyle sınırlanır:

E[T(n)] ≤ 2n (1 + 3/4 + (3/4)² + …) = 2n · 4 = 8n = O(n)

Bu kaba bir sınırdır. Ortanca aranırken beklenen karşılaştırma sayısının kesin değeri yaklaşık 2(1 + ln 2) n ≈ 3,39 n'dir. Java ile ortanca 2000 kez arandı (tohum 42): n = 1001 için ortalama 3,33 n, n = 10.001 için 3,39 n karşılaştırma çıktı. Küçük n'deki fark, formüldeki düşük dereceli terimlerden gelir.

En kötü durum yine O(n²)'dir. Pivot her seferinde aralığın bir ucuna düşerse aralık her adımda yalnız bir küçülür. Parçalama zaten Θ(n) sürdüğü için O(log n) gibi bir süre ise imkânsızdır: her öğe en az bir kez okunmalıdır. Seçme için en kötü durumda da doğrusal süre isteniyorsa pivot BFPRT yöntemiyle, yani “ortancaların ortancası” ile seçilir. Uygulamada ise rastgele sürüm daha hızlıdır.

12.7Monte Carlo ile π

12.7.1Yöntem ve kod

Monte Carlo yöntemi, bir sayıyı rastgele örneklerin oranından tahmin eder. En bilinen örneği π sayısının tahminidir. Kenarı 1 olan birim kare ve merkezi karenin sol alt köşesinde, yarıçapı 1 olan çeyrek daire düşünülsün. Karenin alanı 1, çeyrek dairenin alanı π/4'tür. Kareye düzgün rastgele bir nokta atılırsa noktanın çeyrek dairenin içine düşme olasılığı alanların oranıdır: p = π/4 ≈ 0,785.

Bir nokta (x, y), ancak orijine uzaklığı en çok 1 ise çeyrek dairenin içindedir: x² + y² ≤ 1. Karekök almaya gerek yoktur. n nokta atılır ve içeri düşenler sayılır. İç nokta oranı π/4'ün tahminidir; dolayısıyla

π ≈ 4 · iç / n

olur. Yöntem iki yönlü hatalı bir Monte Carlo algoritmasıdır. Süresi tam n adımdır, ama sonucu gerçek değerin altında da üstünde de kalabilir.

static double piTahmin(int n) {
  int ic = 0;
  for (int t = 0; t < n; t++) {
    double x = zar.nextDouble(), y = zar.nextDouble();
    if (x * x + y * y <= 1) ic++;
  }
  return 4.0 * ic / n;
}

Her turda zar.nextDouble() iki kez çağrılır ve [0, 1) aralığında düzgün dağılmış iki sayı üretir. Nokta çeyrek dairedeyse ic bir artar. Döngüden sonra 4.0 * ic / n döndürülür. Buradaki 4.0 önemlidir: ifadeyi double aritmetiğine geçirir. 4 * ic / n yazılsaydı tam sayı bölmesi yapılır ve kesir kısmı atılırdı; örneğin 6 noktadan 4'ü içerideyse sonuç 2,667 yerine 2 olurdu. Metot O(n) sürede ve O(1) ek bellekle çalışır.

12.7.2Kod izleme

Sekiz noktanın altısı içeride kaldı. Metot 4.0 · 6 / 8 = 3,0 döndürür. Tahmin gerçek değerden yaklaşık 0,14 uzaktır. Bu kadar az noktayla şaşırtıcı değildir: tahminin standart sapması yaklaşık 1,64 / √8 ≈ 0,58'dir. 3,0 tahmini bu ölçüye göre oldukça iyidir. Aynı tohumla aynı kod her zaman 3,0 verir; tohum değiştirilirse başka bir sonuç çıkar.

12.7.3Hata ve nokta sayısı

Tahminin ne kadar güvenilir olduğu basit bir olasılık hesabıyla bulunur. Her nokta, p = π/4 olasılıkla 1, aksi hâlde 0 değerini alan bağımsız bir göstergedir. n göstergenin toplamı olan ic'in beklenen değeri np, varyansı np(1 − p)'dir. Tahmin 4 · ic / n olduğu için beklenen değeri tam olarak 4p = π'dir; yöntem ortalamada doğru değeri verir. Standart sapması ise

σ = 4 · √(p(1 − p) / n) = 1,642 / √n

olur. Hata, nokta sayısının karekökü ile ters orantılı azalır. Bunun pratik anlamı ağırdır: hatayı 10'da birine indirmek için nokta sayısı 100 katına çıkmalıdır. Bir ondalık basamak daha doğruluk 100 kat daha fazla iş ister.

Tablo, tek tek çalıştırmaların gürültülü olduğunu gösterir. 100 noktalık tahmin şans eseri çok iyi çıkmıştır; 1.000.000 noktalık tahmin ise 100.000 noktalıktan daha kötüdür. Bu çelişki değildir. σ, tek bir çalıştırmanın hatasını değil, hataların tipik büyüklüğünü verir. Bunu sınamak için 1.000 noktalık tahmin 2000 kez tekrarlandı (tohum 42). Hataların karelerinin ortalamasının karekökü 0,0514 çıktı; formül 0,0519 verir. Normal dağılım yaklaşımıyla hata, çalıştırmaların yaklaşık %95'inde 1,96 σ'nın altında kalır. Hatanın %95 güvenle 0,01'in altında olması için yaklaşık 104.000 nokta, 0,001'in altında olması için yaklaşık 10,4 milyon nokta gerekir.

π tahmini, π'yi hesaplamanın iyi bir yolu değildir; çok daha hızlı deterministik formüller vardır. Ama yöntemin kendisi çok değerlidir. Alanı ya da hacmi formülle hesaplanamayan karmaşık şekiller, çok boyutlu integraller, fizikte parçacık benzetimleri ve finansta risk hesapları aynı fikirle yapılır. Monte Carlo yönteminin hatası boyut sayısından bağımsız olarak 1/√n ile azalır. Yüksek boyutlu problemlerde bu özellik onu ızgara tabanlı yöntemlerden üstün kılar.

12.8Miller–Rabin asallık testi

12.8.1Fermat testi ve Carmichael sayıları

Bir sayının asal olup olmadığını anlamanın en basit yolu, √n'ye kadar bütün sayılara bölmeyi denemektir. Bu yöntem √n bölme yapar. Sayının basamak sayısına göre üstel bir süredir: 300 basamaklı bir sayı için 10¹⁵⁰ bölme gerekir. Kriptografide ise tam olarak bu büyüklükte asal sayılara ihtiyaç vardır. Asallık testi (primality test), sayıyı çarpanlarına ayırmadan asallığını sınar.

Fikir sayılar kuramından gelir. Fermat'nın küçük teoremine göre n asal ve 1 < a < n ise

aⁿ⁻¹ ≡ 1 (mod n)

olur. Bu eşitlik bir a için bozulursa n kesinlikle bileşiktir. Bu, çarpanlar bulunmadan bileşikliğin kanıtlanması demektir. Eşitlik sağlanıyorsa n “belki asal”dır. Sorun şudur: bazı bileşik sayılar, kendisiyle aralarında asal olan her taban için eşitliği sağlar. Bunlara Carmichael sayıları denir. En küçüğü 561 = 3 · 11 · 17'dir. Örneğin 2⁵⁶⁰ mod 561 = 1'dir. 561 ile aralarında asal olan bütün tabanlar, yani 1 ile 560 arasındaki 320 sayının hepsi, Fermat testini geçer. Fermat testi bu sayıları ancak ortak çarpanlı bir taban tutturarak yakalayabilir. Carmichael sayıları sonsuz tanedir.

12.8.2Karekök özelliği ve Miller–Rabin dizisi

Miller–Rabin testi, Fermat testine ikinci bir denetim ekler. Bu denetim 1'in kareköklerine dayanır. n asalsa x² ≡ 1 (mod n) denkliğinin yalnız iki çözümü vardır: x ≡ 1 ve x ≡ −1 ≡ n − 1. Gerekçesi kısadır. x² − 1 = (x − 1)(x + 1) çarpımı n'ye bölünüyorsa ve n asalsa, n çarpanlardan birini böler. Bileşik sayılarda ise 1'in başka karekökleri de olabilir. 561'de örneğin 67² = 4489 = 8 · 561 + 1'dir; 67, 1'in “gizli” bir kareköküdür.

Test şöyle kurulur. n tek bir sayı olsun. n − 1 çifttir ve n − 1 = 2ˢ · d biçiminde yazılır; burada d tektir. Rastgele bir a tabanı için şu dizi hesaplanır:

a^d,   a^2d,   a^4d,   …,   a^2s−1d   (mod n)

Her öğe bir öncekinin karesidir. Dizinin bir sonraki karesi a^2sd = aⁿ⁻¹'dir. n asalsa Fermat'ya göre bu son değer 1'dir. Diziye geriye doğru bakılırsa, 1'e ulaşan her karenin bir önceki öğesi 1'in kareköküdür; asal bir modülde bu öğe ya 1 ya da n − 1 olmak zorundadır. Sonuç olarak n asalsa dizi ya 1 ile başlar ya da bir yerde n − 1 değerini alır.

Testin gücü bir sayı kuramı sonucundan gelir. Rabin, tek bileşik bir n için 1 ile n − 1 arasındaki tabanların en çok dörtte birinin güçlü yalancı olduğunu göstermiştir. Burada bu teoremin kanıtı verilmez, ama sonucu küçük sayılarda kolayca sınanır. 3000'den küçük bütün tek bileşik sayılar için 2 ile n − 2 arasındaki tabanlar Python ile tek tek denendi. En yüksek yalancı oranı n = 1891 = 31 · 61 için 14/59 ≈ 0,237 çıktı; 1/4'ün altındadır. Taban rastgele seçilirse bileşik bir sayının bir turu geçme olasılığı en çok 1/4'tür. k bağımsız turda yanılma olasılığı en çok 4⁻ᵏ'dır.

12.8.3Kod

static boolean asalMi(long n, int k) {
  if (n < 4) return n == 2 || n == 3;
  if (n % 2 == 0) return false;
  long d = n - 1; int s = 0;     // n-1 = 2^s·d
  while (d % 2 == 0) { d /= 2; s++; }
  for (int tur = 0; tur < k; tur++) {
    long a = 2 + zar.nextLong(n - 3); // [2, n-2]
    long x = usMod(a, d, n);     // a^d mod n
    if (x == 1 || x == n - 1) continue;
    boolean tanik = true;
    for (int r = 1; r < s && tanik; r++) {
      x = x * x % n;
      if (x == n - 1) tanik = false;
    }
    if (tanik) return false;     // kesin bileşik
  }
  return true;                  // muhtemelen asal
}

İlk iki satır küçük durumları ayıklar. n < 4 ise yalnız 2 ve 3 asaldır. Çift sayılar 2 dışında bileşiktir; 2 zaten ilk satırda yakalanmıştır. Sonraki iki satır n − 1'i 2ˢ · d biçimine getirir: d çift kaldıkça ikiye bölünür ve s sayılır. Ana döngü k tur yapar. Her turda 2 + zar.nextLong(n - 3) ifadesi [2, n − 2] aralığından düzgün bir taban seçer; nextLong(n - 3) 0 ile n − 4 arasında bir değer verir. (1 ve n − 1 tabanları her sayı için testi geçtiği için işe yaramaz.)

x = usMod(a, d, n) dizinin ilk öğesidir. x 1 ya da n − 1 ise bu tur geçilir ve continue ile sonraki tura gidilir. Değilse tanik önce true yapılır; iç döngü dizinin geri kalan s − 1 öğesini ardışık karelerle hesaplar. n − 1 görünürse tanik = false olur ve iç döngü durur. İç döngü bittiğinde tanik hâlâ true ise a bir tanıktır ve metot false döndürür. Bu yanıt kesindir. Bütün turlar geçilirse metot true döndürür: sayı “muhtemelen asal”dır.

Kod iki ayrıntı içerir. Birincisi, zar.nextLong(long bound) metodu Java 17 ile eklenmiştir; daha eski sürümlerde yoktur. İkincisi, x * x % n çarpımı long türünde yapılır. x < n olduğundan çarpım n²'den küçüktür. long'un en büyük değeri yaklaşık 9,22 · 10¹⁸'dir; karekökü 3.037.000.499'dur. Kod bu yüzden yalnız n < 3 · 10⁹ için güvenlidir. Daha büyük sayılar için BigInteger.modPow ya da doğrudan BigInteger.isProbablePrime kullanılır.

12.8.4Hızlı modüler üs alma

a^d mod n değerini a'yı d − 1 kez kendisiyle çarparak hesaplamak, büyük d'lerde imkânsızdır. Kare al-çarp yöntemi üssün ikili gösteriminden yararlanır. Üs ikili tabanda yazılır; her adımda taban karesi alınarak bir sonraki ikinin kuvvetine çıkarılır. Üssün o biti 1 ise o kuvvet sonuca katılır.

static long usMod(long a, long d, long n) {
  long sonuc = 1;
  a %= n;
  while (d > 0) {
    if ((d & 1) == 1)          // bit 1 ise
      sonuc = sonuc * a % n;
    a = a * a % n;             // kare al
    d >>= 1;                   // sonraki bit
  }
  return sonuc;
}

Döngü değişmezi şudur: her turun başında sonuc · a^d, aranan değere (mod n) eşittir. Bit 1 ise a sonuca çarpılır ve d'nin o biti tüketilir. Sonra a'nın karesi alınır ve d bir bit sağa kaydırılır, yani ikiye bölünür. d = 0 olduğunda değişmez sonuc'un aranan değer olduğunu söyler. Döngü d'nin bit sayısı kadar, yani ⌊log₂ d⌋ + 1 kez döner. Her turda en çok iki modüler çarpma yapılır: süre O(log d) çarpmadır.

Döngü d = 0 olunca biter ve 263 döner: 2³⁵ mod 561 = 263. Tabloda a sütunu sırasıyla 2¹, 2², 2⁴, 2⁸, 2¹⁶, 2³² değerlerini (mod 561) taşır. Bit 1 olan turlarda 2¹, 2² ve 2³² sonuca katılır ve 2¹ · 2² · 2³² = 2³⁵ elde edilir. Toplam 6 kare ve 3 çarpma yapıldı; düz çarpmayla 34 çarpma gerekirdi. Fark küçük üslerde önemsiz görünür. 300 basamaklı bir üste ise yaklaşık 1000 kare yeterken düz yöntem 10³⁰⁰ civarında çarpma ister. Son turdaki a = 511 değeri hesaplanır ama kullanılmaz.

12.8.5561 sayısının izlemesi

Dizi 263, 166, 67, 1'dir ve 560'a hiç ulaşmaz. Metot false döndürür: 561 kesin bileşiktir. Dizinin son adımı özellikle öğreticidir. 67² ≡ 1'dir ama 67 ne 1 ne de 560'tır. Asal bir modülde böyle bir karekök olamaz; bu yüzden 67 bileşikliğin somut kanıtıdır. Dizinin bir kare daha ilerisi 2⁵⁶⁰ ≡ 1'dir. Fermat testi yalnız bu son değere baktığı için aldanır. Miller–Rabin ise 1'e nasıl ulaşıldığına bakar ve aldanmaz.

12.8.6Örnekler ve güçlü yalancılar

61 asaldır. 2¹⁵ = 32.768 = 537 · 61 + 11, yani dizi 11 ile başlar. Karesi 121 = 61 + 60, yani 60'tır ve bu n − 1'dir. Dizi n − 1'e ulaştığı için tur geçilir. Asal bir sayı her turu geçer; Miller–Rabin asal bir sayıya hiçbir zaman “bileşik” demez.

221 = 13 · 17 bileşiktir. a = 174 için dizi 47 ile başlar; 47² = 2209 = 9 · 221 + 220, yani 220'dir ve bu n − 1'dir. 174 bir güçlü yalancıdır: bileşik 221'i bu turda asal gibi gösterir. a = 137 için dizi 188 ve 205'tir; 220 görünmez ve 137 bir tanık olur. asalMi(221, 2) bu iki tabanla çağrılırsa ilk tur geçilir, ikinci tur false döndürür. Tek tur yetseydi ve yalnız 174 çekilseydi yanıt yanlış olarak “asal” olurdu. Birden çok tur bu yüzden gerekir. 221'in 2 ile 219 arasındaki 218 tabanından yalnız dördü (21, 47, 174, 200) güçlü yalancıdır. Tek turun yanılma olasılığı 4/218 ≈ 0,018'dir. Python'da sabit tohumla 100.000 rastgele taban denendi; oran 0,0185 çıktı.

25 = 5² için n − 1 = 24 = 2³ · 3'tür. a = 7'de 7³ = 343 ≡ 18 ve 18² = 324 ≡ 24 = n − 1'dir; 7, 25 için güçlü yalancıdır. 25'in 22 tabanından yalnız ikisi (7 ve 18) yalancıdır. a = 2'de dizi 8, 14, 21'dir; 24 hiç görünmez ve sayı bileşik bulunur.

Bu örnekler Rabin sınırının çoğu sayıda çok kötümser olduğunu gösterir. 561'in 558 tabanından yalnız 8'i, 221'in 218 tabanından 4'ü güçlü yalancıdır. Sınıra en çok yaklaşan sayılar bile 1/4'ü geçmez. Yani gerçek hata olasılığı çoğu zaman 4⁻ᵏ'dan da küçüktür; 4⁻ᵏ en kötü durum için bir güvencedir.

12.8.7Hata, maliyet ve taşma

Miller–Rabin tek yönlü hatalı bir Monte Carlo algoritmasıdır. “Bileşik” yanıtı kesindir, çünkü bir tanık bulunmuştur. “Asal” yanıtı yalnız muhtemelen doğrudur ve k turda yanılma olasılığı en çok 4⁻ᵏ'dır. Asal bir sayı için yanıt her zaman doğrudur. Yanılma yalnız bileşik bir sayıya “asal” denmesi biçiminde olabilir.

Bir tur, bir modüler üs alma ve en çok s − 1 kare alma yapar. İkisi birlikte O(log n) modüler çarpmadır. b bitlik sayılar için okul yöntemiyle bir çarpma O(b²) bit işlemi sürer. b = log n olduğundan bir tur O(log³ n), k tur O(k log³ n) bit işlemidir. Bu, sayının basamak sayısına göre polinom bir süredir. Deneme bölmesinin üstel süresiyle karşılaştırıldığında aradaki fark çok büyüktür.

Kod Java ile denendi. new Random(42) tohumlu üreteçle 2 ile 200.000 arasındaki her sayı için asalMi(n, 20), BigInteger.isProbablePrime ile karşılaştırıldı; yanlış yanıt çıkmadı. Aynı aralıkta tek turla (k = 1) ise 46 bileşik sayı yanlışlıkla “asal” bulundu. 1.000.000.007, 2³¹ − 1 = 2.147.483.647 ve 2.999.999.929 sayıları 20 turla asal bulundu; BigInteger da aynı sonucu verir.

12.9Karger minimum kesim algoritması

12.9.1Minimum kesim problemi

Yönsüz ve bağlı bir çizge düşünülsün. Çizgenin düğümleri boş olmayan iki gruba ayrılsın. İki grup arasında kalan, yani bir ucu bir grupta öbür ucu öteki grupta olan kenarlar bir kesimdir. Bu kenarlar silinirse çizge iki parçaya kopar. Minimum kesim (minimum cut) problemi, en az kenarlı kesimi bulmaktır. Bu sayı, çizgenin bağlantısını koparmak için silinmesi gereken en az kenar sayısıdır; ağ güvenilirliğinin bir ölçüsüdür. Bilgisayar ağlarında, devre tasarımında ve görüntüleri bölgelere ayırmada kullanılır.

Bu problem ağ akışındaki s–t kesiminden farklıdır. Orada iki özel düğüm verilir ve yalnız onları ayıran kesimler aranır. Burada ise hangi düğümlerin ayrılacağı serbesttir. Deterministik olarak çözmek mümkündür: bir düğüm sabitlenip öteki her düğümle bir s–t maksimum akış problemi çözülebilir. Ama bu, n − 1 akış hesabı demektir ve hem uzun hem karmaşık bir koddur. Karger'in 1993'te verdiği algoritma ise birkaç satırlık bir döngüden ibarettir.

12.9.2Kenar büzme

Algoritmanın tek işlemi kenar büzmedir. Bir (u, v) kenarı büzülünce u ile v tek bir “süper düğümde” birleşir. Aralarındaki kenarlar artık bir düğümden kendisine giden öz-döngülere dönüşür ve silinir. u'dan ya da v'den başka düğümlere giden kenarlar süper düğüme bağlanır. Aynı iki süper düğüm arasında birden çok kenar oluşursa hepsi korunur; çizge bir çoklu çizgeye dönüşür. Bu paralel kenarlar önemlidir, çünkü her biri kesimde ayrı bir kenar olarak sayılır.

Algoritma şöyledir: çizgede iki süper düğüm kalana kadar, kalan kenarlar arasından düzgün rastgele bir kenar seçilir ve büzülür. Sonunda kalan iki süper düğüm, düğümlerin iki gruba ayrılışını verir; aralarında kalan kenar sayısı bir kesimdir. Algoritma her zaman tam n − 2 büzme yapar. Sonucu ise bazen minimum değildir. Bu yüzden Monte Carlo algoritmasıdır.

İlk büzmeden sonra {0, 2} süper düğümü ile 1 arasında iki paralel kenar oluşur: eski (0, 1) ve (1, 2). Üçüncü büzmeden sonra {0, 2} ile {1, 5} arasında üç paralel kenar vardır: (0, 1), (1, 2) ve (0, 5). Dördüncü adımda bunlardan biri, (0, 1), seçilir. Üç kenar birden öz-döngü olur ve silinir. İki süper düğüm kalır: {0, 1, 2, 5} ve {3, 4}. Aralarında (2, 3) ve (4, 5) kenarları vardır. Bulunan kesim 2'dir; bu çalıştırma başarılıdır.

Başka bir rastgele seçim dizisi başka bir sonuç verir. Algoritma önce (1, 2), sonra (4, 5), (3, 4) ve (0, 1) kenarlarını seçsin. Bu kez süper düğümler {0, 1, 2} ve {3, 4, 5} olur. Aralarında (2, 3), (0, 5) ve (1, 5) kenarları kalır: kesim 3'tür ve minimum değildir. Hata, minimum kesimin bir kenarı olan (4, 5)'in büzülmesinden doğdu. Bir minimum kesim kenarı büzülünce o kesimin iki tarafı birleşir ve bu kesim artık bulunamaz.

12.9.3Kod

Sunumda bu algoritmanın kodu verilmez. Aşağıdaki kısa sürüm, algoritmanın tamamını bir kenar listesi üzerinde gösterir. Süper düğümler bir grup dizisiyle izlenir: her düğüm bir “temsilci” düğüme bağlıdır ve kok metodu bu bağları izleyerek temsilciyi bulur. İki düğümün temsilcisi aynıysa aynı süper düğümdedirler.

static int kargerKesim(int n, int[][] kenar) {
  int[] grup = new int[n];             // grup[v]: v'nin bağlı olduğu düğüm
  for (int v = 0; v < n; v++) grup[v] = v;
  int kalan = n;                       // süper düğüm sayısı
  while (kalan > 2) {
    int[] e = kenar[zar.nextInt(kenar.length)];
    int g1 = kok(grup, e[0]), g2 = kok(grup, e[1]);
    if (g1 == g2) continue;            // öz-döngü: yeniden çek
    grup[g1] = g2;                     // kenarı büz
    kalan--;
  }
  int kesim = 0;
  for (int[] e : kenar)
    if (kok(grup, e[0]) != kok(grup, e[1])) kesim++;
  return kesim;
}
static int kok(int[] grup, int v) {
  while (grup[v] != v) v = grup[v];
  return v;
}

Döngü, kenar listesinden düzgün rastgele bir kenar çeker. Kenarın iki ucu zaten aynı süper düğümdeyse bu kenar bir öz-döngüdür; atlanır ve yeniden çekilir. Değilse iki grup birleştirilir ve süper düğüm sayısı bir azalır. Bu “yeniden çekme” yöntemi doğru dağılımı verir. Öz-döngü olmayan her kenar aynı olasılıkla seçilir ve iki süper düğüm arasındaki paralel kenarlar ayrı ayrı sayılır. Bu, algoritmanın tanımındaki seçimle aynıdır. İki süper düğüm kalınca kenar listesi bir kez taranır ve iki ucu farklı gruplarda olan kenarlar sayılır.

static int kargerTekrar(int n, int[][] kenar, int T) {
  int enIyi = Integer.MAX_VALUE;
  for (int t = 0; t < T; t++)
    enIyi = Math.min(enIyi, kargerKesim(n, kenar));
  return enIyi;
}

kargerTekrar, algoritmayı T kez bağımsız olarak çalıştırır ve bulunan en küçük kesimi döndürür. Karger'in hatası tek yönlüdür: bulunan kesim minimumdan hiçbir zaman küçük olamaz. Bu yüzden en küçük sonucu almak doğrudur. Kod okunaklı olsun diye yazılmıştır, hızlı olsun diye değil. Basit uygulamalarda tek çalıştırma O(n²) sürer.

Kod Java ile örnek çizgede denendi. Betikli bir üreteçle (0, 2), (1, 5), (3, 4), (0, 1) sırası verildiğinde 2; (1, 2), (4, 5), (3, 4), (0, 1) sırası verildiğinde 3 döndü. Sonra zar = new Random(42) ile 200.000 bağımsız çalıştırma yapıldı. 91.392 çalıştırma 2, 88.725 çalıştırma 3, 19.883 çalıştırma 4 kenarlı bir kesim buldu. Başarı oranı 0,457'dir.

12.9.4Başarı olasılığı

n = 6 için alt sınır 2/30 = 1/15 ≈ 0,067'dir. Örnek çizgede gerçek başarı olasılığı bundan çok yüksektir. Python ile bütün büzme dizileri kesirli aritmetikle tek tek hesaplandı: herhangi bir minimum kesimin bulunma olasılığı tam 16/35 ≈ 0,457'dir. Benzetimdeki 0,457 ile uyumludur. Farkın iki nedeni vardır. Birincisi, çizgede üç minimum kesim vardır ve herhangi birinin bulunması başarı sayılır. İkincisi, kanıttaki “her düğümün derecesi en az c” sınırı bu çizgede gevşektir: dereceler 2 ile 3 arasındadır.

Teoremin ilginç bir yan sonucu vardır. Farklı minimum kesimlerin bulunma olayları birbirini dışlar ve her birinin olasılığı en az 2/(n(n − 1))'dir. Olasılıkların toplamı 1'i aşamayacağı için bir çizgede en çok n(n − 1)/2 farklı minimum kesim olabilir. Bu sınır sıkıdır: n düğümlü bir döngü çizgesinde iki kenarın her seçimi bir minimum kesim verir ve tam n(n − 1)/2 minimum kesim vardır. Altı düğümlü döngüde Karger her çalıştırmada bir minimum kesim bulur, ama belirli bir kesimi yalnız 1/15 olasılıkla bulur.

12.9.5Tekrarla güçlendirme

Tek çalıştırmanın başarı olasılığı p ≥ 2/(n(n − 1)) küçüktür. Algoritma T kez bağımsız çalıştırılıp en küçük sonuç alınırsa, hepsinin başarısız olma olasılığı en çok (1 − p)ᵀ'dir. 1 − x ≤ e⁻ˣ eşitsizliği kullanılırsa

(1 − 2/(n(n − 1)))ᵀ ≤ e^{−2T/(n(n − 1))}

bulunur. T = n(n − 1)/2 · ln n seçilirse sağ taraf e^{−ln n} = 1/n olur. Toplam süre O(n² log n) çalıştırma × O(n²) = O(n⁴ log n)'dir. Bu basit bir uygulamanın süresidir. Karger ve Stein'ın geliştirdiği özyinelemeli sürüm, büzmenin ilk adımlarının güvenli, son adımlarının riskli olduğu gözleminden yararlanır ve süreyi O(n² log³ n)'ye indirir.

Bu sınırlar en kötü çizgeler içindir. Örnek çizgede gerçek başarı 16/35 olduğundan 27 tekrarın hepsinin başarısız olma olasılığı (19/35)²⁷ ≈ 6,9 · 10⁻⁸'dir. Java'da kargerTekrar(6, G, 27) 20.000 kez çağrıldı (tohum 42) ve her seferinde 2 döndü. Yalnız 3 tekrarla başarı oranı 0,836 çıktı; kesin değer 1 − (19/35)³ ≈ 0,840'tır.

12.10Diğer uygulamalar

Rastgelelik algoritma tasarımının birçok alanında kullanılır. Aşağıdaki örnekler bunlardan birkaçıdır.

Çizge boyama. Farklı boyama düzenleri rastgele kararlarla denenir. Amaç, komşu düğümlere aynı rengi vermeden az renkli iyi boyamalar bulmaktır. Rastgele bir başlangıçtan yapılan yerel iyileştirmeler, deterministik bir sıranın takıldığı kötü çözümlerden kurtulmayı sağlar.

Rastgele derinlik öncelikli arama. Komşular rastgele bir sırayla gezilir. Bağlantılılık ve kapsayan ağaç gibi sonuçlar değişmez, ama elde edilen ağaç her seferinde farklıdır. Labirent üretimi bu fikre dayanır: bir ızgaranın rastgele kapsayan ağacı, her hücreden her hücreye tek yolu olan bir labirenttir.

Eşleştirme. Rastgele artımlı algoritmalar kenarları rastgele bir sırayla ele alır ve en büyük eşleşmeye yaklaşan çözümler üretir. Rastgele sıra, kötü bir girdi sırasının algoritmayı yanıltmasını önler.

Yaklaşık sayma. Count-Min Sketch gibi veri yapıları rastgele seçilmiş hash fonksiyonlarıyla çalışır. Çok büyük bir veri akışında her öğenin kaç kez geçtiğini, küçük bir bellekle ve denetimli bir hatayla tahmin eder.

Matris işlemleri. Rastgele matris yöntemleri, büyük bir matrisin düşük ranklı yaklaşımlarını hızla üretir. Boyut indirgeme ve veri sıkıştırma bu yaklaşımları kullanır.

Hesaplamalı geometri. Dışbükey örtü, en yakın nokta çifti ve Delaunay üçgenlemesi için rastgele artımlı algoritmalar vardır. Noktalar rastgele bir sırayla eklenir ve beklenen süre O(n log n) olur.

Rastgele zamanlama (iş atama), benzetimli tavlama ve genetik algoritmalar gibi üst sezgisel yöntemler de aramada rastgelelikten yararlanır. Bu yöntemler büyük arama uzaylarında iyi çözümler bulur, ama optimuma ulaşacaklarını garanti etmez. Bu yönüyle Las Vegas ve Monte Carlo algoritmalarından ayrılır: onların doğruluğu ya da hata olasılığı kanıtlanmış bir sınırla verilir.

12.11Sözde rastgele sayılar

Notta sürekli “rastgele bir sayı seçilir” dendi. Ama bilgisayar deterministik bir makinedir; gerçek rastgelelik üretmez. Programlar bunun yerine sözde rastgele sayılar (pseudo-random number) kullanır. Bunlar deterministik bir formülle üretilen, ama istatistiksel testlerde rastgele gibi davranan sayılardır. Formülün başlangıç değerine tohum (seed) denir.

En eski ve en basit yöntem doğrusal eşlik üretecidir (linear congruential generator, LCG):

Xₖ₊₁ = (a · Xₖ + c) mod m

java.util.Random bir LCG'dir. Parametreleri a = 25.214.903.917, c = 11 ve m = 2⁴⁸'dir. Sınıf, örnekteki zayıflık nedeniyle 48 bitlik durumun yalnız üst bitlerini çıktı olarak kullanır. Böyle bir üreteç algoritma deneyleri ve benzetimler için yeterlidir. Ama birkaç ardışık çıktısından iç durumu hesaplanabilir ve sonraki bütün sayılar öngörülebilir.

Aynı tohum her zaman aynı diziyi verir. Bu bir zayıflık değil, değerli bir özelliktir. new Random(42) ile başlayan bir program her çalıştırmada aynı “rastgele” kararları verir. Hata ayıklamada bir hatanın yeniden üretilmesi, deneylerin tekrarlanabilmesi ve testlerin her seferinde aynı sonucu vermesi bu sayede sağlanır. Bu notun bütün benzetimleri de sabit tohumla yapılmıştır. π izlemesindeki sekiz nokta new Random(2024) ile her seferinde yeniden elde edilir.

Amaca göre farklı üreteçler kullanılır. Kriptografide, yani anahtar, parola ya da oturum belirteci üretirken öngörülemezlik şarttır; bunun için java.security.SecureRandom kullanılır. Çok iş parçacıklı programlarda tek bir Random nesnesini paylaşmak iş parçacıklarını birbirine bekletir; ThreadLocalRandom.current() her iş parçacığına kendi üretecini verir.

Tablodaki ikinci satır rastgele pivot seçiminde kullanılan kalıptır. Aralıkta ust − alt + 1 değer vardır; nextInt'e bu sayı verilir ve sonuç alt kadar kaydırılır. + 1 unutulursa ust hiç seçilmez. Bu, Fisher–Yates'teki nextInt(i) hatasının aynısıdır.

12.12Sık yapılan hatalar

Rastgele algoritmalardaki hatalar çoğu zaman derleme hatası vermez ve tek bir çalıştırmada da görünmez. Program çalışır, makul görünen sonuçlar üretir, ama olasılık dağılımı ya da analiz yanlıştır. Aşağıdaki liste not boyunca karşılaşılan hataları toplar.

12.13Özet

• Rastgele algoritma girdiye ek olarak rastgele bitler kullanır. Süre ve bazen çıktı bir rastgele değişkendir. Beklenen süre, her girdi için algoritmanın kendi seçimleri üzerinden alınır.
• Analizin temel araçları beklenen değerin doğrusallığı, gösterge değişkenleri, geometrik dağılım (1/p deneme), bağımsız tekrar (qᵏ) ve Markov eşitsizliğidir.
• Las Vegas algoritması her zaman doğrudur, süresi rastgeledir. Monte Carlo algoritmasının süresi sınırlıdır, yanıtı küçük bir olasılıkla yanlıştır. Doğrulanabilir yanıtlı Monte Carlo, tekrarla Las Vegas'a; Las Vegas, Markov eşitsizliğiyle Monte Carlo'ya çevrilir.

• Bir algoritmanın hata olasılığı, bağımsız tekrarlarla üstel hızla küçültülür. Tek yönlü hatada tek bir kesin yanıt yeterlidir; Karger'de en küçük sonuç alınır.
• Bilgisayarın ürettiği sayılar sözde rastgeledir. Sabit tohum deneyleri tekrarlanabilir kılar; kriptografide SecureRandom gerekir.

12.14Kavram listesi

• rastgele algoritma randomized algorithm
• beklenen değer expected value
• beklenen çalışma süresi expected running time
• ortalama durum average case
• gösterge değişkeni indicator random variable
• geometrik dağılım geometric distribution
• Markov eşitsizliği Markov's inequality
• Las Vegas algoritması Las Vegas algorithm
• Monte Carlo algoritması Monte Carlo algorithm
• tekrarla güçlendirme amplification
• Fisher–Yates karıştırma Fisher–Yates shuffle
• pivot pivot
• parçalama partition
• rastgele seçme (QuickSelect) quickselect
• asallık testi primality test
• tanık, güçlü yalancı witness, strong liar
• Carmichael sayısı Carmichael number
• minimum kesim minimum cut
• kenar büzme edge contraction
• sözde rastgele sayı pseudo-random number
• tohum seed

12.15Kendini Dene

1. Fisher–Yates karıştırması [1, 2, 3, 4, 5, 6] dizisine uygulanıyor. i = 5, 4, 3, 2, 1 için çekilen j değerleri sırasıyla 2, 4, 0, 1, 0'dır. Her adımdan sonra dizi nedir?

   Cevap

   i = 5, j = 2: [1, 2, 6, 4, 5, 3]. i = 4, j = 4: değişmez. i = 3, j = 0: [4, 2, 6, 1, 5, 3]. i = 2, j = 1: [4, 6, 2, 1, 5, 3]. i = 1, j = 0: [6, 4, 2, 1, 5, 3]. Beş takas yapıldı; ikisi öğeyi yerinde bıraktı.

2. Saf karıştırma beş öğeli bir diziye uygulanırsa kaç eşit olasılıklı yol vardır? Sonucun düzgün olamayacağı nereden anlaşılır? Fisher–Yates'te yol sayısı kaçtır?

   Cevap

   5⁵ = 3125 yol ve 5! = 120 permütasyon vardır. 3125 / 120 ≈ 26,04 tam sayı değildir; 3125 tek, 120 çifttir. Permütasyonlar eşit sayıda yolla üretilemez. Fisher–Yates'te 5 · 4 · 3 · 2 = 120 yol vardır ve her permütasyon tam bir kez elde edilir.

3. Sekiz farklı öğeli bir dizide BogoSort'un beklenen karıştırma sayısı kaçtır? Algoritmanın bu kadar karıştırmadan sonra hâlâ bitmemiş olma olasılığı yaklaşık kaçtır?

   Cevap

   8! = 40.320 karıştırma. Bitmemiş olma olasılığı (1 − 1/40.320)⁴⁰³²⁰ ≈ e⁻¹ ≈ 0,368'dir. Geometrik dağılımda beklenen değere kadar bitmeme olasılığı büyük n'lerde yaklaşık 1/e'dir.

4. a = [9, 4, 7, 1, 6, 3, 8] için bol(a, 0, 6) çağrılıyor ve zar.nextInt(7) 4 döndürüyor. Parçalamadan sonra dizi, dönüş değeri ve karşılaştırma sayısı nedir?

   Cevap

   Pivot a[4] = 6'dır ve sona taşınır: [9, 4, 7, 1, 8, 3, 6]. 4, 1 ve 3 sırayla sola alınır: [4, 9, 7, 1, 8, 3, 6], [4, 1, 7, 9, 8, 3, 6], [4, 1, 3, 9, 8, 7, 6]. Pivot k = 3'e yerleşir: [4, 1, 3, 6, 8, 7, 9]. Dönüş 3, karşılaştırma sayısı ust − alt = 6'dır.

5. Rastgele pivotlu hızlı sıralamada 10 öğeli bir dizide z₃ ile z₇ hangi olasılıkla karşılaştırılır? Beş öğeli bir dizide beklenen karşılaştırma sayısı kaçtır?

   Cevap

   {z₃, …, z₇} kümesinde 5 öğe vardır; ilk pivot z₃ ya da z₇ olmalıdır: 2/5. Olasılık dizinin boyutuna bağlı değildir. Beş öğe için H₅ = 137/60 ve E[X] = 2 · 6 · 137/60 − 20 = 7,4'tür. En kötü durum 5 · 4/2 = 10 karşılaştırmadır.

6. Monte Carlo yöntemiyle 10.000 noktadan 7.860'ı çeyrek dairenin içine düştü. π tahmini nedir? Bu nokta sayısında tahminin standart sapması yaklaşık kaçtır?

   Cevap

   4 · 7.860 / 10.000 = 3,144. Standart sapma 1,642 / √10.000 ≈ 0,016'dır. Gerçek hata |3,144 − π| ≈ 0,0024'tür; tipik hatadan küçüktür.

7. n = 91 ve a = 3 için Fermat testi ne söyler? Miller–Rabin aynı tabanla ne söyler?

   Cevap

   3⁹⁰ ≡ 1 (mod 91) olduğundan Fermat testi geçilir; 3, 91 için bir Fermat yalancısıdır. Miller–Rabin'de 90 = 2¹ · 45, yani s = 1, d = 45'tir. 3⁴⁵ ≡ 27 (mod 91); 27 ne 1 ne de 90'dır ve s = 1 olduğu için başka kare alınmaz. 3 bir tanıktır: 91 = 7 · 13 kesin bileşiktir.

8. usMod(3, 13, 17) çağrısında her turdan sonra sonuc ve a nedir? Dönüş değeri kaçtır?

   Cevap

   13 = 1101₂. Bit 1: sonuc = 3, a = 9. Bit 0: sonuc = 3, a = 81 mod 17 = 13. Bit 1: sonuc = 39 mod 17 = 5, a = 169 mod 17 = 16. Bit 1: sonuc = 80 mod 17 = 12, a = 256 mod 17 = 1. Dönüş 12'dir: 3¹³ mod 17 = 12.

9. Sekiz düğümlü bir çizgede Karger algoritmasının tek çalıştırması için başarı alt sınırı nedir? Başarısızlık olasılığını 1/8'in altına indirmek için üstel sınırla kaç tekrar yeter? Kesin hesap kaç tekrar verir?

   Cevap

   Alt sınır 2/(8 · 7) = 1/28'dir. e^−T/28 ≤ 1/8 için T ≥ 28 ln 8 ≈ 58,2, yani 59 tekrar. Doğrudan (27/28)ᵀ ≤ 1/8 çözülürse T ≥ ln 8 / ln(28/27) ≈ 57,2, yani 58 tekrar yeter.

10. Beklenen süresi 100 ms olan bir Las Vegas algoritması 300 ms sonra durduruluyor. Yanıtsız kalma olasılığı için ne söylenebilir? Algoritma bu kuralla en çok beş kez bağımsız olarak yeniden başlatılırsa hiç yanıt alınamama olasılığı en çok kaçtır?

    Cevap

    Markov eşitsizliğine göre P(T ≥ 300) ≤ 100/300 = 1/3'tür. Beş bağımsız denemenin hepsinin yanıtsız kalma olasılığı en çok (1/3)⁵ ≈ 0,0041'dir. Toplam süre en çok 1,5 saniyedir; bu yeni algoritma bir Monte Carlo algoritmasıdır.

12.16İleri okuma

• R. Motwani ve P. Raghavan, Randomized Algorithms (1995): rastgele algoritmaların klasik başvuru kitabıdır; Las Vegas ve Monte Carlo türlerini, Karger algoritmasını ve asallık testlerini kanıtlarıyla işler.
• M. Mitzenmacher ve E. Upfal, Probability and Computing (2. baskı, 2017): gösterge değişkenleri, Markov ve Chernoff sınırları gibi olasılık araçlarını algoritma örnekleri üzerinden öğretir.
• T. H. Cormen, C. E. Leiserson, R. L. Rivest ve C. Stein, Introduction to Algorithms (4. baskı, 2022), Bölüm 5, 7 ve 9: olasılıksal analiz, rastgele pivotlu hızlı sıralamanın ayrıntılı analizi ve beklenen doğrusal süreli seçme.
• D. E. Knuth, The Art of Computer Programming, Cilt 2 (3. baskı, 1997): sözde rastgele sayı üreteçlerini, doğrusal eşlik üreteçlerinin kuramını ve karıştırma algoritmasını ayrıntılı inceler.

12.17Kaynaklar

1. R. Motwani, P. Raghavan, Randomized Algorithms, Cambridge University Press, 1995.
2. M. Mitzenmacher, E. Upfal, Probability and Computing, 2. baskı, Cambridge University Press, 2017.
3. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 4. baskı, MIT Press, 2022 (Bölüm 5, 7, 9, 31).
4. C. A. R. Hoare, “Quicksort”, The Computer Journal 5(1), 1962.
5. M. O. Rabin, “Probabilistic Algorithm for Testing Primality”, Journal of Number Theory 12(1), 1980.
6. D. R. Karger, “Global Min-cuts in RNC, and Other Ramifications of a Simple Min-Cut Algorithm”, SODA, 1993.
7. D. E. Knuth, The Art of Computer Programming, Cilt 2: Seminumerical Algorithms, 3. baskı, Addison-Wesley, 1997 (Bölüm 3.4.2: karıştırma).

İlgili sayfalar: Bölüm 12 sunumu · Çalışma soruları · Terim sözlüğü · © Sercan Külcü. Tüm hakları saklıdır.