MIT Açık Ders malzemeleri

http://ocw.mit.edu

6.046J Algoritmalara Giriş, Güz 2005

Bu materyallerden alıntı yapmak veya kullanım şartları hakkında bilgi almak için:

Erik Demaine ve Charles Leiserson, 6.046J Introduction to Algorithms, Fall 2005. (Massachusetts Institute of Technology: MIT OpenCourseWare). http://ocw.mit.edu (Giriş Tarihi: 08, 01, 2010). Lisans: Creative Commons Attribution-Noncommercial-Share Alike.

Not: Lütfen atıf taparken bilgilere eriştiğiniz gerçek tarihi kullanınız.

Atıflar ve Kullanım Koşulları konusunda daha fazla bilgi için:

http://ocw.mit.edu/terms ve http://www.acikders.org.tr sitesini ziyaret ediniz.

DERS 16

Bugün, açgözlü algoritmalar, “greedy algorithms” olarak adlandırılan özel bir grup algoritma ile ilgili konuşacağız. Ancak bunu grafikler kullanarak yapacağız. Bu nedenle, kitabınızın EK B’sinde bulabileceğiniz grafiklerle ilgili bölümü kısaca hatırlatmak istiyorum. Eğer EK B’yi henüz gözden geçirmediyseniz, şimdi tam zamanı. Ayrıca evde çözeceğiniz sınavınız için de bu oldukça önemli. Size, Digraf’ı hatırlatmak amacıyla, pekiyi, Digraf nedir? Neyin kısaltmasıdır? Directed Graph yani Yöneltilmiş Grafiğin kısaltmasıdır; G eşittir (V,E). V köşeler kümesi, --- E de kenar kümesi. İngilizcede “Vertex” tekil “Vertices” onun çoğulu. İngilizcenin bir acayipliği. Belki de Fransızcadan gelme.

E kümesi, V çarpı V’lerin alt kümesi, yani kenarlardan oluşur. Bu bir digraftır. Yönlendirilmemiş grafik ise, sırasız bütün kenar çiftlerini barındıran bir E kümesine sahiptir.

Pekiyi, yönlendirilmiş veya yönlendirilmemiş grafiklerde, kenar sayısının büyük- O’su nedir? O( ), güzel. Grafiklerle uğraştığımız müddetçe, kümelerle oldukça haşır neşir olacağız. Genel olarak, büyük O’ların içinde düşey çizgi simgelemini kullanmayız, çünkü bu zaten anlaşılır. Kullanmak işi sadece karmaşıklaştırır. Aslında bu biraz üstünkörü bir simgelem; olması gereken “V karenin boyutunun düzeyi “ şeklinde bir anlatımdır. Ama bu yazılacakları oldukça karmaşıklaştırır; bütün bunları çarpıyoruz ve bütün bu dikey barlar bu bağlamda anlatımı zorlaştırır. Bu asimptotik bir simgelem olduğu sürece dikey barları kullanmayacağız.

E kümesi, seviyesindedir, çünkü bu ikililerden oluşan bir kümedir ve eğer böyleyse n elemanlı bir küme en fazla n’in 2li kombinasyonu boyutunu alacağından, bu da en fazla olabilir. Burada G‘nin bağlantılı (connected) olması başka bir özellik olarak karşımıza çıkıyor; bu E kümesinin V’nin büyüklüğü eksi -1 ‘den büyük olduğunu işaret ediyor. Pekiyi, bir grafiğin yani G’nin bağlantılı olması ne anlama gelir?

Bunun anlamı, bir köşeden, başka bir köşeye bir yol var demektir. Bu G’nin bağlantılı olduğunu ifade eder. Durum bu ise, kenar sayımız en az köşe sayımız eksi birdir. Bu durumda, size bir şeyi hatırlatmak isterim, eğer log E’ye bakarsam, yani kenarlar sayısının log’una bakarsam, buna göre büyük-O (log V)’dir.

Buna göre de, Omega (log V)’dir. Bu da teta (logV)’ye eşittir. Dolayısıyla, temel olarak, bağlantılı grafikte, kenar sayısı köşe sayısıyla polinomsal olarak bağlantılıdır; böylece, log’ları da kıyaslanabilir. Bu bize ileride çok yardımcı olacak. Çünkü bazı durumlarda logE’yi bulduğumuzda, birileri “ama logV’yi bulmadınız” diyebilir. Böyle bir durumda bu bağlantıyı hatırlatacağım.

Bilgisayarlarda grafikleri ifade etmenin birçok yolu var; ben de bunlardan önemli olan bir kaçını anlatacağım. Aslında daha fazlası var. Ama biz birkaç tanesini göreceğiz.

En basiti adjacency matrix yani komşuluk matrisi olarak adlandırılandır. Burada G eşit (V,E) gibi bir grafiğin A komşuluk matrisi, V’yi 1’den n’e kadar tamsayılardan oluşan bir küme olarak seçersem, n çarpı n büyüklüğünde olur ve bu A matrisinin ij’inci elemanının değeri, eğer ij kenarlar kümemizde varsa 1, yoksa 0 olacaktır. Basitçe, bu matriste ij girdisi varsa 1 yazarsınız ve bu size i ile j arasında bir kenar olup olmadığının öndayanağını verir.,

Predicate yani ön-dayanak, eğer hatırlarsanız ya 0 ya da 1 olan bir Boolean formülüydü. Bu durumda i’den j’ye bir kenar varsa 1, aksi halde 0’ı kullanıyoruz. Bazen kenar ağırlıklı grafiklerimiz olur, O zaman insanlar bunları kenar ağırlıkları olarak kullanırlar; bu i’den j’ye giden kenarın ağırlığı olacak. Şimdi bir örnek çözelim ve sezgilerimizin matematiksel tanımlarla örtüştüğünden emin olalım.

İşte bizim örnek grafiğimiz.

Şimdi bu grafiğin komşuluk matrisini çizelim. Bu, 1’den 1’e bir kenar olduğunu söylüyor mu? Cevap hayır. 1’den 2’ye bir kenar var mı? Evet, 1’den 3’e? Evet. 1’den 4’e? Yok, 2’den 1’e, yok, 2’den 2’ye, hayır, 2’den 3’e, evet var, 2’den 4’e? Hayır. 3’ten hiçbirine giden bir kenar yok, 4’ten 3’e bir kenar var. Bu kadar. Bu komşuluk matrisi, bu grafiğin matrisidir. Demek ki, bir grafiği bu komşuluk matrisiyle ifade edebiliyorum.

