Tahrirlash masofasi.vagner-fisher algoritmi

Информация о документе

Цена	12000UZS
Размер	218.1KB
Покупки	0
Дата загрузки	07 Ноябрь 2026
Расширение	docx
Раздел	Дипломные работы
Предмет	Информатика и ИТ

Tahrirlash masofasi.vagner-fisher algoritmi

Купить

I Kirish
Odatda tabiat yoki jamiyatda uchraydigan turli muammo, masala yoki
jarayonlarni o’rganishni EHM yordamida olib topish uchun, birinchi navbatda,
qaralayotgan masala, jarayon – ob’ektning matematik ifodasi, ya’ni matematik
modelini ko’rish kerak bo’ladi. Qaralayotgan ob’ektning matematik modelini
yaratish juda murakkab jarayon bo’lib, o’rganilayotgan ob’ektga bog’liq ravishda
turli soha mutaxassislarining ishtiroki talab etiladi.
Algoritm tushunchasi
Yuqorida qayd qilganimizdek, qo’yilgan biror masalani EHMda echish
uchun, avval uning matematik modelini, keyin algoritmini va programmasini
tuzish kerak bo’ladi. Bu uchlikda algoritm oppi muhim ahamiyatga ega. Endi
algoritm tushunchasining ta’rifi va xossalarini bayon qilamiz.
Algoritm bu oldimizga qo’yilgan masalani echish zarur bo’lgan amallar
ketma-ketligidir.
Masalan kvadrat tenglamani echish uchun quyidagi amallar ketma-ketligi
zarur bo’ladi:
1. a,v,s- koeffiientlar berilgan bo’lsin,
2. Berilgan a,b,c- koeffiientlar yordamida discriminant D=b2-4ac hisoblanadi,
3. D>0 bo’lsa X ½ = (- b )/(2 * a )
4. D<0 bo’lsa haqiqiy echim yo’q
Misol sifatida yana berilgan a, v, s tomonlari bo’yicha uchburchakning yuzasini Geron
formulasi bo’yicha hisoblash masalasini ko’rib o’taylik.
1. A, v, s –uchburchakning tomonlari uzunliklari,
2. R= (a+v+s)/2 –perimetrning yarmi hisoblansin,
3. T=p(r-a)(r-v)(r-s) hisoblansin,
4. S=/~ T hisoblansin.
Yuqoridagi misollardan ko’rinib turibdiki, algoritmning xar bir qadamda
bajariladigan amallar tushinarli va aniq tarzda ifodalangan, hamda chekli sondagi
amallardan keyin aniq natijani olish mumkin. Fikr etilgan, tushinarlilik, aniqlik,
cheklilik va natijaviylik tushunchalari algoritmning asosiy xossalarini tashkil etadi. Bu
tushunchalar oppis pararaflarda alohida ko’rib o’tiladi.
Algoritm so’zi va tushunchasi IX asrda yashab ijod etgan buyuk alloma
Muhammad al-Xorazmiy nomi bilan uzviy bog’liq. Algoritm so’zi Al-Xorazmiy
2

nomini Evropa olimlari tomonidan buzib talaffuz qilinishidan yuzaga kelgan.
AlXorazmiy birinchi bo’lib o’nlik sanoq sistemasining tamoyillarini va undagi to’rtta
amallarni bajarish qoidalarini asoslab bergan.

Algoritmning asosiy xossalari
Diskretlilik (Cheklilik). Bu xossaning mazmuni algoritmlarni doimo
chekli qadamlardan iborat qilib bo’laklash imkoniyati mavjudligida. Ya’ni uni
chekli sondagi oddiy ko’rsatmalar ketma-ketligi shaklida ifodalash mumkin. Agar
kuzatilayotgan jarayonni chekli qadamlardan iborat qilib qo’llay olmasak, uni
algoritm deb bo’lmaydi.
Tushunarlilik. Biz kundalik hayotimizda berilgan algoritmlar bilan
ishlayotgan oppish soatlar, mashinalar, dastgohlar, kompyuterlar, turli avtomatik
va mexanik qurilmalarni kuzatamiz.
Ijrochiga tavsiya etilayotgan ko’rsatmalar, uning uchun tushinarli mazmunda
bo’lishi shart, aks holda ijrochi oddiygina amalni ham bajara olmaydi. Undan
tashqari, ijrochi har qanday amalni bajara olmasligi ham mumkin.
Har bir ijrochining bajarishi mumkin bo’lgan ko’rsatmalar yoki buyruqlar
majmuasi mavjud, u ijrochining ko’rsatmalar tizimi (sistemasi) deyiladi. Demak,
ijrochi uchun berilayotgan har bir ko’rsatma ijrochining ko’rsatmalar tizimiga
mansub bo’lishi lozim.
Ko’rsatmalarni ijrochining ko’rsatmalar tizimiga tegishli bo’ladigan qilib
ifodalay bilishimiz muhim ahamiyatga ega. Masalan, quyi sinfning a’lochi
o’quvchisi “son kvadratga oshirilsin” degan ko’rsatmani tushinmasligi natijasida
bajara olmaydi, lekin “son o’zini o’ziga ko’paytirilsin” shaklidagi ko’rsatmani
bemalol bajaradi, chunki u ko’rsatma mazmunidan ko’payirish amalini bajarish
kerakligini anglaydi.
Aniqlik. Ijrochiga berilayotgan ko’rsatmalar aniq mazmunda bo’lishi
zarur. Chunki ko’rsatmadagi noaniqliklar mo’ljaldagi maqsadga erishishga olib
kelmaydi. Odam uchun tushinarli bo’lgan “3-4 marta silkitilsin”, “5-10 daqiqa
qizdirilsin”, “1-2 qoshiq solinsin”, “tenglamalardan biri echilsin” kabi noaniq
ko’rsatmalar robot yoki kompyuterni qiyin ahvolga solib qo’yadi.
Bundan tashqari, ko’rsatmalarning qaysi ketma-ketlikda bajarilishi ham
muhim ahamiyatga ega. Demak, ko’rsatmalar aniq berilishi va faqat algoritmda
ko’rsatilgan tartibda bajarilishi shart ekan.
Ommaviylik. Har bir algoritm mazmuniga ko’ra bir turdagi
masalalarning barchasi uchun ham o’rinli bo’lishi kerak. YA’ni masaladagi
boshlang’ich ma’lumotlar qanday bo’lishidan qat’iy nazar algorim shu xildagi har
qanday masalani echishga yaroqli bo’lishi kerak. Masalan, ikki oddiy kasrning
3

umumiy mahrajini oppish algoritmi, kasrlarni turlicha o’zgartirib bersangiz ham
ularning umumiy mahrajlarini aniqlab beraveradi. Yoki uchburchanning yuzini
oppish algoritmi, uchburchakning qanday bo’lishidan qat’iy nazar, uning yuzini
hisoblab beraveradi.
Natijaviylik. Har bir algoritm chekli sondagi qadamlardan so’ng albatta
natija berishi shart. Bajariladigan amallar ko’p bo’lsa ham baribir natijaga olib
kelishi kerak. Chekli qadamdan so’ng qo’yilgan masala echimga ega emasligini
aniqlash ham natija hisoblanadi. Agar ko’rilayotgan jarayon cheksiz davom etib
natija bermasa, uni algoritm deb atay olmaymiz.
Algoritmning tasvirlash usullari
Yuqorida ko’rilgan misollarda odatda biz masalani echish algoritmini so’zlar
va matematik formulalar orqali ifodaladik. Lekin algoritm boshqa ko’rinishlarda
ham berilishi mumkin. Biz endi algoritmlarning eng ko’p uchraydigan turlari bilan
tanishamiz.
1. Algoritmning so’zlar orqali ifodalanishi. Bu usulda ijrochi uchun
beriladigan har bir ko’rsatma jumlalar, so’zlar orqali buyruq shaklida beriladi.
2. Algoritmning formulalar bilan berilish usulidan matematika, fizika,
kimyo kabi aniq fanlardagi formulalarni o’rganishda foydalaniladi. Bu usulni
ba’zan analitik ifodalash deyiladi.
3. Algoritmlarning grafik shaklida tasvirlanishida algoritmlar maxsus
oppishc figuralar yordamida tasvirlanadi va bu grafik ko’rinishi blok-sxema
deyiladi.
4. Algoritmning jadval ko’rinishda berilishi. Algoritmning bu tarzda
tasvirlanishdan ham ko’p foydalanamiz. Masalan, maktabda qo’llanib kelinayotgan
to’rt xonali matematik jadvallar yoki turli xil lotereyalar jadvallari.
Funktsiyalarning grafiklarini chizishda ham algoritmlarning qiymatlari jadvali
ko’rinishlaridan foydalanamiz. Bu kabi jadvallardan foydalanish algoritmlari opp
bo’lgan tufayli ularni o’zlashtirib olish oson.
4

