Algoritmaların Tasarımı ve Analizi #13 | Güçlü Bileşenler: Kosaraju–Sharir Algoritması
Açgözlü Algoritmalar (Greedy) ve GraflarEğitmen: Dr. Süleyman Burak ÇELİK
Sınavda şöyle gelir: bu yönlü çizgenin güçlü bileşenlerini doğrusal zamanda bulun. Bu derste güçlü bağlantılılığı ve bileşen çizgesini kuruyor, iki derinlik öncelikli aramayla çalışan Kosaraju–Sharir algoritmasını adım adım izliyor ve iki sınav tipi soruyu çözüyoruz. Bu derste: 1. Güçlü bağlantılılık: gidip geri dönebilen düğümler aynı bileşende 2. Bileşen çizgesi her zaman dagdır; kaynak ve kuyu bileşenler 3. Tek aramanın bir ağacı iki bileşeni birden toplayabilir (klasik yanlış) 4. Kuyu bileşenden başlamak: ters çizgede en son biten düğüm 5. Kosaraju–Sharir: ters çizgede bitiş yığını, asıl çizgede yığından çıkan sırayla bileşen toplama; O(V + E) 6. Soru 1: sekiz düğüm, on iki kenar; tam iz, bitiş sırası ve dört bileşen; alfabe sırası ve tepeden boşaltma tuzakları 7. Soru 2: bileşen çizgesi, kaynak ve kuyu, ifade eleme; yeni bir ok bileşenleri nasıl birleştirir Bölümler: 0:00 Tek Yönlü Sokaklar 0:47 Kaynak Kitap ve Bugünkü Konu 0:58 Güçlü Bağlantılılık 1:45 Bileşen Çizgesi 2:26 Tek Arama Yetmez 2:57 Kuyu Bileşenden Başlamak 3:40 Ters Çizgede Son Sıra 4:32 Kosaraju–Sharir Algoritması 5:22 Soru 1: Sekiz Düğümlü Çizge 6:41 Soru 1: Birinci Aşama 8:36 Soru 1: İkinci Aşama ve Bileşenler 9:55 Soru 1: Tuzaklar ve Sağlama 10:55 Soru 2: Bileşen Çizgesi 12:18 Soru 2: Hangisi Doğru? 13:17 Bu Derste Öğrendiklerimiz 13:59 Akılda Kalan Kural ve Sıradaki Ders Bir sonraki derste ağırlıklı yönsüz çizgelere geçip en küçük kapsayan ağacı kuracağız. Kaynak kitap: Jeff Erickson — Algorithms, 1. baskı (2019, CC BY 4.0), §6.5–6.6 (kitap s. 237–242; PDF s. 255–260). 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 13. dersi. Ön koşul: Topolojik Sıralama ve Daglarda Dinamik Programlama. Hedef kitle: bilgisayar mühendisliği ve yazılım öğrencileri.