MIT AçıkDersmalzemeleri

http://ocw.mit.edu

6.046J AlgoritmalaraGiriş, Güz 2005

Bu materyallerdenalıntıyapmakveyakullanımşartlarıhakkındabilgialmakiçin:

Erik Demaineve Charles Leiserson, 6.046J Introduction to Algorithms, Fall 2005. (Massachusetts Institute of Technology: MIT OpenCourseWare). http://ocw.mit.edu (GirişTarihi: 08, 01, 2010YIL). Lisans: Creative Commons Attribution-Noncommercial-Share Alike.

Not: Lütfenatıftaparkenbilgilereeriştiğinizgerçektarihikullanınız.

AtıflarveKullanımKoşullarıkonusundadahafazlabilgiiçin:

http://ocw.mit.edu/termsvehttp://www.acikders.org.trsitesiniziyaretediniz.

DERS 8

Hashing yani KIYIM fonksiyonunun 2. bölümü, Bugün Kıyım fonksiyonuyla şaşırtıcı işler yapacağız. Gerçekten zarif ve şaşırtıcı. Öncelikle Kıyım’ın temel bir zayıflığından bahsederek başlayacağız. Bu şöyle ifade edilir: Seçeceğiniz her kıyım fonksiyonu için, her zaman aynı yuvaya kıyım yapacakkötü bir anahtarlarkümesi olur.Tamam, bir kıyım fonksiyonu seçtiniz,bu fonksiyonun pratikte doğru çalıştığını gözlemledik. Ama her zaman kötü bir değerler kümesi bulunacaktır. Şimdi biraz daha bu konuya odaklanalım.

Bir müşteriniz için derleyici hazırladığınızı, derleyicinizde bir sembol tablosu olduğunu ve müşterinizin,biriktirme hızının, yüksek olmasını istediğini, düşünün. Müşteriniz biriktirme sırasında oturup beklemek istemiyor. Ayrıca sizden başka derleyici hazırlayan bir de rakibiniz mevcut. Müşteriniz bu iki derleyiciyi sıralama ve çalışma zamanına göre test edecek. Müşteriniz, bu test esnasında, kendi denektaşı testinin yanı sıra, sizin rakibinizin programını, rakibinizinde sizinkini test etmesine izin verecek. Yani, aslında kodunuzu paylaşmış olacaksınız.

Dolayısıyla, siz de rakibinizin kodunu inceleyip, hangi kıyım fonksiyonunu kullandığını görebileceksiniz. Aynı şekilde bu şartlar altında, rakibinizin de sizin kodunuzu inceleyeceğini ve bütün değerleri aynı yuvayakıyacak değişkenlerin listesini çıkarıp bir şeyi aramaya kalktığınızda bu bağlantılı liste yordamıyla hep aynı sonuçlara ulaşabileceğini öngörebilirsiniz.

Bu sizin programınızı, elemanlarınızın bir kıyım tablosunda güzelce dağılmış olma durumuna oranla olağanüstü yavaşlatacaktır; çünkü kıyım tablolarını kullanmamızın ana nedeninden uzaklaşılmış olacaktır.Öyleyse, rakibimizi nasıl alt edeceğiz? Cevap tek sözcük! Tek sözcük. Nasıl başaracağız? Sınıfımızdaki bütün rakipleri nasıl yeneceğiz? RASTGELELİK! Evet, rastgelelik! Siz rastgele bir yapı geliştirirseniz, rakibiniz sizin kıyım fonksiyonunuzu tahmin edememesini sağlarsınız. Rakibiniz kodunuzu incelese de, programınız çalışması esnasında rastgele bir fonksiyon seçeceği için, kullanılan kıyım fonksiyonunun ne olduğunu tahmin etmenin bir yolu yoktur.

Tamam, demek ki oyun bu; rakibiniz bir girdi grubu sunabilir, ancak bu grubun sizin kıyım fonksiyonunuzu yavaş çalıştıracağını garanti edemez. Seçtiğiniz kıyım fonksiyonu açısından şanssız olabilirsiniz, ancak bu rakibinizin başarısı olmayacaktır.Yani buradaki fikir kıyım fonksiyonunu rastgele, ancakkullanılacakanahtarlardan bağımsız olarak seçmektir. Dolayısıyla rakibiniz kodunuzu görse bile kodun çalışması esnasında hangi kıyım fonksiyonunun kullanılacağını söyleyemeyecektir. Rakibiniz rastgele değerlerin nasıl çıktı vereceğini bilemeyecektir.

Sonuçta bu veri tanımlama yönteminin çalıştığını görürsünüz ve bunun adı Evrensel Kıyım fonksiyonudur ve pratikte kullanılan yöntemlerden birisidir.

Şimdi biraz matematik yapalım. Büyük U harfianahtarların küme evreni olsun. H ise U evrenindekianahtarları kıyım tablosundakiyuvalara eşlemleyen kıyım fonksiyonlarının sonlu bir biriktirmesi olsun. Burada H sınırlı bir collection yani biriktirmedir.Eğer bütün anahtar çiftleri birbirinden farklı ise şu doğrudur:

Seçilecekbir anahtar çifti için, bu iki anahtarı aynı yuvaya düşürecekkıyım fonksiyonlarının sayısı, 1/m çarpı anahtar kümelerinin toplam sayısıdır. Burada m ile ilgili olarak; küçük h’nin büyük H anahtarlar kümesi içinden rastgele seçildiği varsayılırsa, seçilen x ve y değerlerinin çarpışma olasılığı nedir? Eğer kıyım fonksiyonlarının sayısı büyükH/m ise, x ve y’nin çarpışma ihtimali nedir diye soruyorum? Kıyım fonksiyonunu rastgele seçiyorum. Yani rastgele bir kıyım fonksiyonu alırsak, x ve y nin çarpışma olasılığı nedir? 1/m. Doğru söylüyorsunuz. Şimdi bunun için bir şekil çizelim ve herkes gerçeğin bu olduğunu anlasın. Bunun tümkıyım fonksiyonlarının bir kümesi olduğunu hayal edin.

Tamam. Şimdi bir x ve y seçersem;diyelim ki bu kıyım fonksiyonu setinde h(x) = h(y) olsun. Bu kümenin niceliği yani cardinality’si H’nin niceliğinin 1/m katıdır. Yani, ben bir dart oku atarak bir kıyım fonksiyonunu rastgele seçersem, kıyım fonksiyonunun, bu özel kümeye denk gelmesi oranı m’de 1’dir. Tabii bu seçeceğim bütün x ve y’ler için doğru olmak zorundadır. Doğal olarak farklı x ve y’ler seçtiğimde, bu x ve y’nin eşlemleyeceği kıyım fonksiyonları da farklı olacaktır. Ama seçeceğim herhangi bir x ve y için, kıyım fonksiyonunda aynı yere kıyımlanma oranı 1/m olacaktır.

