Algoritmaların Tasarımı ve Analizi #11 | Derinlik Öncelikli Arama: Kenar Türleri ve Döngü Bulma

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

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

Sınavda şöyle gelir: yedi düğümlü yönlü bir çizgede derinlik öncelikli aramanın ön ve son numaraları nedir, her kenar hangi türdendir, çizgede döngü var mı? Bu derste aramayı saat, yığın ve düğüm durumlarıyla adım adım kuruyor, kenar türlerini aralıklardan okuyor ve iki sınav tipi soruyu çözüyoruz. Bu derste: 1. Derinlik öncelikli arama: önce dalı sonuna kadar izle, sonra geri dön 2. Sarmal: her düğümden bir kez başlatmak, orman ve ağaç sayısı 3. Saat ile ön numara ve son numara; aralıklar iç içe ya da ayrık 4. Düğüm durumları: yeni, aktif, bitmiş; aktif düğümler yığındaki yoldur 5. Dört kenar türü: ağaç, ileri, geri, çapraz 6. Geri kenar varsa döngü vardır; yönlü döngüsüz çizge denetimi O(V + E) 7. Soru 1: yedi düğüm, on kenar; tam iz, 14 saat adımı, kenar sınıflandırması ve sağlama 8. Soru 2: ön koşul çizgesinde döngü denetimi ve seçenek eleme Bölümler: 0:00 Ön Koşullarda Döngü Var mı? 0:44 Kaynak Kitap ve Bugünkü Konu 0:55 Derinlik Öncelikli Arama 1:46 Bütün Çizgeyi Dolaşmak: Sarmal ve Orman 2:20 Saat: Ön ve Son Numara 3:12 Yeni, Aktif, Bitmiş 3:41 Dört Kenar Türü 4:36 Geri Kenar ve Döngü 5:32 Soru 1: Yedi Düğümlü Çizge 6:29 Soru 1: Adım Adım İz 9:15 Soru 1: Kenarları Sınıflandırma ve Sağlama 10:16 Soru 2: Ön Koşul Çizgesi 12:29 Soru 2: Hangisi Doğru? 13:11 Bu Derste Öğrendiklerimiz 13:51 Akılda Kalan Kural ve Sıradaki Ders Bir sonraki derste son numaraları kullanarak topolojik sıralamayı ve yönlü döngüsüz çizgelerde dinamik programlamayı göreceğiz. Kaynak kitap: Jeff Erickson — Algorithms, 1. baskı (2019, CC BY 4.0), §6 giriş, §6.1–6.2 (kitap s. 225–232; PDF s. 243–250). 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 11. dersi. Ön koşul: Çizgeleri Dolaşmak (temsil, kuyruk ve yığın). Hedef kitle: bilgisayar mühendisliği ve yazılım öğrencileri.