Grafiği bu şekilde ifade ettiğim zaman ne kadar depolama yerine ihtiyaç vardır? Teta , çünkü ikisinin de depolanması için gerekli büyüklük aynıdır. ’nin depolanmasını biz dense representation yani yoğun gösterim denilen bir şekilde ifade ederiz. Grafik yoğun olduğu zaman bu iyi çalışır. Grafiğin yoğun olması, varolan kenarların sayısının, bütün olası kenarların sayısına yakın olması anlamına gelir. Bu durumda bu iyi bir gösterimdir. Ancak, birçok grafik için var olan kenar sayısı olası kenar sayısından azdır, bu durumda grafik daha seyrektir. Sparse yani seyrek grafiklere örnek vermek isteyen biri var mı? Bir grafik sınıfı soruyorum, öyle ki, grafikteki kenar sayısı olan n artsın, ama kenarların sayısı karesi oranında artmasın, çok daha az oranda artsın. Bir bağlantılı liste, bir zincir; buna teorik grafik açısından bakarsanız, bu mükemmel bir örnek, n uzunluğundaki bir zincir için sadece n tane kenar. Bu durumda, kenarların sayısı V düzeyinde olacaktır. Her bir sıra için sadece bir kenarımız var. Başka hangi grafikler seyrektir? Düzlemsel yani planar grafik. V tane köşesi olan ve V’nin en az 3, E’nin en fazla 3V - 6 olduğu, bir düzlem üzerine çizilebilen grafikler.

Sonuç olarak V düzeyinde kenar sayısına sahip olmuş oluruz. Ortak grafiklere başka örnek ne var? Evet, ikili ağaçlar, aslında her türlü ağaç; eğer eki okursanız, buna serbest ağaç denir. Bir ağaç, bağlantılı grafiktir, tabii içinde hiç döngü olmamak şartıyla.

Yoğun grafiklere örneğiniz var mı? Tam grafik, Evet, bunların hepsi 1 olur; eğer kenar ağırlığınız varsa, matrisiniz tamamen 1’lerle dolu olur. Sonuç olarak, bu, yoğun gösterimler için iyi bir seçimdir. Ancak bazen daha seyrek gösterimler yapmak isteyebilirsiniz, bunun için de kadar yer ayırmak istemeyebilirsiniz. Sonuçta matrisinizin büyük kısmı 0’lardan oluşacaktır. Eğer bunun 0 olduğunu biliyorsak, neden onu 0 olarak göstermeye çalışalım?

Bu amaçla, adjacency list gösterimi yani komşuluk listesi gösterimi kullanılır. Aslında verilen bir köşenin komşuluk listesi, komşusu olan köşeleri V’nin Adj’si yani komşuluğu olarak gösterilmesidir. Terminoloji açısından köşeler V’ye komşuluk eder ama kenarlar köşelere denk gelir. Bu durum, bir köşe ile kenar arasındaki ilişkidir. Komşuluk ise iki köşe arasındaki ilişkidir. Bu sadece dil; bu amaçla niye iki terim kullanıyorlar bilmiyorum ama yapılan budur.

Grafiğimizde, birinci köşenin komşuluk listesi 2 ve 3’ten oluşan kümedir, çünkü 1’den sadece 2 ve 3’e kenarlar gitmekte.. 2’nin komşuluk listesi 3ve 4’tür. 3’ünkü boş kümedir. 4 için ise 3’tür. Bu bizim gösterimimiz. Bu gösterim için ne kadar depolama yerine ihtiyacımız olduğunu bulmak için, komşuluk listesinin uzunluğunu anlamamız gerekir.

Bir V köşesinin komşuluk listesinin uzunluğu nedir? Buna ne isim veririz? Bu derecedir. Yönlendirilmemiş bir grafikte buna köşenin derecesi deriz. Bu yönlendirilmemiş durum. Digraf, yani yönlendirilmiş grafikte ise, bunu şöyle yazmakta yarar var, dereceye dış derece denir. Yani yönlendirilmiş grafikte, her köşemiz için bizim bir dış derecemiz, bir de iç derecemiz olur.

Burada iç derecemiz 3; burada dış derecemiz 2, tamam mı? Burada önemli bir önkuramımız var; “handshaking lemma” yani “tokalaşma önkuramı”. Bu matematikteki önemli önkuramlardan biridir. Bu bir hikayeden geliyor. Bir partiye gidilir, bu partideki herkes birbiriyle tokalaşır. Bazıları kimseyle tokalaşmaz. Birileri bazılarıyla tokalaşır. Kimse kendi elini sıkmaz. Parti sürerken, ev sahibi herkesin kaç kişiyle tokalaştığını saymaya başlar. Kaç kişinin elini sıktınız diye konuklarına sorar. Cevapları toplar, cevabın çift sayı olması garantidir. Bu tokalaşma önkuramıdır. Eğer bunu bizim grafiklerimize uygular ve köşelerin derecelerini toplarsak, bu herkesin tokalaşma sayısıdır, bu her zaman kenarların sayısının iki katıdır. Pekiyi, neden bu doğru, neden kenar sayısının 2 katı çıkar? Evet?

Evet. Ne zaman bir kenar eklerseniz, her iki uçtaki kişilere birer derece eklemiş olursunuz. Yani kenarları saymanın iki farklı yolu vardır. Benim grafikte dolaşıp her köşenin derecesini sayarken kenarlara da bir işaret koyduğumu hayal ederseniz, işim bittiğinde her kenarda iki işaret olacaktır. Tamam değil mi? Bu oldukça basit bir teoremdir. Bunun anlamı, yönlendirilmemiş grafikler durumunda elde edilen komşuluk listesi gösterimi için – ne kadar depolama alanı gereklidir?

En fazla 2E. Bu E düzeyindedir, ama hepsi bu değil. Evet, köşelerimizin sayısı artı kenar sayısının düzeyini bilmeniz gerekir. Yönlendirilmiş veya yönlendirilmemiş farketmez, çünkü sadece köşelerden oluşan ve hiç kenarı olmayan bir grafik bile bana V seviyesinde maliyete neden olacaktır. Demek ki, bu, teta (V artı E) kadar depolama yeri kullanacaktır. Asimptotik olarak bu aynı şeydir. Aslında bunu görmek digraflarda daha kolaydır, çünkü digraflarda, dış dereceleri ekliyorum ve bu E’ye eşit. Aslında bu yeniden düzenleme gibi amortize edilmiş bir çözümleme ile yapılacak olursa, bütün kenarların sayısını toplamanın bir yolu da, hesaplama işini köşe bazında yapmaktır. Her köşenin derecesini alırım bunu kenar bazında hesaplar ve kenar sayılarını 2’ye katlayıp toplarım; bu muhasebe tekniğinde kullanılan çözümlemede uygulanan amortize edilmiş bir çözümlemenin aynısıdır. Bunu göreceğiz.

