Azaltma
- Algoritmalar kursu
- Uzman seviye
- Ders 7/41
- 4 dk
Bir problemi başka bir probleme azaltmayı öğrenirsin.
Azaltma
Azaltma (reduction), bir problemi başka bir probleme dönüştürmektir. Eğer A, B'ye polinom zamanda azaltılırsa ve B çözülürse A da çözülür.
Bu teknik, NP-complete problemleri kanıtlamak için kullanılır. Yeni bir problemin NP-complete olduğunu göstermek için bilinen bir NP-complete problemi ona azaltılır.
Çözüm doğrulama
Bir alt kümenin toplamı hedefe eşit mi diye doğrulama O(n)'dir. Bu, subset sum'in NP'de olduğunu gösterir.
Doğrulama polinom zamanda yapılır; bu yüzden subset sum NP'dedir. Ama çözümü bulmak NP-complete'tir.
Uygulama verify_subset fonksiyonu
verify_subset(arr, subset, target) yaz. subset'in toplamı target'a eşit mi döndür. print(verify_subset([3, 5, 7], [3, 7], 10)) ile True yazdır.
Başlangıç kodu
def verify_subset(arr, subset, target):
# Alt kümenin toplamı hedefe eşit miÖrnek çözüm
def verify_subset(arr, subset, target):
# Alt kümenin toplamı hedefe eşit mi
return sum(subset) == target
print(verify_subset([3, 5, 7], [3, 7], 10))Beklenen çıktı
True
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Azaltma: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
A → B |
Azaltma |
polinom |
Hızlı |
B çözülür |
A çözülür |
NP-complete |
Hedef |
2 Subset sum'in doğrulaması ne kadar sürede?
- O(1)
- O(2^n)
- O(n²)
- O(n) Doğru cevap
Açıklama: Doğrulama O(n)'dir; sadece alt kümenin toplamı hesaplanır.
3 toplam hesabı
return sum(____) == targetreturn sum(subset) == targetAçıklama: subset doğru.