Burada insanların bazen farklı düşünmeleri zor olabilir, çünkü olaya anahtarların rastgele seçilmesi gibi bakabilirler. Ama burada olan bu değildir. Burada kıyım fonksiyonlarını rastgele seçiyoruz. Dolayısıyla bizim olasılık hesap uzayımız kıyım fonksiyonlarını baz alıyor, anahtarları değil. Bu, birbirinden farklı olarak seçtiğim her iki anahtar için doğru olmak zorunda. Bu kıyım fonksiyonları ve kıyım yaptıkları yerler; yani düşünürseniz, bu harika bir özellik.

Burada hangi iki anahtarı seçerseniz seçin, bu kümedeki rastgele kıyım fonksiyonlarından biri1/m olasılıkla bu anahtarları aynı yere yollayacaktır. Bu çok zarif;çok, çok zarif bir özelliktir ve matematiğin bununla çok güzel birleştiğini birazdan göreceğiz. Yani, bizim teorimiz şudur:h’yi,H kıyım fonksiyonları kümesinden rastgele seçerek, sonra da n adet anahtarı T tablosunda m tane yuvaya yerleştirirsek, bu durumda verilen bir x değeri için x ile beklenençarpışma sayısı, n/m’den küçüktür.

Kim n/m’yi ne olarak adlandırdığımızı hatırlıyor. Alfa, burada kullandığımız terim neydi? Loadfactor Yük Oranı. Tablonun yük oranı. Yük oranı alfa. Yani, yuva başına ortalamaanahtar sayısı tablonun yük oranıdır. Bu teorem ne diyor? Eğer kıyım fonksiyonlarını içeren evrensel bir kümemiz varsa, olaylar tam da istediğimiz gibi gerçekleşir.

Değerler eşit dağıtılır. Dağıtılacak değerlerden herhangi bir seçilmiş anahtarla çarpışma sayısı n/m olacaktır. Bu gerçekten çok güzel bir özelliktir. Şimdi, size henüz U’nun oluşturulmasını göstermedim, özür dilerim, kıyım fonksiyonları kümesinin,H’nin oluşturulması birazemek gerektiriyor. Ama öncelikle bunun neden bu kadar güzel bir özellik olduğunu göstereceğim. Temel olarak bunun nedeni, bu teoremdir. O zaman önce teoremi ispatlayalım. Bu teorinin ne anlattığına dair sorusu olan var mı? Bugün biraz hızlı gideceğiz. Bugün yapılacak çok fazla güzel iş var. Dolayısıyla herkesin bizimle ilerlemeye hazır olduğundan emin olmak istiyorum.Sorusu olan varsa; teorimi anladığınızdan emin olmalısınız, çünkü sonradan, işler daha heyecanlı bir hal aldığında kafanızın karışması yerine konuyu erken anlamak en iyisidir. Pekiyi, güzel.

Bunu kanıtlamak için, , T’deki anahtarların x ile toplam çarpışma sayılarını ifade eden rastgele değişken olsun. Bu toplam sayıdır ve rastgele algoritmaların olasılık çözümlenmesi yapılırken çok sık kullanılacak bu teknikte aslında göstergesel rastgele değişkenlerin toplamıdır.

Eğer değerleri göstergesel rastgele değişkenlere dönüştürebilirseniz, bu durumun çözümlenmesi toplu halde değişkenleri çözümlemeye oranla çok daha kolay olur. Dolayısıyla, göstergesel rastgele değişkeni küçük c_xy olsun. c_xy, eğer h(x),h(y)’ye eşit ise 1, diğer durumlarda da 0 değerini alacaktır. Böylece burada sadece 2 şeyle uğraşıyoruz:

Birincisi, c_xy ‘nin beklenendeğeri nedir sorusu? Elimde rastgele kıyım fonksiyonunu seçen bir işlem varsa, c_xy ‘nin beklenen değeri nedir?

1/m. Çünkü temel olarak tanımımız bu. Başka bir deyişle; bir kıyım fonksiyonunu rastgele seçtiğimde, kıyımın aynı yere yapılmasının oranı nedir? 1/m. Bir diğer konu ise büyük C_x , yani toplam çarpışma sayısı ifade eden rastgele değişken;bu x değeri hariç, c_xy ‘nin tablodaki tüm anahtar değerlerindeki toplamlarına eşittir.

Dolayısıyla x ile çarpışmaya neden olan her değer için toplama 1, neden olmayan her değer için 0 ekliyoruz. Dolayısıyla tablodaki x ile her çarpışmayı toplama ekleriz. Şu ana kadar bir soru var mı? Çünkü bu hazırlık evresi. Bu hazırlık aşaması bu konunun önemli bir parçası ve birçok öğrenci genelde hazırlık aşamasında hata yapar, hatta birçok araştırmacı da bu aşamada hata yapar.

Başta doğru hazırlanırsanız sonradan matematik iyi çalışır. Ancak çoğu zaman, durumu matematiğe nasıl çevirdiğiniz hazırlıktır. Bu işin zor kısmıdır. Bu süreci doğru atlatırsak, gerisi cebir, cebiri kullanabiliriz. Tabii ki cebir işlemleri sırasında da hata yapabiliriz, ancak bu hataların kontrolü ve düzeltmesi, çeviri sırasında yapılanlara göre çok daha kolaydır. Dolayısıyla herkesin, hazırlık aşamasını anladığından emin olmak istiyorum. Böylece artık matematik yeteneklerimizi kullanabiliriz.

Demek ki; toplam çarpışma sayısının beklenen değeri,yani büyük C_xin beklenen değeri y’nin, küçük c_xy ‘nin tablodaki tüm anahtar değerlerinin, y T-x boyunca değişirken c_xy‘in beklenenleritoplandığında elde edilen değere eşittir. Pekiyi, neden böyledir? Evet,doğrusallık nedeniyle..Beklenenin doğrusallığı, bağımsızlık gerektirmez. Bu bütün rastgele değişkenler için doğrudur.

