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 3

Herkese günaydın.. Bugün biraz algoritmalarla uğraşacağız. Algoritmalara geri döneceğiz ve geçen derste özyinelemeleri çözmek için kullandığımız ana teoremi geliştirip basit matematik yöntemlerle çözümler bulacağız. Bunları çokça kullanacağız. Çünkü bugün özyinelemeli algoritmalar konumuz.. Koşma zamanını, ana teoremi kullanarak bulacağız. Geçen sefer yaptığımıza benzer şeyler yapacağız; umarım geçen sefer bir hata yapmamışımdır. Birkaç idari hatırlatmam var. Gelecek etüde gelmelisiniz. Bu zorunlu. Ayrıca isterseniz gelecek ev ödevi laboratuarına da katılabilirsiniz. Bunu yapacaksanız problem setlerinin üzerinde laboratuar öncesi birkaç saat çalışmanızda yarar var. Aslında gelecek birlikteliğe kadar epey zamanınız var. Ve hafta başı ders yok. Bu öğrenci tatili denen bir tatil, onun için gelmeyin.

Bugün böl ve fethet denilen bir kavram üzerine çalışma yapacağız. Bu kavram aynı zamanda böl ve yönet olarak da bilinir. Ve Latince bilenleriniz için divide et imperia olarak söylenir ve tarihte denenmiş ve test edilmiş bir yöntemdir. Herhangi bir bölgeyi parçalara ayırıp ondan sonra orayı fethedersiniz. Bu parçalama değişik politik yaklaşımlar kullanılarak yapılır ve öyle yapılır ki o bölgede bölünme olur ve kimse birbirini sevmez. Aile içinde bir kan davası yaratmak gibi etkili bir yöntemdir. Testinizde bunu hatırlayın. Şaka yapıyorum tabii. Evet büyük bir güç yapısını daha küçük güç yapılarına bölerseniz ve bu küçük güç yapılarını yönetebilirseniz bunların hepsine hakim olabilirsiniz. Dikkat etmeniz gereken şey bunların tekrar bir araya gelmemeleridir. Bu İngilizlerin özellikle uyguladığı böl ve yönet yöntemidir. Ama bugün bizim yapacağımız İngilizlerin değil Cormen, Leiserson, Rivest ve Stein gibi algoritma kitabı yazarlarının yöntemlerini uygulamak olacak. Bu çok temel ve çok güçlü bir algoritma tasarım tekniğidir ve bu sizin ilk gerçek algoritma tasarımı deneyiniz olacak. Biz hala analiz modundayız. Ama artık gerçek tasarım yapmaya başlayacağız. Bu derste 2, belki 3 ya da 4 ana tasarım tekniğini işleyeceğiz. Bugünkü onlardan bir tanesi onun için bu çok önemli. Bu özyinelemelerin her türünü çözümlemede bir yöntem olacak ve geçen derste kullandıklarımızı da ele alarak bunun neden yararlı olduğunu göreceğiz. Tahmin edebileceğiniz gibi böl ve fethet’ in ilk adımı bölmektir. İkinci adımı da fethetmektir. Öte yandan aslında 3 adım olduğunu tahmin edememişsinizdir. Ben burada bir boşluk bırakacağım siz de aynısını yapın. Böl ve fethet bir algoritmik tekniktir. Size çözmeniz için büyük bir problem veriliyor. Siz bunu verimli olarak nasıl çözeceğinizi bilmiyorsunuz. Bu nedenle bu problemi alt problemlere bölüyorsunuz. Bu işin bölme kısmı. Bu problemi alt problemlere böleceksiniz daha doğrusu anlık uygulama problemlerine böleceksiniz. Ve bu anlık ya da parçalı problemler sizin alt problemleriniz olacak. Ve bu alt problemlerin daha küçük boyutlu olması gerekiyor. Daha küçük boyutlu olması demek n’nin değerinin orijinal problemde olduğundan daha küçük olması demektir. Evet bir şekilde çözüm konusunda bir ilerleme kaydettiniz. Şimdi elinizde çözmeniz gereken bir ya da birkaç problem var ve her biri orijinaline göre daha küçük. Ve siz özyinelemeli olarak her bir problemi çözeceksiniz.

Bu fethetme adımı; her alt problemi yinelemeli olarak fethediyorsunuz. Ondan sonra bunların çözümlerini bütün problemin çözümünü oluşturacak şekilde birleştiriyorsunuz. İşte genel böl ve fethet paradigması budur ve bir çok algoritma da buna uyum gösterir. Eğer hatırlayacak olursanız bu paradigmaya uyan bir algoritmayı daha önce görmüştünüz. Birleştirerek sıralama, evet. Hayret hepiniz uyanıksınız; etkilendim; evet daha önce birleştirerek sıralamayı görmüştük. Ve eğer biraz akıllıysam bunu buradaki boşluğa sığdırabilirim. Tabii, akıllı olmak lazım. Birleştirerek sıralamayla ilgili kısa bir tekrar yapacağım. Bu metottaki 1 2 3 formatını hatırlatacağım. Buradaki ilk adım diziliminizi 2 parçaya bölmekti. Bu çok önemli bir şey değil yani sadece düşünüyorsunuz, diyorsunuz ki “benim dizilimim 2 yarımdan oluşsun”. Burada herhangi bir iş yok. Bu sıfır zaman demek. Sadece dizilime şöyle bir bakacaksınız, işte burada. Aslında işe başlamadan önce belki n/2 ’yi hesaplamanız gerekir. Ama bu da sabit zaman alır. Ondan sonra da diyeceksiniz ki “benim dizilimim bir sol, bir de sağ parçaya bölünmüş”. Ondan sonra ilginç olan özyinelemeli olarak bunların her birini ayrı ayrı çözmek; işte bu fethetme evresi. Her alt dizilimi özyinelemeli olarak sıralıyoruz. Üçüncü adımda da bu 2 çözümü birleştiriyoruz ve bunun ne anlama geldiğini görüyoruz. Şimdi elimizde bu dizilimin tümevarım yöntemi ile sıralanmış bir versiyonu var; bu versiyonu da tümevarım yöntemi ile sıralamıştık. Şimdi bize lazım olan tüm dizilimin sıralanmış versiyonu; bunun da bir birleştirme problemi olduğunu, 2 sıralanmış dizilimin birleştirilmesinden oluştuğunu görmüştük. Ve bunun aslında doğrusal zamanda nasıl yapıldığını, yani n zamanında nasıl yapıldığını işlemiştik. Bunu tekrar yapmayacağım. Ama önemli olan bu çerçeve içinde ele alınabilineceğini görmek. Ben temelde koşma süresini ve birleştirerek sıralamayı bir özyineleme olarak yazmak istiyorum. Daha önce bu özyinelemeyi görmüştünüz. Çözümün de ne olduğu size söylenmişti. Ama şimdi bunun çözümünün nasıl olduğunu öğreneceğiz. Ve ayrıca böl ve fethet paradigmasına uyan her algoritma yaklaşık bu formda bir yinelemeye dayanacak; Özellikle de bizim eski dostumuz “Ana metod” buna uyarlı olacaktır.

