MIT Açık Ders malzemeleri

http://ocw.mit.edu

6.046J Algoritmalara Giriş, Güz 2005

Bu materyallerden alıntı yapmak veya kullanım şartları hakkında bilgi almak için:

Erik Demaine ve Charles Leiserson, 6.046J IntroductiontoAlgorithms, Fall 2005. (Massachusetts Institute of Technology: MIT OpenCourseWare). http://ocw.mit.edu (Giriş Tarihi: 08, 01, 2010). Lisans: Creative CommonsAttribution-Noncommercial-ShareAlike.

Not: Lütfen atıf taparken bilgilere eriştiğiniz gerçek tarihi kullanınız.

Atıflar ve Kullanım Koşulları konusunda daha fazla bilgi için:

http://ocw.mit.edu/terms ve http://www.acikders.org.tr sitesini ziyaret ediniz.

DERS 12

Günaydın.. Bugün yeni bir dengeli arama yapısından, yani araya yerleştirme, silme ve arama işlemlerinde dinamik kümeyi koruyan bir veri yapısından, skip lists yani atlama listelerinden bahsedeceğiz. Ben buna dinamik bir arama yapısı diyeceğim çünkü bu bir veri yapısıdır. Arama işlemini destekler ve dinamik dediğimde araya yerleştirme ve silmeyi kastediyorum. Pekala, hem karşılaştırma yapabilmek hem de herkesi uyandırmak için, başka hangi dinamik arama yapılarını biliyoruz? Sayın bakalım, ama aynı zamanda verimli olsunlar, yani işlem başına logaritmik zamanlı olsunlar.. Bu bizim ayağa kalkmamızı sağlayacak kolay bir soru..

Bunların hepsini geçen hafta gördünüz, bu nedenle size çok zor gelmemeli..

Treap, iyi.. Bunlarla ilgili bazı problemler çözmüştük. Bu bir bakıma ilk prensiplerden çıkarılan en basit dinamik arama yapısı çünkü tüm ihtiyaç rastgele yapılanmış ikili arama ağacındaki bir sınırlamaydı.. Bundan sonra treap’ler başarılıydı. Yani bu problem setinizi ne zaman çözdüğünüze bağlı olmak kaydıyla ilk gördüğünüz yapı olabilir.. Başka neler var?

Charles? Kırmızı siyah ağaçlar, iyi cevap.. Bu tam bir hafta önceydi. Umarım hala hatırlıyorsunuzdur. Bunların log n düzeyinde garantili performansı var. Yani bu beklenen sınır. Bu en kötü durumda işlem başına log n düzeyinde; araya yerleştirme, silme ve arama için.. Ve geçen etüde gidenlerin öğrendiği bir tane daha var: B-ağaçları, iyi.. Ve B-ağaçlarının içine iki-üç ağaçlarını, iki-üç-dört ağaçlarını, tümünü dahil ediyorum. Yani B bir sabitse veya B-ağaçları akıllıca yapılandırılmışlarsa bunların performansı en kötü durumda log n düzeyindedir. Bunu bilmeniz gerekiyor. Bunların tümü dengeli arama yapılarıdır. Bunlar dinamiktir. Bunlar araya yerleştirme ve silmeyi desteklerler. Bunlar aramayı, verilen bir anahtarı bulmayı desteklerler. Ve bu yapıların tümünde anahtarı bulamasanız bile onun öncülüne yada ardılına kolalıklı erişebilirsiniz.

Eğer bir veri yapısını değiştirmek istiyorsanız, geçen derste olduğu gibi değiştirme işleminin bunlardan hangisiyle en kolay yapılacağını düşünmelisiniz. Şimdi size sormak istediğim soru; varsayın ki hepinize bir dizüstü bilgisayar verdim.. Ne iyi olurdu değil mi? Ve sonra o dizüstünün sizde kalması için bu veri yapılarından birini çalıştırmanızı istedim… Diyelim ki bu ders süresinde.. Bunu yapabileceğinizi düşünüyor musunuz? Kaç kişi yapabileceğini düşünüyor? Birkaç kişi, ön sırada oturanların hepsi.. İyi.. Sanırım ben yapabilirdim.. Tercihim B-ağaçları olurdu.. Bana göre en kolayı onlar.. Tabii kitabı kullanmak yok.. Bu kapalı kitap bir sınav. olurdu. Ama maalesef herkese verebileceğim sayıda dizüstü bilgisayar yok..

Aslında B-ağaçları oldukça mantıklı.. Silmede ardıldan çalmayı ve yapılmaması gerekenleri hatırlamalısınız. Yani silme biraz şaşırtıcıdır. Kırmızı-siyah ağaçlar, bunu hiçbir zaman hatırlayamam. Ya bir yerlere bakmam, ya da 3 durumu yeniden çıkarmam lazım.. Treap’ler biraz daha hoş ama bunların nasıl çalıştığını hatırlamak zaman alır. Eğer ezberlemediyseniz problem setinizi bir kez daha çözmeniz gerekir.

Öte yandan atlama listeleri hiçbir zaman unutamayacağınız ve sorunsuz olarak bir saate çözebileceğiniz veri yapılarıdır. Bu iddiayı birkaç kez öne sürdüm ama daha önce uygulamaya koymadığım için kendimi hep kötü hissettim.

Bu nedenle bu sabah atlama listelerini uyguladım; bir linkli listeyi çözmek 10 dakikamı ve atlama listesi de 30 dakikamı aldı. Sonra da bunların hatalarını ayıklamak 30 dakika daha sürdü. İşte o kadar.. Yani yapılabilir. Atlama listeleri gerçekten kolay. Ve kodu yazarken de diğer yapılarda olduğu gibi çok düşünmek zorunda kalmadım. Sadece bir noktada “yazı turayı nasıl atmalıyım?” diye düşündüm. Tüm düşüncem o kadardı. Yani, atlama listeleri rastgele bir yapılanmadır. Burada bir sıfatı daha ekleyelim; basit sözcüğünü.. Yani elimizde basit, verimli, dinamik rastgele bir arama yapısı var: Tüm bunlar bir arada.. Yani bunlar treap’lere benziyor ama sınır sadece rastgele bir sınır. Ama bugün beklenen sınırdan çok daha güçlü bir sınırlama durumunu göreceğiz.

Kısacası atlama listeleri özellikle log n beklenen zamanında çalışır. Yani her işlemin koşma zamanı beklenen düzeyinde log n’dir. Ama biz bu sonucun çok daha yüksek olasılıkta olduğunu kanıtlayacağız. Aslında bu çok büyük bir iddia.. Bunun anlamı, bir bakıma her bir işlemin ve tüm işlemlerin koşma zamanının kesinlikle log n zamanında olması. Bunu neden daha belirgin söylemiyorum? Yani bu şöyle olacak; bunun log n olasılığında olması demek, en az 1 eksi 1 bölü n üzeri bir polinom olması demektir.

Ve siz bu polinomu dilediğiniz büyüklükte seçebilirsiniz. Yani temelde her zaman atlama listelerinizi alır, üzerinde polinomsal sayıda işlem yapabilirsiniz çünkü bu veri tabanını kullanan polinomsal zamanlı bir algoritma ile çalışıyorsunuzdur. Polinomsal sayıda araya yerleştirme, silme arama yaparsınız ve bunların her biri, her zaman log n süresi alır; bu neredeyse garantilidir.

Yani bu dağılımın kuyruğunda çok sıkı bir sınırlamadır. Ortalaması log n düzeyindedir; bu çok heyecan verici değil.. Ama gerçekte, bu olasılık dağılımının ağırlığı log n civarındadır ve çok küçük epsilon değerleri kadar log n ‘den büyük olabilir. İşte gideceğimiz yön bu. Bu veri yapısı Pugh tarafından 1989 da kuramlandı. Ve bu en yeni olanıdır.

Aslında, treap’ler daha yeni, özür dilerim.. Onlar 1993’de bulundu ama bu da yalnızca araya yerleştirme, silme ve arama için oldukça yeni bir veri yapısıdır. Ve çok basittir. Bunu veri yapılarıyla ilgili neredeyse hiçbir şey bilmeden de türetebilirsiniz. Şimdi, performansın log n düzeyinde olduğunu çözümlemek, tabii ki incelikli düşünce gerektirir. Ama veri yapısının kendisi çok basittir.

En baştan başlayacağız. Kırmızı-siyah bir ağacın ne olduğunu bilmediğinizi düşünün. B-ağacın da ne olduğunu bilmiyorsunuz. Hatta bir ağacın bile ne olduğunu bilmiyorsunuz. Bir dinamik kümede birtakım öğeleri depolamak için kullanılan en basit veri yapısı nedir? Bir liste, iyi , bir bağlantılı listedir.. Şimdi bunun sıralı bir bağlantılı liste olduğunu varsayın; böylece biraz daha fantezi olabilir.

Şimdi elemanları bağlantılı olan bir liste varsa, liste bu; belki de zevkine bunu çift yönlü bağlantılı yaparsak, sıralı bir bağlantılı listede arama yapmak ne kadar zaman alır? log n yanıtlardan biridir. n diğer yanıttır. Bunların hangisi doğru? n doğru yanıttır. Yani sıralanmış olsa bile burada ikili arama yapamayız çünkü bağlantılı bir listeye rastgele erişim yetkimiz yoktur. Şimdi yalnızca liste başına bir işaretleyicinin bana verildiğini varsayın. Aksi takdirde bunun bir dizilim olduğunu varsayacağım. Bu durumda sıralanmış bir dizilimde log n süresinde arama yapabilirsiniz. Sıralanmış bağlantılı listede ise tüm listeyi taramanız gerekir. Yani en kötü durumda arama teta n düzeyindedir. Bu çok iyi değil, ama bunun biraz geliştirirsek skip listelerini otomatikman keşfederiz.

