Samarqand davlat univesiteti raqamli tehnologiyalar fakulteti amaliy matematika yo

O’ZBEKISTON RESPUBLIKASI
OLIY VA O’RTA MAXSUS TA’LIM VAZIRLIGI
SAMARQAND DAVLAT UNIVESITETI
RAQAMLI TEHNOLOGIYALAR FAKULTETI
AMALIY MATEMATIKA YO`NALISHI
1-KURS TALABASI _________________ ________________NING
Np-to`liq algoritmlar.Pyukzakka joylashtirish.Grafni bo`yash. Algoritmini loyihalash va tahlil qilish mavzusida
Kurs ishi

SAMARQAND 2021-YIL

Mavzu: Np-to`liq algoritmlar.Pyukzakka joylashtirish.Grafni bo`yash. Algoritmini loyihalash va tahlil qilish.

KIRISH:
I-Bob. Np-to`liq algoritmlar . Pyukzakka joylashtirish.
1.1 P va NP muammosi
1.2 Muammo NP-tugaganligini isbotlash
1.3 NP-to‘liqlik masalasining kuchlilik tomoni
II-Bob. Grafni bo`yash. Algoritmini loyihalash va tahlil qilish.
2.1 Graflarni bo‘yash
2.2. Graf – bu tugunlar va qirralar (tugunlar juftligini birlashtiruvchi) to’plami.
2.3. Agoritmlarni tahlil qilish
Xulosa
Foydalanilgan adabiyotlar ro`yxati