Haydi, buna birleştirerek sıralamayı uygulayalım ve cevabı daha önceden bildiğimiz bir durumda biraz pratik yapalım. Bu birleştirerek sıralama özyinelemesiydi. Bu özyinelemeyi bilmeniz ve sevmeniz gerekiyor, çünkü her zaman karşınıza çıkacak. Bu genel yaklaşım sonucunda alt problemlerin boyutlarını gözlemlemek ve bunları çözümlemek, bunlardan kaç tane olduğunu ve ne kadar ekstra iş yapacağını saptayacaksınız. Burada bu alt problemlerin boyutları var. Öyle görünüyor ki her 2 alt problem de aşağı yukarı aynı boyutta. Burada biraz dağınıklığımız var. Aslında T’nin hem (n/2) tabanlı, hem de (n/2) tavanlı olması gerekiyor, ama bundan sonraki etüde geldiğinizde bunun neden problem olmayacağını, aslında tavan ve taban kavramlarının önemli olmadığını göreceksiniz. Burada bir teoremle karşılaşacaksınız ve bu teorem bu olgunun bir sorun olmadığını size kanıtlayacak. n’in 2’nin bir kuvveti olduğunu düşünebilirsiniz ama bu evrede sadece bunu böyle kabul edelim. Yani elimizde 2 tane problem var. Ve bunların boyutu n/2. Buradaki 2 aslında alt problemlerin sayısını gösteriyor. Ve bu n’in boyutu bize ne kadar ek iş yapacağımız konusunda fikir veriyor. Pekiyi, yapacağımız ekstra iş, potansiyel olarak ne kadar? Aslında fethetme her zaman bir özyinelemedir. Bu giriş kısmının dışında yapacağınız bir iş yok. Yani bu örnekte bölmek önemsiz olacak ama genelde biraz iş gerektirebilir. Birleştirme ise burada doğrusal bir iş gerektirecek. Böylece bu da bölmek ve fethetmek konusunda koşma zamanlarını anlatıyor. Buradaki özyinelemesiz iş budur. Ve bu da aslında bir böl ve fethet algoritmasının nasıl yinelemeye dönüştüreceğini gösterir. Aslında çok kolaydır ve genelde ana metod yani master method kullanılır. Burada.. 2. durumdayız. Çok güzel, evet bu 2. durum ve burada k sıfır değerinde. Böylece bizim özyineleme ağacımızda tüm iş maliyetleri aşağı yukarı aynı olur. Bunların hepsinin değeri () oranlıdır. Burada n’in log 2 bazında 2 kuvveti sadece n’dir. Onun için bunlar eşittirler. Elimizde özyineleme ağacındaki dallara ya da seviyelere bağlı ekstra bir logaritma faktörü kalır.

Ana metodun arkasındaki sezgi olgusunu hatırlatırım. Bu n log n ve bu iyi bir şey. Birleştirerek sıralama n log n’yi çözmek için hızlı bir sıralama algoritmasıdır. Araya yerleştirme sıralaması n² üzerinde çalışır. Bir açıdan n log n uygulayabileceğiniz en iyi durumdur. Bundan sonraki 2 derste bunu işleyeceğiz. Ama şimdiden size ön bilgi veriyorum. Bugün birkaç farklı böl ve fethet algoritması üzerine çalışacağız. Sıralama bunlardan bir tanesi. Ama aslında çözmek isteyeceğimiz bir sürü problem daha var. Öyle görünüyor ki böl ve fethet olgusunu temelde bunların birçoğuna uygulayabilirsiniz; ama hepsine değil. Örneğin, sabahleyin nasıl uyanmalıyım olayını böl ve fethetle çözmek o kadar kolay değil. Aslında bu problem setleri içerisinde iyi bir problem olabilir.

Sıradaki böl ve fethet algoritması aslında sıralamadan daha kolay. Birleştirerek sıralamadan bile daha kolay. Ama eğer tek alt probleminiz varsa buradaki çözümü göstermek için çok iyi bir örnek. İçinizde kaç kişi daha önceden binary search yani ikili aramayı görmüştü? Görmeyen var mı? Sadece 1 kişi, tamam. Bu durumda biraz daha hızlı gideceğim. Elinizde bir x elemanı var. Ve siz bu x elemanını bir sıralanmış dizilimde bulmak istiyorsunuz. Bunu etütten önce görmemiş olan var mı? Yok, iyi. Yani bunu başka bir derste görmüş olabilirsiniz. Çok iyi, demek ki ön koşul derslerini almışsınız. Ben bunu böl ve fethet olarak sınıflamak istiyorum. Çünkü genelde bu olguya o açıdan bakılmamış olabilir. Bu işlemde bölme adımı x ’in diziliminizin orta elemanı ile karşılaştırılmasıdır. Ve ondan sonra fethetme adımı gelir. İşte diziliminiz burada ve burada da orta değer var. Burada x’i diziliminizin orta elemanıyla karşılaştırırsınız; diyelim ki x ondan küçük olsun. Bu durumda x ‘in sol yarımda olduğunu bilirsiniz. Ve burada güzel bir döngü değişmezi vardır. Ama bu problemde özyinelemeli olarak düşüneceğiz; problemi x ‘in bu alt dizilimdeki yerini bulmak için kullanacağım. Birleştirerek sıralamadaki iki özyineleme yerine burada bir alt dizilim var. Ondan sonra birleştirme adımında herhangi bir şey yapmayacağız. Demek istediğim, eğer x ‘i burada bulursanız ondan sonra bütün dizilimde bunu arama zorunluluğunuz kalmaz. Yani bunu tekrar yapmanıza gerek olmaz. Evet bu aslında ikili aramanın böl ve fethet paradigmasına uyarlanmasıdır. Bu çok önemli bir örnek değildi. Fakat öyle durumlar var ki siz bu özyinelemeyi sadece bir tarafta yapabilirsiniz. Tabii önemli olan 2 özyineleme yapmak yerine 1 özyineleme yapmanın arasındaki farkı görmektir. Bu ikili arama için yapılan bir özyineleme uygulaması. Biz n boyutunda bir problemle işe başlıyoruz. Sonra bunu 1’e düşürüyoruz. Burada görünmeyen 1 faktörü var . Yani n/2 boyutunda bir alt problem var. Tekrar ediyorum. Burada tavan ve tabanlar çok fark etmiyor. Ek olarak da elimizde x’in orta elemanla karşılaştırılması işlemini anlatan bir sabit var. Yani sonuç olarak bu tek bir karşılaştırma yapılacak gibi görünüyor. Bunun bir çözümü var; log n. Ve hepiniz ikili aramanın koşma süresini biliyorsunuz. Ama biz burada yinelemenin çözümlemesine bakıyoruz. Söylemek istediğim şey arada birkaç farklılık olması. Elimizde mesela toplanır düzende bir n terimi yok. Eğer olsaydı o zaman bu doğrusal olurdu. Koşma süresi doğrusal olurdu. Ama bu bile n log n ‘den daha iyi. Böylece biz 2 den kurtuluyoruz. Onun değerini 1’e düşürüyoruz. n’yi alıyoruz ve değerini 1’e düşürüyoruz. Bu koşma süresini çok daha hızlandırır, n kere hızlandırır.. Burada herhangi şaşırtıcı bir şey yok.

Şimdi daha enteresan algoritmalar kullanalım. Bir sayının kuvvetini alma problemi; size x sayısını veriyorum. Bu gerçek bir sayı veya kayan noktalı bir sayı olabilir. Her neyse. Ve size bir de n tamsayısını veriyorum. n ≥ 0 olmak üzere. Burada x’in n kuvvetini hesaplamak istiyorum. Gördüğünüz gibi çok basit bir problem. Aslında bir açıdan bütün bunlardan daha basit. Ama işte burada. Ve böl ve fethet yöntemi buradaki sıralama için yapılacak doğru şey. Evet bu naive yada saf algoritma gerçekten çok basit.

x ‘in n’inci kuvvetini nasıl hesaplarsınız? Bu işlemin tanımından yola çıkarsak x’ i n kere kendisiyle çarpmam gerekir. Yani, X çarpı X çarpı X çarpı x toplam kaç n kopyası varsa. Ve bu x ‘in n’inci kuvvetini verir. Önemli bir sürpriz yok burada. Yani n sayısında çarpma var, daha doğrusu n-1 sayısında çarpma var ve bu da Teta(n) zamanı demektir. Ama bu problemin çözümünde bu yapılabilecek en verimli iş değil. Böl ve fethet yolunu kullanarak bu yöntemle ne yapabileceğimizin konusunda önerisi olan var mı? Daha önce bu algoritmayı görenler var mı? Birkaç kişi. Ama ben geri kalanlarla da ilgileniyorum. Anında yaratıcılığı test etmek, çok zor olmasına rağmen benim her zaman hoşuma giden bir olgudur. Fikirlerinizi rastgele söyleyin. Bu problemi doğrusal zamandan daha çabuk nasıl çözebiliriz? Bu nasıl bir böl ve fethet problemidir? x ve n girişlerimiz var. Tamam bunu x’e bölerek çözmeye çalışabiliriz. Ama bu biraz zor. Bir sayı olması lazım. Veya bunu n’e bölerek de yapabiliriz. Herhangi bir tahmini olan var mı? Evet. x’ in (n/2) kuvvetine bakmamız yararlı olabilir. Çok iyi. Bu böl ve fethet algoritmasının temelindeki fikirdir. Evet ‘ye bakmak istiyoruz. Bu biraz şaşırtıcı olacak. Şimdi taban değerlerine ve çatı değerlerine dikkat etmemiz gerekiyor. Söylemek istediğim şey burada, çarpı haline dönüşüyor. Ve bunun tutarlı olması için n’in çift sayı olması gerekiyor. Eğer n tek sayıysa o zaman burada daha dikkatli olmam gerekir. Ama şimdi sezgimize dayanarak böl ve fethet algoritmasının niye yararlı olabileceğini düşünelim. Diyelim ki elimizde n boyutunda bir problem var. Biz bunu boyutu n/2 olan 2 alt problem haline dönüştürüyoruz. Ama aslında bunlar aynı alt problem. Bu nedenle sadece 1 tanesini çözmem yeterli olacak. Yani x’in n/2 kuvvetini hesaplarsam, o zaman öteki x’ in n/2 kuvvetini de bulmuş olacağım. Böylece n/2 boyutunda özyinelemeli 1 işlem olur ve ondan sonra ben bu sayının karesini alırım. Ve bu sadece tek işlem. Yani ikili aramada olduğu gibi aynı yineleme var; bu log n zamanlı ve her zaman n zamanlı olanlardan daha iyi. Hoş değil mi.

