TOPOLOGIK SARALASH. ALGORITMNING MURAKKABLIGINI BAHOLASH 2

Загружено в:

12.08.2023

Скачано:

0

Размер:

2769.92578125 KB

Скачать

“TOPOLOGIK SARALASH. ALGORITMNING
MURAKKABLIGINI BAHOLASH”
Mundarija
Kirish
I. NAZARIY QISM
1.1. Topologik tartiblash haqida umumiy nazariya…………...……………….....
1.2. Topologik saralashni topish algoritmlari………………...…………………..
1.3. Topologik saralash uchun chuqur birinchi qidiruv
1.4. Kodni amalga oshirish - Topologik tartiblash uchun Kan algoritmi..............
1.5. Vaqt murakkabligi tahlili ………...………………….....................................
II. AMALIY QISM
2.1. Topologik tartiblash algoritmining qo'llanilishi.………...............................
2.2. Topologik tartib asosidagi amaliy masala…………………………......…...23
Xulosa
Adabiyotlar ro’yhati:

KIRISH
M а vzuning d о lz а rbligi. T а ‘lim tizimid а gi isl о h а tl а rni а m а ld а j о riy qilishd а
bugungi kund а t а ‘lim j а r а y о nining а s о siy t а shkiliy qismi b о ‘lg а n, а m а liy
m а shg‘ul о tl а rni s а m а r а d о rligini о shirish, о ‘qitishni ilg‘ о r p е d о g о gik
t ех n о l о giy а l а rini q о ‘ll а sh а s о sid а о ‘quv с hil а r v а t а l а b а l а rg а j а h о n а nd о z а l а rd а gi
bilim, k о ‘nikm а , m а l а k а l а rni sh а kll а ntirish о ‘quv j а r а y о nini m о ddiy – t ех nik а v а
ах b о r о t b а z а si bil а n t а ‘minl а sh yuq о ri d а r а j а li m а l а k а li k а drl а rni t а yy о rl а sh sif а tli
о ‘quv – uslubiy, ilmiy h а md а did а ktik m а t е ri а ll а r y а r а tish, t а ‘lim tizimi f а n v а ishl а b
с hiq а rish о ‘rt а sid а о ‘z а r о s а m а r а li а l о q а d о rlik о ‘rn а tish d о lz а rb m а s а l а l а rd а n
his о bl а n а di.
F а n v а t ех nik а j а d а l sur а td а riv о jl а n а y о tg а n h о zirgi p а ytd а y а ngi
t ех n о l о giy а d а n f о yd а l а nib d а rs о ‘tishni h а y о t t а q а z о qilm о qd а . Shu nuqt а i n а z а rd а n
h о zirgi kund а t а yy о rl а n а y о tg а n е l е ktr о n k о ‘rg а zm а l а r v а d а rslikl а r о ‘quv с hil а rg а
m а vzuni tushun а rli b о ‘lishig а y о rd а m b е rm о qd а . H о zirgi kund а t а ‘lim j а r а y о nid а
k о mpyut е rning gr а fik imk о niy а tl а rid а n f о yd а l а nishg а b о ‘lg а n qiziqish v а bung а
b о ‘lg а n t а l а bning о rt а b о rishi kuz а tilm о qd а .
Ushbu kurs ishid а ― Topologik saralash. Algoritmning murakkabligini
baholash b о ‘yi с h а multim е di а li е l е ktr о n r е sursl а r y а r а tish, ul а rni t а shkil е tuv с hil а ri,
ul а rg а q о ‘yil а dig а n t а l а bl а r, е l е ktr о n r е sursl а r y а r а tish t ех n о l о giy а l а ri uslubl а ri
h а qid а fikrl а r yuritil а di.
Kurs ishi kirish, 4 b о b, х ul о s а , f о yd а l а nilg а n а d а biy о tl а r r о ‘y ха ti v а il о v а d а n ib о r а t.
2

Topologik tartiblash haqida umumiy nazariya
Umumiy ko rinishʻ
Topologik saralash yoki Kan algoritmi yo‘naltirilgan asil grafikni shunday
tartibga soladigan algoritm bo‘lib, har bir tugun o‘zi ko‘rsatgan barcha tugunlardan
oldin qaytarilgan tartibda paydo bo‘ladi, ya’ni agar bizda a --> b bo‘lsa, a b dan oldin
paydo bo‘lishi kerak.
Topologik tartib
Uning asosiy qo'llanilishi yo'naltirilgan grafiklardagi sikllarni aniqlashdir,
chunki tsiklni o'z ichiga olgan grafik uchun topologik tartib mumkin emas. Uning
qo'llanilishidan ba'zilari: OTda blokirovkani aniqlash, Kurs jadvali muammosi va
boshqalar.
Qo'llash doirasi
 Ushbu maqola Topologik saralashning ishlashi haqida gapiradi .
 Topologik saralash zarurati .
 Topologik saralashning turli operatsiyalari .
 Topologik saralashni amalga oshirish .
 Topologik saralashning murakkabligi .
Olib ketishlar
 Topologik saralashning murakkabligi
 Vaqt murakkabligi - O(N + M) O ( N + M ) Bu erda N - tugunlar soni va M -
qirralarning soni
Topologik tartiblarga kirish
Bugun, topologik tartib haqida gapirishdan oldin , keling, tort haqida
gapiraylik. Ha, tort. Bugun biz shokoladli tort pishiramiz.
Xo'sh, pirojnoe pishirish uchun qanday qadamlarni bajarasiz?
1. Sizda un, pishirish kukuni, pishirish soda, yogurt, yog 'va boshqalar kabi ma'lum
ingredientlar mavjud. Bularning barchasini pishirishga qo'yishdan oldin, bu
ingredientlarning barchasini yaxshilab aralashtirish kerakligini bilishingizga
aminman.
2. Biroq, xamirni (aralashtirilgan ingredientlarni) panga qo'yishdan oldin, avval
panani moylash va un bilan to'ldirish kerak.
3. Xamirni quyganingizdan so'ng, uni pishirishingiz kerakligini bilasiz. Ammo keyin
yana, tortni pishirishdan oldin, siz pechni oldindan qizdirishingiz kerak.
4. Kekni muzlash uchun u salqin bo'lishi kerak. Lekin uni sovutish uchun avval
pishirish kerak.
5. Kekni muzlashdan oldin uni sovutish kerak.
Nega bu pirojnoe pishirish haqida? Biz topologik tartibni o'rganmadikmi ? Kutib
turing, biz bunga erishmoqdamiz.
Yuqorida aytib o'tilgan ushbu to'liq protsedurani grafik sifatida ko'rsatish
mumkin. Aniqrog'i, yo'naltirilgan grafik. Nega? Keyingi harakatga o'tishdan oldin
ma'lum bir harakatni bajarishimiz kerakligini aytib o'tdik.
3

Asosan, bizda amal qilish kerak bo'lgan tartib bor, shuning uchun agar grafik
yo'naltirilgan bo'lsa, albatta mantiqiy bo'ladi, har bir tugunning mazmuni ma'lum bir
harakatdir.
Grafik qanday ko'rinishi mumkin:

Yuqoridagi grafikda ko'rib turganingizdek, avval siz ingredientlarni
aralashtirishingiz kerak va, albatta, shundan keyingina xamirni panga qo'shishingiz
mumkin. Kekni pishirishdan oldin, panani moylash kerak va hokazo.
Bu erda qanday kuzatish mumkin? Grafikni tugunlarning ustuvorligi
bo'yicha tartiblash mumkin va topologik tartib aynan shunday!
Biz topologik tartibni o'rganish uchun asos yaratdik va endi uni rasmiy ravishda
aniqlashimiz mumkin.
Topologik tartiblash nima ?
Aslida, topologik tartiblash - massiv yoki vektorni yoki ro'yxatni qaytarish
orqali yo'naltirilgan grafikni saralaydigan algoritm bo'lib, u har bir tugun o'zi
ko'rsatgan barcha tugunlardan oldin paydo bo'ladigan tugunlardan iborat .
Bu erda biz uni oddiygina massiv deb ataymiz, siz vektor yoki ro'yxatni ham
ishlatishingiz mumkin.
Aytaylik, bizda grafik bor edi,
a --> b --> c
keyin topologik tartiblash algoritmi qaytadi - [a, b, c] . Nega? Chunki, a b ga
ishora qiladi , ya'ni a turda b dan oldin kelishi kerak. b c ga ishora qiladi , ya'ni b
turda c dan oldin kelishi kerak .
Keling, nisbatan murakkabroq misolni ko'rib chiqaylik.
4