İşte başlangıç noktamız burası: sıralı linkli listeler, veri n zamanlı.. Ve bu evrede araya yerleştirme ve silmeleri çok düşünmeyeceğim. Önce aramayı geliştirelim, güncellemeler konusunda sonra tasalanırız. Güncellemeler rastgele yapma işleminin başlayacağı yer. Arama: çok kolay bir fikir. Pekiyi sıralı bir listeyi nasıl daha iyi bir hale getirebiliriz? Tüm bildiğimizin linkli listeler olduğunu farz edin. Bunu daha hızlı bir hale getirmek için ne yapmalıyım? Burası biraz yaratıcılığa ihtiyacınız olan yer.

Daha çok link: bu iyi fikir. Yani birkaç adım daha ileriye gitmek için belki birkaç işaretçi ekleyebilirim. Eğer elimde log n sayıda işaretleyicim varsa ileride tüm 2’ nin üstellerini ele alabilirim. Bu oldukça iyi bir arama yapısıdır. Bazıları bunu kullanır; tüm uç birimden uç birime ağlar bunu kullanır. Ama bu benim için biraz lüks. Aa bu iyi. Bu doğrusal yapının üzerine bir ağaç kurmayı deneyebilirsiniz. Temelde gideceğimiz yer burası. Yani köklerden diyelim ki listelerin ortancalarına işaretçiler koymayı deneyebilirsiniz. Buralarda arama yapabilirsiniz. Ortancayı işaretlersiniz, ortancayla karşılaştırma yaparsınız ve böylece ilk yarıya mı ikinci yarıya mı gideceğinize karar verirsiniz ve bu kesinlikle doğru yoldur ve biraz da sofistikedir. Başka bir liste mi? Evet, evet güzel.

Böylece iki liste kullanacağız. Bu en kolay yapılabilecek ikinci şey. Tamam ve önerdiğiniz gibi bunların arasında işaretçiler olabilir. Yani bazı elemanlar burada aşağıda, bazıları da şurada yukarda olabilir. Listeler arasında işaretçiler olmasını istiyoruz. Tamam, bunu kesinleştirmek biraz delice bir şey. Ama bir şekilde iyi bir duygu veriyor. Öyleyse bu bir linkli liste: ,bu da ikinci liste:

Ve size bir ilham vermek istediğimden haydi bir oyun oynayalım. Oyunun adı bu dizi nedir? Evet dizi 14’tür. Cevabı biliyorsanız söyleyin. Daha kimse bulamadı mı? Tamam, biraz şaşırtıcı. Bu küçük bir sınıf. Onun için birisinin cevabı bildiğini umuyorum. Kaç öğretim görevlisi yanıtı biliyor? Birkaç kişi, tamam.

Slaytlara bakarsanız yanıtı da bilirsiniz. Ama bu kopya çekmek olur. Şimdi size bir ipucu vereceğim. Bu bir matematiksel dizi değil. Bu bir gerçek hayat dizisi. Evet?

Evet, pekiyi hangi şehir? New York. Bu 7. cadde metrosu. Bu New York’ da en sevdiğim metro hattı. Ama New York şehri metrosunun ilginç özelliği nedir? Evet, bir atlama listesidir. İyi cevap. Gerçekten öyledir. Atlama listeleri öyle pratiktir ki metro sistemine bile entegre edilmiştir. Bu ilginç değil mi? Tamam, Boston metrosu da çok ilginçtir. Çünkü Birleşik Devletlerin en eski metrosudur, belki de dünyanın. New York’un ki de buna yakındır ve 24 saat açık olmak gibi başka güzel özellikleri de vardır. Bu kesinlikle bir artıdır ama ekspres hatları olması gibi bir özelliği de vardır. Bu biraz soyut oldu ama 7. Cadde hattında iki tür tren vardır. Aslında bunlar sokak numaraları. Bu Penn istasyonu Times meydanı ve böyle. Yani aslında iki hat vardır. Ekspres hat 14’ten 34’e 42’ye 72’ye ve 96’ya gider. Bundan başka her durakta duran yerel hat da vardır. Ve bunu 4 takım rayla çözerler. Yani, ekspres hatların kendine ayrılmış rayları var. Örneğin Penn İstasyonundan 59 numaraları durağa gitmek isterseniz yani aşağı batı yakasından ekspres hatta binersiniz.

42’ye çabuk varırsınız sonra da yerel hatta geçer 59’a gidersiniz. Tamam, bunlar ekspres ve yerel hatlardı ve de bunları birkaç listede temsil edebiliriz. Bir listemiz olur ve aşağıda da bir listemiz olduğundan burada biraz boşluk bırakın. Bu lokal hat, ; 34,42,50,59,66,72,79, ve böyle. Sonra da yukarda ekspres hattımız var ve bu sadece 14,34,42,72,ve böylelerinde duruyor. Tüm listeyi yeniden çizmeyeceğim. Fikri anladınız. Yapacağımız şey yerel ve ekspres hatlar arasına linkler koymak..

Ve bu bizim 2 linkli liste yapımız. Şekli çizerken anlatmak istediğim buydu. Şimdi bunun özelliği, alttaki listede her elemanın gösterildiğidir. Üstteki listede ise bu elemanların bazıları kopyalanmıştır. Ve bu özelliği koruyacağız. Yani ‘de elemanlar depolanırken ’de bir alt küme depolanıyor. Ve hangilerini depolayacağımıza henüz karar vermedik. Düşünmemiz gereken tek şey bu. Ve ilhamımız New York metro sisteminden geliyor. Tamam, fikir işte bu. Tabii 2’den fazla liste de kullanacağız. Tamam, elimizde linklerimiz de var. Diyelim ki linkler ve ’deki ortak anahtarlar arasında.

İyi. Şimdi, bütünlük adına ve buna daha sonra ihtiyacımız olacağı için, bu listelerin gerçekte nasıl yapılandırılacağıyla uğraşmaktan önce aramalarla ilgili konuşalım. Tabii bu tabloyu istiyorsam. Yani x elemanını aramak isterseniz ne yaparsınız? Bu örnekte metro algoritmasını ele alacağız. Eğer her zaman metro sisteminin üst-sol köşesinden işleme başlarsanız, eğer her zaman aşağı-batı yakasından başlarsanız örneğin 14. Sokaktan… ki bunun tam olarak neresi olduğunu bilmiyoruz ama az çok Manhattan’ın aşağısında bir yerde… ve siz 59 gibi belli bir istasyona gitmek istiyorsunuz.

Ve mümkün olduğu kadar ekspres hatta kalmak istiyorsunuz çünkü bu hattan yola çıktık. Sonra buradan iniyorsunuz ve geri kalan yolu yerel hatta tamamlıyorsunuz. Her zaman üst-sol köşeden başlarsanız yapılacak doğru şey budur. Şimdi bunu bir tür algoritma şeklinde yazacağım çünkü bunu genelleştireceğiz. Bu evrede bu çok açık ve ileride de böyle olacak.

Yani gidebildiğim kadar yukarıdaki listede gideceğim ta ki çok uzağa gidene kadar. Şimdi hiç metro sistemini kullanmamış birine tarif ettiğinizi düşünün. Diyorsunuz ki 14. den başlayın. Ekspres hatta binin ve 72’ye vardığınızda gereğinden fazla ileri gitmiş olacaksınız. Bir geri gidin ve orada yerel hatta binin. Bu gerçekten rahatsız edici bir tarif. Ama bir algoritmanın yapması gereken bu çünkü daha önce hiç metroya binmedi. Yani önce kontrol edecek ve onu burada yapalım. Benim 59’a gitmeyi hedeflediğimi varsayın. 14’ten başladım. İlk yaptığım şey 34’e gitmek. Oradan 42’ye giderim. Bu hala iyi çünkü 59, 42’den büyük. Sağa gitmeye devam ederim. Sonra derim ki: hay Allah 72 çok büyük. Bu çok uzak oldu.

Yani geriye, olduğum yere giderim. Aşağı inerim ve sağa gitmeye devam ederim. İstediğim elemanı bulana kadar; ya da bunun aşağıdaki listede olmadığını keşfederim çünkü aşağıdaki listede herkes var. İşte algoritma bu.. Demek sağa giderken çok uzağa gittiğinizde durun ve bunu bir karşılaştırmayla keşfedin. Sonra ye yürüyün. Ve ’ de x’i bulana kadar sağa doğru gidin.. veya x den daha büyük bir şey bulursanız x listenizde değil demektir.

Ve öncülü ya da ardılı bulursunuz ve bu sizin hedefiniz olabilir. Eğer x’ i bulamadıysanız, orada olmaması durumunda nereye gideceğini bulmalısınız çünkü bu durumda onu araya yerleştirebilirsiniz. Bu algoritmayı araya yerleştirmede kullanacağız. Tamam ama yaptığımız arama bu evrede oldukça kolay. Şimdi tartışmadığımız konu arama algoritmasının hızıydı ve bu da hangi elemanlar alt kümesinin ‘ de depolanacağıyla ilgiliydi. Şimdi metro sisteminde büyük olasılıkla bütün popüler istasyonları ’e koyarsınız. Ama burada biz en kötü durum performansıyla ilgileniyoruz. Yani elimizde düğümlerin olasılık dağılımı yok. Biz her düğüme tek düze şekilde en hızlı erişimle ilgileniyoruz.

Yani tüm sorgularda maksimum süreyi en aza indirgemek istiyoruz. ile ne yapacağımız konusunda bilgisi olan var mı? Başlangıçta tüm düğümleri ’ e koymalı mıyım? Tamam, bu bir kesin alt küme. Size ’ in boyutunu söylediğimi varsayın. Size şu kadar ekspres durağı kullanabileceğimi söyleyebilirim. Bunları ’nin elemanları arasında nasıl dağıtırsınız? Tek düze olarak, iyi. Yani hangi düğümler, pardon hangi anahtarlar e girmeli. Aslında yapılacak en iyi şey bunları tek biçimde yaymaktır ve 7. Cadde hattı kesinlikle böyle değildir.

Ama her şeyi yeniden tasarlayacağımızı hayal edin. Burada aralıkları biraz daha büyük bırakacağız. 34 ve 42 birbirine çok yakın. Birkaç durak daha alacağız. Ve şimdi bu şeyleri çözümlemeye başlayabiliriz. Bunu uzunluğunun bir fonksiyonu olarak yapacağız. Böylece aramanın maliyeti için ’in uzunluğun bir fonksiyonunu kullanacağım ve nin uzunluğu da tüm elemanlar yani n .