Bu bir seyrek gösterimdir ve çoğu zaman komşuluk matrisi gösteriminden daha iyidir. Örnek olarak, internet ağının komşuluk listesi gösterimi yerine bir komşuluk matrisiyle yapıldığını hayal edin. İnternetteki linkleri göz önüne aldığımda, “Ben bunlara bağlıyım, bunlara ise bağlı değilim.” diye belirtmek zorunda olurdum. Herhangi bir sayfada, bağlı olmadığınız linklerin de listesini belirtme zorunluluğu, seyrek gösterimin avantajını gösterir.

Bunun yanısıra, komşuluk matrisi gösterimiyle ilgili güzel şey ise, her bir kenar tek bir bit ile gösterilebilir. Öte yandan komşuluk listesi gösteriminde her bir komşuyu ifade etmek için kaç bite ihtiyacımız olur? Her farklı komşuyu belirtmek için kaç bite ihtiyacımız var ? Her köşeyi isimlendirmek için LogV düzeyinde bite ihtiyaç olur. Bunun çok daha verimli olduğu gösterimler var. Eğer çok yoğun bir grafiğiniz varsa, bu daha iyi bir gösterim olacaktır. Gelecek hafta bu konunun üzerinde daha fazla duracağız; bir matris ve bir grafik aynı şeye bakmanın 2 farklı yoludur. Aslında komşuluk matrislerini çarptığınız birçok grafik teorisi vardır. Yani, grafikler ile matrisler arasında birçok ortak nokta var. Birine uygulayabildiğiniz matematiği, diğerine de çoğu zaman uygulayabilirsiniz.

Bir sorunuz mu var, yoksa parmağınızı öylesine mi havada tutuyorsunuz? Tekrar etmek için bu kadarı yeterli. Bugünün dersine geçmek istiyorum. Grafiklerle ilgili başka sorusu olan var mı? Bu aşama EK B’yi tekrar etmek için iyi bir zamandır. Burada birçok güzel özellik vardır. Bugün ağaçların özelliklerinden birini işleyeceğiz. Ağaçlar çok özel türde grafiklerden biridir, bu nedenle gerçekten bu özelliklerin ne olduğuna bakmanızı istiyorum. Ağaçların hepsi birbirine denk olan 6 farklı tanımı var; bu teoreme bakmak ve okumak oldukça iyi bir fikir olur. Bunu sınıfta kanıtlamayacağız, ama anlamanız ve üzerinde düşünmemiz için iyi bir temel sağlayacaktır. Bundan ileride tekrar söz edeceğiz.

Bugün minimum span trees yani en az kapsayan ağaçlardan bahsedeceğiz.

Bu dünyanın en ünlü algoritmalarından bir tanesidir. Özellikle distributed yani dağıtık sistemlerde oldukça önemlidir. Hemen hemen bütün dağıtık sistemler “en az kapsayan ağaç” modelini bulmaya çalışırlar; her noktada canlı düğümler bulmaya çalışırlar. Bunun için AT&T firması yıllarca tekel olduğu dönemde, fatura sisteminde bunun algoritmasını geliştirdi; bu konunun üzerinde ileride biraz daha duracağız. Bunu uygulayan çok sayıda uygulama var.

Burada problemimiz şudur: Yönlendirilmemiş bağlı bir grafiğimiz, w ağırlık fonksiyonu ile birlikte, G eşittir (V,E) olarak tanımlıyoruz. w kenarlardan gerçek sayılara bir fonksiyondur. Bugünkü derste, basitliği sağlamak amacıyla önemli bir varsayımda bulunacağız; kitabınız bu varsayımı yapmıyor. Kitaptaki bu alternatif gösterime bakmanızı tavsiye ediyorum, çünkü o çok daha genel; ama anlamanız ve basitlik açısından ben problemi birazcık daha kolaylaştırıyorum. Biz bütün kenar ağırlıklarının birbirinden farklı olduğunu varsayacağız.

Bütün ağırlıklar birbirinden bağımsız. Bu ne demek? Eğer bütün kenarlar farklı ağırlığa sahipse bu w fonksiyonu açısından ne anlama gelir? Ayrık matematik derslerini kim hatırlıyor? Bu injective yani bire birdir. Hem bire bir ve hem de onto yani örten olmak zorunda değil. Ancak bire bir olmadıklarında oldukça büyük bir kümeden bahsetmemiz gerekir, bu nedenle bire bir olmaları işimizi kolaylaştıracağından böyle bir varsayımda bulunuyoruz. Kitabınız bu varsayımı yapmıyor; kitapta bir şeyler teknik olarak daha kesin tanımlanıyor.

Böylece bu girdimiz, çıktı ise --

spanning tree yani bir kapsayan ağaç’tır. Bu ağaç T’dir ve kapsayan ağaç derken, bütün köşeler bağlantılı anlamına gelir. Bu en az ağırlığa sahip olmalıdır. Ağacın ağırlığını, bütün bağımsız kenarların ağırlığını toplayarak yazabiliriz. Buradaki simgelemde birazcık yolsuzluk yaptım; aslında (u,v) kenarının w’su şeklinde yazmam gerekirdi çünkü bu kenarların eşlemlenmesinden kaynaklanır ve bana çift parantez getirir. Ama bildiğiniz gibi ben simgelemlerde yolsuzluk yapmayı severim. Dolayısıyla buradaki fazladan parantezleri düşürüyorum, çünkü bunun kenarın ağırlığı olduğunu, sıralı ikilinin ağırlığı olmadığını biliyoruz. Bu simgelemin yazımı bağlamında daha uygun. Özellikle ev sınavlarınızı yaparken, uygun simgelemi kullanmak sizi problemi yazarken kaybedeceğiniz aşırı zamandan kurtaracaktır. Problemleri çözerken hangi simgelemi kullanacağınız üzerinde düşünmek önemlidir. Eğer iyi bir simgelem tercih ederseniz, teknik bir iletişim durumunda genel olarak insanlar sizi daha kolay anlayacaktır. Buna karşılık kötü bir simgelem, insanların sizi anlamamasına neden olabilir.

