• Mavzu: NP - to‘liq masalalar. Hisoblashda yechilmaslik hollari NP-toliq muammolarga kirish
  • NP-toliq muammolarning tarifi
  • 1-Mustaqil ish Fan: Algoritmlarni loyihalash Fakultet: kif guruh: 410-22 Bajardi: Vohobjonov Zavqiddin Mavzu: np to‘liq masalalar. Hisoblashda yechilmaslik hollari np-to'liq muammolarga kirish




    Download 39,79 Kb.
    bet1/8
    Sana18.05.2024
    Hajmi39,79 Kb.
    #243274
      1   2   3   4   5   6   7   8
    Bog'liq
    Zavqiddin AL-M1
    1, Arxivlashtirish dasturi bilan ishlash reja Kirish. Fayllarni ar, Zulfiya, Tohirjon2, Algoritm-Referat

    O‘zbekiston respublikasi raqamli texnologiyalar vazirligi
    Muhammad al-Xorazmiy nomidagi Toshkent axborot texnologiyalari universiteti Nurafshon filliali

    1-Mustaqil ish
    Fan: Algoritmlarni loyihalash
    Fakultet: KIF
    Guruh: 410-22
    Bajardi: Vohobjonov Zavqiddin
    Mavzu: NP - to‘liq masalalar. Hisoblashda yechilmaslik hollari


    NP-to'liq muammolarga kirish
    NP-to'liqlik tushunchasi hisoblash murakkabligi nazariyasi sohasidagi asosiy mavzudir. NP-to'liq muammolar echilishi eng qiyin bo'lgan hisoblash muammolari sinfini ifodalaydi, chunki ular oqilona vaqt ichida yechim topa oladigan samarali algoritmlarga ega emas deb hisoblashadi. Bu muammolar katta nazariy va amaliy ahamiyatga ega, chunki ular nafaqat hisoblash haqidagi tushunchamiz chegaralarini kengaytiribgina qolmay, balki logistika va rejalashtirishdan tortib kriptografiya va sun'iy intellektgacha bo'lgan turli sohalarda ham keng qamrovli ta'sirga ega.
    NP-to'liq muammolarning ta'rifi
    NP-to'liq muammolar - bu echilishi eng qiyin bo'lgan hisoblash muammolari sinfidir. Ular NP murakkablik sinfiga tegishli bo'lib, "nodeterministik polinom vaqt" degan ma'noni anglatadi. Bu shuni anglatadiki, NP-to'liq muammoning har qanday yechimi uchun uni to'g'ri deb tezda tekshirish mumkin, ammo bu yechimni topish uchun zarur bo'lgan vaqt muammoning o'lchamiga qarab eksponent ravishda o'sishi mumkin. Boshqacha qilib aytganda, bugungi kunda mavjud bo'lgan eng kuchli kompyuterlar bilan ham NP-to'liq muammolarni oqilona vaqt ichida hal qila oladigan ma'lum samarali algoritm yo'q.
    "NP-to'liq" atamasi 1972 yilda matematik Richard Karp tomonidan kiritilgan bo'lib, u bir nechta muhim muammolar, masalan, sayohatchi sotuvchi muammosi va sumka muammosi bu sinf vakillari ekanligini ko'rsatdi. NP-to'liq muammolar shunday xususiyatga egaki, agar ulardan birontasini samarali hal qilish mumkin bo'lsa, NP sinfidagi barcha muammolarni ham samarali hal qilish mumkin. Bu shuni anglatadiki, NP-to'liq muammolar, ma'lum ma'noda, NPdagi "eng qiyin" muammolardir, chunki ular hozirda duch kelayotgan eng qiyin hisoblash muammolarini ifodalaydi.
    Muammoning NP-to'liq yoki yo'qligini aniqlash murakkab va qiyin vazifadir, chunki bu muammo NPda ham ekanligini va hech bo'lmaganda NPdagi eng qiyin muammolar kabi qiyin ekanligini isbotlashni talab qiladi. Bu butun dunyo bo'ylab kompyuter olimlari va matematiklarining e'tiborini jalb qilishda davom etayotgan ko'plab ochiq savollar va hal qilinmagan muammolarga ega bo'lgan hisoblash murakkabligi nazariyasi bo'yicha boy tadqiqotlar maydoniga olib keldi.

    Download 39,79 Kb.
      1   2   3   4   5   6   7   8




    Download 39,79 Kb.

    Bosh sahifa
    Aloqalar

        Bosh sahifa



    1-Mustaqil ish Fan: Algoritmlarni loyihalash Fakultet: kif guruh: 410-22 Bajardi: Vohobjonov Zavqiddin Mavzu: np to‘liq masalalar. Hisoblashda yechilmaslik hollari np-to'liq muammolarga kirish

    Download 39,79 Kb.