‘deki tüm elemanları tek düze olarak yayarsam aramanın maliyeti ne olur? Evet? Doğru, üst listelerdeki elemanların toplamı artı aşağıdaki ve yukarıdakinin bölümü. Yani ’in uzunluğu artı ’nin uzunluğunun ’in uzunluğuna bölünmesi olarak yazacağım. Tamam, bu yaklaşık bir değer. Çünkü burada en kötü durum için artı 1 ya da benzer bir şey olması lazım; tüm ’i aramam gerekebilir. Çünkü aradığım istasyon maksimum değerli olabilir. Tamam, belki de şanssız olurum ve maksimum ekspres hatta olmayabilir. Bu durumda yerel hatta geçmem gerekir ve yerel hatta kaç durakta durmam gerekir?

Aslında , ’ yi eşit bölüntülere ayırıyor. Yani bu 2 ekspres durağı arasındaki ardıl istasyonların sayısı. Yani örneğin bu uzunlukta ekspres hatta gidiyorum ama yaklaşık şu uzunlukta yerelde gidiyorum. Ve bu bir . Ayrıca bir sabit de var. Örneğin aşağı yürümek için. Ama temelde ziyaret ettiğim düğüm sayısı bu kadar. Şimdi bu fonksiyonu en aza indirmek istiyorum. Şimdi ’ ye n diyeceğim. Çünkü toplam eleman sayısı bu. ‘i istediğim gibi seçebilirim. Şimdi şuraya geçelim.

Yani artı n bölü ’i en aza indirmek istiyorum. Ve ’i seçiyorum. Şimdi bunun türevini alabilir, sıfıra eşitler ve delirebilirim. Veya bunu gerçekleştirebilirim. Yani o kadar da zor değil ama bu benim için oldukça karmaşık. Böylece diyebilirim ki bu küçük olduğu takdirde iyi bir durum olacaktır. Ve bu da büyük olduğu takdirde en iyi olacaktır. Yani burada bir pazarlık var. Ve bu terimler eşit olduğu takdirde pazarlık belirli sabit faktörlere kadar en aza indirgenebilecektir. Bu durum pazarlığın iki ucunda iyi bir denge olursa geçerlidir. Ve bu sabit faktörler oranındadır. ’i n bölü ’e eşit seçebilirim. Çünkü bu durumda bunlar eşit olduğunda 2 oranında bir faktör kaybederim.

Evet şimdi sadece bunu çözeceğim. Bu gerçekten çok kolay. Bu ’in karesi eşittir n. Yani , n ‘nin kare kökü. Tamam, burada elde ettiğim maliyet artı bölü , n’ nin karekökü artı, n bölü karekök n. Yani sonunda karekök n’dir. Böylece 2 çarpı karekök n elde ederim. Böylece arama maliyeti ve buradaki sabitle ilgileniyorum çünkü birazdan anlam kazanacak. 2 karekök n: artıdan gelen sabitle ilgilenmiyorum ama çarpım sabitiyle ilgileniyorum. Tamam bu iyi görünüyor. İşe bir listeyle başladık ve aramayı n zamanda yapıyordu, yani işlem başına teta n süresinde. Şimdi elimizde iki linkli liste var, arama teta kök n süresinde yapılıyor.

Bu iyi görünüyor. Yapılanma böyle görünüyor. Burada kök n eleman var. Bu yerel hat. Ve şunu temsil eden bir ekspres durağı var. Ama yerel hattımızda başka bir kök n değerleri var. Ve bunu da temsil eden bir ekspres durağı var. ve bu ikisi birbiriyle ilintili ve böyle gidiyor. Şuraya nokta nokta noktaları koymam lazım. Tamam bu dilimlerin her birinin uzunluğu kök n. Ve yukarıdaki temsilcilerin sayısı da n’ nin karekökü. Ekspres duraklarının sayısı n’ nin karekökü. Şimdi her şey dengelenmiş durumda. Yukarda en fazla karekök n arama yapacağım. Ve sonra bu listelerden birinde en fazla karekök n kadar arama yapacağım.

Böylece her arama en fazla 2 kök n olacak. İyi, bundan sonra ne yapmalıyız? Yine araya yerleştirme ve silmeleri unutun. Aramaları daha sonra hızlandırmalıyım. Çünkü n’ nin karekökü bildiğiniz gibi o kadar da cazip değil. Pardon? Daha çok hat. Bir tane daha süper ekspres hattı ekleyelim ya da başka bir linkli liste. Evet bu ikiliydi. Neden üç olmasın? Aslında bir sıralı linkli listeyle başladık. Sonra ikiye çıktık. Bu bize 2 çarpı n’ nin karekökünü verdi. Şimdi üç sıralanmış linkli liste istiyorum. Burada çoğullaştırma yapmadım. Koşma süresinin ne olacağı konusunda tahminler var mı? Bu sadece tahmin işi.

Düşünmeyin. İki çarpı n’ nin karekökünden gideceğiniz yer… pardon? İki çarpı ikinin karekökü, n’ nin dördüncü kökü mü? Bu doğru değil. Hem sabit hem de kök değişti. Fakat çok şaşırtıcı şekilde değil. Üç çarpı küp kök: iyi. Sezgi burada çok yardımcı olur. Doğru yanıtın ne olduğu önemli değil. Sezginizi kullanın. Bunu kanıtlayabilirsiniz, çok zor değil. Şimdi elinizde üç liste var ve dengelemek istediğiniz en üstteki listenin uzunluğu, üstteki iki listenin oranı ve alttaki iki listenin oranı ve bu üçünün çarpımlarının n olmasını istiyorsunuz. Çünkü üstteki çarpı ilk oran çarpı ikinci oran: bunların n’ ye eşit olması lazım. İşte buradan n’ nin küp kökünü elde edersiniz. Bunların her biri eşit olmalıdır. Bunları öyle ayarlarsınız ki maliyet bu üçünün toplamı olsun.

Yani her birini n’ nin küp köküne eşitlersiniz ve bunlardan üç tane vardır. Bundan emin olmak istiyorsanız evde kontrol edin. Görünen o ki birkaç tane daha istiyoruz. Öyleyse k sayıda sıralanmış listeyi düşünün. k sayıda sıralı liste, k çarpı n’ nin k’nıncı kökü olacaktır. Bunu şu ana kadar büyük olasılıkla tahmin etmiştiniz. Öyleyse k’ yı hangi değere eşit alalım? Tam minimum değeri aramıyorum. k için iyi bir değer nedir? Bunu n’ ye mi eşit yapalım? n seçimi aslında hoş çünkü n’ nin, n’ ninci kökü 1’e eşit olur. Şimdi bu n. Bu nedenle baştaki sabitlere önem verdim. Çünkü liste sayısı arttıkça bu sabit de büyüyecektir. Kullanabileceğim en büyük mantıklı k değeri nedir?

Log n. Çünkü orada bir k var. Kesinlikle log n’ den daha fazlasını kullanmak istemiyorum. Böylece log n kere n’nin log n’ninci kökü ve bunu n’den türetmek biraz zor. Şimdi n’ nin, log n’ ninci kökü nedir? Hepinizin şu anda düşündüğü şey bu. n’ nin, kök n’ninci log’ u eksi 2 nedir? Bu güzel sorulardan biridir ve yanıtı da? Haydi ama, kökün tanımını hatırlayın. Tamam. Kök n’ nin 1 bölü log n’ ninci kuvvetidir. Tamam, iyi. Kuvvet almanın tanımını hatırlayın. Büyük A’ nın B’ ninci kuvveti? Bu 2’ nin büyük B log büyük A’ nıncı kuvveti değil midir? Bu size bir yerlerden tanıdık geliyor mu? Yani bu 2’ nin log n bölü log n’ ninci kuvveti olur. Ve bu da, bu evrede çıkarmanızı umduğum gibi 2’ ye eşittir. Hey, böylece n’ nin, n’ ninci kökünün logaritması eksi 2 sıfıra eşit. En sevdiğim yanıt. Tamam bu da öyle. Böylece tüm bu şey 2 log n. Çok şık. Bununla daha da uğraşarak bir şeyler yapabilirsiniz ama 2 log n benim için oldukça iyi. Kesinlikle daha fazla liste kullanmak istemiyoruz ama log n sayıda liste oldukça iyi görünüyor. Şimdi logaritmik bir arama süresi elde ettik. Gelin kontrol edelim. Yani şu ana kadar hep sezgisel çalıştık. Şimdi listenin nasıl göründüğünü çizelim. Ama bu liste çalışacak. Şimdi bu örneği bir daha çizeceğim, çünkü siz de bunu yapmalısınız.

Haydi, New York şehri metro sistemini yeniden tasarlayalım. Ve burada yukarıda 3 boşluk bırakmanızı istiyorum. Bunu şimdiye kadar ezberlemiş olmanız gerekirdi. Ama ben ezberlemedim. Aslında yerel hattı değiştirmeye yetkimiz yok. Ama birkaç durak daha ekleyebilsek iyi olurdu. Tamam 79. Sokakta durabiliriz. Bu yeterli. Şimdi elimizde log n tane liste var. ve burada log n, 4 civarında. Burada birkaç liste yapmak istiyorum. Özellikle 14 hepsinde görülecek. Bunları niye buraya çizmiyorum ki?

Şimdi soru, buraya hangi elemanlar girecek? Elimde log n tane liste var. Ve amacım yukarda burada olanların sayısını bu iki liste arasındaki oranı, ve bu iki liste arasındaki oranı, ve bu iki liste arasındaki oranı dengelemek. Bütün bunların dengeli olmasını istiyorum. Bunlardan log n tane var. Bu oranların çarpımının da n çıkması gerekir. Yani bu aşağıdaki eleman sayısı kadar. Böylece bu oranların hepsinin çarpımı n’ dir.