I-Bob. Np-to`liq algoritmlar

Har bir informatika talabasi P va NP muammolari haqida eshitishi kerak. Aytish mumkinki, bu kompyuter fanidagi eng mashhur echimsiz muammo. Clay Matematika Instituti tomonidan tanlangan 7 ming yillik mukofot muammosidan biri, birinchi to'g'ri echim uchun 1 million dollar mukofotni olib yurish va hozir ham ochiq. P = NP muammosini isbotlash yoki echish informatika, matematika, kriptografiya, AI, multimedia ishlov berish, iqtisodiyot va boshqa sohalarda chuqur ta'sir ko'rsatishi mumkin. Ushbu muammo noaniq tarzda aytilishi mumkin
"Kompyuter tomonidan tezda tekshirilishi mumkin bo'lgan har qanday muammoni kompyuter ham tezda hal qiladimi?".
Garchi bu masalaning mavjudligi 1950-yillarda Jon Nesh va Kurt Godel tomonidan muhokama qilingan bo'lsa-da, ushbu muammoni 1971 yilda Stefan Kuk o'zining mashhur "Teoremalarni tayyorlash protseduralarining murakkabligi" nomli maqolasida rasmiy ravishda kiritgan. Rasmiy bayonotga va muammoni tushuntirishga sho'ng'ishdan oldin, avval mavzu bilan bog'liq ba'zi ta'riflarni ko'rib chiqamiz.
Tegishli atamalar va ta'riflar: -
Yuqoridagi noaniq bayonotda ishlatiladigan kompyuter so'zi Deterministik Turing Machine (DTM) ga tegishli. Oddiy so'z bilan aytganda, bu faqat bitta keyingi bosqichga o'tishni tanlashi mumkin bo'lgan mashina. Dallanmagan mashina [3]. Har bir mavjud kompyuter shunday ishlaydi.
Polinom - ba'zi kuchlarga va ularning koeffitsientlariga ko'tarilgan o'zgaruvchilardan tashkil topgan ibora. Masalan, ax² + bx + c shaklidagi ikkinchi darajali ko'paytma. Algoritm vaqt murakkabligi - kirishning uzunligi funktsiyasi sifatida bajarilishi uchun algoritm olgan vaqt. Katta O belgi yordamida umumiy ifodalanadi. Masalan, 2n o'lchamdagi barcha elementlarni birma-bir bosib chiqarish uchun algoritm yozsak, uning vaqt murakkabligi O (n) bo'ladi.
Polinomial vaqt murakkabligi - algoritmning vaqt murakkabligi n ^ {O (1)}
P = Deterministik Turing mashinasi tomonidan ko'paytirilgan vaqt ichida echiladigan muammolar to'plami.
NP = noaniq bo'lmagan polinomik vaqt ichida yechilishi mumkin bo'lgan echimlar muammolarining to'plami (javob ha yoki yo'q) i.e ko'p bo'lmagan vaqt ichida noaniqsiz Turing Machine [4] tomonidan hal qilinishi mumkin.
Nondeterministic Turing Machine (NTM) - dallanadigan mashina. Agar hisoblashning keyingi bosqichi uchun ko'plab imkoniyatlar mavjud bo'lsa, ushbu mashina ularning barchasini bir vaqtning o'zida o'chirib qo'yishi mumkin. NTM-lar O (1) vaqtda ko'p variantlardan to'g'ri variantni taxmin qilishga qodir.
NPga alternativ ta'rif bu mumkin bo'lgan echim taqdim etilsa, DTM polinomik vaqt ichida uning to'g'riligini tekshirishga imkon beradigan qarorlar to'plamidir. Shuni ta'kidlash kerakki, barcha P muammolar NP ga ham tegishli, chunki agar muammo
DTM tomonidan ko'p martali hal qilinsa, mumkin bo'lgan echimni tekshirish hal qilishdan osonroq bo'ladi. Shunday qilib, DTM ham ko'plik vaqt ichida ham tekshirishi mumkin edi. Shunday qilib, arzimas, P ⊆ NP i.e P NP ning pastki qismi.
Bugungi kunda mavjud bo'lgan barcha kompyuterlar DTM va NTM fikrlash tajribalarida ishlatiladigan sof nazariy kompyuter ekanligini bilish ham muhimdir. Professor Erik Demain aytganidek [1].
"Demak, bu (NTM) ancha kuchli model. Albatta, bunday ishlaydigan kompyuterlar yo'q, afsuski, men ko'proq qiziqayapman ”.
Ko'proq atamalar va ta'riflar: -
NP-qiyin - agar X ∈ NP X-ga tushadigan bo'lsa, X muammosi kamida NPda hal qilinadi, masalan NP-ning har bir muammosini hal qilish qiyin (agar P! = NP bo'lsa, unda X P ga tegishli bo'lmaydi).
Reduksiya - A muammoni kiritishlarni ko'paytma vaqt algoritmidan foydalanib, B muammosining ekvivalent kirishiga aylantirish jarayoni. Ekvivalent degani, A va B muammolari kirish va o'zgartirilgan kirish uchun bir xil javobni (Ha yoki Yo'q) berishi kerak. A dan B gacha qisqartirish algoritmining mavjudligi quyidagilarni nazarda tutadi:
1. Agar B ∈ P bo'lsa, u holda A ∈ P (ko'paytmali vaqt ichida A dan B gacha qisqartirishingiz mumkin va B polinomik vaqt ichida echishingiz mumkin. Buni birlashtirish A uchun ko'p vaqtli algoritmni beradi)
2. Agar B ∈ NP bo'lsa, unda A ∈ NP
3. Agar A NP-qattiq bo'lsa, B - NP-qattiq. A ko'paytirilgan vaqt ichida B ga kamayishi mumkin va agar B NP-qiyin bo'lmasa, u B B NP-NP-qiyin va bu A ∈ NP-NP-qattiq, bu farazga zid (A-NP-qiyin) degan ma'noni anglatadi.
NP-to'liqligi - agar X ∈ NP va X bo'lsa, NP-qiyin bo'lsa, X muammo NP-tugallanadi.
P va NP muammosi
Har bir informatika talabasi P va NP muammolari haqida eshitishi kerak. Aytish mumkinki, bu kompyuter fanidagi eng mashhur echimsiz muammo. Clay Matematika Instituti tomonidan tanlangan 7 ming yillik mukofot muammosidan biri, birinchi to'g'ri echim uchun 1 million dollar mukofotni olib yurish va hozir ham ochiq. P = NP muammosini isbotlash yoki echish informatika, matematika, kriptografiya, AI, multimedia ishlov berish, iqtisodiyot va boshqa sohalarda chuqur ta'sir ko'rsatishi mumkin. Ushbu muammo noaniq tarzda aytilishi mumkin
"Kompyuter tomonidan tezda tekshirilishi mumkin bo'lgan har qanday muammoni kompyuter ham tezda hal qiladimi?".
Garchi bu masalaning mavjudligi 1950-yillarda Jon Nesh va Kurt Godel tomonidan muhokama qilingan bo'lsa-da, ushbu muammoni 1971 yilda Stefan Kuk o'zining mashhur "Teoremalarni tayyorlash protseduralarining murakkabligi" nomli maqolasida rasmiy ravishda kiritgan. Rasmiy bayonotga va muammoni tushuntirishga sho'ng'ishdan oldin, avval mavzu bilan bog'liq ba'zi ta'riflarni ko'rib chiqamiz.

Tegishli atamalar va ta'riflar: -

Yuqoridagi noaniq bayonotda ishlatiladigan kompyuter so'zi Deterministik Turing Machine (DTM) ga tegishli. Oddiy so'z bilan aytganda, bu faqat bitta keyingi bosqichga o'tishni tanlashi mumkin bo'lgan mashina. Dallanmagan mashina [3]. Har bir mavjud kompyuter shunday ishlaydi.

Polinom - ba'zi kuchlarga va ularning koeffitsientlariga ko'tarilgan o'zgaruvchilardan tashkil topgan ibora. Masalan, ax² + bx + c shaklidagi ikkinchi darajali ko'paytma.

Algoritm vaqt murakkabligi - kirishning uzunligi funktsiyasi sifatida bajarilishi uchun algoritm olgan vaqt. Katta O belgi yordamida umumiy ifodalanadi. Masalan, 2n o'lchamdagi barcha elementlarni birma-bir bosib chiqarish uchun algoritm yozsak, uning vaqt murakkabligi O (n) bo'ladi.

Polinomial vaqt murakkabligi - algoritmning vaqt murakkabligi n ^ {O (1)}

P = Deterministik Turing mashinasi tomonidan ko'paytirilgan vaqt ichida echiladigan muammolar to'plami.
NP = noaniq bo'lmagan polinomik vaqt ichida yechilishi mumkin bo'lgan echimlar muammolarining to'plami (javob ha yoki yo'q) i.e ko'p bo'lmagan vaqt ichida noaniqsiz Turing Machine [4] tomonidan hal qilinishi mumkin.
Nondeterministic Turing Machine (NTM) - dallanadigan mashina. Agar hisoblashning keyingi bosqichi uchun ko'plab imkoniyatlar mavjud bo'lsa, ushbu mashina ularning barchasini bir vaqtning o'zida o'chirib qo'yishi mumkin. NTM-lar O (1) vaqtda ko'p variantlardan to'g'ri variantni taxmin qilishga qodir.

NPga alternativ ta'rif bu mumkin bo'lgan echim taqdim etilsa, DTM polinomik vaqt ichida uning to'g'riligini tekshirishga imkon beradigan qarorlar to'plamidir. Shuni ta'kidlash kerakki, barcha P muammolar NP ga ham tegishli, chunki agar muammo DTM tomonidan ko'p martali hal qilinsa, mumkin bo'lgan echimni tekshirish hal qilishdan osonroq bo'ladi. Shunday qilib, DTM ham ko'plik vaqt ichida ham tekshirishi mumkin edi. Shunday qilib, arzimas, P ⊆ NP i.e P NP ning pastki qismi.

Bugungi kunda mavjud bo'lgan barcha kompyuterlar DTM va NTM fikrlash tajribalarida ishlatiladigan sof nazariy kompyuter ekanligini bilish ham muhimdir. Professor Erik Demain aytganidek [1].
"Demak, bu (NTM) ancha kuchli model. Albatta, bunday ishlaydigan kompyuterlar yo'q, afsuski, men ko'proq qiziqayapman ”.
Ko'proq atamalar va ta'riflar: -
NP-qiyin - agar X ∈ NP X-ga tushadigan bo'lsa, X muammosi kamida NPda hal qilinadi, masalan NP-ning har bir muammosini hal qilish qiyin (agar P! = NP bo'lsa, unda X P ga tegishli bo'lmaydi).
Reduksiya - A muammoni kiritishlarni ko'paytma vaqt algoritmidan foydalanib, B muammosining ekvivalent kirishiga aylantirish jarayoni. Ekvivalent degani, A va B muammolari kirish va o'zgartirilgan kirish uchun bir xil javobni (Ha yoki Yo'q) berishi kerak. A dan B gacha qisqartirish algoritmining mavjudligi quyidagilarni nazarda tutadi:

1. Agar B ∈ P bo'lsa, u holda A ∈ P (ko'paytmali vaqt ichida A dan B gacha qisqartirishingiz mumkin va B polinomik vaqt ichida echishingiz mumkin. Buni birlashtirish A uchun ko'p vaqtli algoritmni beradi)

2. Agar B ∈ NP bo'lsa, unda A ∈ NP
3. Agar A NP-qattiq bo'lsa, B - NP-qattiq. A ko'paytirilgan vaqt ichida B ga kamayishi mumkin va agar B NP-qiyin bo'lmasa, u B B NP-NP-qiyin va bu A ∈ NP-NP-qattiq, bu farazga zid (A-NP-qiyin) degan ma'noni anglatadi.

NP-to'liqligi - agar X ∈ NP va X bo'lsa, NP-qiyin bo'lsa, X muammo NP-tugallanadi.

Muammo NP-tugaganligini isbotlash

Muammoning to'liqligini isbotlash 2 bosqichni o'z ichiga oladi. Avval biz muammo NPga tegishli ekanligini ko'rsatishimiz kerak va keyin biz buni NP-qiyinligini ko'rsatishimiz kerak. Bosqichlarni quyidagicha izohlash mumkin:

1-qadam - X ∈ NP ni ko'rsatish. X uchun netereterministik algoritmni toping. Ammo amaliy usul, agar potentsial echim taqdim etilsa, X uchun ko'paytmali vaqt tekshiruvini o'tkazishdir.
2-qadam - X-ni ko'rsatish qiyin emas. Ma'lum NP-muammoni X-ga qisqartirish. Demak, biz ko'rgan 3-rasm orqali X bu NP-qiyin ekanligini anglatadi.

Bu masala qisqa P va NP murakkab sinfi uchun qo’llanilishi mumkinligi tengmi?

P-sinfi deb kompyuter “tezda”(“Birzumda”) yechimi mumkin bo’lgan masalalar majmuiga aytiladi. Bunga arifmetik amallarning asosi (negizi) ro’yhatlarni saralash, jadval bo’yicha ma’lumotlarni tezda tekshirish qilaylik sizda bo’lgan izlash kiradi.
NP-sinfiga javobning to’g’riligini tezda tekshirish mumkin bo’lgan masala kiradi. Masalan: faraz qilaylik sizda qiymati 2,3,5,6 va 7 so’mlik tangalardan bittadan bor va siz narxi 21 so’m bo’lgan harid uchun qaytimsiz to’lashni hoxlamoqdasiz. Ulardan yig’indisi 21 so’m bo’lgan tangalar tangalarni yig’ib olish mumkinmi?
Bu masalaga javob olish uchun har hil variantni tanlash lozim, agar masala yechimini yo’qligini isbotlasmoqchi bo’lsak, umuman olganda barcha bo’lishi mumkin bo’lgan variantlardni tanlash lozim. Agar tangalar sonini bir necha usulda ko’paytirsak yechish mutlaqo nomuvofiq ko’rinishda bo’ladi. Bunda natijani oson tekshirish uchun shunchaki barcha “ming yillik masalasi” ning mohiyati quyidagicha (bunday) ifodalanadi (ta’riflanadi): P va NP sinflari tengmi? Agar masala yecvhimining to’g’riligini tekshirish oson bo’lsa, masalani o’zini yechish ham oson bo’lishi mumkinmi?

Ko’pchilik mutaxassislar javobning yo’qligi (salbiy)ga amindirlar, lekin buni hozircha hech kim isbotlay olgani yo’q agar P=NP bo’lib qolsa, unda insoniyatni kriptografiyaga (sirli belgi va ishoralar bilan yozish tizimi) keskin burilish ko’taradi.

NP-to’liqlik masalasi

Amaliy nuqtai nazardan qiziq bo‘lgan vazifalarning aksariyati, polinomial' (polinomial' vaqt mobaynida ishlovchi) algoritmlar. Ya'ni, n uzunlikdagi kirishda algoritmning ishlash vaqti doimiy k (kirish uzunligidan mustaqil) uchun O(nk) dan oshmaydi. Har bir masalada ushbu xususiyatni qondiradigan yechim algoritmi mavjud emas. Ba'zi masalalarni umuman biron bir algoritm yordamida hal qilib bo‘lmaydi. Bunday masalaning klassik misoli bu “to‘xtash muammosi” (berilgan dastur berilgan kirishda to‘xtashini bilish). Bundan tashqari, ularni hal qiladigan algoritm mavjud bo‘lgan masalalar mavjud, har qanday bunday algoritm uzoq vaqt ishlaydi – uning ishlash vaqti har qanday fiksirlangan k soni uchun O(nk) bo‘la olmadi.

Agar biz amaliy algoritmlar va faqat nazariy qiziqish algoritmlari o‘rtasida qo‘pol, ammo rasmiy chegara chizishni istasak, unda ko‘plikli vaqt ichida ishlaydigan algoritmlar sinfi birinchi o‘rinda turadi. NP -to‘liq deb nomlangan masalalar sinfini ko‘rib chiqamiz. Ushbu masalalar uchun hech qanday polinomial' algoritmlar topilmagan, ammo bunday algoritmlar mavjud emasligi isbotlanmadi. NP bilan bog‘liq muammolarni o‘rganish “P = NP” deb nomlangan savol bilan bog‘liq. Bu savol 1971 yilda berilgan va hozirda hisoblash nazariyasida eng qiyin masalalardan biri hisoblanadi.
Nima uchun dasturchi NP – tugallangan masalalar haqida bilishi kerak? Agar biron bir NP – to‘liqlik uchun uning to‘liqligini isbotlash mumkin bo‘lsa, uni deyarlihal qilib bo‘lmaydi deb hisoblash uchun asos bor. Bunday holda, uni aniq hal qiladigan tezkor algoritmni qidirishni davom ettirishdan ko‘ra, taxminiy algoritmni tuzishga vaqt sarflash yaxshiroqdir.
Yuqorida aytib o‘tilganidek, ko‘p jihatdan hal qilinadigan (polinomial) masalalar konsepsiyasi amalda yechilishi mumkin bo‘lgan masalalar g‘oyasini takomillashtirish hisoblanadi. Ushbu kelishuvni nima tushuntiradi? Birinchidan, amalda ishlatiladigan ko‘paytirilgan algoritmlar, odatda juda tez ishlaydi. Ikkinchidan, polinomial algoritmlar sinfini ko‘rib chiqish, bu sinfning hajmi ma'lum bir hisoblash modelini tanlashdan deyarli mustaqil bo‘lishidir. Masalan, tasodifiy tasodifiy kirish mashinasida (RAM) ko‘paytirilgan vaqt ichida yechilishi mumkin bo‘lgan masalalar sinfi T'yuring mashinalarida polinomal yechiladigan masalalar sinfiga to‘g‘ri keladi. Sinf parallel hisoblash modeli uchun bir xil bo‘ladi, prosessorlar soni, kirish uzunligi polinomi bilan cheklangan. Uchinchidan, polinomal yechiladigan masalalar sinfi tabiiy yopiqlik xususiyatlariga ega. Masalan, ikkita algoritmning tarkibikompozisiyasi ham polinomial vaqtli ishlaydi. Buning sababi, ko‘pxadlarning yig‘indisi, ko‘paytmasi va kompozisiyasi ko‘pxadrdir.
Quyida hisoblash masalasining abstrakt modelini keltirilgan. Buni abstrakt masala deb nomlaymiz, Q – ikkita to‘plam elementlari orasidagi ixtiyoriy binar munosabat: I – shartlar to‘plami va S – yechimlar to‘plami. Masalan, G=(V,E) yo‘naltirilmagan grafning berilgan ikkita uchlari orasidagi eng qisqa yo‘lni topish masalasida, shart (element I) uch element, graf va ikkita qirradan iborat va yechim (S element) – bu grafda kerakli yo‘lni tashkil etuvchi vertikallarning ketma-ketligi.
NP to‘liqligi nazariyasida faqat hal qilish masalalari ko‘rib chiqiladi – muayyan savolga “ha” yoki “yo‘q” deb javob berish kerak bo‘lgan masalalar. Rasman, I to‘plam shartlarini {0,1} to‘plamga to‘g‘ri keladigan funksiya sifatida ko‘rib chiqilishi mumkin. Masalan, G=(V,E) grafdagi eng qisqa yo‘lni topish masalasi bilan berilgan G=(V,E) graf yordamida ikkita tugun u, v∈V va natural k butun sonlar u va v tugunlari orasida undan katta bo‘lmagan hamda G grafda yo‘l bor yoki yo‘qligi masalasini yeching.
Optimallashtirish bilan bog‘liq masalalar bu – muayyan miqdordagi qiymatni maksimal darajada oshirish yoki minimallashtirish kerak bo‘lgan masalalardi. NP – to‘liqlik haqida savol berishdan oldin bunday masalalar, ularni hal qilish masalalariga aylantirilishi kerak. Shunday qilib, masalan, grafdagi eng qisqa yo‘lni topish masalasida optimallashtirish masalasini yechish masalasidan ruxsat berish masalasiga o‘tdik va yo‘l uzunligiga cheklov qo‘shdik. Agar transformasiyadan keyin NP – to‘liq masalasi yuzaga kelsa, unda asl muammoning qiyinligi ham belgilanadi. Ma'lumotlar taqdimoti
Kirish ma'lumotlarini (ya'ni I to‘plamning elementi) algoritmga kiritishdan oldin ularning qanday qilib “kompyuterga qulay” tarzda taqdim etilishi to‘g‘risida kelishib olish kerak. Dastlabki ma'lumotlar bitlar ketma-ketligi bilan kodlangan deb qabul qilamiz. Formal aytganda, S to‘plamining elementlarini ifodalash bu S dan e ni bitli satrlar to‘plamlariga tushishidir. Masalan, (0, 1, 2, 3,...) – butun sonlarni, odatda (0, 1, 10, 11, 100, ...) – bitli satrlar bilan ifodalanadi.
Taqdim qilingan ma'lumotlarni joylashtirb, mavhum masalani satrli ma'lumotga aylantiramiz, bu satirli ma'lumot uchun kirish ma'lumotlari, masalaning dastlabki ma'lumotlarini aks ettiruvchi bitli satir bo‘ladi. Kirish ma'lumotlari (bitli satr) n – uzunlikda bo‘lganida, algoritmning ishlash vaqti O(T(n)) – bo‘lsa, algoritm satirli masalani O(T(n)) vaqtda yechadi desak bo‘ladi. Agar k konstanta va O(T(n)) vaqt ichida bu masalani yechadigan algoritm mavjud bo‘lsa, satirli masala polinomial' deb ataladi. Murakkablik P sinfi – bu barcha satirli masalalar bo‘lib, polonomia' vaqt ichida yechilishi mumkin, ya'ni, O(nk) vaqt ichida yechilishi mumkin, bu yerda k kirishga bog‘liq bo‘lmaydi.
Polinomial abstrakt masalasining konsepsiyasini aniqlashni istagan holda, biz turli xil ma'lumotlarni taqdim etish mumkinligiga duch kelamiz. Xar bir taqdim qilingan e to‘plam uchun, I kirishlari bo‘lgan Q abstrakt masalaning satirli masalasini olamiz.
Biroq, amalda (asosi 1 bo‘lgan raqamli tizim kabi “qimmat” vakillik usullarini istisno qilsak), tabiiy vakillik usullari odatda ekvivalentdir, chunki ularni bir-biriga ko‘p jihatdan aylantirish mumkin. A polinomial algoritmi mavjud bo‘lsa, f:{0,1}*→{0,1}* funksiyasi polinimial vaqt ichida hisoblab chiqiladi, u har qanday x∈ {0,1}* uchun f(x) natijani beradi.
Ixtiyoriy abstrakt masala uchun I to‘plami sharitlarini ko‘rib chiqamiz. I to‘plamning е1 va е2 elementlari polinomial' bog‘langan deyiladi, agar polinomial' vaqtda hisoblash mumkin bo‘lgan ikkita f12(e1(i)) = e2(i) va f21(e2(i)) = e1(i), i ∈ I funsiyalar mavjud bo‘lsa. Bunday hollarda, polinomial' bog‘langan ikkita elementdan qaysi birini tanlash muhim emas.
P, NP, NP-complete (NP-to‘liklik masalalari) sinflar orasidagi munosabatlar, NP-hard (NP-murakkab masalalar), P≠NP va P=NP bo‘lgan xollarda.
NP- tuliklik masalasi — algoritmlar nazariyasida NP – sinfdagi «ha» yoki «yo‘k» javobli masalani shu sinfdagi boshka masalaga polinomial' vakt oralgida moslashtirish mumkin (yani, boshlangich ma'lumotlar xajmiga boglanganlik darajasi ma'lum polinimdan katta bulmagan amallar yordamida bajariladi).
Shunday qilib, NP -to‘liq masalalar, ma'lum ma'noda, NP sinfidagi “tipik” masalalar to‘plamini shakllantiradi: agar ularning ba'zilari uchun "tezkor" yechim algoritmi topilsa, NP sinfidagi har qanday boshqa masalani xuddi shu tarzda hal qilish mumkin.
Formal' ta'rif
Alifbo deganda har qanday cheklangan belgilar to‘plami tushuniladi (masalan, {0, 1} yoki {a, b, c}). Ixtiyoriy ∑ alifbosidan tuzilgan barcha so‘zlar to‘plami (yozilgan satirlar, ushbu alifboning belgilaridan tashkil topadi) ∑* bilan belgilanadi.
∑ alfavit yordamida yaratilgan ixtiyoriy L tili bu ∑^* to‘plamning L to‘plam ostisi, ya'ni L⸦∑^*.

L uchun tanib olish vazifasi berilgan so‘z L tiliga tegishli yoki yo‘qligini aniqlashdir.

∑ alifbo ustida va - ikkita til bo‘lsin. tiliga (Karp bo‘yicha) L2 tiliga qisqartirish deyiladi, agar funksiyasi mavjud bo‘lsa, bu funksiyani polinomial' vaqt bilan hisoblash mumkin bo‘lsa, quyidagi xususiyatga yega: : x ∈ L1, , agar va faqat agar . Karp bo‘yicha qisqartirish L1≤pL2 bilan belgilanadi.
Agar NP-dan biron bir til unga qisqartirilsa, tili NP-to‘liq deb nomlanadi. Til NP-mukammal deb nomlanadi, agar u NP-qiyin bo‘lsa va shu bilan birga o‘zi NP sinfida bo‘lsa.
A masala B masalasiga qisqartirilganligi, A masala B masalasidan ko‘ra “murakkabroq” ekanligini anglatadi (chunki agar biz B masalani yechilishi, A masalanini ham yechilishini bildiradi). Shunday qilib, NP bilan bog‘liq qiyinchiliklar sinfga NP bilan bog‘liq masalalar va ular uchun "ancha qiyin" bo‘lgan masalalar kiradi (ya'ni NP bilan bog‘liq masalalarni kamaytirish mumkin bo‘lgan masalalar). NP sinf NP to‘liq masalalarni va ulardan "osonroq" bo‘lgan masalalarni o‘z ichiga oladi (ya'ni, NP-to‘liq masalalarga qisqartirishgan masalalar). Ta'rifdan shunday xulosa kelib chiqadiki, agar NP-to‘liq masalasi polinomial' vaqtda hal qiladigan algoritm topilsa, unda barcha NP-to‘liq masalalar P sinfga joylashtiriladi, ya'ni ular polinomial' vaqtda yechiladi.

NP-to‘liqlik masalasining kuchlilik tomoni

Agar masalaning qisim masalalari mavjud bo‘lsa u kuchli NP-to‘liq masala deyiladi, bunda: Masalaning raqamli parametrlari mavjud bo‘lmasa (ya'ni, bu masalada uchraydigan kattaliklarning maksimal' qiymati polinom uzunligi bilan yuqoridan chegaralangan).
Masalaning raqamli parametrlari mavjud bo‘lmasa (ya'ni, bu masalada uchraydigan kattaliklarning maksimal' qiymati polinom uzunligi bilan yuqoridan chegaralangan).
II-Bob. Grafni bo`yash. Algoritmini loyihalash va tahlil qilish.
2.1 Graflarni bo‘yash
Grafni bo‘yash. Grafning xromatik soni. Kyonig teoremasi (grafning bixromatikligi). Planar grafni to‘g‘ri bo‘yash hadidagi teorema. Graf xromatik sonini topishning evristik algoritmi.
Ta’rif. Aytaylik  garf va ranglar toplami deb ataluvchi biror bir to‘plam berilgan bo‘lsin. Har qanday akslantirishga G grafni bo‘yash deyiladi .Bo‘yash to‘g‘ri
deyiladi, agar qo‘shni uchlar turli xil ranglarg bo‘yalgan bo‘lsa, ya’ni
G grafni to‘g‘ri bo‘yashni qurish uchun zarur bo‘lgan, minimal ranglar soniga xromatik son deyiladi va  kabi belgilanadi.
Ikki ulushli graf uchlar to‘plamini ikkita to‘plam ostiga bo‘lish mumkin va bu to‘plamdagi elementlar bir biriga qo‘shni bo‘lmaydi, u holda grafning bunday uchlari ikki xil rangda to‘g‘ri bo‘yash mumkin, ya’ni ikki ulushli graf xromatik soni 2 ga teng.
Xromatik soni 2 ga teng bo‘lgan graf, bixromatik deyiladi.

