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 13

Günaydın. Geçen hafta bu dersin tasarımla ilgili yapılacaklarının çözümlemeden daha fazla olduğu bölümüne geldik. Bugün aslında çözümleme yapacağız, ancak bu bizi ilginç tasarım konularına sürükleyecek. Gelecek derste, bugün öğreneceklerimizi uygulamalı olarak kullanacağımız metodların olduğu gerçekten ilginç ve pratik bir probleme geçeceğiz. Bugün AmortizeÇözümlemeden Amortized Analysis’den bahsedeceğiz.

Bu konuyu motive etmek açısından şöyle bir soru soruyoruz; bir Kıyım tablosunun ne kadar büyük olması gerektiği sorusu. Evet, bir kıyım tablosu ne büyüklükte olmalıdır? Fikri olan var mı? Bir kıyım tablosu yaratmak zorundasınız. Bu tablo ne büyükte olmalıdır? Kıyım tablomuzun basit bir kıyım tablosu olduğunu ve çarpışmaları zincirleme ile çözdüğümüzü düşünelim. Tablonun büyüklüğü ne olmalı? İhtiyaç duyduğunuzun iki katı mı; bu ne büyüklüktedir?Örneğin,toplam eleman sayısının iki katı mı?Kıyım tablosunun boyutunu büyüttüğümde, acaba arama süresine ne olacak?

Kıyım Tablosunun boyutunu arttırdığım zaman acaba arama süresi ne oluyor? Genel olarak ne oluyor? Azalır, değil mi? Evet, kıyım tablosunu yeterince büyütürsem, aslında kıyım tablosunu doğrudan erişimli bir tabloya çevirmiş olurum. Yani en kötü durumdadüzey(1) zaman alır. Yani, bir anlamda; sizin cevabınıza bir dakika içinde geri döneceğiz. Kıyım tablosunu yapabildiğimiz kadar büyük yapmalıyız. Böylece arama ucuzlayacaktır. Pekiyi, madalyonun öbür yüzü ne ? Kıyım tablosunu büyütürsek, bu gereğinden fazla yer kaplayacaktır. Dolayısıyla, tablonun kaplayacağı yer yönünden, kıyım tablosunu olabildiğince küçük yapmalıyım.

Sonuç olarak, tablom büyük olsun istiyorum ve ideal olarak bunun yoludaha önce analizimizde tartıştığımız gibi n tane eleman için teta n düzeyinde bir tablo yaratmak. Çünkü tablomuzu teta n’den daha büyük yaptığımızda, arama süresindeki kazancımız, kaybedeceğimiz yere değmeyecektir. En azından olaya böyle bakabilirsiniz. Ancak bu başka bir sorunu ortaya çıkaracak. Tabloya kıyımlanacak eleman sayısını bilmiyorsam, Kıyım Tablosunun büyüklüğünü nasıl belirleyeceğim?

Pekiyi, ne kadar büyüklükte yapmalıyım? Evet, eğer n’i yani, eleman sayısını önceden bilmiyorsam acaba ne yapacağım? Bu sorunun çözümü oldukça zariftir. Çözüm, DynamicTables yani Dinamik Tablolar diye anılan bir stratejidir. Buradaki fikir, herhangi bir zamanda, tabloya kapasitesinden fazla eleman geldiğinde, başka deyişle tablomuz taştığında, tablomuz taştığı durumda tablomuzu daha büyütmek, yani daha büyük bir tablo haline getirmek. Kıyım fonksiyonunda eğer zincirleme metodunu kullanıyorsak Kıyım Tablomuzun taşması yada işlevini yapamaması diye bir durumdan bahsedemeyiz. Ancak eğer kıyımı açık adresleme ile yapıyorsak, o zaman bu durum oluşabilir. Ama yine de zincirlemeden bahsedelim, tablodaki eleman sayısı çok arttığında yapacağımız, Kıyım Tablomuzu büyütmektir.

Bunu örneğin C dilinde “Malloc” ile, Java dilinde “New” komutu ile yapıyoruz. Bu fonksiyonlarla daha büyük bir tablo yaratıyoruz. Eski tablodaki elemanları yenisine taşıyoruz ve eski tabloyu serbest bırakıyoruz. Bir örnek yapmakta yarar var.

1 büyüklüğünde burada bir tablom var ve şu an boş. İçine bir yerleştirme yapıyorum. Yani 1 elemanı tabloya kıyıyorum. Evet oturdu. Burada, bunu kıyarak yapmayacağım. Problemi soyutlamak için, sadece elemanları tabloya dolduracağım. Ancak bu Kıyımda da çalışacaktır.

Bu sabit büyüklükteki herhangi bir veri yapısında da çalışacaktır. Bir yerleştirme daha yapıyorum, oops, yer yok. Bir taşma söz konusu. Burada yapacağım, yeni bir tablo yaratmak; bu tabloda birazcık daha fazla yere ihtiyacım olacak. Eski tablomun büyüklüğünü 2’ye katlayıp, 2 büyüklüğünde bir tablo yaratıyorum. Eski tablomdaki değeri yeni tabloma kopyalıyorum. Eski tabloyu serbest bırakıyorum, böylece ikincielemanı tabloma ekleyebilirim. Yine aynı şeyi yaparsam,başka bir taşma olur. Şimdi tablomu 4 büyüklüğünde yapıyorum. Eski tablodaki elemanları yeni tabloya taşıyorum ve taşmaya neden olan üçüncü elemanı yeni tabloma yerleştiriyorum.

Buraya ekleme yapıyorum. 5 tane yaptım. Herhalde “denden” işareti kullanabilirim artık;bu daha akıllıca olur.Oops, ne yapıyorum, gene taştım. Şimdi de 8 büyüklüğünde bir tablo hazırlıyorum. Bunları oraya kopyalıyorum ve beşincielemanı yani 5’i yerleştiriyorum. Altı, yedi ve diğerleribu şekilde sürüyor. Herkes temel fikri anladı mı? Yani, her ne zaman bir taşma olursa varolan tablomun 2 katı büyüklüğünde bir tablo yaratıyorum. Şimdi bunun hızlı bir çözümlemesini yapalım.

