logo
  1. Bosh sahifa
  2. Diplom ishlar
  3. Umumiy
  4. Matritsa qidiruv algoritmlari

Matritsa qidiruv algoritmlari

Yuklangan vaqt:

12.08.2023

Ko'chirishlar soni:

0

Hajmi:

53.3466796875 KB
Ko'chirib olish
O’zbekiston Respublikasi Oliy ta’lim, fan va innovatsiyalar vazirligi Sharof Rashidov nomidagi SAMARQAND DAVLAT UNIVERSITETI INTELLEKTUAL TIZIMLAR VA KOMPYUTER TEXNOLOGIYALARI FAKULTETI Dasturiy injiniring yo’nalishi 104-guruh talabasi Toshtemirov Isrofilning Algoritm va ma’lumotlar strukturasi fanidan “Matritsa qidiruv algoritmlari” mavzusida tayyorlagan KURS ISHI Tekshirdi:____________________ Samarqand 2023-yil 1 MUNDARIJA Kirish……………………………………………………………………………….3 1. Algoritm va ma’lumotlar strukturasi fanining mazmuni va vazifalari…………..4 2.Algoritm haqida…………………………………………………………………..5 3.Qidiruv algoritmlari………………………………………………………………7 4.Matritsa…………………………………………………………………………...9 5.Matritsa qidiruv algoritmi………………………………………………………10 6.Matritsa qidiruv algoritmi afzalliklari va kamchiliklari…………………………. 7. 6.Xulosa…………………………………………………………………………26 7.Foydalanilgan adabiyotlar………………………………………………………27 2 Kirish. Yangi XXI - asrda axborot texnologiyalari hayotimizning turli jabhalariga kirib borishi axborotlashgan jamiyatning shakllantirishga zamin yaratib bermoqda. "Internet", "Elektron pochta", "Elektron ta'lim", "Elektron boshqaruv", "Elektron hukumat", "Masofaviy ta'lim", "Ochiq ta'lim", "Axborotlashgan iqtisod" kabi tushunchalar hayotimizga kirib kelishi jamiyatimizning axborotlashishiga intensiv ta'sir ko`rsatmoqda. Axborot – kommunikatsiyalari orqali mamlakatlarning milliy iqtisodi globallashib, axborotlashgan iqtisod shakliga o'tmoqda, ya'ni milliy iqtisoddagi axborot va bilimlarning atilgan axborot va bilimlarning 90 % so'nggi 30 yil mobaynida yaratilgan bo'lib, ular hajmining ko'payib borishi axborot- kommunikatsiyalaridan samarali foydalanishni talab etmoqda. Ko'plab mamlakatlar o'zlarining istiqboldagi rivojlanishini axborotkommunikatsiyalari asosida yo'lga qo'yishni anglab yetishgan. Mustaqil O'zbekiston Respublikamizda ham jamiyatni axborotlashtirish, kompyuter ilmini o‘qitishni rivojlantirish bo'yicha Qonunlar qabul qilinib, ular asosida bir qator dastur va tadbirlar amalga oshirib kelinmoqda. Jumladan, O'zbekiston Respublikasi Prezidentining «Axborotlashtirishni yanada rivojlantirish to'g'risida» 2002 - yil 30 - maydagi PF- 3080- son Farmoni asosida 2010- yilgacha Axborot-kommunikatsiyalarini rivojlantirish bo'yicha milliy dastur ishlab chiqilgan bo'lib, u hozirda butun respublikamiz milliy iqtisodiyotning turli tarmoqlari va sohalarida tatbiq qilinmoqda. Algoritm va ma’lumotlar strukturasi fani Hozirgi kunda biror bir sohada ishni boshlash va uni boshqarishni kompyutersiz tasavvur qilish qiyin. XXI asr savodxon kishisi bo’lishi uchun kompyuter savodxon bo’lish, axborot texnologiyalarini puxta egallamoq lozim. Har bir mutaxassis, u qaysi sohada ishlashdan qat’iy nazar, o’z vazifasini zamon talabi darajasida bajarishi uchun axborotni ishlab chiqaruvchi vositalar va ularni ishlatish uslubiyotini bilish va ishlash ko’nikmalarga ega bo’lishi zarur. Talabalarni ijtimoiy-iqtisodiy va ma’naviy muammolarni hal etishga safarbar qilmoq uchun tegishli axborotlarni o’z vaqtida to’plab, qayta ishlab, muayyan bir tartibga solish va zudlik bilan kishilarga etkazish kerak bo’ladi. Buning uchun jamiyatni axborotlashtirish dasturini amalga oshirish va ilg’or axborot texnologiyasini joriy etish zarurdir. Dasturlarni mustaqil tuzishdan 3 maqsad kompyut е rga mutloq xokimlik qilish, ya’ni ish davomida yuzaga k е ladigan muammolarni t е zroq hal etish imkonini yaratishdir. Kompyut е r dasturlari s е rm е hnat ishlarni avtomatlashtiradi, xatolarni kamaytiradi va m е hnat unumdorligini oshiradi. Bundan tashqari, dasturlar tuzish juda ham mashg’ulotdir. Dasturlarni yaratish jarayonida qo’yilgan masalaning yechish algoritmi dastlab to’g’ri ishlab chiqilishi muhim axamiyatga ega. Shuning uchun algoritmlarni tuzish va dasturlarni ishlab chiqish bir-biri bilan chambarchas bog’liq jarayonlardir. Oliy o’quv yurtlarining informatika, axborot t е xnologiyalari, amaliy mat е matika kabi yo’nalishlarida ta’lim olayotgan talabalar algoritmni ishlab chiqish, dasturlar yaratish, ularni sinash, sozlash, tahlil qilish uchun bilimlarni puxta o’zlashtirishlari zarur. Bunda, ta’lim oluvchi uchun dasturlarni ishlab chiqishda asosiy va eng muhim bosqich hisoblangan algoritmlarni tuzish va shular asosida dasturlar yaratish haqida ma’lumotlarni b е ruvchi adabiyotlar k е rak. Ma’ruzalar matni Oliy o’quv yurtlari talabalari uchun mo’ljallab yozilgan va zamonaviy kompyut е r t е xnologiyalarini mustaqil ravishda o’rganayotgan barcha qiziquvchilar uchun ham foydalidir. Algoritm tushunchasi zamonaviy matematika va informatikaning asosiy tushunchalaridan biri hisoblanadi. Algoritm termini o’rta asrlar ulug’ matematigi al- Xorazmiy nomidan kelib chiqqan. XX asrning 30- yiligacha algoritm tushunchasi ko’proq matematik ma’no emas, balki metodologik ma’noni kasb etar edi. Algoritm deganda, u yoki bu masalalar sinfini yechish imkonini beruvchi aniq ifodalangan chekli qoidalar majmui tushunilgan. EHM larning paydo bo’lishi bilan algoritm tushunchasi yanada keng tarqaldi. EHM va dasturlash usullarining rivojlanishi algoritmlarni ishlab chiqish avtomatlashtirishdagi zaruriy bosqich ekanligini tushunishga yordam berdi. EHM larning paydo bo’lishi algoritmlar nazariyasining rivojlanishiga olib keldi. Algoritmlarni tuzish – bu ijodiy ish bo’lib, 4 ixtiyoriy zaruriy algoritmni tuzish uchun umumiy usullar mavjud emas, kishining ijodiy qobiliyatiga bog’liq. Albatta, algoritmni aniq sxema bo’yicha tuzish zarur bo’lib qoladigan sodda hollar ham mavjud. Bunday hollarda yechilish algoritmi avval biron kim tomonidan olingan masalalarni misol keltirish mumkin. Algoritm Algoritmlarning turli ta’riflari mavjud. Rasmiy ta’riflardan biri bo’yicha algoritm bu qo’yilgan masalani bir xil yechilishiga olib keluvchi aniq harakatlarning ketma-ketligi. Bu tushunchadan algoritmning quyidagi xossalari kelib chiqadi: 1. Diskretlilik – ya’ni aniqlanayotgan jarayonni qadamba-qadam ko’rinishi. 2. Ommaviylik – algoritm o’xshash masalalar turkumini yechishi kerak. 3. Tushunarlilik – algoritmda beriladigan ko’rsatmalar foydalanuvchiga tushunarli bo’lib, uning talablariga javob berishi kerak. 4. Aniqlilik – algoritmda ma’lum tartibda amallarni bajarish nazarda tutilishi kerak va bajaruvchiga joriy qadam tugatilishi bilan qaysi qadam keyingi bo’lib bajarilishi aniq ko’rsatilishi kerak. Algoritmlar rasmiy ravishda bajariladi, bu degani bajaruvchi ajarilayotgan amallarni mazmunini anglash shart emas. Algoritm tuzish jarayoniga algoritmlashtirish deyiladi. Algoritm tuzish jarayonida nazariy va amaliy nuqtai nazardan algoritmlash, dasturlash va EHM larni qo’llash bilan bog’liq bo’lgan bilimlar kerak. Asosiy maqsad bu masalani qo’yish, masalaning yechish algoritmini tuzish, algoritmi mashina dasturi ko’rinishida amalga oshirish va algoritmni samaradorligini ko’rsatish uammolarini o’rganish. Bu jarayonlar algoritmni to’liq yaratish tushunchasiga olib keladi va quyidagi bosqichlarni belgilaydi: 1. Masalaning qo’yilishi. 2. Modelni yaratish. 3. Algoritmni ishlab chiqish. 4. Algoritm to’g’riligini tekshirish. 5. Algoritmni amalga oshirish. 6. Algoritmni va ularning murakkabligini tahlil qilish. 5 7. Dasturni tekshirish. 8. Hujjatlashtirish. Avtomatlashtirish darajasiga ko`ra avtomatlashtirilgan, avtomatik va noavtomatlashtirilgan (an`anaviy) boshqarish tizimlari o`zaro farqlanadi. Avtomatlashtirilgan tizimlar kishilar bo`g`inini (op е ratorlar, ma`muriy apparat) o`zining organik tarkibiy qismiga kiritadi. Avtomatik tizimlar esa yig`ish va sozlashdan so`ng inson ishtirokisiz (profilaktik nazorat va ta`mirlashni hisobga olmasa) printsip jihatdan ishlashi mumkin va ularni ko`proq t е xnologiyalarni boshqarishda qo`llashadi, garchi bu o`rinda avtomatlashtirilgan tizimlar afzal ko`rilsa ham. Tashkiliy boshqaruv tizimlariga k е lganda, ular bu sp е tsifikatsida k е lib chiqib avtomatik bo`lolmaydi. Odamlar bu tizimlarda quyidagi asosiy vazifalarni hal etadi: birinchidan, bu boshqarish maqsadlari va m е zonlarining qo`yilishi va tuzatib borilishidir (ular sharoit o`zgarganda o`zgartirib boriladi), ikkinchidan, qo`yilgan maqsadlarga erishishning eng yaxshi yo`llarini izlab topishda ijodiy el е m е ntlarni kiritish (qo`llanayotgan t е xnologiya yoki tashkiliy ishni k е skin o`zgartirish), uchinchidan, ishlab chiqilayotgan qarorlar 6 tizimini tugal tanlash va ularga yuridik kuch b е rish. Nihoyat, turtinchi vazifa bo`lishi mumkin, bu tizimni boshlang`ich axborot bilan ta`minlashki, uni to`plashni to`liq avtomatlash mumkin emas yoki noratsional hisoblanadi (masalan, kadrlarni hisobga olish ma`lumotlari, ish joyining o`zgarishi ahvoli va hokazolar). Qidiruv algoritmlari. Internetning dastlabki kunlarida qidirish algoritmlari juda ibtidoiy edi. O'sha kunlarda an'anaviy biznes reklama uchun juda ko'p pul sarflagan. Hech kim qidiruv tizimining algoritmlarida minimal mablag' sarflagan holda tarmoq orqali reklama qilish mumkinligini bilmas edi. Ammo ba'zi ixlosmandlar o'zlarining saytlarini yaratdilar, turli xil hiyla-nayranglardan foydalanishdi va yaxshi pul ishlash uchun qidiruv natijalarining yuqori qismiga o'tdilar. Qidiruv tizim algoritmlari Vaqt o'tishi bilan vaziyat o'zgardi. Qidiruv tizimlar jiddiy byudjetlar bilan to'lib toshgan o'z xizmatlarini monetizatsiya qilishni boshladilar, bu esa ularga yaxshi mutaxassislarni ishlashga jalb qilishga imkon berdi. Aynan ular aniqroq algoritmlarni ishlab chiqishda yordam berishdi, bu esa butun vaqt davomida qidiruv natijalarida etakchilik uchun kurashish sharoitlarini an'anaviy reklama usullariga yaqinlashtirdi. Va bugungi kunda u eng ayyor emas, balki eng tajribali, eng iste'dodli va oxirgi iste'molchiga yordam berishni chin dildan yutadi. Muammo shundaki, 6 qidiruv tizimining algoritmlari o'zlari hech qachon mukammal bo'lmagan va hozir ham emas. Ular doimiy ravishda takomillashtirilmoqda, yangi algoritmlar paydo bo'ldi, eskirganlari takomillashtirilmoqda. Shuning uchun, vaqti-vaqti bilan muammo chayqaladi, bu esa ba'zi saytlarning pozitsiyalarini yo'qotishiga olib keladi. Bu ko'plab veb-ustalarni xafa qiladi, chunki ular daromadlarini yo'qotadilar. Shuningdek, doimiy ravishda qidiruv tizimlari qoidalarini chetlab o'tish yo'llarini izlayotgan odamlar hech qaerda yo'q bo'lib ketmadi. Qidiruv natijalarining yuqori qismiga qoidalarni chetlab o'tishga urinishlar doimo paydo bo'ladi va bu algoritmlarni takomillashtirishga olib keladi. Ilgari havolalar soniga qarab saytlarni reytinglash eng muvaffaqiyatli echim deb hisoblanardi. Darhaqiqat, bu haqiqat - saytga qancha havolalar olib borilsa, shuncha ko'p vakolatlarga ega bo'ladi. Biroq, bu erda bitta kamchilik mavjud. Haqiqat shundaki, qaysi havola tabiiy ravishda paydo bo'lganini va qaysi biri qidiruv tizimlarini aldash uchun ochiqchasiga soxtalashtirilganligini tushunish mumkin emas. Algoritmlarni takomillashtirishga urinishlar bo'lgan, ammo hali ham hech kim eng yaxshi natijalarga erisha olmagan. Natijada, mazmunliroq narsani o'ylab topish kerak edi. Va u paydo bo'ldi. Endi qidiruv tizimlari tashrif buyuruvchilar saytdan mamnun bo'ladimi yoki yo'qmi degan ma'lumotdan foydalanishga harakat qilishadi. Ular xulq- atvor omillari deb ataladi. Ya'ni, sayt ommabopmi yoki yuqori lavozimlarga loyiqmi yoki yo'qligini aniqlash uchun siz tashrif buyuruvchilarni josuslik qilishingiz kerak. Agar odamlar sayt sahifalaridagi havolalarni faol ravishda kuzatib borsalar, u erda ko'p vaqt sarf qilsalar, ba'zi shakllarni to'ldirsalar, yangiliklarga obuna bo'lsalar, demak sayt odamlarga yoqadi. Va bu allaqachon SERPdagi mavqeini oshirish uchun sababdir. Bugungi kunda qidiruv tizimlari shunday ishlaydi. Qidiruv natijalarining eng yuqori pog'onasiga ko'tarilish uchun siz saytni tinglovchilarga o'xshatish uchun hamma narsani qilishingiz kerak bo'ladi. Albatta, siz ham havolalarni olishingiz kerak bo'ladi, chunki ular hali ham muhimdir va reytingda ishlatiladi. Ammo xulq-atvor omillari haligacha hal qiluvchi omil bo'lib qolmoqda. Matritsa Matritsa tushunchasi va unga asoslangan matematikaning “Matritsalar algebrasi” bo limi amaliyotda, jumladan, iqtisodiyotda katta ahamiyat kasb etadi. Bu shu ʻ 7 bilan tushuntiriladiki, aksariyat iqtisodiy obyekt va jarayonlarning matematik modellari matritsalar yordamida sodda va kompakt ko rinishida tasvirlanadi. ʻ Matritsa tushunchasi birinchi marta ingliz matematiklari U.Gamilton (1805-1865- y.y.) va A.Kel (1821-1895 y.y.) ishlarida uchraydi. Hozirgi kunda matritsa tushunchasi tabiiy va amaliy jarayonlarning matematik modellarini tuzishda muhim vosita sifatida qo llaniladi. Ta’rif. Matritsa deb m ta satr va n ta ustunga ʻ ega bo lgan qavslar ichiga olingan to rtburchakli sonlar jadvaliga aytiladi. ʻ ʻ Matritsalar lotin alifbosining bosh harflari bilan belgilanadi. Masalan, 11 12 1 21 22 2 1 2 ... ... . ... ... ... ... ... n n m m mn a a a a a a A a a a              Matritsani tashkil qilgan sonlar uning elementlari deyiladi. Matritsa o lchami m n ʻ  kabi yoziladi.Matritsaning i  satr, j  ustun kesishmasidagi element ij a kabi belgilangan. Demak, 34 a  3 - satr va 4 - ustin kesishmasida joylashgan elementdir. Ba’zida matritsalarni yozishda (...) qavslar o rniga [...] qavslar yoki ||...|| kabi ʻ belgilardan foydalaniladi. Aytaylik quyidagi jadvalda iqtisodiyotning tarmoqlari bo yicha resurslarning taqsimlanishi berilgan bo lsin: Resurslar Iqtisodiyot ʻ ʻ tarmoqlari Sanoat Qishloq xo jaligi Elektr energiyasi resurslari 7,3 5,2 Mehnat ʻ resurslari 4,6 3,1 Suv resurslari 4,8 6,1 Bu resurslar taqsimotini matritsa ko rinishida quyidagicha yozish mumkin: 7,3 5,2 4,6 3,1 . 4,8 6,1 A ʻ            Bu matritsaning o lchami 3 2 ʻ  bo lib, satrlari resurs turlariga ustunlari esa ʻ tarmoqlarga mos keladi. ( 1  n ) o lchamli matritsaga satr matritsa, ( m ʻ  1 ) o lchamli matritsaga esa ustun matritsa deyiladi, ya’ni ʻ   K a a a  11 12 1n , 11 21 1 . m a a L a              Bundan tashqari ba’zida bu matritsalar mos ravishda satr-vektor va ustun-vektor deb ham ataladi. Matritsaning elementlari esa vektorlarning komponentlari, deyiladi. Har bir elementi nolga teng bo lgan, ʻ ixtiyoriy o lchamli matritsaga nolmatritsa deb aytiladi va quyidagi ko rinishda ʻ ʻ bo ladi: 0 0 ... 0 0 0 ... 0 . ... ... ... ... 0 0 ... 0 ʻ               Ta’rif. A va B matritsalar bir xil o lchamga ega bo lib, ularning barcha mos elementlari o zaro ʻ ʻ ʻ teng bo lsa, bunday matritsalar teng matritsalar deyiladi va A B ʻ  ko rinishda ʻ yoziladi. Misol. Quyidagi matritsaviy tenglikdan x va y noma’lumlarning qiymatlarini toping: 3 2 3 . 1 2 1 y x y               Yechish.Matritsalarning mos elementlarini taqqoslab quyidagi tengliklarni hosil qilamiz: y x y x      2, 2 0. Ta’rif. A matritsaning ustunlari soni B matritsaning satrlari soniga teng bo lsa, A matritsa B matritsa bilan zanjirlangan ʻ matritsa deyiladi. Masalan, 2 3 4 4 5 2 9 8 2 A            va 5 8 1 4 4 3 B            matritsalar zanjirlangan matritsalar bo ladi. Chunki, A matritsaning ʻ o lchami 3 3 ʻ  ga, B matritsaning o lchami 3 2 ʻ  ga teng. Shuni ta’kidlash lozimki B va A matritsalar zanjirlangan emas. Chunki, B matritsaning ustunlari soni 2 ga, A matritsaning satrlari soni 3 ga teng bo lib, o zaro bir xil emas. Ta’rif. ʻ ʻ 8 Ham satrlar soni,ham ustunlar soni n ga teng bo lgan, ya’ni n n ʻ  o lchamli ʻ matritsa n  tartibli kvadrat matritsa deyiladi. Masalan, 1 8 6 1 2 5 7 3 1 0 11 15 0 5 3 9 A                matritsa 4-tartibli kvadrat matritsadir. 11 22 , ,..., nn a a a elementlarning tartiblangan t о ‘plami kvadrat matritsaning asosiy diagonali deyiladi.Agar ( ) A a  ij kvadrat matritsada i j i j   ( ) munosabat bajarilganda 0 ij a  bo lsa, u holda A matritsa yuqori (quyi) uchburchakli matritsa deyiladi. ʻ Matritsaning algoritmga bog’liqligi shundaki uning ishlash prinsipi matritsaga asoslangan. Matritsa qidiruv algoritmlari. Algoritmlarning murakkabligini o'rganishda biz miqdorni baholash usullarini ishlab chiqamiz "resurs" ning, odatda yangi yoki mavjud dasturlar tomonidan ishlatiladigan vaqt yoki saqlash joyi; harakat qilamiz berilgan vazifani bajaradigan har qanday dastur tomonidan talab qilinadigan resurslar uchun pastki chegaralarni isbotlash vazifa; biz bir xil muammo uchun turli xil algoritmlar orasidagi qiziqarli munosabatlarni qidiramiz yoki bir-biriga bog'lanmagan ko'rinadigan muammoli hududlar o'rtasidagi mumkin bo'lgan aloqalarni o'rganing; va umuman biz asosiy qiyinchiliklarni va ularni hal qilish yo'llarini chuqurroq tushunishga intiling, turli xil hisoblash muammolari. Ushbu eslatmada biz matritsalarni ko'rib chiqamiz. Matritsa usullari ko'pchilikda muhim qo'llanilishiga ega ilmiy sohalar va ko'pincha kompyuter vaqtining katta miqdorini hisobga oladi. Amaliy algoritmlarni takomillashtirishdan foyda, shuning uchun potentsial juda katta. Matritsalarni ko'paytirish kabi asosiy algoritmlar to'liq tushunishni taklif qilish uchun etarlicha sodda. Murakkab matematik muammolarni va ba'zi nafis echimlarni taklif qilish uchun etarlicha boy tuzilishga ega. 2 Matritsa arifmetikasining ta'riflari Agar A p × q matritsa va B a q × r matritsa bo'lsa, ularning mahsuloti C = A · B p × r matritsadir. cij = tomonidan berilgan yozuvlar bilan 9 Pq i = 1 uchun k=1 aikbkj, . . . , p va j = 1, . . . , r. Ba'zan A ni uning A1, p qator vektorlaridan tashkil topgan deb hisoblash foydalidir. . . , Ap va B kabi uning r ustunli vektorlaridan tashkil topgan B1, . . . , Br. U holda cij Ai va vektorlarining ichki mahsulotidir Bj. O'lchamlari bir xil bo'lgan ikkita A, B matritsalarining yig'indisi berilgan C = A + B matritsadir cij tomonidan = aij + bij hamma uchun i, j. 3 Arifmetik murakkablik. Arifmetik algoritm uchun kompyuter dasturi odatda boshqa ko'rsatmalarni bajaradi. Algoritmning aniq arifmetik amallariga qaraganda. Masalan, olib kelish bo'ladi, saqlash, yuklash va nusxalash operatsiyalari. Kesh xotira va tashqi xotiraning xususiyatlari qurilmalar ish vaqtiga katta ta'sir ko'rsatishi mumkin. Umumiy bajarilish vaqtining nisbati bunday "qo'shimcha xarajatlar" ga sarflanadigan kompyuter va dasturlashga juda bog'liq bo'ladi.Oddiylik va mustaqillik uchun biz ko'pincha faqat hisobga olamiz ishtirok etgan arifmetik amallar. Ushbu o'lchov arifmetik murakkablik deb ataladi. Ushbu soddalashtirishning oqibatlari, xususan, amaliy dasturlarda, albatta, bo'lishi kerak diqqat bilan ko'rib chiqiladi. p × q matritsaning q × r matritsaga (a p × q × r mahsuloti) ko‘paytmasida pr yozuvlarining har biri ko'paytmani q ko'paytirish va q - 1 qo'shish yordamida hisoblash mumkin. Biz yozishimiz mumkin bu arifmetik murakkablikni q m + (q - 1) a deb hisoblang va keyin (p × q × r) mahsulot uchun jami oling. pqr ning m + p(q - 1)r a. Ikki p × q matritsalar yig'indisi faqat pq a dan foydalanadi. 10 Biz m va a ni har bir turdagi raqamlarni kuzatib borish uchun rasmiy belgilar sifatida tasavvur qilishimiz mumkin arifmetik operatsiya, aks holda biz bularni har bir operatsiyaning vaqti yoki narxi deb hisoblashimiz mumkin va Shunday qilib, operatsiyalarning umumiy qiymati uchun ifodaga ega bo'ladi. Biz hech qachon farq qilmaymiz asosiy qo‘shish va ayirish va bunday amalning murakkabligi haqida so‘z boradi qo'shish/ayirish (a/s) sifatida. Xuddi shunday, biz ba'zan ko'paytirish/bo'lish yozishimiz mumkin. ㅤㅤㅤㅤㅤㅤㅤㅤㅤ ㅤㅤㅤ Matritsali mahsulot uchun Winograd algoritmi a1·b1+a2·b2 ni hisoblash uchun albatta 2 ta koʻpaytirish/boʻlish (va 1 ta qoʻshish/ayirish) kerak boʻladi va umuman olganda, a1 · b1 + · · · + an · bn uchun n ta koʻpaytirish/boʻlish kerak. Muqobil a1 · b1 + a2 · b2 ni hisoblash usuli quyidagicha: µ1 = a1 · a2 µ2 = b1 · b2 µ3 = (a1 + b2) · (a2 + b1) natija = µ3 - µ1 - µ2. Ushbu o'ziga xoslikning matritsa mahsuloti uchun ahamiyatini ko'rish uchun yaxshi tushuncha kerak, bu birinchi navbatda bir qarashda, ko'rinadiganidan ko'ra ko'proq ko'paytirish va ko'proq qo'shimchalar olib ko'rinadi. Algoritm muhim xususiyat shundaki, µ1 va µ2 faqat ko‘paytirishni o‘z ichiga oladi mos ravishda a va faqat b. Nima uchun bu juda muhim? Biz allaqachon matritsa mahsulotini ichki mahsulotni topish deb hisoblash mumkinligini ta'kidlagan edik bitta matritsaning har bir satri bilan boshqa matritsaning har bir ustuni uchun ishlatiladigan kichik algoritmda ichki mahsulot, agar vektorlardan faqat bittasi elementlarini o'z ichiga olgan hisoblash mavjud bo'lsa u holda bu vektor har safar o'rniga o'sha satr (ustun) uchun faqat bir marta 11 bajarilishi mumkin. Ushbu "oldindan ishlov berish" g'oyasi juda muhim va bu holda Winogradga olib keladi. Algoritm birinchi navbatda n bo'lgan n × n matritsalarning oddiy holati uchun tavsiflanadi hatto. x = (x1, . . . , xn) uchun aniqlang W(x) = x1 · x2 + x3 · x4 + · · · + xn−1 · xn. Keyin (i) A ning har bir Ai qatori uchun W(Ai) va B ning har bir Bj ustuni uchun W(Bj ) ni hisoblang. (ii) Har bir juftlik uchun (i, j) Ai uchun a va Bj uchun b yozing, hisoblang a · b = (a1 +b2)·(a2 +b1) + (a3 +b4)·(a4 +b3) +· · ·+ (an−1 +bn)·(an +bn−1)−W( a)−W(b). (i) uchun arifmetik murakkablik 2n(n/2 m + (n/2 - 1) a), va (ii) uchun (n/2 m + (3n/2 + 1) a), jami beradi (12n 3 + n2) m + (32 n3 + 2n(n - 1)) a = 1 2 n 3 m + 32 n3a + O (n2). Pastki tartib shartlarini e'tiborsiz qoldirib, biz taxminan n almashdik Qo'shimcha uchun 3/2 ko'paytirish 3/2 qo'shish/ayirish. Algoritm umumiy p×q×r mahsulotiga osonlik bilan kengaytiriladi. Agar q hatto bo'lsa, algoritm aslida bir xil bo'ladi. Agar q toq bo'lsa, bitta elementar ko'paytirish har bir ichki mahsulotda an'anaviy tarzda amalga oshiriladi va alohida qo'shiladi, qaysi arifmetik murakkablikka 12 sezilarli ta'sir ko'rsatmaydi. Qo'shimcha saqlash talablari Winograd algoritmi minimal: har bir satr va ustun uchun faqat bitta qo'shimcha joy kerak W qiymatini saqlash uchun. Bu algoritm m > a bo'lganda mumkin bo'lgan qiymatga ega. Odatda ilovalar qachon matritsa hisoblanadi. Elementlar murakkab sonlar yoki ko'p aniqlikdagi sonlardir. Muhim cheklov algoritm uning to'g'riligi ko'paytirishning kommutativligiga bog'liq. Bu ko'rinadi yuqoridagi a1b1 + a2b2 uchun asl identifikatsiyada. Keling, murakkab matritsalar ishini batafsil ko'rib chiqaylik. Kompleks deb faraz qilsak raqamlar juft reallar bilan ifodalanadi, ularning haqiqiy va xayoliy qismlarini, ravshanligini beradi hisoblash algoritmi (x + iy) · (u + iv) = (xu − yv) + i(xv + yu) 4 m+ 2 a ni oladi, murakkab qo‘shish esa 2 a ga tushadi. Bu Winograd uchun yaxshi dastur bo'lib tuyuladi. Agar biz g'ayrioddiy usullarni qidirayotgan bo'lsak, quyidagi muqobilni topishimiz mumkin murakkab mahsulot uchun: l1 = x · u l2 = y · v l3 = (x + y) · (u + v). Keyin (x + iy) · (u + iv) = (l1 - l2) + i(l3 - l1 - l2). Garchi bu identifikatsiya Winograd algoritmi asosidagi identifikatsiyani eslatsa ham, e'tibor bering. bu yerda ko'paytirishning kommutativligini qabul qilish shart emas. Chunki bu usuldan foydalaniladi 3m + 5a, 4 m + 2 a o'rniga, m a dan ancha katta bo'lgan vaziyatni talab qiladi. Agar ishtirok etgan elementlarning o'zlari katta matritsalar bo'lsa, bu shart bajariladi. 13 Ushbu kuzatish murakkab matritsali mahsulot uchun algoritmlarning yangi sinfini beradi. E'tibor bering kommutativlik haqidagi yuqoridagi fikrning dolzarbligi. Berilgan murakkab matritsalar, A va B, bo'linish Biz yozishimiz uchun ularni haqiqiy va xayoliy qismlarga ajrating A = X + iY, B = U + iV, bu yerda X, Y, U, V haqiqiy matritsalar. Keyin yuqoridagi edentifikatsiya A · B yordamida hisoblash uchun ishlatiladi faqat 3 ta haqiqiy matritsa mahsuloti va 5 ta haqiqiy matritsa summasi. Endi bizda ko'rib chiqiladigan ko'plab algoritmlar mavjud, ulardan sakkiztasini aniqlaymiz. Ikki berilgan murakkab matritsalar, ularni to'g'ridan-to'g'ri klassik usul (C) yoki yordamida ko'paytirish mumkin Winograd algoritmi (W), so'ngra murakkab yozuvlar yuqoridagi identifikatsiya tomonidan berilgan To'g'ridan-to'g'ri yo'l (S) yoki G'ayrioddiy (Underhand?) usulida (U) ko'paytirilishi mumkin. Bu usullarni bilan belgilang CS, CU, WS, WU. Shu bilan bir qatorda, asl matritsalar haqiqiy va xayoliy qismlarga bo'linishi va S yoki U usullari yordamida ko'paytirilishi mumkin. Kerakli haqiqiy matritsa mahsuloti C yoki W tomonidan amalga oshiriladi, natijada hosil bo'ladi. Biz n × n × n mahsulot uchun ushbu usullarning arifmetik murakkabligini tahlil qilamiz. Bu faqat nazariy mashq, chunki amalda "qo'shimcha xarajatlar" o'xshash algoritmlarni solishtirishda hal qiluvchi mezon bo'lishi mumkin. m ning yetakchi koeffitsientlaridan va arifmetik murakkablikning a komponentlaridan pastda. Usul koeffitsienti n 3 n koeffitsienti 3, CS, 4 4 CU, 3 7 WS, 2 4 WU, 1 1 2,512SC 4 4,SW 2 6,UC 3 3,UW 1 1,2,4,1,2. 14 Yuqoridagi muhokamadan kutilgandek, agar dastlab matritsalarni bo'linadigan bo'lsa,birinchi bosqich S bilan emas, balki U bilan bajarilishi kerak va agar matritsalar ko'paytirilsa to'g'ridan-to'g'ri, W C dan yaxshiroqdir. Qolgan murakkabliklarga qarab, biz buni topamiz 1. agar m > a bo'lsa, UW eng pastiga ega; 2. agar m < a bo'lsa, UC eng pastiga ega; 3. agar m = a bo'lsa, WS, UW, UC qo'shma yetakchilar, lekin agar 3-holatda quyi tartibli shartlar hisobga olinsa, u holda UC eng past arifmetikaga ega murakkablik: 3n Sakkizta algoritmni solishtirish Amalda, boshlang'ich "U" bo'linishidan foydalanadigan usullar o'shandan beri sezilarli kamchilikka ega bu dasturlar faqat bitta o'rniga uchta matritsani ko'paytirishni va katta qismini talab qiladi jami bajarilish vaqti indekslarni ishga tushirish va hisoblash bilan bog'liq bo'lishi mumkin va operatsiyalar uchun argumentlar manzillari. Men sinab ko'rmagan istiqbolli yondashuv Amalda, lekin UC va kabi usullardagi ba'zi samarasizliklarni bartaraf etishi mumkin UW quyidagicha. Biz uchta haqiqiy matritsa mavjudligidan foydalanamiz bir xil o'lchamdagi mahsulotlarni hisoblash va ularni bajarish mumkin parallel. Agar ushbu mahsulotlarning tegishli operatsiyalari aralashgan bo'lsa, ba'zilari "Umumiy xarajatlar" taqsimlanishi mumkin. Rekursiv usul va takrorlanish munosabatlari matritsa mahsuloti uchun algoritmning boshqa uslubi uchun biz bo'lingan matritsalardan foydalanishimiz mumkin va "Blokli ko'paytirish". Masalalarni soddalashtirish uchun faraz qilaylik, A, B n > 1 bo‘lgan n × n matritsalar. A, B larni submatritsalardan tashkil topgan deb quyidagi tarzda qaraymiz A11 | A12 15 A21 | A22 B11 | B12 B21 | B22 Bu yerda A11, B11 r × r matritsalar, 0 < r < n, u holda hosila quyidagicha berilgan: A11B11 + A12B21 | A11B12 + A12B22 A21B11 + A22B21 | A21B12 + A22B22 Natijaning to'g'ri ekanligi osongina isbotlanadi va faqat qo'shishning assotsiativlik xususiyatidan foydalanadi. Shunday qilib, A · B mahsuloti quyi matritsalarning 8 ta mahsulotini bajarish orqali hisoblanadi, keyin esa olingan kichik matritsalarning 4 yig'indisiga. Submatritsali mahsulotlar shunga o'xshash tarzda bajarilishi mumkin keyinchalik kichikroq matritsalarga bo'lish yo'li bilan va natijada olingan matritsalar paydo bo'lguncha davom etadi kichik, ehtimol 1 × 1. Shunday qilib, bizda matritsa mahsuloti uchun rekursiv protsedura mavjud. Agar olsak r = dn/2e, shuning uchun bo'linish imkon qadar teng qismlarga bo'linadi va agar P (n) ni yozsak, S(n), mos ravishda n×n×n ko‘paytmaning arifmetik murakkabligi va n×n yig‘indisi uchun hosil bo‘ladi. quyidagi takrorlanish munosabati. P(n) 8P(dn/2e) + 4S(dn/2e).≤ Lekin S(n) = n amallar, shuning uchun bizda P(n) 8P(dn/2e) + O(n) bor ≤ Yuqoridagi shakldagi takrorlanish munosabatlari tez-tez uchraydi va biz quyida umumiy yechimni beramiz. Aynan shu narsani ko'rgan kuzatuvchi o'quvchi uchun bu ajablanarli emas ko'paytirish "klassik" algoritmda bo'lgani kabi 16 amalga oshiriladi va qo'shimchalar hozirgina amalga oshirildi assotsiativlik yordamida qayta tashkil etilgan. 1-teorema Agar F musbat butun sonlarda manfiy bo'lmagan funksiya bo'lsa, ba'zilari uchun 1, b > 1 va b 0, F(n) a.F(dn/be) + O(n)≥ ≤ agar a = logb a bo'lsa: F(n) = O(n agar a < b bo'lsa, = O(n a log n) agar a = b bo'lsa. 6 Strassen algoritmi Winograd algoritmi nuqtai nazaridan, ba'zilar buni taxmin qilish vasvasasi bo'ladi ko'paytirish va qo'shimchalar o'rtasidagi almashinuv mumkin, arifmetikaning umumiy soni talab qilinadigan operatsiyalar n tartibida n×n mahsulot uchun. Bu shunday emas! Strassen oddiy va hayratlanarli kuzatish [7] shundan iboratki, 2×2 matritsalarni koʻpaytirish uchun faqat 7 ta (8 emas) koʻpaytiriladi. elementlarni ko'paytirish kommutativ bo'lmasa ham kerak. Ushbu faktdan foydalanib, blok oxirgi bo'limda tasvirlangan ko'paytirish algoritmi bitta qoniqarli darajaga ko'tarilishi mumkin: P(n) 7P(dn/2e) + O(n ≤ yuqorida berilgan teorema bo'yicha hosil bo'ladi P(n) = O(n log2 7 Eslatib o'tamiz, P (n) - arifmetik amallarning umumiy soni (ko'paytirish, qo'shish / ayirish). 17 Ko'rinib turibdiki, ushbu algoritmni oqilona xususiyatlarga ega mashinada to'g'ridan-to'g'ri amalga oshirish bilan umumiy bajarish vaqti ham belgilangan tartibda bo'ladi. Oddiylik uchun A, B n × n matritsalar, n esa teng matritsalar deb faraz qilamiz. 4 ta teng chorak matritsaga bo'linishi mumkin. A11 | A12 A21 | A22 B11 | B12 B21 | B22 C11 | C12 C21 | C22 hisoblash: m1 = (A11 + A21) (B11 + B12) m2 = (A12 + A22) (B21 + B22) m3 = (A11 − A22)(B11 + B22) m4 = A11 (B12 - B22) m5 = (A21 + A22)B11 m6 = (A11 + A12)B22 m7 = A22 (B21 - B11). Keyin C11 = m2 + m3 - m6 - m7 C12 = m4 + m6 C21 = m5 + m7 C22 = m1 - m3 - m4 - m5. 18 Shunday qilib, P(n) = 7P(n/2) + 18S(n/2) va hokazo P(n) = O(n log2 7 Ushbu identifikatsiyalar diagramma shaklida qulay tarzda ifodalanishi mumkin, bu erda hujayrada (Aij , Bkl) +(−)AijBkl atamasini ifodalaydi. Bog'langan doiralar guruhlarini ifodalaydi tegishli mahsulotlarda uchraydigan shartlar. Endi to'g'riligini tekshirish oson identifikatsiyalar. Kerakli matritsalar sonini 18 dan 15 gacha kamaytirish uchun yuqoridagi identifikatorlarga chiziqli o'zgarishlarni qo'llash orqali kichik yaxshilanishga erishish mumkin. Albatta, bu hech qanday ta'sir qilmaydi ko'rsatkich bo'yicha, log2 7, lekin arifmetik murakkablikni doimiy omilga kamaytiradi. Olingan identifikatsiyalar quyida keltirilgan. Qizig'i shundaki, ettita mahsulotning birinchi ikkitasi A11B11 va A12B21 bo'lib, ular ham aniq bloklarni ko'paytirish orqali amalga oshiriladi. B21 B22 B11 B12 A12 A22 A11 A21 C21 C22 C21 C22 C11 C11 C12 C12 1 7 4 5 2 6 3 Strassen diagrammasi m1 = A11B11 m2 = A12B21 m3 = (−A11 + A21 + A22)(B11 − B12 + B22) m4 = (A11 − A21)(−B12 + B22) m5 = (A21 + A22)(−B11 + B12) 19 m6 = (A11 + A12 - A21 - A22)B22 m7 = A22 (−B11 + B12 + B21 - B22). Keyin C11 = m1 + m2 C12 = m1 + m3 + m5 + m6 C21 = m1 + m3 + m4 + m7 C22 = m1 + m3 + m4 + m5. E'tibor bering, da'vo qilingan 15 ta qo'shimchaga faqat umumiy shartlarni sinchkovlik bilan almashish orqali erishiladi. Probert [6] 15 optimal ekanligini ko'rsatdi. Ba'zi tegishli natijalar 2 × 2 × 2 mahsulotini 7 dan kam ko'paytirish yordamida hisoblash mumkinmi? Winograd [10] ko'paytirish kommutativ bo'lsa ham, 7 optimal son ekanligini ko'rsatadi. Hopcroft va Musinski [3] shuni ko'rsatadiki, har qanday kommutativ bo'lmagan halqa uchun qo'shni noaniqliklar tomonidan olinadi kommutativ halqaga, 2 × 2 × 2 mahsulot uchun 7 marta ko'paytirish bilan har bir algoritm bo'lishi mumkin. Strassen algoritmiga chiziqli o'zgarishlarni qo'llash orqali olingan. Misol tomonidan taqdim etilgan yuqorida keltirilgan ikkita identifikatsiya to'plami. Matritsani ko'paytirish masalasining tenzor formulasi [8, 2] simmetriyaga ega p×q×r, p×r×q uchun zarur bo‘lgan minimal ko‘paytirish soni bir xil ekanligini ko‘rsatadi. q × r × p, q × p × r, r × p × q va r × q × p mahsulotlar va shuning uchun faqat uchlikka bog'liq. {p, q, r}. Bu natija bilan [4] dan olingan natijalardan foydalanib, biz uchun minimal songa ega bo'lamiz uchlik {p, q, 2} d(3pq + max(p, q))/2e, p 2 yoki p = q = 3 uchun, masalan, p = q = 2 uchun 7 va 15≤ 20 p = q = 3 uchun. Shu turdagi usullardan foydalangan holda Strassen chegarasida har qanday yaxshilanish aniq. Rekursiya 2 × 2 × 2 dan kattaroq asosiy mahsulotga asoslangan bo'lishi kerak. Agar 3 × 3 matritsani faqat 21 ta ko'paytirish (kommutativ bo'lmagan) yordamida ko'paytirish mumkin bo'lsa, u holda a log3 21 < log2 7 dan beri tezroq algoritm olinadi. 24 dan yaxshiroq hech narsa hali mavjud emas erishildi, lekin hech qanday yaqin pastki chegara isbotlanmagan. 4 × 4 matritsalar uchun, aniq 48 erishish kerak edi. Rekursiya kvadrat bo'lmagan parchalanishlarga ham asoslanishi mumkin. [3] natijalari shuni ko'rsatadiki, p × q × r mahsulot uchun k ko'paytirish natijasida k hosil bo'ladi. pqr × pqr × pqr hosilasi va demak, 3 logpqr k ning n ko‘rsatkichi. 1980 yilda Viktor Pan 143640 ta ko'paytirishdan foydalangan holda 70 × 70 × 70 o'lchamdagi mahsulot uchun algoritmni nashr etdi [5]. E'tibor bering, log70 143640 < 2.796. Keyingi bir necha yil ichida eng yaxshi ko'rsatkich asta-sekin tushib ketganligi ma'lum. Hozirgi rekord hali ham Coppersmith va tufayli 2.376 Winograd [1]. Biroq, katta doimiy omillar tufayli, yagona sub-kubi Amaliylikka har qanday da'voga ega bo'lgan algoritm Strassenga tegishli. Ixtiyoriy shakl va o'lchamdagi matritsalar ko'paytmasi uchun algoritmda u juda samarasiz. Faqat matritsalarni 0 bilan to'ldirish uchun, keyingi ikki darajagacha. Har bir o'lchamni yarmiga qisqartirish va bitta satr yoki 0 ustunini qo'shish samaraliroq, lekin eng yaxshi strategiya har xil o'lchamlarga bo'lish, kvadrat bo'lmagan matritsalarning ba'zi takrorlanishlaridan foydalanish va uzatishni o'z ichiga oladi. Winograd usuliga yoki kichik matritsalar uchun klassik usulga. Foydalanish, albatta, samarasiz Strassen rekursiyasi 1 × 1 matritsagacha. 21 2-bo'limda bir nechta matritsa mahsulotlarini parallel ravishda bajarish orqali arifmetik bo'lmagan qo'shimcha xarajatlarni bo'lishish g'oyasi quyidagini amalga oshirishda foydali bo'lib tuyuladi. Strassen algoritmi ham. Biroq, qabul qilib bo'lmaydigan o'sishni oldini olish uchun ehtiyot bo'lish kerak. 8 Matritsali ko‘paytmaning qisqarishlari va ekvivalentlari Strassenning asl maqolasida [7], u shuningdek, har qanday tez matritsali mahsulot algoritmi qanday natija berishini ko'rsatadi. matritsani inversiyalash va hisoblash determinantlari uchun mos ravishda tezkor algoritm. Bular pasaytirishlar quyidagi “blok LDU faktorizatsiyasi” formulasiga asoslanadi, bu osontasdiqlangan. I(n) uchun takrorlanish munosabati, n × n matritsani invertatsiya qilishning arifmetik murakkabligi, tomonidan berilgan I(n) 2I(dn/2e) + O(P(dn/2e) + O(n)≤ 2 ). Agar P(n) = O(n) ni beradigan mahsulot algoritmini qabul qilsak a), ba'zi a 2 uchun umumiy ≥ 3-bo'limda berilgan eritma hosil beradi I(n) = O(n a ). Xuddi shunday, LDU faktorizatsiyasidan bizda bor Det A11 A12 A21 A22 22 = Det(A11)Det( ).∆ Agar D (n) determinantlar uchun arifmetik murakkablik bo'lsa, bizda takrorlanish mavjud D(n) 2D(dn/2e) + I(dn/2e) + O(P(dn/2e)) ≤ va shuning uchun xuddi shu gipoteza bilan, D(n) = O(n a ). Inversiya algoritmi blok LDU faktorizatsiyasini rekursiv ravishda ishlatadi va shuning uchun A bo'lsa ham muvaffaqiyatsiz bo'ladi. rekursiyaning istalgan darajasidagi “A11” yoki “ ” birlik boʻlganda, ∆ birlik emas. Ushbu qiyinchilikni engish uchun quyidagi natijalar berilgan. Birlik bo'lmagan A matritsa, agar x bo'lsa, musbat-aniqlangan Barcha nolga teng bo'lmagan vektorlar uchun TAx > 0 x. 2-teorema Har qanday yagona bo'lmagan A matritsa uchun ATA matritsasi musbat-aniqdir. Isbot: x T(A TA)x = (Ax) T(Ax) = Ax2 0. ≥ Agar x 6= 0 bo'lsa, Ax 6= 0 va shuning uchun Ax2 > 0. Strassen algoritmida shuni ko'rsatish mumkinki, agar A musbat-aniq bo'lsa, u holda har bir matritsa rekursiv qo'ng'iroqlarda teskari bo'lishi kerakligi ham ijobiy-aniq. Demak, matritsaning inversiyasi ATA ga 23 Strassen algoritmini qo'llash orqali 3-teorema orqali amalga oshirilishi mumkin. Shunday qilib, ikkita n×n matritsaning A, B ko‘paytmasini topish uchun mos ravishda invertatsiya qilish kifoya. tuzilgan yagona bo'lmagan 3n × 3n matritsa. Shuning uchun bizda bor P(n) I(3n).≤ Buni oldingi natija bilan birlashtirib, biz quyidagilarni olamiz: 4-teorema Barcha a 2 uchun, ≥ P(n) = O(n Matritsalarni kvadratlash uchun shunga o'xshash natija dan kelib chiqadi. X ul osa Men “matritsa qidiruv algoritmlari” mavzusida men qidiruv algoritmlarini mukammalroq o’rgandim bu mavzu haqida bir nechta chet el manbalarini axtardim. Bu algoritm yani matritsali qidiruv algoritmlari atpechatkalarda va boshqa joylarda juda zarur va qo’l keladi. Qidiruv algoritmlari ko’p joylarda ishlatiladi masalan googleda saytlarda ham kerak bo’ladi. Googleda Z algoritmiga asoslanib ishlaydi. Bu algoritm massiv orqali ishlaydi bunda biz qidirayotgan ma’lumotga o’xshash malumotlarni ham chiqarib beradi. Matritsali 24 algoritm esa matritsa elementlari orqali ishlaydi. Bu algoritmlarni bir nechta takomillashgan variantlari ham ishlab chiqilgan. Algoritmlarning ishlash prinsipi qancha oson ishlasa biz ishlatayotgan dasturlar va shu algoritm asosida ishlayotgan har bir narsaning ishlashi ham juda osonlashadi v ava foydalanuvchi uchun soddaroq holatga keladi. 25 Foydalanilgan adabiyotlar 1. Narasimha Karumanchi - Data structures and algorithms made easy Copyright ©2010 by CareerMonk.com All rights reserved. 2. Big C++ - Wiley India 3. C++: The Complete Reference- Schildt, McGraw-Hill Education (India) 4. C++ and Object Oriented Programming – Jana, PHI Learning. 5. Object Oriented Programming with C++ - Rajiv Sahay, Oxford 6. Mastering C++ - Venugopal, McGraw-Hill Educa-tion (India) 7. Vanderbilt universiteti www.dre.vanderbilt.edu/ schmidt / (615) 343-8197 8. Dr. Subasish Mohapatra . Object Oriented Pro-gramming Using C++ 9. The C++ Standard Library A Tutorial and Reference by Nicolai M. Josuttis 26

