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 Introduction to Algorithms, Fall 2005. (Massachusetts Institute of Technology: MIT OpenCourseWare). http://ocw.mit.edu (Giriş Tarihi:  08, 01, 2010).                              

Lisans: Creative Commons Attribution-Noncommercial-Share Alike.

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 2

 

Benim adım Erik Demaine.. Bana Erik diyebilirsiniz.. 6.046’ya tekrar hoş geldiniz; bu ikinci dersimiz..

Bugün esas olarak birinci dersteki konuların matematiksel temellerini genişleteceğiz.

Birinci derste, algoritmaların çözümlenmesi, araya yerleştirme sıralaması ve birleştirerek sıralama konularına bir giriş yapmıştık. Bu iş için bazı araçlara gereksinim vardı ve biz de parlak bir fikir olan asimptotikler kavramını ele aldık; katsayıları ve formüllerin en  büyük  terimleri dışındakileri hesaba katmadık. Bu nedenle bugün, asimptotik simgelem’in matematiğini iyice kavrayana kadar geliştireceğiz.

Yine geçen dersin sonunda, birleştirerek sıralamadaki öz yineleme olgusu ve koşma süresini irdeleyerek yinelemeleri nasıl çözeceğimizi görmüştük.

Bugün de bu iki kavram üzerinde duracağız.  

 

Soru mu var? Pekiyi daha yüksek sesle konuşurum. Teşekkürler.. Mikrofonum var ama sesimi yeterince yükseltmiyor..

 

Haydi, asimptotik simgelem ile başlayalım.. Basit asimptotik simgelemi daha önceden görmüştük.. Eminim ki bu simgelemle, daha önce aldığınız derslerde de karşılaşmışsınızdır; örneğin  “büyük O-simgelemi” gibi kavramlarla.. Ve bugün biz bunun kesin tanımını yapacağız ki neyin doğru neyin yanlış, neyin geçerli neyin geçersiz olacağını bilelim.

Bugün tanım yapacağız; maalesef bugün matematik yoğun, hemen hiç algoritma olmayan bir ders olacak ve bu nedenle çok heyecan duymayabilirsiniz. Ama gelecek derste bugün öğrendiklerimizi gerçek algoritma uygulamalarında kullanacağız.

 

Bu “büyük O simgelemi”; büyük harf O simgelemi..  Elimizde n’nin f fonksiyonu eşittir büyük O’nun g( n ) eşitliği, yani f(n) = O[g(n)] var.

Bunun anlamı.. bazı uygun katsayılar vardır ki.. c > 0 ve  > 0 gibi -- yeterince büyük bütün n değerleri için f fonksiyonu cg(n) ile sınırlıdır. Bu sezgiyle kolay anlaşılabilecek bir kavram; bunu daha önce görmüştük.. Burada, f(n)’nin  eksi olmadığını varsayacağım ve üst sınırın da g(n) ile sınırlı olmasını istiyorum.

 

Bazı örnekler görmüştük, örneğin,   2 n²= O() eşitliğini tanımlayalım..

Bunun yaklaşık anlamı, eğer baştaki katsayıları ve düşük değerli terimleri hesaba katmazsak, denklemin solundaki değer, sağındaki değere küçük-eşittir. Yani büyük O, eşit ya da daha küçük anlamına gelir. Ama burada gördüğünüz bunun formal biçimlemesidir. Bu simgelemle ilgili komik olan yön, bunun simetrik olmamasıdır. Normal olarak denklemlerin simetrik olduğu düşünülür. Yani A eşittir B ise, B eşittir A söyleminin de geçerli olması gerekir. Ama burada durum böyle değil.

, n² nin büyük O fonksiyonu değildir; hatta ün büyük O fonksiyonu da n²’ ye eşit değildir. Birazdan bunun ne anlama geldiğini göreceğiz. …Ama bu evrede, …büyük O simgeleminin biraz garip bir simgelem olduğunu unutmayın ve hep anlamını düşünün.

Bu  simgelemin anlamını kavramanın bir diğer yöntemi de f(n)’nin, g’ye benzeyen bazı fonsiyon setlerinin içinde yer aldığını düşünmektir. Bu nedenle  g(n)’nin  büyük O’su..bir fonksiyon seti olarak tanımlanabilir.. adına  f(n)  diyelim.. ve bazı katsayılar olsun. Burada aynı tanımı yapıyorum:

c>0 ve >0.. yani f (n), 0’a büyük-eşit ve c ile  g(n)’nin  çarpımına küçük-eşit.. Tabii tüm n değerlerinin ’a  büyük-eşit olması koşuluyla..

 

Bu oldukça uzun bir tanımlama; bu nedenle yani her seferinde tanımı yeniden yazmak yerine simgelem kullanıyoruz. Şöyle düşünmelisiniz:

n²,  büyük O fonksiyonuna eşittir demek yerine, anlatmak istediğimiz şey 2 n² nin, ile oluşturulan büyük O setinin içinde yer aldığıdır.

Bu simgelemde eşit işaretini kullanırken, setin içinde anlamında kullanıyoruz, ve bu şekilde  kullanacağız.  Böyle de yazabilirsiniz; bu kısaltmanın kullanıldığı makaleler var ama biz bu anlamda eşit işareti kullanacağız. Bunun sonucunda da eşit işaretine, bu işarette olduğu gibi simetrik olmayan bir anlam yükleniyor.

 

Büyük O simgeleminde kullandığımız bazı hoşluklar var. Bunlardan biri de simgelemi bir makro gibi kullanmak..

Bugün kapsamamız gereken çok konu var; onun için biraz hızlı gideceğim. Bu nedenle anlamadığınız bir şey olursa, beni soru sorarak durdurun ve yavaşlayayım. Aksi halde her şeyin anlaşılmış olduğunu kabul edip tam hızla devam edeceğim.

 

Makro uzlaşımı, … daha önceleri makro programlama ve benzeri çalışmalar yaptınızsa, size tanıdık gelecektir.  Ama buradaki anlatım biraz daha matematiksel olacak...

Biz büyük O simgelemini bir şeyin büyük O’suna eşit olarak tanımladık. Ve büyük O’yu da sadece eşit işaretinin bir yanında, bir fonksiyonun büyük O’su olarak tanımladık. Öte yandan eşitliğin sağ tarafında büyük O’yu içeren genel bir ifadenin olmasında yarar vardır.

Örneğin, şöyle bir eşitlik yazalım: f (n)= + O(n²). Burada amacımız hata sınırını belirlemek. Diyoruz ki, f(n) aslında ’tür ama bu denklemde O(n²) olarak anılabilecek düşük düzeyde değerler de var.. Ve bunun da anlamı; f(n)’yi,  fonksiyon sözcüğünün kısaltması olarak kullandığımda,  n’nin h fonksiyonu olarak tanımlanan bir fonksiyonumuz var –- ve bu büyük O(n²) nin içinde.. yada büyük O(n²)’ye eşit. böylece f(n) = + h(n).

Yani diyoruz ki, yeterince büyük n değerleri durumunda, bu ifadede bir katsayı ve n² ‘nin çarpımı ile üst sınırı tanımlanmış düşük düzeyli terimler var.. buradaki terim gibi.. Bu durumda f(n), (dikkat edin şimdi gerçek bir eşitlikten söz ediyorum), artı bu hata terimine eşittir. Bu yaklaşım, bu anlatımda çok yararlı..

Özünde ön sabiteyi tanımlıyorum..  ve diyorum ki üst sınırı en çok n² olan başka değerler de var..

f(n), ’e bağıldır da diyebilirdik ama bu daha zayıf bir deyim olurdu. Bizim anlatımımız daha detaylı… Bu yaklaşımı çok sık kullanmayacağız ama bilmekte yarar var. Ama bazen karşımıza çıkacak; örneğin geçen derste büyük O bir toplama işleminin içinde yer almıştı. Yani bunları her yerde kullanabilirsiniz; unutmamanız gereken o setin içinde bir fonksiyonu temsil ettikleridir.

 

Büyük O bir denklemin sol tarafında yer aldığında, anlamı biraz daha zor anlaşılır, biraz daha incelikli hale gelir.. Aslında aynı bağlamda kullanılır ama bu durumda eşitlik kavramı başka bir uzlaşım gerektirir. Bu nedenle de eşit işareti bakışımsızdır, yani simetrik değildir. Eşittir yerine “içindedir” ifadesini kullanmalısınız.  İçindedir, buradaki her şey, şuradaki bir şey anlamındadır şeklinde yorumlanmalıdır. Yani sol taraftaki her şey için bir varsayılan varsa, bu sağ taraf için de geçerlidir. Bu gerçek bir deyimdir. + O(n) olan her şey aynı zamanda O(n²) dir ama, bunun tersi geçerli değildir. Yani ortada asimetrik yani bakışımsız bir durum vardır ve düşündüğünüzde kolay anlaşılsa da dikkatli olmanız gerekir.

 