Elimizden tane yerleştirme işleminden oluşan bir dizi var. “Bir yerleştirme işleminin en kötü durumdaki maliyeti nedir?”diye sorarsak..Bunlardan herhangi birinin en kötü durumdaki maliyeti nedir? Evet, n düzeyindedir; kopyalamanın maliyeti ne olursa olsun, örneğin kopyalamayı bir maliyetinde kabul edersek, sonuçta en fazla n+1 olur, çünkü aslında hepsini kopyalamamız gerekir. Yani, düzey Teta n’dir. Yani, n yerleştirme yapmam gerekiyorsa bu en kötü durumda bana n çarpı teta n yani teta n²’ye mal olacak bir işlem gerektirecektir.

Soru var mı? Anlattıklarım mantıklı geldi mi? Elinizi kaldırın. Doğru, bu n işlemin hepsi en kötü durum olmayacaktır, güzel. Ve aslında, bu yaptığım tamamen yanlış bir çözümlemedir. Çünkü,sadece bir tanesinin en kötü durum düzeyinde yani n düzeyinde olması tüm n’lerin teta n düzeyinde olacağı anlamına gelmez. Yani bu tamamen kötü bir analizdir. Yanlış bir analizdir. Aslında n adet yerleştirme en kötü durumda teta n kadar zamana mal olur. Teta n kare değil. Yani çözümlemede bizim en kötü durumdaki bir yerleştirmeyi teta n düzey olarak belirlediğimiz yere kadar doğru. Bu kısım ise, bizim yanlış adımımız. Ne zaman kanıtlarda bir hata görürseniz, hangi adımda yanlış yaptığınızı bilmek istersiniz, böylece burada kafanızın karışmadığından emin olursunuz!

Şimdi doğru çözümlememizi yapalım. ’ninci yerleştirmenin maliyeti olduğunu düşünelim. Bu Eğer i eksi 1 ikinin tam kuvvetiyse i’ye eşittir,.Aksi takdirde 1 değerini alır..Burada çalışırken, bu sadece bir önceki yerleştirmedeikinin tam kuvveti olduğunda gerçekleşti çünkü bu benim tablomun büyüklüğüydü. Bunun sonucu bir taşma oluştu ve bütün o kopyalamayı yapmak zorunda kaldım. Diğer durumlarda, mesela 6 için, yerleştirmenin maliyeti sadece 1’di;sadece yerleştirdim. Herkes bunu gördü mü? Şimdi küçük bir tabloda bunu daha açıkça görebiliriz. Bu ideğerleri ve buda i adımındaki tablonun boyutu, ve bu da i’nin yerleştirilmesinin maliyeti.i’ nin değerleri 1 den 10’a kadar.

i’nin boyutu, birinciadımda, 1. İkinci adımda 2. Üçüncü adımda 3’ü tabloya eklemek istediğimizde, tablonun büyüklüğünü ikiye katlamamız gerektiği içinbu 4. Ve 4 yerleşiyor. Daha sonra 5. Boyutumuz 8 oldu. 6’da 8. 7’de 8. 8’de 8. Ve 9’da tablo boyutumuz 16 oldu. 16 ve diğerleri.Boyutlar bunlar. Şimdi maliyete bakalım. Burada maliyet 1, tamam 1’i ekle. Buradaki maliyet, 1’i kopyalamalıyım ve 1 tanede yeni sayıyerleştirmeliyim.

Maliyet 2. Burada 2 tane kopyalama ve bir tane yerleştirme var. Maliyet 3. Burada sadece bir ekleme yapmalıyım. Maliyet 1. Burada 4 taneyi kopyalayıp bir tane ekleme yapacağım. Maliyet 5. Pardon? Bence öyle. Evet, bu i maliyeti. 5 için i maliyeti. Bu 5’se, bu da 2’nin kuvveti. Tamam, 1, 1, 1 ve 9 harcadım, sonra tekrar 1. Bu bizim harcadığımız. Parçalara ayırırsam maliyetleri görmek daha kolay olur. Şimdi bunu iki değermiş gibi yeniden yazalım, çünkü istediğimi eklemek içinherzaman bir maliyet olacaktır.

Kalan miktar için buralarda 1 harcamak zorundayım. Buralarda da 1ek, 2 ek, 4 ek ve 8 ek harcama yapmak zorundayım. Bu örnek şekli daha kolay anlaşılır yapıyor. Bu kopyalama ile yerleştirmenin kıyaslaması, tamam mı? Şimdi, eğer not tutuyorsanız, defterinizde birazcık boşluk bırakın, çünkü bu tabloya daha sonra geri döneceğim. nadetyerleştirmenin maliyetini sonradan burada toplayabilirim.

Bu n elemanın eklenme maliyeti sadece şöyledir; i, 1 ile n arasında değişirken ’lerin toplamı. Şu çözümlemeye göre bu da kaçınılmaz olarak n’ye eşit, artı n’ye kadar olan ama n’yi aşmayan ikinin bütün kuvvetleri toplandığında; eğer cebir işlemlerini düzgün yaparsam, bu log(n – 1)’in tabanı olur; bu da ikinin j ‘nci kuvveti olur. Yani n’ye kadar olan n’ye kadar olan 2’nin bütün katlarını toplarım. Bu nasıl bir dizi? Geometrik bir dizi, dolayısıyla en büyük terimle sınırlıdır. Burada en büyük terim hakimdir ve bu log(n -1)’in tavanıdır, yani en fazla n’dir. Diğer bütün terimler en fazla n’dir. Yani bu aslında en çok 3n’ye eşit yadaküçük. Bu da bizim göstermek istediğimiz teta n düzeyi; sadece cebir.

Dolayısıyla,bir yerleştirmenin ortalama maliyeti Θ (n) / n’dir; bu da Θ(1) olur. Yani bir yerleştirme için ortalama maliyet Teta1düzeyindedir, bu da kıyım tablosu yaratırken tam istediğimiz şeydir. Bazen, önceki yerleştirmelerden dolayı fazla maliyet ödemek zorunda kalırsınız. Toplamda n işlemin maliyeti n düzeyindedir. Bu Amortize Çözümlemenin nosyonudur ve eğer yaptığımız işlemler dizisine bakarsam, maliyeti bütün işlemlere dağıtabilirim, dolayısıyla da ortalama maliyet n düzeyinde kalacaktır.