Kyonig teoremasi. Graf bixromatik bo‘lishi uchun, toq uzunlikdagi sikllari bo‘lmasligi zarur va yetarli.

Umumiy holda grafning xromatik sonini aniqlash trivial savol emas. Lekin grafning xromatik soni bahosiga nisbatan birqancha faktlar ma’lum.

Teorema. Agar G=(V,E) graf barcha uchlari darajalari k dan katta bo‘lmasa, u holda grafni to‘g‘ri bo‘yashni qurish uchun (k+1) xil rang yetarli bo‘ladi, ya’ni .

Shuni ta’kidlab o‘tish kerakki, xromatik sonning ushbu bahosi umumiy holda aniqdir, ya’ni shunday graflar mavjudki, ularning uchlarining darajalari k dan oshmaydi, xromatik soni k+1 ga teng. Masalan, to‘liq grafning uchlari darajalari ga teng, xromatik soni esa .

Grafning xromatik sonini baholash masalasida planar graflar muhim o‘rin tutadi. 19-asr oxirida ixtiyoriy planar grafning xromatik soni 5 dan oshmasligi isbotlandi. Lekin, xromatik soni 5 ga teng bo‘lgan planar grafga misol bo‘lmagan. Bu esa, planar grafni 4 xil bo‘yoq bilan to‘g‘ri bo‘yash mumkinligini taxmin qilishga asos berardi. Ushbu masala to‘rt xil bo‘yoq masalasi deb yuritila boshlandi. 1976 yilda amerikalik olimlar Kennet Appel va Volfgan Xakenlar maxsus kompyuter dasturlari orqali 4 xil bo‘yoq haqidagi teoremani isbotlashdi.

