Algoritmaların Tasarımı ve Analizi #09 | Açgözlü Seçim ve Doğruluk

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

Geçen derste küçük problemlerin doğru cevaplarını saklayarak tekrar hesaplamayı kaldırdık. Bugün bazı problemlerde daha doğrudan bir seçim yapabileceğimizi göreceğiz. Her adımda belirli bir ölçüte göre bir seçeneği alacak, kararımızı geri değiştirmeden ilerleyeceğiz. En erken biteni seçmek neden güvenli. Algoritmaların çalışma adımlarını gerçek konuşmayla eşleşen şemalar ve özgün örneklerle adım adım inceliyoruz. Bu derste: 1. Güvenli kural: en erken biteni seç 2. Önce B ve C; ardından A atlanır 3. Çakışmayı denetleyip sınırı koru 4. G ile birlikte dört iş seçildi 5. Değiş tokuş: ilk işi değiştir, sayı aynı kalsın 6. Aynı gerekçe kalan problemde tekrarlanır 7. İki doğal kural neden başarısız? 8. Amaç değişirse kural da yeniden incelenir 9. Siz deneyin: uç noktalar çakışıyor mu? Bölümler: 0:00 Bir seçimi yapıp geri dönmeden ilerlemek 0:50 Zaman aralıklarının kuralını açık tut 1:38 Güvenli kural: en erken biteni seç 2:25 Önce B ve C; ardından A atlanır 3:09 Çakışmayı denetleyip sınırı koru 3:52 G ile birlikte dört iş seçildi 4:38 Değiş tokuş: ilk işi değiştir, sayı aynı kalsın 5:26 Aynı gerekçe kalan problemde tekrarlanır 6:14 İki doğal kural neden başarısız? 7:04 Amaç değişirse kural da yeniden incelenir 7:50 Siz deneyin: uç noktalar çakışıyor mu? 8:35 Sıralama ile taramayı ayrı say 9:20 Açgözlü seçimin dayanağı kanıttır Kaynak kitap: Jeff Erickson — Algorithms, 1. baskı (2019, CC BY 4.0), §4.2–4.3. Kavram ve konu sırası kaynak kitaptan izlenir; anlatım, şemalar ve sayısal örnekler özgündür. Ekrandaki sayılar açık varsayımlı öğretim modelleridir; gerçek cihaz ölçümü değildir. Kitap: https://jeffe.cs.illinois.edu/teaching/algorithms/ (yasal ve ücretsiz kaynak). Hedef kitle: bilgisayar mühendisliği ve yazılım öğrencileri.