Ama aynı zamanda tek sayı olma durumunu da çözmem lazım. Yani n’in tek sayı olma durumu. Bu durumda değerine bakacağım. n – 1 in çift sayı olması lazım. Burada da eksik olan bir x faktörü olur. Eğer n tek sayıysa o zaman 1 özyinelemeli işlem ve 2 çarpma yapacağım. Ama yineleme aynı. Bu özyinelemeli problemin boyutu n/2 artı sabit bir zaman; buradaki işlem 2’ye bölme işlemidir. Ve birleştirme işi de bir veya 2 çarpma yapma işidir. Ve bu da log n’dir. Eğer yapmanız gereken işlem sayıların çarpılmasıysa logaritma n olabilecek en iyi durumdur. İyi. Basit ama çok güçlü… Bundan sonra eğer bir sayının kuvvetini hesaplamak istiyorsanız artık ne yapacağınızı biliyorsunuz.

İçinizde Fibonacci sayılarının tanımını bilmeyen var mı?. Veya bilmediğini itiraf etmek isteyen var mı? Evet bu iyi bir eski dost. Ben bu tanımı size hatırlatmak için yazacağım ve özellikle de taban durumlarıyla ilgili olanını yazacağım. Diyeceğim ki, Fibonacci sayıları çok önemlidir, çünkü doğada çok fazla görülür. Birtakım meyvelere bakarsanız Fibonacci dizisini görürsünüz. Her dilimin etrafındaki çıkıntılara bakıp saydığınız zaman Fibonacci görünür. Eğer kumsaldaki kuma bakar ve dalgaların sahile nasıl vurduğunu gözlemlerseniz bana söylendiğine göre bu bir Fibonacci dizisidir. Çevreme baktığımda her tarafta Fibonacci dizileri görülür. Peki doğa Fibonacci Dizisini nasıl hesaplıyor? Aslında bu başka bir dersin konusu. Pekiyi ama biz Fibonacci Dizisini en hızlı nasıl hesaplayabiliriz? 2 tane algoritma gördüğünüzü varsayıyorum ve bunların içinde en safı da özyinelemeli algoritma. Burada diyorsunuz ki, ‘de eğer n = sıfırsa, sıfıra dön. n = 1 ise, 1 e dön. Aksi halde özyinelemeli olarak ‘i hesapla, ‘i hesapla ve bunları birbiriyle topla. Bunu daha önce görmüş olanlara soruyorum, bu algoritmayı uygulamak ne kadar zaman alır? Bunu tahmin etmenin zor olduğunu düşünüyorum. Onun için çok kesin cevap vermeye çalışmayın. Tamam, pekiyi bu algoritmayı daha önce kaç kişi gördü ve çözümledi? Sınıfın yarısı. Tamam, o zaman koşma süresi nedir? Uzun, çok uzun öyle mi?. Kesin cevap vermek isteyen var mı? Anlayamadım?.

Exponensiyel yani üstel, evet. Bu daha doğru ve daha kesin bir açıklama. Ama bundan daha da kesin olmak istiyorum. Belki daha önce bu çözümlemeyi görmemişsinizdir. Bu değer ‘ye (fi’nin n kuvvetine) eşittir. Ve burada altın oranı temsil eder. Altın oran matematik dünyasında hemen her yerde görülür. Korkarım ki bu derste bundan sadece bu kez bahsedeceğiz. Ama hak ettiği yeri aldığı için mutluyum. Buna üstel zaman denir. Bilmeniz gereken bunun birden büyük olduğudur. Bu üstel zamandır. Üstel zaman temelde herhangi bir sabitin n kuvvetine eşittir. Üstel zaman çok uzun bir zamandır; kötüdür. Polinomsal zaman ise iyidir. Bizim istediğimiz şey polinomsal zamanlı algoritmalardır. Bu sınıf temelde bütünüyle polinomsal zamanlı algoritmalar üzerinde durur. Soru mu var? Tamam, algoritma ne yapıyor bir kez daha tekrar edeyim. Fibonacci fonksiyonunu tanımlıyor. Ben önce taban durumlarını kontrol ediyorum. Sonra Fibonacci (n-1) ’i özyinelemeli olarak ele alıyorum. Fibonacci (n-2) ’yi özyinelemeli olarak alıyorum ve bu 2 sayıyı birbiri ile topluyorum. Böylece bu dallanan ağacı elde ediyorsunuz. Aslında yaklaşık aynı boyuttaki 2 alt problemi çözüyorsunuz ve bunların arasındaki boyut farkı toplamda 1 veya 2 mertebesinde daha küçük. Söylemek istediğim problem boyutunu hemen hiç küçültmüyorsunuz. Bu nedenle bunun üstel olması gerektiği içimize doğuyor. Bir özyineleme ağacı çizerseniz. bunun ne kadar çabuk büyüdüğünü görürsünüz. Demek istiyorum ki, n / 2 düzeyinde sadece bir dalda problemi n den n/2 ye küçültürsünüz. Ötekinde ise belki de n den 1 e kadar inmiş olursunuz. Fakat dallarının hiçbirisi n/2 düzeyinden sonra durmaz. Elinizde en azından 2 nin n/2 kuvveti var. Ve bu karekök 2 nin n’inci kuvvetine) eşittir. Ve bu da ‘nin n kuvvetine yaklaşık bir değerdir. Yani bu kesinlikle üsteldir ve üstel olması kötüdür. Biz polinomsal istiyoruz. n², n³ , log n iyi olur. Yukarıda bir polinomla sınırlı olan her şey iyi olacak. Bu eski bir fikirdir. Bu fikrin izini kombinezonlar optimizasyonu yada katışımları eniyileme dünyasının ünlü isimlerinden Jack Edmonds’a kadar sürebilirsiniz. O polinomsallığın iyi bir şey olduğunu söylemişti. Ben onu akademik büyükbabam olarak kabul ederim. Çok enteresan bir insandır. Evet. Bu nedenle bu oldukça kötü bir algoritmadır.

Sizin daha iyi algoritmalar görmüş olduğunuzu sanıyorum ki bunlar buradaki özyinelemeli algoritmanın aşağıdan yukarıya ters çevrilmesi ve uygulanmasına benzeyebilir. Bu konuyu başka türlü düşünmenin bir yolu da eğer Fibonacci (n) için bir özyineleme ağacı yaparsanız, aşağıdaki alt ağaçlarda birçok ortak yapı olduğunu görür ve zaman kaybettiğinizi fark edersiniz. Fibonacci (n-1)’ i çözdüğünüz zaman, Fibonacci (n-2)’ nin de çözüldüğünü görürsünüz. Bir şeyi niye 2 defa çözelim? Bir defa çözmek yeterli olur. Bu nedenle bunu aşağıdan yukarıya doğru çözmeye başladığınız zaman kolaylıklar ortaya çıkar. Bu işlemi aynı zamanda daha önce hesaplamış olduğunuz bazı cache yada önbellekteki bilgileri yinelemeli olarak kullanarak ta yapabilirsiniz. Bu çok büyük bir sürpriz olmaz, Fibonacci sayılarını sırasıyla hesaplarsınız. Ve her seferinde örneğin ’i hesapladığınızda ondan önceki ikisini de hesaplamış olursunuz. Bunları birbiriyle toplarsınız ve bu sabit bir zaman alır. Bu durumda koşma süresi lineer yani doğrusaldır; n cinsinden doğrusaldır ve bu bizim girişimizdir. Çok iyi. Bu yapabileceğimiz en iyi bir şey midir? Hayır. ’i doğrusal zamanda hesaplamaktan daha hızlı hesaplamanın yolları konusunda bir fikri olan var mı? Şimdi bir çoğunuzun şu ana kadar gördüğünden biraz daha ayrı bir yol kullanmamız lazım. Şu ana kadar gördüğünüz tekniklerle bunu yapma konusunda bir fikri olan var mı? Evet, evet. Biz fi ve psi’nin n nci kuvvetleri konusunda matematiksel bir hile yapabiliriz. Aslında fi, fi, pi, fo, pu, hangi Yunan harfini kullanırsanız kullanın; iyidir. Matematiksel hile şöyle olacak, söylediğimiz gibi gerçekten hile yapacağız. İyi bir şey değil ama yararlı; buna naive recursive squaring yani saf özyinelemeli kare alma diyeceğiz; özyinelemelerin karesini almayı biliyoruz ve özyineleme karesini almak log n zamanı alır.

