|
1-1-11-amaliy
ALGORITM TUSHUNCHASI VA ULARDAN FOYDALANISH
Bizning dunyomizdagi deyarli hamma narsa qandaydir qonun va qoidalarga bo'ysunadi. Zamonaviy ilm-fan hali ham to'xtamaydi, buning natijasida insoniyat juda ko'p formulalar va algoritmlarni biladi, ularga amal qilib, siz tabiat tomonidan yaratilgan ko'plab harakatlar va tuzilmalarni hisoblashingiz va qayta yaratishingiz, inson tomonidan ixtiro qilingan g'oyalarni amalga oshirishingiz mumkin.
Algoritm - XII asrda paydo bo'lgan tushuncha. "Algoritm" so'zining o'zi "Hind hisobi haqida" kitobini yozgan Yaqin Sharqning mashhur matematiki Muhammad al Xorazmiy nomining lotincha talqinidan kelib chiqqan. Bu kitobda arab raqamlari yordamida natural sonlarni qanday to‘g‘ri yozish yo‘l-yo‘riqlari ko‘rsatilgan va bunday sonlar ustidagi ustundagi amallar algoritmi tavsifi berilgan.
XII asrda "Hind hisobi to'g'risida" kitobi lotin tiliga tarjima qilingan va keyin bu ta'rif paydo bo'lgan.
Algoritmni yaratish ijodiy yondashuvni talab qiladi, shuning uchun ketma-ket harakatlarning yangi ro'yxati faqat tirik mavjudot tomonidan yaratilishi mumkin. Ammo allaqachon mavjud bo'lgan ko'rsatmalarni bajarish uchun tasavvurga ega bo'lish shart emas, hatto ruhsiz texnika ham bunga dosh bera oladi.
Berilgan ko'rsatmalarning aniq bajarilishining ajoyib namunasi bo'sh mikroto'lqinli pech bo'lib, uning ichida oziq-ovqat bo'lmasa ham ishlashda davom etadi.
Algoritmning mohiyatini chuqur o'rganishga hojat bo'lmagan sub'ekt yoki ob'ekt rasmiy ijrochi deb ataladi. Shaxs rasmiy ijrochiga ham aylanishi mumkin, ammo u yoki bu harakat foydasiz bo'lsa, fikrlaydigan ijrochi hamma narsani o'ziga xos tarzda bajarishi mumkin. Shuning uchun asosiy ijrochilar kompyuterlar, mikroto'lqinli pechlar, telefonlar va boshqa uskunalardir. Informatika fanida algoritm tushunchasi eng katta ahamiyatga ega. Har bir algoritm ruxsat etilgan harakatlarni hisobga olgan holda ma'lum bir mavzuni kutish bilan tuzilgan. Subyekt ko'rsatmalarni qo'llashi mumkin bo'lgan ob'ektlar ijrochi muhitini tashkil qiladi.
Bizning dunyomizdagi deyarli hamma narsa qandaydir qonun va qoidalarga bo'ysunadi. Zamonaviy ilm-fan hali ham to'xtamaydi, buning natijasida insoniyat juda ko'p formulalar va algoritmlarni biladi, ularga rioya qilib, siz tabiatning ko'plab harakatlari va ijodlarini hisoblashingiz va qayta yaratishingiz va inson tomonidan ixtiro qilingan g'oyalarni hayotga tatbiq qilishingiz mumkin. Ushbu maqolada biz algoritmning asosiy tushunchalarini ajratamiz.
Hayotimiz davomida bajaradigan ko'p harakatlarimiz bir qator qoidalarga rioya qilishni talab qiladi. Unga yuklatilgan vazifalarning sifati va natijasi insonning nima, qanday va qanday ketma-ketlikda bajarishi kerakligi haqida qanchalik to'g'ri ekanligiga bog'liq. Bolaligidan ota-onalar farzandlarida asosiy harakatlar algoritmini ishlab chiqishga harakat qilmoqdalar, masalan: uyg'onish, to'shak yig'ish, tishlarini yuvish va yuvish, mashqlar qilish, nonushta qilish va hokazo. uning ertalabki hayotini ham o'ziga xos algoritm deb hisoblash mumkin.
Algoritm - bu muayyan masalani hal qilish uchun shaxs bajarishi kerak bo'lgan ko'rsatmalar to'plamini bildiruvchi tushuncha.
Umuman olganda, algoritm juda ko'p ta'riflarga ega, bir nechta olimlar uni turli yo'llar bilan tavsiflaydilar.
Agar odam har kuni ishlatadigan algoritm hamma uchun har xil bo'lsa va ijrochining yoshiga va vaziyatga qarab o'zgarishi mumkin bo'lsa, matematik masalani hal qilish yoki texnologiyadan foydalanish uchun bajarilishi kerak bo'lgan harakatlar to'plami. hamma uchun bir xil va har doim o'zgarishsiz qoladi.
Algoritmning boshqa tushunchasi mavjud, algoritmlarning turlari ham farqlanadi - masalan, maqsad sari intilayotgan odam uchun va texnologiya uchun.
Axborot texnologiyalari asrimizda odamlar har kuni o'zlaridan oldin boshqa odamlar tomonidan yaratilgan ko'rsatmalar to'plamini bajaradilar, chunki texnologiya bir qator harakatlarni aniq bajarishni talab qiladi. Shuning uchun maktab o'qituvchilarining asosiy vazifasi bolalarni algoritmlardan foydalanishga o'rgatish, mavjud qoidalarni hozirgi vaziyatga mos ravishda tezda tushunish va o'zgartirishdir. Algoritm tuzilishi har bir maktabda matematika va informatika darslarida o‘qitiladigan tushunchalardan biridir.
Algoritna bu aniq hisoblashlarni bajarvivchi protsedtira bo‘lib unga kirisli qismida kattalik yoki kaitaliklar berilib cliiqishda natijaviy kałtalik yoki katialiklar olinadi. Demak algoritiri hísoblovchi qadarnlardan taslikil topgan bo‘1ib dasłlabki qiyinatlarga ko‘ra natijaviy kałtaliklar qiyrnatini beradi. Bti holatni sxematik tanda quyidagicha tasvirlash inumkin.
Algoritmni qo“yilgan hisoblash niasalani (computational problem) aniq bajaruvchi uskuna sifatida ham qaralishi miiinkin. Algoriłnilarda keltirilgan protseduralar yordamida kattaliklar bilan amallar bajarilib natijalar olinadi. Agar algoritmni har qanday kiruvchi qiymatlar uchun aniq va mos chiquvchi qiymatlarni bera olsa u aniq (correct) deb yuritiladi. Algorimlardan amaliyotda foydalanishga ayrim ınisollarni keltiraırıiz:
Odanı DNK si tarkibidagi 100 ming gen identifikatsiyasi, DNK-ni tashkil eluvclıi 3 ınilliaı d asosiy juftlikni saralashva tahlili masalasi;
lntemetda ma’luırotlar olish ınasalasi: kata hajındagi ına’lumollarni olish, jo‘natish,qidiruv va optilnal marshrut tanlash;
Electron komrnertsiya ırıasalalarida( kredit karla noınerlari , parollar, bank xisob-kitob raqamlari himoyasi, raqaınli imzo va b);
Algoritınlarni ishlab chiqishda nıasalani yechiıni ıtchun zarur bo‘1gan vaqt va xotira hajıni ınuhiın ko‘rsatgichlar lıisoblanib algoritınlami yaratishda ularni samarali foydalaııishni hisobga olish zarttr. Aynan bir ınasalani yechish uchun turi i algoritınlar tuzilishi muınkin. Ular bir-biridan sarnardorlik darajasi bilan farqlanadilar. Bu farq lurli texnik va dasturiy ta’ıninotlarda har xil bo‘lishi mumkin.
Umunıan olganda algoritm - bu quyilgan masalaning echimiga olib keladigan, ma’lum qoidaga binoan bajariladigan aınallaming chekli qadanılar kelma-ketligidir. Boshqaclıa qilib aytganda algoritm boshlang‘ish rna’lumotlardan naıijagasha olib keluvshi jarayonning aniq yozilishidir.
Algoriım tushunshasining turli la’riflari bir qator talablarga javob berishi kerak:
algoriım chekli sondadi elementar bajariluvshi ko’rsatmalardan iborat bo‘lishi kerak;
algoritrn chekli sondadi qadanılardan iborat bo‘lis1ıi kerak;
algoritın barsha boshlang‘ish berilganlar vıshun umumiy bo‘lis1ai kerak ;
algorilrn to‘g‘ri echiınga olib kelishi kerak.
Har qanday algoritın nıa’lum ko‘ rsatınalarga binoan bajariladi va bu ko‘rsatnıalarga buyruq deyiladi. Yuqoridagi fikrga ko‘ra algoritm asosan masalani eshimini toppish ushun tuziladi.
Bitta masalalıi eshishning bir neshaalgoritnıi mavjud bo‘lishi nıumkin. Ular orasida eng samaralisini, bajarîlislai ushun eng kam amallar, mashina vaqti, xotira va h.k.ni talab qiluvslıi algoritrnni tanlash loziM. Saınarali algoritmlar nıavjud bo‘1ishi sharılari va ulami quı‘ish (ishlab shiqish)ni o‘rganislı algoritınlar nazariyasi asosini tashkil etadi.
Algoritm kibernetika va matematikaning asosiy tushunshalaridan biri bo‘lib bu ataına o‘rıaasr1arda vashab ijod ctgan buyuk o‘zbck maıemaıigi Al- Xoraznıiy nolridan kelib shiqqan. U IX asming 825 yilidayoq o‘zi kashf etgan o‘nli sanoq tiziınida to‘rt ariiınetikaamallarini bajarish qoidalarini bergan. Arifnıetikaanıallarini bajarislı jarayoni esaalxoraznı deb ataigan. Bu ataına 1747 yildan boshlab algorisnıus, 1950 yilga kelib algofİfm deb ham ataldi. Fanda "Yevklid algoritnıi", "G‘iyosiddin Koslıiy algoritıni", "Laure algoritmi”, "Markov algoritmi” deb ataluvshi algoritrnlar ma’l um algoritm tushtınslaasi tobora kengayib borib, kibernetikaning nazariy va mantiqiy asosi hisoblangan algoriımlar nazariyasi paydo bo‘lgan. Kompyuterlar paydo bo‘lishi bilan algoritm atanıasi hozirgi ına’nosi bilan axborot texnologiyalari solaasida eng asosiy ataınalardan biri bo‘lib qoldi. Odatda algoritırlar u yoki bu hisoblashga doir nıasalalami (somputational probleıns) eshislı ushun luziladi
Qo‘şi1gan masala ushun yaratiladigan algoritında kiruvshi va shiquvshi ıra’l umotlar muhiırı alıaıriyatga ega, agar algoritm to‘g‘ri tuzilgan bo‘lsa, ijroshi (koınpyuter) aniq natijalar beradi.
Algoritnı quyidagi xossalarga ega: aniqlik, tvıshtınarlil ik, oırıaıaviyl ik, natijavijlik va diskretlik.
Aniqlik va tushunarlilik - degandaalgoritında ijroshiga berilayotgan ko’rsatrnalar aniq ınazmunda bo‘lislai tushuıailadi. SHunki ko‘rsatmalardagi noaniqliklar nıo‘ljal1angan ınaqsadga erishishgaolib kelnıaydi. ljroslıiga tavsiya etiladigan ko’rsaııııalar tushunarli ınazmvında bo‘lishi sharı, aks holda ijroshi tırri bajaraolmajdi.
Onaınavivl ik - deganda mar bir algoritnı mazmuniga ko’ra bir lurdagi ınasalalarning barshasi ushun ham o‘rinli bo‘lishi, ya’ni umumiy bo‘lishi tushuniladi.
Natiiavivlik —deganda algoritnıda chekl i qadamlardan so‘ng al batta natija bo‘lislıi tuslıuniladi. Shuni ıa"kidlasla joizki, algoritın avvall’dan ko‘zlandan maqsadga erishishga ol i b kelınasligi hani rnumk in. Bunda ba’zan algoritmning noto’g‘ri ıvızilgani yoki boshqa xatolik sabah bo‘1ishi mumkin, ikkinshi ıomondan, qo‘yilgan masala i jodiy yeslıimga ega bo‘lmasligi hain ınvınıkin. Lekin salbiy natija hank deb qabvıl qilinadi.
Diskretlik — deganda algoritnılami chekli qadaınlardan tashkil qilib bo‘laklash iınkoniyati tushuniladi
Algoritmlarga doir quyidagi masalalami misol sifatida keltirish nıtırnkilı:
Talabalıi kundal ik ishlarni tashkil etish; To‘rtburshak pirenıetri va yuzasini hisoblash ;
R radusl i doi rani yuzasini va aylana uzunligini toppish ;
A¡, Al. A„ .. A„ sonlarni toq elenıentlarini yig‘indisini toppish;
Berilgan ketına-ketlik sonlami o‘sish (kamayish) tartibda joylaslıtirislı va lı.k.
Algoritnıning ushta turi nsavjud: shiziqli, tarmoqlantıvshi va takrorlanuvshi(tsiklik).
CHiziqli algoritmlar - mesih qanday shartsiz faqat ketnıa-ket bajariladigan jarayonlardir.
Takrorlanuvshi alooritmlar - ma’lum shartlarga muvofiq bajariladigan jarayonlardir.
Takrorlanuvchi algoritmlar - biron bir slıart tekshirilislıi yoki biron paranıetming har xil qiyrnatlari asasidachekli ravishda takrorlanish ytlz beradigan jarayonlardir.
Algoritnılarni tvırli usullarda tasvirlash nıunıkin.
so‘z bil an ifodalash;
fomıulalarda berislı;
blok-sxenıalarda tasvirlaslı;
dastur shaklida ifodalash va boshqalar.
Algoritnılanıi blok-sxema ko‘rinislıda tasvirlaslı qulay va tushunarli bo'1gani ushun eng ko‘p ishlatiladi. Dunda algoritmdagi har bir ko’rsatma o‘z shaklida ega. Masalan: parallelograııım ko‘rinishdagi belgi ma’luırotlarni kiritish va shiqarish; to‘g‘ri to‘rtbılrshak belgisi hisoblash jarayonini; roınb belgisi shartlarning tekshirilishini bildiradi. Algoritiınni blok-sxeına shaklida tasvirlashda quyidagi geometrik figuraiardan foydalaniladi:
Norbit
|
Belgılanıshı
|
BaJaradıgan vazıfası
|
Jarayon
|
|
Bir yoki bir nechta amallamı
bajarilishi natijasida rna’l unaotlarning uzgarislıi
|
Karor
|
|
Bıror sharıga boglık ravıslıda
algoritmning bajarilish yunalishini tanlash
|
SHakl
uzgartirish
|
|
Dasturııı uzgartıruvclıı buyruk yoki buyruklar tvırkuınini uzgarıirish amalini bajarish
|
Avval
jarayon
|
|
Oldınd‹ın ishlab chıkılgan dastur
yoki algot‘itnıdan foydalanish
|
Kiritish
CHikarish
|
|
Axborotlami kayta islılash mvınıkin
bulgan shaklga utkazish yoki olingan natijani tasvirlasla
|
Displey
|
|
EXMga ulangan displeydan
axborotlami kiritish yoki chikarish
|
Xvjjat
|
|
Axborotlarni kogozga claikarish yoki
kogozdan kiritish
|
Axborotlar
okiıni chizigi
|
|
Bloklar orasidagi boglanishlami
tasviılash
|
Boglagiclı
|
|
Uzilib kolgan axborot okinalarini
ulash belgisi
|
Boshlash
Trıgatish
|
|
Axborotni kayta ishlaslıni boslılash,
vaktincha yoki bvıtunlay tuxtatislı
|
I zola
|
|
Bloklarga tegishlı ttırli xildagi
tuslıvıntirishlar
|
Hozirgi kunda juda ko‘ p algoritınik tillar mavjud bo‘1ib, ulami dasturlash tillari deb atayıniz. Algoritınik til - algoritınlarni bir xil vaaniq yozish ushun ishlatiladigan belgilashlar va qoidalar tiziınidir. Algoritınik til oddiy tilga yaqin bo‘lib u matematik belgilami (yuqorida aytil ganidek) o‘z ishigaoladi. Qo‘yilgan ınasalalaı ni eshislıga tuzilgan algoritlrlami to‘ g‘ ridan- to‘g‘ri mashinaga beri b, eslıib bo‘ lmaydi, slıu sababli yozilgan algoritmni biror bir algoritmik tilga o‘tkazislı zanır. Har qanday algoritmik til o‘z go‘ llanilislı sohasiga ega. Masal an, o‘quv jarayonlari ushun Pascal, Delplıi, VBA, java, C++dasturlash tillari va boshqalar.
Algoritmlar samaradorligini baholash.
Koınpyuteringizning tezligi va xotira rniqdorini abadiy oshirish ınuıııkin, deylik. Bu holaıda algoriıınlar o‘rganish kerakrni? Bor bo‘lishi rnumkin, lekin faqat nanıoyish etish uchun, eclıiırı usulini cheklangan vaqti bor va u to‘g‘ri javob beradi.
Koınpyuterlar juda tez bo‘lganda, ınasalani echishga har qanday konkret usul lııos kelannidi.
Albatta, bugungi kunda juda sanıarali kompyuterlar, lekin ularning ishiashi juda katta bo‘1ishi ıBumkin eınas. Xotira ham arzon, lekin bepul bo‘lishi ıntunkin eınas. Shunday qilib, hisob-vaqti - cheklangan resurs, shuningdek xotira ıniqdori hani. Siz donolik bilan bu resurslarini boshqarishingiz kerak,bunga algoritnalardan, vaqt va xotira xarajatlaridan saıııarali foydalanish kerak.
Har xil masalalarni yechish uchun neo‘ljallangan, turli xi1 algoritmlar, saıııaradorligi bo‘yicha sezilarli darajada farq qiladi. Bu farqlar juda katta bo‘1ishi ınumkin ekan. Masalan, ikki saralash algorit@ar, 2-darsta muhokama qilinadi. Birinclıisini bajarislı uchun, saralashni joylashtirislı, bunga vaqt kerk bo‘1adi, shunday balıolmımoqda cın2 , n- bu saralash elelnentlarning soni, c, bo‘lsa bu — doiıaaiy, n ga bog‘liq enaas. Shunday q il ib, bu algoritrnni vaqti taxminan n2 proporısional.
Ikkinchi algoritm anıalga oshirish uchun, saralash birlashtirishi, vaqt talab etadi, ıaxıninan cin lg n ga teng, lg n- bu log, n qisqa yozuvi, c, bu - boshqa doirniy n ga bog‘liq eıııas.Odatda doimiy usul qo‘shiınchalar doimiy birlashish usulidan kiclıikroq, c < cz Doimiy omillar algorilnıni ish vaqti¡;a juda kan ta’sir q iladigan bog‘1iq oınillardan ko‘ra, shunga ishoncla hosil qilaylik.Saralashni joylaslıtirish algoritnıni isİı vaktini shunday yozaylik c ı n n,birlashtirish saralashini esa cen lgn.
Joylaslıtirish saralashi n oısıilga ega, birlashtirish saralashi esa lg n ga ega bu esa sezarli darajada kaınligini ko‘ rishina iz muınkin. K iritish hajnıi n elarlicha katta bo‘lganda 9o‘shislı saralashi odatda tezroq bo‘1adi, saralash ob'ektlar kiclıik hajındagi birlashtirishda, katta lı uchun aharniyatsiz qiymati lgn nisbatan n to‘1iq doirniy tarqi qadriyatlar o‘ınini qoplash, aslida birlashish yanada sezilarli naınoyon bo‘ladi, saralash afzalligi ziyoda
idagi misol shuni ko‘rsatadiki, kompyuter apparat kabi algoritınlarni hain, texnologiya sifatida lıisobga olinislıiıniz kerak.
Umumiy tiziın ish faoliyatini algoritm samaradorligiga hani bog‘liq, va apparat kuclıiga hain. Algoritm rivojlantirish sohasida jadal rivojlantirish bo‘lyapti, boshqa koıııpytıter texnologijalaridek
Savol tvıg‘iladi, algorıtııılar shunclıalik ınulıiıni, zaıronaviy konıpytıterlarda ishlaydigan bo“lsin, agar shunday kabi yuqori texnologi)'alar boshqa sohalarda ulkan yutuqlarga erıshilgan bo‘Isa
zanıonaviy kompytıter nıinıarileri va ulanıing ishlab shiqarish texnologiyalari,
osonlik bilan erislıislı, intuitiv grafik foş'dalaııuvclıi interfeysi (GUI);
Ob'ektga yo‘naltirilgan tizimlar;
lııtegıatsiyalaslıgan veb texnologiyasi;
tezroq tarınoqlari, simli va siınsiz.
Misol uchun, bir joydan boshqasiga olish uchun qanday belgilaydigan Web xizıaaat. Uni aınalga oshirish bir yuqori saıaıarali apparat, grafik foydalanuvclli iıtterfeysi, bir global taınoq va, el1tin1oI, bir ob’ckt yo‘naItirilgan yondashuv yotadi.
Bundan tashqari, btınday yo‘nalishlarini topish kabi bir berilgan veb- xiznıati tomonidan anıalga nıuayyan operatsi) atar uchun zarur algoritnılarni foydalanish, ko‘rish va enterpolasyon nıanzilini, xantalar bilan foydalaniladi. Bundan tashqari, dastur,y\ıqori saviyada algoritmik ılJaznlcınini talab qilmaydi, ktıchli algoritııılarda bog‘li‹ı Bu dastur ishlaslı apparat islıiga bog‘lit} ekaııligi rna’lum, va aınaliy rivojlanishida turli algoritınlardan foydalaniladi.
Biz haınnıaıııiz bilanıizki, ilova yaqindan i,'rafik foydalantıvchi interfeysi bilan bog“liq, va har qanday t rafik foydalanuvclıi interfeysiııi ishlab clıiqish uchun talab algoritmlari kerak bo‘ladi. Tarmoq ustida ishlaydigan ilovalarni eslatib o‘taıniz.
“ALGORITMLAR” FANIDAN O‘QUV USLUBIY MA.IMUA
Ular faoliyat olib borishlari uchun, algoritmlarga asoslanga ş o‘nalishni olib borishlari kerak bo‘ladi. Eng keng tarqalgan dasturlar tilda tvıziladi, nıashinadan farqli. Ulaming kodi lurli konıpilyator va interpretatorlar bilan ishlov beriladi, turi i algoritnalardan keng foydalanadi. Bundan taslıqari, kompytıterlar kuchini doirniy o‘sishi, ular tobora murakkab vazifalanli hal qilish uchun qo‘llaniladi. Biz nıuanımoni ınurakkabligini ortishinıiz bilan, i k ki saralash usullari qiyosiy ıahlili ınisolida ko‘rib turganimizdek eng muhinı farqlar algoritnılarini samaradorligini ko‘rinadi oshirilnıo9da.Asosiy algoritmlar va ulanıi rivojlantirish usullari-asosiy xusvısiyatlatdan biri.Zanıonaviy kompytıter lexnologiyalari bilan, ayrim vazifalanıi algoritmlarni bilınagan holda liam qilinislıi munakin, tek in bu sohada kop narsaga erishish nıuınkin.
|