Bir örnek yapalım. Burada bir grafiğimiz var; ben daha önce birilerinin bana biyokimyadan esinlenip esinlenmediğini sorduğunu hatırlıyorum. Hayır esinlenmedim. Bunları sadece yazıyorum. Burada grafiğimiz; bazı kenar ağırlıkları verelim. Bunlar kenarların ağırlıkları-- ve istediğimiz, öyle bir ağaç bulabilmek ki, bağlantılı ve çevrimsiz olsun ve her köşenin ağacın bir parçası olduğu bir grafik olsun. Aynı zamanda da en az ağırlığa sahip olsun. Biriniz bana “en az kapsayan ağaç” için bazı kenarlar önerebilir mi?

Evet, 9, güzel. 9 burada olmalı, çünkü neden? Çünkü bu kenara tek bağlanan kenar 9. Aynı şekilde 15 de burada olmalı. Bu ikisi de olmalı. Başka hangileri olmalı? 14 olmalı. Neden 14 olmalı? 14 veya 3’ten biri mutlaka olmalı. Ben en az ağırlıklı olanı istiyorum. Toplamda en az ağırlığı olanı istiyorum. 3’ün burada olması gerektiğini benimle tartışmak isteyen var mı?

Evet? Bu ikisinden küçük olanı, yani “en az kapsayan bir ağacın” toplamını alırken 3 hesaba katılmamışsa, ben 14 olan kenarı siler ve yerine 3 olan kenarı koyabilirim. Böylece daha az ağırlığı olan bir şey elde ederim, değil mi? Yani 3 burada olmak zorunda. Burada olması gereken başka hangi kenarlar var? Biraz bulmaca mantığı kullanın. 6 ve 5’in de mi burada olması gerekiyor? Bunlar niye burada olmalı?

Evet ama bu yolla da birbirlerine bağlanabilirler; bu yolu takip etme zorunluluğu yok. 6, 3 ile aynı nedenle burada olmak zorunda, değil mi? Çünkü bu elemanı bağlamak için iki seçimimiz var. Çünkü 12 olmazsa onu yine de bu yoldan bağlayabilirim. Yani 6 kesin olarak bu, burada. Hala herşey bağlı değil. “En az kapsayan ağaç” için başka neye ihtiyacım var? 7,5 ve 8, neden 7, 5 ve 8? Bunu sırasıyla tartışabilir miyiz? 5 neden burada olmalı? Evet, dört bağlı ögemiz var, bu, bu, aslında bu ve bu bağlı, güzel. En az üç kenarın onları bağlaması lazım, çünkü her bir kenar, bağlı ögeleri bir azaltacak. Dolayısıyla 3 kenara ihtiyacımız var, bu üçü en ucuz olanlar. Evet, bu çalışır.

Bu çalışır, değil mi? Diğer kenarlardan birinin seçimi daha büyük olurdu ve bu çalışır, güzel. Pekiyi, şu an kapsayan bir ağaca sahip miyiz? Büyük, “bağlı bir grafiğimiz” var doğru mu? Benim çözümüm de bu mu? Evet bu benimkiyle aynı; tamam hayat tahmin edilebilir.

Herkesin “en az kapsayan ağacın” ne olduğuna dair bir fikri oldu mu? Burada neler olduğu hakkında? Bu bulmaca ile ilgili bazı gözlemler yapalım ve şimdi size “optimal substructure property” yani “en uygun altyapı özelliğini” hatırlatmak istiyorum; çünkü, “en az kapsayan ağaç” çok iyi bir “en uygun altyapı” özelliğine sahiptir.

Kurulumda, bir MST’ye yani “en az kapsayan ağaca” sahip olacağız; buna T diyelim. Grafikteki diğer kenarların gösterilmeyeceğini size göstereceğim. Grafiğimiz burada. İşte bu bir grafik. Benim kağıdımdakine benziyor. Bunun bir “en az kapsayan ağaç” olduğu fikrindeyiz. Şimdi “en uygun altyapı özelliğine” bakacağız. Bunun için, ağacımdaki bir kenarı yok edeceğim, rastgele bir kenarı, örneğin (u,v)’yi sileceğim. Buna u, buna da v diyelim. Bu kenarı kaldırıyoruz.

Ağaçtaki bir kenarı kaldırırsam, ağaca ne olur? Geriye ne kalır? İki ağaca sahip olurum, doğru mu? Geriye iki ağacım kaldı. Size okumanızı tavsiye ettiğim kitap ekinde bunun kanıtı var; böylece her ne kadar bu durum çok açıksa da kanıtlanması da önemlidir. Bunu kaldırdık. T iki alt ağaca bölüntülendi. Bunları ve olarak adlandıracağız. Burada bir alt ağaç var ve burada da diğer alt ağaç. Ağaçta bölüntü yaptık. Hangi kenarı alırsam alayım, 2 alt ağacımız olacaktır. Alt ağaç önemsiz olabilir, mesela içinde sadece bir köşe yani düğüm olabilir ve herhangi bir kenar olmayabilir.

İspatlayacağımız teorem, “en uygun altyapı özelliğinin” sağlandığını gösterecek., grafiği için “en az kapsayan ağaç”, , G’nin bir altgrafiği ve ’in köşeleri tarafından oluşturulmuş. ,’deki köşeler.

Bu resimde bu, bu da. Bu resimde, bunlar ’in köşeleri, yani, tamam mı? , x ve y köşe ikililerinin kümesi -- ve x ile y’nin her ikisi de’deki kenarlar ve aynı zamanda ’e ait olan kenarlar.

G’deki kenarları burada göstermedim. Ama temel olarak, eğer bir kenar buradan buraya gidiyorsa bunlar ’de olmalı; buradan buraya gidiyorsa olmamalı. Ve buradan buraya gidiyorsa, yine olmamalı. ’in köşeleri tarafından oluşturulan alt grafik, sadece ’deki cisimleri bağlar; aynı şey için de geçerlidir.

Teorem, grafiğindeki köşelerin oluşturduğu kenarlara bakıldığında bunun, bu alt grafik için “en az kapsayan ağaç” olduğunu söylüyor. Bu, teoremin ne söylediği. Eğer buraya bakarsam, buradaki köşelerin kümesi tarafından oluşturulan kenarlar açısından da aynı şeyin için de geçerli olması gerekir.