Haydi özyinelemeli kare almayı uygulayalım. Bilmeniz gerekmiyor ama eğer Fibonacci sayılarının özelliklerini biliyorsanız, ki şimdilik bilmediğinizi düşünüyorum, bunlardan bir tanesi şudur: Eğer ‘nin n’inci kuvvetini e bölerseniz, sonra da bunu en yakın tam sayıya yuvarlarsanız, bu n’inci Fibonacci sayısıdır. Bu güzel bir şey. O halde aslında ‘ne eşit. Bundan yola çıkarak özyineleme karelemesini ‘nin n kuvvetini log n zamanında hesaplamak için kullanabiliriz. Çıkan sonucu 5 e böleriz ve bilgisayarımızda çıkan değeri en yakın tamsayıya yuvarlayabilen bir yazılım varsa, işimiz bitti demektir. Fakat bu her zaman çalışan bir sistem olmaz. Gerçek bir bilgisayar büyük ihtimalle yi ve 5 ‘i kayan noktalı sayılar olarak kullanır ve bunların da belli sayıda bitleri vardır. Ve bu hesaplamayı gerçek dünyada yapmaya kalkarsanız bazı önemli bitleri kaybedersiniz. Bu durumda da en yakın tamsayıya yuvarlama ihtiyacı karşısında doğru cevap çıkmayabilir. Yani kayan noktalı sayıları kullanan bir bilgisayarda sonunda doğru cevap bulamayabilirsiniz. Bu sayılarla istediğinizi yapabilecek teorik bir makinede bile sabit bir zamandan daha fazla sürecek çarpım süreleri olacak. O halde başka bir modele bakmak zorundayız. Çünkü kere yi sabit bir zamanda çarpamazsınız. Bu tabii bu dersin konusunun dışında. Onun için bunu böylece kabul edin. Normal bir makinede bazı problemleri sadece üstel zamanda çözebilirsiniz. Ama elinizde gerçek sayıları çarpabilen ve sonra da bunu en yakın tam sayıya çevirebilen bir makine varsa, o zaman bu tip soruları polinomsal zamanda çözebilirsiniz. Ama buna izin verilmez. Ben şimdi size 3 ders sonrasının konularından biraz bahsediyorum. Onun için burada keseceğim daha fazla bu konuyu uzatmayacağım. Ancak Fibonacci sayılarının başka bir özelliğini kullanırsak özyineleme karelemesini başka bir yolla çözebiliriz. Ve bu noktada hep tam sayılara bağlı kalacağım, böylece her şey daha kolay olacak. Bu arada etüde gitmeyi unutmayın; dilerseniz ev ödevi laboratuarına da gidebilirsiniz. Ancak hafta başı buraya gelmeyin; sizden bunu istiyoruz.

Bu aslında doğru bir özyineleme kare alma algoritmasıdır ve daha önce bunu görmediyseniz, bunun ne olduğunu tahmin etmeniz zordur. O nedenle ben size burada göstereceğim. Ben buna teorem diyeceğim ve bu sınıfta teorem sözcüğünü ilk kez kullanıyorum. Bu teoremin sonunda öyle bir sonuç çıkar ki, bu matrisin n’inci kuvvetidir. Hoş değil mi. Buna bir süre şöyle bakarsanız bir süre sonra “ evet, gayet tabii” diyeceksiniz. Bu teoremi size biraz sonra kanıtlayacağım. Ama elimizde böyle bir teoremimiz varsa o zaman yi bu matrisin n’ninci kuvveti olarak hesaplayarak bulabiliriz. Bu 2 x 2 bir matris. Siz 2 adet 2x2’lik matrisi çarparsanız, sonuçta yine bir 2x2 matris elde edersiniz. Bu nedenle bu sabit boyuttadır. 4 tane sayı vardır ve ben 4 tane sayının üstesinden gelebilirim. Bu durumda kayan noktalı uygulamalarla ilgili bir sürü saçma problemle karşılaşmam; uğraşmam gereken sadece 4 tane sayı var. Matrislerde bir taraftan büyümüyor. Böylece bu böl ve fethet algoritmasının koşma süresi yine log n olacak, çünkü her 2 ye 2 matris çarpımının sabit zaman alacağını biliyoruz. Evet? A, evet, teşekkür ederim; bir yazım hatası yapmışım, özür dilerim. ‘in aslında sol üst köşede olmasını umuyorum. Ama bir dakika bunu bir kontrol edeceğim; ediyorum. Evet, sağ üst köşede olmalı. Sizin de söylediğiniz buydu değil mi?. Burada daha çok yere ihtiyacım var; kusura bakmayın. Burada sol tarafta da 2x2 bir matris olması gerekiyordu. Teşekkür ederim. Böylece bu matrisin n‘ninci kuvvetini log n zamanında hesaplayabiliyorum; ve ister sağ üst köşe, ister sol alt köşedeki değeri seçtiğimde, bu Fibonacci sayısı oluyor. Bu da bana log n düzeyinde bir zaman algoritmam olduğunu gösteriyor ve bunun benzeri ile son yineleme uygulamalarımızda, yani ikili arama ve özyinelemeli kare alma algoritmalarında karşılaşmıştık. Bu değer logaritma n artı bir sabit, yani log n’dir.