Теоrema (to‘rt xil bo‘yoq haqidagi teorema). Ixtiyoriy G planar graf to‘rttadan ortiq bo‘lmagan ranglar bilan tog‘ri bo‘yalishi mumkin, ya’ni .

Graf xromatik sonini baholashning bir qancha evristik algoritmlari mavjud. Xasis algaritm deb nomlanuvchi algoritmni keltirib o‘tamiz. Ranglarni  bilan belgilaymiz va ni -rang deb ataymiz.
Xasis algoritm quyidagilardan iborat:
(a) uchlarni biror bir tartibda joylashtiriladi: ;
(b) uchni rangga bo‘yaladi;
(c) agar uchlar bo‘yalgan bo‘lsa, u holda uchni bu uch bilan qo‘shni bo‘lgan uchlarni bo‘yash uchun ishlatilmagan ranglar ichida eng kichik j-nomerli rangga bo‘yaladi.
Xasis algoritmdan foydalanilgan holda olingan bo‘yashning optimalligi, uchlarni joylashtirishni tanlab olish tartibiga bog‘liq. Har doim uchlarni joylashtirishning shunday tartibi mavjudki, xasis algoritmni optimal  bo‘yashlar soniga olib keladi. Shuni ta’kidlab o‘tish kerakki, xasis algoritm yordamida grafni bo‘yashda, d darajali uchni bo‘yashdagi erishilmagan ranglar soni d sonidan ortmaydi, demak nomerli rang ishlatilishi mumkin. Shuning uchun ham quyidagicha baho o‘rinli.

