Rastgele Algoritmalar
Rastgele algoritmalar, yürütme sırasında rastgele seçimler yaparak verimlilik, basitlik veya sağlamlık elde etmektedir. Bu algoritmaların performansı ve doğruluğu, en kötü durum kesinlikleri yerine olasılıksal garantiler olarak ifade edilmektedir.
Tanım
Rastgele bir algoritma, kararlarının bir kısmını almak için rastgele bit kaynaklarını kullanan bir algoritmadır; böylece çalışma süresi, çıktısı veya her ikisi de beklenti veya olasılık dağılımı ile analiz edilen rastgele değişkenler olmaktadır.
Kapsam
Bu kapsam, rastgeleliği bir hesaplama kaynağı olarak kullanan algoritmaları ele almaktadır: Las Vegas modeli (her zaman doğru, rastgele çalışma süresi) ve Monte Carlo modeli (sabit çalışma süresi, sınırlı hata olasılığı), rastgele hızlı sıralama (randomized quicksort), rastgele seçim (randomized selection), asallık testi (primality testing) gibi kanonik örnekler, atlama listeleri (skip lists) gibi rastgele veri yapıları ve bunları analiz etmek için kullanılan olasılıksal analiz araçları (beklenti, varyans, kuyruk ve konsantrasyon eşitsizlikleri).
Temel sorular
- Rastgeleliği dahil etmek, bir algoritmayı bilinen herhangi bir deterministik algoritmaya göre nasıl daha hızlı veya daha basit hale getirebilir?
- Las Vegas ve Monte Carlo algoritmaları arasındaki fark nedir?
- Beklenen çalışma süresi veya hata olasılığı nasıl analiz edilir?
- Konsantrasyon eşitsizlikleri, kötü sonuçların olasılığını nasıl sınırlar?
- Bir Monte Carlo algoritmasının hatası, tekrar yoluyla nasıl azaltılabilir?
Anahtar kavramlar
- kaynak olarak rastgele bitler
- Las Vegas algoritması
- Monte Carlo algoritması
- beklenen çalışma süresi
- hata olasılığı ve yükseltilmesi
- konsantrasyon eşitsizlikleri
- rastgele hızlı sıralama
- atlama listeleri
Temel kuramlar
- Las Vegas ve Monte Carlo Karşılaştırması
- Las Vegas algoritmaları her zaman doğru bir sonuç üretmekle birlikte rastgele (beklenti olarak analiz edilen) çalışma süresine sahiptir; Monte Carlo algoritmaları ise sabit bir süre içinde çalışır ancak sınırlı bir olasılıkla yanlış bir sonuç üretebilir ve bu olasılık tekrar yoluyla azaltılabilir.
- Olasılıksal Asallık Testi
- Miller-Rabin gibi rastgele testler, rastgele tanıkları kontrol ederek polinom zamanda yüksek güvenle asallığı doğrulamaktadır; bileşik bir sayı çoğu tanık tarafından ifşa edildiğinden, tekrarlanan denemeler hata olasılığını ihmal edilebilir hale getirmektedir.
Klinik önem
Rastgele algoritmalar yaygın olarak kullanılmaktadır: Miller-Rabin asallık testi, açık anahtarlı kriptografinin temelini oluşturmaktadır; rastgele karma (randomized hashing) ve yük dengeleme (load balancing), dağıtık sistemleri verimli tutmaktadır; rastgele hızlı sıralama (randomized quicksort) ve hızlı seçim (quickselect), sağlam beklenen performans sağlamaktadır; ve rastgele örnekleme (randomized sampling) ve taslaklama (sketching), büyük veri akışlarının işlenmesini mümkün kılmaktadır.
Tarihçe
Olasılıksal algoritmalar, 1970'lerde rastgeleliği saygın bir hesaplama aracı haline getiren Solovay-Strassen ve Miller-Rabin asallık testleri ile önem kazanmıştır. 1980'ler ve 1990'lar, rastgele veri yapılarını (atlama listeleri, treap'ler), rastgele grafik ve geometrik algoritmaları ve Motwani ile Raghavan'ın 1995 tarihli ders kitabında kodlanan sistematik kuramı görmüştür.
Öne çıkan isimler
- Michael Rabin
- Robert Solovay
- Volker Strassen
- Rajeev Motwani
- Prabhakar Raghavan
İlgili konular
Temel eserler
- motwani1995
- rabin1980
- cormen2009
Sıkça sorulan sorular
- Bir Monte Carlo algoritması yanlış olabiliyorsa ona nasıl güvenilebilir?
- Hata olasılığı sınırlıdır ve bilinmektedir; tek taraflı hata algoritmaları için ise algoritmayı bağımsız rastgelelik ile birkaç kez çalıştırarak keyfi olarak küçük hale getirilebilir. Yeterli tekrardan sonra yanlış bir cevabın olasılığı, bir donanım arızası olasılığından çok daha küçüktür.
- Rastgele hızlı sıralama neden deterministik hızlı sıralamaya tercih edilir?
- Deterministik hızlı sıralama, kötü pivot seçimleri nedeniyle düşmanca veya zaten sıralanmış girdilerde O(n kare) en kötü durumuna ulaşabilir. Pivotları rastgele seçmek, girdiden bağımsız olarak bu en kötü durumu son derece olası olmayan hale getirir ve her girdide beklenen O(n log n) performansını sağlar.