Şimdi teoremi kanıtlayalım. Bu teoremin kanıtlanmasında hangi teknikleri kullanmamız gerektiği konusunda önerisi olan var mı? Daha doğrusu tekil sorayım. Hangi teknik kullanılmalı? Tümevarım. Çok güzel. Bu güne kadar bu soruyu ne zaman sorduysam cevap hep tümevarımdı. Bu gelecek derslerim için bana bir uyarı olmalı. Arkadaşlarımdan biri aldığı bir çözümleme dersinde “profesör ne zaman soru sorsa sorularının yanıtı hep 0 olmuştur” dedi. Eğer çözümleme dersi aldıysanız bu gerçekten komik bir durum. Yani ben de bazen eğlenmek için cevabı sıfır olan birkaç soru sorabilirim. Haydi şimdi tekrar n üzerinde tümevarım yaklaşımını ele alalım. Aslında yapılması gereken şeyin bu olduğu oldukça açık. Ama bazı durumları kontrol etmemiz lazım. Taban şıkkında matrisin birinci kuvveti var; yani kendisi: 1, 1, 1, 0. Tabii burada n en az 1 olmalı demeliydim. Yazdıklarımı sizde kontrol edin; bunların , olması gerekir. Sizde kontrol ederseniz göreceksiniz. 0’a eşit, 1’e eşit, ve de 1’e eşit. İyi, taban durumunda bu doğru. Bundan sonraki adım da çok heyecan verici değil ama sizin algoritmanızın doğru olduğunu mutlaka kanıtlamanız gerekiyor. Hesaplamanız gereken şey bu olsun. Bunu yapmanın birçok yolu var ama şöyle başlayalım. Bunu hızlı bir şekilde yapalım, çünkü çok heyecan verici bir iş değil. Hangi yönde gidelim, Şu yönde gidelim: Ben n’in tümevarımına ulaşmaya çalışıyorum. n’in tümevarımını elde etmek istiyorsam o zaman doğru bildiğim bir noktadan başlayıp bu bilgileri kullanmam gerek. Eğer n nin değerinini 1 azaltırsam bildiğim özellik bu matrisin değerleri 1, 1, 1, 0 ‘ın n-1’nci kuvvetine eşit olduğu. Ben bunu tümevarım hipotezinden zaten biliyorum. 1, 1, 1, 0’ın n-1 nci kuvveti. Bu durumda ben bu yöntemi bir şekilde kullanabilirim. Bu eşitlik fark etmiş olabileceğiniz gibi henüz doğru değil. Buna bir şeyleri daha eklemem lazım. Bunu doğru kılmak için neyi eklemem gerekir? Evet 1, 1, 1, 0 gibi bir faktör daha eklemem gerekir. Bir bakıma bu kanıtlamayı geliştirdiğim yöntem kullanabileceğim tek yöntem. Eğer tümevarım yöntemini kullanıyorsanız bundan başka bir şey kullanamazsınız. Ama ondan sonra kontrol etmeniz gerekir. Kontrol sonucunda bu eşitliğin tutarlı olduğunu görüyorum. Örneğin bu 2 şeyin çarpımına eşit. Yani bu sütunla bu satırın çarpımına eşit.. Bu değer kere 1 artı kere 1 ve bu da ‘in tanımıdır. Ve buradaki değerlerin dördünü de kontrol edebilirsiniz. Bu doğrudur. Çok iyi. Eğer bu doğruysa o zaman ben bunları birleştirebilirim. Yani 1, 1, 1, 0 ‘ın n-1’inci kuvveti ile 1, 1, 1, 0 ın çarpımı, 1, 1, 1, 0 ın n’inci kuvvetini verir; beni kanıtımın sonuna getirir. Çok basit bir kanıtlama yöntemi. Fakat algoritmanızın gerçekten çalışıp çalışmayacağını bilmek için bu işlemi yapmanız lazım. İyi. Soru mu var? Teşekkür ederim. Bu sağ alttakinin olması gerekiyor. İşte bu nedenle kanıtlarınızı kontrol etmeniz gerekiyor. Bu hatayı aslında şu sırayla bu sütunu çarparken keşfedecektik. Ama sizin zaten burada olma sebebiniz de bu; benim hatalarımı gidermek. Burada olmanın bir testte olmaktan daha iyi yönü de bu işte. Bu çok büyük bir hata değildi; böyle bir hata yaparsanız çok fazla not kaybetmezsiniz.

Tamam, başka böl ve fethet algoritmaları. Şu ana kadar hep basit olanlarla ilgilendik. Bunların içinde en ilginci birleştirerek sıralamaydı ve bunu daha önceden çözmüştük; çok heyecan verici de değildi. Ve bunun dışındakilerin hepsi log n zamanını alıyordu. Haydi biraz log n dünyasından çıkalım. Sanırım artık ana metodu ezberlemişsinizdir; bu nedenle bunu siliyorum. İyi. Şimdi yapacağımız iyi bir test olacak.

Bir sonraki problem matris çarpımları üzerine ve kullandığımız iki 2 x 2 matrisin çarpımından yola çıkarak n x n boyutunda matrislerin çarpımlarının nasıl uygulanacağını göreceğiz. Sizin matris çarpımlarını bildiğinizi varsayıyoruz ama bunların bir algoritmaya dönüştürülmesi için size kısa bir hatırlatma yapacağım. Elimizde 2 tane matris var. Büyük A ve büyük B;. ij elemanlarında, i bir sırayı j de bir sütunu tanımlıyor ve biz bunlara küçük ve küçük diyeceğiz. Hedefiniz bu matrislerin çarpanını hesaplamaktır. Belki de belirtmem gereken şey i ve j nin 1 den n ye kadar değer aldığıdır. Yani bunlar kare matrisler. Bunların çıkışı yani C matrisi, A ve B matrislerinin çarpımı olacak ve elemanlarına sahip olacak. Hatırlatmak gerekirse, herhangi bir matris elemanı, A’nın i sırasıyla B’nin j sütunundaki iç elemanların çarpımlarının toplamına eşittir. Bunu söyle bir toplam olarak yazabilirsiniz. Bunun hesaplamasını, her i ve her j için yapmak istiyoruz. Bunu yapacak en belirgin algoritma hangisi? Yani, her i ve her j için toplamları hesaplayacaksınız. Yani tüm çıkışları, tüm toplamları hesaplayacaksınız. Burada toplam n operasyon var gibi görünüyor kabaca. Yani belki 2n-1 gibi, her neyse. n düzeyinde operasyon var. C nin altında hesaplamam gereken n² düzeyinde giriş öğesi var, bu da n³ zamanı demektir. Ben şunu yürekten programcı olanlar için yazacağım: Pseudo code, sözde kodu bu. Ben genellikle sözde kodu pek kullanmıyorum. Ama bu algoritma oldukça basit bir algoritma olduğu için bunu çok detaylı olarak yazabilirim. Ama program yazmayı seviyorsanız bu çözümlemeyi yaparken size bir temel verir. Bu döngü içinde üçlü bir iç içe yerleştirme olduğunu görürsünüz. Burada bir kod hatası yaptım. Umarım buraya kadar yazmamışsınızdır. nin 0 dan başlamasını istiyorum. Ondan sonra da ye uygun çarpımı, yani ’yı ve yi ekleyeceğim. İşte algoritma bu. Önemli olan 1’den n ye kadar olan döngülerde n kadar iç içe yerleştirme olduğunu görmeniz. Bu n³ zamanına mal olur. Çünkü bu sabittir ve bu da sabittir. Basitçe söylemek gerekirse n³. Haydi bundan daha iyisini yapmaya çalışalım.

