Algoritimni loyihalash

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. 

---

5 
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: 
Simpson formulasi yuqorida keltirib chikarilgan formulalarga 
karaganda aniqligi yuqori bo`lgan formula hisoblanadi. Bu formulada 
integralning qiymatini yuqori aniqlikda olish uchun bulinish 
kadamlarini tobora oshirish talab etilmaydi. [a,b] kesmani
a=x
0

1

2
…x
n-1 

n
=b  nuqtalar bilan p=2  ta juft teng bulakchalarga 
ajratamiz. u= f(x) egri chiziqka tegishli bo`lgan (x
0
,y
0
), (x
1
,y
1
), (x
2
,y
2
) 
nuqtalar orqali parabola o’tkazamiz. Bizga ma`lumki, bu parabolaning 
tenglamasi 
y = Ax
2 
+ Bx + C
(5.5) 
bo`ladi, bu erda A, V, S — hozircha noma`lum bo`lgan koeffitsientlar. 
[x
0
,x
2
] kesmadagi egri chiziqli trapetsiyaning yuzini shu kesmadagi 
parabola bilan chegaralangan egri chiziqli trapetsiyaning yuzi bilan 
almashtirsak, quyidagiga ega bo`lamiz: 
 




0
2
2
0
2
2
3
0
3
2
2
3
2
2
3
2
3
2
0
2
0
2
0
x
x
C
x
x
B
x
x
A
x
B
Cx
x
A
dx
C
Bx
Ax
dx
x
f
x
x
x
x
x
x






















(x
2
 —x
0
) ni kavsdan tashqariga chikarib, umumiy maxraj-ga keltirsak: 
 






C
x
x
B
x
x
x
x
A
x
x
dx
x
f
x
x
6
3
2
6
2
0
2
2
2
0
2
0
0
2
2
0








(5.6) 
(5.5) dagi noma`lum A, V, S koeffitsientlar quyidagicha topiladi: x ning
x
0
, x
1
, x
2
qiymatlarida f(x) ning qiymatlari y
0
, y
1
, y
2
ekanini va 
2
2
0
1
x
x
x


j a m i n i hisobga olsak, (5.5) dan: 
























.
,
2
3
,
2
2
2
2
2
0
2
2
0
1
0
2
0
0
C
Bx
Ax
y
C
x
x
B
x
x
A
y
C
Bx
Ax
y
(5.7) 

---

6 
(5.7) ning ikkinchi ifodasini turtga ko`paytirib, uchala tenglikni bir-
biriga kushsak: 












C
x
x
B
x
x
x
x
A
C
x
x
x
x
B
x
x
x
x
A
y
y
y
6
3
2
6
2
4
2
0
2
2
2
0
2
0
2
2
0
0
2
2
2
2
0
2
0
2
1
0


















(5.8) 
Bu ifodani (5.6) bilan solishtirsak, bularning ung taraflari bir xil 
ekanligini ko`ramiz. (5.8) ni (5.6) ning ung tarafiga kuysak va x
2
-
x
0
=2h [h=(b-a)/n] ekanligini e`tiborga olsak, quyidagi taqribiy 
tenglikni topamiz:
 


2
1
0
4
3
2
0
y
y
y
h
dx
x
f
x
x




(5.9) 
Xuddi shunday formulani [x
2
, x
4
] kesma uchun ham keltirib chiqarish 
mumkin:
 


4
3
2
4
3
4
2
y
y
y
h
dx
x
f
x
x




(5.10) 
Bu formulalarni butun kesma [a, b] uchun keltirib chikarib, bir-biriga 
kushsak, quyidagini hosil kilamiz: 
 


m
m
m
b
a
y
y
y
y
y
y
y
h
dx
x
f
2
1
2
2
2
3
2
1
0
4
2
...
4
2
4
3











(5.11) 
Bu topilgan formula Simpson formulasidir. Ba`zi xollarda uni 
parabolalar formulasi deb ham ataydilar. 
(5.11) ni eslab kolish unchalik kiyin emas; tok rakamli ordinatalar
turtga, juft rakamli ordinatalar (ikki chekkadagi ordinatadan tashqari) 
ikkita ko`paytiriladi. CHekkadagi ordinatalar y
0
, y
2m
esa birga 
ko`paytiriladi. 
Gauss usuli n noma’lumli n ta chiziqli tenglamalar sistemasini 
Kramer qoidasi bo’yicha yechish 𝑛 = 4 dan boshlab katta va 
mashaqqatli ishga aylanadi, chunki bu ish to’rtinchi tartibli beshta 
determinantni hisoblash bilan bog’liq. Shu sababli amalda Gauss 
usuli muvaffaqiyat bilan qo’llaniladi va u sistema birgalikda hamda 
aniq bo’lsa, uni soddaroq ko’rinishga keltirish va barcha 
noma’lumlarning qiymatlarini ketma-ket chiqarib tashlash, so’ngi 
tenglamada faqat bitta noma’lumni qoldiradi. 

