P ve NP
- Algoritmalar kursu
- Uzman seviye
- Ders 5/41
- 4 dk
P ve NP sınıflarının farkını öğrenirsin.
P ve NP
P, polinom zamanında çözülebilen problemler kümesidir. NP, verilen bir çözümün polinom zamanda doğrulanabildiği problemler kümesidir.
Her P problemi NP'dir. Ama NP'nin tümü P midir? Bu, bilgisayar biliminin en büyük açık sorunudur.
Doğrulama örneği
Bir dizinin sıralı olup olmadığını doğrulamak O(n)'dir: her komşu çifti karşılaştır. Bu yüzden sıralama denetimi P'dir.
Sıralı olup olmadığını doğrulayan bir fonksiyon, P sınıfına örnektir. Çözümü (sıralı diziyi) ver, anında doğrula.
Uygulama is_sorted fonksiyonu
is_sorted(arr) yaz. Dizinin sıralı olup olmadığını döndür. print(is_sorted([1, 2, 3])) ile True yazdır.
Başlangıç kodu
def is_sorted(arr):
# Dizi sıralı mıÖrnek çözüm
def is_sorted(arr):
# Dizi sıralı mı
for i in range(len(arr) - 1):
if arr[i] > arr[i + 1]:
return False
return True
print(is_sorted([1, 2, 3]))Beklenen çıktı
True
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 NP problemlerinin ortak özelliği nedir?
- Polinom zamanda çözülür
- Çözümü polinom zamanda doğrulanır Doğru cevap
- Çözümü yoktur
- Sadece döngüler içerir
Açıklama: NP problemlerinin çözümü polinom zamanda doğrulanır.
2 sıralı koşulu
if arr[i] > arr[i + ____]:if arr[i] > arr[i + 1]:Açıklama: 1 doğru.
3 P ve NP: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
P |
Çözülür |
NP |
Doğrulanır |
P=NP |
Açık sorun |
polinom |
Hızlı |