Bir eşitliğin sol tarafındaki makroda herhangi bir artış varsa ( ki bu f(n) olmalıdır), eşitliğin geçerli olması için sağ tarafındaki makrolarda da artış olmalıdır..

Buna göre, elinizde “içindedir” anlamıyla kullandığınız eşit işaretleri zincirinden oluşan denklemleriniz varsa, en baştaki terim en son terimle sınırlıdır yada sonuncuya eşittir.Yani eşit işaretlerini normalde zincirleme kullanabilirsiniz.. Ama yerlerini değiştiremezsiniz, ters çeviremezsiniz.

Pekala.. Bu büyük O simgelemidir..  Sorusu olan var mı?

 

Evet, büyük O üst sınırların tanımlanmasında çok yararlıdır. Ama alt sınırlarla da ilgili konuşmalıyız. Algoritmalarda, üst sınırlara koşma süreleri bağlamında ilgi duyarız. Koşma süreleri, en çok n²  değerine, büyük O’ya kadar da en çok n log n değerine ulaşır, ama bazen belirli bir minimum değere ulaşabilen fonksiyonları da tanımlamak zorunda kalırız. Örneğin, belli bir modelde sıralamanın en az n log n zamanını alacağını göstereceğiz. Bunun için de başka bir simgeleme ihtiyaç var..

 

Bu simgelemi adı da büyük Omega simgelemi.... ve oldukça simetriktir.

Set tanımlamasını buraya yazayım…  f(n) =büyük Omega[g(n)] olarak yazacağız ve bu yeterince büyük n değerleri için, f(n)’nin en azından g(n)’nin bir katsayı ile çarpımına eşit olduğu anlamına gelecek.. Temelde f ve g arasındaki eşitsizlik ilişkisini tersine çeviriyorum.. Böyle tanımlanması çok şaşırtıcı değil.. Konunun daha derinlerine inmek için rastgele bir örnek verelim:

 
Karekök n = büyük Omega (log n). Ve bunu şöyle yorumlamalısınız: yeterince büyük n değerleri için, bazı sabit faktörlere kadar karekök n en azından log n’dir. Yani Omega , büyük-eşit anlamına gelir. Size bazı analojiler vereyim:

Büyük O var.. büyük Omega var.. Büyük O küçük-eşit, büyük Omega büyük- eşit.. Birazdan buraya başka şeyler de yazacağım….

Elimizde bilinen işlemcilerin olması güzel; normalde kesinlikle küçük, kesinlikle  büyük ve eşit işaretlerine sahibiz.. Ve asimptotlar dünyasında işlem yaparken,  katsayılarla düşük değerli terimleri ihmal etmek için bu analogların, yani benzer değişkenlerin çözümlemelerini kullanacağız.  

Örneğin elimizde Teta [g(n)] var.. Bu büyük Tetadır ve ortasındaki çizgiyi boylu boyunca çizmek yerine ortalamalısınız… Yunancayı ben icat etmedim; böyle olması gerekiyor..

Teta sabitlenmiş faktörlere kadar, bir değere küçük- eşit ve bir değere büyük-eşit olduğu anlamına gelir ve bu nedenle büyük O ve büyük Omega setlerinin kesişiminde yer alır… Yani eşit işaretini andırır ama tabii çok farklıdır.. Katsayıları görmezden geldiğiniz  zaman n²,  2(n²)’nin  büyük Tetasıdır diyebilirsiniz..  Buradaki diğer tanımlamalara baktığınızda, tamam,                                             

 n²+ O(n) = büyük Teta (n²)’dir ama bu, teta ile yapılamaz çünkü n’nin karekökü log den asimptotik olarak daha büyüktür… Önceden gördüğümüz n²  ile arasındaki bazı ilintiler  de Tetaya uygun değildir.

Bir de stricts, yani kesinler simgelemi vardır ve.. bunlar küçük-o ve küçük-omega simgelemleridir. Küçük teta simgelemi yoktur, çünkü kesin eşitlik karşısında kesin olmayan eşitlik diye bir kavram olmaz. Kabaca, “küçük o” daha küçük.. ve “küçük omega” da daha büyük anlamında kullanılırlar. Bu alışmanız gereken bir simgelem.. Burada bunu tanımlamayacağım çünkü önceki tanımla hemen hemen aynı.. Öncekinden tek farklılığı, c katsayısı ve bir  değeri var demek yerine, her c katsayısı için başka bir  olacağını kabul etmek..

 

f ve g arasındaki eşitsizlik ilişkisi, her c değeri için geçerli olmak zorundadır.. sadece bir tanesi için değil.. Böylece , c’ye bağımlı hale geliyor.. n değerinin yeterince büyük olduğunu varsaysanız da bu size kesin bir eşitsizlik ilişkisi veriyor.  g’nin önüne,hangi katsayıyı koyarsanız koyun,.. örneğin “küçük o” ile uğraştığımızı düşünelim,..f,  yeterince büyük n değerleri için c çarpı g’den yine de küçük olacaktır…

Rastgele birkaç örnek verelim:  Yine katsayıları görmezden geleceğiz..

yeterince büyük n değerleri için ’ den her zaman küçük olur..Bu biraz dikkat etmeniz gereken bir konu; böyle bir şeyi kanıtlamak zamanla, bu uygulamaları uğraştıkça daha kolay hale gelecek..

’ın c cinsinden ne çıkacağını hesaplamanız gerekir. .. Bunun 2 / c olduğunu sanıyorum… Küçük- eşit durumu varsa, bunun doğru olması gerekir.. Tamam.. Burada c ‘yi epsilon ve deltalardaki epsilon gibi düşünmelisiniz.  c ne kadar küçülürse küçülsün,  c en azından 2/c büyüklüğündeyse, ben n²’ yi   'ün üst sınırıyla sınırlayabilirim…

 

Ama  teta ile işlem yapıyorsanız bu varsayımları ikisini de kullanamazsınız.

Örneğin, ½ n² = büyük Teta (n²) eşitliği.. küçük o(n²) değildir.. küçük omega(n²) de değildir, çünkü kesin n²’ye eşittir.

Bununla sıra ilişkileri hakkında bazı öngörüler edineceksiniz; ancak problem setinize bakarken de göreceğiniz gibi karmaşık durumlarla da karşılaşacaksınız…

Asimptotik simgelem hakkında sorular var mı?  Bu kısa bir tekrardı.. Artık bunu yineleme problemleri çözmede kullanabiliriz. Bugün bunu çok fazla kullanmayacağız ama gelecek derste uygulamaları bolca yapacağız.

 

Günün ikinci konusu olan yinelemeleri çözme konusuna geçiyoruz.

Daha önce aldığınız discreet yani ayrık matematik sınıflarında herhalde bazı yinelemeleri çözmüşsünüzdür. Burada biz bu iş üzerinde biraz daha fazla çalışacağız ve özyinelemeli algoritmaların çözümlenmesinde kullanılan bazı teknikleri ele alacağız. Daha sonraki derslerde de buna derinlemesine gireceğiz. Burada yinelemeleri çözmek konusunda kullanacağımız 3 ana yöntem var.