Ve bunlardan log n tane varsa her bir oran hangi büyüklüktedir? Orana r diyelim; bu durumda r’nin log n’inci kuvvetinin n’ye eşit olması gerekir. r nedir? r eksi 2 nedir? Sıfır. Evet, bunun iki üzeri log n’ye eşit olması gerekir. Böylece buradaki elemanların aşağıda kalan elemanlara oranını alırsam aşağıda n elemanımız olur ve bu benim istediğim. Diğer bir deyişle buradaki elemanların yarısını, şuradaki elemanların dörtte birini, buradaki elemanların sekizde birini istiyorum ve bu böyle gidiyor. Bu nedenle eşit aralıklı elemanların yarısını alacağım: 34., 50., 66., 79. Ve böyle…

Bu bizim yeni yarı ekspres hattımız: Çok hızlı değil ama bu yukarı çıkmak için iki farklı ürünü kazanıyorsunuz. Ve işiniz bittiğinde iniyorsunuz ve ek çok bir adım yürüyorsunuz. Ve aradığınızı buluyorsunuz. Tamam. Ve bu işlemi elemanlar bitinceye kadar tekrar ediyoruz. Hay Allah. Kendi el yazımı okuyamıyorum. Bu 79 olmalı. Tamam daha büyük bir örneğim olsaydı daha çok seviyem olurdu ama bu da yeterli. Diyelim ki her iki elemanda bir duruyorum. Evet bu iyi görünüyor. Bu kabaca daha önce gördüğünüz bir yapıya benziyor mu? Evet? Bir ağaç: Evet. Bu bir ikili ağaca çok benziyor.

Bunu bırakacağım. Problem setinizde atlama listelerinin neden gerçekte ağaçlara benzediğini göreceksiniz. Ama gerçekten bunlar bir ağaca benzer. Bu düzeyde bir ikili aramayı andırır. 14’e bakarsınız; 15’e bakarsınız ve böylece sol yarıda mı sağ yarıda mı olduğuna karar verirsiniz. Ve bu bir ağaçta olduğu gibidir. Tam bir ağaca benzemez çünkü bu elemanın her yerde tekrar ettiğini görüyorsunuz. Ama gene de kabaca bir ağaca benzer. I derinliğinde ikinin I’ nıncı kuvveti kadar düğüm olur . Aynen dengeli bir ağaçta olduğu gibi.

Ben bu yapıya ideal bir atlama listesi diyeceğim. Ve tüm yaptığımız arama işlemi olursa, ideal atlama listeleri oldukça iyidir. Belki pratikte ikili arama ağacı kadar iyi değildir ama belli sabit faktörlere kadar onun kadar iyidir. Örneğin aramayı genelleştirip bunun log n olup olmadığını kontrol edebilirsiniz. Yani arama işlemine sol üstten başlarsınız. Diyelim ki 72’yi arıyoruz. Sol üstten başladınız. 14, 72’den küçüktür. Bu nedenle sağa giderim. 79 çok büyüktür. Böylece bu oku takip ederim. Fakat bunun çok büyük olduğunu söylerim. Bunun yerine 14’ ten aşağı inmeye devam ederim. Sağa giderim. Oo, 50, bu hala 72’ den küçük. Tekrar sağa gitmeyi denerim. Oo, 79. Bu çok büyük . Bu iyi değil. Bu nedenle aşağı inerim. Yine 50’ye gelirim; tekrar yaparım.

Tekrar sağa gitmeyi denerim. Oo 66. Bu iyi. Tekrar sağa gitmeyi denerim. Oo 79. Bu çok büyük. Bu nedenle aşağı giderim. Şimdi buradan sağa giderim ve 72. Tamam. Aksi takdirde, çok ileri gitmiş olurum ve aşağı inmeye çalışırım ve hay Allah eleman burada olmamalı derim. Bu çok basit bir arama algoritmasıdır: Buradakinin aynı gibi ancak ’ i ve ’yi çıkarmak kaydıyla. Çok ileri olana kadar sağa gidersiniz. Sonra aşağı gidersiniz. Sonra tekrar çok fazla olana kadar sağa gidersiniz ve aşağı gidersiniz. Bu işlemi log n kez tekrarlamak zorunda kalabilirsiniz.

Her düzeyde sadece birkaç adım gidersiniz. Çünkü bu iki boyut arasındaki oran yalnızca 2’dir. yani bu arama için 2 çarpı log n ‘ye mal olur. İyi. Söylemek istediğim burada sezgi kullandığımız için bunu kontrol ettik; biraz tartışılır bir şekilde. Böylece bu ideal bir atlama listesidir ve biz araya yerleştirme ve silmeleri de desteklemek zorundayız. Bir araya yerleştirme ve silme yaptığımızda yapıyı korumanın bir yolu yoktur. Bu çok özel bir durumdur. Bunlardan sadece biri mükemmel bir şekilde yayılmıştır ve her şey çok güzeldir. Yani bunu yapamayız. Bu yapıyı elimizden geldiği kadar kabaca koruyacağız. Ve eğer içinizde biriniz New York şehri metro planlayıcılarından birini tanıyorsa bunu onlara söyleyebilirsiniz. Tamam. Yani atlama listeleri. Demek istediğim, bizim veri yapımız temelde bu. Bunu başlangıç noktası olarak kullanabilirsiniz ama ondan sonra atlama listelerini kullanmaya başlarsınız. Ve bir şekilde araya yerleştirme ve silmeleri de uygulayabilmeliyiz ve bunu öyle yapmalıyız ki arama hala log n süresi alsın ve yapı kabaca korunsun.

Şimdi araya yerleştirmelere odaklanalım. Eğer araya yerleştirmeleri doğru yaparsak silmeler gerçekten kolaydır. Ve bunlar ilk prensiplerden çıkar. Karmaşık bir şey kullanma yetkimiz yoktur. Ama kaliteli tebeşir kullansak iyi olur. Bu daha iyi görünüyor. Şimdi bir x elemanını araya yerleştirmek istediğinizi düşünün. Bu elemanı aramayı konuştuk. Şimdi bunu nasıl araya yerleştiririz? Yapmamız gereken ilk şey bunun nereye yerleştirileceğini hesaplamaktır. Yani x elemanını ararız. x’i herhangi bir listede değil, en alttaki listede ararız.

Üstteki listede nereye yerleşeceğini bulmak kolaydır. Bu yaklaşık sabit zaman alır. Bizim bilmek istediğimiz şey, üstteki listenin sabit uzunluğu olduğundan x’in alttaki listede nereye gideceğini bulmaktır. Diyelim ki 80’i yerleştirme araması yapıyoruz.

Aslında bu bayağı büyük. Biz 75’i arayalım. Bu durumda 75’in aynı hat üzerinde 72 ila 79 arasına yerleşeceğini buluruz. Eğer bunu orada bulursak bundan şikayetçi olmalıyız çünkü resmi basit tutmak için bütün anahtarların farklı olacağını varsayacağım.

Ama bu işlem aynı anahtarı tekrar tekrar araya yerleştirseniz bile iyi çalışır. Yani bu iyi haber. Kesinlikle yapmamız gereken şey x’i alttaki listede araya yerleştirmektir. Şimdi bunun nereye gideceğini biliyoruz; oraya gitmeli. Çünkü biz alttaki listenin tüm elemanları içermesi değişmezini muhafaza etmek istiyoruz. İşte böyle yaparız. Değişmezi koruduk. Alttaki liste tüm elemanları içeriyor. Böylece 75’i ararız. Deriz ki 75 buraya gider ve bir şekilde 75’i buraya linkleriz. Umarım bir linkli listenin nasıl yapıldığını biliyorsunuzdur. Şu işaretçiyi buradan silmeme izin verin.

Atlama listelerini uygulamada tüm iş linkli listelerin manipülasyonudur. Peki bu yeterli mi? Hayır, ama şimdilik bu uygun çünkü bu aralıkta bir şeyi arıyorsanız sadece 3 uzunluğunda bir zinciri görürsünüz ama eğer 75’ i ve 76’yı sonra da 76 artı epsilonu, 76 artı 2 epsilonu araya yerleştirir ve böyle devam edersem burada bir sürü eleman olur ve zincir gerçekten uzar. Böylece birden her şey o kadar da dengede değildir. Eğer bir arama yapacak olursam burada birini aramak için oldukça uzun süreye ihtiyacım olur.

Eğer k elemanını araya yerleştirirsem bu k zamanı alacaktır. Ben bunun log n olarak kalmasını istiyorum. Eğer sadece log n sayıda elemanı araya yerleştirirsem şimdilik bu kabul edilebilir. Şimdi karar vermek istediğim bu listelerden hangisinde 75’in olması gerektiği. Aslında çok açık bir şekilde alttakinde yer alması gerekiyor. Her eleman en alttakinde olmak zorunda mı, bir seviye yukarı mı gitmeli? Belki. Bu bir şeylere bağlı ve şu anda açık değil. Eğer buraya birkaç öğe yerleştirirsem bunların bazıları üstteki düzeye gitmek durumunda. İki düzey yukarı mı gitmeliyim? Belki. Ama daha küçük bir olasılık var. Bu durumda ne yapmalıyım? Evet?

Doğru. İdeal bölüntü boyutunu korursunuz. Ve bu da bu zincirin uzunluğu olabilir. Ve bakarsınız, eğer bu çok uzarsa bunu ortadan bölüp bu elemanı üst düzeye terfi ettiririm ve aynı şeyi burada da yaparım. Eğer bu zincir bir sonraki düzey ekspres durakların arasında da çok uzarsa ortadaki elemanı terfi ettiririm. Ve problem setimizde de yapacağımız şey bu. Bu benim için çok karmaşık olur. Benim işimi zorlaştıracak sayaçlara ihtiyacım yok.

Başka ne yapabilirim? İdeal atlama listesi yapısını korumaya çalışabilirim. Ama bu çok pahalı olur. Örneğin 75 terfi edecek eleman olursa bu eleman en aşağıya kadar indirgenmek zorunda. Ama bu her şeyi sağa doğru iter. Ve bu da güncelleme için lineer süre maliyeti gerektirir. Başka düşüncesi olan var mı? Eğer bunların sadece yarısının yukarı gitmesini istersem yazı tura atabilirim. İyi fikir. Tamam bunun için size bir 25 kuruş vereceğim. Bu iyi bir madeni para. İşte burada. Ama bu paraya bir işlem de yapmak zorundasınız. Yani havaya atmalısınız.