Tabii bu amaç için böl ve fethet yöntemini kullanacağız. Pekiyi, şimdi bir matrisi nasıl böleceğiz? Bir matrisin içinde bir sürü sayı var. Her birinin içinde n² sayısında. Bölmenin birçok yöntemi var. Şu ana kadar yaptığımız bütün böl ve fethet problemlerini n boyutlu matrisleri n/2 boyutuna indirgeyerek çözdük. Ve problemlerin boyutu da n² gibiydi. Şimdi burada ben n x n boyutunda matrislerle başlayacağımı varsayıyorum ve bunları n/2 ye n/2 oranına dönüştürmek istiyorum. Bu işlemi nasıl yapacağım konusunda önerisi olan var mı? Evet, matrisin blok formunu kullanarak. Doğru cevap. Bu birinci böl ve fethet algoritması olacak ve çalışmayacak ama bizim ihtiyacımız olan ilk fikir. Bu eşitliğe bakalım ve şunu görmeye çalışın: Bir 2 x 2 blok matris ve bu matrisin her elemanı n/2 ye n/2 alt matrislerden oluşuyor. Ben C matrisinin dörde bölündüğünü varsayıyorum. r, s, t, ve u. Bunları küçük harfle yazmış olmama rağmen bunların matris olduğunu unutmayın. Her biri n/2 ye n/2 boyutunda. Ve A matrisini a, b, c, d parçalarına böleceğim ve B ile çarpacağım. B’yi de e, f, g, h parçalarına böleceğim. Neden bölemeyeyim? Yaptığım şey tamamı ile doğru. Ve eğer doğrusal cebir dersi aldıysanız, matrislerle ilgili bu işlemlerin yapılabileceğini biliyorsunuzdur. Şimdi bunların 2 ye 2 boyutunda olduğunu düşünebilirim. Sonra bu küçük harflerin aslında birer matris olduğunu unutalım ve diyelim ki r bu sıra ile bu sütunun değerlerinin çarpımıdır. Yani ae kere bc nin çarpımıdır. Burada hile yapmayayım. Aksi taktirde çok kolay olur. r = ae + bg, s = af + bh, t = ce + df pardon dg ve u = cf+ dh. Kendinizi fazla zora sokmamalısınız. Tamam, şimdi bunları doğru hesapladım. İyi. Yani yaptığım, bu çarpımı nasıl genişleteceğimle ilgili bir örnekti. Şimdi elimizde özyinelemeli bir algoritma var ve aslında elimizde yine bir böl ve fethet algoritması var. İşe bizim n x n boyutundaki matrisimizle başlıyoruz. Aslında elimizde bunlardan 2 tane var ve biz bunları 8 küçük parçaya bölüyoruz. a, b, c, d, e, f, g, h. Ondan sonra bunları bize C yi verecek şekilde hesaplıyoruz ve birbirleri ile birleştiriyoruz. Pekiyi bunları nasıl hesaplıyoruz? Çünkü harflerin arasındaki bu masum görünüşlü küçük operatörler, aslında özyinelemeli matris çarpımları; bu küçük harflerin her biri (n/2) ye (n/2) boyutlu birer matris olduğundan, sonucu bulmak için hesaplamayı özyinelemeli olarak yapmak zorundayım. Elimizde 8 tane (n/2) ye (n/2) matrisin özyinelemeli çarpımı var; bizi zorlayacak olan bu. Ondan sonra 4 toplama yapacağız ve buna ek olarak da küçük bir birleştirme çalışması yapacağız. İki matrisi toplamak için gerekli süre nedir? ; bu oldukça ucuz sadece zaman alacak. Unutmayın daha önceden yaptığımız uygulamada matris çarpımları zamanda alınıyordu, şimdi onu geçmeye çalışıyoruz. Matris toplamaları ise daha kolay bir problem, sadece bütün sayıları birbiriyle toplamanız lazım; gene de den daha hızlı yapamazsınız. Yani bu yinelemeli bir uygulama değil, iyi yönü bu; fakat kötü olan yönü bu yinelemelerden sekiz tane olması. Bu durumda T(n) = 8T(n/2) + Teta () olur. Bu arada ana metodu silmiştim fakat onu zaten ezberlemiş olmanız gerekirdi. Bu yinelemenin çözümü nedir? Θ () ; bu rahatsız edici bir değer. Pekiyi a 8, b 2 ise, 8’in iki tabanlı logaritması 3 eder ve bütün bilgisayar bilimcilerinin bunu ezbere bilmesi gerekir. = olduğunda, bu ‘den polinomsal olarak daha büyüktür ve onun için birinci durumdayız . Şimdi bunları ters çevirelim; bu , önceki algoritmamızdan daha iyi bir durum değil, bu pek hoş görünmüyor. Ve şimdi ilahi sezgi geliyor. Şuraya geçelim.. Fibonacci algoritmaları gibi öyle algoritmalar var ki bir süre düşündüğünüz zaman bunu çözümlemeniz o kadar büyük bir iş değildir. Söylemek istediğim şey matrise bakarsınız ve aklınızı kullandığınızda her şeyin doğru işleyeceğini görürsünüz. İlk bakışta o kadar açık değil ama, müthiş zekice bir yaklaşım; bu algoritma gerçekten çok akıllı bir algoritmadır. Bunu daha önce görmüşseniz hayranlığınız o kadar yüksek seviyede olmayabilir ama bu o kadar güzel bir uygulamadır ki bununla tekrar karşılaşmak sizi mutlu eder. Ştrassen’in bu algoritmayı bulabilmesi için çok akıllı olması gerekirdi. Buradaki düşünce, şu çarpmalardan kurtulmaktır. Yüzlerce toplama yapsam bu toplamaların maliyeti bana Θ () olur. Bu 8’i daha küçük bir sayıya dönüştürmem lazım; bunun için matris boyutlarını 3x3 veya benzerine değiştirmeye kalktığınızda bunun size çok yararı olmadığını görürsünüz. Aynı boyutta bir problemle karşılaşırsınız çünkü temelde kullandığınız şey aynı algoritmadır, sadece düzen değişir. Buna karşılık ne yapıp yapıp çarpma sayısını mutlaka azaltmamız lazım. Bunu yediye azaltalım; buradaki savımız eğer elimizde ikiye iki boyutunda matrisler varsa bunların çarpımını yedi çarpma işlemi ile yapabileceğimizdir. Eğer bu varsayım doğru ise o zaman sekiz çarpımı yediye düşürürüz ve işlemi biraz daha hızlandırabiliriz. Nasıl olduğunu biraz sonra göstereceğim. Bunu kafadan da hesaplayabilirsiniz. Öte yandan sıkılıp tam sayı olmayan logaritmaların hesabı ile uğraşmak istiyorsanız yolunuz açık olsun. Tamam. Şimdi bu algoritma maalesef biraz uzun ama sadece yedi çarpma içeriyor. Bu büyük P’ lerin her biri iki şeyin çarpımına eşit ve sadece toplama veya çıkartma içeriyor, aynı şey, yani aynı boyutta iş yapılıyor. Bunlar yedi çarpma işlemi, ben bunları 7 T(n/2) kapsamında hesaplayabilirim. Aman, altıncıda yanlış var. Altıncı ve yedinci birbirlerinin aynı.. Bir şeyi kopyalamanın çok önemli bir iş olmadığını düşünebilirsiniz ama benim gibi dalgın bir profesör olursanız ne kadar kolay olduğunu görürsünüz; tamam. Şimdi ümit edelim her şeyi doğru yazmış olayım.

Devam ediyoruz. Bu yeterli değildi tabii, yedi şeyimiz var ama açıkçası bunları dört şeye indirgememiz lazım; yani C nin elemanlarına.. İşte buradalar. C nin elemanları olan (r, s, t, u). Sonuçta r=+ – + çıkar.Tabii, yani bunu görememiş miydiniz? Bu seferki gerçekten çok kolay; s=+ ; t=+ , yani bu şekilde seçilmişlerdi. Bundan sonraki u biraz karmaşık: +- –; tamam mı? Tamam, şimdi bunlardan hangisini kontrol etmemi istersiniz, o kadar kibar olmayın. s’ye ne dersiniz? Ben size s’ nin doğru olduğunu gösterebilirim. Başka tercihiniz var mı? u.. Ooo, hayır işaret hataları, tamam şimdi doğru oldu. Ama bunun işlediğinden emin olmak için dördünü birden kontrol etmelisiniz. Ve ben bunu notlarımda yaptım u=; = (ae+ah+de+dh) dir. Beni kontrol etmelisiniz, eğer hata yaparsam gerçekten bu utanç verici olacak.

(af-ah) = ;

ün önünde bir eksi işareti var, ve bunun değeri (ce+de);

ve bundan sonra eksi ye gidiliyor ki bu büyük bir birleşim (ae+af-ce-cf); tamam. Şimdi filmdeki gibi benim de bazı şeyleri silen bir asistana ihtiyacım var. ah, de, af, ce, ae teşekkür ederim; ve umuyorum ki dh-- ve --eksi eksi (fiuh) cf kalacaktır. Ve eğer şanslı isek bulduğumuz, şurada yazılanın aynı, sadece sıralaması ters olan bir halidir. Sihirli gibi değil mi; acaba Strassen bunu nasıl buldu? Buna karşın dikkat etmelisiniz, toplamada artının ters sırada olması kabul edilebilir çünkü toplama işlemi sıra bağımsızdır. Ama çarpım işleminde ters sırada olması durumunda matrisler sıra bağımsız olamaz. Şimdi cf’ yi kontrol edeyim, bu tamam, dh’ yi edeyim, bunlar da doğru sırada; (fiuh) öteki üçünü kontrol etmeyeceğim. Bu matris çarpımı umuyoruz ki subcubic time yani küp-altı zamanda çalışacak; şimdi yinelemesini yazalım. T(n) bu durumda 7 oluyor; aslında algoritmasını da spor olsun diye yazmak istiyorum. Neden olmasın? Zamanımın olduğunu varsayıyorum, çok zamanım var; en son dersimde dersimi on dakika az yaptım yani on dakika erken bitirdim, bunun için sizden özür diliyorum, bunun sizi çok üzdüğünü de biliyorum. Aslında o gün dersin ne zaman bitmesi gerektiğini bilmiyordum, onun için bugün on dakika daha uzatacağım dersi, tamam mı? Hepinizin bunu kabul ettiğini görmekten mutluyum. Şaka yapıyorum. Üzülmeyin.