II NAZRIY QISM
Dinamik dasturlash (program malash) — matematikaning ko p engʻ
maqbul (optimal) boshqarishga oid masalalar nazariyasi va ularni yechish
usullarini o rganuvchi bo limi. Bu yerda dasturlash (programmalash) tushunchasi
ʻ ʻ
"rejalashtirish", "qaror qabul qilish", ya ni "bir qarorga kelish" ma nolarida ham
ʼ ʼ
qo llaniladi. Bu prinsip D. d.ning asosiy masalasini oxiridan boshlab yechishga
ʻ
imkon beradi. D. d. chekli bosqichli jarayonlardan tashqari, uzluksiz davom
etadigan jarayonlar uchun ham ishlab chiqilgan. U texnika, kosmik parvozlar, xalq
xo jaligini rejalashtirishning turli masalalarida eng maqbul yechimlar topishga
ʻ
imkon beradi. D. d. usuli elektron hisoblash mashinalari, kompyuterlar yordamida
tatbiq qilinadi.
" Dinamik dasturlash" iborasi birinchi marta 1940-yillarda ishlatilgan. R.
Bellman muammoning yechimini topish jarayonini tavsiflash uchun, bu erda bitta
masalaga javobni faqat undan "oldin" keladigan muammoni yechigandan keyin
olish mumkin. 1953 yilda u ushbu ta'rifni zamonaviy ta'rifga aylantirdi.
Bellmanning dinamik dasturlashga qo'shgan hissasi Bellman tenglamasi nomida
abadiylashtirildi, bu dinamik dasturlash nazariyasining markaziy natijasi bo'lib,
optimallashtirish masalasini rekursiv shaklda qayta shakllantiradi.
Dinamik dasturlash odatda muammolarni hal qilishda ikkita yondashuvni qo'llaydi:
• - yuqoridan pastga dinamik dasturlash: muammo kichikroq pastki
vazifalarga bo'linadi, ular hal qilinadi va keyin asl masalani hal qilish uchun
birlashtiriladi;
• - pastdan yuqoriga dinamik dasturlash: asl muammoni hal qilish uchun
keyinchalik zarur bo'lgan barcha kichik vazifalar oldindan hisoblab chiqiladi va
keyin asl muammoning echimini yaratish uchun ishlatiladi.
Dinamik dasturlash masalalarida optimallashtirish jarayoni vaqtga bog'liq
(vaqtning bir necha bosqichlaridan). Shuning uchun optimal yechim har bir
bosqich uchun ketma-ket topiladi, shu bilan birga butun jarayon uchun optimal
echimlar taqdim etiladi. Dinamik dasturlash vazifalari ko'p bosqichli deb
ataladi.Boshqaruv dinamik dasturlashda har bir bosqichda qabul qilingan qarorlar
to'plami butun jarayonning borishiga ta'sir qilish maqsadida chaqiriladi. Amaliy
shartlarda dinamik dasturlash vazifalari rejalashtirish vazifalarining 90% ni tashkil
etadi: ishlab chiqarish hajmlari, xom ashyo ta'minoti, moliyalashtirish miqdorlari
va boshqalar rejalashtirish, bu umumiy maqsadni - yil oxirida maksimal ishlab
chiqarishni ta'minlashi kerak. Va oddiy choralar bilan: uskunani to'liq quvvat bilan
ishlatish, mumkin bo'lgan maksimal sarmoya - umumiy muammoni hal qilib
5

bo'lmaydi, chunki boshqa omillar, masalan, uskunaning eskirishi ta'sir qila
boshlaydi. Bunday holda, bosqichma-bosqich rejalashtirish zarur, ya'ni. muayyan
bosqichlarda eskirgan uskunani almashtirish. Shunday qilib, mahsulotlarni
chiqarish ko'p bosqichli vazifa bo'lib, uning har bir bosqichi aniq maqsadga ta'sir
qiladi.
Dinamik dasturlash masalalarini yechish sxemasi
Muammoni shakllantirish :
Ayrim ob'ektning holati fazo fazo vektori x - bilan tasvirlansin. (x ,, x 2 , ..., x i ) e
R " . Biz jarayonni / V bosqichli deb hisoblaymiz, ya'ni uning evolyutsiyasi sxema
bo'yicha N bosqichda sodir bo'ladi.
Начальное состоян(dastlabki holat),к-й шаг(k-yi qadam),конечное
состоян(yakuniy holat).
Davlatlar o'rtasida o'tish KTH qadam davlat tenglama muvofiq amalga
oshiriladi.Bu yerda d k e R » deb w-o'lchovli ustida nazorat vektor K - qadamdagi ;
6

J' k (x, Ti) - x , d argumentlarining" - o'lchovli vektor funksiyasi .X k - / dx * ~ ', x
* “', x k ~ ' va k , va k , n *) vektorining komponentlarini yozamiz . Shunday qilib,
u bir natija deb taxmin qilinadi to-vo qadam, davlat uchun tizim harakat x uchun
qaysi qadam dastlabki davlat tomonidan faqat belgilanadi X uchun ~ ' va tanlangan
keyin vector
K- bosqichning samaradorligi ko'rsatkichi bu bosqichning berilgan raqamli
xarakteristikasi (maqsadli funktsiyasi) hisoblanadi:
Va butun jarayonning samaradorligi bosqichli maqsadli funktsiyalardan iborat
Fazali traektoriya x va boshqaruvida ikkinchi cheklovlar qo'yiladi:
X k va U k to'plamlari R ", R" ' bo'shliqlarida berilgan
Bundan tashqari, dastlabki va yakuniy shartlar keltirilgan:
Ko'pincha X 0 va X N to'plamlari faza traektoriyasining boshlanishi va oxirini
aniqlaydigan bitta nuqtani o'z ichiga oladi.
Ko'p bosqichli optimallashtirishning umumiy muammosi quyidagicha yozilishi
mumkin:
7

ueU kabi barcha boshqaruv elementlaridan tanlash talab qilinadiMaqsad funksiyasi
(4.18) ekstremal qiymatni (minimal yoki maksimal) qabul qiladigan d ' = ("*', m '
A ) .
Misol 1. Quyidagi optimallashtirish masalasini ko'p bosqichli optimallashtirish
muammosi sifatida shakllantiring.
Berilgan boshlang'ich massasi M bo'lgan iV-bosqichli raketa yordamida, massasi
bo'lgan sayyoralararo stansiya m .
A V = F (y, z),
Bu yerda y - bu bosqichda tezlashtirilgan massa; z - sahnaning o'zi massasi.
Raketa massasining shunday taqsimotini toping ( M) uning bosqichlari
orasidagi oxirgi tezligi maksimal bo'ladi.Biz x k (k = O ... A0) bilan sayyoralararo
stansiyaning massalari yig'indisini va unga tutash k qadamlarni
belgilaymiz .Keyin :
Ko'p bosqichli optimallashtirish masalalari nazariyasi 50-yillarda amerikalik
matematik R.Vellman tomonidan ishlab chiqilgan. Bunday muammoni hal qilish
usuli dinamik protramming usuli deb ataladi va Vellmanning optimallik printsipiga
asoslanadi.
Optimal traektoriyasi xususiyatiga ega ekanligini har bir butun final qismi bilan
boshlanadigan KTH qadam (& = 1, N - 1), jarayonning qolgan qadamlar uchun
optimal hisoblanadi. Boshqacha qilib aytganda, yechimning har bir bosqichida,
butun jarayonning rivojlanishini hisobga olgan holda, faqat bitta qadam
8

optimallashtiriladi. Va shunday qilib, qaror qabul qilishda kelajak hisobga olinadi.
Biroq, har bir jarayonda kelajakka bog'liq bo'lmagan yakuniy k- bosqich mavjud.
Shuning uchun, ushbu bosqichda nazorat maksimal ta'sirni olish imkonini beradi.
K- qadamni rejalashtirib , ular unga ( - 1 ga), keyin ( - 2 ga) va hokazolarni
biriktiradilar. Dinamik dasturlash jarayoni oxiridan boshigacha davom etayotganga
o'xshaydi.K-bosqichni rejalashtirish uchun siz (/: - 1) bosqichda tizim holatini
bilishingiz kerak. Agar (k - 1) qadamdagi holat noma'lum bo'lsa, u holda bu
bosqichda tizimning mumkin bo'lgan holatlari haqida turli xil taxminlar mavjud.
Har bir taxmin uchun oxirgi optimal nazorat tanlash uchun qadam k. Bunday
optimal nazorat shartli optimal deb ataladi.Keling, (k - 1) bosqichdagi jarayonning
mumkin bo'lgan holatlari haqida bir qancha taxminlar qilaylik . Bu holatlarni S k _i
,, S k _ ] 2, ..., S k ^ r deb belgilaymiz . Ikkinchisi, biz bu davlatlar har bir uchun
shartli optimal nazorat topish , ham k , (x t _ ,,), va K 2 (x A ._ ,,), ..., va k r (x 4 , _
r ).Shunday qilib, KTH qadam rejalashtirilgan. Darhaqiqat, (k - 1) bosqichda tizim
qanday holatni qabul qilsa, & -da qanday davom etishi allaqachon ma'lum.Biz (k -
1) bosqichda xuddi shunday harakat qilamiz , k-bosqichda allaqachon tanlangan
shartli optimal boshqaruvlarni hisobga olgan holda faqat shartli optimal
boshqaruvlarni tanlash kerak . Natijada, barcha o'tishlarni tugatgandan so'ng, biz x
° koordinatasini olamiz.
Birinchi qadam uchun biz taxminlar qilmaymiz, chunki x ° qiymati berilgan,
keyin biz allaqachon topilganlarni hisobga olgan holda optimal boshqaruvlarni
topamiz. X ° dan x * gacha o'tib, biz butun jarayon uchun kerakli optimal
boshqaruvni olamiz. Optimallik tamoyilidan foydalanib, optimal boshqariladigan u
,, ..., m v _ , ketma-ketligi bilan qanoatlantirilishi kerak bo'lgan zarur shartlarni
topamiz .
. R.Vellman tomonidan dinamik dasturlash usuli sxemasi
9