Siz yazı-tura atabilir misiniz? İyi, ne geldi? Tura. Tamam. Bu ilk rastgele bit. Ama biz bir atlama listesi yapılandıracağız. Belki de size bunun nasıl yapılacağını anlatmalıyım. Ama temel fikir yazı-tura atmaktır. Eğer yazı gelirse, af edersiniz, eğer yazı gelirse bunu bir üst düzeye terfi ettireceğiz ve yeniden yazı-tura atacağız. Bu diğer hangi listelerin x’ i depolaması gerektiği sorusunun yanıtıdır. Daha kaç listeye x’ i eklememiz gerekir? Aslında algoritma yazı-tura atın, eğer yazı gelirse x’ i bir sonraki düzeye terfi ettirin diyor ve tekrar yazı-tura atın diyor.

Tamam, bu önemli. Çünkü biz bu elemanın rastgele yükselmesini istiyoruz. Ama yeni başlayanlar için yazı-tura atıyoruz. Bazen bir üst düzeye gitmiyor. Aslında biz onun bir üst düzeye 1 bölü 2 olasılığıyla gitmesini istiyoruz çünkü bu 2 boyut arasındaki oranın, yarım, af edersiniz, 2 olmasını istiyoruz. Orana nasıl baktığınıza bağlı olarak. Yani ben elemanların yaklaşık yarısının burada yukarda olmasını istiyorum. Bu nedenle yazı-tura atmasını istiyorum. Eğer yazı gelirse buraya çıkıyorum. Bu adil bir para.

Yani ben bunu 50,50 istiyorum. Bu durumda bu elemanların kaçı yukarı düzeye gitmek durumunda? Bu durumda yüzde elli olasılıkla. Sonra bir noktada daha yazı-tura atıyorum. Eğer yazı gelirse bir düzey daha yukarı çıkıyorum. Böylece bu, bu iki grup arasındaki yaklaşık oranı 2’de tutar. Ve beklenen oran tüm düzeylerde kesinlikle 2 olur. Eğer en üste gidip orada yazı-tura atarsam ve yine yazı gelirse bir düzey daha oluştururum. Araya yerleştirme algoritması budur. Çok basittir. Daha karmaşığını problem setinizde göreceksiniz.

Haydi bunu yapalım. Tamam ama birinin rastgele sayılar üretmesine ihtiyacım var. Kim rastgele sayılar üretebilir? Yarım rastgele? Ben size 25 kuruşu vereceğim. Burada bir tane var. Buyurun. Bu sıkıcı bir 25 kuruş. Kim rastgele sayılar üretmeyi ister? Şurada birisi başka birisini öneriyor. Bu, bunu yapmanın iyi bir yöntemi. Buyurun. Size 25 kuruşu veriyorum ama onu atmanızı izin vermiyorum. Sizin için rastgelelik yok. Aslında bitleri üretebilirsiniz. Ve ondan da bir sayı hesaplayabilirsiniz. Evet bana bir sayı verin. 44. Yanıt olabilir. Tamam. Yazı-turayı attık ve tura geldi. İş bitti. Bu araya yerleştirme algoritmasıdır.

Burada aslında biraz daha boşluk bırakacağım ve bunu en alta yazacağım. Tamam. 44 üst seviyeye çıkmamalı çünkü tura gelmişti. Şimdi bana başka bir sayı verin. 9. Tamam. Listede 9’u arıyorum. Pardon bir şeyi daha söylemem gerekli. Ufak bir değişikliğe ihtiyacım var. Bunun amacı aramaların çalışmasını garanti etmek. Buradaki endişe büyük bir sayıyı araya yerleştirdiğim ve onu üst düzeye taşıdığım zaman olur. Bu bir atlama listesi veri yapısında çok kötü görünür. Çünkü ben her zaman sol-üstten başlamak isterim ama şimdi bir sol-üst yok. Yani küçük bir ayarlama yapıyoruz. Bunu hatırlamamız gerek. Bu küçük değişiklik her listede özel bir değer eksi sonsuzu depolamaktır. Bu durumda eksi sonsuz her zaman en üste gider ve o andaki en üst değerin de üstünde olur.

Böylece başlangıçta her zaman bir sol-üst değerim olur. Bunu daha önceden belirtmediğim için özür dilerim.

Böylece ilk başta elimde sadece eksi sonsuz olacak. Sonra 44’ü araya yerleştiriyorum. Diyorum ki 44 buraya gider, herhangi bir terfi yok, işim bitti. Şimdi 9’u araya yerleştireceğiz. 9 buraya gider. Şimdi eksi sonsuzdan 9’ a yazı-turayı atın, yazı. Gerçekten parayı havaya attı mı? Pekiyi, tamam. Tabii tabii daha önceden atmıştır. Kesin öyledir. Size sadece zor anlar yaşattırıyorum. Bu durumda yukarda burada 9 var. Bu eksi sonsuzu korumamız lazım. Böylece her şeyle birlikte o da terfi etsin. Şimdi bu güzel bir atlama listesi gibi görünüyor. Parayı tekrar atın. Tura. İyi. Tamam. Bu ideal bir atlama listesi gibi görünüyor. Bu çok iyi değil mi? Her defasında doğru çalışıyor. Şimdi bana bir sayı daha verin. 26. Tamam. 26’yı arıyorum. 26 buraya gidiyor.

Kesinlikle en alttaki listeye gidiyor. İşte 26. Sonra da 44’ü yukarı alırım. Parayı at. Tura. Tamam. Şimdi başka bir sayı verin. 50. Oo bu büyük bir sayı. Bunu aramak biraz zaman alacak ve onu burada bulacağım. 50. Yazı-tura at. Yazı, iyi. Böylece 50 terfi edecek. Bir daha at. Tura. Tamam. Hala makul bir sayı. Başka bir sayı? 12. Burada işlerin heyecanlı olması için biraz zaman gerekiyor. Tamam 12 buraya 9 ile 26 arasında giriyor. Siz beni bayağı uğraştırıyorsunuz. Tamam. Yazı-tura atın. Yazı geldi. 12 terfi ettirilecek. Biraz çalışmanız gerektiğini biliyorum ama biz buraya 12’yi bulmak için gelmiştik.

Biz en son aşağıya indiğimiz noktanın 9 olduğunu biliyoruz ve 12’yi terfi ettiriyoruz. O buraya araya yerleşiyor. Onu bu belirli linkli listeye yerleştiriyoruz; çok karmaşık değil. iki onikiyi birbirine linkliyoruz. Hala bir tür linkli liste gibi görünüyor. Bir yazı-tura daha atın. Tamam. Tura geldi. Bir sayı daha verin. 37. Hımmm. Bu iyi bir hafıza testi. 37, neydi 44 ve 50? Ve 50 ondan sonraki üst düzey. Bence elemanları değiştirmeye devam etmeliyim ve size de sürekli yazı-tura attırmalıyım. Evet. demin 37’yi araya yerleştirdik. Tura geldi. Bu uzun bir zincir olacak gibi görünüyor. Bu daha da kötü görünüyor. Tamam. Şimdi bana 50’den büyük bir sayı verin. 51. İyi yanıt.

Teşekkür ederim. Tamam. Tekrar yazı-tura at. Bir daha atın. Tura. Bir sayı daha. Bir dakika. Başka birisi bir sayı seçsin. Bu iyi gitmiyor. Ne dersiniz? 52. Güzel cevap. Yazı-tura at. Yine tura. Hiç şaşırmadım. Şurada birçok yazı elde etmiştik. Tamam bir sayı daha. 53. Teşekkür ederim. Yazı-tura at. Yazı,yazı. Tamam. Yazı, yazı, siz yazı-tura atmadınız. Tamam 53. Ama fikri anlamaya başladınız değil mi? eğer ardı ardına iki yazı gelirse eleman iki düzey yukarı gidiyor. Tamam. Şimdi artık gerçekten yazı-tura at. Yazı. Hele şükür. Yazıları bekleyip duruyordum. Eğer sırasıyla ardı ardına üç kez yazı atarsanız, üç seviye gidersiniz. Ve her defasında eksi sonsuzu terfi ettiririz. Tekrar bakın. Yazı. Aman Allah’ım. Bunlar daha önceden nerelerdeydi? Tekrar atın. Bu sefer umarım tura çıkar. Tura geldi iyi. Tamam, fikri anlamışsınızdır. Sonunda tahtadaki yer biter. Aslında çok yukarı gitmek oldukça ender bir durumdur. log n’ den daha yukarı gitmenin olasılığı nedir?

Bir diğer kolay logaritma hesaplaması. Her defasında yukarı gitme olasılığı yüzde 50’ dir. log n düzeyinde yukarı gitmenin olasılığı n’ de 1’dir. Çünkü yarımın logaritma n kuvveti, 1 bölü n’ dir. Aslında bu n’ ye bağımlıdır ama ben çok yukarı gitmeyeceğim.

Ve sezgisel olarak bu çok da kötü değildir. İşte bunlar atlama listeleriydi. Oranlar, beklenen türünden elde edilir ama bu oldukça zayıf bir kuraldır. Bu, bu değişikliklerin uzunluğu hakkında bilgi vermez. Ama sezgisel olarak oldukça iyidir. Ortalama olarak oldukça iyidir diyelim. Burada iki yarı rastgele işlem vardır. Birincisi sayı seçmekti ve bunun hakkında bir şey söylemek istemiyorum. Sayılar seçilmiş olabilir, sıralı olabilir, tersten sıralı olabilir, rastgele olabilir. Bilmiyorum. Bu nedenle arkadaşınızın söyledikleri önemli değildi, en azından önemli olmaması gerekir. Ama burada önem kazandı. Endişelenme, hala seviliyorsun. Hala 25 kuruşunu alacaksın. Ama algoritmanın ilgilendiği, yazı-turaların sonuçlarıydı. Ve bu veri yapısının yüksek olasılıkla hızlı olması söylevi sadece rastgele yazı-turalara bağlıydı.

