Özet - NP-completeness
- Algoritmalar kursu
- Uzman seviye
- Ders 8/41
- 4 dk
Bir problem sınıflandırmasını yazdıran mini görev yaparsın.
Özet - NP-completeness
Bu grupta P, NP ve NP-complete kavramlarını öğrendin. Brute force çözüm, polinom doğrulama ve azaltma tekniği birleşince sınıflar anlaşılır.
Şimdi tüm parçaları bir araya getiren bir fonksiyon yazacaksın. Bu özet, grubun kavramlarını tek bir kodda birleştirir.
Uygulama count_subsets fonksiyonu
count_subsets(arr, target) yaz. Toplamı target olan alt küme sayısını döndür. print(count_subsets([3, 5, 7], 10)) ile 1 yazdır.
Başlangıç kodu
def count_subsets(arr, target):
# Toplamı target olan alt küme sayısını bulÖrnek çözüm
def count_subsets(arr, target):
# Toplamı target olan alt küme sayısını bul
n = len(arr)
count = 0
for mask in range(1 << n):
s = 0
for i in range(n):
if mask & (1 << i):
s += arr[i]
if s == target:
count += 1
return count
print(count_subsets([3, 5, 7], 10))Beklenen çıktı
1
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 NP-complete bir problemi çözmek ne kadar sürer?
- Üstel zaman (en kötü) Doğru cevap
- Polinom zaman
- Sabit zaman
- Logaritmik zaman
Açıklama: En kötü durumda üstel zaman gerekir.
2 bitmask döngüsü
Soru
for mask in range(1 ____ n):
Cevap
for mask in range(1 << n):Açıklama: << doğru.
3 Özet - NP-completeness: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
is_sorted |
P |
brute_force_subset |
NP-complete |
verify_subset |
Doğrulama |
azaltma |
Reduction |