Yani özetlemek gerekirse, Amortize Çözümleme ile bir dizi işlemde, her ne kadar bir veya birden fazla işlem pahalı olsa da, ortalama işlem maliyetinin küçük olduğunu çözümlemiş olduk.. Yani --nyani burada olasılık diye bir şey yok. Ortalamalardan konuşmamıza rağmen, hiç olasılıktan sözedilmedi.Genelde ortalama değerlerle çalıştığımızda olasılık hesapları da işin içinde olur. İşte size ortalama durumu veburada hiçolasılık yok. Bu en kötü durumdaki ortalama performanstır, çünkü n tane işlem en kötü durumda bana sabit miktarda bir zamana mal oluyor. n tane işlem tetan düzeyinde süreye mal olacak.

Her işlem maliyetli bir düzeyinde ama bu n işlemde amortize edilmiştir. Soru varmı? Evet, karıştırabilirsiniz, ama zorunda da değilsiniz. Yani basit amortize edilmiş çözümleme çok güçlü bir şey söylüyor. Size en kötü durum sınırlarını veriyorama her elemana ayrı ayrı bakmak yerine bunu dizi ölçeğinde gerçekleştiriyor. Aslında , kitaplar da üç tür Amortize yöntemi anlatılır.

Belki daha da fazla.. Bir zamanlar 2 taneydi; daha sonra üçüncüsü gelişti. O nedenle belki de dördüncüsü vardır. Birincisi aggregate yani topak diye çağrılan bir çözümlemedir. Ve bu biraz önce gördüğümüz yöntemdi; temelde n işlemin ne kadar süre aldığını çözümleriz.Bugün iki tane daha göreceğiz. Birine accounting yani hesaplama yöntemi, diğerine ise potential yani potansiyel yöntemi denir. Bu ikisi birinciye göre daha kesin sonuçlar verir çünkü her işlem için belirli amortize edilmiş maliyetler ayrılır.

Topak çözümlemesinin özelliklerinden biri, bir işlemin gerçekten neye mal olduğunu kolay söyleyemiyor oluşunuzdur. Bu durumda söyleyebilirsiniz;burada düzey 1 diyebilirsiniz. Okey? Ama hesaplama ve potansiyel yöntemlerinde, belirli bir işlemin neye mal olduğunu söylemenin kesinliklebelirlenebilen bir yolu vardır. Şimdi, ilk yöntemimizdeki gibi hesaplama metodunabakalım. Dolayısıyla, tamamen aynı örnek üzerinden gideceğiz. Bir bakıma bu örnekte, en kolayı topak çözümlemesi kullanmak. Burada, bir şekilde daha karmaşık bir tartışmaya girebiliriz.

Ama, bu metotların birçok durumda daha güçlü olduğu ortaya çıkacak. Yani, bu işi basit bir yaklaşımla yapacağım ama belli bir soruna farklı açılardan yaklaşıldığı zaman kavrayışınız da gelişecektir. Hesaplama yöntemi aslındakendinizi mali muhasebeci konumuna koymanızdır. Yani burada yapacağımız, i’ninci işleme hayali bir amortize maliyet yüklemek.

Buna şapkalı diyeceğiz ve sembolik olarak buna bir birim işin 1 dolar ayıracağız. Veri yapısını değiştirmek için süre gibi giderler var. Buradaki fikir maliyetlerini faturalamak. Yani “Bu işlem size 5 dolarlık bir bedele mal olacak” der gibi.. Ve bu bedel işlemi gerçekleştirmek için harcanır ama sonunda kullanılmayan bir bakiye de kalabilir. Dolayısıyla, kullanılmayan miktar daha sonraki işlemlerde kullanılmak üzere bankada saklanır.

Yani burada ödenecek bedel, şapkalı işlemi için yetersizse, parayı bankadan çekiyorsunuz.Böylece hapse düşmemeniz için sahip olmanız gereken özellik,acaba bu nedir? Bunu yapabilmeniz için,evet bunu yapabilmeniz için bankada paranız olması gerekir. Hangi matematiksel özellik bankadaki paranın yerini tutar? Evet, bunun 0’dan büyük veya eşit olması gerekiyor, doğru mu? Çoğu kişi bunu bilir.

Banka hesabınız hiçbir zaman eksiye düşmelidir. Başka bir deyişle, Amortize maliyetler eksi işlemlerin maliyeti, her zaman diğer işlemleri yapmaya yeterli olmalıdır. Aksi takdirde ileriye dönük borçlanırsınız. Amortize çözümlemede, en azından basit olanlarında, geleceğe dönük borçlanmayız. Burada şu toplama sahip olmalıyız: i, 1’den n’ye kadar değişirken, , lerin toplamı, ki bu gerçek giderlerdir ve bakiye hesap hiçbir zaman eksiye gitmemelidir; bu nedenle de maliyetler her zaman bütün n’ler için amortize maliyetlerle yukarıdan sınırlandırılmış olmalıdır.

Banka hesabının eksiye gitmemesi için,tüm gerçek maliyetleri topladığımda, bunları her zaman ödeyebilmem gerekir. Bu benim istediğim bedel. Bu da gerçekten neye mal olduğu. Olması gereken iyi durum, bir veri yapısındaki işlemlerin harcama maliyetlerinin, yani veri yapısının o ana kadar ki maliyetinin, insanlarao veri yapısını kullanmak için fatura ettiğim miktar tarafından karşılanabilmesidir.

Ve bu bütün n değerleri için geçerli olmalıdır. Ama dikkat edin bu bana, bir işlem için belirli bir miktarda bedeli önermenin yolunu da açıyor. Dolayısıyla, toplam amortize maliyetler, toplamdaki gerçek maliyetler için üst sınırı oluşturuyor. Toplam amortize maliyetler gerçek maliyetlerin üst sınırıdır. Bununla ilgili sorusu olan var mı? Dinamik Tablo konusunda bu yöntemi kullanarak örnek yapacağız. Şimdi, Dinamik Tabloya geri dönelim.

Şimdi bu durumda, bütün,i’inci ekleme için 3 dolar amortize maliyeti fatura edeceğiz; tüm i’ler için. Buradaki düşünce;1 dolar anlık yerleştirmenin maliyetini karşılayacak, 2 dolar da tablo boyutunu iki katına çıkarmak için depolanacak. Tablonun büyümesi gerekecek ve tablo boyutu ikiye katlandığında, sakladığımız dolarların 1 dolarınıen yenielemanı taşımak için, 1 dolarını da eski bir elemanın yerini değiştirmek için harcayacağız.