Birincisinin adı substitution method yani yerine koyma metodu. Yinelemeleri çözmek için genel bir prosedür yada yöntem yoktur. Maalesef yinelemeleri çözmek için iyi bir algoritma da yoktur. Sadece birtakım teknikler vardır. Bunların bazıları bazen işe yarar ve eğer şanslıysanız sizin yinelemeniz için bunlardan biri çalışır. Aslında bunlar bir integral problemi çözmek gibidir. Bazılarını sadece bilmeniz gerekir. Ve bunların çözümü için bazı yöntemleri bilmeniz gerekir. Genelde cevabınızın doğru olup olmadığını kontrol etmeniz kolaydır. Aynı integral problemlerinde olduğu gibi türevi alırsınız ve doğru cevabı bulup bulmadığınızı anlarsınız. Bu yaklaşım temelde yerine koyma metodunun özüdür. Yerine koyma metodu her zaman çalışır. Fakat maalesef 1. Adım cevabı tahmin etmektir. Ve cevabı doğru tahmin etmek zorundasınız. Bu işleri biraz zorlaştırır. Öte yandan tahmininizin tam olması da gerekmiyor. Genelde sabit faktörleri bilmeden de bir çözüm bulabilirsiniz. Bu iyi bir şeydir çünkü bildiğiniz gibi sabit faktörlerle çok fazla ilgilenmeyiz. Siz formu tahmin etmek durumundasınız.  Dersiniz ki “bu yaklaşık n² mertebesinde olacaktır.” Yani cevap “bir sabitle n² nin çarpımından oluşacak” anlamına gelir. İşte bunu tahmin edersiniz. Biz burada sabitlerinde ne olmaları gerektiğini hesaplayacağız. Siz yinelemenin bu sınırları karşılayacağını tümevarım yöntemiyle doğrulayacaksınız ve esas anahtar budur. Yani yerine koyma metodu tümevarım yaklaşımını kullanır. Ve bu işin sonunda da genelde sabitlerin ne oldukları kendiliğinden ortaya çıkar. İşin sonunda bu sistemin çalışması için sabitlerin ne olduğunu bulmaya çalışırsınız. İşte genel fikir budur. Bununla ilgili birtakım örnekler göreceksiniz. Aslında aynı örneği birkaç kez göreceksiniz. Maalesef böyle bir durumla karşılaştığınızda; nasıl anlatsam; bu bir algoritma ama doğru cevabı bulmak için kehanetten yararlanılıyor. Ama bazen cevabı tahmin etmek o kadar da zor değildir. Bu duruma bağlıdır. Şu yinelemeye T(n)= 4T( n/2) +n yinelemesine bakarsanız, elimizde varsayımsal olarak bir base case yani temel durum olmalıdır.  Ve bu T’nin bir sabitle ilişkisidir. Genellikle bu da 1 dir. Ama temel durumlar bizi fazla ilgilendirmiyor. Algoritmalarda bu durum her zaman böyledir. Ve biz şimdi bunu çözmeye çalışıyoruz. Burada bunun cevabıyla ilgili herhangi bir tahmini olan var mı? Aslında bu yinelemeyi çözmeyi bilmeyenlerden bir tahmin almak istiyorum. Burada kaç kişi bu yinelemeyi çözmeyi biliyor? Birkaç kişi. Tamam.  Geri kalanlar herhangi bir tahmininiz var mı? Burada olana baktığınızda elimizde T(n/2)  var. Ama n’yi şimdilik ihmal edelim. Burada n/2 var diyelim. Eğer bunu 2 katı arttırırsak elimizde T(n) olur ve bu taraf da 4 kat artar.. n bunun arkasından gelen ek bir terimdir ama bu çok önemli değil. Bildiğiniz hangi işlev bağımsız değişkeni 2 kat arttırdığınızda çıkışı 4 kat arttırır?  Pardon, evet  n². Eğer n² olduğunu düşünüyorsanız cevabınız doğrudur. Ama bunun n² olduğunu şimdilik kanıtlamayacağız. Şimdilik daha kolay bir şey kanıtlayacağız. Çünkü bunun maksimum n² olduğunu kanıtlamak biraz eziyetli olacaktır. Bunu birkaç dakika sonra yapacağız. Şimdilik T(n) = O(n³) tahminini yapalım. Çünkü bunun tümevarım yoluyla kanıtlanması daha kolay olacak. Bu kanıtlama işleminin yapılışını kolay bir örnekle öğrenirseniz, esas hedef olan n² ‘nin cevabını daha kolay elde edersiniz. Bunu kanıtlamak için şimdilik T(n) nin en fazla bir sabitle n³ ün çarpımı olduğunu tahmin edeceğim. Ve şimdi daha hassas çalışacağım. Ben büyük O simgelemini yerine koyma metodunda kullanamıyorum. Onun için bunu biraz genişletip sabitleri kullanmam gerekiyor.

Size biraz sonra büyük O simgeleminin neden kullanılamayacağını göstereceğim; ama bu evrede şunu belirteyim, büyük O simgelemini burada kullanmamak önemlidir. Büyük O simgelemi eğer sınırlı sayıda bir büyük O ilişkileri zinciri varsa, yani Büyük O()’tür. Büyük O() gibi ilişkiler varsa bunların hepsi doğrudur.  Bu şekilde siz n² = Büyük O() diyebilirsiniz. Ama elinizde sınırsız bir ilişkiler zinciri varsa o zaman birinci terim son terimin büyük O’su değildir. Buna çok dikkat etmeniz lazım. Bu olay ders notlarında ayrıca belirtilmiştir. Diyelimki siz n’nin 1 in büyük O’ su olduğunu kanıtlamak istiyorsunuz.  Bu güzel bir ilişkidir. Ama bu doğru  olsaydı her algoritmanın sabit bir koşma süresi olurdu. Bu doğru değildir. Wayne’in World notasyonu yani dünya simgelemine göre bu doğru değildir. Bunu tümevarım yöntemiyle, temel durum 1=O(1), yani order 1, düzey 1 şeklinde tanımlayabilirsiniz. Evet bu doğrudur. Bundan sonraki tümevarım adımında, eğer n-1 in ne olduğunu bilirsem, diyelim ki n-1= O(1) ise, n = (n-1)+1 olacağından eğer, (n-1)= O(1) ise ve  1= O(1) ise sonuçta tüm eşitlik O(1) olur. Ve bu doğrudur; eğer (n-1)=O(1)  ve 1= O(1) olduklarını biliyorsanız, bunların toplamı yine Or(1)  olacaktır, ama bu yanlış bir kanıtlamadır. Yani büyük O’ lar üzerinden tümevarım yapamazsınız. Buradaki durum varsayımsal olan sabitlerin aslında değişmeleridir. Burada bir büyük O var; ve burada da bir büyük O var.  Büyük olasılıkla bu ilişkiyi her uyguladığınızda sabiti 2 kat arttırıyorsunuz. Eğer elinizde sınırlı sayıdaki sabitleri 2 katına çıkaran bir uygulama varsa bu çok önemli bir şey değildir. Çünkü sonuç yine bir sabittir. Ama siz burada n sayıda 2 katına çıkarma işlemi uyguluyorsunuz ve bu iyi bir şey değildir. Bu durumda buradaki sabitler n’ye bağımlı olmaktadır. Bundan kaçınmak için bu tip problemlerde sabiti ayrıca yazarak sonuca ulaşmaya çalışırız;  sabitin değişmediğinden de emin olmalıyız.

Şimdi buraya sabiti yazdım. Artık. rahat olmalıyım. Bunu k’nın n’den küçük bir değer olduğunu varsayarak yapıyorum. Ve şimdi k’nın  n’ye eşit olduğu zaman da bunun geçerli olduğunu kanıtlamam gerekiyor. Şimdi T(n)’yi ele alacağım ve onu genişleteceğim. Çok açık olan bir şey yapacağım. Elimde T(n)’yi genişletecek bir yineleme var. Bu durumda bu yineleme T(n/2) ile ilintilidir. T(n/2) ile ilgili bir gerçek daha biliyorum:  n/2,  n’den küçüktür. Şimdi bunu genişleteyim. T(n) = 4T(n/2) + n .. Tümevarım hipotezinden yola çıkarak T(n/2)  ile ilgili bir üst sınır buldum. Ve bu üst sınır 4 çarpı c x (bağımsız değişkenin küpü) + n dir.

Buradan devam edelim. Şunu biraz daha genişletelim. Elimizde n³/2³ var. 2³, 8 eder. Böylece 4/8 yarımdır. Sonuçta elimizde ½ cn³ + n kalır. Burada ulaşmaya çalıştığım sonuç aslında bu değerin en fazla cn³ olabildiğidir.  n için tümevarım hipotezini geçerli kılmak için bunu kanıtlamam lazım. Burada yapacağım şey istenen değer olan cn³ ‘ü elde etmek için istediğim şeyleri yazmak sonra da istemediğim değerleri bundan çıkarmak olacak. Buna residual yani kalan değer denir.  Şimdi bunu hesaplamam gerekiyor. Elimizde cn³ var ama burada ½ cn³ var. Bu nedenle ½ cn³ ‘ü çıkarmam gerekiyor. Çünkü ancak bu durumda baştaki değeri bulabilirim. Bundan başka elimde bir + n var ama parantezin başında eksi olduğu için, bu da eksi n demektir. Ve kalan değer budur. Bunun en fazla bu değer olması için kalan değerin negatif bir değer olmaması gerekir. Ve kalanın 0 dan büyük ve ona eşit olduğunu bulmam lazım; ama bunu yapmak kolay, çünkü burada c üzerinde kontrolüm var. C yi istediğim gibi seçebilirim. Yani c, mesela en az 2 ise o zaman bu değer de en az 1 dir. Bunun yanında n³ ‘ün n’e eşit veya ondan daha büyük olması koşulu da var. Ve bu her zaman böyledir. Ve örneğin c en az 1 ise n’nin ne olduğunun o kadar önemli olmadığını düşünüyorum; ama diyelim ki n’ye 1 değeri verdik. Böylece T(n)’nin en fazla bir sabitle n³ ün çarpımı olduğunu kanıtladık; ve buradaki sabit de 1’e yakın. 