O’zbekiston Respublikasi Oliy ta’lim, fan va innovatsiyalar vazirligi Sharof Rashidov nomidagi SAMARQAND DAVLAT UNIVERSITETI INTELLEKTUAL TIZIMLAR VA KOMPYUTER TEXNOLOGIYALARI FAKULTETI Dasturiy injiniring yo’nalishi 104-guruh talabasi Toshtemirov Isrofilning Algoritm va ma’lumotlar strukturasi fanidan “Matritsa qidiruv algoritmlari” mavzusida tayyorlagan KURS ISHI Tekshirdi:____________________ Samarqand 2023-yil 1

MUNDARIJA Kirish……………………………………………………………………………….3 1. Algoritm va ma’lumotlar strukturasi fanining mazmuni va vazifalari…………..4 2.Algoritm haqida…………………………………………………………………..5 3.Qidiruv algoritmlari………………………………………………………………7 4.Matritsa…………………………………………………………………………...9 5.Matritsa qidiruv algoritmi………………………………………………………10 6.Matritsa qidiruv algoritmi afzalliklari va kamchiliklari…………………………. 7. 6.Xulosa…………………………………………………………………………26 7.Foydalanilgan adabiyotlar………………………………………………………27 2

Kirish. Yangi XXI - asrda axborot texnologiyalari hayotimizning turli jabhalariga kirib borishi axborotlashgan jamiyatning shakllantirishga zamin yaratib bermoqda. "Internet", "Elektron pochta", "Elektron ta'lim", "Elektron boshqaruv", "Elektron hukumat", "Masofaviy ta'lim", "Ochiq ta'lim", "Axborotlashgan iqtisod" kabi tushunchalar hayotimizga kirib kelishi jamiyatimizning axborotlashishiga intensiv ta'sir ko`rsatmoqda. Axborot – kommunikatsiyalari orqali mamlakatlarning milliy iqtisodi globallashib, axborotlashgan iqtisod shakliga o'tmoqda, ya'ni milliy iqtisoddagi axborot va bilimlarning atilgan axborot va bilimlarning 90 % so'nggi 30 yil mobaynida yaratilgan bo'lib, ular hajmining ko'payib borishi axborot- kommunikatsiyalaridan samarali foydalanishni talab etmoqda. Ko'plab mamlakatlar o'zlarining istiqboldagi rivojlanishini axborotkommunikatsiyalari asosida yo'lga qo'yishni anglab yetishgan. Mustaqil O'zbekiston Respublikamizda ham jamiyatni axborotlashtirish, kompyuter ilmini o‘qitishni rivojlantirish bo'yicha Qonunlar qabul qilinib, ular asosida bir qator dastur va tadbirlar amalga oshirib kelinmoqda. Jumladan, O'zbekiston Respublikasi Prezidentining «Axborotlashtirishni yanada rivojlantirish to'g'risida» 2002 - yil 30 - maydagi PF- 3080- son Farmoni asosida 2010- yilgacha Axborot-kommunikatsiyalarini rivojlantirish bo'yicha milliy dastur ishlab chiqilgan bo'lib, u hozirda butun respublikamiz milliy iqtisodiyotning turli tarmoqlari va sohalarida tatbiq qilinmoqda. Algoritm va ma’lumotlar strukturasi fani Hozirgi kunda biror bir sohada ishni boshlash va uni boshqarishni kompyutersiz tasavvur qilish qiyin. XXI asr savodxon kishisi bo’lishi uchun kompyuter savodxon bo’lish, axborot texnologiyalarini puxta egallamoq lozim. Har bir mutaxassis, u qaysi sohada ishlashdan qat’iy nazar, o’z vazifasini zamon talabi darajasida bajarishi uchun axborotni ishlab chiqaruvchi vositalar va ularni ishlatish uslubiyotini bilish va ishlash ko’nikmalarga ega bo’lishi zarur. Talabalarni ijtimoiy-iqtisodiy va ma’naviy muammolarni hal etishga safarbar qilmoq uchun tegishli axborotlarni o’z vaqtida to’plab, qayta ishlab, muayyan bir tartibga solish va zudlik bilan kishilarga etkazish kerak bo’ladi. Buning uchun jamiyatni axborotlashtirish dasturini amalga oshirish va ilg’or axborot texnologiyasini joriy etish zarurdir. Dasturlarni mustaqil tuzishdan 3