Şimdi örneğe geçelim. 8 büyüklüğünde bir tablom olduğunu ve tablomun boyutunun henüzikiye katlanmadığını hayal edelim.Yani, tabloda 4 elemanım var. Tablomda hiç dolarım yok. Beşincielemanın yerleştirilmesi işi geliyor. Bu eleman için 3 dolar maliyet gösteriyorum. 1 dolar elemanı tabloya yerleştirmeme yarıyor, geriye 2 dolar kalıyor. Dolayısıyla bu 2 doları elemanın yuvasında saklayalım.

Şimdi altıncıeleman geliyor. Bir kez daha, 3 dolar maliyet gösteriyorum, 1 dolarını yerleştirme için kullanıp, 2 dolarını tabloya yazıyorum. Bu böyle gidiyor, 2 dolar, kalan 2dolar. Dokuzuncuelemana geliyor sıra. Tabloyu ikiye katlıyorum. Şimdi 8’li tablodaki bütün elemanları yeni 16’lı tabloya kopyalıyorum. Pekiyi ne oluyor? Toplam 8 dolarım var ve kopyalamam gereken 8 eleman var. Mükemmel. Diğer turlarda her yuvada biriktirdiğim dolarlardan biri son turdaki elemanlardan birinin, diğeri de eski elemanlardan birinin kopyalanmasını karşılıyor.

Tamam, hepsi kopyalandı ve hiç para kalmadı. Dokuzuncueleman geliyor, 2 dolar ondan artıyor. Böylece devam ediyoruz. Bu tartışmada gördüğümüz gibi, eğer her eleman için 3 dolar fatura edersem, her zaman bu tabloyu ikiye katlamaları karşılayabiliyor.Buradaki tümevarımsal değişmez katlamadan sonra bankada parakalmaması. Şimdi 2 dolar koyarsam, ikiye katlama sırasında ödeme yapabiliyorum ve yine de aynı durumda kalıyorum. Bu durumda banka hesabı hiç bir zaman eksi olmuyor. Bu doğrulamamız gereken önemli bir değişmezdir. Bu yüzden Amortize maliyetler, gerçek maliyetler toplamının üst sınırıdır. Amortize maliyetlerin toplamı, i, 0’dan n’e kadar giderken, 3n’dir.

Toplam gerçek maliyetleri 3n ile sınırlandırdım. Bu tabloya geri dönelim ve bakalım ne oluyor. Buraya Şapkalı ‘yi ve banka bakiyesini ekleyeceğim. İlk yaptığım iş yerleştirme, bunun için 3 dolar istiyorum, değil mi?Ve yerleştirme yapıyorum. Geriye ne kaldı? 2 dolar.Aslında 2 dolar alırım ama sadece bir dolar kalır. Yani aslında birinci maliyeti düşük alıyorum. Birinci eleman hariç herkesten 3 dolar aldığımda bunun çalıştığını göstereceğim. Sadece birinci elemandan 2 dolar alacağım. Aslında birinci elemanda birazcık tasarruf edebiliyorum. Bundan3 dolar alacağım.

Pekiyi, işim bittiğinde, banka bakiyem nedir? Sadece bir elemanı kopyalamak zorundayım, dolayısıyla 2 dolar kaldı. Herkes benimle mi? Diğerinden 3 dolar alıyorum. Aslında bundan sonrakilerden hep 3 dolar alacağım. Burada 4 büyüklüğünde bir tablom var veüçüncüelemanı yerleştirdiğimde 2 eleman kopyalamak zorunda kaldım. Yerleştirmeden sonra tabloda sadece 2 dolarım kalır. Dördüncü elemanı ekledim, bu güzel çünkü bankada 4 dolarlık bir bakiyem oldu ve hiçbir şeyi kopyalamak zorunda kalmadım.

Şimdi, beşincielemanı ekliyoruz. 4 elemanı kopyalamak zorundayım. Bu da hesaptan karşılanıyor. 3 faturalıyorum, geriye 2 kalıyor. Burada basitçe bunlarahep 2 ekliyorum. Ve bu noktada hepsini kullanıyorum ve geriye 2 kalıyor;4 ve diğerleri. Dikkatinizi çekmek istediğim bir konu, burada 3 dolar talep edebilirdim. Ve böylece fazladan bir dolarım olurdu. Bu problem olmazdı çünkü hala 3n üst sınırı geçerli olurdu. Bundan, farklı veri tanımlamalarıyla amortize maliyetleri önceden karşılama yönteminin çalışabileceğini anlıyoruz.

Hepsinin aynı olması gerekmiyor. Amortize çözümleme yaparken çalışabilir tek veri tanımlama yöntemi vardır denilemez. Ben her işlem için 4 dolar talep edebilirdim. Ve bu da geçerli olurdu. Ama öyle anlaşılıyor ki işlem başına 2 dolar isteyemezdim. Eğer her işlem için 2 dolar alsaydım eksi bakiyeye düşerdim. Tamam mı? Bakiyem eksi olurdu; ama 3 dolar istersem işler yoluna girer. Değil mi?

4,5,6, bunları fatura edebilirim. Bu durumda daha gevşek bir sınır elde ederdik. Üst sınırın 3n’ye eşit veya 3n’den küçük olması yerine 4n veya 5n’ye eşit yada ondan küçük seçebilirdik. Ama 2n’yi denemiş olsaydım sistem çalışmayacaktı, çünkükopyalamak için gerekli paraya sahip olamayacaktım. Buraya geldiğimde 1 dolarım olacaktı ve tabloyu ikiye katladığımda 8 tane elemanı kopyalamam gerekecekti. Ve sadece 4 dolarlık banka bakiyem olacaktı, özür dilerim, eğer 2 dolar alsaydım, sadece 1 dolarım kalmış olacaktı.