Sizningcha, ushbu yo'naltirilgan grafik uchun topologik tartib qanday
ko'rinadi? Xo'sh, ko'ramiz. Dastlab, bizning qaytariladigan massiv/vektor yoki
tartiblangan massiv/vektor (tartiblangan tartibda grafik tugunlarini o'z ichiga olgan
massiv) bo'sh [ ] .
Saralangan natijaning boshiga 4 qo'shsak bo'ladimi? Yo'q! Algoritm shuni
ko'rsatadiki, agar joriy tugunga ishora qiluvchi tugunlar mavjud bo'lsa, ular birinchi
navbatda qo'shilishi kerak. Shunday qilib, tartiblangan natijaga 4 ni qo'shmoqchi
bo'lsak, 4 ga ishora qiluvchi tugun(lar) ni tekshirishimiz kerak .
Ko'rib turibmizki, tartiblangan natijaga 2 ta tugun qo'shilishi mumkin - 2, 3. Kutib
turing, ularga ham ishora qiluvchi tugun bor! Shunday qilib, hammasi 1 qiymatiga
ega bo'lgan tugundan boshlanadi! 2 yoki 3 ni qo'shishdan oldin biz 1 ni qo'shishimiz
kerak, chunki ikkala tugunning (2, 3) boshqa tugunlari ularga qaratilgan, ya'ni 1 dan
oldin tartiblangan natijaga 2 yoki 3 ni qo'shib bo'lmaydi .
Shunday qilib, saralangan natijamizga qo'shiladigan birinchi element (massiv / vektor
/ ro'yxat) aniq 1 bo'ladi, chunki unga ishora qiluvchi boshqa tugunlar yo'q. Bizning
tartiblangan natijamiz endi shunday ko'rinadi [1]
Keyin qaysi tugunlarni qo'shamiz? '1' tugun ikkita tugunni ko'rsatadi - 2, 3. Qaysi
birini qo'shish mumkin bo'lsa, birinchi bo'lib qo'shilishi kerak?
Topologik turlanishning o'ziga xosligi
Bu topologik tartib haqida . Ko'pgina tartiblash algoritmlarida siz elementlarni
saralashning faqat bitta usuli borligini ko'rgan bo'lishingiz kerak. Ikkita yo'l yo'q yoki
hech qanday variant mavjud emas.
Biroq, topologik tartiblashda ma'lum bir grafikni bir necha usulda saralash
mumkin. Yuqoridagi misolda biz ko'rganimizdek , tartiblangan
massivga 1 qo'shgandan so'ng , bizda 2 yoki 3 ni qo'shish imkoniyati mavjud .
Ammo shuni ta'kidlash kerakki, 2 yoki 3 ning har biri boshqa ustuvorlikka ega
emasligi sababli, bu qiymatlarning ikkalasi ham boshqa tugunga o'tishdan oldin
tartiblangan massivga kiritilishi kerak. Ikkala element ham 2 va 3 bir xil ustuvorlikka
ega.
5

Shunday qilib, bizning misol grafigimizning topologik tartiblangan natijasi [1, 2,
3] yoki [1, 3, 2] kabi ko'rinishi mumkin . Hozircha siz ulardan birini tanlashingiz
mumkin. Biz [1, 3, 2] bilan boramiz .
Bizning tartiblangan natijamizga kiritilishi kerak bo'lgan keyingi element nima
ekanligini taxmin qila olasizmi? 5mi ? _ Ko'rib turganingizdek, 2 qiymatiga ega
bo'lgan tugundan oldinga siljishimiz mumkin bo'lsa-da , biz 5 qiymatiga ega bo'lgan
tugunga o'tishimiz mumkin , lekin 5da unga ishora qiluvchi yana bir tugun bor va
bu 4. Demak, bizdan oldin 4 qo'shilishi kerak. 5 qo'shing .
Natija endi shunday ko'rinadi [1, 3, 2, 4] . Esda tutingki, u ham shunday ko'rinishi
mumkin [1, 2, 3, 4] , lekin hozircha u boshqa ko'rinishga ega emas.
Biz 4 ta elementni qo'shganimizdan so'ng , biz faqat bitta element qolganligini
ko'ramiz va bu 5 ta , shuning uchun saralangan natijaga oxirgi qo'shamiz. Voila, siz
yo'naltirilgan grafikni topologik tarzda tartibladingiz!
Keling , topologik tartiblashni rasmiy ravishda aniqlaylik , endi biz uning qanday
ishlashini tushundik.
Yo naltirilgan grafikning topologik tartiblanishi yoki topologik tartiblanishi ʻ
uning cho qqilarining chiziqli tartiblanishidir, shunda u cho qqidan v cho qqigacha (u
ʻ ʻ ʻ
--> v) har bir yo naltirilgan uv chekkasi uchun u tartiblashda v dan oldin keladi.
ʻ
Biz topologik tartiblash va uning qanday ishlashini tushundik , lekin uni qanday
kodlashimiz mumkin? Keling, ushbu turdagi algoritmni muhokama qilaylik.
Ammo bunga o'tishdan oldin, keling, biroz murakkab grafiklarni ko'rib
chiqaylik va xuddi shu tarzda tartiblangan natijani (bu siz afzal ko'rgan boshqa
ma'lumotlar tuzilmasi bo'lishi mumkin) topishga harakat qilaylik.

6

Keling, ushbu massivni ko'rib chiqaylik - [5, 7, 3, 11, 8, 2, 9, 10] . Sizningcha,
bu massiv topologik tartiblangan grafikni ifodalaydimi? Ha, albatta! Siz ushbu
massivni grafik bo'ylab yuqoridan pastgacha va chapdan o'ngga siljigan holda
tasvirlashingiz mumkin.
Bu haqida nima deyish mumkin - [3, 5, 7, 8, 11, 2, 9, 10] ? Ha, bu ham amal
qiladi. Oldingi misolimizda bo'lgani kabi, bizda bir xil ustuvorlikka ega bo'lgan ikkita
2, 3 tugunlari bor edi va bu erda xuddi shu tarzda, 5, 7, 3 va 8, 11 tugunlari bir xil
ustuvorliklarga ega!
[7 , 5, 11, 3, 10, 8, 9, 2] haqida nima deyish mumkin ? O'zingiz tekshirib ko'ring, bu
to'g'ri.
Oxirgi - [10, 5, 7, 3, 8, 11, 2, 9] ? Bu haqiqiy emas. Nega? Garchi bir xil
ustuvorliklarga ega bo'lgan tugunlar birga bo'lsa ham, bittasi yo'q. Qiymati 10. 10
bo lgan tugunni tartiblangan massivimizga unga ishora qiluvchi biron bir elementdan ʻ
oldin qo shib bo lmaydi, ya ni massivga birinchi navbatda 3. 3 qo shilishi kerak va
ʻ ʻ ʼ ʻ
shundan keyingina 10 haqiqiy mulohaza bo ladi.
ʻ
Bu grafik haqida nima deyish mumkin?

Ko'rib turganingizdek, bu grafik tsiklga ega. Aytaylik , biz dastlab
ro'yxatimizga A tugunini qo'shamiz va A B ga ishora qilgani uchun
keyingi qo'shilishi mumkin bo'lgan tugun B dir . Lekin unchalik tez emas, biz B ga
ishora qiluvchi yana
bir tugun borligini ko'ramiz , ya'ni D . Demak, biz D ni
qo'shishimiz mumkin. Yana D ga ishora qiluvchi yana bir tugun bor , ya'ni C.
Ushbu tsikl bizga ushbu grafik uchun har qanday to'g'ri topologik tartibni topishga
imkon bermaydi.
Endi biz 2 nuqtani xulosa qilishimiz mumkin:
 Grafikning bir nechta topologik tartiblangan massivlari bo'lishi mumkin
 Yo'naltirilgan siklik grafiklarda topologik tartiblangan tartib yo'q.
7

