Algoritmaların Tasarımı ve Analizi #14 | En Küçük Kapsayan Ağaç: Güvenli Kenar ve Borůvka

Açgözlü Algoritmalar (Greedy) ve Graflar

Eğitmen: Dr. Süleyman Burak ÇELİK

Sınavda şöyle gelir: bu ağırlıklı çizgenin en küçük kapsayan ağacını bulun; toplam ağırlık kaç? Bu derste ağırlıkların farklı olduğu çizgede ağacın tek olduğunu, güvenli ve gereksiz kenarı, bütün algoritmaların ortak şablonunu ve Borůvka algoritmasını adım adım kuruyor, iki sınav tipi soruyu çözüyoruz. Bu derste: 1. En küçük kapsayan ağaç: bütün düğümleri en az toplam ağırlıkla bağlayan ağaç 2. Ağırlıklar farklıysa en küçük kapsayan ağaç tektir 3. Ara orman; güvenli, gereksiz ve kararsız kenar 4. Bir bileşenden dışarı çıkan en hafif kenar her zaman ağaçtadır (değiş tokuş gerekçesi) 5. Tek şablon: güvenli kenar ekle, gereksizi at, tekrarla 6. Borůvka: her bileşen en hafif dış kenarını seçer; bileşen sayısı her turda en az yarıya; O(E log V) 7. Soru 1: sekiz düğüm, on üç kenar; Borůvka turları, iki kez sayma tuzağı, toplam 37 ve sağlama 8. Soru 2: ara ormanda kenar sınıflandırma ve ifade eleme Bölümler: 0:00 Köyleri En Ucuza Bağlamak 0:49 Kaynak Kitap ve Bugünkü Konu 1:01 En Küçük Kapsayan Ağaç 1:44 Farklı Ağırlıklar ve Tek Ağaç 2:31 Güvenli, Gereksiz, Kararsız Kenar 3:25 Neden Güvenli Kenar Ağaçtadır? 4:04 Tek Algoritma Şablonu 4:32 Borůvka Algoritması 5:34 Soru 1: Sekiz Düğümlü Çizge 6:54 Soru 1: Birinci Tur 8:43 Soru 1: İkinci Tur 9:39 Soru 1: Toplam ve Sağlama 10:35 Soru 2: Ara Orman 12:07 Soru 2: Hangisi Doğru? 13:20 Bu Derste Öğrendiklerimiz 14:00 Akılda Kalan Kural ve Sıradaki Ders Bir sonraki derste aynı şablonun iki ünlü biçimini, Jarník (Prim) ve Kruskal algoritmalarını göreceğiz. Kaynak kitap: Jeff Erickson — Algorithms, 1. baskı (2019, CC BY 4.0), §7.1–7.3 (kitap s. 257–263; PDF s. 275–281). Kavram ve konu sırası kaynak kitaptan izlenir; anlatım, şemalar ve sayısal örnekler özgündür. Kitaptan metin, şekil veya problem kopyalanmamıştır. Kitap: https://jeffe.cs.illinois.edu/teaching/algorithms/ (yasal ve ücretsiz kaynak). Algoritmaların Tasarımı ve Analizi serisinin 14. dersi. Ön koşul: Güçlü Bileşenler: Kosaraju–Sharir Algoritması. Hedef kitle: bilgisayar mühendisliği ve yazılım öğrencileri.

Bu videoyu izlemek için Premium üyelik gerekir.