Dinamik dasturlash algoritmlarini ishlab chiqish jarayoni
Dinamik dasturlash algoritmlarini yaratish jarayonida siz to'rt bosqichdan iborat
ketma-ketlikni bajarishingiz kerak:
1.Optimal yechimning tuzilishini aytib bering.
2.Optimal yechimning qiymatini rekursiv tarzda aniqlang.
3.Pastdan yuqoriga tahlil yordamida optimal yechim qiymatini hisoblang.
4.Qabul qilingan ma'lumotlarga asoslanib, optimal echimni ishlab chiqing.
Agar muammoning optimal yechimi uning kichik muammolarining optimal
yechimlaridan oqilona tuzilgan bo'lsa, u optimal quyi tuzilmaga ega
bo'ladi.Muammoda optimal quyi tuzilmaning mavjudligi dinamik dasturlash va uni
hal qilish uchun ochko'z algoritmlarning qo'llanilishini aniqlash uchun ishlatiladi.
Masalan, grafikning ba'zi uchlari orasidagi eng qisqa yo'lni topish masalasi kichik
masalalarning optimal echimini o'z ichiga oladi.
Dinamik dasturlash orqali hal qilinadigan ko'plab muammolarni ma'lum bir
yo'naltirilgan asiklik grafikda bir cho'qqidan ikkinchisiga eng qisqa yo'lni topish
sifatida aniqlash mumkin .
1)Eng uzun vaznsiz yo'l muammosi
2)Optimal pastki tuzilmaning yo'qligi
Ba'zan muammoda optimal pastki tuzilma mavjud bo'lmasligi mumkin.
Yo'naltirilgan grafik bilan muammoni ko'rib chiqingG = ( V, E) va tepalar u , v ∈
V, cho'qqidan oddiy yo'lni aniqlash muammosi u tepaga v, qirralarning maksimal
sonidan iborat.Yo'lni ko'rib chiqing q→ r → tbu eng uzun eng oddiy yo'l q ⇝ t...
Yo'lq→ r eng uzun yo'l q ⇝ r? Yo'q, chunki oson yo'lq→ s → t → ruzoqroq. Yo'lr
→ t eng uzun yo'l r ⇝ t? Yana, yo'q, chunki oson yo'lr → q→ s → tuzoqroq.
Shunday qilib, eng uzun vaznsiz yo'lni topish muammosida optimal pastki
tuzilmalar paydo bo'lmaydi. Ushbu vazifani bajarish uchun dinamik dasturlash
printsipi asosida ishlaydigan samarali algoritm hali topilmadi. Aslida, bu NP-to'liq
muammo , ya'ni. uni polinom vaqtida echish qiyin.
Dinamik dasturlash yordamida ularni yechish imkonini beruvchi
masalalarning eng muhim xususiyati quyi vazifalar uchun optimallikdir.
Muammoni shakllantirishga qarab, u segmentda, prefiksda, daraxtda dinamik
dasturlash bo'ladimi, kichik muammolar uchun optimallik muddati har xil bo'lishi
10

mumkin, ammo, umuman olganda, u quyidagicha ifodalanadi: agar mavjud bo'lsa.
muammoni hal qilish jarayonida paydo bo'ladigan ba'zi bir kichik muammo uchun
optimal yechim, keyin uni butun muammoni hal qilish uchun ishlatish
kerak.Muayyan qaytarib bo'lmaydigan ishlab chiqarish jarayonini ko'rib chiqing va
uni yo'naltirilgan va asiklik grafik shaklida tasvirlang. Jarayon bir nechta
shtatlardan o'tadi. Ishlab chiqarish boshlanishi bilan (birinchi holat) biz grafikning
yuqori qismini belgilaymizSva ishlab chiqarishning tugashi (oxirgi holat) T...
Jarayon optimallashtirishni talab qiladi, ya'ni. siz eng yaxshi yo'lni topishingiz
kerakS ⇝ T... U grafikning yuqori qismidan o'tadiU... Optimal yo'l prefiksiS ⇝ U
eng yaxshi yo'ldir S ⇝ U... Endi prefiks bo'yicha dinamik dasturlash uchun
optimallik tamoyilini ko'rib chiqamiz. Shunday qilib, bizda optimal yo'l borS ⇝
Tbu o'tadi U... Prefiksga ruxsat beringD U, ya'ni. dan yo'lS ⇝ U, optimal emas.
Keyin biz optimal bo'lmagan qismni almashtiramizS ⇝ U yo'l S ⇝ T optimal va
yo'l U ⇝ Toxiriga qo'shing. Biz optimal yo'lni olamizS ⇝ T... Kichik muammolar
uchun optimallik printsipi bajarildi. Bular. grafikning bir cho'qqisidan ikkinchisiga
optimal yo'lni olish uchun kichikroq yo'llarning prefikslari optimal bo'lishi kerak.
Misol tariqasida quyidagi masalani ko'rib chiqing: asiklik yo'naltirilgan
og'irlikli grafik berilgan, u dan v gacha bo'lgan eng qisqa yo'lning og'irligini topish
kerak. Prefiksda optimallik tamoyilidan foydalanamiz.
Maylid - funktsiya, qaerda d( men ) dan eng qisqa yo'lning og'irligi u v i... Bu
aniqd( u ) ga teng 0... Mayliw ( i , j ) - qovurg'a og'irligi dan i v j... Grafikni
topologik tartiblash tartibida aylanib o'tamiz . Biz quyidagi nisbatlarni olamiz:
d( i ) =minj : j ⇝ i( d( j ) + w ( j , i ) ).Grafikni topologik tartiblash tartibida
aylanib o'tganimiz uchun , keyini- hamma uchun qadam d( j ) (j dan chekka borki j
v i) allaqachon optimal javoblar tayinlangan va shuning uchun d( men ) optimal
javob ham tayinlanadi.
Funktsiyani hisoblashni xohlaysiz f( 1 , n )... Printsip quyidagicha: barcha
segmentlar uchun ruxsat beringi, j (qaerda u ⩽ i ⩽ j ⩽ v) funksiya uchun optimal
javob ma’lum f( i , j )... Keyin hisoblab chiqamizf( u , v ) shunday orqali f( i , j )...
Misol tariqasida, quyidagi klassik masalani ko'rib chiqing: n uzunlikdagi qator
berilgan, siz maksimal subpalindromni topishingiz kerak (palindrom bo'lgan
maksimal uzunlikning pastki qatori). Maylid( i , j ) - belgi bilan boshlanadigan
pastki qator uchun muammoga javob i va xarakterda tugaydi j... Bu aniqd( i , j ) =
0 Barcha uchun i , j , shu kabi i > j va d( i , i ) = 1 Barcha uchun i... uchun
qiymatini hisoblashimiz kerak deylikd( i , j ), va qiymati d Barcha uchun l , rshu
11

kabi i ⩽ l ⩽ r ⩽ jallaqachon hisoblab chiqilgan va ular optimal hisoblanadi. Ikkita
holatni ko'rib chiqing:
s ( i ) ≠ s ( j ), keyin d( i , j ) = maksimal ( d( i , j - 1 ) , d( i + 1 , j ) )
s ( i ) = s ( j ), keyin d( i , j ) = d( i + 1 , j - 1 ) + 2
Isbot:
Shunday qilib s ( i ) ≠ s ( j ), belgilar s ( i ) va s ( j ) bir vaqtning o'zida
maksimal subpalindromga kiritilishi mumkin emas, ya'ni ham s ( i ) maksimal
subpalindromga kiritilgan (keyin uning uzunligi d[ i , j - 1 ]), yoki s ( j ) maksimal
subpalindromga kiradi (keyin uning uzunligi d[ i + 1 , j ]), yoki ikkalasi ham
maksimal subpalindromga kiritilmagan (keyin uning uzunligi). = d[ i , j - 1 ] = d[ i
+ 1 , j ]).
Vazifalarga misollar:
1.Ifodada belgilarni joylashtirish muammosi
2.Matritsani ko'paytirish tartibi masalasi
3.Kontekstsiz grammatikada xulosa chiqarish muammosi, Coca-Yanger-Kasami
algoritmi
4.Optimal prefiks kodining tartibini saqlash muammosi
5.Kesish nuqtasi monotonligi
6.Eng uzun keng tarqalgan keyingi ketma-ketlik muammosi
7.Tahririyat masofasi muammosi, Vagner-Fisher algoritmi
8.Damerau-Levenshteyn masofasi muammosi
9.Kichik to'plamlarda optimallik printsipi
Funktsiyani hisoblaymiz f( A ), A- bir nechta to'plam. Printsip quyidagicha:
barcha to'plamlar uchun ruxsat bering B (qaerda B ∈ A) funksiya uchun optimal
javob ma’lum f( B )... Keyin hisoblab chiqamizf( A ) shunday orqali f( B )...
belgilaymiz d[ i ] [ m a s k ] yuqoridan yo'lning eng kam xarajati sifatida i tepaga
0o'tish (yuqorini hisobga olmaganda i) barcha o'sha va faqat o'sha uchlari uchun
bir marta jbuning uchun m a skj= 1 (bular. d[ i ] [ m a s k ] dan optimal yo'l
allaqachon topilgan i- cho'qqigacha 0th o'sha cho'qqilar orqali o'tib qaerda m a skj=
1... Agarm a skj= 0, keyin bu uchlari hali tashrif buyurilmagan). Keyin kichik
to'plamlarda optimallik printsipidan foydalanamiz. Dastlabki grafikdagi minimal
12

Gamilton siklining narxi qiymat bo'ladid[ 0 ] [2n- 1 ] - yo'l narxi 0-da cho'qqilar 0-
yu, kerak bo'lsa, barcha cho'qqilarni ziyorat qiling.
Memoizatsiya (inglizcha memoization) - takroriy hisob-kitoblarni oldini
olish uchun funktsiyalarni bajarish natijalarini saqlash.Bu kompyuter dasturlarini
bajarish tezligini oshirish uchun qo'llaniladigan optimallashtirish usullaridan
biridir. Funksiyani chaqirishdan oldin funksiya avval chaqirilganmi yoki yo‘qmi
tekshiriladi.
Misol tariqasida raqamlangan Fibonachchi raqamini topish masalasini ko'rib
chiqing:
int Fibonacci(int n):
if n <= 1
return 1
a = Fibonacci(n - 1)
b = Fibonacci(n - 2)
return a + b
С мемоизацией:
int Fibonacci(int n):
if n <= 1
return 1
if fib [ n ] == -1 // проверка на то, не посчитали ли мы это число раньше;
посчитанные числа хранятся в массиве fib
fib[n] = Fibonacci(n - 1) + Fibonacci(n - 2)
return fib[n]