Bu da eşittir ve burada matematik biraz daha kolay. Bu nedir? 1/m. Bu toplamı kolaylaştırır. Sonuçta (n-1)/m’ çıkar. Basit bir çözümleme bize, neden evrensel kıyım fonksiyonu kümelerinden birine sahip olmayı sevdiğimizi anlatıyor. Çünkü bunlardan birine sahipseniz, bu küme hep sizin istediğiniz gibi davranacaktır. Böylece rakibinizi sadece bir rastgele kıyım fonksiyonu seçerek yenebilirsiniz. Bununla ilgili rakibinizin yapabileceği bir şey yoktur.

Pekiyi, kanıtla ilgili sorusu olan var mı? Şimdi eğlenceli matematiğe geldik. Bu bebeklerden birini yapılandırmak! Bu sadece tekyapıda değildir. Bu klasik evrensel kıyım fonksiyonunun sadece bir türde yapılandırılmasıdır. Kitaplarda başka formlar da var ve galiba pratik testinde de bir tane var. Öyleyse haydi bakalım. Evet bakalım ne olacak? Bu, m asal olduğunda doğru çalışıyor. Yani, yuva kümesi asal sayıda olursa çalışıyor. Yuva sayısı asal olacak.

Buradaki fikir şu; evrenimizdeki herhangi bir k anahtarını r+1 basamağa indirgeyeceğiz. Böylece k’yi,k₀ , k₁ …,k_r olarak yazacağız ve burada 0 ≤ k_I ≤ m-1 arasında olma durumlarınıinceleyeceğiz.. Buradaki fikir k’nin m tabanında nasıl gösterileceği ile ilgilidir. Eğer tabanımız 2 ise, her seferinde sadece bir bitlik bir işlem olacaktır. Bunlar bitler olurdu. Ben 2 tabanında çalışmayacağım. Biz m tabanında işlem yapacağız ve bunların her biri basamaklardan birini ifade edecek. Ben önce düşük düzeydeki yani sol baştaki basamakta işlemleri yapmayı seçtim ama aslında farketmez. Düzeyin ne olduğu ile ilgilenmeyeceğiz ama temel olarak, biz bunu, her bir basamağıniki yönlüifadesine dönüştürmeye çalışacağız. Bunu k’dan yola çıkarak hesaplamak için kullanılabilecek bir algoritmada kalanı mod m, m veya modulo m ile gösterilebiliriz.

Bu en düşük seviye. Tamam, bu geriye kalan. Mod m’de kalanı alın. Geriye kalan ne varsa alın. Yani, taban dönüştürme konusunda bilgi sahibisiniz. Bu gösterimi bu şekilde elde edeceğiz. Bu aslında sadece sahip olduğumuz veriyi elde etme sorunu ve buna m tabanında r+1 sayısı gibi davranacağız. Şimdi, bizim rastgele yapma stratejimizi çağırma zamanı. Rastgeleye dönüştürme stratejisi,bir grup rastgele sayılara bağımlı olan kıyım fonksiyonlarına sahip olma becerisidir. Rastgele sayıları, rastgele bir a değeri seçerek belirleyeceğiz.

Ayrıca bunlar m tabanlı olacaklar. Her a_i 0’dan m-1’e kadar ancak rastgele olarak seçilecek. Dolayısıyla m de rastgele seçilmiş olacak. Rastgele m tabanı basamaklı. Dolayısıyla her biri rastgele seçilecek. Her biri için, a’nınher olası değeri için farklı bir kıyım fonksiyonu elde edeceğiz. Bu yüzden, kıyım fonksiyonlarımızı bu rastgele sayı ile indeksleyeceğiz.. İşte burası rastgeleliğin geldiği yer. Herkes benimle mi? İşte bu kıyım fonksiyonu!

Şimdi yapacağımız şu; Bu vektörün, bu vektörle iç çarpımının mod m deki sonucunu alacağız. Dolayısıyla k’nın her basamağı rastgele seçilmiş başka bir basamakla çarpılmış olacak. Bütün bunları ekleyip, mod m de sonucunu alacağız. Dolayısıyla bu bir iç çarpım işlemi. Biz bunun, bütün kümeye baktığımda içindeki h_a(k) kümesinin evrensel olduğunu da göstereceğiz. Burada bilmemiz gereken bir şey de kıyım fonksiyonlarının kümesinin ne kadar büyük olduğudur.

Kıyım fonksiyonlarının kümesi ne kadar büyüktür? Bu kümenin içinde kaç tane farklı kıyım fonksiyonu var diye soruyorum? Bu temel 6.042 dersinin materyali. Bu, temelder+1 uzunluğunda kaç tane vektör olduğuna bağlı; buradaki her vektör elemanı da 0’dan m-1’e kadar m tane farklı değer alabilir. Yani kaç tane? m-1’in r’ninci kuvveti mi? Hayır, ama yakın, o civarlarda, büyük bir sayı. Bu m’in r+1’inci kuvveti. Güzel. H’nin büyüklüğü eşittir . Bunu hatırlamak isteyeceğiz; bu formülü. Peki, bunun neden böyle olduğunu anlayalım. A’nın ilk değeri için m tane değer seçeneğim var. İkinci için m tane ve r’ninci değer için de m tane. Burada r+1 eleman olduğundan, her seçenekte aynı sayıdaki seçimlere sahibim, yani bu bir çarpım.

Bu saymadaki çarpım kuralı. Eğer 6.042’deki sayma ile ilgili notlara bakmadıysanız, geri dönüp o konuyu hatırlamak iyi bir fikir olacak.. Çünkü burada yaptıklarımızın doğası o konularla ilgili. Bu sadece çarpım kuralı. Güzel. Dolayısıyla kanıtlamak istediğimiz teorem, H’nin evrensel olduğudur. Bu birazcık Sayı Teorisi içeriyor, dolayısıyla iş ilginçleşiyor. Bu önemli ama apaçık olmayan bir ispat, dolayısıyla soracağınız herhangi bir soru varsa, lütfen sorun, çünkü bundan sonra anlatacaklarım, şu ana kadar anlattıklarım kadar basit olmayacak.

Şu ana kadar anlattıklarımız da basit değildi ama bu daha fazla matematik içerecek bir konu. İşte size bir ispatı. İki tane anahtarımız var. Bunun evrensel olduğunu göstermek için,herhangi iki anahtarı seçtiğimde bunları aynı yereyollayankıyım fonksiyonlarının sayısının,kıyım fonksiyonlarının kümesinin büyüklüğünün m’ye bölünmüş haline eşit olması lazım. Tamam. Dolayısıyla, 2 anahtara bakacağım. İki anahtarırastgele seçelim. Şimdi x’i r tabanına indirgenmiş haliylegösterelim ve y’ide, y₀, y_1…….gibi farklı anahtarlar olsun.