Evet, bu bir üst sınırdır. Ama sıkı bir üst sınır değildir. Aslında bizim inandığımız n²‘nin üst sınırı olduğudur ve bu da doğrudur ama burada biraz daha dikkatli olmanız gerekiyor. Bu yanıtın n³ olduğu anlamına gelmiyor, sadece en fazla n³ olabileceği, daha doğrusu, O(n³) olduğu anlamına geliyor. Bu kanıtlamayı biz tümevarım yöntemiyle yaptık. Şimdi teknik olarak bu tümevarıma bir de temel durum ilave etmem gerekir; yani bir şeyler hala eksik. Temel durum, burada o kadar zor değil çünkü T(1) bir sabit, ama bazı şeyleri etkileyebilecek bir sabit.  Eğer T(1) bir sabitse, burada ihtiyacımız olan şey bunun değerinin c kere 1³,  yani c olması ve bu, c yi yeterince büyük seçtiğimiz takdirde doğrudur. Yani c yi yeterince büyük seçmemiz lazım. Şimdi biz sabitlerle fazla ilgilenmiyoruz ama buradaki önemli konu biraz dikkatli olmak. Sonuç olarak T(n)nin 1 x n² ye eşit olması doğru değil. c’nin en az 1 olma koşulu olmasına rağmen temel durumun çalışması için c nin en azından 100 yada T(1)’ in değerine eşit olması lazım. Onun için burada biraz dikkatli olalım. Bu, cevabı genelde etkilemeyecek çünkü burada çok basit temel durumları seçtik. Tamam, şimdi Or( n²)’nin sıkı bir üst limitini bulmaya çalışalım. Burada bir omega(Ω) sınırlaması kanıtlamayacağım ama siz dilerseniz yerine koyma metodunda Ω(n²)’nin üst sınırını bulabilirsiniz. Burada ben n² ‘nin üst sınırını kanıtlamakta yetineceğim. Şunu deneyelim,. T(n)’nin üst sınırı Or(n²) ye eşittir. Aynı şeyleri yapacağım. Burayı biraz daha hızlı yazacağım çünkü aslında sadece basitçe kopya çekiyorum. Buradaki tek fark eskiden 3 varken şimdi 2 yi kullanacağım. Bu durumda T(n)=4T( n/2)+n olur. Bu T(n/2)’yi genişleteceğim. Bu en fazla 4 c (n/2)² + n dir. Ve bu durumda 2 nin küpü değerinin yerine 2 nin karesi yani 4 kullanacağım. 4 ler birbirini götürür. Bu durumda c + n elde ederim. Bunu başka türlü yazmayı tercih ederseniz, yani kalan eksi değeri de göstermek isterseniz, o zaman elimde cn² - (-n) olur. Ve ben bunun negatif olmasını istemiyorum. Ama öteki taraftan eksinin negatif olmaması çok zor bir şey. Eğer n= 0 ise bundan mutlu oluruz. Ama maalesef burada yaptığımız şey n üzerine bir tümevarım ve  n’in 1’e eşit veya büyük değerleri için geçerli olması gerekiyor. Yani bu cn² ‘ye küçük-eşit değil. Dikkat edin, insanın içinden bunun büyük O (n² )’ye eşit olduğunu yazmak geliyor, ve birinci adımda bu geçerli. cn² - ( -n) ifadesinde her şey n düzeyinde daha doğrusu bu n düzeyinde bu da n² düzeyinde. Doğal olarak bu ifade O(n²), bu doğru. Ama tümevarım yaklaşımını tamamlamıyor. Bu yaklaşımı tamamlamak için siz tümevarım hipotezini n ile birlikte bir c olduğu zaman da kanıtlamak durumundasınız. Burada c sabitini c+1 şeklinde elde edebilirsiniz ve bu iyi değildir. Bu doğrudur ama işinize yaramaz. Bu tümevarımı tamamlamaz; onun için bunu ihmal edebilirsiniz. Bu kanıtlama yöntemi işimize yaramıyor. Bu da rahatsız edici çünkü biz T(n)’in n²ye eşit olduğunu bir şekilde hissediyoruz.. Bu sakıncayı gidermek için T(n)’yi biraz daha farklı bir formda ifade etmek gerekiyor. Bu yine ilahi bir sezgi; sizin ilahi sezgileriniz varsa hiçbir sorununuz olmaz, ama biz ölümlüler için biraz daha zor bir durum bu.

Sonuçta tüme varım hipotezimizi biraz daha güçlendirmemiz gerekiyor. Plan bu. Biz aslında biraz zayıf bir varsayımla T(k)’nın k² ‘nin bir sabit ile çarpımına küçük-eşit olduğunu varsaydık. Biz sabitin ne olduğunu bilmiyorduk. Bu tamam ama daha düşük düzeyde terimlerin olmadığını da varsaymıştık. Şimdi daha düşük düzeydeki terimlere bakmak istiyorum. Belki onların bir rolü olacaktır. Bu aşamalı işleme baktığınız zaman diyebilirsiniz ki “elimde n² gibi bir şey olacak ve sabitler oldukça sıkı bağdaşmış.” Yani diyoruz ki 4 ler birbirini götürüyor ve c muhafaza ediliyor. Bu düşük düzeyde terimden ve n’den nasıl kurtulacağım? Belki buradakinden doğrusal bir terimi çıkarabilirim ve eğer şanslıysam bu taraftakini götürür. Şu noktada elimizde olan tüm sezgisel yaklaşım bu. Ama sonuçta çalıştığını ve sonuç alındığını görürüz.

T(n)’ye bakarız ve her zaman olduğu gibi bunun 4T( n/2) + n olduğunu görürüz. Şimdi biraz daha karışık bir forma geçeceğiz. Elimizde 4( ( n/2)² -  (n/2)) + n var. İlk kısım daha önceki ile aynı. Çünkü 4 ler birbirlerini götürüyor. Böylece elimizde  n² kalıyor ki bu iyi bir şey,. yani bu istediğimiz formda aslında. Bundan sonra bir sabit çarpı n var. Ve bunun ne olduğunu bulalım. Elimizde artı 1 çarpı n var, bu nedenle bunu (1- /2) kere n olarak yazalım. Bir dakika, yanlış yaptım. Elimizde 4 kere 2 var. Bu nedenle 2 nin aslında yukarıda olması lazım. Bir kez daha kontrol edeyim..        (1- 2) n Tamam.  Şimdi bunu istenilen eksi kalan değer olarak yazabiliriz. Ve burada biraz da dikkatli olmamız lazım çünkü öncekinden daha kuvvetli bir tümevarım hipotezi ile karşı karşıyayız. İstediğimiz şey  x n² yeni bir şey değil; aslında burada bu uygun olurdu. Ve biz 2 ‘yi büyük seçebilirdik. Ama aslında ihtiyacımız olan    n² - kere n ve ondan sonra eksi bir şeyler.. Tekrar ediyorum bu istenilen eksi kalan değerdir. Eksi kalan değere bakalım; bir eksi 1’imiz var ve bir de eksi  ‘miz var. Bu çok güzel görünmüyor. ..Artı ; teşekkür ederim.  Bunun artı  olması lazım. Ben    - , +  işaretlerimi karıştırıyorum. Burada bir eksi var. Ve orada da bir -1 var. Evet böyle olur. Sonuçta istediğim şey kalanımın 0 dan büyük-eşit olması. Ve bunu sağladığım takdirde bu tümevarım argümanını yürütecek durumda olacağım.   

Ek dersler bu hafta başlıyor. Eğer gitmek istiyorsanız bunların hepsi aynı odada ve

Burada yapılacak çalışmaların detayları için WEB’e bakabilirsiniz.

