NP-complete
- Algoritmalar kursu
- Uzman seviye
- Ders 6/41
- 4 dk
NP-complete problemlerin özelliğini öğrenirsin.
NP-complete
Bir problem NP-complete ise hem NP'de hem de NP-hard'dır. Tüm NP problemleri bu probleme polinom zamanda azaltılabilir.
Eğer bir NP-complete problem polinom zamanda çözülürse, tüm NP polinom zamanda çözülür demektir; yani P=NP.
Brute force
Subset sum NP-complete bir problemdir. Basit çözüm, tüm 2^n alt kümeyi denemektir; bu O(2^n)'dir.
Küçük girdiler için brute force işe yarar. Büyük girdiler için yaklaşık algoritmalar gerekir.
Uygulama brute_force_subset fonksiyonu
brute_force_subset(arr, target) yaz. Tüm alt kümeleri dene, toplam target olan var mı döndür. print(brute_force_subset([3, 5, 7], 10)) ile True yazdır.
Başlangıç kodu
def brute_force_subset(arr, target):
# Tüm alt kümeleri deneÖrnek çözüm
def brute_force_subset(arr, target):
# Tüm alt kümeleri dene
n = len(arr)
for mask in range(1 << n):
s = 0
for i in range(n):
if mask & (1 << i):
s += arr[i]
if s == target:
return True
return False
print(brute_force_subset([3, 5, 7], 10))Beklenen çıktı
True
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 alt küme toplam
subset_sum([3, 5, ____], 10) → Truesubset_sum([3, 5, 7], 10) → TrueAçıklama: 7 doğru.
2 Subset sum hangi sınıftadır?
- P
- Logaritmik
- NP-complete Doğru cevap
- Sabit zaman
Açıklama: Subset sum NP-complete'tir.
3 NP-complete: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
NP-complete |
Zor |
brute force |
2^n |
subset sum |
Örnek |
P=NP |
Açık |