Bunlar 2 farklı anahtar; eğer bu ikisi 2 farklı değerse, yani aynı değillerse, butaban gösterimine göre bunlar bir yerde farklı olacaklardır. Bu doğru mu?En azından bir basamakta farklılık gösterirler. Tamam, burası birçok kişinin koptuğu nokta, burada bir basitleştirme yapacağım. Bunlar bu basamaklardan herhangi birinde farklılık gösterebilirler. Ben 0 pozisyonunda farklı olacaklarını söyleyeceğim, çünkü hangi basamakta farklılaştıklarının bir önemi yok, matematik aynı, ama i adımında farklılaştıklarını söylersem, gördüğünüz gibi i’ye eşit olmayan değerler için bir sürü hesaplama yapmak zorunda kalırım; bu da işi iyice karmaşıklaştırır.

0pozisyonu için hesaplarsam, diğerlerini sadece toplayarak devam edebilirim. Dolayısıyla matematik açısından başka bir pozisyonda yapacağım işlemler de simetri özelliğinden ötürü aynı olacaktır. Tüm basamaklar simetriktir. Bu nedenle 0pozisyonunda fark olduklarını söyleyelim, ama aynı şey diğer basamaklarda da farklı olsalardı doğru olacaktı. Dolayısıyla genellemeyi kaybetmemiş olacağız. Pozisyon 0Kabul ediyoruz. Buradaki bütün pozisyonlar simetrik olduğu içinşimdi şu soruyu sormalıyız; --

Evrensel gibi görünen kümemizdekikıyım fonksiyonunda kaç tane x ve y çarpışacaktır? Tamam bunları saymalıyız. Ne kadar sıklıkla çarpışıyorlar? Burada sayı teorisini ağırlıklı olarak kullanacağız. Eğer Çarpışma olursah_a(x) = h_a(y)’ye eşit olacaktır. Bunların çarpışması için böyle olması gerekir.

Bunun anlamı da, i sıfırdan r’ye değişirken a_içarpı x_i ‘nintoplamlarının i sıfırdan r’ye kadar değişirken, a_i kere y_i ‘nin toplamlarına eşit olduğudur; burada bunlar eşleniktir ve mod m tabanındadır.

Aslında bu eşlenik mod yani mod m’dir.Sayı teorisini görmemiş arkadaşlarınız için eşlenik olma kavramını şöyle açıklayayım: Eşlenik olmak özüne dönme yollarından biridir ve buradakileri modla ve sonra şuradakileri modla demekyerine mod yada tabanı belirleme uygulamasını en sonda bir kez yaptırırız. Her şey m moduna dönüştürülür.Ve bu durumda eşlenik işaretini kullanırız.Eşlenikliğin daha detaylı matematiksel açıklaması da var ama biz mühendisler için bu kadarı yeterli. Şu ana kadar herkes benimle beraber umuyorum.Bu sadece tanımı uygulamadır.Böylece bunu şöyle de gösterebiliriz:i, 0’dan r’ye kadar değişirken, a_içarpı (x_i – y_i)’nin toplamları,mod m’de 0’a eşleniktir.

Tamam bunu öbür tarafa atalım ve dağıtımyasasını uygulayalım. Şimdi sadece sıfırıncıpozisyonu dışarı çekmem gerekiyor, çünkü önem verdiğim tek yer orası. Eğer sıfırıncı pozisyonuseçmeseydim, bir sürü matematiksel zorluklarla karşılaşacaktım.Bu a₀çarpı(x_0- y₀)’ın dışarı alınması.Amabu çok fark ettirmezsadece matematiği daha kolay hale getirir…Böylece bir terimi dışarı çekmiş olduk. Bu da şu anlama gelir: mod m’dea₀çarpı(x_0- y₀ ) bu terime eşleniktir.. Şimdi m tabanında eksi değerin ne yaptığını hatırlayın; bu sayıyı 0’dan m-1’e kadar olan bir değere çeviriyorum. Örneğin7 modeksi 5 iki’dir. İkidir. Yani, eğer eksi değerlerim varsa, m veya m’nin katlarından birinibunlaraeklerim, çünkü m’nin katlarını eklemek eşlenikliği etkilemez. Şimdi bir sonraki adımda, sayı teorisi gerçeğini kullanacağız. Dolayısıyla şimdi sayı teorisine ve kitaba başvuralım. --- bir de regresyonyapalım.

Bu, sınırlı alanlar teorisinden gelir. Bu, bilenler için, bilgilerini koyacakları bir yerdir; bilmeyenler için ise matematiğin öğrenilmesi gerekengüzel alanlarından birisidir.

m bir asal sayı olsun. Herhangi bir küçük z,ki büyük Z_mkümesinin içinde ve büyük Z_mise mod m’deki tam sayılardan oluşsun. Bu, 0’dan m-1’e kadar, çarpım, çıkarma, toplama, vb. bütün işlemler için geçerlidir. Yani, 0 ile m-1 aralığının dışında bir değer elde ederseniz m’nin katlarını ekleyip, çıkartıp normalize ederek m tabanına dönmeniz gerekir.

Bu mod m’de çalışmak için gereken standart işlemdir. 0’a eşlenik olmayan z değeri için,büyük Z_mkümesininiçinde z’nin tek bir tersi yani vardır. Öyle ki; z ile ’i çarparsam modm’de 1’e eşlenik bir sonuç elde ederim. Dolayısıyla hangi sayı ile çalışırsam çalışayım o sayıyı çarpınca sonucun1’e eşit olduğu başka bir sayı vardır. m’nin 7 olduğu bir örneği çözelim şimdi. Burada küçük bir tablo oluşturalım. zsıfıra eşit değil. Diğer sayıları yazalım. Şimdi z’nin tersini bulmaya çalışalım.

1’in tersi nedir? 1’i neyle çarparsam 1 elde ederim? Güzel, 1. Peki ya 2? 2 hangi sayıyla çarpılırsa 1’e eşit olur?. 4. Çünkü 4 çarpı 2 = 8’dir ve 7 tabanında 8, 1’e eşleniktir.Pekiyi 3’ünki ne olur? 5! Doğru.3x5 = 15’. Çünkü 15, 7’ye bölündüğünde 2 çıkar ve kalan 1’dir. Peki ya 4? 2!

5?3! Ve 6? Evet 6’nın tersi kendisidir. 6 kere 6 = 36’dır! 36’dan 7’nin katı 35 çıkarsa geriye 1 kalır. Burada dikkat ederseniz bir sayının tersi neyse, çıkantersin tersi de yine o sayıdır diyebiliriz. Bu grup teori ve alan teorisinde çalışırken kanıtladığımız şeylerden birisidir. Bu tarz matematikle uğraşırken başka birçok güzel şeyle karşılaşabilirsiniz, Ama aslında, m asal sayı değilsebu doğru olmaz. Şimdi mod 10’da çalışırken neler olabileceğini düşünebilirsiniz.