Şimdi devam edelim. -1 ne zaman 0’a büyük-eşit olacak?  Bunun doğru olması için  ‘nin en azından 1 olması lazım. Çok büyük bir mesele değil; çünkü sabitlerimizi istediğimiz gibi seçebiliyoruz. Ama yine de seçilebilecek sabitlerin bazıları için geçerlidir bu. Bunun için biz  ‘yi  0’a büyük-eşit olarak seçebiliriz. O zaman da mutlu oluruz. Bu durumda n² - n, 1’e eşit veya ondan büyükse bu eşitlik yazılabilir. Burada komik bir şey var: Bu tümevarımı sonuçlandırıyor, en azından bu adımını sonuçlandırıyor. Neyi kanıtlamış olduk?   en azından 1 ise,  ‘in bütün değerleri için bu geçerli olacaktır. Ama burada dikkat edeceğimiz bir şey var. ‘in yeterli derecede büyük olması lazım. Nedenini biliyor musunuz? ‘in de negatif olmaması lazım. Bunun geçerli olması için  ‘in pozitif olması lazım. Ama gene de yeterince büyük olması lazım.  Af edersiniz, galiba biraz fazla hızlı gittim ve size soru sormadım.

Evet. temel durumdan dolayı. Yani temel durumda, T(1) vardır ve bu c çarpı 1² -  olur. Ve kanıtlarken de bunun en çok şu değeri almasını  istiyoruz. Ve T(1)’in de bizim kabul ettiğimiz bir sabit olduğunu düşünüyoruz. Burada ‘i, ‘den yeterince büyük seçmemiz gerekiyor. ‘nin en az 1 olması gerekiyor.  en azından 100 kere daha büyük olmalı; eğer bu 100 ise.. Bu durum ancak  in yeterince yüksek seçilmesiyle sağlanabilir. Yani ‘ye göre yeterince yüksek. Sizin bu konuda dikkatli olmanız lazım; gerçi bu örnekte bu çok önemli değildi. Yerine koyma yöntemi ile ilgili sorularınız var mı? Bu örnek aslında 3 değişik şekilde ele alındı. Ama sonunda doğru cevaba ulaştık. Ama aslında doğru cevabı bulmak için onu bilmek zorundaydık ve bu biraz zordur. Aslında bu hesaplamayı bir prosedüre, bir yönteme dayanarak yapabilsek daha şık olurdu. Ve bundan sonraki 2 teknik bunlarla ilgili olacaktır.

Af edersiniz, duymadım.  

 

Alt sınırı nasıl mı kanıtlarız? Bu yineleme için bunu ben denemedim ama aynı formu kullanarak yapacağınıza sanıyorum. Burada T(n)  kere n²-  kere n olduğunu düşünün; bu yaklaşımın sonuç alıp alamayacağını ben denemedim ama sanıyorum ki alacaktır;  deneyin.

 

Bundan sonra anlatacağım metotlar size bir bakıma hem üst sınır hem de alt sınır için birtakım sonuçlar verecektir ama dikkatli olmanız gerekir. Bunu yaparken, aynı yerine koyma metodunda yaptığınız gibi, işlemlerinizi tek tek kontrol etmelisiniz. Ve tabii bunda da giderek uygulama yaparak uzmanlaşacaksınız. Genelde biz sadece üst sınırlarla ilgileniriz. Bu nedenle üst sınırların kanıtlanmasına odaklanacağız, ama bazen de alt sınırlarla ilgileneceğiz. Üst sınırı bulduğunuz zaman alt sınırı da bularak bunu kanıtlamak hoş bir şeydir.

 

Burada üzerinde duracağımız ikinci yöntem recursion tree metodu yani özyineleme ağacı yöntemidir. Herhangi bir yinelemeyi toplamanın özel bir yoludur. Benim en çok sevdiğim yöntemdir. Bu sistem genelde hep çalışır ve bununla ilgili en iyi şey de budur. Size ihtiyacınız olan sezgiyi, öngörüyü kendiliğinden sağlar. Genelde size cevabın ne olduğunu söyler. Çok sıkı kuralları olan bir yöntem değildir.  Bu bakımdan bazı sancılar yaratır ama bunu uygularken çok dikkatli olmalısınız aksi takdirde yanlış cevabı elde edersiniz. Bizim sevdiğimiz karakterler olan bir sürü nokta noktayı ihtiva eder; fakat bu nokta noktalar da aslında kendi içinde gevşek anlatımlardır. Teknik olarak yapmanız gereken şey özyineleme ağacı yöntemiyle cevabın ne olduğunu bulmak ve sonra da bu cevabın doğru olup olmadığını yerine koyma yöntemiyle kontrol edip kanıtlamaktır. Genelde bu kanıtlama adımı gerekli değildir ama sıkı bir sistem olması için bunu uygulamalısınız. Ve belki de ilk çözdüğünüz birkaç yineleme probleminde en azından bu şekilde davranmanızda yarar var. Özyineleme ağacı yöntemini iyice anladıktan sonra biraz daha gevşek çalışmaya hakkınız olacak. Doğru cevabı bulduğunuza inanacaksınız.

Haydi bir örnek yapalım. Özyineleme ağaçlarını geçen kez birleştirerek sıralama yaparken kısaca görmüştük ve sezgisel bir öngörüyle  nlogn’yi kullanmıştık. Ve geçen seferkine yakın bir örneği ele alacak olursak özyineleme ağacı metodu çok basittir. Onun için sizin yaşamınızı biraz daha zorlaştırmak için daha karmaşık bir özyinelemeyi ele alalım. Burada başka bir algoritmayı hayal edelim. Problemin boyutu n olsun ve n/4 boyutunda bir problemi özyineleme metoduyla çözsün. Ondan sonra bunu boyutu n/2 boyutunda çözsün. Ve n² oranındaki işi bu tarafta özyineleme işi olmadan yapsın. Bu ne demek? Yani anlattığım çok açık değil.  Yapacağımız şey bir resim çizmek. Ve ondan sonra bunu bir özyineleme ağacı formuna genişletmek. Ve ondan sonra da her şeyi birbiriyle toplamak.. Genel bir resme ihtiyacımız var.  Özyineleme ağacı yönteminin prensipleri gereğince bunu bir resim olarak çiziyoruz. Ve diyoruz ki T(n); n², T(n/4) ve T( n/2) nin toplamlarına eşittir. Bu aslında bir toplamayı yazmanın garip bir yolu ama niye böyle yapmayalım ki.  Sonuç olarak bu bir ağaç ve öyle bir ağaç olacak ki biz bu iki yaprağı özyinelemeli olarak genişleteceğiz. Ben T(n)’i bunlara genişletiyorum; sonra genişletme işlemlerine devam ediyorum. Genişletiyorum, her şeyi genişletiyorum. Şimdi bir adım daha atalım. Elimizde bu n², T(n/4) ve  T(n/2) var. Bunu bir kez daha genişletirsek elde n²  artı 2 şey olacaktır. Bu 2 şeyin birincisi (n/4) ² ve ikincisi de  (n/2) ² olacaktır. Tabii bunların da özyinelemeli dalları var. Bu durumda T( n/16) ve -- T(n/8) elde ederiz. Aritmetiğim burada biraz sulanıyor. Bunların aynı olması lazım. T(n/8) olması lazım ve bunun da T(n/4) olması lazım. Bu işe devam edip sonsuza kadar gidebilirsiniz; temel duruma yani T’nin bir sabit olduğu duruma kadar gidebilirsiniz. Onun için burada bazı adımları atlayacağım; bunları nokta noktalarla göstereceğim. İşte burada dikkatli olmamız gerekiyor. Sonunda elimizde n² , (n/4)² ve (n/2)² olur. Şimdiye kadar kolaydı çünkü hepsini yapmıştım. Bu özyineleme ağacının içinde  (n/16) ² , (n/8) ² tekrar (n/8)² , (n/4)² v.s. nokta nokta..var. Tabanda bazı sabitler olacak; bunlar yapraklar. Kaç yaprağımız olduğunu merak ediyorum. Yani bilmemiz gereken bu ağaçta kaç tane yaprak olabileceği. Yalnız burada bir incelik var. Daha önce birleştirerek sıralama ve bir önceki özyinelemede olmadığı gibi buradaki yaprak sayısı biraz tuhaflaşıyor. Çünkü daha değişik hızlarda özyineleme yapıyoruz. Bu ağaç şu ağaçtan çok daha küçük olacak. Daha küçük bir derinlik yapısı olacak çünkü zaten n/16 ya kadar gidilmişti. Oysaki burada biz n/4 e kadar indik.    

 