Dolayısıyla bu şeylerin çalışması için birazcık oynamalısınız ve neyin çalışıp neyin çalışmadığını görmelisiniz. Yani, algoritma tasarımı için hiç algoritma formülü yoktur. Pekiyi, güzel. Şimdi kitabınızdan tablo küçülmesini okuyabilirsiniz. Tablonuzda varolan elemanları silmeye başladığınızda ne olacak? Şimdi tablonuzu daha küçük hale getirmek istiyorsunuz. Burada çok dikkatli olmalısınız; fizikteki histerezi kim hatırlıyor? Hayal meyal? Birkaç kişi? Histerez konusunda dikkatli olmalısınız. Eğer dikkatli olmazsanız, eleman sayısı ikinin kuvvetinin altına her indiğinde, siz de tabloyu yarıya indirirseniz, kendinizi dayak yiyor gibi hissedebilirsiniz. Ancak yeterli sayıda silme işlemi yaptıktan ve sistemde bir miktar bellek yarattıktan sonra küçülebilirsiniz.

Kitapta daha genel bir durum için bir çözümleme var. Pekiyi, hesaplama yöntemi ile şimdi herhangi bir sorusu var mı? Hesaplama yöntemi gerçekten çok çok şirindir. Ayrıca, birçok öğrencinin kullanmayı tercih ettiği metottur. Tamam mı? Öğrenciler anlayana kadar nefret ederler. Öğrendikten sonra, derin bir oh çekerler. Ancak çalışmaya başlamak ciddibir cesaret gerektirir. Ama çok etkileyicidir. İyi Potansiyel metot argümanlarıgerçekten tatlıdır. Ve biz bir dahaki sefere, bir tanesini göreceğiz., Dolayısıyla, bu konuyu gelecek dersten önce tekrar edip anlamanız önemli, çünkü gelecek derste Potansiyel Metodunu anlamış olduğunuzu varsayacağız. Yeterli reklamı yaptık sanıyorum.

Bence Potansiyel Metodu, Algoritmik çözümleme konusunda çok güzel sonuçlar veren bir metot; çok güzel sonuçlar ve çok güzel teknikler kümesi. Aslında ne olmaya özeniyorsunuz; muhasebeci mi, fizikçi mi? Fikir şu, muhasebeci veya bankacı olmak istemiyoruz. Fizikçi olmak istiyoruz. Bu banka hesabı, çözümleyeceğimiz dinamik kümenin potansiyel enerjisi. Pekiyi neden? Bu bize bir yayın yaptığı gibi bir iş üretiyor. Potansiyel enerjiyi öğrenirken veya bir eşyayı daha yükseğe koyarken ve yer çekiminin onu çekerken yaptığıiş gibi. Dinamiği potansiyele çevirmek ve burada yapacağımız da tam budur. Ve bu matematiğe benzer, ama bu uygulamada sürekli matematik yerineayrık matematik kullanacağız.

Potansiyel metodun çerçevesi şöyle: Önce gibi bir veri yapısı ile işe başlıyoruz, ve i işlemi ‘i , ’ye dönüştürüyor. Buradaki veri yapısındaki işlemlerin eşlemleme gibi çalıştığını görüyoruz; bir veri yapısını başka bir veri yapısına, öncekinden sonrakine yapılan eşlemleme. Tamam, bu zaten matematikseldir. Ve tabii ki, i işleminin maliyeti olarak kalacaktır. Şimdi potansiyel fonksiyonu olan fi’yi tanımlayacağız ve fi, veri yapısı kümelerini reel sayılara map edecek yani eşlemleyecek.

Şimdi tüm veri yapılarıyla ilintilendirilmiş bir potansiyel, reel ve genelde tamsayı olan potansiyeller elde edilir; burada bu durumda ф( ), 0’a eşittir. Dolayısıyla başlangıç potansiyelimiz 0’dır ve ф( ), tüm i’ler için 0’dan büyük veya 0’a eşittir. Dolayısıyla, potansiyel hiçbir zaman 0’dan küçük, eksi bir değer olamaz; tıpkı banka hesabı gibi. Çünkü aslında potansiyel hesaplama metodundaki banka hesabınıtemsil ediyor. Evet, potansiyelimizin hiç bir zaman eksi olmasını istemiyoruz.

Aslında, bazen potansiyel fonksiyonların kullandığı bu iki özelliği de ihlal ettiğiniz zamanlar olacak. Bazı karmaşık ve enteresan potansiyel tartışmalarında kurala uymayan örnekler olabilir, ancak, bu sınıfta yapacağımız basit örneklerde bunun doğru olduğunu kabul edeceğiz. Ama bazen ф( )’ın0 olmadığını göreceğiz, bu bir şeyi değiştirmeyecek. Ancak, bizim çözeceğimiz örneklerde, potansiyel fonksiyon konusunda genel olarak ф( )’ın0 olacağını varsayacağız.

Şunu bilmenizi istiyorum, burada göstereceğimiz potansiyel fonksiyon örneklerinden çok daha fazla ve geniş yer kaplayan potansiyel fonksiyon örnekleri var. Bu durumda, amortize maliyeti ф’ye göre şapkalı olarak tanımlayacağız ve öyle bir tanım ki eğer hatırlayamazsanız, bu formülü final sınavında yanınıza alacağınız hatırlama kağıdına not edin: Şapkalı eşittir artı ф( ), eksi ф( ).

Evet, bu potansiyeldeki değişimdir; yani potansiyel farkıdır. Bunu kısaca delta olarak analım. Bunun farklı durumlarda ne demek olduğunu görelim. Eğer delta 0’dan büyükse, yani bu sıfırdan büyük; şapkalı ile arasındaki ilişki nedir? Bu 0’dan büyük. Dolayısıyla Şapkalı , ’den büyüktür, öyle değil mi? Şapkalı , ’den büyük; bu ne anlama gelir?

Bu, i işlemini yaptığımda, işlemin maliyetinden daha fazlasını tahsil ettiğim anlamına gelir. Burada tahsil ettiğim fazla miktar bankaya gidiyor, yani potansiyel enerji olarak saklanıyor. Yani i işlemi, sonra kullanılmak üzere işi veri yapısında depoluyor. Benzer şekilde eğer delta , 0’dan küçükse, şapkalı , ’den küçüktür. Bu durumda veri yapısı i işlemini yapabilmek için depolanmış işten harcama yapılır.