maqsad kompyut е rga mutloq xokimlik qilish, ya’ni ish davomida yuzaga k е ladigan muammolarni t е zroq hal etish imkonini yaratishdir. Kompyut е r dasturlari s е rm е hnat ishlarni avtomatlashtiradi, xatolarni kamaytiradi va m е hnat unumdorligini oshiradi. Bundan tashqari, dasturlar tuzish juda ham mashg’ulotdir. Dasturlarni yaratish jarayonida qo’yilgan masalaning yechish algoritmi dastlab to’g’ri ishlab chiqilishi muhim axamiyatga ega. Shuning uchun algoritmlarni tuzish va dasturlarni ishlab chiqish bir-biri bilan chambarchas bog’liq jarayonlardir. Oliy o’quv yurtlarining informatika, axborot t е xnologiyalari, amaliy mat е matika kabi yo’nalishlarida ta’lim olayotgan talabalar algoritmni ishlab chiqish, dasturlar yaratish, ularni sinash, sozlash, tahlil qilish uchun bilimlarni puxta o’zlashtirishlari zarur. Bunda, ta’lim oluvchi uchun dasturlarni ishlab chiqishda asosiy va eng muhim bosqich hisoblangan algoritmlarni tuzish va shular asosida dasturlar yaratish haqida ma’lumotlarni b е ruvchi adabiyotlar k е rak. Ma’ruzalar matni Oliy o’quv yurtlari talabalari uchun mo’ljallab yozilgan va zamonaviy kompyut е r t е xnologiyalarini mustaqil ravishda o’rganayotgan barcha qiziquvchilar uchun ham foydalidir. Algoritm tushunchasi zamonaviy matematika va informatikaning asosiy tushunchalaridan biri hisoblanadi. Algoritm termini o’rta asrlar ulug’ matematigi al- Xorazmiy nomidan kelib chiqqan. XX asrning 30- yiligacha algoritm tushunchasi ko’proq matematik ma’no emas, balki metodologik ma’noni kasb etar edi. Algoritm deganda, u yoki bu masalalar sinfini yechish imkonini beruvchi aniq ifodalangan chekli qoidalar majmui tushunilgan. EHM larning paydo bo’lishi bilan algoritm tushunchasi yanada keng tarqaldi. EHM va dasturlash usullarining rivojlanishi algoritmlarni ishlab chiqish avtomatlashtirishdagi zaruriy bosqich ekanligini tushunishga yordam berdi. EHM larning paydo bo’lishi algoritmlar nazariyasining rivojlanishiga olib keldi. Algoritmlarni tuzish – bu ijodiy ish bo’lib, 4