Pekiyi, bu özyineleme ağacında kaç tane yaprak var?. Aslında ihtiyacım olan üst sınır. Anlamlı bir üst sınır. Bunun en fazla n’in 10. kuvveti olduğunu size söyleyebilirim ama bu anlamsız olur. n’den küçük olması lazım. Doğru. Pekiyi neden? Çünkü n boyutunda bir problemle işe başlıyorum. Ondan sonra problemi n/4 ve bir başka problemi de n/2 boyutlarında özyineliyorum. 1 değerine ulaştığım zaman da duruyorum. Böylece n/4+n/2=3/4n olur ki bu n’den kesinlikle küçüktür. Böylece ağaçta olması gereken toplam yaprak sayısı da en fazla n olabilir. Yani n boyutundaki bir iş için yola çıkarsam ve bunun dörtte birinden kurtulursam ve sonra da özyinelemeye devam edersem, bu sonunda n’den küçük olacaktır. Evet kesinlikle n’den az yaprağımız var. Şu ana kadar çok ilginç bir şey yapmadım. Ama ikinci iyi fikir, bu özyineleme ağaçlarını sonsuza kadar büyütüp ondan sonra da, “hay Allah bunları nasıl toplayacağım” demek zorunda kalmamanızdır; toplamaları her düzeyde ayrı ayrı yaparsınız.  Bu uygulamadaki en yararlı fikir bu ve genelde çok iyi işe yarar. Ama bu örnekte bu biraz daha karmaşık, çünkü ben önce n² nin n² olduğunu hesaplamak zorundayım. Bu ilk adım kolay. Ama ikinci adımda biraz daha yoğun düşünmem gerekiyor. Biliyor musunuz 3 tip matematikçi vardır.  Bunlardan bazıları toplama yapabilir. bazıları yapamazlar ve ben son grupta olduğum için yardımınıza ihtiyacım var. Şunları benim için toplar mısınız? Yani n² bölü bir şeyler çıkmalı. Lütfen. 5/16 n² , tamam, şimdi gerçekten yardımınıza ihtiyacım var. Bir öncekini ben kendim de yapabilirdim, ama bu seferki biraz daha karmaşık; siz bunu hesaplayana kadar ben de notlarıma bakacağım. Cevap var mı? 73/256 bunu onaylayacak başkası var mı? Bana biraz yüksek geldi. 73 çok doğru görünmüyor;. 64 mü? Yaklaştınız. Aslında bunu doğru hesaplamamız önemli. Alttaki 256 doğru. Bunu söyleyebilirim. 16² nin 256 olduğunu herkes bilir. Biz bilgisayar bilimcileriyiz. 25, güzel. Burada 2 kişi 25 dedi. O halde demokrasi kuralına göre bu doğrudur. Benim notlarımda da 25 yazıyor. Çünkü ben bunu evde yapmıştım. O halde 25/256 kere n² doğru cevap olmalı.

Şimdi bu progression yani aşamalanmada kimse sihirli bir şeye dikkat etti mi? Evet, her seferinde karesi çıkıyor. Doğru. Ve bunları toplayacak olursak buna ne diyebiliriz? Bir geometrik seri. Doğru. Sonuçta öyle çıkıyor ki bu geometrik. Ve biz geometrik serilerin nasıl toplanacağını biliyoruz. En azından siz biliyorsunuz.

 

n² ile işe başlamıştık. Ve en alt düzeyde, tam anlamıyla düzey de değil ama n gibi bir şey çıkacak ve biz geometrik olarak azalıyoruz. Biliyoruz ki bu yinelemenin çözümü olan toplam, bu ağaçtaki sayıların hepsinin toplamı. Eğer biz buradaki her düzeyde toplamları alırsak, sonra da bu ara toplamları toplarsak bize cevabı verecektir. Bu düzey düzey hesaplanmış olan toplamların toplamıdır. Ve bunu hesaplamanın hoş bir yoludur. Size geometrik cevaplar gibi güzel yanıtlar güzel cevaplar sunar. Elimizde     ( 1 çarpı n² +5/16 çarpı n²+25/256 çarpı n² + …)  bir şeyler daha var. Ve eğer biz biraz kadere inanıyorsak bu üç sayının yinelemesine bakarak doğru yanıta ulaşacağımızı hesaplayabiliriz. Arada bu / gibi bir şey olacak. En azından öyle umuyoruz. Bu şekilde devam ediyor. Sonsuza kadar devam etmiyor ama bir an için sonsuza kadar devam edeceğini varsayalım. Sonsuza kadar devam etmesi durumunda bu üst sınır olacaktır.  Burada  da n² olmalı..  Eğer geometrik seriler hakkında tek şey biliyorsanız bilmeniz gereken 1+ 1/2+1/4 ve bunun devamındaki tüm değerleri topladığınız zaman--en fazla 2 elde edersiniz. Biz bilgisayar bilimcileriyiz. En azından 2 li tabanı bilmek zorundayız. Bu 0,111111’i  ikili sistemde yazmak gibidir. Aslında 1.11111 yazılmalıydı ve şu birleri sonsuza kadar devam ettirirseniz bu 1 e eşittir. Onun için bir önceki örnekte sonuç 2’dir.   

 

Bu daha da küçük. Elimizde 5/16 var. Bu yarımdan daha az. Ve giderek her seferinde bunun karesini arıyoruz. Yani sonuçta 2 den az olacak. Eğer isterseniz elimizde genel geometrik serileri çözmek için şık bir formül var ama bu evrede ihtiyacımız olan şey sadece bunun bir sabit olduğunu göstermek. Bu Or( n²)‘dir.  Aynı  zamanda  Ω(n²)dir. Bunun Ω(n²) olduğu belirgin çünkü bunu sınırlayan üstteki değer n². Böylece  biz      n² ‘nin alt sınırını elde ederiz. Ve bunun değeri de 2’nin bir faktörüdür. Bu da çok iyi bir değer.  Aslında bundan daha da iyi bir değer elde ediliyor. İşte bu özyineleme ağacı metodu. Çok kesin bir sonuç elde edemedik, çünkü burada nokta nokta noktalar vardı, ama biz bunun geometrik olduğuna şimdilik inanıyoruz. Çoğu zaman da geometrik olduğu ortaya çıkar. Burada büyük bir problem olmaz. Ama geometrik olacağı kesin olmadığı durumlarda ben bunu, yerine koyma metoduyla yine de kontrol ederim. Şimdi inceleyeceğimiz durumlarda bu daha da açık olacak. O kadar açık olacak ki her şeyin doğru olduğuna dair bir teorem bile öne sürebileceğiz.

 

Daha zamanımız var, iyi. Evet. Bunlar özyineleme ağaçlarıydı. Şimdi üzerinde konuşacağımız bir yöntem daha var. Ve bunu siz özyineleme ağacı metodunun bir uygulaması olarak da düşünebilirsiniz. Ama bu daha hassastır. Aslında bu bir teoremdir.

Özyineleme ağacı uygulamalarında eğer nokta noktalar varsa sonuç çok açık değildir, onun için kontrol edilmesi gerekir. Bu Master method, yani ana metodun üzücü tarafı bunun biraz kısıtlayıcı olmasıdır. Bu metot sadece yinelemelerin belli ailelerinin üzerinde uygulanabilir.  Bu metod T(n) = a T(n/b) + f(n) türü bir durumda uygulanabilir.. Buna f mi diyeceğim? Evet buna f diyeceğim.  Bu yöntem biraz önce çözdüğüm özyinelemeyi çözümleyemez çünkü orada değişik boyutlardaki 2 farklı problemi ele alıyordum. Bu metotta özyineleme uygulayacağınız her problem aynı boyutta olmak zorunda.. Yani bir tip alt problem olacak. Bunu düşünmenin bir başka yöntemi de bunu bir özyineleme algoritması olarak ele almanızdır. Yani a sayıda alt problemler vardır. Bunların her biri n/b boyutundadır. Ve sonuç olarak toplam emek bu olacaktır. Ondan sonra f(n) için yineleme olmayan bir çalışma yaparsınız. Burada bazı sınırlamalar var. a en az 1 olmak zorunda; en az 1 yineleme olmak zorunda ve b de kesinlikle 1 den büyük olmak zorunda. Problemi kesinlikle küçük boyutta tutmalısınız. Yoksa sonsuza kadar devam eder gider. ve f nin de güzel bir özelliği olması gerekiyor. f(n) asimtotik olarak pozitif olmak zorunda. Burada kaç kişi asimtotik olarak pozitifin anlamını biliyor? Kimse bilmiyor mu? Tamam, demek ki ders kitabını okumamışsınız; olabilir, aslında ben de okumadım ama bunu Charles’a söylemeyin. Ama o okumadığınızı fark edecektir.

Pekiyi, sizce asimtotik olarak pozitif ne anlama gelebilir? Biraz daha ilerlemek için bunu soruyorum. Pardon. Evet. Yeterince büyük n değerleri için, ve f(n)’nin de pozitif olması gerekir anlamına gelir. Yani n’nin belirli bir  değerinden büyük olması halinde, f(n)’nin de 0’dan büyük olması şartı gerekiyor. Sonucun pozitif olması gerekiyor. Yani n= 1 için eksi  1 elde etmek çok önemli bir şey değil. Bu sonucu etkilemez. Çünkü biz içindeki asimtotlarla ilgileniyoruz.