13

III NAZARIY QISM
Masofani tahrirlash
Hisoblash tilshunosligi va informatika fanida tahrirlash masofasi bir qatorni
boshqasiga aylantirish uchun zarur bo'lgan minimal operatsiyalar sonini hisoblash
orqali ikki qatorning (masalan, so'zlarning) bir-biriga o'xshashligini aniqlashning
bir usuli hisoblanadi. Masofalarni tahrirlash tabiiy tilni qayta ishlashda ilovalarni
topadi, bunda avtomatik imlo tuzatish lug'atdan so'zlayotgan so'zga nisbatan past
masofaga ega so'zlarni tanlash orqali noto'g'ri yozilgan so'z uchun nomzod
tuzatishlarini aniqlashi mumkin. Bioinformatikada u A, C, G va T harflarining
qatorlari sifatida ko'rish mumkin bo'lgan DNK ketma-ketliklarining o'xshashligini
miqdoriy aniqlash uchun ishlatilishi mumkin.
Tahrirlash masofasining turli xil ta'riflari qator operatsiyalarining turli
to'plamlaridan foydalanadi. Levenshteyn masofaviy operatsiyalari qatordagi
belgini olib tashlash, kiritish yoki almashtirishdir. Eng keng tarqalgan ko'rsatkich
bo'lib, Levenshtein masofasi atamasi ko'pincha masofani tahrirlash bilan
almashtiriladi.[1]
Tahrirlash masofasining har xil turlari qator operatsiyalarining turli to'plamlariga
imkon beradi. Masalan:
Levenshtein masofasi o'chirish, kiritish va almashtirish imkonini beradi.
Eng uzun umumiy ketma-ketlik (LCS) masofasi almashtirishga emas, balki faqat
kiritish va o chirishga imkon beradi.ʻ
Hamming masofasi faqat almashtirishga imkon beradi, shuning uchun u faqat bir
xil uzunlikdagi satrlarga tegishli.
Damerau-Levenshtein masofasi ikkita qo'shni belgilarni kiritish, o'chirish,
almashtirish va almashtirish imkonini beradi.
Jaro masofasi faqat transpozitsiyaga imkon beradi.
Ba'zi tahrirlash masofalari ruxsat etilgan tahrirlash operatsiyalarining
ma'lum to'plami bilan hisoblangan parametrlash mumkin bo'lgan ko'rsatkich
sifatida aniqlanadi va har bir operatsiyaga xarajat (ehtimol cheksiz) tayinlanadi. Bu
Smit-Uoterman algoritmi kabi DNK ketma-ketligini moslashtirish algoritmlari
14

bilan yanada umumlashtiriladi, bu esa operatsiya narxini qayerda qo'llanilishiga
bog'liq qiladi.
Levenshteyn masofasi
S alifbosida ikkita a va b qator berilgan (masalan, ASCII belgilar to‘plami,
baytlar to‘plami [0..255] va boshqalar), tahrirlash masofasi d(a, b) tahrirlashning
minimal vaznli qatoridir. a ni b ga aylantiruvchi amallar. Tahrirlash
operatsiyalarining eng oddiy to'plamlaridan biri 1966 yilda Levenshtein tomonidan
aniqlangan:[2]
Bitta belgini kiritish. Agar a = uv bo'lsa, x belgisini qo'yish uxv hosil qiladi. Buni e
→ x deb ham belgilash mumkin, bo'sh satrni e dan foydalanib belgilash mumkin.
Bitta belgini o chirish uxv ni uv (x→e) ga o zgartiradi.ʻ ʻ
Bitta x belgisini y ≠ x belgisiga almashtirish uxv ni uv (x→y) ga o‘zgartiradi.
Levenshteynning asl ta'rifida bu operatsiyalarning har biri birlik narxiga ega
(belgining o'zi o'rniga nol xarajat bo'lishi bundan mustasno), shuning uchun
Levenshteyn masofasi a ni b ga aylantirish uchun zarur bo'lgan minimal
operatsiyalar soniga teng. Umumiyroq ta rif, manfiy bo lmagan og irlik
ʼ ʻ ʻ
funksiyalarini wins(x), wdel(x) va wsub(x, y) operatsiyalari bilan bog laydi.
ʻ
Qo'shimcha ibtidoiy operatsiyalar taklif qilingan. Damerau-Levenshteyn masofasi
bitta tahrirlashda keng tarqalgan xato hisoblanadi: ikki qo'shni belgining
transpozitsiyasi, rasmiy ravishda uxyvni uyxv ga o'zgartiradigan operatsiya bilan
tavsiflanadi.OCR chiqishini to g rilash vazifasi uchun birlashma va bo lish
ʻ ʻ ʻ
amallari qo llanilib, ular bitta belgini juftlikka yoki aksincha almashtiradilar.
ʻ
Tahrirlash masofasining boshqa variantlari operatsiyalar to'plamini cheklash
orqali olinadi. Eng uzun umumiy keyingi ketma-ketlik (LCS) masofasi birlik
narxida faqat ikkita tahrirlash amali sifatida kiritish va o chirish bilan tahrirlash
ʻ
masofasidir.[1]:
37 Xuddi shunday, faqat almashtirishlarga ruxsat berish orqali
(yana birlik narxida) Hamming masofasi olinadi; bu teng uzunlikdagi satrlar bilan
cheklanishi kerak.[1]Jaro-Winkler masofasini faqat transpozitsiyalarga ruxsat
berilgan tahrirlash masofasidan olish mumkin.Masofani manfiy bo'lmagan xarajat
bilan tahrirlash quyidagi shartlar bajarilganda metrikaning aksiomalarini qondiradi
va satrlarning metrik fazosini keltirib chiqaradi.Har bir tahrirlash operatsiyasi
ijobiy narxga ega;Har bir operatsiya uchun teng narxga ega teskari operatsiya
mavjud.Ushbu xossalar bilan metrik aksiomalar quyidagicha qanoatlantiriladi:
d(a, b) = 0, agar a=b bo'lsa, chunki har bir satr aniq nol amallar yordamida o'ziga
15

$trivial tarzda o'zgartirilishi mumkin.a ≠ b bo'lganda d(a, b) > 0, chunki bu nolga teng bo'lmagan xarajat bilan kamida bitta operatsiyani talab qiladi.d(a, b) = d(b, a) har bir operatsiya narxining tengligi va uning teskarisi. Uchburchak tengsizligi: d(a, c) ≤ d(a, b) + d(b, c). Levenshtein masofasi va birlik narxi bilan LCS masofasi yuqoridagi shartlarni va shuning uchun metrik aksiomalarni qondiradi. Adabiyotda tegishli ko'rsatkichlar bo'lmagan tahrirlash masofasi variantlari ham ko'rib chiqilgan. Birlik tahrirlash masofasining boshqa foydali xususiyatlariga quyidagilar kiradi: LCS masofasi yuqorida bir juft qator uzunliklari yig‘indisi bilan chegaralangan.LCS masofasi Levenshtein masofasining yuqori chegarasidir. Bir xil uzunlikdagi torlar uchun Hamming masofasi Levenshteyn masofasining yuqori chegarasi.Narx/vaznlardan qat'i nazar, quyidagi xususiyat barcha tahrirlash masofalariga ega: Agar a va b umumiy prefiksga ega bo'lsa, bu prefiks masofaga ta'sir qilmaydi. Rasmiy ravishda, a = uv va b = uw bo'lganda, d(a, b) = d(v, w).[4] Bu masofani tahrirlash va skriptlarni tahrirlash bilan bog'liq ko'plab hisoblarni tezlashtirishga imkon beradi, chunki umumiy prefiks va qo'shimchalarni chiziqli vaqt ichida o'tkazib yuborish mumkin.Ushbu takrorlanishni baholashning oddiy, rekursiv usuli eksponensial vaqtni oladi. Shuning uchun, u odatda Vagner va Fisherga tegishli bo'lgan dinamik dasturlash algoritmi yordamida hisoblanadi , garchi u bir nechta ixtirolar tarixiga ega. Vagner-Fischer algoritmi tugallangandan so'ng, tahrirlash operatsiyalarining minimal ketma-ketligi {\displaystyle d_{mn}}d_{mn} dan boshlab dinamik dasturlash algoritmi davomida foydalanilgan amallarning orqa izi sifatida o'qilishi mumkin. To'liq dinamik dasturlash jadvali tuzilganda uning fazoviy murakkabligi ham D(mn); Bu algoritm har qanday lahzada xotirada faqat ikkita satr (yoki ikkita ustun) bo'lishini kuzatish orqali uni D(min(m,n)) ga oshirish mumkin. Biroq, bu optimallashtirish tahrirlash operatsiyalarining minimal seriyasini o'qishni imkonsiz qiladi.Bu muammoning chiziqli-fazo yechimi Xirshberg algoritmi tomonidan taklif qilingan. Ukkonen bir nechta variantni tavsiflaydi, ulardan biri ikkita satr va maksimal tahrir masofasi s oladi va min(s, d) ni qaytaradi. U bunga faqat dinamik dasturlash jadvalining bir qismini diagonali atrofida hisoblash va saqlash orqali erishadi. Bu algoritm O(s×min(m,n)) vaqtini oladi, bunda m va n qatorlar uzunligi. 16$

Fazoning murakkabligi tahrirlash ketma-ketligini o qish zarurligiga qarab O(s2)ʻ
yoki O(s) dir.
Landau, Myers va Shmidt tomonidan amalga oshirilgan keyingi takomillashtirish
O(s2 + max(m,n)) vaqt algoritmini beradi.
Ilovalarni tahrirlash.Tahrirlash masofasi hisoblash biologiyasi va tabiiy tilni qayta
ishlashda ilovalarni topadi, masalan. imlo xatolarini yoki OCR xatolarini tuzatish
va taxminiy satrlarni moslashtirish, bunda maqsad kichik miqdordagi farqlar
kutilishi kerak bo'lgan holatlarda ko'p uzunroq matnlardagi qisqa satrlar uchun
mosliklarni topishdir.
Turli xil algoritmlar mavjud bo'lib, ular bir-biriga bog'liq bo'lgan muammolarni hal
qilish uchun juft qatorlar orasidagi masofani hisoblashdan tashqari muammolarni
hal qiladi.
Xirshberg algoritmi ikkita satrning optimal tekislanishini hisoblaydi, bunda
optimallik tahrirlash masofasini minimallashtirish sifatida aniqlanadi.Taxminiy
satr moslashuvi tahrirlash masofasi nuqtai nazaridan shakllantirilishi mumkin.
Ukkonenning 1985 yildagi algoritmi naqsh deb ataladigan p qatorni va doimiy k ni
oladi; keyin u ixtiyoriy s qatorida p ga tahrirlash masofasi ko pi bilan k[11]
ʻ
bo lgan pastki qatorni topadigan deterministik chekli holat avtomatini quradi
ʻ
(qarang. Aho-Korasik algoritmiga qarang, u xuddi shu tarzda istalgan birini
qidirish uchun avtomat tuzadi. bir qator naqshlar, lekin tahrirlash operatsiyalariga
ruxsat bermasdan). Taxminiy satrlarni moslashtirish uchun shunga o'xshash
algoritm bitap algoritmi bo'lib, tahrirlash masofasi nuqtai nazaridan ham
aniqlanadi.
Damerau-Levenshtein masofasi, xuddi Levenshtein metrikasi kabi, ikki
qatorning "o'xshashligi" o'lchovidir. Algoritm dastlab odam tomonidan terilgan
matnlarni solishtirish uchun ishlab chiqilgan bo'lsa ham, uni qidirish algoritmi
loyqa qidiruvni amalga oshirishda, shuningdek, bioinformatikada (DNKni
taqqoslashda) qo'llanilishini topadi (Damerau inson xatolarining 80 foizini
ko'rsatdi. matn terishda qo shni belgilarning o zgarishi, belgini o tkazib yuborish,
ʻ ʻ ʻ
yangi belgi qo shish va belgilardagi xatolikdir.Shuning uchun Damerau-
ʻ
Levenshteyn metrikasi ko pincha tahririy dasturlarda imloni tekshirish uchun
ʻ
ishlatiladi).
Soddalashtirilgan algoritm
Muammoni to'g'ri hal qilmaydi, lekin amalda foydali bo'lishi mumkin.
17

Keyinchalik, biz quyidagi belgidan foydalanamiz: S va T - Damerau-Levenshtein
masofasini topish kerak bo'lgan chiziqlar; M va N - mos ravishda ularning
uzunligi.
Levenshteyn masofasidan qidirish algoritmidan bitta chek bilan farq qiluvchi
algoritmni ko'rib chiqaylik (biz D matritsasini saqlaymiz, bu erda D (i, j) satr
prefikslari orasidagi masofa: S qatorining birinchi i belgilari va birinchi j belgilari.
Shunday qilib, javob olish uchun takrorlanish munosabati yordamida D
matritsasini to'ldirish kerak. Algoritm murakkabligi: O (M ⋅ N). Xotira narxi: O
(M ⋅ N).
Algoritm psevdokodi:
int DamerauLevenshteinDistance(S: char[1..M] , T: char[1..N] ; deleteCost,
insertCost, replaceCost, transposeCost: int ):
d: int[0..M][0..N]

// База динамики
d[0][0] = 0
for i = 1 to M
d[i][0] = d[i - 1][0] + deleteCost
for j = 1 to N
d[0][j] = d[0][j - 1] + insertCost

for i = 1 to M
for j = 1 to N
// Стоимость замены
if S[i] == T[j]
d[i][j] = d[i - 1][j - 1]
else
d[i][j] = d[i - 1][j - 1] + replaceCost
d[i][j] = min(
d[i][j], // замена
d[i - 1][j ] + deleteCost, // удаление
d[i ][j - 1] + insertCost // вставка
)
if (i > 1 and j > 1 and S[i] == T[j - 1] and S[i - 1] == T[j])
d[i][j] = min(
d[i][j],
18

d[i - 2][j - 2] + transposeCost // транспозиция
)
return d[M][N]
Qarama-qarshi misol: S = 'CA' va T = 'ABC'. Satrlar orasidagi Damerau-
Levenshteyn masofasi 2 ga teng (CA → AC → ABC), lekin yuqoridagi funksiya 3
ni qaytaradi. Gap shundaki, bu soddalashtirilgan algoritmdan foydalanish
cheklovni qo‘yadi: har qanday pastki qatorni ko‘pi bilan bir marta tahrirlash
mumkin. Shuning uchun AC → ABC o'tish mumkin emas va harakatlar ketma-
ketligi quyidagicha: (CA → A → AB → ABC).
Soddalashtirilgan Damerau-Levenshtein algoritmi metrik emas, chunki uchburchak
qoidasi bajarilmaydi: DLD ('CA', 'AC') + DLD ('AC', 'ABC') DLD ('CA', 'ABC' ).
Ko'pgina amaliy muammolarning holati pastki qatorlarni bir necha marta
tahrirlashni anglatmaydi, shuning uchun soddalashtirilgan algoritm ko'pincha
etarli. Quyida Damerau-Levenshtein masofasini topish muammosini to'g'ri hal
qiladigan murakkabroq algoritm mavjud.Tasdiqlash faqat formula uchun talab
qilinadi, uning ma'nosi transpozitsiyani (A) ishlatmasdan o'tish narxini
operatsiyalar sonidagi transpozitsiyani o'z ichiga olgan o'tish narxini
solishtirishdir; qolgan formulalar xuddi Vagner-Fisher algoritmini isbotlashdagi
kabi asoslanadi. Ammo haqiqatan ham, keyingi ketma-ketlikni bir necha marta
tahrir qilganda, har doim ikkita turdagi operatsiyalarning optimal ketma-ketligi
mavjud:
Qo'shni belgilarni o'zgartiring, so'ngra ular orasiga ma'lum miqdordagi belgilarni
qo'ying;
Bir nechta belgilarni olib tashlang va keyin qo'shni belgilarni o'zgartiring.
U holda S [i] belgisi T [1] da .. T [j] j ′ pozitsiyasida, T [j] belgisi S [1] da .. S [i] i ′
pozitsiyasida bo'lsa. ; keyin T [1] .. T [j] ni S [1] dan olish mumkin .. S [i]
belgilarini S [i ′ + 1] o chirish orqali .. S [i − 1] qo shnisining transpozitsiyasi
ʻ ʻ
orqali S [i ′ ] va S [i] belgilari va T [j + 1] belgilarini kiritish .. T [j - 1]. Bunga jami
D (i ′, j ′) + (i-i′-1) ⋅ deleteCost + transposeCost + (j-j′-1) ⋅ insertCost operatsiyalari
sarflanadi, bu ( ∗ ) da tasvirlangan. Shuning uchun biz transpozitsiyali va
transpozitsiyasiz ishni ko'rib chiqib, optimal operatsiyalar ketma-ketligini tanladik.
Algoritm murakkabligi: O (M ⋅ N ⋅ max (M, N)). Xotira narxi: O (M ⋅ N). Biroq,
algoritm tezligini O (M ⋅ N) ga oshirish mumkin.
Algoritm psevdokodi:
19

int DamerauLevenshteinDistance(S: char[1..M] , T: char[1..N] ; deleteCost,
insertCost, replaceCost, transposeCost: int ):
// Обработка крайних случаев
if (S == "")
if (T == "")
return 0
else
return N
else if (T == "")
return M
D: int[0..M + 1][0..N + 1] // Динамика
INF = (M + N) * max(deleteCost, insertCost, replaceCost, transposeCost) //
Большая константа

// База индукции
D[0][0] = INF
for i = 0 to M
D[i + 1][1] = i * deleteCost
D[i + 1][0] = INF
for j = 0 to N
D[1][j + 1] = j * insertCost
D[0][j + 1] = INF

lastPosition: int[0..количество различных символов в S и T]
//для каждого элемента C алфавита задано значение lastPosition[C]

foreach ( char Letter in (S + T))
lastPosition[Letter] = 0

for i = 1 to M
last = 0
for j = 1 to N
i' = lastPosition[T[j]]
j' = last
if S[i] == T[j]
D[i + 1][j + 1] = D[i][j]
last = j
else
20

D[i + 1][j + 1] = min(D[i][j] + replaceCost, D[i + 1][j] + insertCost, D[i]
[j + 1] + deleteCost)
D[i + 1][j + 1] = min(D[i + 1][j + 1], D[i'][j'] + (i - i' - 1) ⋅ ⋅ deleteCost +
transposeCost + (j - j' - 1) ⋅ ⋅ insertCost)
lastPosition[S[i]] = i

return D[M][N]
Masofa - bu ikki joyning bir-biridan qanchalik uzoqligini ko'rsatish uchun
biz tez-tez ishlatadigan so'z. Xuddi shunday, massivlarni moslashtirish kontekstida
bu ikki massiv qanchalik farq qilishini ko'rsatadi. Masofani o'lchash uchun turli xil
ko'rsatkichlar mavjud, ulardan biri odatda Levenshtein masofasi bo'lib, men
qoidalarni tushuntirmoqchiman.
Levenshtein masofasi quyidagi operatsiyalarni torli masofa uchun tegishli
jarimalar bilan ishlatadi.
Qo'shimcha: "casle" => "qal'a" . 't' qo'shiladi. Penalti: 1
O chirish: “maktab” => “maktab” . "o" o'chiriladi. Penalti: 1ʻ
O'zgartirish: "blok" => "blokk". "k" "c" bilan almashtiriladi. Penalti: 2
O'zgartirish jazosi ko'proq bo'lishining sababi shundaki, u o'z mohiyatiga ko'ra
o'chirish va tartibda qo'shishdir.
Minimal masofa muammosi.Minimal masofa muammosi ikkita satr orasidagi
minimal masofani topishga qaratilgan. Biz ikkita satrda barcha mumkin bo'lgan
operatsiyalarni qoplash uchun rekursiv funktsiyani ishlab chiqishimiz mumkin,
ikkita minimal mumkin bo'lgan masofa.
def
levenshtein_distance (a,b):
return l_d (a,b)
def l_d (a,b):
if min ( len (a), len (b)) == 0 : # recursion terminator
return max ( len (a), len (b))
k = 0 if a[ -1 ] == b[ -1 ] else 2
return min ( l_d (a[: -1 ],b) + 1 , # addition
21

$l_d (a,b[: -1 ]) + 1 , # deletion l_d (a[: -1 ],b[: -1 ]) + k # substitution ) print levenshtein_distance ( "al" , "alis" ) print levenshtein_distance ( "ezgi" , "ezgy" ) print levenshtein_distance ( "seyhmus" , "sehmuz" ) Axborot nazariyasi va informatika fanida Damerau-Levenshteyn masofasi (Fridrix J. Damerau va Vladimir I. Levenshteyn [1][2][3] nomi bilan atalgan) ikki ketma-ketlik orasidagi tahrir masofasini o lchash uchun qator ko rsatkichidir.ʻ ʻ Damerau-Levenshtein ikki so'z orasidagi norasmiy masofa - bu bir so'zni boshqasiga o'zgartirish uchun zarur bo'lgan minimal operatsiyalar soni (bitta belgini qo'shish, o'chirish yoki almashtirish yoki ikkita qo'shni belgilarning transpozitsiyasidan iborat).Damerau-Levenshteyn masofasi klassik Levenshteyn masofasidan uchta klassik bitta belgidan iborat tahrirlash operatsiyalariga (qo'shish, o'chirish va almashtirish) qo'shimcha ravishda uning ruxsat etilgan operatsiyalari qatoriga transpozitsiyalarni kiritish bilan farq qiladi. Damerau o zining muhim maqolasida ma lumot-qidiruv tizimidagi imlo ʻ ʼ xatolarini tekshirishda 80% dan ortig i to rt turdan birining bitta xatosi natijasi ʻ ʻ ekanligini ta kidladi. Damerauning maqolasi faqat bitta tahrirlash operatsiyasi ʼ bilan tuzatilishi mumkin bo'lgan imlo xatolarini ko'rib chiqdi. Dastlabki motivatsiya imlo tekshiruvi kabi ilovalarni yaxshilash uchun inson xatolari orasidagi masofani o'lchash bo'lsa-da, Damerau-Levenshtein masofasi biologiyada oqsil ketma-ketligi o'rtasidagi o'zgarishlarni o'lchash uchun ham qo'llanilgan. {\displaystyle a}a va {\displaystyle b}b qatorlari orasidagi Damerau-Levenshteyn masofasini ifodalash uchun funksiya {\displaystyle d_{a,b}(i,j)}d_{a,b}(i, j) aniqlanadi, uning qiymati {\displaystyle i}i-simvol prefiksi (boshlang‘ich pastki qator) {\displaystyle a}a va {\displaystyle j} j-simvol prefiksi {\displaystyle b} orasidagi masofadir. Ikkita algoritm keltirilgan: birinchisi, oddiyroq, optimal qatorni tekislash masofasi yoki cheklangan tahrir masofasi deb nomlanuvchini hisoblaydi,[7], ikkinchisi qo'shni transpozitsiyalar bilan Damerau-Levenshtein masofasini hisoblaydi. Transpozitsiyalarni qo'shish sezilarli murakkablikni oshiradi. Ikkala algoritm o'rtasidagi farq shundan iboratki, optimal satrlarni tekislash algoritmi hech qanday pastki qator bir martadan ortiq tahrir qilinmasligi sharti bilan satrlarni tenglashtirish uchun zarur bo'lgan tahrirlash operatsiyalari sonini hisoblaydi, 22$

ikkinchisi esa bunday cheklovni taqdim etmaydi.Masalan, CA va ABC o'rtasidagi
tahrirlash masofasini oling. Damerau–Levenshteyn masofasi LD(CA, ABC) = 2,
chunki CA → AC → ABC, lekin optimal satrlarni tekislash masofasi OSA(CA,
ABC) = 3, chunki agar CA → AC operatsiyasi ishlatilsa, undan foydalanish
mumkin emas. AC → ABC, chunki bu pastki qatorni bir necha marta tahrirlashni
talab qiladi, bu OSAda ruxsat etilmaydi va shuning uchun operatsiyalarning eng
qisqa ketma-ketligi CA → A → AB → ABC hisoblanadi. E'tibor bering, optimal
qatorni tekislash masofasi uchun uchburchak tengsizligi bajarilmaydi: OSA(CA,
AC) + OSA(AC, ABC) < OSA(CA, ABC) va shuning uchun u haqiqiy ko'rsatkich
emas.
Optimal satrlarni tekislash masofasi.Optimal satrlarni tekislash masofasini
Levenshtein masofasini hisoblaydigan Vagner-Fischer dinamik dasturlash
algoritmining oddiy kengaytmasi yordamida hisoblash mumkin. Psevdokodda:
algorithm OSA-distance is
input : strings a[1..length(a)], b[1..length(b)]
output : distance, integer

let d[0..length(a), 0..length(b)] be a 2-d array of integers, dimensions length(a)
+1, length(b)+1
// note that d is zero-indexed, while a and b are one-indexed.

for i := 0 to length(a) inclusive do
d[i, 0] := i
for j := 0 to length(b) inclusive do
d[0, j] := j

for i := 1 to length(a) inclusive do
for j := 1 to length(b) inclusive do
if a[i] = b[j] then
cost := 0
else
cost := 1
d[i, j] := minimum(d[i-1, j] + 1, // deletion
d[i, j-1] + 1, // insertion
d[i-1, j-1] + cost) // substitution
if i > 1 and j > 1 and a[i] = b[j-1] and a[i-1] = b[j] then
23

d[i, j] := minimum(d[i, j],
d[i-2, j-2] + 1) // transposition
return d[length(a), length(b)]
The difference from the algorithm for Levenshtein distance is the addition of one
recurrence:
if i > 1 and j > 1 and a[i] = b[j-1] and a[i-1] = b[j] then
d[i, j] := minimum(d[i, j],
d[i-2, j-2] + 1) // transposition
Quyidagi algoritm qo'shni transpozitsiyalar bilan haqiqiy Damerau-
Levenshtein masofasini hisoblaydi.Bu algoritm qo shimcha parametr sifatidaʻ
massivlarning barcha yozuvlari S alifbosining o lchamini talab qiladi.
ʻ
algorithm DL-distance is
input : strings a[1..length(a)], b[1..length(b)]
output : distance, integer

da := new array of | Σ | integers
for i := 1 to | Σ | inclusive do
da[i] := 0

let d[−1..length(a), −1..length(b)] be a 2-d array of integers, dimensions
length(a)+2, length(b)+2
// note that d has indices starting at −1, while a, b and da are one-indexed.

maxdist := length(a) + length(b)
d[−1, −1] := maxdist
for i := 0 to length(a) inclusive do
d[i, −1] := maxdist
d[i, 0] := i
for j := 0 to length(b) inclusive do
d[−1, j] := maxdist
d[0, j] := j

for i := 1 to length(a) inclusive do
db := 0
24

$for j := 1 to length(b) inclusive do k := da[b[j]] ℓ := db if a[i] = b[j] then cost := 0 db := j else cost := 1 d[i, j] := minimum(d[i−1, j−1] + cost, //substitution d[i, j−1] + 1, //insertion d[i−1, j ] + 1, //deletion d[k−1, ℓ−1] + (i−k−1) + 1 + (j-ℓ−1)) //transposition da[a[i]] := i return d[length(a), length(b)] Cheklanmagan Damerau-Levenshtein masofasini hisoblash uchun to'g'ri algoritmni ishlab chiqish uchun, har doim tahrirlash operatsiyalarining optimal ketma-ketligi mavjudligini unutmang, bu erda bir marta o'zgartirilgan harflar keyinchalik o'zgartirilmaydi. (Bu transpozitsiyaning qiymati {\displaystyle W_{T}}W_{T}, hech bo lmaganda qo shish va o chirish narxining o rtachaʻ ʻ ʻ ʻ qiymati bo lsa, shunday bo ladi, ya ni {\displaystyle 2W_{T}\geq). W_{I} ʻ ʻ ʼ +W_{D}}{\displaystyle 2W_{T}\geq W_{I}+W_{D}}.[9]) Shunday qilib, biz pastki qatorni o zgartirishning faqat ikkita simmetrik usulini ko rib chiqishimiz ʻ ʻ kerak. bir marta: (1) harflarni almashtiring va ular orasiga ixtiyoriy sonli belgilar qo'shing yoki (2) belgilar ketma-ketligini o'chiring va o'chirilgandan keyin qo'shni bo'ladigan harflarni ko'chiring. Ushbu g'oyaning to'g'ridan-to'g'ri amalga oshirilishi kub murakkabligi algoritmini beradi: {\displaystyle O {\big (}M\cdot N\cdot \ max(M,N){\big )}}{\displaystyle O{\big (} M\cdot N\cdot \max(M,N){\big )}}, bu yerda M va N qator uzunliklari. Lowrance va Vagner g‘oyalaridan foydalangan holda, bu sodda algoritmni eng yomon holatda {\displaystyle O(M\cdot N)}{\ displaystyle O(M\cdot N)} qilib yaxshilash mumkin. yuqoridagi psevdokod shunday qiladi. Taxminiy satrlarni moslashtirishda maqsad kichik miqdordagi farqlar kutilishi kerak bo'lgan holatlarda ko'p uzunroq matnlardagi qisqa satrlar uchun mosliklarni topishdir. Qisqa satrlar, masalan, lug'atdan olinishi mumkin. Bu erda satrlardan biri odatda qisqa, ikkinchisi esa o'zboshimchalik bilan uzun. Bu keng ko'lamli ilovalarga ega, masalan, imlo tekshiruvi, optik belgilarni aniqlash uchun 25$

tuzatish tizimlari va tarjima xotirasiga asoslangan tabiiy tilga tarjima qilish uchun
dasturiy ta'minot.
Levenshteyn masofasini ikkita uzunroq satrlar orasida ham hisoblash mumkin,
ammo uni hisoblash uchun sarflanadigan xarajatlar, bu ikki qator uzunligining
mahsulotiga taxminan proportsional bo'lib, buni amaliy bo'lmaydi. Shunday qilib,
yozuvlar ulanishi kabi ilovalarda loyqa qatorlarni qidirishda yordam berish uchun
foydalanilganda, taqqoslangan satrlar taqqoslash tezligini yaxshilash uchun odatda
qisqa bo'ladi.[iqtibos keltirish kerak].
Tilshunoslikda Levenshteyn masofasi lingvistik masofani yoki ikki tilning
bir-biridan qanchalik farq qilishini aniqlash uchun metrik sifatida ishlatiladi.[3] U
o‘zaro tushunarlilik bilan bog‘liq: lingvistik masofa qanchalik baland bo‘lsa,
o‘zaro tushunarlilik shunchalik past bo‘ladi, lingvistik masofa qanchalik past
bo‘lsa, o‘zaro tushunarlilik shunchalik yuqori bo‘ladi.Levenshteyn masofasini
hisoblash shuni kuzatishga asoslanadiki, agar biz birinchi qatorning barcha
prefikslari va ikkinchisining barcha prefikslari orasidagi Levenshteyn masofalarini
ushlab turish uchun matritsani zahiraga olsak, u holda matritsadagi qiymatlarni
dinamik dasturlash usulida hisoblashimiz mumkin va Shunday qilib, oxirgi
hisoblangan qiymat sifatida ikkita to'liq satr orasidagi masofani toping.
Pastdan yuqoriga dinamik dasturlashning namunasi bo'lgan ushbu algoritm
1974 yilda Robert A. Vagner va Maykl J. Fisherning "Stringdan qatorga tuzatish
muammosi" maqolasida variantlari bilan muhokama qilingan.Bu
LevenshteinDistance funksiyasi uchun oddiy psevdokodni amalga oshirish bo lib,ʻ
u ikkita satrni, m uzunlikdagi s va n uzunlikdagi t ni oladi va ular orasidagi
Levenshtein masofasini qaytaradi:
function LevenshteinDistance ( char s [ 1 .. m ] , char t [ 1 .. n ]) :
// for all i and j, d[i,j] will hold the Levenshtein distance between
// the first i characters of s and the first j characters of t
declare int d [ 0 .. m , 0 .. n ]

set each element in d to zero

// source prefixes can be transformed into empty string by
// dropping all characters
for i from 1 to m :
d [ i , 0 ] := i

// target prefixes can be reached from empty source prefix
26

// by inserting every character
for j from 1 to n :
d [ 0 , j ] := j

for j from 1 to n :
for i from 1 to m :
if s [ i ] = t [ j ] :
substitutionCost := 0
else :
substitutionCost := 1
d [ i , j ] := minimum ( d [ i - 1 , j ] + 1 , // deletion
d [ i , j - 1 ] + 1 , // insertion
d [ i - 1 , j - 1 ] + substitutionCost ) // substitution

return d [ m , n ]
Levenshtein masofasini quyidagi algoritm yordamida iterativ tarzda
hisoblash mumkin.
function LevenshteinDistance ( char s [ 0 .. m - 1 ] , char t [ 0 .. n - 1 ]) :
// create two work vectors of integer distances
declare int v0 [ n + 1 ]
declare int v1 [ n + 1 ]
// initialize v0 (the previous row of distances)
// this row is A[0][i]: edit distance for an empty s
// the distance is just the number of characters to delete from t
for i from 0 to n :
v0 [ i ] = i
for i from 0 to m - 1 :
// calculate v1 (current row distances) from the previous row v0
// first element of v1 is A[i + 1][0]
// edit distance is delete (i + 1) chars from s to match empty t
v1 [ 0 ] = i + 1
// use formula to fill in the rest of the row
27

for j from 0 to n - 1 :
// calculating costs for A[i + 1][j + 1]
deletionCost := v0 [ j + 1 ] + 1
insertionCost := v1 [ j ] + 1
if s [ i ] = t [ j ] :
substitutionCost := v0 [ j ]
else :
substitutionCost := v0 [ j ] + 1
v1 [ j + 1 ] := minimum ( deletionCost , insertionCost , substitutionCost )
// copy v1 (current row) to v0 (previous row) for next iteration
// since data in v1 is always invalidated, a swap without copy could be more
efficient
swap v0 with v1
// after the last swap, the results of v1 are now in v0
return v0 [ n ]
Ushbu ikki qatorli variant suboptimaldir: kerakli xotira hajmi kesh joylashuvini
yaxshilash uchun bir qatorga va bitta (indeks) qo'shimcha so'zga qisqartirilishi
mumkin
Xirshberg algoritmi bu usulni birlashtiradi. U bir xil asimptotik vaqt va
makon chegaralarida tahrirlash masofasini emas, balki optimal tahrirlash ketma-
ketligini ham hisoblay oladi.
Informatikada w va n soni uchun Levenshteyn avtomati chekli holatli
avtomat bo'lib, u Levenshteynning w dan masofasi ko'pi bilan n bo'lgan barcha
satrlar to'plamini taniy oladi. Ya'ni, x qatori Levenshteyn avtomati tomonidan tan
olingan rasmiy tilda bo'ladi, agar x ni ko'pi bilan n ta bitta belgi qo'shish, o'chirish
va almashtirish orqali w ga aylantirish mumkin bo'lsa.

Vagner-fisher algoritmi
28

Eng qisqa masofani topish uchun matritsani hisoblash kerak. Uni satrlar va
ustunlar bo'yicha hisoblash mumkin. Algoritmning psevdokodi, almashtirishlar,
qo'shishlar va o'chirishlarning yakkalik narxlarida yozilgan (elementlar dan
raqamlanganligini yodda tutish kerak).
Quyidagi psevdokod oddiy maxsus holatni hal qiladi, bunda belgi kiritish,
belgini o'chirish va bir belgini boshqasiga almashtirish har qanday belgi uchun bir
xil turadi.
int levensteinInstruction ( String s1, String s2, int InsertCost, int
DeleteCost, int ReplaceCost):
D[0][0] = 0
fo r j = 1 to N
D[0][j] = D[0][j - 1] + InsertCost
for i = 1 to M
D[i][0] = D[i - 1][0] + DeleteCost
for j = 1 to N
if S1[i] != S2[j]
D[i][j] = min(D[i - 1][j] + DeleteCost,
D[i][j - 1] + InsertCost,
D[i - 1][j - 1] + ReplaceCost)
else
D[i][j] = D[i - 1][j - 1]
return D[M][N]
Yuqorida tavsiflangan algoritm Ę ( M ⋅ N) operatsiyalar va bir xil xotira talab qiladi
lekin faqat masofa kerak bo'lsa kerakli xotirani qisqartirish oson Ę ( N)...
Hisoblash uchun e'tibor beringD [ i ] bizga faqat D [ i - 1 ] kerak, shuning uchun
biz D [ i ] v D [ 1 ], a D [ i - 1 ] v D [ 0 ].. hisoblaymiz. Faqat joylarni almashtirish
uchun qoladiD [ 1 ] va D [ 0 ] ...
int levensteinInstruction ( int[] D):
for i = 0 to M
for j = 0 to N
вычислить D [1][ j ]
swap ( D [0], D [1])
return D [0][ N ]
Rekursiv algoritm
Vaqtni ta ' minlash uchun Ę ( M ⋅ N ) xotirada D ( min ( M , N ) ), matritsani aniqlang .
E satr qo'shimchalari orasidagi minimal masofa , ya'ni.E( i , j ) - oxirgi orasidagi
masofa i belgilar Sbitta va oxirgi j belgilar S2... Shubhasiz, matritsaE matritsaga
o'xshash tarzda hisoblash mumkin D, va xuddi shunday tez.Endi biz taxmin qilib,
algoritmni tasvirlaymiz. S2 ikki qatorning eng qisqasi.Agar chiziqlardan birining
29

(yoki ikkalasining) uzunligi ko'p bo'lmasa bitta, vazifa ahamiyatsiz. Agar yo'q
bo'lsa, quyidagi amallarni bajaring.
S bitta uzunlikdagi ikkita pastki qatorga M/ 2... (AgarM g'alati bo'lsa, u holda
pastki satrlarning uzunligi bo'ladi ( M- 1 ) / 2 va ( M+ 1 ) / 2.) Pastki qatorlarni
belgilaymiz S-bitta va S+bitta...Matritsaning oxirgi qatorini hisoblash uchun D
iplar uchun S-bitta va S2, matritsaning oxirgi qatori E iplar uchun S+bitta va S2...
Shu kabi D ( |S-bitta| ,i)+E( |S+bitta| ,N- men )minimal. Bu yerdaD va E -
oldingi bosqichdagi matritsalar, lekin biz ularning faqat oxirgi qatorlaridan
foydalanamiz. Shunday qilib, biz bo'linishni topdik.S2 chap yarmining
masofasining yig'indisini minimallashtiradigan ikkita pastki qatorga Sbitta chap
tomonga S2 va o'ng yarmining masofasi Sbitta o'ng tomonga S2... Shunday qilib,
chap pastki qatorS2 chap yarmiga mos keladi.
Rekursiv ravishda o'zgartiradigan tahririyat retseptini qidiring S-bitta Chapga S2
(ya'ni, pastki qatorda S2)
Rekursiv ravishda o'zgartiradigan tahririyat retseptini qidiring S+bitta o'ng
tomonga S2 (ya'ni, pastki qatorda S2[ i + 1 ... N]).
Psevdokod:
int levensteinInstruction ( String s1, String s2):
if s1.length <= 1 || s2.length <= 1
Решаем тривиально, возвращаем редакционное предписание
else
String s1l, s1r, s2l, s2r
if s2.length < s1.length
s1l = s1.substring(0, s1.length / 2) // S1-
s1r = s1.substring(s1.length / 2, s1.length) // S1+
// d, e - массивы
d = calcD (s1l, s2) // Вычисляем
последнюю строку матрицы D для S1- и S2
e = calcE (s1r, s2) // Вычисляем
последнюю строку матрицы E для S1+ и S2
k = 0
for i = 1 to s2.length
if d[i] + e[s2.length - i] < d[k] + e[s2.length - k]
k = i
s2l = s2.substring(0, k)
s2r = s2.substring(k, s2.length)
30

else
// s1 - меньшая
строка
s2l = s2.substring(0, s2.length / 2) // S2-
s2r = s2.substring(s2.length / 2, s2.length) // S2+
d = calcD (s2l, s1) // Вычисляем
последнюю строку матрицы D для S2- и S1
e = calcE (s2r, s1) // Вычисляем
последнюю строку матрицы E для S2+ и S1
k = 0
for i = 1 to s1.length
if d[i] + e[s1.length - i] < d[k] + e[s1.length - k]
k = i
s1l = s1.substring(0, k)
s1r = s1.substring(k, s1.length)
return levensteinInstruction (s1l, s2l) + levensteinInstruction (s1r, s2r)
IV.Xulosa
31

Insoniyat tarixining ko’p asrlik tajribasi ezgu go‘yalardan va sog‘lom
mafkura hamda zamonaviy bilimlardan maxrum har qanday jamiyat uzoqqa bora
olmasligini ko‘rsatdi. Shuning uchun, mustaqillikka erishgan mamlakatimiz o‘z
oldiga ozod va obod Vatan, demokratik jamiyat barpo qilish, erkin va farovon
hayot qurish, rivojlangan mamlakatlar qatoridan o‘rin olish kabi muhim vazifalarni
qo‘ydi. Bu vazifalarni hal qilish asosan biz-yosh avlod zimmasiga tushadi.
Biz kelajak jamiyatning faol quruvchilari bo‘lishimiz uchun fan va
texnikaning eng ilg‘or yutuqlari hamda kuchli bilimlar bilan qurollanishimiz,
olingan bilimlarni amaliyotda qo‘llay bilishimiz ana shu yo‘ldagi eng muhim
talablardan biri hisoblanadi. Bu narsa ayniqsa EHM bilan aloqador kundalik
masalalarni yechishda yaqqol ko‘rinadi. Demak, biz yoshlardan zamonaviy EHM
lar bilan ishlashni o‘rganish, xalq xo‘jaliginining turli masalalarini yechishga
mo‘ljallangan dasturiy ta’minot bilan tanishish hamda dasturlash vositalari
yordamida hali EHM da yechilmagan masalalar uchun yangi dasturlar yaratishni
talab qilinadi.
Informatsion texnologiyalarning rivojlanishi va axborot oqimlarining tobora
ortib borishi, ma’lumotlarning tez o’zgarishi kabi holatlar insoniyatni bu
ma’lumotlarni o’z vaqtida qayta ishlash choralarini qidirib topishga undaydi.
Ma’lumotlarni yaratish, so’ngra undan keng foydalanish bugungi kunda dolzarb
bo’lib qolmoqda.Darhaqiqat, hozirgi kunda inson hayotida Algoritmlar juda
muhim rol o’ynaydi. Sababi, jamiyat taraqqiyotining qaysi jabhasiga nazar
solmaylik o’zimizga kerakli ma’lumotlarni olish uchun, albatta, algoritmga
murojaat qilishga majbur bo’lamiz. Demak, algoritmni tashkil qilish axborot
almashuv texnologiyasining eng dolzarb hal qilinadigan muammolaridan biriga
aylanib borayotgani davr taqozasi.
Ma’lumki, algoritm tushunchasi fanga kirib kelgunga qadar, ma’lumotlardan
turli ko’rinishda foydalanish juda qiyin edi. Dastur tuzuvchilar ma’lumotlarini
shunday tashkil qilar edilarki, u faqat qaralayotgan masala uchungina o’rinli
bo’lardi. Har bir yangi masalani hal qilishda ma’lumotlar qaytadan tashkil qilinar
va bu hol yaratilgan dasturdan foydalanishni qiyinlashtirar edi. Algoritmni tashkil
qilish, ularga qo’shimcha ma’lumotlarni kiritish va mavjud algoritmlardan
foydalanish uchun maxsus algoritmlar bilan ishlaydigan dasturlar zarur bo’ladi.
Hozirgi kunda Respublikamizda keng tarqalib borayotgan ish joylarini
avtomalashtirish va ish joylarida axborot kommunikatsiya vositalaridan keng
foydalanishga katta e’tibor berilmoqda.Men kurs ishimni bajarish davomida
ko`plab izlanishlar olib bordim.
32

Kurs ishini bajarish davomida dasturlash texnologiyasi bilan chuqurroq tanishib
chiqdim va chuqur malaka hosil qildim.Shuningdek algoritmlar bilan ishlash,
ularni oddiy va dinamik usullarda tashkil qilish malakasini hosil qildim.
Algoritmlarni tuzish tizimlari bilan tanishib chiqdim va undagi turli xil so’rovlar
orqali ishlar olib bordim.
Xulosa qilib shuni ta’kidlash mumkin, xozirgi fan-texnika xamda
informatsion texnologiyalarining jadal rivojlanayotgan vaqtida AIJlarga bo`lgan
talablar juda xam kuchli bo`lib, bu talablarni to`laqonli qondirish biz va bizga
o`xshash yosh dasturchilarning oldida turgan ulkan vazifalardan biri bo`lib
xisoblanadi.
V. Foydalanilgan adabiyotlar ro’yhati
33

1. Nazarov Fayzullo Maxmadiyarovich, “Algoritimlar va ma’lumotlar
strukturasi”. Samarqand – 2019.
2. Boboxo’jayeva N.M “Algoritimlar nazariyasi”.
3. B.B.Akbaraliyev. “Ma’lumotlar tuzilmasi va algoritimlar”. Toshkent – 2011.
4. A.R.Azamatov, “Algoritimlash va dasturlash asoslari”.Cho 'lpon nomidagi
nashriyot-matbaa ijodiy uyi Toshkent — 2013 .
5. Sh. I. Razzoqov, M. J. Yunusova. Dasturlash: Kasb-hunar kollejlari uchun
o quv qo llanma. T. : “Ilm Ziyo”, 2011y. ʻ ʻ
6. T. X. Holmatov, N. I. Tayloqov. Amaliy matematika, dasturlash va
kompyuterning dasturiy ta`minoti. O quv qo llanma. T:. “Mehnat”, 2000 y.
ʻ ʻ
7. Sattorov A. Informatika va axborot texnologiyalari. Darslik. Т. :,
“O qituvchi”, 2011 y.
ʻ
8. Goluzin G.M. Geometricheskaya teoriya funktsii kompleksnogo
peremennogo. - M. : Nauka, 1976.- 540 s.
9. Virt N. Algoritmi strukturi dannix programmi.-M.:Mir, 1985.-405s

Internet manbaalari
1. http://ziyonet.uz
2. www.google.uz
3.ww.codenet.ru
4. www.ecsoman.edu.ru–Rossiya Federatsiyasi Oliy o`quv yurtlarida
o`qitilayotgan fanlar bo`yicha o`quv-uslubiy komplekslar.
5. http://www.voydod.uz/ - qidiruv tizimi. 15.ziyonet.uz–O`zbekistonning
axbortlarni izlab topish tizimi.
6.http://ITPortal sayti.
34

Tahrirlash masofasi.vagner-fisher algoritmi

Купить

Похожие документы
3d-max dasturida obektlarni yaratish
Algoritm va ma’lumotlar strukturasi
3D-MAX dasturi haqida
3D Studio MAX dasturiga kirish. 3D Studio MAX dasturi haqida tushuncha
Adobe photoshop dasturida tasvirlarda ishlov berish,taqdimot yaratish

Информация о документе

Продавец

Tahrirlash masofasi.vagner-fisher algoritmi

Похожие документы