Yani eğer bu 0’dan küçükse, potansiyelimdeki değişim, yani banka hesabımdaki miktar azalmış ve veri yapısı işlemin yapılmasını sağlamak için potansiyel enerjiyi harcamış demektir. Çünkü gerçek maliyet, amortize maliyetten fazlaydı. Potansiyel fonksiyona karşı muhasebe metodunu karşılaştırarak durumu incelerseniz; muhasebe metodunda benim amortize değerim bu olacak diyebilirsiniz. Yani “Banka hesabımı inceleyeyim, hiç bir zaman eksiye geçmediğinden emin olayım”. Potansiyel Fonksiyon argümanında ise, bir anlamda banka hesabımın ne olduğunu söylüyorsunuz.

Şimdi amortize maliyetleri çözümleyelim.. Bu yaklaşımlar arasındaki farklılıktır. Bir tarafta banka hesabını, öbür tarafta amortize maliyetleri belirliyorsunuz. Pekiyi o zaman bu neden devam etmek için mantıklı bir yol? n işlemin toplam amortize maliyetine bir bakalım. Bu şapkalı ’lerin,i 1’den n’e kadar değişirken oluşan toplamıdır. Bu toplam amortize maliyettir. Bu da şuna eşittir, yerine koyma ile hesaplarsanız: Şapkalı yerine şu formülü koyarsak;

Bu da; artı ф( ) eksi ф( ). Bu da eşittir .lerin toplamı. Şimdi bu terimleri topladığım zaman ne olacak? Bunun için kullandığımız matematiksel terim ne? Teleskop gibiiç içe geçiyor.Sol taraftaki her terim i değerini aldığında bir kezeklenir ve i eksi bir olduğunda çıkarılır; tabii ilk ve son terimler hariç. n için olan terim sadece eklenir ve 0 için olan terim ise sadece çıkarılır. Bu, iç içe geçme özelliğinden kaynaklanır;teleskop özelliğinden.Şimdi bu terim nedir? Bununla ilgili hangi özelliği biliyoruz?

Bu 0’dan büyük veya eşit. Bu da 0’a eşit. Dolayısıyla bu da, ’den yani C_i toplamlarından büyük veya eşittir. Bu yüzden Amortize maliyetler gerçek maliyetler için üst sınır olur ki, bu da bizim istediğimiz şey. Bazı amortize maliyetler gerçek değerlerin toplamının üst sınırıdır. Ancak burada amortize maliyetleri tanımlamak için önce potansiyel fonksiyonu tanımladık ve bundan yararlandık. Dolayısıyla, potansiyel fonksiyon; daha önce de söylediğim gibi hesaplamayada muhasebe metodu ile potansiyel metot arasındaki fark, birinde banka hesabının diğerinde ise maliyetin belirtilmesidir. Bir noktada potansiyel enerjiyi mi belirliyorsun, yoksa bir noktadaki maliyeti mi belirtiyorsunuz?

Tamam, ama her koşulda, bu sınıra sahip olacaksınız, ayrıca bu matematik çok daha güzel. Ben iç içe geçmeyi teleskop yöntemini seviyorum. Yani sonuçta, amortize maliyetler, gerçek maliyetlerin üst sınırı. Tablomuzun boyutunu ikiye katlamayı burada yapalım. Bunu çözümlememiz için, önce potansiyelimizi tanımlamalıyız. Aranızda bunu kafadan hesaplayabilen biri varsa, benden daha iyidir. Bunun için çok büyük ihtimalle birkaç saatimi harcayıp, boğuşabilirim;çünküben çok zeki değilim. Pekiyi, bu durumda bu kullanacağımız potansiyel fonksiyonu, 2i eksi 2 üzeri log i’nin tavanı.

2 üzeri log 0’ın tavanının 0 olduğunu varsayalım, çünkü bunun limitiçerisindeki değeri budur. 0’ın logaritması eksi sonsuz olur, dolayısıyla 2 üzeri eksi sonsuz 0 demektir. Bu matematiksel olarak uygundur; bunu varsayın. Pekiyi, bunu nereden çıkardım? Bununla biraz oynadım. Biraz önce sildiğim diziye baktım ve terse çevirme kullanarak potansiyel fonksiyonu tanımlamak oldukça kolay dedim. Ama amortize maliyetleri tanımlamak zor, yani hesaplama kısmını. Bu örnekte muhasebe metodu kullanmak daha kolay. Buna rağmen, ben size doğru potansiyeli bulursanız, potansiyel metotla da bunu yapabileceğinizi göstereceğim.

Sezgisel olarak bu,i’ninci işlemde banka hesabımızda ne kadar kaldığıdır. Çünkü bankaya her defasında 2i kadar para koydum ve bundan tablo katlamalarınınmaliyet kısmını çıkardım.Öyleyse önce ф( )’ın ne olduğunu gözlemleyelim. Sıfır. Güzel. Ve ф( ) sıfırdan büyük veya eşit. Neden öyle? Tüm i’ler için. Neden? Log i’nin tavanı en fazla kaç olabilir? Log i’nin tavanı ya log i’dir, ya da log i artı birdir. Öyle değil mi?

Yani en büyük değer log i artı bir. Eğer bu, log i artı bir ise, 2 üzeri log i artı bir, sadece 2i eder. Bu olabilecek en büyük değer, doğru mu? Dolayısıyla 2,üzeri log iartı 1, sadece, bunu öbür yoldan yapalım, i çarpı 2’dir, burası için i, burası için 2. Bu olabilecek en büyük değerdir; veya bu sadece log i’dir. Bu da 2i eksi i veya 2i eksi ..2i olur. Her iki durumda da 0’dan büyük. Öyle değil mi?

Bunlar benim iyi tanımlanmış bir potansiyel fonksiyona sahip olmam için gereken 2 özellik. Şimdi, buradaki ucuz olma özelliği, amortize maliyetlerin karşılanacağı anlamına gelmiyor. Ben kendi çözümlememi yapacağım ve bana gereken sınırları bulacağım. Ancak bu, düzgün potansiyel fonksiyon yazabilmem için gereken yazım kurallarını sağladığımı ifade ediyor. Şimdi hızlı bir örnek çözerek bunun ne anlama geldiğini anlayalım. Tablomda 8 yuva olduğu durumunu varsayalım, doğru yaptım mı?, evet, 8 yuva ve 6 tanesi dolu. Ф, 2i ye eşit olacak. Bu da 2 çarpı 6 eksi 2’nin ikincikuvveti.