Ana metota bu formda özyinelemeler verirseniz size cevabı çıkarır; metodun en önemli özelliği de budur. Öte yandan bunun rahatsız edici yönü bu metodun 3 değişik şıkkı olmasıdır. Bir defa biraz uzundur ve diğerlerine göre ezberlenmesi daha zordur. Çünkü ötekiler sadece fikirdi. Burada birtakım şeyleri hatırlamamız gerekir. Şimdi size teoremi açıklayayım; henüz açıklamayayım. Size önce çok basit bir ilişkiden bahsedeceğim; f(n)’nin buradaki özyineleme içermeyen uygulamasını özel bir fonksiyon olarak n üzeri  olarak açıklamaya çalışalım. Neden , bunu birazdan anlayacaksınız. Şunu göreceksiniz ki bu değer özyineleme ağacındaki yaprak sayısına eşit olacak, ama bu birazcık öngörü.. Onun için bu değer ya küçük-eşit, yada büyük-eşit olabilir. Şu anda burada asimtotlarla uğraştığımızı unutmayın; bu nedenle daha küçük, eşit veya büyük olma durumlarına hassasiyet göstereceğiz. Şöyle düşünebilirsiniz: Aslında bunun anlamı küçük o, büyük teta veya küçük omegadır. Aslında teorem bu 3 şık için geçerli olsaydı hoş olacaktı. Ama bazı boşlukları var.

 

1. Durumla başlayalım.   1. Durum  f ‘nin küçük olma durumudur. Ve bu küçüklük onun sadece küçük o olması anlamına gelmiyor aslında bundan çok daha küçük. Aslında  dan polinomik ölçüde daha küçük olmalı.

 

Birtakım pozitif epsilon değerleri için koşma zamanı bu n üzeri b tabanında logaritma  (a eksi epsilon)’a eşittir. Yani aslında () polinomsal olarak daha küçüktür. Burada küçük  o durumunu kullanamayız. Çünkü bu biraz güçlü gelir. Burada söylemek istediğimiz şey bayağı küçük olduğu; ama bu durumda cevap kolaylaşıyor.                        T(n) =  Teta ( )  . Çok iyi; işte bu birinci durumdur.

 

2. Durum,  f(n)’in   ’ya yaklaşık eşit olma durumudur; ve yaklaşık eşitlikle benim kastettiğim k polylogaritmik faktörlere kadar olmasıdır. Bu n’in ikili logaritma tabanında ve  k kuvvetine kadar olan değeridir.. Bu simgelemi bilmelisiniz.  Örneğin k= 0 olabilir. Bu durumda birtakım sabit faktörlere kadar bunlar birbirine eşittir. Mesela k’nın 0’dan küçük olması geçerli değildir; bu durumda k’nın eksi olmaması önemlidir. Ve büyük bir olasılıkla bir tamsayı olmalıdır. Aslında tamsayı olması da çok önemli değil ama burada tamsayı oluyor. Yani aslında şöyle olabilir.   kere log n’in k kuvveti;  yada bazen hiçbir şey, herneyse. Tekrar ediyorum buradaki çözüm çok zor değil. T(n) = Θ ( çarpı n )  . Bu ikinci durumdur.

 

Biraz daha karmaşık olan bir üçüncü durumumuz var. 3. durumda biraz daha fazla varsayım yapmamız gerekiyor. Bu durumda f(n),  dan daha büyük hale geliyor.. f(n)= Ω() . İşte burası bizim büyük  omegayı kullanacağımız  bir durum.  Ama epsilonun artı olması gerekiyor ve biraz daha büyük olması değil, polinomsal olarak büyük olması gerekiyor. Şu durumda logaritma farkları kadar büyüktü; burada ise bir polinomsal oranda büyük olması gerekiyor.