Mod 10’da tersi olmayan bir sayı söyleyebilir misiniz? Evet, 2. Bir diğeri de 5! Daha genel anlatmamız gerekirse, göreceli olarak asal olmayan yani bölenleri olan, yani o sayı ile mod büyüklüğü arasında en büyük ortak böleni 1 olmayan durumlarda mod m’de o sayının tersdeğeri bulunamaz.Ama eğer bir asal sayı ise, diğer bütün değerler, göreceli olarak asaldır. Ama Bu da bizim faydalandığımız özelliktir.

Bu durumda ben (x₀– y₀)’a bölmek istiyorum. Bu evrede yapmak istediğim işlem bu. Ama her şeyden önce, eğer m bir asal sayı değilse bunu yapamayabilirim. Belki de yaparım ama her zaman olmaz. Ama m asalsa kesinlikle (x₀ – y₀)’a bölebilirim. Bunun tersini bulabilirim. Ayrıca burada, (x₀ – y₀) 0’a eşlenik olmadığından da emin olmalıyım. Bu x₀ ile y₀’ın eşit olması anlamına gelir ama varsayımımızı bunların eşit olmaması durumuna dayandırmıştık.

Bir kez daha genel anlatımı unutmamak için tekrarlarsak, eğer başka bir pozisyonda çalışıyor olsaydık, o pozisyonda da tam olarak aynı şeyleri yapıyor olacaktık. Şimdi, (x₀ –y₀)’a bölebiliyoruz. Ve ispatımızla devam edelim:x_0,y₀’dan farklı olduğundan, (x₀ – y₀) ‘ın tersi her zaman var olacaktır. Oradaki durumugeliştirdiğimizde,

a₀ eksi,i,1’den r’ye değişirken,a_i çarpı (x_i– y_i)(x₀ – y₀)’ın ters değerinin çarpımının toplamlarına eşlenik olacaktır.

İspatımızın başına geri dönelim ve ne elde ettiğimizi görelim. Biz iki tane farklı anahtarımız olduğunu, bütün bu a_i’leri rastgele seçtiğimizi ve bu iki farklı anahtarın aynı yuvaya kıyıldığını söylüyoruz. Eğer aynı yuvaya kıyılıyorlarsa, bu; a₀’ın diğera_i’nin bir fonksiyonu sonucu çıkan bir değeri olmasıgerektirir. Başka bir deyişle, ben a_i’leri 1’den r’ye kadar seçtimve örnekteki gibi bu seçimi sıralı olarak yaptıysam, a₀’ı çarpışacak şekilde nasıl seçebilirim ki! Çarpışmaya sadece bir değer neden olabilir, o da bu eşlenik denklemle tanımlanan a₀ değeridir.

Eğer a₀ için farklı bir değer seçseydim, çarpışmayacaklardı. Bunu yazalım. Yani, bu a_i’lerin herhangi biri seçildiğinde, a₀’ın m olası seçeneği arasından sadece birisix ile y nin çarpışmasına neden olacaktır. Yani bir kez daha tekrarlayalım, bu a_i’lerin herhangi biri seçildiğinde a₀’ın m olası seçeneği arasından sadece birisi x ile y nin çarpışmasına neden olacak.a₀’ı seçerken yapacağım diğer seçimlerdeise çarpışma olmayacak. Dolayısıyla, çarpışmalar açısından rastgeleliğimin serbestlik derecesini m oranında azaltmış bulunuyorum. xile y’nin çarpışmasına neden olan küçük h_a’ların sayısı, eşittir: Çarpım kuralını kullandığımda m tane seçenek var.

a₁ için olan m seçenek çarpı a₂ için m seçenek çarpı …a_riçin m seçenek ve a₀ için bir seçeneğim var. Bunlar çarpışma olacak ise, a₁, a₂, a_r ve sadece bir seçeneğim olan a₀ için seçimlerim. Eğer çarpışmayacaklarsa, a₀ için daha fazla seçeneğim olacak. Ama eğer çarpışmalarını istiyorsam, seçeneğim sadece bir a₀ değeridir, o da budur! Bu benim seçebileceğim tek değer. Bu da ’ye eşittir yani H’nin büyüklüğünün m’ye bölünmesi.

Bu da ispatı tamamlar. Başka evrensel yapılandırmalar mümkün, ancak bu zarif ve özel bir tanesi. Burada konu, benim m+1, özür dilerim, r+1 düzeyinde özgürlüğümün olması. Her düzeyde de m tane seçeneğim var. Ama eğer çarpışmalarını istersem, r adet olası seçeneği kullandıktan sonra, sonuncu seçenek kendiliğinden oluşuyor. Dolayısıyla çarpışma durumu yaratan fonksiyon kümelerinin sayısı sadece m’de bir taneolacak.Gayet akıllıca bir yapı.

Çok akıllıca. Tamam, herkes zannediyorum benimledir. Çok fazla insanı kaybetmedim değil mi? Evet soru var mı? Evet? Bunun aslında sıkça kullanılan uygulamaları var.Kriptografi benzeri bir ders alırsanız, bunlarda mod m ile iç çarpımlargibi konular ve özellikle basit sınırlı alanlar olan Galois Alanlarının çözümlerinde bu anlattıklarımla bol bol oynarsınız.

Örneğin Galois Alanları yani harici /veya komutlarının buradaki gibi sıkça kullanıldığı alanlardır; bundan farkı 2 tabanlı olmasıdır.Yani bu tarz işlemlerle ilgili birçok çalışma var. İnsanlar bu tarz özellikleri anlıyorlar. Ama sorunuz “algoritmalar konusunda mükemmel sezgi edinmenin algoritması nedir?” sorusunu hemen akla getiriyor. Keşke bilseydim, hemen kontağı açardım. Ama bu o kadar kolay olsaydı, burada karşınızda duruyor olmazdım.. Güzel. Şimdi bende hayranlık uyandıran başka bir konuya geçmek istiyorum. Bu çok çok güzel bir matematik uygulaması ve kıyım fonksiyonu geliştirmekteki yeteneğinizeönemli katkıda bulunacaktır..