Algoritma, bu Strassen’dir; önce böleriz, sonra fethederiz ve birleştiririz. Her zaman olduğu gibi buralarda hiçbir yere bunu yazmamışım, iyi. A yı ve B ye bölelim, bu kolay bir işlem; ondan sonra bu değişik terimleri sonuçlar için hesaplayalım, yani sonuçta bütün P’ leri hesaplamaya hazırlanıyoruz. (a+b) yi, (c+d) yi (g-e) yi (a+d) yi (e+h) yi ve diğerlerini hesaplayacağız. Burada gördüğünüz her terimi hesaplayacağız. Bu da bizim zamanımızı alacak, çünkü bunlar sadece bir grup toplama ve çıkarma. Büyük iş değil, bunlar sabit sayıda.. Ondan sonra da bütün ‘leri özyinelemeli olarak hesaplayarak duruma hakim olacağız. Bunlardan elimizde yedi tane var, den başlıyor den ye kadar devam ediyor. Son olarak da bunları birleştireceğiz, yani küçük (r,s,t ve u) yu hesaplayacağız. Aslında bunlar da toplama ve çıkarma işlemleri onun için zaman alacak. Böylece sonunda, bölme ve birleştirme işlemleri açısından önemli bir algoritma elde ediyoruz . Özyineleme her zaman özyinelemedir, ama şimdi ilginç adımları var, birinci ve üçüncü adımlar. T(n) özyinelemesi 7 tane özyinelemeli alt probleme dönüştü ve bunların her birinin boyutu n/2; ve toplama işlemleri açısından bir de ek olarak Θ ( ) var. Şimdi yinelemeyi çözmemiz gerek; yı hesaplamamız gerekiyor ve burada bu ve biz biliyoruz ki sekizin iki bazlı logaritması üçtür, yine biliyoruz ki yedinin iki bazlı logaritması üçten biraz az ama ikiden çok olacak; çünkü iki, 4’ün iki bazındaki logaritması. Böylece bu polinomsal olarak büyük, ama yine polinomsal olarak den küçük olacak. Şu anda gene birinci şıktayız; şimdi yedinin iki bazlı logaritmasını şeklinde yazarak biraz hileli ifade kullandım. lg iki bazında logaritma demektir. Bunu bilmeniz gerekiyor; kitabın her yerinde bu yazılı ve bizim problem setlerimizde de var. Onun için neden yazmayalım; özellikle de burada elimin altında bir hesap makinesi varsa.. Bu eski model bir hesap makinesi.. Hayır bu doğru değil, özür dilerim, bu aslında --, evet, 2,81 den kesinlikle daha küçük. Bu iyi bir durum yani polinomsal olarak den daha iyi, ama toplama durumunun ürettiği kadar iyi değil.. Matrislerin çarpımını matrislerin bölümünden daha hızlı yapacağımıza inanıyoruz ama bundan emin değiliz. hızına ulaşamayacağımızı düşünüyoruz ama, kim bilir belki de olabilir. Burada herhangi bir alt sınır yok.. Bu matris çarpımları için en iyi algoritma değildir, sadece değerinden daha iyi bir sonuç verir. Şu ana kadar elde edilen en iyi sonuç da dır; ikiye yaklaşmışız. Bu sayıların biraz garip değerler olduğunu düşünebilirsiniz. Belki de buradaki sabitler exponent ya da üst’te ettiğiniz gelişmelerin önüne geçiyordur.

Sonuçta öyle görünür ki exponent‘i yani üstü geliştirmek önemli bir olgudur. Şunu söylemek istiyorum n değeri büyüdükçe daha büyük üst değerleri sizi çok üzebilir. Bu nedenle ‘ün çok büyük n değerleri için pratik olmadığını söylemiştik; Strassen’in n’nin yeterince büyük n değerleri için matris çarpımlarından daha iyi sonuçlar verdiğini biliyoruz; ortalamada n’nin 32’den büyük değerleri için bunun böyle olduğunu söyleyebiliriz. Diğer sebeplerin yanında üstü küçülttüğü için de daha iyi sonuçlar veriyor ama bu iyi bir değer, bu da oldukça iyi bir değer. Bu çok pratik olmayan bir durum onun için bu algoritmayı kullanmayın; elimde bununla ilgili referanslar yok ve şu anda sadece teoriyi gelişmek için çalışma yapıyoruz. Bundan daha iyi algoritmalar arada bir takım metotlar olabilir ama bu uygun değildir. Bayağı çok zamanım var, sorusu olan var mı? Daha işimiz bitmedi, ama matris çarpımları konusuna geçmeden önce bana soru sormak isteyen var mı?

Tamam, ama bir problemim daha var.. Böl ve fethet genel bir fikirdir; biliyorsunuz bu fikri ülkelere hakim olmak için kullanıyorlar, aynı zamanda matrisleri çarpmak için de kullanıyoruz, yani kim bu ilişkiyi düşünebilirdi? Şimdi burada böl ve fethet yöntemi ile uygulayabileceğimiz bir problem daha var; bu aslında algoritmik bir problem değil ama bilgisayar bilimi ile ilgili, bu kesin. Bu Very Large Scale Integration (VLSI) yada Çok Büyük Çapta Tümleşim. Bilgisayar çipleri yada yongaları bildiğiniz gibi çok büyük çapta tümleşim kullanırlar; bugünlerde bu daha da büyümüştür herhalde., Burada VLSI yerleşiminden kaynaklanan bir problem var; bunun nedenlerine ve detaylarına fazla girmeyeceğiz ama elimizde bir devre olduğunu düşünelim ve bu devrenin de bir ikili ağaç olduğunu kabul edelim. Şimdilik bu devrenin bir kısmını ele alalım ama siz bunu tüm devre kabul edin. Tam bir ikili ağaç böyle görünür, benim verdiğim derslerde bugüne kadar en fazla kullandığım şekil bu; benim favori şeklim ve bu dört seviyeli bir ikili ağacı gösteriyor. Tamam işte bu yükseklikte böyle bir ağaç var; şimdi bunu bir yonga ızgarasının içinde bir yere gömmek istiyorum. Diyelim ki bunun n sayıda yaprağı var ve ben bu ızgara içindeki en az alana bunu gömmek istiyorum. Bu güzel bir problemdir ve sizin böl ve fethet tekniğini bir araç olarak nasıl güçlü bir şekilde kullanabileceğinizi gösterir. Evet, elimde böyle bir ağaç var bunu şöyle çizmeyi tercih ediyorum ve bunu o ızgaranın üstüne çizmeyi istiyorum. Bunun sonuçta işe yaraması için bu tepe noktalarını yani vertex’lerini ızgaranın üzerindeki noktalara gömmem lazım ve kare bir ızgaradan bahsediyorum. Evet bu tepe noktaları temelde ızgaranın üzerindeki noktalara gelmek zorunda ve bu şeklin kenarları da ortagonal yani dikken hatlar olarak noktaları birbiriyle birleştirmeli, böyle yollar üretmeli fakat bir kenar diğerinin üzerine gelmemeli yada onu kesmemeli; çünkü kabloların birbirlerini kesmemesi gerekir. Bu problemi çözmenin bir görünen yolu vardır, bir de doğru yolu vardır; şimdi ben size ikisinden de bahsedeceğim. Her iki yöntem de ilk bakışta görülemeyebilir ama böl ve fethet yöntemi size doğru yönde bir işaret verecektir. Evet naive gömme yöntemi; bu ben burada naif yada “içime doğanı” kullanmaktan hoşlanıyorum. Ben bu çizimi aşağıdan yukarı doğru yapacağım çünkü böylesi daha kolay; bunun için üç ızgara çizgisini boş bırakın, ondan sonra çizmeye başlayın. Sonuçta bunun hangi büyüklükte olacağını bilmiyorum. Burası bizim ağacımızın tabanı, burası üç kesişme noktası ya da düğümü diye düşünün, sonra bir boş sütun bırakın, ondan sonra bir boş sütun daha bırakın; aslında bu boş sütunları bırakmaya ihtiyacımım yok, ama bunlar şekli daha güzel gösteriyor. Ondan sonra da yukarıya doğru çizimimize devam edeceğiz.

