O’ZBEKISTON RESPUBLIKASI RAQAMLI TEXNOLOGIYALAR
VAZIRLIGI
MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT
TEXNOLOGIYALARI UNIVERSITETI
QARSHI FILIALI
TELEKOMMUNIKATSIYA
TEXNOLOGIYALARI
FAKULTETI
TT_11-22 GURUH TALABASINING
ALGORITMLARNI LAYIHALASH
FANIDAN
5-MUSTAQIL ISHI
BAJARDI: Rasulov Komil
QABUL QILDI: Ablaqulov.K.B
QARSHI-2024
Mavzu: Determinantlarni hisoblash uchun bajaradigan amallar sonini
baholash. Chiziqli algebraik tenglamalar sistemasini anq yechish uchun
sarflanadigan amallar sonini baholash. NP-algoritmlar tushunchasi. Yechimni
toppish NP-algoritmlarga keltiriladigan masalalarga misollar. Chiziqli
dasturlash masalalari kanonik ko’rinishi. Graf usul. Kommivoyajer haqidagi
masala “Dag’al kuch” usuli. “Xasis” algoritmlar. Kruskal algoritmi. Prima
algoritmi. Xofman daraxtlari.
Determinant
ta'rifi
(sxema)
asosida
biz
quyidagilarni
topamiz:
Ifoda uchinchi tartibli determinant va u deyiladi kabi yozilgan ifodaning o'ng
tomonidagi uchinchi tartibli determinantlarni topish uchun quyidagi esda saqlash
oson sxemalar qo'llaniladi."Uchburchaklar qoidasi"
quyidagi diagrammada
ko'rsatilgan.Birinchidan, determinantning asosiy diagonali va asosi bu diagonalga
parallel bo'lgan teng qirrali uchburchaklar uchlaridagi elementlar alohida
chiziqlar bilan bog'langan , determinantning ijobiy belgisi ko'paytmalari, so'ngra
yordamchi ustidagi teng qirrali uchburchaklar. determinantning diagonali va asosi shu
diagonal-ga parallel bo'lganligi alohida chiziqlar bilan bog'lanadi.Uchlaridagi
elementlar alohida chiziqlar bilan bog'lanadi va aniqlovchining
manfiy ishorali
ko'paytmalari ko'rsatilgan.
"Sarryus qoidalari" quyidagi sxemalar bilan ifodalanadi:
1-qoidada determinantning birinchi ikki qatori yoziladi va 2-qoidada uning
birinchi ikkita ustuni aniqlovchining o'ng tomoniga yoziladi. Keyin bo'sh
diagonaldagi uchta element va bu diagonalga parallel bo'lgan to'g'ri chiziqlar alohida
chiziqlar bilan bog'lanadi, determinantning musbat ishorali ko'paytmalari hosil bo'ladi
va yordamchi diagonaldagi uchta element va bu diagonalga parallel to'g'ri chiziqlar.
alohida qatorlar bilan bog`langan, aniqlovchining manfiy belgili ko`paytmalari hosil
bo`ladi.
1-misol. Aniqlovchilarni hisoblang:
1) satr yoki ustun bo'ylab taqsimlangan;
3
2)
buyurtmani pasaytirdi;
3) uchburchak ko'rinish hosil qilish.
1) Aniqlovchini satr yoki ustunga yoyib hisoblash uchun odatda nol sonli satr
yoki ustun tanlanadi, chunki nollarni o'z ichiga
olgan koeffitsientlar nolga
teng. Berilgan determinantni hisoblash uchun ikkita nolga ega 4 qatorni tanlaymiz va
formuladan topamiz:
2) Determinantni xossalari yordamida tartibini kamaytirib hisoblaymiz.
Bunday holda, biz 2-qatorning barcha elementlarini nolga o'rnatamiz, 1-ustunda
joylashgan elementdan tashqari. Buning uchun avval 2-ustunga (-4) ko'paytirilgan 1-
ustunni qo'shing; 3-ustunga (-1) ko‘paytirilgan 1-ustunni qo‘shing; 4-ustunga (-2)
ko'paytirilgan 1-ustunni qo'shing, so'ngra olingan determinantni 2-qatorga
yoying:Olingan uchinchi tartibli determinantning 2-qatorida determinant belgisidan
(-2) olib tashlaymiz va 2-ustunning 1-qator elementi ostidagi elementlarni nolga
aylantiramiz. Buning uchun 2-satrga 1- (-2) ga koʻpaytirilgan qatorni qoʻshamiz, 3-
chi qatorga 1- (-3) ga koʻpaytirilgan qatorni qoʻshamiz, 3-qatorda aniqlovchi
belgisidan 4-ni olib tashlaymiz. Determinantni 2-ustunning elementlariga yoyamiz va
hosil bo'lgan ikkinchi tartibli determinantni hisoblaymiz.
3) Aniqlovchini uchburchak shaklga keltirish orqali hisoblaymiz. Buning
uchun biz quyidagi almashtirishlarni amalga oshiramiz:
▪
3-qatorni
uning ustidagi
chiziqlar bilan almashtiramiz va
1-qatorga
joylashtiramiz;
▪
1-ustunning 1-qatori ostidagi elementlarni nolga aylantiramiz ;
▪
2-qatorda 8-ni va 3-qatorda (-3) aniqlovchi belgisini olib tashlaymiz;
▪
2-ustunning 2-qatori ostidagi elementlarni nolga aylantiramiz;
▪
biz 3-ustunning 4-qatorida joylashgan elementni
nolga aylantiramiz ;- hosil
bo'lgan uchburchakning determinantidan tashqaridagi uchini bo'sh diagonal
elementlarga ko'paytiramiz.
