Algoritmlarni loyihalash fanidan 3-mustaqil ish

"NP-to'liq masala" esa "polinomial vaqtda tekshirish va tasdiq qilish mumkin" sinfida bo'lgan masalalar uchun ishlatiladi. Bu turidagi masalalarning sertifikatlari polinomial uzluksizlik bilan tekshirilishi mumkin. Ya'ni, masala hal qilinishi polinomial vaqtda tekshirilishi mumkin, shunday bo'lsa, masala NP-to'liq deyiladi.

Umumiy ravishda aytganda, P va NP sinflari haqida to'liq tushuncha uchun, matematika va kompyuter ilmi sohalaridagi muhim bir tushuncha bo'lib, masalalarni tartiblash va hal qilish bilan bog'liq algoritmalarga asoslangan. NP sinifini hal qilish mumkinligi hali hal qilinmagan masalalar uchun muhimdir va bu sohada hal qilish mumkinligi haqida zamonaviy ilm-fan olimlari orasida hali chaqirilmagan savolni o'z ichiga oladi.

Algoritmlarni baholash mezonlari. Vaqt va hajim bo’yicha baholashga misollar.

Algoritmlarni baholashning bir necha mezonlari mavjud. Ba'zilari quyidagilardan foydalaniladi:

1. Vaqt kompleksiteti: Algoritmdagi har bir qadamning yakunlanishi uchun ketgan vaqt miqdori. Bunda, algoritmdagi operatsiyalar soni va ularning har birining vaqt miqdori ko'rsatiladi. Har bir amalning vaqt miqdori bir biriga qo'shilib yurishida umumiy vaqt miqdori aniqlanadi.

2. Xotira kompleksiteti: Algoritmda foydalaniladigan xotira obyektlari soni bilan birga ifodalangan ma'lumot miqdori. Xotira kompleksiteti algoritmda kerak bo'lgan xotira ma'lumotlarni o'lchash uchun ishlatiladi.

3. Hajm (memory) kompleksiteti: Algoritmda foydalaniladigan qo'llanma disk kondensatoridagi hajm miqdorini ifodalaydi. Hajm kompleksiteti algoritmda nima qadar xotira kerak bo'lganligi haqida ma'lumot beradi.

Baholashning bir necha misollariga o'tishimiz mumkin:

1. Vaqt bo'yicha misol: Agar bir algoritmda bir qiymatlar ro'yxati bo'lsa vaqiqtalab bo'lgan qiymatni izlash uchun bu ro'yxatni to'liq ko'rib chiqish kerak bo'lsa, bu yerda algoritm o'nlik vaqt kompleksitetiga ega bo'ladi.