Bunu burada bile yapabiliriz. Eğer örnek olarak bunlara bakarsam, diyelim ki 5’ten kestim. Eğer 5 kenarını çıkarırsam, bu 4 köşeden oluşur. Burada oluşan alt grafiğe baktığımda, bu kenarlar buradadır. Aslında 6, 8 ve 3 buradaki “en az kapsayan” ağacın kenarlarıdır. Evet bu teoremin söylediği; şimdi bunu kanıtlayalım.

Tamam, bunu ispatlamak için hangi tekniği kullanacağız? Bu tekniği daha yeni öğrendik: ipucu, ipucu. Bu, sizin metin düzenleyicinizde kullandığınız bir şey: kes ve yapıştır, güzel, kes ve yapıştır. Tamam, o zaman T’nin ağırlığını, sildiğim kenarın ağırlığı artı,’in ağırlığı artı’nin ağırlığı olarak bulabilirim. Tamam, bu toplam ağırlıktır. Yani, argüman oldukça basittir. için’den daha iyi birüssü olduğunu kabul edelim. Bir kapsayan ağacı oluşturmak için daha iyi bir yolum olduğunu kabul edelim.

Tamam, o zaman sadece (u,v) kenarını ve üssü ile’nin birleşimini içeren bir T üssü bulabilirim. O zaman, daha iyi bir kapsayan ağacım varsa, için daha düşük ağırlıklı bir kapsayan ağaç olanüssünü oluşturabilir ve bunu burada (u,v) kenarımın, ve T ile üssü olarak her ne çalışıyorsa onların yerine koyabilirim. Bu da bir kapsayan ağaç olacak ve G için T’nin kendisinden daha iyi olacaktır; çünkü bunların ağırlığı aynen bunun ağırlığı gibidir. Sadece T üssünün ağırlığını kullanmaya alışmalıyım ve bu daha da azdır. T’nin “en az kapsayan ağaç” olduğu varsayımı eğer alt parçalar için daha iyi bir ağaç bulabilirsem bozulacak.

En uygun alt yapı özelliğimiz oldukça güzeldir. Bütün problemi kapsayan genel geçer en uygun çözümüm varsa, en uyguna uyan bazı alt problemlerim de olur ve ben bunların çözümlerini bulabilirim.

Şimdi soru, bu dinamik programlamada bir kalite olgusu olmakla birlikte, örtüşen altproblemler durumunda ne olur? Aynı özelliğe orada da sahip miyim? Bu tarz problemler için aynı tarz bir çözümden bahsedebilir miyiz? Örneğin, farklı kenarları kaldırdığımı hayal edin. Verilen bir kenara bakıyorum ve onu kaldırıyorum. Bu bütünü 2 parçaya bölüyor ve burada bir parçam daha var. Ve onu da kaldırıyorum. Sonunda

işi bir grup birbirine benzeyen alt problemler bularak mı bitireceğim? Evet, eğer bunu çıkarırsam, bunu buraya çıkarırsam, burada başka bir ağacım, burada da başka bir ağacım olur. Aslında bunu dışarı çıkarsaydım ve daha sonra da bunu dışarı çıkarsaydım aynı şey olacaktı. Eğer bir sıralamaya bakarak kenarları dışarı alsaydım, tam olarak bir grup örtüşme alt problemi ile karşılaşacaktım.

Evet, pekiyi, bu durumda nasıl bir yaklaşım kullanmamız gerekiyor? Dinamik programlama, güzel. Ne büyük sürpriz değil mi? Evet, dinamik programlama kullanabilirsiniz. Ama “en az kapsayan ağaç” daha da güçlü bir özellikle karşımıza çıkar. Dinamik programlama için bütün ipuçlarına sahibiz, ama daha güçlü bir teknik kullanabilmemiz için daha büyük bir ipucu çıkacak gibi gözüküyor.

Buna aç gözlü algoritmaların Hallmark’ı yani kalite damgası diyoruz. Bizim aç gözlü seçim özelliği diye tabir ettiğimiz özellik -- bize yerel olarak en uygun seçimin, genel anlamda da en uygun olduğunu söylüyor. Ve tabii ki, bütün bu damgaları kutulamak istersiniz, çünkü bunlar bu yöntemi kullanmak için gereken ipuçlarına sahipler. Aç gözlü seçim özelliği diye adlandırdığımız bir özelliğe sahibiz. Bu durumda bunun nasıl çalıştığını göstereceğim. Bu özelliği kullanarak dinamik programlamadan bile daha iyi sonuçlar elde edebilirsiniz.

Eğer iki tane dinamik programlama özelliğini görürseniz, bu dinamik programlamayı kullanabileceğinize dair size ipucu verir, ama aynı zamanda, aç gözlülük özelliğinin olup olmadığına da bakmanız gerekir, çünkü eğer bu özelliği bulursanız, dinamik programlamadan daha iyi bir yöntem kullanabileceksiniz demektir. Eğer sadece 2 özellik bulursanız, bu genelde dinamik programlamayı kullanacağınız anlamına gelir, ama eğer bu üçüncüyü de bulursanız, yaşasın, büyük ikramiyeyi kazandınız demektir!

İşte bu fikri göstermek için ispatlayacağımız teorem. Bunların hepsi buluşsaldır. Size nerede dinamik programlamayı, nerede aç gözlü algoritmayı kullanacağınızı söyleyen bir algoritma veremem. Ancak hangi yapıda çalıştıklarını anlatabilirim.

İşte size teorem: T, grafiğimizin MST’si yani en az kapsayan ağacı olsun. A da V’nin yani köşelerin herhangi bir alt kümesi olsun.

Şimdi, (u,v) kenarımızın A kümesini ve A’nın tümleyenini en az ağırlıkta bağlayan kenar olduğunu varsayalım; A’nın tümleyeni V – A’dır. Bu durumda teorem, (u,v)’nin en az kapsayan ağaçta olduğunu söyler. Buradaki grafiğimize bakalım ve durumun gerçekten böyle olup olmadığını görelim. A’yı tek düğümlü seçerek bunu deneyebilirim. Mesela buradaki elemanı alalım, bu benim A kümem olsun ve geriye kalan herşey de V-A.

Bunu, diğer herşeye bağlayan en az ağırlıklı kenara bakıyorum. Bunu diğer her şeye bağlayan sadece 2 kenar var. Teorem hafif olanın en az kapsayan ağaçta olduğunu söylüyor. Kazandım. Ele aldığım her bir köşeye bakacak olursanız, o köşeden çıkan en hafif kenarın bizim en az kapsayan ağacımızda olduğunu göreceksiniz. Ama bu kenarların hepsinin burada olduğu anlamına gelmiyor.