Tamam, rakibinizin sayı seçimleri yazı-turalar rastgele olduğu sürece önemli değil. Çünkü rakibiniz, paraları bilmiyor. Yani paraların vereceği sonuçları bilmiyor. Yani bu durumda yazı-tura atışlarının ortalaması uygun olacaktır. Ama bizim iddiamız, ortalamada iyi olmasının ötesindedir. Sonucun her zaman iyi olmasını istiyoruz. Çok yüksek olasılıkla logaritma n olmasını. Yani örnek olarak, 1 eksi 1 bölü n için, olasılık log n olsun, 1 eksi 1 bölü n kare için, olasılık yine log n olsun. 1 eksi 1 bölü n’ nin yüzüncü kuvveti için olasılık yine log n olsun. Tüm bu söylemler, 100’ ün herhangi bir değeri için gerçektir. İşte gideceğimiz yer bu.

Tamam. Bir atlama listesinde nasıl silme yapacağınızı da belirtmeliyim. Elemanı bulun. Bunu her yerde silin. Yani silme işlemi karmaşık bir şey değil. Çünkü elimizde, bağımsız ve rastgele seçimler var. Ve bu elemanların hepsi bir şekilde birbirinden bağımsız. Yani bizi ilgilendirmiyor. Yani bir elemanı silmek onu atmak demek. Karmaşık kısım araya yerleştirme. Bir elemanı araya yerleştirdiğimde bunun ne kadar yukarı gideceğine rastgele bakıyorum. Bu, 1 bölü 2’ nin, i’ ninci kuvveti olasılığıyla i yüksekliğine gidecektir.

İyi. Zamanımı rahat kullandım. Burada bayağı eğlendim. Tamam, biraz daha hızlı gitmek zorundayım.

İşte teorem burada. Öncelikle tam olarak neyi kanıtladığımıza bakalım. Yüksek olasılıkla bu resmi bir kavram olacak ve bunu birazdan tanımlayacağım. n elemanı olan atlama listelerinde her aramanın maliyeti log n düzeyindedir. Teorem bu. Şimdi yüksek ‘’olasılıkla’yı’’ tanımlamam gerekiyor. Yani yüksek olasılığı. Ve bunun söylemi biraz uzun. Bu nedenle bunu WHP yani “yüksek olasılık ile” olarak kısaltabiliriz. Yani ortada rastgele bir olay varsa ve buradaki rastgele olay da n elemanlı bir atlama listesinde her aramanın log n düzeyinde olması ise E olayının yüksek olasılıkla gerçekleşmesinin ne anlama geldiğini bilmek istiyorum.

İşte tanım bu. Buradaki deyim; 1’ e büyük-eşit olan herhangi bir alfa için seçilebilecek uygun sabitler vardır. ..ve E bu olayda bahsedip durduğum bu olasılıkla gerçekleşir. Yani olasılık en az, 1 eksi 1 bölü n’nin alfa kuvveti düzeyindedir. Bu çok kesin olmadı ama şimdilik amacımızı karşılıyor. Eğer gerçekten resmi tanımı istiyorsanız ders notlarını okuyabilirsiniz. Genel sitede bu dersin özel ders notları var. Ve SMA sitesinde de Powerpoint notları var.

Ama buradaki sabitlerin seçiminde biraz incelik de var. Bu sabitin seçilmesi işi var ve bu sabitin de seçimi önemli. Ve bunlar ilintilidir. Ve bir de alfa var ve bunu istediğimiz gibi seçebiliyoruz. Ama sonuçta bunun gerçek olması için gerekli olan olasılığı seçeriz. Eğer bunun gerçek olması için olasılığı 1 eksi 1 bölü n’ nin yüzüncü kuvveti olmasını istiyorsam bunu yapabilirim. Alfayı 100 olarak belirlerim. Ve bu küçük sabit, n’ nin alfa kuvvetine kadar çok yavaş büyür.

Hata olasılığını elde ederim. Bu şeye hata olasılığı denir. Başarısız olma olasılığım, istediğim polinom için, polinomsal oranda küçüktür. Şimdi aynı veri yapısıyla, veri yapımı da düzenlerim. Bu alfaya bağlı olmaz. Herhangi bir alfa değeri için bu veri yapısı log n düzeyinde zaman alacaktır. Şimdi bu sabit alfaya bağımlı olacaktır. Yani, 1 bölü n’ nin yüzüncü kuvveti olarak istediğiniz hata olasılığı büyük olasılıkla 100 log n olacaktır. Ama hala log n. Tamam, bu aramanın koşma zamanının kuyruk dağılımıyla ilgili çok güçlü bir iddiadır. Bunun ne kadar güçlü olduğu konusunda size bir fikir vereyim.

BOOLE’ un eşitsizliğini kaç kişi biliyor? Olasılıkta ‘’union bound’’ yani birliktelik sınırının ne olduğunu kaç kişi biliyor? Bilmeniz gerekir. Bu ek C’ de var. Belki bu teorem aracılığıyla bunu bileceksiniz. İsmiyle bilmek iyidir. Bu, beklenenlerin doğrusallığıyla benzeşiyor. Başka birisine anlatmak için çok kolay. Beklenenlerin doğrusallığı: Hatırlıyor musunuz, olayların beklenenlerinin toplamlarını belirtmek yerine bunun toplamın bekleneni dediğinizi? Bunu beklenenin doğrusallığı olarak söylemek çok daha kolay. Şimdi sizi farklı bir şekilde test edeyim. Bir olaylar kümesi alıyorum. Ve bunların birlikteliğini alıyorum. Yani bu oluyor veya şu oluyor ve böyle… Şimdi. Bu k sayıda olayın ‘’inclusive OR’’ yani ayırtımıdır. Ve bunun yerine o olayların olasılıklarının toplamına bakarım.

Tamam. Kolay bir soru. Bunlar eşit midir? Bağımsız oldukları sürece hayır. Ama bunlar hakkında, bunların ilintisi konusunda herhangi bir şey söyleyebilir miyim? Daha küçük, evet. Bu şuna küçük-eşittir. Olasılık bakış açısıyla bunun sezgisel olması gerekir. Kitabınıza bakın. Tamam: çok temel, neredeyse küçücük bir sonuç. Bu bize ne söyler? Farz edin ki bir tür hata olayı. Bunun olmasını istemiyoruz. Tamam. Burada bazı harfleri karıştırdığımızı varsayalım. Farz edin ki yüksek olasılıkla gerçekleşen bir olaylar kümem var. Bunlara tümleyen diyelim. Şimdi farz edin ki burası şu deyim ya da komutun sonu ve tümleyeni büyük olasılıkla gerçekleşiyor.

Bu durumda ‘nin olasılığı çok küçük, polinomsal oranda küçük. Her istediğim alfa değeri için 1 bölü n üzeri alfaya eşit. Şimdi bir olaylar kümesini aldığımı farz edin ve diyelim ki k, n türünden polinomsaldır. Yani olmasını istediğim bir olaylar kümesini alıyorum. Bunların hepsi yüksek olasılıkla gerçekleşiyor. Bunlar sadece polinomsal olarak çok olabilirler. Şimdi bu sabite bir isim verelim. Buna c diyelim.

Şimdi bu olaylardan n’ nin, c’ ninci kuvveti kadar alalım. Bu olayların hepsinin gerçekleşmesinin olasılığı nedir? Çünkü bunların olan zamanda birlikte oluşması gerekiyor. Çünkü her biri çoğu zaman yüksek olasılıkla oluşuyor. Yani bar ve barın ‘’intersect’’ yani ara kesişimlerine bakmam lazım ve bunu sürdürmem lazım. Şimdi bunların hepsi yüksek olasılıkla gerçekleşiyor. Hepsinin gerçekleşme şansı nedir? O da yüksek olasılıklıdır. Alfayı değiştiriyorum. Birliktelik sınırı; bunların herhangi birinin başarısızlık olasılığını bana söyler; bunun başarısızlık olasılığı, veya bunun başarısızlığını, veya bunun başarısızlığını ve bu da bu değer yani her başarısızlığın olasılıklarının toplamıdır. Bunlar hata olasılıkları. Ben bunların her birinin en çok 1 bölü n üzeri alfa olduğunu biliyorum ve başlarında da bir sabit var. bunların hepsini toplarsam bunlardan sadece n’ nin c kuvveti kadar var. Böylece bu hata olasılığını alırım ve onu n üzeri c ile çarparım.

Böylece n üzeri c bölü n üzeri alfa elde ederim. Ve bu da 1 bölü n üzeri alfa eksi c olur. Alfayı istediğim kadar büyük seçebilirim. Böylece bunu c’ den çok daha büyük seçerim ve bu olay yüksek olasılıkla gerçekleşir. Buraları bayağı karışık yazdım ama bu olay bu nedenle yüksek olasılıkla gerçekleşir. Buradaki sabit ne olursa olsun, kaç olayı ele alırsam alayım, alfayı bundan daha büyük olacak şekilde ayarlarım.

Ve bu olay da yüksek olasılıkla gerçekleşecektir. Yani her aramanın maliyetini, yüksek olasılıkla log n düzeyinde olduğunu söylediğim zaman, sadece bir arama için bunun maliyetinin yüksek olasılıkla log n olduğunu söylemiyorum. Başka bir aramaya bakarsanız, onun maliyeti de yüksek olasılıkla log n olur. Yani söylemek istediğim, her aramaya baktığınızda hepsi yüksek olasılıkla log n düzeyinde zaman alacaktır. Böylece tek aramanın log n düzeyinde zaman alması, yapılan aramalar n cinsinden polinomsal ise yüksek olasılıkla hepsi için de geçerlidir.