---

7 
Algebraik tenglama - P(x1 ,x2 ,…,xn )=0 ko`rinishida yoziladi. Bu 
erda P - x1 ,x2 ,…,xn noma’lum o'zgaruvchilardan iborat ko`phad. 
Algebraik tenglamaning darajasi P ko`phadning darajasiga teng 
bo`ladi. x1 ,x2 ,…,xn o'zgaruvchilarning algebraik tenglamaga nol 
qiymat beruvchi qiymatlari ushbu algebraik tenglamaning ildizlari 
deb ataladi. Transendent tenglama- transendent funktsiyalarni 
(eksponental, logarifmik, trigonometrik va teskari trigonometrik 
funktsiyalar) o'z ichiga olgan tenglama. Masalan, sin x + lg x = x, 
2x - lg x = arccos x 
Tenglama ildizlarini ajratish f(x)=0 (1) tenglamada f(x) funktsiya 
[a,b] oraliqning uchlarida har xil ishoralarga ega bo`lsa, ya'ni 
f(a)×f(b) 0 bo`lib, [a,b] oraliqda kamida bitta ildiz borligini 
ko'rsatadi. Grafik usul Ushbu usul y=f(x) funktsiya grafigini 
chizishga asoslangan. (1) tenglamaning ildizini o'z ichiga olgan 
[a,b] oraliq funktsiya grafigining OX o'q bilan kesishish nuqtasini 

---

8 
o'z ichiga olgan absissa o'qining bo'lagi bo'ladi. Ba'zan f (x) 
funktsiyani ikkita sodda funktsiyalarning ayirmasi sifatida ifodalash 
qulay bo`ladi, ya'ni 
𝑓 𝑥 = 𝜑(𝑥) − 𝜔(𝑥) . 𝜑(𝑥) va 𝜔(𝑥) 
funktsiyalarning grafikalari chiziladi. Ushbu grafiklarning kesishish 
nuqtasining abstsissasi (1) tenglamaning ildizi bo'ladi va shu ildizni 
o`z ichiga oluvchi absissa o`qidagi kesma izolyatsiya oralig'i 
bo'ladi. 
𝑥𝑙𝑛(𝑥)=1 tenglamani grafik usulda yechishni qaraymiz. Yechish. 
Berilgan tenglamani quyidagi ko`rinishda yozamiz: ln (
𝑥 )=1/𝑥. U 
holda berilgan tenglamaning ildizlarini φ(x)=ln(
𝑥) va ψ(x)=1/x egri 
chiziqlarning kesishish nuqtalarining abstsissalari sifatida topish 
mumkin. Funktsiyalar grafikalarini tuzamiz va ildizni ajratish 
oralig'ini aniqlaymiz. Chizmadan ko`rinadiki, tenglama ildizi [1,2] 
kesmada joylashgan bo`ladi. Ushbu ildizning boshlang`ich qiymati 
sifatida x = 1,5 sonni olish mumkin. 
Yuqoridagi funksiyalar to'plam elementlariga tegishli topshiriqlarni 
bajaradi. To’plam va ko’paytirish funksiyalari to'plam elementlarini 
qo'shish va ko'paytirish amallarini amalga oshiradi. ishora funksiyasi 
to'plamning birinchi elementini, oxiri funksiyasi, oxirgi elementni topadi. 
Katta element va kichik element funksiyalari esa, to'plamdagi eng katta va 
eng kichik elementlarni topish uchun mo'ljallangan. 
1. Inyektiv akslantirishlari
Inyektiv akslantirishlar quyidagi kod bilan ifodalangan:

---

9