“TAHRIRLASH MASOFASI.VAGNER-FISHER ALGORITMI” Mundarija: I Kirish_____________________________________________________3 II Nazariy qisim_______________________________________________6 2.1 Dinamik dasturlash_________________________________________6 2.2 Dinamik dasturlash algoritmlarini ishlab chiqish jarayoni_________9 III Asosiy qism________________________________________________15 3.1 Masofani tahrirlash_______________________________________15 3.2 Levenshteyn masofasi____________________________________16 3.3 Vagner-Fisher algoritmi___________________________________30 IV Xulosa___________________________________________________33 V Foydalanilgan adabiyotlar___________________________________35 1

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