Bu veri yapısını sürekli kullandığımı varsaymıyorum. Sadece polinomsal zamanlı olarak kullanıyorum. Ama zaten kimin polinomsal miktarda zamanı var ki? Burası MIT. Umarım bu anlaşılmıştır. Bunu birkaç kez daha göreceğiz. Evet? Algoritma, alfaya bağımlı değildir. Soru, algoritmada alfanın nasıl seçileceğiydi. Yani ona ihtiyacımız yok. Bu sadece bir çözümleme aracıdır. Yani mesafeyi arttırdıkça örneğin 10 log n’ den daha fazla olmasının olasılığı nedir, dersiniz. Bu yaklaşık 1 bölü n üzeri 10’dur. Bunun doğrusal olduğunu varsayalım. Bu durumda 20 log n’ den daha büyük olma şansınız nedir? Bu da 1 bölü n’ nin 20. kuvvetidir. Yani burada dikkat edeceğiniz nokta bu dağılımın kuyruğunun gerçekten hızla küçüldüğüdür. Ve alfayı kendinizi rahat hissetmek için kullanırsınız. Tamam. Alfayı 100 olarak seçebilirsiniz. Ve bu durumda n en az 2’ dir.

Yani başarısızlık şansınız 1 bölü 2’ nin, yüzüncü kuvveti kadardır. Bu çok çok küçük bir değerdir. Yani elinizde gerçek bir rastgele sayı üretici varsa, 1 bölü 2 üzeri 200’ e denk gelme şansınız oldukça küçüktür değil mi? Şimdi alfayı 256 olarak seçtiğinizi farz edin. Ve bu çok güzel bir sayıdır. 2 üzeri 256, bilinen evrendeki parçacıkların sayısından çok daha büyüktür; normal madde parçacıklarından. Yani bu durumda kara madde evrenindeki bazı kavramlara da girmiş oluruz. Yani bu gerçekten çok çok çok büyüktür. Yani evrende en sevdiğiniz parçacığı seçme şansınız bu orandadır. Yani 1 bölü 2’ nin 256. kuvveti kadar. Ya da daha da küçüktür. Yani alfayı 256 olarak seçerseniz algoritmanızın log n süresinden daha uzun süre almasının olasılığı bilgisayarınıza aynı anda bir meteorun çarpmasından, sel baskınından ve dünyanın patlamasından ve güneş sisteminde bir ışınlanma olmasından çok daha küçüktür. Daha devam edebilirim. İster misiniz?

Log n’ den daha büyük olmanız gerçekten olası değildir. Ne kadar olası değil; bunu seçmeniz gerekir. Ama algoritmanın buna bağımlı olmaması sadece çözümleme evresinde geçerlidir. Aslında aynı algoritma, çok hoş. Bazen sınırlar yüksek olasılıkla alfaya bağımlıdır. Algoritma alfaya bağımlıdır demek istiyorum. Ama burada bu bağımlılık yok. Tamam. Bu konudan biraz uzaklaşalım. Şimdi, savı hepiniz anladınız. Haydi biraz ısınalım. Bu veriye de ihtiyacımız olacak. Ama bu oldukça kolay. Önkuram, yüksek olasılıkla atlama listesindeki düzeylerin log n düzeyinde olduğudur.

Ben kesinlikle log n düzeyinde olduğunu düşünüyorum. Şimdi, bir şeyin yüksek olasılıkla gerçekleştiğini nasıl kanıtlarız? Gerçekleşme olasılığını hesaplarız; bunun yüksek olduğunu gösteririz. Bunu daha önce kendime de sordum. Yüksek olasılığın ne anlama geldiğini bilmesem bile aslında bunu önceleri kendime de sorardım. Şimdi, bunun gerçekleşmeme şansını, yani hata olasılığını hesaplayalım. Çünkü bu 1 eksi savımızdır. Bunun en çok c log n düzeyinde olduğunu söylemek istiyorum. Böylece bu olayın hata olasılığı nedir? Bu aslında bir olaya benziyor. Bunu kümeleştirmek için özel işaret içine alacağım. Bunların kesinlikle c log n düzeyinden büyük olma olasılığıdır. Yani, olasılığın çok küçük, polinomsal olarak küçük olduğunu söylemek istiyorum.

Peki, düzeyleri nasıl yapıyordum? Bir elemanı araya yerleştirdiğimde % 50 olasılıkla yukarıya gidiyordum. Ve atlama listesindeki düzey sayısı, tüm elemanların ne kadar yukarı gittiğinin maksimum değeriydi. Fakat maksimum. İşte bu karışık. Tamam. Maksimum beklenenini, bilinmeyen değişkenlerinden bir grup olursa hesaplayabilirsiniz; ortada bir beklenen vardır ve bir sabit vardır ve siz bunun maksimumunu alırsınız. Bu, beklenenin log’u gibidir. Ama biz daha kuvvetli bir deyim istiyoruz.

Elimizde Boole’ un eşitsizliği var. Ve bu polinomsal olarak çok sayıda şeyin olduğunu söylüyor. Diyelim ki n elemanımız var. Bunların her biri bağımsız, bağımlı olmalarıyla ilgilenmiyorum. Eğer bu c log n’ den daha yukarı giderse, düzeylerin sayısı c log n’den fazla olur. Yani bu en yüksek değerdir. Ve benim bilmek istediğim bu olayların herhangi bir n elemanı için gerçekleşip gerçekleşmediğidir. Yani sadece n ile çarparım. Bu kesinlikle en çok x’in üst düzeye geçme ihtimali çarpı n’ dir. Ve burada büyük-eşit log n olur.

Herhangi bir x elemanını seçtiğimde bu gerçek her eleman için aynıdır. Bağımsız olarak işlem görürler. Yani burada x üzerinde toplama yapıyorum. Ve bu sadece n’ nin bir faktörüdür. Anlaşıldı mı? Bu, Boole’ un eşitsizliğidir. Şimdi, x’ in üst düzeye geçme olasılığının c log n kere olması ihtimali nedir? Bunu daha önce log n için yapmıştık. 1 bölü n idi. C log n için bu, 1 bölü n’ nin, c’ ninci kuvvetidir. Bu n kere 2 eder. Daha açık olalım: 1 bölü 2’ nin c log n’ ninci kuvveti; 1 bölü 2’nin c log n’ ninci kuvveti, 1 bölü 2 üzeri c log n eder. Burada log n dışarı alınır ve n olur. n üzeri c elde ederiz. Böylece bu n bölü n üzeri c’ dir. Yani n’ nin c eksi birinci kuvvetidir.

Ve c’ yi istediğim gibi seçebilirim. Böylece c eksi 1’ i alfaya eşitlerim. Bütünüyle böyle düşünürüm. Özür dilerim, 1 bölü n üzeri c eksi 1. Teşekkür ederim. Bu küçük olsa iyi olur. Bu bir üst sınır. Böylece olasılık polinomsal olarak küçük olur. Benim seçme şansımın olması aslında bir numara. Bu sabiti büyük seçiyorum, alfaya göre büyük seçiyorum. Buradaki düşünce c büyüdükçe alfanın büyümesi. Böylece alfayı istediğim gibi seçip c’ yi ona göre ayarlıyorum. Burada bir şeyler daha söylemem lazım. Ama bunlar notlarda var. Alfayı istediğim kadar büyük seçebilirim. Böylece bu olasılığı polinomsal kümelerde istediğim kadar küçültebilirim. İşte bu kadar. Düzeylerin sayısı log n düzeyinde: Bu kolay değil miydi?

Kurallar ve eşitlik. Burada hatırlanması gereken, yüksek olasılıkla uğraştığınızda, Boole’ un eşitsizliğini kullanın ve bir eleman için doğru olan herhangi bir şey hepsi için doğrudur, işte bu kadar. n’ de bir faktör kaybedersiniz ama bu alfa içinde sadece 1’ dir ve alfa büyüktür: Büyük bir sabittir --- büyüktür. Haydi teoremi kanıtlayalım. Yüksek olasılıklı aramalar log n düzeyine mal olur. Şimdi, yüksekliğin log n düzeyinde olduğunu biliyoruz. Ama bu, bu şeyin ne kadar dengeli olmasına bağlı.

Bir aramanın, log n’ ye mal olması gerçekten zincirlerin ne uzunlukta olduğuna bağlı. Bir ikili ağacın aksine, yüksekliğin bir sınırı olduğunu bilmek yeterli değil. Böylece bu çözümleme için parlak bir fikrimiz var. Ve buna geriye çözümleme deniyor. Normal olarak, bir aramanın sol-üst köşede başladığını ve aradığınız elemana gelene kadar sola ve aşağıya gittiğini düşünürsünüz. Ben bunun tersine olan işleme bakacağım. Aradığınız elemandan başlıyorsunuz. Ve sol-üst köşeye varana kadar sola ve yukarı gidiyorsunuz. Bu iki yolda da adımların sayısı aynı. Ve burada bir algoritma uygulamıyorum. Sadece çözümleme yapıyorum. Yani bunlar aynı işlemler, sadece ters yönlüler. İşte böyle görünürler. Bir arama işleminiz var. Başlıyor, ve aslında alttaki listede bir düğümde sona eriyor.

Sonra, o aramada bir düğüme ne zaman gelirseniz, ya sola ya da yukarıya gidersiniz. Ne zaman sola, ne zaman yukarı gidersiniz? Bu aslında yazı-turaların sonuçlarına bağlıydı. Yani bu düzeyde o düğüm, terfi ettirilmiyorsa ve bu da tura geldiği durumlar için geçerliydi. Bu durumda sola gideriz. Bu aynı zamanda soldan geldiğimiz anlamına gelir. Veya yazı gelirse bu düğüm bir üst seviyeye terfi ettirilir. Aynı yazı-tura attığımızda yazı geldiği durumdaki gibi.

Bu geçmişte araya yerleştirme yaptığımız zaman olan olaydı. Sonra yukarı gideriz ya da oradan geliriz. Ve kökte dururuz. Burası başlayacağımız nokta; aynı şey. Yani ya kökte oluruz veya bunu eksi sonsuzda durduğum gibi de düşünebilirim. Tamam bunu biraz karışık anlattım. Bir tekrar yapayım. Normal olarak buradan başlarız. Her şeye geriden baktığımızda aslında gerçekleşen olay köşeli parantezler içinde. Böylece bu arama, aradığınız düğümde sona eriyor. Bu her zaman alttaki listede. Sonra şu soruluyor. Bu düğüm daha önceden terfi ettirilmiş miydi? Eğer ettirilmişse ben yukardan geldim demektir. Eğer ettirilmemişse soldan geldim. Bunun aşağıdaki zincirde bir yerlerde olması lazım. Ve bu her ziyaret ettiğiniz düğüm için geçerlidir.

