np-to’liq masalalar

PPTX 11 pages 477.1 KB Free download

11 pages

FaylHub.uz

Download via Telegram

Size 477.1 KB

File type PPTX

Pages 11

Updated Dec 2025

Page preview (5 pages)

Scroll down 👇

1 / 11

652-21-guruh talabasi shokarimov murodjonning algoritmlarni loyihalash fanidan tayyorlagan mustaqil ishi 652-21-guruh talabasi shokarimov murodjonning algoritmlarni loyihalash fanidan tayyorlagan mustaqil ishi mavzu: np- to’liq masalalar. hisoblashda yechilmaslik hollari reja: 1. np to’liq masalalar 2. np masalalarini yechish 3.kriptografik hujumlar 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. ushbu sinf ichida np-to'liq masalalarga alohida e’tibor beriladi. ushbu masalalarni hal qilish uchun polynomial algoritmlar hali topilmagan. ammo bu sinfdagi barcha masalalarni bir-biriga keltirish mumkin. ya'ni, agar np to’liq masalalarning qandaydir birontasini polynomial vaqt ichida hal qilish mumkin bo'lsa, bu ushbu sinfdagi barcha boshqa masalalarpolinomial vaqtda samarali hal qilinishini anglatadi. bugungi kunga qadar, ko'pchilik mutaxassislar …

2 / 11

bunday yo'llar sifatida quyidagilarni qayd etish mumkin: evristik (yaqinlashgan) yechimlarni topish, qidiruv algoritmlarini takomillashtirish, masalalarning o'lchamlariga eksponential darajada bog'liq bo'lgan jadvallardan foydalanuvchi dinamik dasturlash. yangi masalaga duch kelinganda, birinchi navbatda savol tug'ilishi tabiiy: "ko'rib chiqilayotgan masalani polinomial algoritm yordamida hal qilsa bo'ladimi?". agar ushbu savolga javob ijobiy bo'lib chiqsa, unda np-to'liqlik nazariyasi nuqtai nazaridan muammo haqida hech narsa deyish mumkin emas. keyingi harakatlarimizni iloji boricha eng samarali polinomial algoritmlarni topishga jamlashimiz mumkin. np-to'liq masalani hal qilishning maqbul algoritmini topish muammosini hal qilishda ikkita toifadagi yondoshuv mavjuddir. birinchi guruh qidiruv hajmini minimallashtirishga qaratilgan yondoshuvni o'z ichiga oladi, ammo ayni paytda eksponentsial vaqt sarf qilinishining muqarrarligi tan olinadi. ketma-ket tanlab olish usuli uchun eng ko’p ishlatiladigan usullar qatoriga “tarmoqlar va chegaralar” usuli yoki "noaniq tanlab olish" usuliga asoslangan usullar kiradi. ikkinchi toifaga tegishli yondashuvlar faqat optimallashtirish masalalariga nisbatan qo'llaniladi (ammo bu juda kuchli cheklov emas, chunki amalda yuzaga keladigan juda ko'p masalalar …

3 / 11

asi shteyner muammosi grafni bo'yash muammosi graf cho’qqisini qoplash masalasi to’plamni qoplash masalasi graf cho’qqilarining mustaqil to’plamlari masalasi saper o’yini tetris o’yini 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. 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. 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 - …

4 / 11

5 / 11

Want to read more?

Download all 11 pages for free via Telegram.

Download full file

About "np-to’liq masalalar"

652-21-guruh talabasi shokarimov murodjonning algoritmlarni loyihalash fanidan tayyorlagan mustaqil ishi 652-21-guruh talabasi shokarimov murodjonning algoritmlarni loyihalash fanidan tayyorlagan mustaqil ishi mavzu: np- to’liq masalalar. hisoblashda yechilmaslik hollari reja: 1. np to’liq masalalar 2. np masalalarini yechish 3.kriptografik hujumlar 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 tekshiri...

This file contains 11 pages in PPTX format (477.1 KB). To download "np-to’liq masalalar", click the Telegram button on the left.

Tags: np-to’liq masalalar PPTX 11 pages Free download Telegram