MIT Açık Ders malzemeleri
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(n³) 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³, n² nin büyük O fonksiyonu değildir; hatta n³ ü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², n³ büyük O fonksiyonuna eşittir demek yerine, anlatmak istediğimiz şey 2 n² nin, n³ 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)= n³+ O(n²). Burada amacımız hata sınırını belirlemek. Diyoruz ki, f(n) aslında n³’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) = 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), n³ 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), 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. n²+ 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 n’den asimptotik olarak daha büyüktür… Önceden gördüğümüz n² ile n³ 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..
n² yeterince büyük n değerleri için n³’ 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³ 'ü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 n²
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² + 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? n³. 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.