Bu aynı zamanda yazı-tura atıp, düğümü o düzeyde araya yerleştirmiş olmanıza bağlıdır. Ama bunlar sadece bir grup olay. Şimdi olasılığın yazı olmasını ve olasılığın tura olmasını kontrol edeceğim. Bu her zaman yarımdır. Her yazı-tura attığımda, sonunda diğer yönde sonuçlanmasının olasılığı yarımdır. İşte sihir bu.ve ben burada bu olayların bağımsız olmasını da hiç kullanmıyorum.

Aradığım her eleman için, x’ in her değeri için bu başka bir aramadır. Bu olaylar bağımsız olmayabilirler. Bu durumda bile Boole’ un eşitsizliğini kullanabilirim ve sonucun yüksek olasılıkla log n düzeyinde olduğu sonucuna varabilirim. Bunu her olayın yüksek olasılıkla gerçekleştiğini kanıtlayabilirsem yapabilirim. Bir aramada yazı-tura atışlarının bağımsız olduğunu biliyorum. Ama bunun dışında her şey için, değişik aramalar için bağımsızlığa ihtiyacım yok ve bununla ilgilenmiyorum.

Pekiyi bu işlem ne kadar sürebilir? Bu yürüyüşü kaç kez yapacağımı bilmek istiyoruz. Aslında kök düğüme geldiğim zaman işim bitiyor. Pekiyi kök düğüme ne kadar çabuk gelebilirim? Yarım olasılıkla her adımda yukarıya giderim. Yukarı gittiğim adım sayısı en çok, düzeylerin sayısı eksi 1’ dir ve bu büyük olasılıkla log n düzeyindedir. Buradaki tek farklı fikir bu. Şimdi teoremi geliştiriyoruz. Yani bir aramada yukarı gidiş sayısı ---aslında gerçekte bunlar aşağı gidiş sayısı ama ikisi de aynı şey -- düzey sayısından daha azdır. Gerçekte aramadaki düzey sayısından daha fazla yukarıya gidemezsiniz. Ama araya yerleştirmede istediğiniz kadar yukarıya gidersiniz. Ama aramada bu sayıdan daha fazla gidemezsiniz.

Ve bu yüksek olasılıkla en çok c log n’ dir. Ön kuramda bunu kanıtlamıştık. Böylece yukarı gidiş sayısında bir sınırımız var. Hareketlerimizin yarısı, kabaca yukarı gidiş olacaktır. Pekiyi bu aşağı-yukarı aşağı gidiş sayısı mıdır? Tam anlamıyla değil. Bunun anlamı aynı olasılıkta olmalarının olasılığı yüksektir. Ama c’ yi yeterince büyük yapıp, şunu istediğim kadar büyük hale getirebilirim.

Diğer bir deyişle hareketlerin sayısı, yani aramanın maliyeti en çok yazı-tura atışlarında yazı gelmesinin c log n’ ye ulaşması kadardır, değil mi? Çünkü kavramsal olarak aramanın her adımında bir yöne gidiyorum ve ondan sonra bir yazı-tura daha atıyorum. Orada duran başka bir bağımsız para ile. Ve ya yazı ya tura geliyor. Bunların her biri bağımsız. Öyleyse c log n sayısında yazı gelene kadar kaç kez birbirinden bağımsız yazı-tura atmam gerekecek? Savımız, bunun yüksek olasılıkla log n düzeyinde olduğudur. Ama bunu kanıtlamamız lazım. Yani savımız bu. Şimdi orada bir parayla oturursanız ve c log n kadar yazı gelmesinin kaç atış sonunda olacağını bilmek isterseniz, sav bu sayının yüksek olasılıkla log n düzeyinde olduğunu söylüyor. Ve bunu kanıtlayabilirsem aslında yazı-turaların sayısı kadar olacak toplam adımlarımın log n düzeyinde olduğunu bilirim; çünkü yazıların sayısının c log n olduğunu kesinlikle biliyorum. Savımız, turaların sayısının bundan çok daha fazla olamayacağını belirtiyor. Dikkat edin burada c diyemiyorum. Tamam. log n’ yi elde etmiş olmam gerçekten önemli. Neden? Çünkü yüksek olasılıkla bu kavram n’ ye bağımlı.

Log n: Bu doğru. log n’ den daha büyük bir şey: Bu da doğru. n gibi. Buraya n koyarsam bu da doğru olacaktır. Ama buraya bir sabit veya log log n koyarsam bu doğru değildir. Burada log n olması gerçekten önemli çünkü benim yüksek olasılık kavramım burada yazılı olana bağımlı. Tamam. Şimdiye kadar her şey anlaşıldı mı? Neredeyse bitirdik, bu iyi çünkü zamanım bitti. Kusura bakmayın.

Yani burada hata olasılığını hesaplamak istiyorum. Yani burada c log n’ den daha az yazı gelme olasılığını hesaplamak istiyorum. Bu adımı atlamama izin verin. Yani biraz yuvarlak konuşacağım. En çok c log n kez yazı gelmesinin olasılığı nedir diye soracağım. Burada bu olayı çözümlemek için kaç yazı-tura atılacak para olması gerektiğini belirlemek istiyorum. Yani bu sabiti belirlemek istiyorum. Diyelim ki 10 tane c log n parası atmak istiyoruz. Şimdi bu olayın sonucundaki hata olasılığına bakmak istiyorum. Bu 10 tane c log n atışta en fazla c log n yazı gelmesinin olasılığına. Buradaki sav, bunun çok küçük olduğu. Bu 10 sayısına bağımlı. Sonra 10’ u çok büyük olarak seçeceğim. İşim bitecek ve hayatım biraz daha kolaylaşacak.

Aslında bunu size sormalıydım. Ama bu 6.042’ nin içeriği. Pekiyi. En çok bu kadar yazı gelmesinin olasılığı nedir? Aslında 9 tane c log n parası. Çünkü ortada 10 tane c log n atış var. En çok c log n yazı gelmesi için en azından 9 kez c log n tura gelmesi gerekir. Yani diğer atışların tura gelme olasılığı budur ve bu da bayağı küçüktür. Sonra burada bir permütasyon olgusu vardır. Eğer tam olarak c log n yazı varsa, bu c log n yazıyı 10 tane c log n para atışı içinde yeniden düzenleme yollarının sayısıdır. Yani bu sadece permütasyonların sayısıdır. Ama bu biraz büyük ve rahatsız edici. Bu ise gerçekten küçük. Sav, bunun çok küçük olduğu ve şunun da çok büyük olduğudur.

Bu sadece biraz matematik. Bunu hızlı geçeceğim. Böylece burada çok kalmayacaksınız. Ama bunu tekrarlamanız gerekir. Ayrıca “y choose x” yani ‘’x içinde y seç’’ in en çok, e y bölü x üzeri x olduğunu bilmeniz gerekir. Bu nedenle bu, en çok 10 c log n bölü c log n’ dir. Ve bu 10 olarak bilinir. Bunlar birbirini götürür. Şurada bir e kalır. Sonra bunu c log n’ ninci kuvvete yükseltirim. Sonra bunu 2’ nin 9 c log n’ ninci kuvvetine bölerim. Tamam bu nedir? Bu e kere 10 üzeri c log n bölü 2 üzeri 9 c log n.

Tamam. Bunun çok büyük olduğunu belirtin. Bu çok büyük değil çünkü burada bir 9 var. Haydi bunu hesaplayalım. Bu e kere 10 iyi bir sayı. Bunu yukarı koyabiliriz. Böylece e’ nin logaritması çarpı 10 elde ederiz, 10 kere e ve sonra c log n. Ardından aşağıda 2’ nin 9 çarpı c log n kuvveti var. Böylece bu 2 üzeri c log n her iki durumda da mevcut. Böylece bu 2 üzeri log 10 eksi 9, c, log n. Bunlar basit cebir. Şimdi belirleyeceğim, ama daha değil. Bu 1 bölü 2 üzeri 9 eksi log: Yani buradaki her şeyi ters çeviriyorum ve işareti de eksiye döndürüyorum. Ve bu benim alfam çünkü geri kalanı n.

Böylece bu, 1 bölü n üzeri alfa, alfa bu belirli değeri aldığı zaman. Yani 9 eksi 10 çarpı e, çarpı c’ nin logaritması olduğu zaman. Biraz garip bir değer. Ama buradaki incelik 10 sonsuza gittiğinde, 9 burada 10’ dan bir küçük olan sayıydı değil mi? Çalışmamız sırasında 1’ i, bir yerlerde çıkardık. Yani 10, sonsuza giderken, bu da temelde 10 eksi 1 oluyor. Bu 10’ un logaritması çarpı e. e aslında önemli değil. Buradaki husus, bunun 10 cinsinden logaritmik olması. 10 cinsinden doğrusal olan bir şey, 10 cinsinden logaritmik olan bir şeyden oldukça büyüktür. Buna ‘’abusive notation’’ yani, suistimale açık simgelem denir. Tamam. 10, sonsuza gittiğinde bu da sonsuza gider ve büyür. Ve burada bir c var. Fakat, istediğiniz her c değeri için, savınızda hangi c değerini kullanırsanız kullanın, alfayı dilediğimce büyük seçebilirim. Ve bunu büyük O’ daki sabit değeri değiştirerek yapabilirim; ve bu sabit burada 10’ dur.

Yani sav, büyük olasılıkla doğrudur. Hangi olasılığı seçerseniz, bu size alfayı verir. Siz bu sayıyı log n haline dönüştürmeye sürekli gayret gösterirsiniz. Bu büyür ve işiniz bitmiştir. Bu nedenle, savı log n düzeyinde para atışı olacak şekilde yüksek olasılıkla elde edersiniz.

Bunlar gerçekten ilginç konular; notları okuyun. Dersin sonunda çok hızlı gittiğim için de kusura bakmayın.