Bu ne? Özür dilerim, eksi 2 üzeri log i’nin tavanı. i,6 olduğundan, log i de log 6 olur. Bunun tavanı üçtür. Bu eksi 2 üzeri 3, yani 8 olur. 12 eksi 8, 4 eder. Eğer bunu muhasebe metoduyla düşünürseniz, bunlar 0 olacaktı, bunlar da 2; muhasebe metoduyla da aynı şey elde edilir çünkü burası yarıyoldur, bütün 0’ları yazarsınız ve bunların herbirine 2 eklersiniz.Benim fonksiyonum aslında gerçek maliyetin ne olduğunu bana söylüyor. Anlaşıldı mı? Bu belirli bir potansiyel fonksiyonuyla ne anlattığımızın ifadesi..

Pekiyi şimdi, i’inci yerleştirmenin amortize maliyetini toplayalım. Bu tanım gereği, i’inci eklemenin amortize edilmiş maliyetidir. Ve bu eşittir, pekiyi nedir? Hala bir yerlerde yazılı olarak duruyor mu yoksa sildik mi? Galiba silmişiz. Tekrar yazabiliriz. Eğer i-1 2’nin tam kuvveti ise, i; değilse bire eşit.Bu ’dir; şuradaki terimdir. Artı ф( ), bu nedir?

ф( )şuradakidir.Artı parantez içerisinde 2i -- eksi 2 üzeri log i’nin tavanı -- eksi parantez içerisinde 2 çarpı i eksi 1 -- eksi 2 üzeri log i-1’in tavanı. Bu amortize maliyetimizdir. Güzel bir formül, değil mi? Umalım ki, biraz sadeleşsin. Bu eşittir, burada i ve 1var, eğer bir şeyler, artı, pekiyi, burada iptal edeceğimiz bazı şeyler görülüyor; özellikle bu var. Burada 2i burada eksi 2i var. Bunlar gider. Burada eksi eksi2 kalır. Bu artı 2 olur. Şimdi eksi bu terim, artı bu terim.

Bu daha güzel ama hala karışık. Durum çözümlemesi yapmamız gerekiyor. Neden durum çözümlemesi yapmamız anlamlı? Burada bir eğer durumu var. O zaman durum analizi yapmamız gerekiyor.. Peki, öyleyse 1’nci durumda, i eksi 1, 2’nin tam kuvveti. Bu durumda Şapkalı eşittir; şimdi yani sadece i. 1’nci durum bu. Ve geriye kalanımız var, artı 2, eksi 2 üzeri log i’nin tavanı, eksi 2 üzeri log (i eksi 1) tavanı.

Buda i artı 2.. Şimdi bakalım,eğer i eksi bir, 2’nin tam kuvveti ise, bu terim neye eşit olacak? n_i eksi bir 2’nin tam kuvveti. Evet. Burası artı, teşekkür ederim, bundan dolayı da özür diliyorum. Sizin gibi öğrencilerimin olması iyi çünkü benim matematiğim gerçekten kötü. Aslında bu benim iyi bir teorisyen olmamın da temel nedeni, çünkü hiç bir zaman yazdıklarıma güvenmedim. Bir şekilde kontrol edebileceğim biçimde yazıyorum, aksi halde, 5 denklemi aynı anda çözebilecek kadar zeki değilim ve sadece hepsinin düzgün dönüşmesini umuyorum.

O zaman yazacaksınız.. Ben her zaman yazarım ki yazdığımı doğrulayabileyim. Ne mutlu ki, bunun bir başka güzel yan etkisi, diğer insanlar da yazdıklarımı anlayabiliyorlar. Pekiyi bu bir ne olur? Bu, 2 üzeri log i – 1; tavan yüzünden, eğer bu 2’nin tam kuvveti ise, 2 üzeri log i eksi birin tavanı sadece log i eksi birdir. Bu, 2 üzeri log i eksi bir, böylece bu da i -1’dir, değil mi? O zaman, eğer bu 2’nin tam kuvveti ise, log bir tamsayıdır, doğru mu?

Dolayısıyla, tavanını almak bir şey ifade etmez, tavanı görmezden gelebilirsiniz..Ancak, bu 2’nin tam kuvveti değil. Ama bu ne? Bu, bundan sadece bir fazla. Biz i-1’in 2’nin tam kuvveti olduğunu biliyoruz, dolayısıyla, bu bir üst sayı olacak. Bu ne anlama geliyor? Bu ikisini nasıl karşılaştırırız? Bu bundan ne kadar daha büyük? Büyüklük olarak 2 kat. Bunun ne olduğunu da biliyoruz.

Veya birinci terimden bu sonucu çıkartabiliriz. Burası log i eksi 1 artı bir olacak. Bunu bu haleindirgeyebilirsiniz. Dolayısıyla bu taban ve tavanları düşünmelisiniz, değil mi? “Bu yuvarlamada neler oluyor?” diye. Şimdi bunu sadeleştirebiliriz. Burada neyimiz var? Eğer bunlarıaçarsam, i, artı 2, eksi 2i, artı 2, artı i, eksi 1. Biliyorum ki birçoğunuz, büyük ihtimalle %90’ınız bu adımı yapmayacak. Buradan doğrudan son adıma geçeceksiniz. Burası aslında %30’unuzun veya bir grubun yanlış yapacağı yer.

Bana bu adımı yapmanız için sizi cesaretlendirmeme izin verin. Eğer yavaş giderseniz, hatalarınızı bulmak daha kolay olur. Aslında uzun vadede, yavaş gitmek daha hızlı bir yöntemdir. Genç atlara öğretmek daha zordur. Biraz rahatlayın. Biraz sabır, yavaş yapın ve doğru sonucu alın. Bu gerçekte daha hızlı. Herkes tavşanla kaplumbağanın hikayesini biliyor değil mi? Evet, tabii, ama kimse bu hikayeye inanmıyor. Pekiyi, burada 2i’miz var, burada i ve burada i. Bu bize 2 artı, 2 eksi bir eşittir 3verir. Mükemmel. Müthiş, amortize maliyetimiz, i eksi bir,ikinin tam katıyken 3 oluyor.