Теоrema. Agar G graf uchlarining maksimal darajasi d ga teng bo‘lsa, u holda xasis algoritm yordamida graf uchlarini dan ortiq bo‘lmagan rangga bo‘yash mumkin, ya’ni .

2.2. Graf – bu tugunlar va qirralar (tugunlar juftligini birlashtiruvchi) to’plami.

Graf cho’qqilarini bo’yash algoritmlari. Avvalo Graf ozi nima Grafning cho’qisi nima shuni

bilib olishimiz kerak bo’ladi.
Graf nima ?
Graf – bu tugunlar va qirralar (tugunlar juftligini birlashtiruvchi) to’plamidan iborat bo’lgan abstrakt matematik ob’ektdir.
(V, E) sonlar juftligiga graf deyiladi, bu yerda V – iхtiyoriy bo`sh bo`lmagan to`plam, E esa V(2) ning qism to`plami (E V(2)), bunda V(2) V to`plam elementlarining tartiblanmagan juftliklari to`plami. V to`plam elementlari grafning uchlari deyiladi, E to`plam elementlari esa grafning qirralarideyiladi. Agar V chekli bo`lsa, graf chekli deyiladi, aks holda cheksiz graf deyiladi.
Grafning cho’qisi deb esa quyidagi holatga aytiladi. To`plamlarning bir-biri bilan bog`lanishini tasvirlashimizda graflardan foydalanamiz. Ko`p hollarda bo`sh bo`lmagan X to`plamning elementlari orasidagi o`zaro munosabati, ya’ni Y to`plam elementlarini X to`plamning o`ziga akslantirishni geometrik shaklda ifodalash qulay bo`lib qoladi. Bunday geometrik shakllar graflar deyiladi. Agarda bunga ilmiy ta’rif bersak quyidagi jumlaga ega bo`lamiz: Ikkitа tugunlаr (cho`qqi) vа yo`llаr (qovurg`alаr) to`plаmlаrining bir-biri bilаn bоg`lаnishigа grаflаr dеyilаdi. Uni G(X;U) ko`rinishidа ifоdаlаsh mumkin. Bu еrdа X- tugunlаr to`plаmi, U-yo`llаr to`plаmi.

