The Pigeonhole Principle - Güvercin Yuvası İlkesi
The Pigeonhole Principle
I. Giriş
Güvercin Yuvası İlkesi, p kadar öğe (Güvercinler) p> h ile güvercin yuvasına konur ise en az bir güvercin yuvası birden fazla öğe içermesi gerektiğini belirtir.
Örnek
4 Adet güvercini 3 adet yuvaya belirli şartlar ile yerleştirmeyi deneyelim.
- Bir yuvada en fazla bir güvercin olması şartı ile bir güvercin dışarıda kalır.
- Herhangi bir şart olmaksızın rastlantısal olarak güvercinleri yuvalara yerleştirebiliriz güvercin yuvası ilkesine göre güvercinlerin nasıl ve hangi olasılık durumuna göre yerleştirildiğine bakılmaksızın bir durum içine belirli bir adetten fazla yerleştirilmesinin en az durumunu belirler.
Bu örnek için güvercin yuvası ilkesi şunu söyler :
4 adet güvercinin ve 3 adet yuvanın olduğu durumunda en az 1 adet yuva içerisinde birden fazla güvercin olacaktır.
Burada ki kilit noktamız bir yuva içerisinde "en az 1 adet yuva içerisinde birden fazla güvercin olacaktır" ifadesi güvercin yuvası ilkesinin sonucunda türetilmektedir.
II. Gelişme
Örnek
Güvercin Yuvası İlkesi sezgisel görülebilir ve bu beklenmeyen durumları göstermek için kullanılabilir. Örnek olarak, İstanbul’da aynı saç teline sahip en azından iki insan olduğunu ispatlamak bu problemi şu şekilde düşünebiliriz.
Normal bir insan kafasında ortalama 150.000 saç teli bulunur, hiç kimsenin kafasında 1.000.000'dan fazla kıl olmadığını (m = 1 milyon delik) varsaymak mantıklıdır (üst sınır olarak). İstanbul'da 1.000.000'dan fazla insan var olduğu resmi olarak kanıtlanmıştır (n, 1 milyon öğeden fazla) . Eğer her bir güvercin deliğine, kafadaki farklı sayıdaki saç sayısı yerleştirilecek dersek, en azından iki kişinin kafasında aynı sayıda saç teli olduğunu görürüz.
İlke sadece bir örtüşmenin varlığını kanıtlıyor; örtüşme sayısı hakkında hiçbir şey söylemez bu durum olasılık dağılımı konusuna girer
Birkaç basit örnek ile günlük yaşantımızda ve temel matematik üzerinden inceleyelim:
- Bir kutuda 10 siyah 12 mavi çorap olduğunu ve bir çift çoraba ihtiyaç duyulduğunu varsayalım.Her seferinde yalnızca bir tane ve bakmadan çoraplar alınıyorsa, kaç çorap kutudan alınmalıdır?
- Sorsunun doğru cevabı üçtür çünkü En az bir çift çoraba sahip olmak için (m=2 delik, her delik bir renk), bir deliği bir renk için kullanarak 3 çorap yerleştirilirse (n=3) başarı sağlanır. Burda 2 cevabı olasılıksal olarak doğru olabilir.
- Herhangi bir Verilmiş üç ardışık tam sayıdan ikisinin toplamı mutlaka çifttir.
- Ardışık üç sayı ya Tek, Çift, Tek şeklinde ya da Çift, Tek, Çift şeklinde ilerler matematiksel olarak sıralanabilir. İlk durumda tek+çift=tek ve tek+tek=çift olacağından birinci durum için ispatlanır, ikinci durum ise çift+tek=tek ve tek+tek=çift olur.
Tarih
Güvercin yuvası ilkesi ilk olarak 1624’ün başlarında Jean Leurechon’a tarafından yayımlanan kitabında bahsedilmiş olmasına rağmen
Genelleştirme
Bu prensibin genelleştirilmiş hali; eğer n ayrık obje k kaba yerleştirilecekse en az bir kap ⌈ n/k ⌉’den az olmayacak şekilde nesne barındırır şeklindedir.⌈x⌉ tavan fonksiyonudur (<ceiling function>) x’den büyük x’e en yakın veya x’in kendisi olan tam sayıya eşitler
Bu ilkeyi matematiksel ifadeler ile genelleştirmek istersek; eğer n ayrık obje m kaba yerleştirilecekse en az bir kap «tavan ⌈ n/k ⌉»’den az olmayacak şekilde obje barındırır şeklindedir.
Burada tavan fonksiyonu x’den büyük x’e en yakın veya x’in kendisi olan tam sayı ifade eder
⌈ n/k ⌉ < (N/k) +1 ifadesi doğru olacaktır.
Genelleştirme Örnek
5 bitlik 4 tip ile en az kaç adetlik dizi olmalıdır ki dizi içerisinde en az 5 adet aynı tipte eleman olsun.
Dizimiz iki farklı şekilde düşünebiliriz En az 17 adetlik bir dizi ile sonuca ulaşabiliriz ve bu bizim güvercin yuvası ilkesi genelleştirmeyi ifade eder ama bu dizi 5 boyutlu olup her elemanın aynı tip de olması durumunda olasılıklarımız içerisindendir ve doğru sonucu ifade etmektedir. Bu güvercin yuvası ilkesi olasılıksal genelleştirme olarak belirtilir.
Kriptolojide Güvercin Yuvası İlkesi
Hash algoritmalarının çıktıları sabit boyutludur. Girdilerde sonsuz olabilmektedir bu yüzden burada güvercin yuvası ilkesi oluşmaktadır. Kriptolojide bu durum Collision Resistance <çakışma dayanıklılığı> olarak adlandırılır.
256bit’lik çıktı demek 2²⁵⁶ (=1,15792089237316E+77) adet uygun çıktı olduğu anlamına gelir. Ancak olası girdilerin permütasyonları çok daha büyüktür, yaklaşık olarak 2^2⁶⁴
Eğer n'nin girdinin permütasyonlarının sayısı ve m'nin çıktının permütasyonlarının sayısı olduğunu söylersek, üretilen en az 1 hash'in bu hash ile sonuçlanan birden fazla girdiye sahip olacağını söyleyebiliriz
Güvercin deliği prensibine göre, n> m, dolayısıyla aynı çıktı permütasyonuyla sonuçlanan birden fazla girdi permütasyonu vardır. Bu durum, bir hash işlevinde birden çok girdinin tek bir çıktıya yol açtığı bir çarpışma/çakışma olarak bilinir
Kriptografide, çakışma direnci, kriptografik hash fonksiyonlarının genel ve temel özelliğidir.
Bir hash fonksiyonu H, aynı çıktıya hash olan iki girdi bulmak zorsa, çarpışmaya o kadar dayanıklıdır; yani, a ≠ b ancak H (a) = H (b) olduğunda
Çıktılardan daha fazla girdiye sahip bir durum içerisinde herhangi bir hash fonksiyonunun mutlaka böyle çarpışmalara sahip olacağı anlamına gelir ,bulmaları ne kadar zor olursa, kriptografik olarak o kadar güvenli olur.
Teoride SHA-256 algoritması için çakışma vardır. Ancak bir hash, yalnızca kasıtlı olarak çarkışmalar oluşturmanın pratik bir yolu varsa kırılır. Şimdiye kadar, hiç kimse SHA-256'ya veya SHA-2 hash algoritmaları ailesinden herhangi birine böyle bir saldırı yayınlamadı ama bu durum SHA-1 için geçerli olmadı.
Bakınız : sha1-crypto-auth-new-2-yao.pdf (uc.edu)
Yorumlar
Yorum Gönder