Pekiyi, sadece hayal edin, bu köşeler kümesine bağlı 3 köşeye bakın. Buradan giden 3 kenarım var. En hafifi 5. Bu en az kapsayan ağaçtadır. Veya bunu bu şekilde kesebilirim. Bunlar bunun üzerinde, kenarlardan 7, 8, 14 aşağı gidiyor. 7 en az kapsayan. Nasıl seçersem seçeyim, bu içeri, bu dışarı, bu içeri, bu dışarı, bu içeri, bu dışarı, bu içeri bu dışarı, bütün kenarların ne olduğuna bakalım. En hafif kenar hangisi ise, en az kapsayan ağaca girer. Bu bir anlamda yerel bir özelliktir, Geri kalan ağacın ne olduğuna bakmam gerekmez. Sadece elimdeki küçük köşeler kümesine bakarım ve bunları dünyanın geri kalanına bağlamak için hangi kenarı seçmeliyim ona karar veririm. En ucuz olanı tercih ederim. Bu açgözlü yaklaşımdır ama gördüğümüz kadarıyla kazanır. Bu yerel seçim A alt kümesi için iyi olduğu gibi genelde de geçerlidir. Bu bütün fonksiyonu en uygun hale getirir. Bu teoremin söylediği şeydir. Şimdi teoremi kanıtlayalım. Buraya kadar herhangi bir soru var mı? Haydi teoremi kanıtlayalım.

A’yı V-A’ya bağlayan en az ağırlıklı kenar (u,v) ve bu kenarın (u,v)’nin en az kapsayan ağaçta olmadığını varsayalım. Yani en hafif kenarı içermeyen bir en az kapsayan ağacımız olduğunu varsayalım. Burada teoremi ispat etmek için çelişki yöntemini kullanacağız. Kes ve yapıştır, güzel. Evet, kesip yapıştıracağız. Burada bir örnek çizeyim. Burada simgelem kullanacağım; bunların bir kısmını renklendireceğim. Simgeleme göre bunların bazılarını renklendireyim: A’nın elemanlarını renksiz bırakıyorum ve V-A’nın elemanlarını renklendiriyorum. Yani eğer renkli değilse A’nın elemanıdır.. Bu benim en az kapsayan ağacım. Yine grafikteki bütün kenarları göstermiyorum, ama onlar orada, tamam mı? Benim (u,v) kenarım, ki bu kenar benim en az kapsayan ağacımda yok, bu kenar şu diyelim. u, A’nın içinde, v ise V-A’nın içinde. Kurulumu herkes görüyor mu? Ben bu kenarın en az kapsayan ağacın içinde olması gerektiğini ispatlamak istiyorum.

Burada yapmak istediğim şu; bir T ağacım var, u ve v köşelerim var, ve ağaçtaki her bir köşe arasında sadece bir basit yol mevcut; basit yol, ileri geri gitmeyen, kenar ve köşelerden tekrar geçmeyen yol demek. u’dan v’ye tek ve basit bir yol var. Bu yolun olduğunu düşünelim. Böyle bir yolun olduğunu biliyorum çünkü kitabınızın EK B’sinde Bölüm B.5.1’i okudum; burada ağaçlarla ilgili güzel bir teorem bulunmakta. Burada tek ve basit bir yol olduğunu bu nedenle biliyorum.

Şimdi yapacağımız bu yola göz atmak. Bu durumda, bu yol, buradan buraya, buraya ve buraya gidiyor. Bu yol boyunca, A’daki bir köşenin V-A’daki bir köşeye bağlanacağı bir yer olmalı. Bu A’da olduğundan, ve bu da V-A’da olduğundan yolun bir yerinde bir geçiş olmalı. Bunların hepsi A’da değil; özellikle v, A’da değil.

Yapacağımız, (u,v) kenarını yol üzerinde olan ve A’daki bir köşeyi V-A’daki bir köşeye bağlayan ilk kenar ile değiştirmek. Bu durumda, bu kenar o kenar. A’dan V-A’ya gidiyorum. Genel olarak, birçok zaman alternatif yollarım olabilir, ama ben ilk karşılaştığımı alıyorum; bu elemanı. Bu kenarı içeri koyuyorum. Pekiyi, ne oluyor? (u,v) kenarı A’yı V-A’ya bağlayan en hafif kenar. Yani bu kenardan daha hafif. Bunları değiştirerek, gelmiş geçmiş en hafif ağacı yaratmış olurum, bu da eski ağacın “en az kapsayan ağaç” olduğu varsayımını çürüttü.

Tamam, T’den daha hafif bir kapsayan ağaç bulmamız, bizi çelişkiye sürükledi. Bu bir çelişki. Nasıl gidiyoruz? Herkes benimle mi? Şimdi biraz algoritma yapalım.

Prim’in algoritması diye adlandırılan bir algoritmayı çalışacağız. Prim, en az kapsayan ağaçlarla ilgili bu algoritmayı bulmasından ötürü AT&T’de oldukça yükseldi. Bulduğu algoritma da şirketteki faturalandırma kodlarında uzun yıllar kullanıldı. Prim, aynı zamanda, Bell Laboratuvarların en enerjik yıllarında orada da epey yükselmişti. Bu, sizin tek yapmanız gerekenin bir algoritma keşfetmek olduğunu anlatıyor. Böyle bir durumda, bir tekelin başkanı olabilirsiniz. Tabii, devlet tekellere karşı birşeyler yapabilir, ama eğer bu sizin hayattaki amacınız ise, bir algoritma keşfedin.

Fikir şu. V-A’yı öncelikli Queue yani öncelikli kuyruk olarak yapılandıracağız. Buna Q diyeceğiz. Q’daki her köşeyi, A’daki bir köşeye bağlayan en az ağırlıklı kenar ile anahtarlayacağız.

İşte size kod. Q’nun bütün köşeleri kapsadığı durum ile başlıyoruz. Bu durumda A boş bir küme. Q’daki her en az ağırlıklı kenar sonsuz olarak anahtarlanıyor; çünkü onları boş küme olan A’ya bağlayan bir kenar yok. Şimdi tek elemanla başlıyoruz.

Buna S diyoruz ve buna 0 atıyoruz; S, V’nin içindeki rastgele bir eleman.. Bu bizim başlangıcımız ve sonra ana algoritma devreye girecek. Çözümlemeyi yaparken tahtanın sol tarafına bazı şeyler yazacağım. Siz de not alıyorsanız, belki boşluk bırakmak isteyebilirsiniz. Artık Q boş olmadığı sürece, en küçük elemanı dışına alıyoruz. Yani çekiyoruz. Sonra bazı işler yapıyoruz. Evet, işte bu.