Topologik saralashni topish algoritmlari
Har qanday grafikning topologik tartiblangan tartibini topish uchun bizda
foydalanish mumkin bo'lgan 2 ta algoritm mavjud - Kan algoritmi, Depth-birinchi
qidiruv. Ushbu maqolada biz Kan algoritmini batafsil ko'rib chiqamiz.
Kan algoritmi
Grafikning topologik tartiblanishini qaytarish uchun ishlatilishi mumkin
bo'lgan birinchi va eng mashhur algoritmlardan biri bu Kan algoritmidir . Bu qanday
ishlaydi?
Bilasizmi, biz qaytaradigan oxirgi massivimizga tugunni qanday qo'shish unga
ishora qiluvchi tugunlar qo'shilgan yoki qo'shilmaganiga bog'liqmi? Asosan
bu darajami ?
Tugun darajasi - bu aniq tugun uchun kiruvchi qirralarning soni.
Kan algoritmi asosan kiruvchi qirralari bo'lmagan yoki indegree = 0 ga ega bo'lgan
tugunlarni qidiradi, so'ngra uning chiqadigan qirralarini olib tashlaydi, bu esa uning
chiqish darajasini ham 0 ga tenglashtiradi.
Bosqichma-bosqich algoritm:
1. Indeks = 0 (kiruvchi qirralari yo'q) bo'lgan tugunni toping
2. O'sha tugundan tashqariga chiqadigan barcha qirralarni olib tashlang (uni
chetga = 0 qilib qo'ying, chiqadigan qirralarni olib tashlang)
3. Grafikning topologik tartiblanishini ifodalovchi massivga ushbu tugunni
qo'shing
4. Boshqa tugunlar qolmaguncha takrorlang.
Keling, ushbu bosqichlarni grafikga qo'llaymiz:

8

Sizningcha, biz qayta ishlashimiz kerak bo'lgan birinchi tugun
nima? Ha, bu A. A - kiruvchi qirralari bo'lmagan va ikkita chiquvchi qirrasi bo'lgan
grafikdagi yagona tugun. Shunday qilib, biz bu tugunni uning chiquvchi qirralarini
olib tashlab, uni topologik tartiblash massivimizga qo‘shish orqali ajratib olamiz.
Grafikning tartiblangan tartibi quyidagicha ko'rinadi: [A]
Va bizning grafik hozir shunday ko'rinadi:

Biz qo'shishimiz mumkin bo'lgan keyingi tugun B yoki C dir . Ehtiyotkorlik
bilan qarang, ularning hech birining kiruvchi qirralari yo'q. Biz bilamizki, grafaning
bir nechta topologik tartiblangan tartibi bo‘lishi mumkin, shuning uchun
biz B yoki C tugunlaridan istalgan birini massivga qo‘shish bilan oldinga siljiymiz,
chunki ularning har ikkalasi ham bir xil darajada qo‘shilishi mumkin.
Massiv: [A, C]
Grafik:

9

Endi B dan tashqari har bir tugun kiruvchi chekkaga ega va shuning uchun
massivimizdagi keyingi tugun B bo'lishi kerak.
Massiv: [A, C, B]
Grafik:

Keyingi mos tugun osonlikcha D. Garchi, biz hatto E qo'shishimiz mumkin, lekin
tugun butunlay izolyatsiya qilinganligi sababli, keling, u bilan boraylik. Esda
tutingki, grafik topologik tartibda bir necha usul bilan tartibga solinishi mumkin. Siz
hozir D yoki E ni tanlaysizmi, buyurtmaga ta'sir qilmaydi.
Massiv: [A, C, B, D]
Grafik:

E - kiruvchi qirralari bo'lmagan yagona tugun, shuning uchun uni qo'shamiz, keyin
qolgan yagona tugun F bo'ladi.
Shunday qilib, massiv: [A, C, B, D, E, F]
Va bu bizning Kan algoritmidan foydalangan holda ushbu grafik uchun topologik
tartiblangan tartibdir!
Keling, Kan algoritmining haqiqiy kodini amalga oshirishdan oldin qandaydir
psevdokodni ko'rib chiqaylik.
sorted <-- Empty list initially, of the topologically sorted elements
10

$zero_incoming <-- set of nodes with indegree = 0 while zero_incoming is not empty do: remove a node n from zero_incoming add n to the sorted list for each node out with an edge from n to out do: remove edge from graph if out has no other incoming edges then: insert out in zero_incoming if graph has edges then: return Error {graph has at least 1 cycle} else return sorted {our final array} Ushbu grafik uchun yuqorida qilgan barcha qadamlar yuqorida psevdokodda amalga oshirildi. Endi algoritmni amalga oshirish maqsadlarida tushunishimizni yaxshilash uchun biz zero_incoming to'plam ekanligini aytdik, ammo kodda biz uni birinchi navbatda birinchi bo'lib chiqadigan xususiyatlar tufayli navbat bilan amalga oshiramiz. Endi biz uni kodlashdan oldin, algoritmga kichik o'zgartirish kiritamiz. Qirralarni olib tashlash o'rniga biz qirralarni indikatorli massivda saqlaymiz va o'rniga o'sha massivga o'zgartirish kiritamiz. Biz kirishda olingan qo shnilar ro yxatini kesib o tish va tugunning qo shnilari ʻ ʻ ʻ ʻ sonini har safar tugun qo shnilariga duch kelganimizda ʻ 1 ga oshirish orqali indeks massivini yaratamiz (biz tez orada tushuntirishga o tamiz. ). ʻ Shunday qilib, biz ma'lum bir manba tugunidan chiquvchi qirralarni olib tashlamoqchi bo'lganimizda, biz manba tugunidan maqsad tugunlarga ulanadigan kiruvchi tugunni olib tashlaymiz. Grafikning topologik tartibini topish uchun ishlatiladigan yana bir algoritm DFS hisoblanadi . 11$

Topologik saralash uchun chuqur birinchi qidiruv
Asosiy DFS algoritmi haqida bilish uchun , iltimos, Google-ga kiring va bu
haqda o'qing. Ushbu maqolada biz sizga faqat DFS algoritmidan qanday foydalanish
haqida tushuncha beramiz.
Chuqurlikdagi birinchi qidiruv algoritmida biz mavjud bo'lgan tugunni tashrif
buyurilgan deb belgilaymiz yoki uni chop etamiz yoki muammoga ko'ra unga ba'zi
o'zgartirishlar kiritamiz va keyin bir xil DFS ni rekursiv chaqirishga o'tamiz. uning
qo'shni tugunlarida funksiya. Xo'sh, bu topologik tartib bilan qanday bog'liq?
Bu erda, topologik tartibda, biz saralangan massivga tugunni qo'shni tugunlardan
oldin qo'shishni va boshqa tugunlarga ishora qiluvchi tugunlarni u ko'rsatadigan
qo'shni tugunlardan oldin surishni xohlaymiz.
Grafikning DFS chiqishi aniq uning topologik tartiblanishidan farq qilishi mumkin,
chunki DFS da bir xil ustuvorlikka ega bo'lmagan ikkita qo'shni natijaviy massivga
surilishi mumkin, ammo topologik tartiblashda bunga yo'l qo'yib bo'lmaydi.
Biroq, chuqurlikdagi birinchi qidiruv algoritmi bizning maqsadimizga mos ravishda
o'zgartirilishi mumkin. Bu yerda biz vaqtinchalik stekdan foydalanamiz va
chiqishimizga joriy tugunni qo‘shish o‘rniga, avvalo topologik saralash funksiyasini
barcha qo‘shni tugunlarda rekursiv chaqiramiz va keyin uni stekga suramiz.
Endi sizda DFS dan qanday foydalanish haqida fikringiz bor , uni o'zingiz tanlagan
dasturlash tilida kodlang!
Kodni amalga oshirish - Topologik tartiblash uchun Kan algoritmi
Biz Kanning topologik tartiblash algoritmi uchun psevdokodni ko'rdik, endi
haqiqiy kodga o'tamiz.
Kan algoritmini takrorlab , biz qaysi tugunning kiruvchi qirralari yo'qligini
bilib olamiz, uni tartiblangan ro'yxatimizga qo'shamiz va qirralarni indikatorli qatorda
o'chirib tashlaymiz/saqlaymiz va o'sha tugundan chiquvchi qirralarni olib tashlaymiz.
Buni tugatganimizdan so'ng, biz yana indegree = 0 bo'lgan tugunni qidirishni
boshlaymiz . Agar indeksi 0 ga teng bo'lgan biron bir tugunni topa olmasak, u holda
grafikning tsikli bor degan xulosaga kelishimiz mumkin.
C++
Keling, kodni bosqichma-bosqich ko'rib chiqaylik. Yuqoriga aylantiring,
psevdokodga yana bir bor qarang. Bu erda biz Grafikning kiritilishi qo'shni ro'yxat
ko'rinishida va ro'yxat funktsiyaning kiritilishida beriladi deb taxmin qilamiz.
Psevdokodning dastlabki ikki qatori quyidagilar edi:
sorted <-- Empty list initially, of the topologically sorted elements
zero_incoming <-- set of nodes with indegree = 0
12

$Bu birinchi ikki qadam edi, lekin bu erda biz ularni biroz o'zgartiramiz. Saralangan ro'yxat vektor bo'ladi va zero_incoming birinchi bo'lib chiqadigan xususiyatlar tufayli navbat bo'ladi. Grafikni o'zgartirishni (agar kerak bo'lmasa, kiritishni o'zgartirish yaxshi amaliyot emas) yoki uning qirralarini o'chirishni istamaganimiz uchun biz har bir tugunning indekslarini saqlash uchun boshqa ma'lumotlar strukturasini - vektorni yaratamiz, dastlab hammasi 0. Tugun darajasi - tugundagi kiruvchi qirralarning soni. Quyidagi koddagi v o'zgaruvchisi tugunlar soni. vector<int> sorted; vector<int> indegrees(v, 0); queue<int> zero_incoming; Keyingi qadam massivdagi tugunlarning barcha ko'rsatkichlarini (kiruvchi qirralarning sonini) saqlash bo'ladi. Buning uchun biz iteratordan foydalanamiz. Iterator bizga ro'yxatdagi har bir elementni birma-bir ko'rib chiqishga imkon beradi. list<int>::iterator itr; Shunday qilib, itr - list<int> shablon sinfi uchun yuqoridagi koddagi iteratorimizning nomi . Iteratorlarda biz list<int>.begin() va list<int>.end() dan foydalanamiz, bu bizga mos ravishda ro yxatning boshi va oxiriga ishora qiluvchi misollarni beradi.ʻ Tugunning barcha qo shnilarini ko rib chiqayotganimizda, biz tugunning mos ʻ ʻ keladigan qo shnilar ro yxatining ʻ ʻ begin() va end() misollaridan uni kesib o tish va ʻ uning uzunligini kiruvchi tugunlar soni sifatida saqlash uchun foydalanamiz. Muxtasar qilib aytganda, biz iterator yordamida qo'shnilar ro'yxatini aylanib o'tamiz va barcha tugunlarning indekslarini (tugunning kiruvchi qirralari soni) indekslar vektorida saqlaymiz. for (int node = 0; node < v; node++){ list<int>::iterator itr; for (itr = adj_list[node].begin(); itr != adj_list.end(); itr++){ indegrees[*itr]++; } 13$ $} Endi biz indegrees massivini to'ldirganimizdan so'ng, keyingi qadam navbatimizga indegree = 0 bo'lgan tugunlarni kiritishdir . for (int i = 0; i < v; i++){ if (indegrees[i] == 0) zero_incoming.push(i); } Shunday qilib, bizning navbatimizda indegree = 0 bo'lgan barcha tugunlar mavjud va endi ularni qayta ishlashni davom ettirishimiz mumkin. Esda tutingki, topologik saralashda biz har doim ham buyurtma ololmasligimiz mumkin. Grafikda tsikl bo'lishi mumkin va uni faqat tartiblangan massivdagi tugunlar soni to'liq grafikdagi tugunlarning umumiy soniga teng bo'lmasa yoki boshqacha qilib aytganda, tashrif buyurilgan va qayta ishlangan tugunlar soniga teng bo'lmagan taqdirda aniqlash mumkin. grafikdagi tugunlarning umumiy sonidan farq qiladi. Shunday qilib, tashrif buyurilgan tugunlar sonini saqlash uchun biz ularni saqlaydigan boshqa o'zgaruvchini ishga tushiramiz. Dastur oxirida, agar umumiy tugunlar soni tashrif buyurilgan tugunlar soniga teng bo'lsa, biz grafikda tsikl yo'qligini bilamiz. int visited_nodes = 0; Biz endi navbatda turgan tugunlarni qayta ishlashimiz kerak - zero_incoming. while (!zero_incoming.empty()){ int node = zero_incoming.front(); zero_incoming.pop(); sorted.push_back(node); ... } Yuqoridagi kodda biz navbat bo'sh bo'lguncha ishlaydigan tsiklni boshladik. Biz navbatning old qismini tugun deb nomlangan butun sonda saqladik va keyin uni navbatdan olib tashladik. Uning kiruvchi qirralari yo'qligini bilganimiz uchun, biz 14$ $uni tartiblangan massivimizga qo'shamiz . ... o'rniga nima kelishi kerakligini taxmin qila olasizmi ? Ha! To'g'ri aytdingiz, endi biz qo'shnilar bilan ishlashimiz kerak. Biz u ko'rsatgan barcha tugunlarning darajasini 1 ga kamaytiramiz (bu siz o'ylaganingizda barcha chiquvchi qirralarni olib tashlash bilan bir xil). list<int> iterator itr; for (itr = adj_list[node].begin(); itr != adj_list[node].end(); itr++){ if (--indegrees[*itr] == 0) zero_incoming.push(*itr); visited_nodes++; } Bo'ldi shu! Endi biz tashrif buyurilgan tugunlar tugunlarning umumiy soniga teng yoki yo qligini tekshirib ko ramiz, so ngraʻ ʻ ʻ tartiblangan vektorni qaytarishimiz mumkin, agar yo q bo lsa, grafikda sikl borligini bildiruvchi xatolikni qaytaramiz. ʻ ʻ Mana to'liq kod: vector<int> topological_sort(vector<list<int>> adj_list){ int v = adj_list.size(); vector<int> sorted; vector<int> indegrees(v, 0); queue<int> zero_incoming; for (int node = 0; node < v; node++){ list<int>::iterator itr; for (itr = adj_list.begin(); itr != adj_list.end(); itr++){ indegrees[*itr]++; } 15$ $} int visited_nodes = 0; while (!zero_incoming.empty()){ int node = zero_incoming.front(); zero_incoming.pop(); sorted.push_back(node); list<int>::iterator itr; for (itr = adj_list[node].begin(); itr != adj_list[node].end(); itr++){ if (--indegrees[*itr] == 0) zero_incoming.push(*itr); visited_nodes++; } } if (visited_nodes != v) throw "Graph contains a cycle"; else return sorted; } Kodning oxirida, agar tashrif buyurilgan tugunlar soni grafikdagi tugunlarning umumiy soniga teng bo'lmasa, biz shunchaki xato qo'shdik. Malumot uchun Java-dagi kod: Java public static int[] topological_sort(int[][] adj_list){ int v = adj_list.length; 16$ $int sorted[] = new int[]; int indegrees = new int[v]; Queue<Integer> zero_incoming = new LinkedList<Integer>(); for (int i = 0; i < v; i++){ ArrayList<Integer> temp = (ArrayList<Integer>)adj_list[i]; for (int node : temp) indegrees[node]++; } for (int node = 0; node < v; node++){ if (indegrees[node] == 0) zero_incoming.push(node); } int visited_nodes = 0; while (!zero_incoming.empty()){ int node = zero_incoming.poll(); sorted.add(node); for (int u: adj_list[node]){ if (--indegrees[u] == 0) zero_incoming.add(u); } visited_nodes++; } if (visited_nodes != v) throw new Exception("Graph contains a cycle!"); 17$

else
return sorted;
}
Endi kodni istalgan boshqa tilda yozishingiz mumkin!
Vaqt va algoritm murakkabligi tahlili
Algoritmning vaqt bo’yicha murakkabligiga kirish ma’lumotlarining hajmi
sezilarli ta’sir ko’rsatadi. Unchalik kata bo’lmagan hajmdagi ma’lumotlarni qayta
ishlashda ikkita turli algoritmning ishlash vaqti ahamiyatsizdek tuyulishi mumkin,
ammo ma’lumotlar hajmining ortishi ularning bajarilish vaqtiga sezilarli darajada
ta’sir ko’rsatishi mumkin.
Lekin vaqt bo’yicha murakkablik faqatgina hajmga emas, balki
ma’lumotlarning qiymatiga, shuningdek ularning tushish(uchrash) tartibiga ham
bog’liq. Masalan, ko’pchilik saralash algoritmlari agar massivning o’zi saralangan
bo’lsa, massivni tartiblashga anchayin kam vaqt sarflaydi. Shu kabi holatlar sabab
vaqt bo’yicha murakkablikni uch xil holatda ko’rib chiqiladi: yomon, yaxshi va
o’rta.
Yomon holat kirish ma’lumotlarining omadsiz kiritilishida ya’ni algoritm
masalani yechish uchun maksimal sondagi elementar amallarni bajarishi to’g’ri
kelish holatiga mos keladi. Yaxshi holatda aksincha kirish ma’lumotlari imkon
qadar minimal sondagi amallarni bajarilishi ta’minlaydi.
O’rta holat anchayin murakkab aniqlanadi. Kirish ma’lumotlari imkon
darajasida guruhlarga ajratiladi. Keyin har bir guruhning qatnashish ehtimolligi
aniqlanadi. Shundan so’ng, har bir guruhning ma’lumotlar bilan ishlashi bo’yicha
algoritmning ishlash vaqti hisoblanadi. Bizni ko’pincha eng kam va eng ko’p
holatlari ko’proq qiziqtiradi.
Kiritiluvchi ma’lumotlarning hajmi katta bo’lganda biror masalaning
ekzemplyar(nusxa) asosida bajariluvchi yechimi, algoritmlarning ishlash vaqti
analizini solishtirish asimptotik tahlil deb yuritiladi. Asimptotik murakkabligi
kamroq bo'lgan algoritm ko'proq samarador (effektiv) hisoblanadi.
Ushbu algoritmning vaqt murakkabligini tahlil qilish uchun ( Kan algoritmi ) biz Kan
algoritmini kichik qismlarga ajratamiz.
1. Har bir tugunning ko'rsatkichini aniqlash - O (M) . Bu erda M - qirralarning
soni. Nega? Ko'rsatkichni aniqlash uchun biz grafikning har bir yo'naltirilgan
chetiga bir marta qarashimiz kerak.
18

2. 0 gradusli tugunlarni topish - O(N) . Bu oddiy operatsiya bo'lib, unda biz
barcha tugunlarni aylanib o'tish orqali qaysi tugunlarning kiruvchi qirralari
yo'qligini tekshiramiz. Bu erda N - tugunlar soni.
3. Barcha tugunlarni tartiblangan massivga qo'shing. Ushbu tsikl O(N) marta
bo'lgan har bir tugun uchun bir marta ishlashi mumkin . Ushbu halqaning
tanasida biz ikkita operatsiyadan birini bajaramiz
o tugunni tartiblangan massivimizga qo'shing
o qo'shnilar darajasini 1 ga kamaytiring . Biz har bir chekka uchun faqat
bir marta kamaytiramiz (aniq) va shuning uchun bu qadam O (M) ga
aylanadi , bu erda M yana qirralarning soni.
4. Grafikning barcha tugunlarini massivga kiritganimizni yoki tsiklni
topganimizni tekshirish: O(1)
Shunday qilib, algoritmning umumiy vaqt murakkabligi O (N + M) ekanligini
ko'rishimiz mumkin .
Keling, Kan algoritmining fazoviy murakkabligini ham muhokama
qilaylik . Kodimizda quyidagi ma'lumotlar tuzilmalarini yaratdik:
 Nol gradusli tugunlar - O(N)
 Saralangan massiv - O(N)
Demak, algoritmning yakuniy fazoviy murakkabligi - O(N) ga teng .
Asimptotik tahlilda algoritmning murakkabligi – bu algoritmning ma’lumotlari
hajmi ortishi bilan algoritmning ishlash vaqtining tezkor ravishta ortishini
belgilovchi funksiyadir. Asimptotik tahlilda asosiy uchraydigan o'sishni baholash
funksiyalari bular:
 ( O - katta ) – vaqtni o ' sishini yuqori asimptotik baholash funksiyasi ;
 Ω ( Omega ) – vaqtni o ' sishini quyi asimptotik baholash funksiyasi ;
 Θ ( Teta ) - vaqtni o ' sishini quyi vayuqori asimptotik baholash funksiyasi .
Bunda n
– ma'lumotlarning hajmiy kattaligi bo'lsin. U holda f(n) algoritmning
o’sish funksiyasini asimptotik jihatdan g(n) funksiya bilan chegaralash mumkin:
Mazmuni Tavsifi
f ( n ) ∈ Ο ( g ( n )) f yuqoridan g funksiya bilan doimiy ko'paytiruvchi
aniqligigacha chegaralangan
f ( n ) ∈ Ω( g ( n )) f quyidan g funksiya bilan doimiy ko'paytiruvchi
aniqligigacha chegaralangan
f ( n ) ∈ Θ( g ( n )) f yuqori va quyidan g
funksiya bilan chegaralangan
Misol uchun, muassasaning tozalash vaqti uning maydoni kattaligiga chiziqli
ravishta bog’liq ( Θ ( S )), ya’ni maydon kattaligining n marta ortishi bilan uni tozalash
vaqti ham n
marta ortadi. Telefon daftarchasidan ismni qidirishda agar chiziqli
qidirish algoritmidan foydalanilsa, O(n) chiziqli vaqtni talab etadi. Agar ikkilik
19

qidiruvdan foydalanilsa, u holda ( Ο (log
2 ( n ))) yozuvlar soniga logarifmik bog’liq
bo’ladi.
Biz O – funksiya bilan ko’proq kuzatuvlar olib boramiz. Keyingi kuzatishlarda
algoritmlarning murakkabligi yuqori asimptotik chegara bilan beriladi.
Asimptotik tahlilning muhim qoidalari:
1. O ( k * f ) = O ( f ) – doimiy ko’payuvchi k (konstanta) tashlab yuboriladi, chunki
doimiy kirish ma’lumotlarining ortishi bilan uning ahamiyati yo’qoladi,
masalan:
O(9,1n) = O(n)
2.O ( f * g ) = O ( f )* O ( g ) – ikkita funksiya ko’paytmasining murakkabligini
baholash ularning murakkabliklari ko’paytmasiga teng, masalan:
O(5n*n) = O(5n)*O(n) = O(n)*O(n) = O(n*n) = O(n 2
)
3.O ( f / g )= O ( f )/ O ( g ) – ikkita funksiyaning bo’linmasining murakkabligi ular
murakkabliklarining bo’linmasiga teng, masalan:
O(5n/n) = O(5n)/O(n) = O(n)/O(n) = O(n/n) = O(1)
4.O ( f + g ) teng O(f)
va O(g) larning dominantiga – funksiyalar summasining
murakkabligini baholash, birinchi va ikkinchi qo’shiluvchilarning dominant
(hukmron) murakkabligini baholash bilan belgilanadi, masalan:
O(n 5
+n 10
) = O(n 10
)
Amallarning sonini sanash juda mayda ish, eng muhimi bu unchalik muhim
emas. Yuqorida keltirilgan qoidalardan kelib chiqqan holda, algoritmning
murakkabligini aniqlashda oldin bajarganimizdek amallarni sanash kerak emas, biz
uchun algoritm (operator yoki operatorlar guruhi) konstruksiyasi qaysi murakkablik
darajasiga mansubligini bilish kifoya. Bundan ma’lumki, sikl va rekursiyalarga ega
bo’lmagan algoritm O(1) konstanta murakkabligiga ega. n ta iteratsiyani bajaruvchi
siklning murakkabligi O(n)
ga teng. Bitta n o’zgaruvchi qiymatiga bog’liq bo’lgan
ichma ich joylashgan ikkita siklning konstruksiyasi kvadratik murakkablikka O(n 2
)
ega bo’ladi.
Quyida
eng ko’p uchraydigan murakkablik sinflari keltirilgan:
 O (1) – konstantali murakkablik ;
 О ( n ) – chiziqli murakkablik;
 О ( n а
) – polynomial murakkablik ;
 О (log( n )) – logarifmik murakkablik;
 O(n*log(n)) – kvazichiziqli murakkablik;
 O (2 n
) – eksponensial murakkablik ;
 O ( n !) – factorial murakkablik .
Topologik tartiblash algoritmining qo'llanilishi
20

Yuqoridagi maqolani o'qiyotganda, siz ushbu algoritmdan foydalanishingiz
mumkin bo'lgan ba'zi joylar haqida o'ylab ko'rgan bo'lsangiz kerak. Keling, ulardan
ba'zilari juda keng tarqalgan foydalanishni ko'rib chiqaylik:
1. Grafikdagi siklni topish
Biz yuqorida ko'rdikki, grafikda tsikl mavjud bo'lganda, grafikning topologik
tartiblash / topologik tartibi mavjud emas. Aytaylik, bizda ma'lum jarayonlar
mavjud, 1, 2 va 3 jarayonlar . Biz ularni bajarish uchun to'g'ri tartibni topishimiz
kerak. Sizga berilgan ma'lumotlar:
 1-jarayonni bajarish uchun siz 2-jarayonni bajarishingiz kerak
 3-jarayonni bajarish uchun siz 1-jarayonni bajarishingiz kerak
 2-jarayonni bajarish uchun siz 3-jarayonni bajarishingiz kerak
Yaratilgan grafik quyidagicha ko'rinadi:

Ushbu grafik tsiklni o'z ichiga oladi!
Kompyuter bu tsikl yoki yo'qligini qanday biladi? Avval bajarilishi kerak
bo'lgan jarayonni topishga urinib, u tsiklga yopishib qoladi!
Topologik tartiblash yordamida biz grafikda sikl borligini aniqlashimiz mumkin,
chunki tugunlardan kamida bittasi topologik tartibni buzadi. Agar biz kiritilgan
jarayonlarda tsikl borligini aniqlasak, uni tizimga kiritmaymiz!
2. Operatsion tizimning blokirovkasini aniqlash
Operatsion tizimda bizda bajarilishini kutayotgan yoki allaqachon bajarilgan bir
nechta jarayonlar va holatlar mavjud.
Aytaylik, hozirda bajarilishini kutayotgan jarayon bor, chunki u boshqa jarayondan
resurslarga muhtoj. Ammo agar resurslar bilan ta'minlaydigan jarayon o'zi resursni
ushlab turgan kutish holatida bo'lsa, unda har qanday jarayon qanday amalga
oshiriladi? Bu holat o'lik deb ataladi.
Agar e'tibor bergan bo'lsangiz, bu ham grafikdagi tsiklga o'xshaydi va biz yuqorida
ko'rganimizdek, topologik tartib - bu tsiklni aniqlash va boshi berk
21

ko'chaga tushishning oldini olishning eng yaxshi usuli!
Resurslarni taqsimlash grafigi Grafik uchun mos keladigan
kutish
Bu yerda P1 , P2 va P3 jarayonlar, R1 , R2 va R3 esa resurslardir. Tugallangan
vaziyatda u xuddi tsiklik grafikga o'xshaydi va operatsion tizimlarda blokirovkaning
oldini olish uchun, ya'ni birinchi navbatda uni aniqlash orqali topologik
tartib qo'llaniladi.
Topologik tartib asosidagi amaliy masala
Topologik tartibdan foydalanadigan juda keng tarqalgan muammo bu Kurs
jadvali muammosi.
Muammoning bayoni quyidagicha: Sizga universitetingizda o'tishingiz kerak
bo'lgan
kurslar ro'yxati beriladi. Har bir kursda ba'zi yoki nol shartlar
mavjud. Sizning
vazifangiz kurslarni tugata olasizmi yoki yo'qligini aniqlashdir.
Bir lahzaga muammoning kirish yoki chiqishini unutaylik, faqat muammo bayoniga
e'tibor qarataylik.
Misol keltiraylik, sizda 1, 2, 3, 4, 5, 6 kurslar mavjud . 3 - kursni tugatish
uchun siz 2 va 5 -kursni allaqachon tugatgan bo'lishingiz kerak . 4 - kurs uchun siz 1-
kursni bajarishingiz kerak edi. 6 -kurs uchun siz 3 , 4 va 5 -kursni tamomlagan
bo'lishingiz kerak .
Kutib turing, yuqoridagi gaplar bilan bizning tort muhokamamiz o'rtasida
o'xshashlik bormi? Kek pishirayotganda biz keyingi bosqichga o'tishdan oldin
ma'lum qadamlarni bajarishimiz kerak edi va bu erda ham xuddi shunday
masala! Keyingi yoki qolganlarini o'rganish uchun ba'zi kurslarni tugatishimiz
kerak. Buni topologik tartiblash yordamida hal qila olamizmi? Topologik tartiblash
qanday foydali bo'lishi mumkin?
Muammo bayonotiga yana qarang, siz barcha kurslarni tugata olasizmi yoki
yo'qmi, bilib olishingiz kerak. Ushbu joriy misolda siz barcha kurslarni tartibda
yakunlashingiz mumkin.
22

Xo'sh, qachon yoki qanday holatda kurslarni tugatolmaysiz ? O'ylab
ko'ring. Aytaylik, sizga boshqa oraliq kurs qo'shildi, 7 -kurs . 7 -kursning sharti 3 -
kurs , shuningdek, 5 -kursni tugatishdan oldin siz 7 - kursni tamomlashingiz kerak .
Sizningcha, siz kurslarga qatnasha olasizmi? Keling, uni grafikda ifodalash orqali
buni osonlashtiramiz. Siz hozirgacha bu bilan qulay bo'lishingiz kerak!
Dastlab, bizda faqat 1 dan 6 gacha kurslar bo'lganida, u qanday ko'rinishga ega edi:

7 kursi va 7 va 5 ning old shartlari qo'shilgan holda , grafik endi quyidagicha
ko'rinadi:

Grafikga nazar tashlaydigan bo'lsak, siz birinchi navbatda tsiklni izlagan bo'lishingiz
kerak, chunki biz ushbu maqolada shu bilan shug'ullanganmiz. Siz buni
payqadingizmi?
23

$Moviy chiziqqa rioya qiling, bu sizning tsiklingiz! 7 - kurs 3 - kursni , 3 -kurs esa 5 -kursni va 5 -kurs uchun 7 -kursni tamomlashni talab qiladi! Endi siz muammoni sezdingiz, bu kurslarni o taʻ olmaysiz . Endi muammoni hal qila oldingizmi? Biz shunchaki grafikda tsikl bor-yo'qligini tekshirishimiz kerak. Keling, kirish va chiqish shaklini ham ko'rib chiqaylik, sizga [a, b] ega bo'lgan juftliklar ro'yxati beriladi, bu erda a,b a kursini to'ldirishni bildiradi , b kursi old shart. Yuqoridagi grafik uchun berilgan kirish (tsiklsiz) bo'ladi: [[4, 1], [3, 2], [3, 5], [6, 4], [6, 5], [6, 3]] Va chiqish rost bo'ladi , chunki bu grafikda tsikl yo'q va siz barcha kurslarni olishingiz mumkin. Siz allaqachon topologik saralash bo'yicha mutaxassissiz, shuning uchun biz avval yaratgan funktsiyaga qo'shilishi kerak bo'lgan yagona kod bo'lagi ( Kan algoritmi ) biz uchun qo'shnilik ro'yxatini yaratadigan yana bir funktsiyadir va biz uni topological_sort funksiyasiga kiritganimizdan keyin. , tugatdik! C++ da: // declare a list of lists called graph vector<vector<int>> graph; // traverse the input - prerequisites for (auto& e: prerequisites){ graph[e[1]].push_back(e[0]); } 24$

Ushbu qisqa 3 qatorli kod yordamida siz topologik saralash funktsiyasiga berishingiz
mumkin bo'lgan qo'shnilik ro'yxatini yaratdingiz va bu shunday!
Algoritmlarni tahlil qilishning asosiy vazifasi kirish ma'lumotlari hajmining oshib
borishi bilan resurslarga bo'lgan talabni (vaqt va xotira xarajatlari) o'lchash usullarini
aniqlashdir. Shundan so'ng, o'sish sur'ati qonuniyatlarini tavsiflash uchun zarur
bo'lgan matematik mexanizm ishlab chiqiladi. Kirish ma'lumotlari hajmini oshirish
bilan turli xil funktsiyalar; "bitta funktsiya boshqasiga qaraganda tezroq o'sadi"
iborasi nimani anglatishini aniqlab olishga yordam beradi. Ba'zi hollarda, yaxshi
bajarilish vaqtiga erishish yanada murakkab ma'lumotlar tuzilmalaridan
foydalanishga bog'liq va bo'lim oxirida biz bunday ma'lumotlar strukturasining juda
foydali misolini ko'rib chiqamiz: ustuvor navbatlar va ularni uyum(kucha, heap)
asosida amalga oshirish.
Asosiy maqsad - hisoblash muammolarining samarali algoritmlarini izlash. Ushbu
umumiylik darajasida kompyuterni hisoblashning butun sohasi ushbu mavzu bilan
bog'liq bo'lib tuyuladi; bizning yondashuvimiz boshqalardan qanday farq qiladi?
Algoritmlarni ishlab chiqishda umumiy mavzular va loyihalash tamoyillarini
aniqlashga harakat qilamiz. Bizni samarali algoritmlarni loyihalashning asosiy
usullarini minimal ma'lumot bilan namoyish etuvchi paradigmatik masalalar va
usullar qiziqtiradi.
Algoritmni bajarilish qadami - bu ijrochi tomonidan bitta ko‘rsatmaning
bajarilishidir. Bir masalani hal etuvchi ikkita algoritmdan kam qadam talab
qilinayotgani samaraliroqdir. Samaradorlik o‘lchovi - bu bor-yo‘g‘i qadamlar sonidir.
Lekin chuqurroq e’tibor berib qarasak, bu ta’rifdagi mujmal tomonlarni aniqlaymiz.
Ba’zan avval uchragan algoritmlardagidan ko‘ra vaziyat murakkabroq bo’ladi.
Algoritmlar murakkabligi bilan ham farqlanishi mumkin. Algoritmning
murakkabligini uning matnidagi satrlar soni bilan o‘lchaymiz. Shu bilan birga
quyidagi ikki satrni bir tuzilmaning ikki qismi bo‘lgani uchun bittaga hisoblaymiz
TAKRORLANSIN <son> MARTA TAMOM
Mana,
masalan, quyidagi algoritmda:
1
ni qo‘sh
TAKRORLANSIN
6 MARTA 2 ga ko‘paytir
1
ni qo‘sh
TAMOM

1
ni qo‘sh
TAKRORLANSIN
6 MARTA
TAMOM

2
ga ko‘paytir
25

1 ni qo‘sh
faqat
4 ta satr bor. Bu uning murakkabligi 4 ekanligini bildiradi.
Shuni aytib o‘tish joizki, hozir biz ko’rgan algoritm murakkabligi va
samaradorligi o‘zaro tengdir. Masalan, bo‘ri, echki va karamni daryodan o‘tkazish
algoritmi ham 7 satrdan iborat ham u 7 qadamda bajariladi.
Bu yerda bizni kerakli vositamiz bor: bu TAKRORLANSIN - MARTA tuzilmasi.
Shuning uchun oshiruvchi tomonidan 17 sonini hosil qilish algoritmi 3 satrdan iborat
bo‘ladi (eslatma: tuzilma 1 ta satr deb hisoblanadi):
1 ni qo‘sh
TAKRORLANSIN 16 MARTA
1 ni qo‘sh
TAMOM
Endi bu algoritmning samaradorligi 17 ga, murakkabligi esa 17 emas, 3 ga
teng. Askarlar va qayiq masalasi algoritmida 60 ta askarni daryodan o‘tkazish uchun
240 qadam bajariladi, algoritm matni esa 5 satrdan iborat. Bu algoritmning
samaradorligi 240 ga, murakkabligi esa 5 ga teng. Baqa uchun tuzilgan “Baqa toq
sondagi n ta bargli nilufarning 1 tartib raqamli bargiga tushdi. U barcha pashshalarni
yeb 2 tartib raqamli barg ustiga borish algoritmini tuzing.” masalani algoritmida
qadamlar sonini hisoblaymiz:
son + 1 + son — 1 = (n —1):2 +
(n — 1):2 = n — 1.
Demak, har qanday n toq son uchun algoritmni samaradorligi n - 1 ga teng ekan.
Algoritmning murakkabligi esa n toq son nechaga teng bo‘lishidan qat’iy nazar, 5 ga
teng bo‘ladi!
Xulosa. Baqa masalasiga oid algoritmlarning samaradorligi faqat n sonining
qiymatiga bog‘liq. Chunki masala shartida Baqa har bir bargdagi pashshani yeb
chiqishi talab qilinadi. U holda barglar soni n ta ekanligi va Baqa biror bargning
ustida turgandan keyin harakat boshlanganligidan qadamlar soni doimo n-1 ta
bo‘lishi kelib chiqadi.
Haqiqatan, masalan, agar 1 tartib raqamli bargdan 4 tartib raqamlibargga o‘tish
кегак bo‘lsa, u holda barcha imkoniyatlarni 1.1—1.2-rasmlarda, agar 1 tartib raqamli
bargdan 5 tartib raqamli bargga o‘tish kerak bo‘lsa, u holda barcha imkoniyatlarni 1.3
—1.5-rasmlardan ko‘rishimiz mumkin.
26

Va nihoyat, yana bir izoh. Samaradorlik va murakkablik talabi ko‘pincha bir-biri
bilan ziddiyatga kirishadi. Bu mutlaqo tabiiy. Axir, mashina sotib olayotgan
bo‘lsangiz, eng chiroyli va qulay mashinaning eng arzon bo‘Iishiga umid qilmaysiz.
Algoritmlashda ham shunday. Agar sizga juda samarador algoritm kerak bo‘lsa, bu
algoritm boshqalariga nisbatan ancha murakkabroq bo’lishi ehtimoli katta.
Amaliyotda esa oqilona murosaga kelishga to ‘g‘ri keladi.
Hisoblash qobiliyati. Ko'plab muammolarda uchraydigan yana bir xususiyat - bu
ularning asosan diskretligi. Ko'plab muammolarda uchraydigan yana bir xususiyat-bu
ularning asosiy ajralib turishi. Boshqacha qilib aytganda, bu shunday masalalarki,
ularda yechim kombinatorial variantlarning keng to'plamidan qidirib topiladi; maqsad
aniq belgilangan shartlarni qanoatlantiradigan echimni samarali topishdir.
271.5-rasm1.4-rasm

Hisoblash samaradorligi tushunchasini aniqlash uchun, biz birinchi navbatda ish
vaqtining samaradorligiga e'tibor qaratamiz: algoritmlar tez ishlashi kerak. Ammo
algoritmlar boshqa resursrardan foydalanish nuqtai nazaridan ham samarali bo'lishi
mumkinligini tushunish muhimdir. Xususan, algoritm tomonidan ishlatilinadigan
xotira miqdori ham samaradorlikning muhim jixati bo'lishi mumkin.
Algoritm samaradorligi . (1)T: algoritm samarali deb ataladi agar real kirish
ma'lumotlari uchun u tezkor amalga oshirilsa.
(2)T: algoritm samarali deb ataladi agar u sifatli bajarilishni “to’liq
qidirish”(полнiy перебор)ga nisbatan tezroq ta'minlasa.
"To'liq qidirish" usuliga qaraganda ancha yaxshi ishlashni ta'minlaydigan
algoritmlar, deyarli har doim qimmatli evristik g'oyani o'z ichiga oladi, buning
natijasida ushbu yaxshilanishga erishiladi; Bundan tashqari, ular ko'rib chiqilayotgan
masalaning ichki tuzilishi va hisoblash qobiliyati haqida foydali ma'lumotlarni
taqdim etadilar.
Polinomial vaqt samaradorlik ko'rsatkichi sifatida. Tabiiy kombinatorial
masalalarda qidirish vaqti, kirish ma'lumotlari N hajmiga nisbatan eksponensional
o'sishga moyildir; agar o'lcham bittaga ko'paysa, unda imkoniyatlar xajmi bir necha
marta ko'payadi. Bunday masalalarni yechish uchun yaxshi algoritm yanada samarali
miqyoslash modeliga ega bo'lishi kerak; kirish ma'lumotlarining kattalashib borishi
bilan o’zgarmas ko’paytuvchiga(aytaylik, ikki baravar) oshishi bilan algoritmning
bajarilish vaqti ham qandaydir o’zgarmas S ko’paytuvchiga ko'payishi kerak.
(3)T: Agar algoritm polinomial bajarilish vaqtiga ega bo'lsa, u samarali deb
ataladi.
Lekin, polinomial vaqt d ning katta qiymatlarida yaxshi natija bermasligi
mumkin, masalan d>=100 holatda bu son juda katta bo’ladi, natijada polinomial
bajarilish vaqti kattalashib ketadi. Algoritm ishlayveradi. Bu xolda N^d faqat chegara
vazifasini o’taydi.
28

Xulosa:
Ushbu kurs ishni bajarish davomida algoritmlarni samaradorligini va
murakkabligini baholash to’g’risida ko’plab ma’lumotlarga ega bo’lindi. Turli
masalalar orqali algoritmlarni samaradorligi va murakkabligi ko’rildi va solishtirildi.
Optimalikning kriteriyasi bu algoritmning murakkabligi hisoblanadi. Algoritm
murakkabligi odatda ikkiga bo’linadi ya’ni vaqt va hajm bo’yicha murakkablikka
ajratadi. Algoritm murakkabligi qoidasi quyidagicha ya’ni – bu algoritmning
ma’lumotlari hajmi ortishi bilan algoritmning ishlashi vaqtining tezkor ravishda
ortishini belgilovchi funksiya hisoblanadi.
Saralash metodlari ikkiga ajratiladi: ichki saralash va tashqi saralash.
Ichki saralash –ma’lumotlar operativ xotirada joylashgan bo’lib, bunda dasturning
harakatlari sonini (solishtirish, solishtirishlar soni, elementlar almashinuvi va boshqa
metodlarga asoslangan) optimallashtirish muhim ahamiyat kasb etadi;
Tashqi saralash – ma’lumotlar murojaatlarni sekinlashtiruvchi tashqi xotirada
(magnit lenta, baraban, disk va b.qa) joylashgan bo’lib, bunda aynan shu qurilmaga
murojaatlar sonini kamaytirish lozim.
Algoritmninga murakkabligini tahlil qilishni uch xil holatda tahlil qilamiz ya’ni:
Eng yomon holat, o’rtacha holat va eng yaxshi holat.
Eng yomon holatda biz algoritm eng ko’p vaqt sarflaydiganiga qaraymiz.
O'rtacha holatda algoritmni ishlash vaqtini topish uchun , barcha sonlarni topish
uchun ketgan vaqtlarni (har bir sonni alohida-alohida topishga ketgan vaqtlar) o'rta
arifmetigi olinadi.
Eng yaxshi holat bu algoritmni bajarilishi uchun ketgan eng kam vaqtli holatdir.
29

Adabiyotlar ro’yhati:
1. Абрамов С.А. Лекции о сложности алгоритмов.- М.: МЦНМО, 2009.- 256
с.
2. Дональд Кнут Искусство программирования, том 1. Основные
алгоритмы— 3-е изд. — М.: «Вильямс», 2006. — С. 720.
3. Кнут В. Искусство программирования. Т.3. Сортировка и поиск. – 2-е изд.
- Издательский дом “Вильямс”, 2000.
4. Вирт Н. Алгоритмы и структуры данных. Пер. с англ. – М.: Мир, 1989. –
360.
5. Носов В.А. Основы теории алгоритмов и анализа их сложности. – М.,
1992.
30

“TOPOLOGIK SARALASH. ALGORITMNING MURAKKABLIGINI BAHOLASH” Mundarija Kirish I. NAZARIY QISM 1.1. Topologik tartiblash haqida umumiy nazariya…………...………………..... 1.2. Topologik saralashni topish algoritmlari………………...………………….. 1.3. Topologik saralash uchun chuqur birinchi qidiruv 1.4. Kodni amalga oshirish - Topologik tartiblash uchun Kan algoritmi.............. 1.5. Vaqt murakkabligi tahlili ………...…………………..................................... II. AMALIY QISM 2.1. Topologik tartiblash algoritmining qo'llanilishi.………............................... 2.2. Topologik tartib asosidagi amaliy masala…………………………......…...23 Xulosa Adabiyotlar ro’yhati:

KIRISH M а vzuning d о lz а rbligi. T а ‘lim tizimid а gi isl о h а tl а rni а m а ld а j о riy qilishd а bugungi kund а t а ‘lim j а r а y о nining а s о siy t а shkiliy qismi b о ‘lg а n, а m а liy m а shg‘ul о tl а rni s а m а r а d о rligini о shirish, о ‘qitishni ilg‘ о r p е d о g о gik t ех n о l о giy а l а rini q о ‘ll а sh а s о sid а о ‘quv с hil а r v а t а l а b а l а rg а j а h о n а nd о z а l а rd а gi bilim, k о ‘nikm а , m а l а k а l а rni sh а kll а ntirish о ‘quv j а r а y о nini m о ddiy – t ех nik а v а ах b о r о t b а z а si bil а n t а ‘minl а sh yuq о ri d а r а j а li m а l а k а li k а drl а rni t а yy о rl а sh sif а tli о ‘quv – uslubiy, ilmiy h а md а did а ktik m а t е ri а ll а r y а r а tish, t а ‘lim tizimi f а n v а ishl а b с hiq а rish о ‘rt а sid а о ‘z а r о s а m а r а li а l о q а d о rlik о ‘rn а tish d о lz а rb m а s а l а l а rd а n his о bl а n а di. F а n v а t ех nik а j а d а l sur а td а riv о jl а n а y о tg а n h о zirgi p а ytd а y а ngi t ех n о l о giy а d а n f о yd а l а nib d а rs о ‘tishni h а y о t t а q а z о qilm о qd а . Shu nuqt а i n а z а rd а n h о zirgi kund а t а yy о rl а n а y о tg а n е l е ktr о n k о ‘rg а zm а l а r v а d а rslikl а r о ‘quv с hil а rg а m а vzuni tushun а rli b о ‘lishig а y о rd а m b е rm о qd а . H о zirgi kund а t а ‘lim j а r а y о nid а k о mpyut е rning gr а fik imk о niy а tl а rid а n f о yd а l а nishg а b о ‘lg а n qiziqish v а bung а b о ‘lg а n t а l а bning о rt а b о rishi kuz а tilm о qd а . Ushbu kurs ishid а ― Topologik saralash. Algoritmning murakkabligini baholash b о ‘yi с h а multim е di а li е l е ktr о n r е sursl а r y а r а tish, ul а rni t а shkil е tuv с hil а ri, ul а rg а q о ‘yil а dig а n t а l а bl а r, е l е ktr о n r е sursl а r y а r а tish t ех n о l о giy а l а ri uslubl а ri h а qid а fikrl а r yuritil а di. Kurs ishi kirish, 4 b о b, х ul о s а , f о yd а l а nilg а n а d а biy о tl а r r о ‘y ха ti v а il о v а d а n ib о r а t. 2

Topologik tartiblash haqida umumiy nazariya Umumiy ko rinishʻ Topologik saralash yoki Kan algoritmi yo‘naltirilgan asil grafikni shunday tartibga soladigan algoritm bo‘lib, har bir tugun o‘zi ko‘rsatgan barcha tugunlardan oldin qaytarilgan tartibda paydo bo‘ladi, ya’ni agar bizda a --> b bo‘lsa, a b dan oldin paydo bo‘lishi kerak. Topologik tartib Uning asosiy qo'llanilishi yo'naltirilgan grafiklardagi sikllarni aniqlashdir, chunki tsiklni o'z ichiga olgan grafik uchun topologik tartib mumkin emas. Uning qo'llanilishidan ba'zilari: OTda blokirovkani aniqlash, Kurs jadvali muammosi va boshqalar. Qo'llash doirasi  Ushbu maqola Topologik saralashning ishlashi haqida gapiradi .  Topologik saralash zarurati .  Topologik saralashning turli operatsiyalari .  Topologik saralashni amalga oshirish .  Topologik saralashning murakkabligi . Olib ketishlar  Topologik saralashning murakkabligi  Vaqt murakkabligi - O(N + M) O ( N + M ) Bu erda N - tugunlar soni va M - qirralarning soni Topologik tartiblarga kirish Bugun, topologik tartib haqida gapirishdan oldin , keling, tort haqida gapiraylik. Ha, tort. Bugun biz shokoladli tort pishiramiz. Xo'sh, pirojnoe pishirish uchun qanday qadamlarni bajarasiz? 1. Sizda un, pishirish kukuni, pishirish soda, yogurt, yog 'va boshqalar kabi ma'lum ingredientlar mavjud. Bularning barchasini pishirishga qo'yishdan oldin, bu ingredientlarning barchasini yaxshilab aralashtirish kerakligini bilishingizga aminman. 2. Biroq, xamirni (aralashtirilgan ingredientlarni) panga qo'yishdan oldin, avval panani moylash va un bilan to'ldirish kerak. 3. Xamirni quyganingizdan so'ng, uni pishirishingiz kerakligini bilasiz. Ammo keyin yana, tortni pishirishdan oldin, siz pechni oldindan qizdirishingiz kerak. 4. Kekni muzlash uchun u salqin bo'lishi kerak. Lekin uni sovutish uchun avval pishirish kerak. 5. Kekni muzlashdan oldin uni sovutish kerak. Nega bu pirojnoe pishirish haqida? Biz topologik tartibni o'rganmadikmi ? Kutib turing, biz bunga erishmoqdamiz. Yuqorida aytib o'tilgan ushbu to'liq protsedurani grafik sifatida ko'rsatish mumkin. Aniqrog'i, yo'naltirilgan grafik. Nega? Keyingi harakatga o'tishdan oldin ma'lum bir harakatni bajarishimiz kerakligini aytib o'tdik. 3

Asosan, bizda amal qilish kerak bo'lgan tartib bor, shuning uchun agar grafik yo'naltirilgan bo'lsa, albatta mantiqiy bo'ladi, har bir tugunning mazmuni ma'lum bir harakatdir. Grafik qanday ko'rinishi mumkin: Yuqoridagi grafikda ko'rib turganingizdek, avval siz ingredientlarni aralashtirishingiz kerak va, albatta, shundan keyingina xamirni panga qo'shishingiz mumkin. Kekni pishirishdan oldin, panani moylash kerak va hokazo. Bu erda qanday kuzatish mumkin? Grafikni tugunlarning ustuvorligi bo'yicha tartiblash mumkin va topologik tartib aynan shunday! Biz topologik tartibni o'rganish uchun asos yaratdik va endi uni rasmiy ravishda aniqlashimiz mumkin. Topologik tartiblash nima ? Aslida, topologik tartiblash - massiv yoki vektorni yoki ro'yxatni qaytarish orqali yo'naltirilgan grafikni saralaydigan algoritm bo'lib, u har bir tugun o'zi ko'rsatgan barcha tugunlardan oldin paydo bo'ladigan tugunlardan iborat . Bu erda biz uni oddiygina massiv deb ataymiz, siz vektor yoki ro'yxatni ham ishlatishingiz mumkin. Aytaylik, bizda grafik bor edi, a --> b --> c keyin topologik tartiblash algoritmi qaytadi - [a, b, c] . Nega? Chunki, a b ga ishora qiladi , ya'ni a turda b dan oldin kelishi kerak. b c ga ishora qiladi , ya'ni b turda c dan oldin kelishi kerak . Keling, nisbatan murakkabroq misolni ko'rib chiqaylik. 4

Sizningcha, ushbu yo'naltirilgan grafik uchun topologik tartib qanday ko'rinadi? Xo'sh, ko'ramiz. Dastlab, bizning qaytariladigan massiv/vektor yoki tartiblangan massiv/vektor (tartiblangan tartibda grafik tugunlarini o'z ichiga olgan massiv) bo'sh [ ] . Saralangan natijaning boshiga 4 qo'shsak bo'ladimi? Yo'q! Algoritm shuni ko'rsatadiki, agar joriy tugunga ishora qiluvchi tugunlar mavjud bo'lsa, ular birinchi navbatda qo'shilishi kerak. Shunday qilib, tartiblangan natijaga 4 ni qo'shmoqchi bo'lsak, 4 ga ishora qiluvchi tugun(lar) ni tekshirishimiz kerak . Ko'rib turibmizki, tartiblangan natijaga 2 ta tugun qo'shilishi mumkin - 2, 3. Kutib turing, ularga ham ishora qiluvchi tugun bor! Shunday qilib, hammasi 1 qiymatiga ega bo'lgan tugundan boshlanadi! 2 yoki 3 ni qo'shishdan oldin biz 1 ni qo'shishimiz kerak, chunki ikkala tugunning (2, 3) boshqa tugunlari ularga qaratilgan, ya'ni 1 dan oldin tartiblangan natijaga 2 yoki 3 ni qo'shib bo'lmaydi . Shunday qilib, saralangan natijamizga qo'shiladigan birinchi element (massiv / vektor / ro'yxat) aniq 1 bo'ladi, chunki unga ishora qiluvchi boshqa tugunlar yo'q. Bizning tartiblangan natijamiz endi shunday ko'rinadi [1] Keyin qaysi tugunlarni qo'shamiz? '1' tugun ikkita tugunni ko'rsatadi - 2, 3. Qaysi birini qo'shish mumkin bo'lsa, birinchi bo'lib qo'shilishi kerak? Topologik turlanishning o'ziga xosligi Bu topologik tartib haqida . Ko'pgina tartiblash algoritmlarida siz elementlarni saralashning faqat bitta usuli borligini ko'rgan bo'lishingiz kerak. Ikkita yo'l yo'q yoki hech qanday variant mavjud emas. Biroq, topologik tartiblashda ma'lum bir grafikni bir necha usulda saralash mumkin. Yuqoridagi misolda biz ko'rganimizdek , tartiblangan massivga 1 qo'shgandan so'ng , bizda 2 yoki 3 ni qo'shish imkoniyati mavjud . Ammo shuni ta'kidlash kerakki, 2 yoki 3 ning har biri boshqa ustuvorlikka ega emasligi sababli, bu qiymatlarning ikkalasi ham boshqa tugunga o'tishdan oldin tartiblangan massivga kiritilishi kerak. Ikkala element ham 2 va 3 bir xil ustuvorlikka ega. 5

TOPOLOGIK SARALASH. ALGORITMNING MURAKKABLIGINI BAHOLASH 2

12.08.2023

0

2769.92578125 KB

Похожие