ixtiyoriy zaruriy algoritmni tuzish uchun umumiy usullar mavjud emas, kishining ijodiy qobiliyatiga bog’liq. Albatta, algoritmni aniq sxema bo’yicha tuzish zarur bo’lib qoladigan sodda hollar ham mavjud. Bunday hollarda yechilish algoritmi avval biron kim tomonidan olingan masalalarni misol keltirish mumkin. Algoritm Algoritmlarning turli ta’riflari mavjud. Rasmiy ta’riflardan biri bo’yicha algoritm bu qo’yilgan masalani bir xil yechilishiga olib keluvchi aniq harakatlarning ketma-ketligi. Bu tushunchadan algoritmning quyidagi xossalari kelib chiqadi: 1. Diskretlilik – ya’ni aniqlanayotgan jarayonni qadamba-qadam ko’rinishi. 2. Ommaviylik – algoritm o’xshash masalalar turkumini yechishi kerak. 3. Tushunarlilik – algoritmda beriladigan ko’rsatmalar foydalanuvchiga tushunarli bo’lib, uning talablariga javob berishi kerak. 4. Aniqlilik – algoritmda ma’lum tartibda amallarni bajarish nazarda tutilishi kerak va bajaruvchiga joriy qadam tugatilishi bilan qaysi qadam keyingi bo’lib bajarilishi aniq ko’rsatilishi kerak. Algoritmlar rasmiy ravishda bajariladi, bu degani bajaruvchi ajarilayotgan amallarni mazmunini anglash shart emas. Algoritm tuzish jarayoniga algoritmlashtirish deyiladi. Algoritm tuzish jarayonida nazariy va amaliy nuqtai nazardan algoritmlash, dasturlash va EHM larni qo’llash bilan bog’liq bo’lgan bilimlar kerak. Asosiy maqsad bu masalani qo’yish, masalaning yechish algoritmini tuzish, algoritmi mashina dasturi ko’rinishida amalga oshirish va algoritmni samaradorligini ko’rsatish uammolarini o’rganish. Bu jarayonlar algoritmni to’liq yaratish tushunchasiga olib keladi va quyidagi bosqichlarni belgilaydi: 1. Masalaning qo’yilishi. 2. Modelni yaratish. 3. Algoritmni ishlab chiqish. 4. Algoritm to’g’riligini tekshirish. 5. Algoritmni amalga oshirish. 6. Algoritmni va ularning murakkabligini tahlil qilish. 5

O'xshashlar

Qidiruv algoritmlari
Matritsada qidiruv algoritmlari
INTERPOLATSION QIDIRUV
IZLASH ALGORITMLARI. KNUT VA MORE ALGORITMLARI
Saralash algoritmlari