Burada dikkat çekmem gereken bir konu var, burada neler oluyor ona bakalım; sonra örnekte bunu deneyeceğiz. Her bir basamakta en küçük elemanı kuyruğun dışına çıkartıyoruz. Sonra da komşuluk listesindeki her adımda, yani v’den u’ya giden bir kenarın olduğu her durumda, v’nin hala V-A kümemizin içinde kalıp kalmadığına bakıyoruz; çünkü dışarıya çıkardığımız şeyler artık A’nın bileşenleri olacaktır. Tamam mı? Ne zaman dışarıya bir şey çıkarırsak, bu yapılandıracağımız yeni bir A olacak..

Her adımda, A’yı diğerlerine bağlayan en ucuz kenar hangisi bulmaya çalışıyoruz. Aslında temel olarak yaptığımız, en ucuz kenarı bulup, onu A’ya taşımak ve daha sonraki en ucuzu bulmaya çalışmak. Bu işlemi yapmaya hep devam ederiz. Şimdi örnekte yapacağız. Ve bu işlemi her yaptığımızda hangi köşenin beni içeri taşımaktan sorumlu olduğunun kaydını tutarız.

Benim iddia ettiğim, sonuçta, burada yarattığım ikililer kümesine, yani V ve V’nin Pi’sine baktığımda, bunlar “en az kapsayan ağacı” oluşturacaktır. Şimdi bunu yapalım. Bu neydi? Eski kurulum. Buradaki elemanlardan kurtulalım, çünkü bunları baştan tekrar hesaplayacağız. Siz grafiği tekrar notlarınıza almak isteyebilirsiniz. Bunu birazcık düzelteyim, evet başlıyoruz. Herşeyi sonsuz yapıyorum. Burası anahtar değerini tutacağım yer. Bundan sonra yapacağım şey bir köşe bulmak. Bunu seçiyorum ve S olarak adlandırıyorum. Bu köşeyi seçiyorum ve bunu 0 yapıyorum. Şimdi, en küçük değeri çıkışa vereceğim. Aslında yapacağım bu elemanı gölgelemek, böylece elemanın A’ya katıldığını göstermiş oluyorum. Şimdi A’nın simgelemi bu şekilde olacak; bu A’nın -- bu da V-A’nın elemanı. Yapacağımız bir gözatmak. Bu elemanı dışarı çıkardığımızda komşuluk listesindeki her bir kenar ve yine komşuluk listesindeki her bir köşe, yani bu elemanların hala Q’da yani V-A’da olup olmadığına bakıyoruz. Ve eğer öyleyse ve anahtar değeri kenar ağırlığından küçük ise, bu değeri kenar değeri ile değiştiriyoruz. Bu durumda burayı 7 ile değiştiriyoruz. Bunu 15’le, bunu 10’la değiştiriyoruz; çünkü bizim ilgilendiğimiz en ucuzu. Dikkat edin, V-A’daki yani öncelikli kuyruğumdaki her şey, A’ya daha önceden taşıdığım ögelere en ucuz yol değerleri ile bağlı. Bu güncellemeyi yaptığımda bizim öncelikli kuyruğumuzda bir şeyler oluyor; anahtar değeri çok açık olmasa da kesin olarak azalıyor.

Bu nedenle “decrease key” yani "anahtar değerini azaltma” uygulamalıyım. Anahtar azaltma, bir öncelikli kuyruk işlemidir ve bu uygulamada anahtar değerini azaltır. Bu öncelikli kuyruğu oluşturmak için kullanılan veri yapılarında açıkça olmasa da kesin olarak çalışır. Öncelikli kuyruk oluşturmak için kullanılan en yaygın veri yapısı – Heap yani yığındır. Yığında bu işlemi yaptığımdan emin olmalıyım; yığını etkilemeden herhangi bir değişiklik yapamam. Dolayısıyla burada örtülü bir işlem var.

Şimdi tekrarlıyorum. En ucuzu buluyorum, sonra bu elemanlardan u’ya bir işaretçi oluşturuyorum. Bu eleman buraya giden bir işaretçi hazırlıyor. Bu eleman, bu yoldan giden bir işaretçi hazırlıyor, bu eleman da bu yolda. Bu benim Pi’m; Pi değeri benim değerimi değiştirmeme neden olan elemanı takip ve kaydeder. Şimdi tekrar gidelim ve en ucuzunu tekrar bulalım. Bunu biraz hızlı yapacağız, bu hızlı bir algoritma.

Aynı şeyi tekrar yapacağız. Dışarı çıkarmak için en ucuz olanı hangisi? Bu eleman değil mi? Bunu dışarı alacağız, bunun bütün komşularını güncelliyoruz. Bu eleman 5 oluyor, bu 12, bu da 9. Bu eleman değişmiyor. Bunu değiştirmiyoruz, çünkü artık öncelikli kuyrukta değil. Bu elemanların işaretçilerini ayarlıyoruz. Bu basamakta da işimiz bitti. Tekrar en ucuzunu buluyoruz. En ucuzu hangisi? Buradaki 5. Bunu dışarı alıyoruz. Komşuları güncelliyoruz. Bu 6 oldu şimdi. Ve bu işaretçimiz var.

Bu elemana bir güncelleme yapmıyoruz, çünkü öncelikli kuyrukta değil. Bu eleman 14 oluyor, bu 8. Bu elemanı güncelliyoruz, 8. Bunu doğru bir şekilde yaptım mı? Evet, Pi bu elemanın bir fonksiyonu. Bu eleman daha sonra yok oluyor. Burada unuttuğum birşey var, 12, evet, bu kaldırıldı. Çünkü Pi sadece bir fonksiyon, şimdi tamamım. Şimdi A kümem bu 3 elemanı içeriyor, şimdi en ucuz kenarı arıyorum. Biliyorum ki, bu en az kapsayan ağaçta. Bunu açgözlülükle seçebilirim..

