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.