Mаsаlаn: U1, U2- tugunlаr (cho`qqilаr); L-yo`l

Grafning cho’qqilari ko’p hollarda tugunlar deb yuritiladi. Tugun bu bir nеchtа yo`llаrning bоshlаnishi vа оxiri (tugаshi) bo`lishi mumkin. Tugunlаr sifаtidа elеktr stаnsiyalаrni misоl qilish mumkin.
Quyida Grafning cho’qillari (tugunlari)ni bo’yab o’tish orqali ushbu Grafning uchlari orasidagi eng qisqa masofani qidirish dastuini tuzib chiqamiz :

#include

using namespace std;
int main()

{
int n;

cout<<"Graf uchlari va qirralari sonini kiriting: ";cin>>n;
int a[n][n]={0};
int d[n]={10000};
int v[n]={1};
for(int i=0;i
d[i] = 10000;
v[i] = 1;
for(int j=i+1;j
{
int tmp;
cout<>tmp;
a[i][j]=a[j][i]=tmp;
}
}
for(int i=0;i
{
for(int j=0;j
printf("%5d",a[i][j]);
cout<

}

int minex ;

int min ;

d[0] = 0;

do {

minex = 10000;

min = 10000;

int tmp;

for (int i = 0; i<="" b="">

{

if ((v[i] == 1) && (d[i]

{

min = d[i];

minex = i;

}

}

if (minex != 10000)

{

for (int i = 0; i<="" b="">

{

if (a[minex][i] > 0)

{

tmp = min + a[minex][i];

if (tmp < d[i])

{

d[i] = tmp;

}

}

}

v[minex] = 0;

}

} while (minex < 10000);

cout<<"\nUchigacha bo'lgan qisqa masofalar: \n";

for (int i = 0; i<="" span="">

printf("%5d ", d[i]);

int end = 4;

v[0] = end + 1;

int k = 1;

int weight = d[end];

while (end != 0)

{

for (int i = 0; i<="" b="">

if (a[i][end] != 0)

{

int temp = weight - a[i][end];

if (temp == d[i])

{

weight = temp;

end = i;

v[k] = i + 1;

k++;
}

}

}

cout<<"\nUchigacha neg qisqa yo'l:\n";

for (int i = k - 1; i >= 0; i--)

printf("%3d ", v[i]);

return 0;

}

2.3. Agoritmlarni tahlil qilish

Yilda Kompyuter fanlari, algoritmlarni tahlil qilish ni topish jarayoni hisoblash murakkabligi algoritmlar - vaqt, saqlash yoki boshqa manbalar miqdori ularni ijro eting. Odatda, bu a ni o'z ichiga oladi funktsiya algoritm kiritish uzunligini va uni bajaradigan qadamlar soniga bog'laydigan (uning vaqtning murakkabligi) yoki u foydalanadigan saqlash joylari soni (uning kosmik murakkablik). Algoritm ushbu funktsiya qiymatlari kichik bo'lganda yoki kirish hajmining o'sishiga nisbatan sekin o'sganda samarali bo'ladi deyiladi. Xuddi shu uzunlikdagi turli xil yozuvlar algoritmning xatti-harakatlariga olib kelishi mumkin, shuning uchun eng yaxshi, eng yomon va o'rtacha ish tavsiflarning barchasi amaliy qiziqish uyg'otishi mumkin. Agar boshqacha ko'rsatilmagan bo'lsa, algoritmning ishlashini tavsiflovchi funktsiya odatda yuqori chegara, algoritmga eng yomon holatlardan aniqlandi. "Algoritmlarni tahlil qilish" atamasi tomonidan kiritilgan Donald Knuth.[1] Algoritmni tahlil qilish keng doiraning muhim qismidir hisoblash murakkabligi nazariyasi, bu berilganni hal qiladigan har qanday algoritm uchun zarur bo'lgan manbalar uchun nazariy baholarni beradi hisoblash muammosi. Ushbu taxminlar izlashning oqilona yo'nalishlari to'g'risida tushuncha beradi samarali algoritmlar.
Algoritmlarni nazariy tahlil qilishda ularning murakkabligini asimptotik ma'noda baholash, ya'ni o'zboshimchalik bilan katta kirish uchun murakkablik funktsiyasini baholash odatiy holdir. Big O notation, Katta-omega yozuvlari va Big-teta yozuvi shu maqsadda ishlatiladi. Masalan; misol uchun, ikkilik qidirish qidirilayotgan tartiblangan ro'yxat uzunligining logarifmiga mutanosib bo'lgan bir necha bosqichda yoki O (log (n)) da, so'zma-so'z " logaritmik vaqt". Odatda asimptotik taxminlar har xil bo'lgani uchun ishlatiladi amalga oshirish bir xil algoritm samaradorligi bilan farq qilishi mumkin. Ammo berilgan algoritmni istalgan ikkita "oqilona" amalga oshirish samaradorligi a deb nomlangan doimiy multiplikativ omil bilan bog'liq. yashirin doimiy.
Ba'zida samaradorlikning aniq (asimptotik bo'lmagan) o'lchovlari hisoblab chiqilishi mumkin, ammo ular odatda algoritmni amalga oshirishda ma'lum taxminlarni talab qiladi, deyiladi hisoblash modeli. Hisoblash modeli an nuqtai nazaridan aniqlanishi mumkin mavhum kompyutermasalan, Turing mashinasi, va / yoki ma'lum bir operatsiyalar birlik vaqtida bajarilishini e'lon qilish orqali, masalan, agar biz ikkilik qidiruv qo'llanadigan tartiblangan ro'yxatda n va biz ro'yxatdagi elementni har bir qidirishni birlik vaqtida, so'ngra eng ko'p jurnalda bajarilishi mumkinligiga kafolat beramiz2 n Javobni qaytarish uchun + 1 marta birlik kerak.

Bitta masalani hal qilish uchun turli xil algoritmlarni ko'rib chiqsak, ular qancha hisoblash resurslarini (ishlash vaqti, xotira) talab qilishini tahlil qilish va eng samaralisini tanlash foydalidir. Albatta, biz hisoblashning qaysi turidan foydalanilganligi to'g'risida kelishib olishimiz kerak .. Algoritmning ishlash vaqti bilan biz bajaradigan elementar qadamlar sonini tushunamiz. Aytaylik, psevdokodning bir qatorida belgilangan miqdordagi operatsiyalar talab qilinadi (masalan, ba'zi murakkab harakatlarning og'zaki tavsifi bo'lmasa - masalan, "hamma nuqtalarni x-koordinata bo'yicha saralash"). Qo'ng'iroq qilish (qo'ng'iroq qilish) protsedurasini (ma'lum miqdordagi operatsiyalarni oladi) va uning bajarilishini (bajarilishini) farqlashingiz kerak, ular uzoq davom etishi mumkin. Algoritmning murakkabligi bu vazifaning o'lchamiga qarab talab qilinadigan manbaning kattaligi tartibini (vaqt yoki qo'shimcha xotira) aks ettiradigan qiymatdir. Shunday qilib, biz algoritmning vaqtinchalik T (n) va fazoviy V (n) murakkabligini ajratamiz. Murakkablikni baholashni ko'rib chiqishda biz vaqtinchalik murakkablikdan foydalanamiz. Fazoviy murakkablik ham shunga o'xshash tarzda baholanadi. Baholashning eng oson usuli bu eksperimental usul, ya'ni algoritmni dasturlash va natijada olingan dasturni bir nechta vazifalar bo'yicha bajarish, dasturlarning bajarilish vaqtini baholash. Biroq, bu usul bir qator kamchiliklarga ega. Birinchidan, eksperimental dasturlash, ehtimol qimmat jarayon. Ikkinchidan, shuni yodda tutish kerakki, dasturlarning bajarilish vaqtiga quyidagi omillar ta'sir qiladi:

Dastur algoritmining vaqt murakkabligi;

2. bajariladigan dasturning kompilyatsiya qilingan kodining sifati;
3. Dasturni bajarish uchun ishlatiladigan mashina ko'rsatmalari.
Ikkinchi va uchinchi omillarning mavjudligi algoritmning vaqt murakkabligini o'lchashning tipik birliklaridan foydalanishga imkon bermaydi (soniya, millisekundlar va boshqalar), chunki agar siz turli xil dasturchilar (har bir algoritmni kim dasturlasa) bir xil algoritm uchun har xil baholarni olish mumkin. o'z), turli xil kompilyatorlar va turli xil kompyuterlar. Ko'pincha, algoritmning vaqt murakkabligi kiritish hajmiga bog'liq. Odatda algoritmning vaqt murakkabligi n o'lchamidagi kirish ma'lumotlarini T (n) tartibiga to'g'ri keladi, deyiladi. Amaliyotda T (n) ning aniq qiymatini aniqlash juda qiyin. Shuning uchun ular O-simvolizmidan foydalanib, asimptotik munosabatlarga murojaat qilishadi. Keyinchalik muhokama qilinadigan algoritmning bajarilish vaqtini nazariy jihatdan hisoblaydigan usul mavjud.

Xulosa
Men 1-kusr 104-guruh talabasi Xalilov Dilshod NP-to’liq algoritmlar. Pyukzakka joylashtirish. Grafni bo’yash. Agoritmni loyihalash va tahlil qilish mavzusi bo’yicha o’z fikrimni bildiraman

Algoritm keng maʼnoda faqat kompyuterga oid atama boʻlmay, balki unda berilgan koʻrsatmalarni bajara oluvchi har qanday narsaga oiddir. Algoritmlar kundalik hayotimizda deyarli har doim uchraydi. Algoritmlarni loyihalash va tahlil qilishni o’rganib chiqdim. Algoritmlar haqida garflar haqida qisqacha tasavvurga ega bo`ldim.

Foydalanilgan adabiyotlar ro`yxati

1.http:\\acm.tuit.uz
2.”Informatika” fani bo'yicha maruzalar matini.
C/C++ dasturlash tili 2-qism.
3.Sorting Algorithms in 6 Minutes.
4.http:\\Referat.arxiv.uz
5.http:\\Ziyonet.uz
6.http:\\dastur.uz
7 https://uz.mihalicdictionary.org/wiki/analysis_of_algorithms
8 https://fayllar.org/25-graflarni-boyash.html
9 https://arxiv.uz/ru/documents/referatlar/algebra/graflar-ustida-sodda-amallar
10 https://en.wikipedia.org/wiki/Graf
11to%E2%80%98liqlik+masalasining+kuchlilik+tomoni&rlz=1C1GCEA_enUZ904UZ904&oq=NP-12to%E2%80%98liqlik+masalasining+kuchlilik+tomoni&aqs=chrome..69i57.39406j0j9&sourceid=chrome&ie=UTF-8