Algoritimni loyihalash

---

1 
MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT  
AXBOROT TEXNOLOGIYALARI UNIVERSITETI QARSHI 
FILIALI  
  
  
  
  
  
  
“ TT VA KT ” FAKULTETI  
2-BOSQICH AKT 11-21 GURUH TALABASINING
“ ALGORITIMNI LOYIHALASH” FANIDAN  
3-MUSTAQIL ISHI 
  
  
  
  
  
  
Bajardi : RO’ZIYEV.B  
Qabul qildi : NOSIROV.B 

---

2 
MAVZU:
P va NP sinflar, NP-to‘liq masalalar tushunchasi. 
REJA: 
1. Algoritmlarni baholash mezonlari. Vaqt va hajim bo’yicha 
baholshga misollar. 
2. Integrallarni taqribiy hisoblashda NyutonKotes formulalari. 
G’oyalari va hatolik tartibi. 
3. Integrallarni taqribiy hisoblashda Gauss formulalari. G’oyasi va 
hatolik tartibi. Samaradorligi 
4. To’plamlarda qisqartma akslantirishlar. Ularga va amaliy 
tadbiqlarga misollar. 
5. Algebraik va transsendent tenglamalarni taqribiy yechishda 
oraliqni teng ikkiga bo’lish va vatarlar usullarini samaradorlik 
bo’yicha taqqoslash. 
6. Algebraik va transsendent tenglamalarni taqribiy yechishda 
vatarlar va Nyuton usullarini samaradorlik bo’yicha taqqoslash. 
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 

---

3 
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 

---

4 
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 ”.