Şimdi alakalı başka bir konuya geçmek istiyorum. Bu konu,perfect hashing yani Mükemmel Kıyım olacak. Şu ana kadar yaptıklarımız beklenenzamandabaşarımla ilgiliydi.. Kıyım,beklenen süre bağlamında iyi bir uygulama. Mükemmel kıyım ise şu sorulara ilgilenir:Farzedin kisize bir anahtar kümesi verdim ve bana statik bir tablo yaratmanızı istedim. Böylece en kötü zamanda tabloda anahtarı arayabileyim. Bir iyi birde en kötü zamanda. Dolayısıyla elimde sabit bir anahtar kümesi var.Aynı İngilizcedeki en sık kullanılan 100 veya 1000 sözcük gibi bir şey.

Ben bir sözcüğü ele aldığımda, sözcüğün İngilizcede sık kullanılıp kullanılmadığına tabloya bakarak hızlı bir şekilde anlamalıyım. Bu işi beklenen başarımladeğil de garantilenmiş en kötü durum zamanında yapabilmeliyim. Bunu hızlı yapabilmemin bir yolu acaba var mı? Demek ki problem şu; verilen n adet anahtar için statik bir kıyım tablosu yaratmak. Diğer bir deyişle, yeni girdi veya silme yapılmayacak. Sadece elemanları oraya koyacağız. Büyüklüğü ise,m = O(n).

Dolayısıyla çok büyük bir tablo istemiyorum. Büyüklüğü anahtarlarım boyutunda olan bir tablo istiyorum. m = O(n) boyutunda bir tablo ve en kötü durumda arama O(1) zamanı alacak. Ortalama durumu biliyor olacağım, bu çok zor değil,ama en kötü durumda değerlerin yığılıp, fazla zaman kaybına neden olacağı bir nokta olmayacağından emin olmalıyım. Herhangi bir noktada bu olmamalı;her bir arama O(1) zamanında olmalı.

Herhangi bir değeri ne kadar sürede elde ettiğime dair istatistiksel bir değişim olmamalı. Acaba Herkes bulmacanın ne olduğunu anladı mı? Bu çok önemli çünkü çok fazla kullanım alanı var. Bir tablo yaratacağınızı ve bu tablonun içinde hangi değerlere bakacağınızı biliyorsunuz. Ama bu tablo için fazla yer harcamak da istemiyorsunuz. Buradaki fikir iki aşamalı bir veri tanımlaması yapmaktır.

Fikir, iki aşamalı bir plan uygulamak.ve ilk aşamada evrensel kıyım fonksiyonunu çalıştıran bir veri tanımlaması kullanmaktır. Fikir, kıyım yapmak; bir kıyım tablomuz olacak, yuvalara kıyım yapacağız, ancak zincirleme işlemini kullanmak yerine ikincibir kıyım tablosu daha olacak. İkinci tabloya ikincibir kıyım daha yapacağız. Ve buradaki fikir ikinci düzeyde hiç çarpışma olmadan kıyım yapmak.

Dolayısıyla birincidüzeyde çarpışma olabilir. Birinci tabloda çarpışan her şeyi ikincidüzeydeki tabloya koyacağız, ama bu tabloda çarpışma olmayacak. Buuum. Tam buraya kıyım yapacağız. Şimdi veri tanımlamasını gösteren bir resim çizelim: Tamam, şimdi elimizde olanlar şunlar: 0, 1, 6’ya kadar yazalımve sonunda, m-1. İşte bu bizim Kıyım Tablomuz. Birinci düzeyde evrensel kıyım kullanacağız. Dolayısıyla evrensel bir kıyım fonksiyonu bulalım. Rastgele bir fonksiyon seçiyoruz. Yapacağımız bu düzeye yani ilk düzeye kıyım yapmak. Bundan sonra iki şeyi takip edeceğiz.

Birincisi, diğer düzeydeki kıyım tablomuzun büyüklüğü. Bu durumda, kıyım tablomuzun büyüklüğünü yuva sayısıyla adlandıracağız; 4 olacak. İkinci düzey içinse farklı bir kıyım anahtarı kullanacağız. Dolayısıyla, ikinci düzeyde her yuvanın farklı bir kıyım fonksiyonu olacak. Mesela, bir yuva rastgele seçilmiş 31 değerini taşıyabilir. Şuradaki a’lar gibi.. Bu, yani hangi anahtarla kıyım yapacağım benim kıyım fonksiyonumun temeli olacak. Bu yuva 86 olsun. Sonra, kıyım tablosuna bir işaretçi koyayım; buna büyük S₁ diyeyim. Bu 4 yuvaya sahip olacak ve 14ile 27’yi saklayacak. Bu yuvalar ise boş.

Pekiyi, örneğin bunda ne vardı? Yani buradaki fikir şu; sayıları yerleştireyim. Buradaki fikir, eğer benim küçük h diyeceğim üstteki seviye kıyım fonksiyonuna bakarsak; Bu h(14) =h(27) o da 1’e eşit. Çünkü birinci yuvadayız.Şimdi bu ikisi birinci düzeyde kıyım tablosunda aynı yuvaya kıyılıyor. Bu birinci düzeyde.. Buradaki de ikincidüzey. Yani 14 ve 27 birinci seviyede çarpıştılarve aynı yuvaya gittiler. Ancak ikinci seviyede farklı yuvalara kıyıldılar. Seçtiğim kıyım fonksiyonu seçtiğim rastgele sayılara göre anahtar listesi oluşturarak bu yapıyı yarattı. Ve bunların nasıl bulunacağını anlatacağım. Şimdi ikinci düzeyde, h₃₁(14) sayısı için, 1’e eşit.,ve h₃₁(27) sayısı için 2 değerlerini aldı..İkinci seviyede.

Burada kıyım yaparken, şuradaki tablom ne olursa olsun, bunu kıyım fonksiyonumuntemeli olarak kullanıyorum. Eğer ikinci düzeyde hiç çarpışma olmamasını garanti edebilirsem, bu bana aramanın en kötü durumundabüyük O(1) zamanına mal olacak. Peki nasıl arıyorum?Bu kıyım fonksiyonu için değerin ne olduğuna bakıyorum. Bu değeri kıyım fonksiyonuna uyguluyorum, bu da beni başka bir yuvaya götürüyor. Bu temelde 2 kıyım fonksiyonu uygulaması artı biraz arama artı az bir miktar kayıt yapmama mal oluyor.

