Algoritmaların Tasarımı ve Analizi #12 | Topolojik Sıralama ve Daglarda Dinamik Programlama
Açgözlü Algoritmalar (Greedy) ve GraflarEğitmen: Dr. Süleyman Burak ÇELİK
Sınavda şöyle gelir: yönlü döngüsüz bir çizgenin topolojik sırasını doğrusal zamanda bulun; kenarlar ağırlıklıysa en uzun yolu hesaplayın. Bu derste ters son sıranın neden topolojik sıra olduğunu gösteriyor, aynı aramayla tablo doldurarak en uzun yolu buluyor ve iki sınav tipi soruyu çözüyoruz. Bu derste: 1. Topolojik sıra: her ok soldan sağa; ön sıra topolojik sıra değildir (karşı örnek) 2. Ters son sıra = topolojik sıra: kenar başına üç durum gerekçesi 3. Diziyi doldurmak: saat düğüm sayısından başlar, biten düğüm saatin gözüne yazılır 4. Örtük topolojik sıra: her düğümü bittiği anda işlemek 5. Belleğe alma ve dinamik programlama: bağımlılık çizgesi dag olmalı (Fibonacci örneği) 6. Dagda en uzun yol: hedef 0, kenar ağırlığı + komşunun değeri, en büyüğü; O(V + E) 7. Soru 1: yedi düğümlü dagda tam iz; ön ve son numaralar, ters son sıra, sağlama 8. Soru 2: aynı dagda ağırlıklarla her düğümden hedefe en uzun yol tablosu, açgözlü seçim tuzağı ve en kısa yol Bölümler: 0:00 Hangi Ders Önce Alınır? 0:55 Topolojik Sıra Nedir? 1:22 Neden Ters Son Sıra? 2:11 Sırayı Diziye Yazmak 2:57 Örtük Topolojik Sıra 3:36 Belleğe Alma ve Dinamik Programlama 4:29 Dagda En Uzun Yol 5:28 Soru 1: Yedi Düğümlü Dag 6:30 Soru 1: Adım Adım İz 9:09 Soru 1: Topolojik Sıra ve Sağlama 9:55 Soru 2: Ağırlıklı Dag 11:14 Soru 2: En Uzun Yol Tablosu 12:07 Soru 2: Tuzak ve En Kısa Yol 12:55 Bu Derste Öğrendiklerimiz 13:38 Akılda Kalan Kural ve Sıradaki Ders Bir sonraki derste döngülü yönlü çizgelere dönüp güçlü bağlı bileşenleri doğrusal zamanda bulacağız. Kaynak kitap: Jeff Erickson — Algorithms, 1. baskı (2019, CC BY 4.0), §6.3–6.4 (kitap s. 232–237; PDF s. 250–255). 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 12. dersi. Ön koşul: Derinlik Öncelikli Arama: Kenar Türleri ve Döngü Bulma. Hedef kitle: bilgisayar mühendisliği ve yazılım öğrencileri.
Bu videoyu izlemek için Premium üyelik gerekir.