Şimdi de 2nci durumu inceleyelim.i eksi bir 2’nin tam kuvveti değilken oluşan durum. Şapkalı , şimdi i yerine 1 alıyoruz..1, artı 2, eksi 2 üzeri log i’nin tavanı, artı 2 üzeri log i eksi birin tavanı olur. Bu iki terimin, i eksi 1,ikinin tam kuvveti değilken ne olduğunu kim söyleyecek? Bunlar Nedir? Eşit. Evet..Neden? Çünkü tavan işlemi ikisine de aynı etkiyi yapıyor, bu da onları aynı tam sayıya getiriyor. Dolayısıyla bu ikisi birbirine eşit, bu da bunun 3’eeşit olduğu sonucunu veriyor.

Tamam, n tane yerleştirme işlemi var. Şimdi her yerleştirme işlemi için 3’lük bir amortize maliyetim olduğunu söyleyebilirim. Dolayısıyla n tane yerleştirme, n tane amortize edilmiş maliyete neden olur. Yani n tane yerleştirme de,3n amortize maliyetine eşittir. Bu gerçek maliyetin en kötü durumdaki üst sınırıdır. Böylece n tane yerleştirme en kötü durumda tetan düzeyinde maliyet gerektiriyor. Çözümlemede bir hata var; küçük bir hata. Daha önce birinci eklemenin 3 yerine 2’ye mal olduğunu anlatmıştım.

Bununla yeterince dikkatli ilgilenmedim. Bu sadece bir egzersiz ve bunun nerede olduğuna ve nasıl açıklayacağınıza bakın. Aslında ilk eklemenin amortize maliyeti ikidir. Özetlemek gerekirse, amortize çözümlemenin sonuçları: Amortize maliyetler bize veri yapısı başarımının temiz bir soyutlamasını vermektedir.

Burada varsayalım ki dinamik bir tablo yaratıyorum. Bu tabloya her yerleştirmenin sabit miktarda zamana mal olduğunu söylemek sizin kendi başarım modeliniz açısından daha kolaydır. Gerçek zaman davranışlarıyla ilgilenmediğiniz müddetçe, sadece bütünleşik yani toplam davranışı incelediğiniz sürece, bu başarım için güzel bir soyutlamadır. Bu, bazen size pahalıya mal olan karma karışık şeyleri anlatmaktan daha iyidir; bununmantığını nasıl kurarsınız? Her bir işlem bana 1 düzeyine mal oluyor diyebilmek, gerçekten basittir. Ama şunu anlamalılar; bu amortize yaklaşımda 1 düzeyindedir. Öte yandan, eğer gerçek zamanda çalışmayı umursuyorsanız, amortize metodu size yaramaz.

Tamam, ama birçok problem için bu mükemmele yakın derecede iyidir. Bana bunun neden basit olduğunu daha kolay anlatma şansı verir. Farklı işlemlerin farklı amortize maliyetleri olduğundan başka veri yapılarının da amortize maliyetlerine bakacağız. Burada güzel olan, farklı işlemlerin maliyetlerini sadece toplayarak istediğim sonuca ulaşabilirim. Her işlem farklı maliyete sahiptir; bazıları log n olur, bazıları düzey 1 veya başka bir şey olur. Hepsini toplayın, bu gerçek maliyetlerin üst sınırı olacaktır. Bu, bahsini ettiğimiz karmaşık veri yapılarının mantığının çözülmesi ve soyutlandırılması için büyük bir sadeleştirmedir. Bu gerçekten çok kapsamlıdır. Soyutlama, bilgisayar biliminde, size 4 yıl boyunca lisans düzeyinde öğretilenler, master yaparsanız 1 sene daha gösterilenler ve eğer doktoraya devam ederseniz, bu bir başka 15 yıl veya ne kadar sürüyorsa..

Öğretilenler tamamen soyutlama, soyutlama, soyutlama, soyutlamadır. Bu da güçlü bir soyutlamadır, oldukça iyidir.

Şimdi 3 yöntem öğrendik. Genel olarak herhangi biri kullanılabilir. Birini diğerine çevirebilirsiniz. Her birinin kendi nitelikleri vardır ama duruma göre bunlardan birisi en basit yada kesin sonucu verir.Dolayısıyla herhangi biri kullanılabilir; ancak siz hepsini öğrenmek zorundasınız, çünkü bazı durumlarda metotlardan birine, bazen da diğerine ihtiyacınız olabilir. Eğer ilgili kitapları, makaleleri okuyorsanız, bu farklı yolları bilmek isteyeceksiniz. Siz muhasebe yöntemiyle rahat bile olsanız, sınavda veya başka bir yerde, sizden potansiyel fonksiyon yöntemi ile çözüm istemeyeceğim anlamına gelmiyor.Yani bütün metotlarla rahat olmak isteyeceksiniz.

Bir son nokta, aslında farklı potansiyel fonksiyonlar veya muhasebe maliyetleri farklı sınırlaryaratabilir. Amortize analiz yaptığınızda, bir grup maliyetin, diğerinden daha iyi olduğunu söylemenin hiç bir anlamı yoktur. Sadece örnek olarak, genellikle silmeyi destekleyen herhangi bir veri yapısında, bütün silmeleri yerleştirmelere karşı amortize edebilirim. Genel olarak, silmelerin bedava olacağını ve her yerleştirmenin iki kat fazlasına mal olacağını söyleyebilirim.

Silmeyi amortize etmek için yerleştirme yaparken yeterli tahsilat yapmayı hesaplama metodu ile yapabilirsiniz. Bunu potansiyel metodu ile de yapabilirsiniz. Her bir eleman için potansiyel, veri yapımında var olan elemanların sayısı çarpı her bir silmenin maliyetidir. Anlatmak istediğim, maliyetleri farklı yöntemlerle ayırabilirim. Veya gerçek maliyetlere eşit amortize maliyetlerim olabilir. Sadece tek yol yok vefarklı yollar seçmek farklı sınırlar yaratabilir. Yaratmayabilir ama yaratabilir de..Geneldede farklı sınırları yaratır. Bir dahaki sefere, potansiyel fonksiyonların şaşırtıcı kullanımını anlatacağım. Bugünkü iyiydi ama gelecek ders muhteşem olacak. Muhteşem bir çözümleme türünü ele alacağız.

Dersimiz burada bitmiştir.