Bu düzeyde çarpışma olmamasının nedeni şudur: Eğer birinci düzeydeki kıyım tablosunun i’nci yuvasına kıyılan n_i tane eleman varsa, ikinci düzeydeki kıyım tablosunda m_isayıda yuva kullanırız ve burada m_i, n_i ’nin karesi kadar yuvaya eşit olarak seçilir.Şunu burada söylemem gerekirdi.bu m_i, yani kıyım tablosunun büyüklüğü, bu da a_i olacaktı. Dolayısıyla temel olarak, n_i tane elemanı n_i ‘nin karesi kadar yere yerleştireceğim; yani bu inanılmaz büyük olacak.Boyut olarak karesel büyüklükte olacak.Burada göstereceğim şey bu koşullar altında sıfır çarpışma sağlayacak kıyım fonksiyonları bulmamın kolay olacağıdır. Oyunun adı budur. Kıyım fonksiyonlarını hiç çarpışma olmayacak şekilde ayarlayabilmektir. Bu şekli bu nedenle az elemanlı çizdim.Örnek olarak, 2 elemanım varsa 4 büyüklüğünde bir kıyım tablom olur. 3 elemanım varsa 9 yuvalı bir kıyım tablosuna ihtiyacım olur.

Eğer 100 elemanım varsa, 10000 yuvalı bir kıyım tablosuna ihtiyacım olacak. O büyüklükte bir şeyle uğraşmayacağım. Gerçekte bu çalışıyor ve bize istediğimiz bütün özellikleri sağlıyor ve bu da çözümlemenin bir parçası. Tamam, herkes bunun en kötü durumda zamanınınbüyük O(1)’e mal olduğunu ve temel yapısının ne olduğunu anladı mı? Bu arada, bu şeyler, bu örnekte asal değiller. Her zaman bu değerlere yakın asal sayılar seçebilirim. Bu örnekte bunu yapmadım.

Tersine, asal sayı olmayan sayılarla çalışan bir evrensel kıyım fonksiyonu seçebilirdim. Ama bunu da bu örnekte yapmadım.Çözümleme için hazır mıyız? Tamamöyleyse biraz çözümleme yapalım. Bu gerçekten güzel bir çözümlemedir. Aslında çözümlemenin bir kısmını yaptık, şimdi geri kalan kısmını göreceksiniz. Buradaki ustalıkikinci düzeydeki çözümlemeyi yapmaktır. Bu benim çözümlemek istediğim esas şey. Bununla, kıyım fonksiyonları bulabileceğimi, değerleri bu dizinlere seyrek bir şekilde eşlemleyebileceğimi, dolayısıyla da böyle kıyım fonksiyonları olduğunu ve bu fonksiyonları önceden hesaplayabileceğimi göstermeme yol açacak.

Bunları saklayacak güzel bir yöntemim var. Kullanacağım teoremise şu:. Evrensel küme H’deki rastgele bir kıyım fonksiyonu olan h’yi kullanarak, n’nin karesine eşit m tane yuvaya anahtarlar kıyıldığında,beklenen çarpışma sayısı ½’denküçük olacaktır. Tamam. Aslında bir çarpışma bile olmasını beklemiyorum. Ortalamada yarımdan az bir çarpışma sayısı umuyorum. Şimdi bunu kanıtlayabiliriz;küçük h altındaki 2 anahtarın çarpışma olasılığı nedir?

h evrensel kümeden rastgele seçildiğinde h’ninetki alanındaki belirli 2 anahtarın çarpışma olasılığı nedir diye soruyorum. 1/m. Doğru mu? Tanımı bu, doğru, bu örnek için aynı zamanda 1/n²’ye de eşit. Dolayısıyla, tabloda kaç tane anahtar çifti var? Kaç tane anahtar birbiriyle çarpışabilir? Bu aslında temel olarak kaç çift değeri hesaplamam gerektiğine bağlıdır. Bu n’nin ikili kombinasyonu kadar anahtar çifti eder.

Bu nedenle de her n için beklenen çarpışma sayısı, nnin ikili kombinasyonu kadar olacaktır.n’nin ikili çiftlerinin buradaki çarpışma olasılığı 1/n² dir.Bu da ; nçarpı(n-1)/2, eğer formülü hatırlarsanız, çarpı 1/ n² eder.Bu da yarımdan küçüktür. Bu tüm çiftler için geçerlidir. Eğer 6.042’deki doğumgünü paradoksunu anımsarsanız, bunubu paradoksla ilişkilendirebilirsiniz.

Ama burada daha büyük bir kümeye sahibim ve bütün çiftlere bakıyorum, ama kümem yeterince büyük olduğu için çarpışma olasılığı göreceli olarak daha küçüktür. Eğer m’nin karekökünün ötesinde arttırmaya başlarsam, eleman sayısı olan m’nin karekökü büyümeye başladığı anda, çarpışma ihtimali de dramatik bir şekilde artar. Bunu doğumgünü paradoksundan da biliyorsunuz. Ama eğer daha seyrek, daha az ise, çarpışma olmaz. Veya göreceli olarak daha az çarpışma olacaktır. Şimdi size daha önce varsaydığım bir şeyi hatırlatmak istiyorum; ama biraz hızlı geçmek istiyorum. Bu Markov’un eşitsizliği. Markov eşitsizliğini kim hatırlıyor? Herkes elini hemen kaldırsın. Markov eşitsizliği şunu söyler:

Bu önemli olasılık gerçeklerinden biridir. 0’ın altında sınırlanmış rastgele değişken x için, x’in verilmiş herhangi bir t’den büyük olma ihtimali, x’in beklentisi bölü t’den küçüktür. Bu önemli bir gerçektir. Eğer x 0’dan küçük ise bu geçerli olmaz. Ama güzel bir gerçektir. Bu sayede, bir olayın olasılığıyla, bekleneniilişkilendirebiliyorum. Buradaki fikir; genel olarak, eğer beklenen küçük olacaksa, bu durumda rastgele değişkenin değerinin büyük olması olasılığı yoktur. Bu pek mantıklı olmaz. Yani beklentim bir iken, bir milyon gibi yüksek bir olasılıknasıl olabilir, yada buradaki gibi beklenti küçük yani yarımken bunu nasıl uygulayabiliriz? Olamaz.

İspat da tanımdan yola çıkılarak yapılıyor.Ben bunu ayrık rastgele değişkenler için yapıyorum. Tanım gereği x’in beklenen değeri,x 0’dan sonsuza giderken, x çarpı kere rastgele değişkenimin büyük X’eeşit olmaolasılıklarının toplamına eşittir. Bu tanımımızdır. Gerisi hayal edebildiğinizce kaba bir yaklaşıklaştırma olacak. Herşeyden önce tüm küçük terimleri atarak başlayalım; x’in t’den sonsuza gittiği durumda, xçarpı rastgele değişkenim büyük X’in x olma olasılığının toplamlarına eşit yada büyük olanları atıyorum. Yani bütün alt seviye terimleri atıyoruz. Şimdi bunların hepsini eşittir t’nin alttan sınırlandırılmış değerleri ile değiştireceğim.