Şimdi, en ucuz eleman hangisi? Bu eleman gibi gözüküyor? Evet, 6. Bunu alıyoruz ve bunları güncellememiz gerekiyor. Burada bir işlem yok. Bu elemanlar zaten A’da oldukları için bir şey değişmiyor. Şimdi en ucuzumuz 8. 8’i dışarı alıyoruz; bunu güncelliyoruz. Burada yapılacak bir şey yok; burada da yok. Hayır, hayır, burada 14 yerine bunu 3 yapabiliriz. Bu işaretçiden vazgeçip şunu alıyoruz; şimdi en ucuzu 3. 3’te yapılacak bir şey yok tabii ki. Son olarak 9’u alıyorum. Tamam. Ve 15. Tamam. Algoritma sona eriyor.

Şimdi baktığımda, başlangıçta sahip olduğum bütün kenarları aldığımı görüyorum.

Burada bir çözümleme yapalım. Bu kısım bana Teta V düzeyinde maliyet getirdi, doğru mu? Şimdi bu kısımda ne yaptığımıza bakalım; burayı yaparken bu döngüye kaç defa girdik? V defa. Kuyruğa V tane eleman koyduk; hiç bir şey eklemedik. Onları sadece dışarı aldık; V defa. Burada V çarpı belli sayıda en küçüğü bulma işlemi yaptık. Daha sonra komşuluk listesine gittik ve sabit bazı işler yaptık. Ama azaltılmış anahtarlarımız açıkça olmasa da kesin olarak elde edildi. Bu buradaki işlemimiz.

Kaç tane kesin olarak azaltılmış anahtarımız var? Bu bizim pahalı işlemimiz olacak. Bu durumda küçük u’nun derecesi kadar. Sonuçta toplamda, kaç tane azaltılmış anahtarımız var? V tane geçiş var. Küçük u ne kadar büyük olabilir? En fazla küçük v düzeyinde. Yani kullanımda azalma oldu. Ama bundan daha iyi bir sınırlama elde edebiliriz.

Gerçekten kaç tane var? En fazla E seviyesinde. Çünkü, ne yapıyorum, bütün köşelerin derecelerini topluyorum. Bu benim bunu kaç defa yürüttüğümü gösteriyor. Yani Teta E düzeyinde kesin azaltılmış anahtarlarım var. Şimdi süre, Teta v çarpı en küçüğün dışarı alınması için gerekli zaman, artı E çarpı azalan anahtar için gereken süreye eşittir. Dolayısıyla, şimdi, veri yapılarına bakalım ve farklı veri yapılarında bu formül ne kadar zaman süre alıyor onu bulalım.

Bir veri yapısını oluştururken farklı yollarımız vardır. En küçüğü bulma, anahtarların azaltılması ve toplam alma maliyetleri. Bir veri yapısı oluşturmanın en kolay yolu sıralanmamış bir dizilim oluşturmaktır. Eğer sırasız bir dizilim varsa, dizinin en küçük elemanını bulmak neye mal olur? Doğru, bu durumda büyük-O büyük V düzeyinde, çünkü bu dizilim V büyüklüğünde bir dizilimdir. Peki ya anahtar azaltma? Bunu 1 düzeyinde halledebilirim.

Toplamda . Güzel seviyesinde bir algoritma. Veya bu insanların önerdiği gibi binary heap yani ikili yığında nasıl olur? En küçüğü bulma işleminde, ikili yığın bana O (log V)’ye mal olacaktır. Anahtar azaltma ise, log V süresine mal olur, çünkü değerleri sadece karıştırırsınız, aslında köke doğru karıştırırsınız. Böylece buradaki toplam maliyet nedir?

E log V, güzel. Hangisi daha iyi? Bu duruma göre değişir. Hangisi ne zaman daha iyidir? Eğer yoğun bir grafik ise E ’ye yakındır, bu durumda dizilim daha iyidir. Ama eğer yoğun değil, seyrek bir grafikse, E ’den oldukça küçüktür ve ikili yığın daha verimlidir. Bu Fibonacci Yığını diye çağrılan bir veri yapısının bulunmasını sağladı. Fibonacci Yığını kitabın 20. Bölümünde işleniyor. Sizi içerikten sorumlu tutmayacağız ama bu gerçekten ilginç bir veri yapısıdır, çünkü amortize edilmiş bir yapıdadır. Bu veri yapısıyla en küçüğü dışarı alma işlemini log V düzeyinde amortize edilmiş sürede yapabilirsiniz.

Anahtar azaltmayı ise amortize edilmiş 1 düzeyinde yaparsınız. Bunları kullandığımda ne elde ediyorum? Bu V kere log V artı E. E artı VlogV. Bunlar amortize edilmiş, pekiyi bu ne? Şaşırtmacalı bir soru. Bu en kötü durum. Burada amortize edilmemiş.. Bunlar amortize edilmiş; bu da zaten amortize etmenin güzelliği. Bunun en kötü durum olduğunu söyleyebiliyorum. E artı VlogV, çünkü amortize edilmiş işlem maliyetlerini eklediğim zaman, gerçek maliyetler için bir üst sınır bulmuş oluyorum. Bu nedenle farklı işlemlere farklı maliyetler atamanın amortize edilmiş analizin güzelliklerinden biri olduğunu söylüyorum. Hepsini toplarım ve en kötü durum maliyetini bulurum. Bu sonuçta VlogV olur.

Gitmeden önce bir kaç algoritma daha var. Kitabınızdaki Kruskal Algoritması amortize edilmiş veri yapısına başka bir örnek. Buna Disjoint Set yani Ayrışık Küme veri yapısı da deniyor. Bu da ikili yığın gibi E logV zamanında çalışıyor. Dolayısıyla kitabınızı okumanızı tavsiye ediyorum. Bu konuda bugüne kadar yapılmış en iyi algoritma bizim fakültedeki David Karger ile eski bir mezunumuz Phil Kline’nın, ki kendisi şimdi Brown’da profesör ve Princeton’da profesörlük yapan Robert Tarjan, ki kendisi hemen her veri yapısının ustası olarak görülüyor, bunlar tarafından 1993’te geliştirildi. Bu rastgele bir algoritma. V artı E düzeyindeki beklenen süre ile sonucu veriyor. Bugüne kadar yapılmışların en iyisi bu.

Doğrusal zamanda bir deterministic yani belirlenimci bir en kötü durum sınırlaması olup olmadığı bugüne kadar çözülmemiş problemlerden biridir. Ama rastgele doğrusal çözüm vardır ve bunun dışında ek varsayımlar olmadan elde edilen en iyi sınır budur.

Tamam, çok ilginç konular işledik. Gelecek sefer pratikte kullanılan açgözlü algoritmalar ve dinamik programlama ile ilgili bir sürü fikir üzerinde çalışacağız.

Dersimiz burada bitmiştir.