İşte ağaç, ızgaranın üzerinde hizalandığında, burada bir çizgi gerekli, kenarları birbirini kesmiyor. Bu ne kadar alan işgal eder? Alan derken sınırlayıcı kutunun içindeki alanı kastediyorum ve burada kullanmayacak olmama rağmen bu boş alanı da hesap ediyorum. Yüksekliğe bakmak istiyorum; yüksekliğe H(n) diyelim. Sonra genişliğe bakalım ve buna da W(n) diyelim. Açıkça görülüyor ki H(n), log n’ye benziyor, W(n) de n veya onun iki katı gibi görünüyor; ama ben bunu bir özyineleme olarak yazmak istiyorum; çünkü bu işlemin sonunda doğru şeyi yapmamız konusunda bize ilham verecek. H(n), yani bunu yaparken bir anlamda bunun bir özyineleme ağacı olduğunu düşünmelisiniz. Büyük ağaçla başlıyoruz, bunu ikiye bölüyoruz ve her birinin boyutu n/2 oranında olacak, çünkü sonra da yaprakları sayacağız. Her iki tarafta da tam n/2 boyutunda; yükseklik konusunda fazla bir sorunumuz yok çünkü bunlar birbirine koşut. Yükseklik aslında bir alt problemin boyu artı 1 değerinde. Genişlik için iki genişliği toplamamız gerekiyor ve buna 1 ekleyeceksiniz. Burada 1 eklemeniz gerekmiyor ama en kötü şartta en fazla 1 eklersiniz. Bu durumda H(n) = H(n/2) + Teta (1); buna bir ilave etmeniz gerekir. W(n) = 2W(n/2) + O(1). Bunlar bildiğiniz taban durumları; söylemek istediğim şey bunların bizim bilmemiz ve sevmemiz gereken özyinelemeler olduğu.. Bunun değeri log n; aslında size tüm cevapları verdim. Ancak bunun lineer yani doğrusal olması da gerekiyor. Tekrar ediyorum bu birinci durum; n’in iki tabanlı logaritmada ikinci kuvveti yine n’dir; bu durumda cevap buradaki birden çok daha büyük olur. Burada da n’in birin iki bazlı logaritmada birinci kuvveti, n’in sıfırıncı kuvvetine, yani 1’ e eşittir. Böylece aynı çıkar ve biz log n değerini elde ederiz. Bu durumda alan nlog n olur ama, yonga imalatçıları o alana daha çok kullanılacak işlemci yerleştirmek için boş alanın daha da küçük olmasını isterler., Bu nedenle bu alanı daha da küçültmek bizim amacımız. Ama alan n’den daha küçük bir değere küçülecek gibi görünmüyor. Yaprakları bir yerlere yerleştirmek gerekiyor ama şimdiden bu oldukça iyi; aslında elde ettiğimiz şey sonuçta bir log faktörü kadar kaymış durumda ama bizim hedefimiz n’ yi elde etmek. n’yi nasıl elde ederiz? n’ yi elde etmek için bu yerleşimde neyin değişmesi konusunda tahminler var mı? İlk bakışta bu pek görünmeyebilir ama yükseklik ve genişlik ile ilgili ne yapmalıyız? Söylemem gerekir ki yüksekliği log n’ den daha küçük hale getirmek çok zor; çünkü bu bir ağaç ve genişliği de log n’ den daha küçük hale getirmek de pek mümkün değil. Bu durumda sonucun doğrusal olması için ne yapılabilir? Rastgele fikirlerinizi öğrenmek istiyorum. Bu çıkışın yada sonucun n olması için hangi fonksiyonların kullanılması gerekir? ve ; bu iyi bir çözüm. Başka fikri olan var mı? n çarpı sabit; evet n çarpı bir sabit de uygun olabilir. Ama ben diyorum ki ikisini de bir sabitden daha küçük hale getiremeyeceksiniz. ye log n ‘i hedefleyebilirsiniz, uygun görünebilir ama bunun da imkansız olduğunu düşünüyorum. ve doğru cevap gibi görünüyor, o nedenle bunun üzerinde çalışalım. Evet, ve . Bu ana kadar çözümüne ulaşan özyinelemelerle uğraşmadık ama bunlar yok değil. Diyelim ki hedefimiz W(n) = Teta ( ) olması ve H(n) =Teta( ) olması. Bunu yapabilirsek mutlu olacağız, çünkü bu durumda alan doğrusal bir sonuç olarak karşımıza çıkacak. Peki nasıl? Hangi özyineleme bildiğimiz ana metod formülünü kullandığımız zaman sonucunu olarak verir? Söylemek istediğim böyle bir düşünceyi geliştirebilirsiniz; özyinelemeler biraz şaşırtıcıdır ama şunu düşünelim: . Ne zaman yarım olur? Çünkü bu durumda , olur. Böyle bir durumda da benim bu özyinelemeye çözümünü oluşturmam için bir umut belirir. Bu sistemde böl ve fethet tasarımı uyguluyoruz, onun için böyle bir şey olması lazım. Aslında yönteme karar verdiğiniz zaman gerisi kolay, seçim sonrası yöntemle denemeler yapabilirsiniz. Ne zaman yarıma eşit olur? Bir sürü çözüm var, haydi haykırın. 4 ve 2; bu iyi. Bunu daha iyi anlamaya çalışalım: = yarımdır, çünkü = 2 eder. Şimdilik bunu hedefleyelim, neden olmasın? Ne zaman elde ederiz? Bu b, bu da a; bu nedenle T(n) = 2T (n/4) artı bir şeyler olması lazım. Ve ben ‘deki n’lerin hakim olmasını istiyorsam, bunun ‘den polinomsal olarak daha küçük olması gerekiyor. Bu nedenle bunun da n’nin (1/2- ) kuvveti düzeyinde bir değere eşit olması lazım ama daha küçük olabilir; örneğin bir olabilir. Sıfır daha da iyi ama bunu umut etmek biraz zor gibi görünüyor. Bu nedenle karakök n‘den polinomsal olarak daha küçük bir değer arıyoruz; hedefimiz bu, ve şimdi sihir başlıyor. Eğer bununla bir süre uğraşırsanız bir evrede bu sihiri keşfedersiniz. n boyutundaki bu problemi n/4 boyutunda iki alt problemle çözmek durumunda olduğunuzu hissederseniz ne yapabilirsiniz? Bu durumda artık bu değerlerin kareleri boyutunda düşünmek doğal olur.

Buna H yerleşimi deniliyor. Buna neden böyle dendiği anlaşılabilir. Çünkü böyle olursa daha iyi bir ızgara çizimi, daha iyi bir grafik çizimi yapabilirim. Bu özyinelemeli bir yerleşimdir. Bunların birkaçını çizeceğim ama sizin genelini hayal edebileceğinizi düşünüyorum. Dört tane büyük H alacağım ve bunun iyi bir plan olduğunu düşünüyorum, çünkü n/4 boyutunda problemlerle ilgileneceğim. Bunun n/4 yaprağı var, bunun da n/4 yaprağı var, bu ortadaki kök aslında, burada da n/4 yaprak var, bunun da n/4 yaprağı var; böylece elimde boyutu n/4 olan dört tane problemim var. Öte yandan bunları bir şekilde iki boyutuna düşürmem lazım. Çok şükür ki genişliğe de baksam, yüksekliğe de baksam bunların içinden sadece ikisinin önemli olduğunu görüyorum. Yükseklikte bu ikisi önemli ve bu ikisini de yan ürün olarak elde edebiliriz. Bunlar da birbirlerine paralel yada koşut gidiyor; biraz önce burada baktığımız yükseklikte olduğu gibi; ama ben bunu hem yükseklikte, hem genişlikte elde ediyorum. Bunları ölçtüğümde eşit olduklarını görüyorum onun için bunlara L diyeceğim. Bu şekilde elimizde L(n) boyutları kalıyor. Ve eğer hesaplarsam L(n) nedir? Burada elimde L(n/4) var; çünkü yaprakların sadece dörtte biri bunun içinde, veya şunun içinde.. Sonra Teta (1) gibi bir sabitim var ama çok önemli bir şey değil. Sonra da L(n/4) tekrar var. Böylece aradığım yinelemeyi elde ettim..

L(n) = 2L(n/4)+ Θ(1) ; ve bunun da çözümü daha önceden bulduğumuz gibi . Şu anda ana metodun birinci durumundayız. Hoş değil mi? Bu öncekinden çok daha küçük bir yerleşim yada çizim. Charles bu yerleşimi sen mi icat ettin? Hayır. Ama ben biliyorum ki bu senin doktora tezinde vardı ve sen bunu bir takım yönlere doğru geliştirdin. Bu aslında ağaçların ızgaralara yerleşmesinde klasik sayılabilecek bir yaklaşım ve böl ve fethet yönteminin başka bir uygulaması. Söylemek istediğim, bu örnek algoritmalar için özel olarak geliştirilmiş bir yöntem değil, ama VLSI yada çok büyük çapta tümleşim ile direk ilgili. Aynı zamanda sizin düşünce yönteminize de artı bir tat veriyor. Eğer siz nasıl bir koşma süresini hedeflediğinizi biliyorsanız, testlerde yada problem setlerinde yaptığınız gibi, “elde etmem gereken koşma süresi budur” diye öngördüğünüzde, sizi buraya getiren yinelemeyi unutmayın. Bu size ilham verecektir.

Şimdilik bu kadar. Gelecek derste görüşmek üzere.