Bu durumda bizim başka bir varsayıma gitmemiz lazım. Çünkü f ‘nin nasıl büyüdüğü ile ilgili kaygılarımız var. Özyinelemede aşağıya doğru indikçe, f’nin küçüldüğünden emin olmalıyız. Bu şunun için önemli. Eğer ağaçta aşağıya gittikçe f küçülmezse, sonunda sonsuzlara varan toplamalar yapmak zorunda kalabilirsiniz. Bunun neden sıfırdan büyük herhangi bir epsilon üssü olduğunu görebiliyorum. Benim burada mutlu edecek şey bu T(n) özyinelemesini alıp, f’leri yerleştirdiğimiz zaman, f(n)’in bir şekilde af (n/b) ile ilgili olmasıdır. Benim hoşuma gidecek şey özyineleme ağacının en üzerinde olan f(n)’nin onun bir altındaki düzeyden daha büyük olmasıdır. Yani bir alttaki seviyedeki değerlerin hepsinin toplamı bir sabit faktör oranında daha büyük olmalıdır. Burada bir alttaki seviyede elimde (1 – ε') değeri var. Ve bu 1 den kesinlikle daha az; yani bir üstteki değerden 1 çarpı bir sabit oranında daha az. Emin olmam gereken şey aşağıya indikçe değerlerin daha da küçülüyor olması. Bu durumda T(n) = Teta (f(n)) diyebiliriz.  İşte bu bir teoremdir. Bu ana teoremdir.

 

Yada buna ne demek isterseniz. Bu isim adı Master olan bir kişinin anısına verilmemiştir; bu şu ana kadar anlatılan metotların yada yöntemlerin hepsinin anası, ustasıdır, çünkü kullanımı yada uygulaması çok kolaydır. Haydi bunu birkaç kere uygulayalım. Hepsini birden bir seferde hazmetmek zor oluyor. Onun için size kanıtın bir skecini vereceğim. Ve özyineleme ağacına baktığınız zaman bunun doğru olması çok şaşırtıcı olmayacak. Ama önce bunu bir kez kullanalım. Örneğin T(n) = 4T( n/2) + n ‘i ele alalım. Bu a dır. Bu b dir. Bu da f(n) dir. İlk hesaplamamamız gereken şey   ‘nin değeridir. Bunu ben bile yapabilirim sanıyorum. 4 ün log 2 tabanlı çözümlemesi. Evet. log 2 tabanlı çözümlemeyi ben de yapabilirim. Bu n² çıkar. Bu durumda f(n)  n² den büyük müdür, küçük müdür?  Aslında f(n) = n’dir ve n²  de  polinomsal faktör oranında daha büyüktür. Bu örnekte  biz birinci durumda oluruz. Öyleyse cevap nedir? . n² ‘dir , evet. Yani T()’ =  Teta (n²).

 

Küçük değişiklikler yapalım. a’yı ve b yi aynı tutup sadece f yi değiştirelim. Mesela diyelim ki T(n) = 4T(n/2) + n² . Bunu söylemek sanki heceleme egzersizi gibi oluyor. n²,  n² ye bazı sabitler olsa da asimptotik olarak yakın çıkıyor. Evet, cevap nedir? Bu İkinci Durum ,yani biraz daha zor. Bu örnekte k’ nın değeri ne? Sıfır. Cevap ne? Araştırmalar ne diyor? n² log n. Güzel. Birkaç tane daha.  T(n) = 4T(n/2) + n³ . Cevap ne?  . Bu Üçüncü Durum. Biliyorum bu oldukça sıkıcı ama bu aptal teoremi uygulamaya çalışıyoruz. Peki n²  bölü logn için ne dersiniz? Bunun yanıtı ne? Güzel. Bu durumda kimsenin bir yanıt bulamaması lazım. Bu biraz şaşırtıcı. Ben de arasıra cevabı unutuyorum. Yanlış hatırlamıyorsam n² loglog n  / log n olması lazım. Öyle değil mi ? Hayır hayır. n² log log n. Tamam şimdi oldu. Evet, ama bilmeniz gereken bir şey var. Bu ana metotdan çıkan bir sonuç değil. Bu sizin çözümlemeniz gereken bir şey  ve özyineleme ağacı yöntemi bunun için iyi bir yöntem olabilir. Ve logaritmaların bazı özelliklerini de bilmeniz ve uygulamalarını kavramanız gerekiyor. Bu durumda ana metod uygun değildir. Yani başka bir metot kullanmanız lazım. Tamam.

 

Ana metodun doğruluğuyla  ilgili size söyleyebileceğim son şey, bunun bu metodun sezgi olgusuyla ilintili olduğudur; özellikle özyineleme ağacı uygulamalarında ve burada, bu metotla her şey çalışır. Ama benim size anlattığım kanıtın taslağı, yani tamamı değil. Kanıtın tamamı için ders kitabını okumanız gerekir. Yani benim size anlattıklarımdan daha zor şeyler bulmayacaksınız ama formal detayları bilmeniz için okumanızda yarar var. Benim bu detayları açıklayacak vaktim bu derste yok.  Size sadece dikkat çekici kısımları anlatacağım. Yani ana metodun sezgisel olgusunun ve kanıt tasarımının üzerinde duracağım. Burada yapacağımız şey özyineleme ağacını bu yineleme için kullanacağız. Önce her düzeyi ayrı ayrı toplayacağız. Ondan sonra bütün düzeyleri birbiriyle toplayıp elimizde ne kaldığına bakacağız. Başlangıç olarak en tepedeki f(n) i ele alacağız ve bunu bir düzey genişleteceğiz. Bu yolla a değişik problem yaratacağız. Her birinin boyutu n/b olacak  ve bunları da genişlettikten sonra  her birisi için bir f (n/b) elde edeceğiz. Bunlar aynı boyutta olacaklar; genişletme işlemlerine devam edeceğiz ve daha alt düzeyde başka alt problemler yaratacağız. Bu kez elimizde f (n/b) ² gibi değerler olacak. Bu sonuçta geometrik olarak küçülen boyutlarla çalışmayı gerektirecek. Buna devam edeceğiz ve en altta da sabit boyutlu alt problemlerle uğraşacağız. Bu biraz özel olacak, çünkü bu temel durum; alt düzeyde başka sabitlerle karşılaşacağız. Bizim istediğimiz şey burada kaç yaprak olduğunu anlamak ama şu anda bu biraz karmaşık gibi görünüyor. Önce bu ağacın yüksekliğini hesaplayalım. Bunu buraya çizeyim. Bu ağacın yüksekliği nedir? Başladığım nokta n boyutunda bir problem ve varmaya çalıştığım nokta 1 boyutunda bir problem. Bu ne kadar zaman alır? Kaç  değişik düzey gerektirir? Bu soru herhalde bazılarınız için çok kolay, bazılarınızın için ise tam dudaklarınızın ucunda değil. Evet. n’in b bazlı logaritması. Bu ağacın yüksekliği h=  çünkü  aslında 1 e ulaşana kadar kaç kez b ile böldüğüm anlamına geliyor. Tamam bu iyi. Şimdi kaç tane yaprak olduğunu hesaplayabilmem gerekir. Çünkü a düğüm faktörünü biliyorum  ve h yüksekliğini biliyorum. Buradaki yaprak sayısı   =  ;  bunu biraz daha açayım. Logaritmaların özelliğine bağlı olarak n’i aşağıya, a’yı yukarı alabiliriz. Bu durumda elimizde bizim iyi dostumuz olan  kalır. Yaptığımız şey en üst seviyede olan f’yi, en alt seviyedeki  tetalara kadar olan  ile karşılaştırmak. Bu uygulamada yaprakların hepsi aynı seviyede, çünkü biz her dalda aynı oranda küçülüyoruz. En alt seviyedeki maliyeti toplarsam bu  Teta () ‘ya eşittir. Üst seviyedeki şeyleri toplayacak olursam bu da f(n)’e eşit ve bu çok şaşırtıcı değil. Ama bundan sonraki seviye biraz daha ilginç hale geliyor; ana metodu ezberlediyseniz bu size tanıdık gelecek, çünkü burada af(n/b) ilişkisi var. Burada a çarpı f(n/b)’nin bir sabit faktörle, yani (1- ε' ) değeriyle küçüldüğünü biliyoruz. Aşağıya doğru geldik; bu, sabit faktör oranında şundan daha küçük.  Ondan sonraki seviyede bunu toplayacağız. Yani  f (n/b) ² değeri çıkacak. Ben burada bir şeyi yanlış yazdığımı fark ettim;  parantez içinde özür dilerim. Bu (n/b) ²  olmayacak, (n/b²) olacaktı. Böylece bu dizi, en azından  üçüncü durumda geometrik olarak azalıyor. Eğer bir dizi sabit faktörlere kadar geometrik olarak azalırsa -- en büyük terim tarafından domine edilir. Ve bu da f(n) dir. Yani üçüncü durumda Teta( f(n)) ‘i elde ederiz. Diğer birkaç duruma bakalım ve bunları elimizde kalan zamana ayarlayalım. Ooo, daha çok zamanımız var, 5 dakikamız var; tonlarca zaman demek.

 

Pekiyi, ne yapacağız. Şunu yazayım. 3. Durumda maliyetler düşüyor. Şimdi burada ben nokta noktaların fonksiyonunun çok açık olduğunu söyleyebilirim. Burada bu çok basit.  Burada bu a’nın k’nıncı kuvveti carpı  f(n/b’nin k’nıncı kuvveti). ve üçüncü durumda biz maliyetlerin yada değerlerin geometrik olarak ağaçtan aşağıya gittikçe azaldığını kabul ediyoruz.

 

Bu 3. duruma başka bir açıdan yaklaşalım: Önce birinci durumu yapalım. Çünkü bu durumun anlaşılması sezgisel olarak daha kolay. Birinci durumda biz f(n)’nin bu değerden polinomsal olarak daha küçük olduğunu biliyoruz. Ama bu ortadaki basit prosedür vasıtasıyla bunu birazcık değiştiriyoruz. Burada daha formal bir tartışmaya ihtiyacınız olduğundan elimi sallıyorum. Ben diyorum ki, bu,  bu yönde geometrik olarak artacaktır; geometrik olarak artması gerekir, çünkü bu f(n) şundan polinomsal olarak daha küçüktür. Ve siz orta bölgede bazı polinomlar elde edeceksiniz ve bunlar küçükten büyüğe doğru yorumlanacak. Bu nedenle büyük olan bu değer  geometrik seri olduğu için domine edecektir. Yani hakim olacaktır. Daha önce söylediğim gibi bu bir öngörüdür; formal bir argüman değildir. Burada olan formaldi. Çünkü bunu biz böyle varsaydık ama şu andaki uygulamayı biraz daha tartışmamız lazım. Yani bunlar geometrik olarak artmayabilirler ama daha hızlı artabilirler ve bu da kabul edilebilir. Bu nedenle 3.durumda siz geometrik serilerin büyük terimi tarafından her zaman domine edilirsiniz. Burada bu f(n) dir. Ve burada da Teta () olan terim domine eder. 

 

2. durumda bu oldukça basit ama biraz logaritmaların özelliklerine bilmeniz gerekir. 2. durumda  biz bütün bunların temelde aşağı yukarı aynı olduğunu kabul etmiştik. Yani tepenin tabana eşit olduğunu kabul etmiştik. Ve bu şimdi, bu çok prosedürsel yol yada yöntem vasıtasıyla değişiyor. Yani orta bölgede olanlar  birbirine benzemek zorunda. Ama tam anlamıyla da değil, çünkü burada bir logaritma faktörümüz yok. Burada bir log k  durumumuz vardı; elimizde ( çarpı n) olan bir değer vardı. Bu durumda ise log k diye bir şey yok. Bu nedenle logaritmalar burada yok olur. Ama bunların yok olması daha yavaştır. Bu terimlerin üst yarısındakilere bakarsanız bunların hepsinde k nın logaritmasını göreceksiniz. Alt yarısında ise bunlar yok olmaya başlayacak. Ben size biraz kehanet sonucu elde edilen bilgileri veriyorum. Eğer logaritmaları ele alırsanız ve bağımsız değişkeni çok değiştirmezseniz logaritmalar kalacaktır. -- Belki de yarı yoldan biraz önce yok olacaklar.

Yani burada söylediğim şey aşağı yukarı her düzeyin birbirine yakın olduğu ama özellikle yarının  üstünde kalan seviyelerin asimptotik olarak birbirine eşit olduğu. Bu nedenle maliyet bir seviye yani buradaki f(n) çarpı düzey sayısı yani h dir; ve h =  n’dir. b aslında bir sabit olduğu için bizi ilgilendirmez. Bu Teta ( log n) dir.

Yani T(n) = (çarpı n  çarpı log n)  durumu oluşur  ve sonuçta [f(n) log n] kalır. Bu çok hızlı yapılmış bir taslak. Kusura bakmayın. 1. ve 2. durumlarda biraz özensiz davrandım. Bu nedenle kitaptan kanıtı okuyun. Çünkü bir evrede bunu öğrenmek zorundasınız; logaritmaları buna göre kullanacaksınız. Hepsi bu kadar. Sorunuz var mı?. Hepiniz gitmeye meraklısınız. Tamam teşekkürler.

 

Gelecek derste görüşürüz.