Bu sadece x’in t’den sonsuza giden değerleri üzerinde bir toplama işlemidir; toplanacak elemanlar t çarpı büyükX’in,küçükx ‘eeşit olma olasılığı. x burada büyük t değerleri alır, çünkü bunlar büyük değerlerdir. Ve bu da bunu dışarıya çıkarabileceğim için, t çarpı x’in t’den büyük iken, büyükX’inküçükx ‘e eşit olma olasılıkları toplamı, yani büyük X’in t’ye eşit yada büyük olma durumu olur. t’ye böldüğümde bu da tamamlanmış sayılır.

Bu Markov’un eşitsizliğidir. Gerçekten basittir. Chebyshev veya Chernoff sınırları gibi daha güçlü şeyler de var. Ama Markov’un eşitsizliği inanılmaz derecede basit ve kullanışlı. Dolayısıyla biz bunu bir corollary yani sonuç teoremi olarak kullanacağız. Sonuç olarak, n tane değeri n² yuvaya Evrensel Kıyım Fonksiyonu kullanarak yerleştirdiğimizde çarpışma olmama ihtimali ½’den büyük veya eşit. Rastgele birkıyım fonksiyonu seçiyorum.

n tane anahtarı n² sayıda yuvaya kıyarken, çarpışma olmama ihtimali nedir diye sorarsam? Cevap; Hiç çarpışma olmama ihtimali en az yarımdır. Yarısında çarpışma olmayacağını garantiledim. İspatı ise gayet basit. Birden fazla çarpışma olması ihtimali,şimdi Markov’un eşitsizliğini uyguluyorum,bu da beklenen çarpışma sayısı bölü 1 Markov’ eşitsizliğine göre. Burada beklenen çarpışma sayısı daha önce de gösterdiğimiz gibi yarımdan az. Buda ½’den küçük. Yine Markov eşitsizliğini uygulayarak. Burada beklenen çarpışma sayısı daha önce de gösterdiğimiz gibi yarımdan az. Yani en az bir çarpışma olmasınınolasılığı yarımdan az ise, hiç çarpışma olmama olasılığı da en az yarımdır. Burada işimiz biter. İyi düzeyde bir kıyım fonksiyonu bulmamız kolaydır. Bir kaçını rastgele test ettim. Çoğu, tamam, yarısı, en az yarısı düzgün çalışacaktır. Eğer biraz düşünürseniz, bu rastgele bir yapılandırma, çünkü hangisi olacağını söyleyemiyorum. Bu açıdan yapılandırmacı değildir ama rastgele bir yapı.

Birçoğu bu güzel özelliğe sahip olduğu için, var olmak durumundalar. Herbirini bulabilirim; rastgele birkaç tanesini test ettim ve bir tane buldum. Buradaki tablomu doldurdu. Bütün bunlar ön hesaplama. Varolan bir taneyi bulma olasılığım yüksek olduğundan onları bulacağım. Aynı zamanda iyi bir ikinci düzey kıyım fonksiyonu bulmak için birkaç tanesini rastgeletest edin;çabucak bulursunuz çünkü en azından yarısı çalışacak.

Ben sadece iyi birkaç tane olduğunu göstermek istiyorum. Yapmam gereken, her bir durum için en az bir tanesinin çalıştığını ispatlamak. Aslında, ben çok miktarda çalışan olacağını zaten gösterdim. Yarısı çalışacak. Ama var olduğunu göstermek için, olasılığın 0’dan büyük olduğunu göstermem gerekiyor. Bitirmek için hala depolama durumunu çözümlemek gerekiyor, çünkü teoremde tablomun büyüklüğünün n düzeyinde olacağına dair güvence verdim.

Bunlar karesel büyüklükte yuvalardı. Bunların büyük O (n) olduğunu göstereceğim. Birincidüzeyde bu kolay. Burada, yuvaların sayısının, anahtarların sayısına eşit olmasını sağlarız. Bu şekilde birinci düzeyde depolama n seviyesinde olur. Şimdi n_inin anahtarların sayısınıgösterenve i’ninci yuvaya kıyılan rastgele bir değişken olduğunu düşünelim.Bu büyük T’deki i yuvasına kıyımlansın. n_i yuvalardaki elemanların sayısı. m_i n_i ‘nin karesine eşit; bunu daha öncede kullanmıştık.Buda ikinci düzey tablosu S_i ‘nin yuva sayısı.

Burada beklenen toplamdepolama birinci düzey için n;dilerseniz n düzeyinde diyebilirsiniz, ama temelde birinci düzey için n artı beklenen değer, yani i’lerin 0’dan m-1’e değiştiğinde n_i karelerinin tetalarının toplamı olacaktır. Buradaki her elemanın karesini eklemem gerekir. Bu toplamayı kim hatırlıyor? Daha önce nerede gördük? Ek derse kim katıldı? Bunu nerede gördük?

Beklenen değerleri topluyoruz. Evet, o algoritma neydi? O sıralama algoritmasını yapmıştık, değil mi? Bunun hesaplanmasının önemli olduğu sıralama algoritması hangisiydi? Herkes aynı anda söylemesin? Sıralama algoritması ne olarak çağrılıyordu? Bucket -Kova sıralaması. Evet,n kutuya rastgele düşen, rastgele değişkenlerin karelerinin toplamı teta n di.Teta n.. Doğru mu?

Daha önce de yaptığımız gibi, bununla bir olasılık sınırı belirleyebilirsiniz! Markov’un eşitsizliğini de kullanarak belli bir miktar çarpı n’den büyük olmasının ihtimali nedir diye sorarsam? Ama bizim bu çözümlemedeki kilit noktamız bu. Eskiden bunu zamanla ilgili işlemiştik ama sıralama algoritmalarını başta çalışmamızın nedenlerinden biri bunlarda kullanılan tekniklerin çözümlemenin diğer yuvalarında da yaygın olarak görülmesidir. Siz benzer birçok şey gördünüz, Kovasıralamasını da gördünüz, dolayısıyla bunu ekstradan çalışmadan biliyorsunuz.

Geriye dönüp, Kova sıralaması analizini,çözümlemesinitekrar etmek isteyebilirsiniz, çünkü burada kullandık. Aynı analiziiki yerde kullandık.

Bugünkü dersimiz bitmiştir.. Gelecek derste görüşmek üzere..