Bajaruvchi: Bekmatov e tekshiruvchi: Axmedov f samarqand-2022 5-mavzu. P, Np, np-to’liq masalalar



Download 0,6 Mb.
bet1/6
Sana15.06.2022
Hajmi0,6 Mb.
#672519
  1   2   3   4   5   6
Bog'liq
5-hafta, Bekmatov


O’ZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI VA KOMMUNIKATSIYALARNI RIVOJLANTIRISH VAZIRLIGI
MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI SAMARQAND FILIALI

TELEKOMMUNIKATSIYA TEXNOLOGIYALARI VA KASB TA’LIMI FAKULTETI
5-labarotoriya ishi

Bajaruvchi: Bekmatov E
Tekshiruvchi:Axmedov F

Samarqand-2022

5-mavzu. P, NP, NP-to’liq masalalar.
1.1. NP- To’liq masalalar .
1.2. NP- To’liq masalalarga keltirish usullari .
1.3. Graf erkin uchlarini ajratish masalasi .
1.4. Kommivoyajer haqidagi masalar .
1.5. Qatorlar yig’indisini hisoblash .
1.6. To’plam ostilari yig’indisini hisoblash.


Ishning maqsadi: NP to’liq masalalari haqida tushuncha; NP to’liq masalalariga kiruvchi saper o’yini masalasi va yechimi;
Kerakli jihozlar: Kompyuter, proyektor, doska, C++ dasturlash tili
NP- to`liq masalalarini yechish usullarini keltiring?
Ko'p qiziqarli va amaliy masalalarni polynomial vaqtda hal qilish mumkin emas yoki ular uchun hozirgi vaqtda polinomial algoritmlar topilmagan. NP (Nondeterminictic Polinomial) murakkablik sinfidagi masala - bu shunday masalalar sinfidirki, ularni yechish uchun polinomial algoritm mavjud bo'lmasligi mumkin, lekin agar biz uning yechimini bilsak (masalan, biz buni taxminan topgan bo’lsak), unda polinominal vaqt ichida uning to'g'riligini tekshirish mumkin.
NP-to'liq masalalarning namunalari:

  • Bool formulalarining bajarilish masalasi

  • “O’n beshlik” o'yinining eng qisqa yechimi

  • Kommivoyajer masalasi

  • Shteyner masalasi

  • Grafni bo'yash masalasi

  • Graf cho’qqisini qoplash masalasi

  • To’plamni qoplash masalasi

  • Graf cho’qqilarining mustaqil to’plamlari masalasi

  • Saper o’yini

  • Tetris o’yini

NP-murakkab masalalarni hal qilish usullari quyidagilarga bo'linadi:

  • aniq,

  • evristik

  • metaevristik usullari


NP to'liq masalalarni hal qilish uchun evrestik algoritmlar
Evristika yoki evristik algoritm – algoritm deb ta’riflanishi uchun quyidagi hususiyatlarga ega bo’lishi kerak:

1. U odatda shartli ravishda optimal bo’lmasa ham, yahshi yechimlarni topish kerak.
2. Uni ixtiyoriy ma’lum aniq algoritmdan ko’ra, amalga oshirish tezroq va soddaroq bo’lishi kerak.
Odatda yahshi algoritmlar evristik bo’lib chiqadi. Faraz qilaylik, biz tez ishlaydigan va barcha test topshiriqlariga javob beradigan algoritmni tuzdik, lekin uning to’g’riligini isbotlab bilmaymiz. Shunday isbot berilmaguncha, algoritm evristik deb tushuniladi.
Evristika (boshqa yunon tilidan: εὑρίσκω - "qidiraman", "kashf qilaman") - bu bilim sohasi, ijodiy faoliyatning o'ziga xos xususiyatlarini o'rganadigan ilmiy soha. Evristika deganda kognitiv, konstruktiv, amaliy masalalarni hal qilishni osonlashtiradigan sodda usullar va uslublarning umumlashgan majmuasi tushuniladi.
Evristik algoritm (evristik) - bu masalani hal qilish algoritmi, shu jumladan aniq yoki optimal bo'lishi kafolatlanmagan, ammo qo’yilgan masalani hal qilish uchun yetarli bo'lgan amaliy usul. Aniq yechimni topa olmagan holatlarda masalani hal qilishni tezlashtirishga imkon beradi.
Evristik algoritm - bu barcha mumkin bo'lgan holatlarda uning to'g'riligi isbotlanmagan, ammo ko'p hollarda juda yaxshi yechim topishi ma'lum bo'lgan masalani hal qilish algoritmi. Aslida, hatto evristik algoritm rasman noto'g'ri ekanligi ham ma'lum bo'lishi mumkin (ya'ni isbotlangan). Agar u bir vaqtning o'zida noto'g'ri natijani faqat alohida, juda kam uchraydigan va alohida ajratilgan hollarda bersa yoki noaniq, ammo baribir maqbul natijani beradigan bo'lsa, undan foydalanish mumkin.
Oddiy qilib aytganda, evristika mutlaqo matematik asoslangan emas (yoki "umuman to'g'ri emas"), ammo bu amaliy foydali algoritmdir. Masalani hal qilishning aniq algoritmidan farqli o'laroq, evristik algoritmlar quyidagi xususiyatlarga ega ekanligini tushunish muhimdir:

  • yaxshiroq yechimni kafolatlamaydi.

  • garchi u aniq mavjud bo'lsa ham, yechimni topishga kafolat bermaydi.

  • Ba'zi hollarda u noto'g'ri qaror qabul qilishi mumkin.

Hisoblash murakkabligi yuqori bo’lgan masalalarni hal qilish uchun evristik algoritmlardan keng foydalaniladi. Ya’ni ko’p vaqt talab qiladigan va ba’zan texnik jihatdan imkonsiz barcha variantlarni to’liq qayta ko’rib chiqadigan algoritm o’rniga ancha tezroq, ammo yetarlicha nazariy asoslanmagan algoritm qo’llaniladi.
Taqribiy va evristik usullar - yechim elementlarini tanlash uchun evristikadan foydalanish.
Psevdopolinomial algoritmlar - dinamik dasturlash sinfiga oid algoritmlar.
Local yahshilash usuli - ba'zi bir mavjud yechim atrofida eng maqbul yechim izlash.
Tarmoqlar va chegaralar usuli - ba'zi baholashga ko'ra maqbul bo'lmagan yechimlarning barcha sinflarini bekor qilish.
Tasodifiy qidiruv usuli - tanlovni tasodifiy tanlovlar ketma-ketligi bilan ifodalash.

Yaqinlashtiruvchi(approksimatsion) algoritmlar polinomial vaqt ichida bajariladi va optimal darajaga yaqin bo'lish kafolati bo'lgan yechimlarni topadi.
Algoritmlarni ishlab chiqish uchun to'rtta umumiy metodologiya:

  1. Birinchi umumiy metodologiya tez va oson bajariladigan ochko'z algoritmlardir. Asosiy masala bu optimalga yaqin maqbul yechimlarga olib keluvchi ochko'z algoritm qoidalarini topishdir.

  2. Ikkinchi umumiy metodologiya – narxlarni belgilash usuli - iqtisodiy asoslangan; masaladagi har bir cheklovga rioya qilish uchun to'lanishi kerak bo'lgan narxni ko'rib chiqiladi.

  3. Uchinchi umumiy metodologiya – Butun sonli chiziqli dasturlash usulidir. Butun sonli dasturlash masalasi ham chiziqli dasturlash masalasidek qo’yilib, optimal yechim o’zgaruvchilarning qiymati butun musbat son bo’lsin, degan qo’shimcha talab qo’yiladi.

  4. To’rtinchi umumiy metodologiya – dinamik dasturlash usuli bo’lib, optimallashtirish masalalarini hal qilishda, ma'lum cheklovlarni hisobga olgan holda, maksimal yoki minimal echimni qidiradigan masalalar uchun foydali usuldir, chunki u barcha mumkin bo'lgan kichik masalalarni ko'rib chiqadi va hech qachon biron bir sub-masalaning yechimini qaytarmaydi.

Yaqinlashtiruvchi(approksimatsion) algoritmlarning tasnifi:

  • kafolatlangan faoliyat ko’rsatuvchi algoritmlari;

  • lokal optimallashtirish algoritmlari va evristik protseduralar;

  • lokal optimallashtirish algoritmlari va evristik protseduralardan foydalanuvchi birlashtirilgan algoritmlar;

  • taqribiy yechimlarga erishish uchun aniq usullarning elementlaridan foydalanuvchi algoritmlar;

  • "tarmoqlar va chegaralar" kabi birlashtirilgan algoritmlar, katta o'lchamdagi masalalarni hal qilish algoritmlari.



Download 0,6 Mb.

Do'stlaringiz bilan baham:
  1   2   3   4   5   6




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish