Ommaviylik – algoritm o’xshash masalalar turkumini yechishi kerak.
Hár bir algoritm mazmunına kóre bir túrdegi máselelerdiń barlıǵı ushın da orınlı bolıwı kerek. YA'ni máseledegi baslanǵısh maǵlıwmatlar qanday bolıwınan qaramastan algorim sol xildagi hár qanday máseleni sheshiwge jaramlı bolıwı kerek. Mısalı, eki ápiwayı kasrning ulıwma mahrajini tabıw algoritmi, bólsheklerdi túrlishe ózgertirip bersangiz da olardıń ulıwma mahrajlarini anıqlap beraveradi. Yamasa úshmúyeshliktiń júzin tabıw algoritmi, úshmúyeshliktiń qanday bolıwınan qaramastan, onıń júzin esaplab beraveradi.
7. Algoritmlerdiń nátiyjelilik qásiyeti.
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 yechimga ega emasligini aniqlash ham natija hisoblanadi. Agar ko‘rilayotgan jarayon cheksiz davom etib natija bermasa, uni algoritm deb atay olmaymiz.
Har bir tuzilayotgan algoritm qo‘yiladigan amallar sonidan qat’iy nazar cheklangan miqdordagi qadamlardan keyin natija berishi shart. Agar ko‘rib o’tiladigan jarayon cheksiz davom etib natija bermasa uni algoritm deb bo‘lmaydi. Shuni ta’kidlab o‘tish joizki, algoritm avvaldan ko‘zlangan maqsadga yetishishga olib kelmasligi mumkin. Bunga ba‘zi hollarda algoritmning xato tuzilganligi yoki istisnolar sabab bo’lgan bo‘lishi mumkin. Boshqa tomondan aytganda esa, masalaning yechimi ijobiy ko‘rsatkich chiqarmasiligi mumkin. Lekin bu natija salbiy bo‘lsa ham natija deb qabul qilinadi.
8. Algoritmlerdiń diskretlilik ózgesheligi.
Diskretlilik – ya’ni aniqlanayotgan jarayonni qadamba-qadam ko’rinishi.
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.
Algoritmda masalalar yechimini ifodalash jarayoni alohida olingan sodda ko‘rsatmalar ketma-ketligini qadamma-qadam bajarishdan iborat bo‘lishi kerak. Har qanday ko‘rsatmalar ham algoritm bo‘la olmaydi. Masalan, “Texnologik liniyani ishga tushirishdan oldin liniyani tekshiring” talabnomasi uzluksiz xarakterga ega bo‘lganligi uchun algoritm bo‘la olmaydi. Algoritmda har bir bajariladigan ko’rsatma qismi algoritmn qadami hisoblanadi.
9. Algoritmlerdi bahalaw kriteriyalari haqqında maǵlıwmat beriń
10. O () bahalaw haqqında maǵlıwmat beriń
Quyida O() (Big O notation) haqida ma'lumot o'zbekcha berilgan:
O() (Big O belgisi) algoritmlarning asimptotik xarakterli ishlash vaqtini baholash uchun ishlatiladi. U algoritm unumdorligini ifodalash uchun qo'llaniladi va algoritmning kirish ma'lumotlari o'lchamiga bog'liqligi darajasini ko'rsatadi.
O() belgisi algoritmning eng yomon holatini ifodalaydi. Masalan, agar O(n) bo'lsa, bu shuni anglatadiki, kirish ma'lumotlari o'lchamiga proporsional ravishda algoritm ishlash vaqti ortadi. Agar O(1) bo'lsa, kirish ma'lumotlari o'lchamidan qat'iy nazar, algoritm ishlash vaqti o'zgarmaydi.
Ba'zi muhim O() belgilari:
1. O(1) - Doimiy vaqt murakkabligi. Kirish ma'lumotlari o'lchamiga bog'liq emas.
2. O(log n) - Logarifmik vaqt murakkabligi. Kirish ma'lumotlari o'lchamining logarifmiga proporsional.
3. O(n) - Chiziqli vaqt murakkabligi. Kirish ma'lumotlari o'lchamiga proporsional.
4. O(n log n) - Kvazi-chiziqli vaqt murakkabligi. Kirish ma'lumotlari o'lchamining logarifmiga proporsional.
5. O(n^2) - Kvadratik vaqt murakkabligi. Kirish ma'lumotlari o'lchamining kvadratiga proporsional.
6. O(2^n) - Eksponensial vaqt murakkabligi. Kirish ma'lumotlari o'lchamining darajasiga proporsional.
O() belgisi algoritm unumdorligini baholashda juda muhim rol o'ynaydi va algoritmlarni tahlil qilishda keng qo'llaniladi.
11. Algoritmlerdi bahalaw kriteriyalari
Algoritmlarni baholash uchun ko’pgina mezonlar mavjud. Odatda kirituvchi berilganlarni
ko’payishida masalani yechish uchun kerak bo’ladigan vaqt va xotira hajmlarini o’sish tartibini aniqlash
muammosi qo’yiladi. Har bir aniq masala bilan kiritiladigan berilganlarni miqdorini aniqlovchi qandaydir
sonni bog’lash zarur. Bunday son masalaning kattaligi deb qabul qilinadi. Masalan, ikkita matritsani
ko’paytirish masalasining o’lchami bo’lib, matritsalar kattaligiga xizmat qilishi mumkin. Graflar haqidagi
masalada o’lcham sifatida graf shohlarining soni bo’lishi mumkin.
Algoritm sarflanayotgan vaqt masalaning o’lchami funksiyasi sifatida algoritmni vaqt bo’yicha
qiyinligi deb nomlanadi. Bunday funksiyaga masalaning kattaligi oshganda limit ostidagi o’zgarish
asimptotik qiyinlik deb aytiladi.
Shunga o’xshab, hajmiy qiyinlik va asimptotik hajmiy qiyinlikni aniqlash mumkin.
Aynan algoritmning asimptotik qiyinligi natijada shu algoritm yordamida yechiladigan masalarni
kattaligini aniqlaydi. Agar algoritm n kattalikdagi kirishlarni 2 n С × vaqtda qayta ishlasa (c-const), unda
algoritmning vaqt bo’yicha qiyinligi ) ( 2 n O teng deb hisoblanadi, va n tartibda deb aytiladi.
Hisoblash mashinalar tezligi oshishiga qaramasdan, ular yordamida yechilayotgan masalalar
kattaligini oshishini algoritm qiyinligini tahlil orqali aniqlaydi.
12. Algoritmdi islew waqtı boyınsha bahalaw
Algoritmni bajarish uchun xotiradan egallagan hajmi bo’yicha baholash. Vaqtni baholash bajaruvchining fizik xarakteristikalari hisobga olinishi kerak, chunki har bir operatsiya har xil o’zgaruvchilar bilan bajarilganda vaqt ham har xil bo’ladi. Odatda o’rtacha tezkorlik qabul qilinadi, chunki aniq ma’lumotni har bir foydalanuvchi uchun yig’ib bo’lmaganligi sababli. Ketma-ket bajarilayotgan operatsiyalar sonini aniqlab, uni o’rtacha tezkorlikka ko’paytirsa, algoritm bajarilishining amalga yaqin bo’lgan vaqtini topishimiz mumkin.
13. Algoritm tariypini aytıń
Bugun siz algoritm tarifini so'radingiz. Algoritm bu kompyuter yoki boshqa qurilmalarda bajarilishi mumkin bo'lgan aniq ko'rsatmalar ketma-ketligidir. U muammoni hal qilish uchun turli xildagi amallarni bajaradi.
Algoritm uchun quyidagi asosiy xususiyatlar xos:
1. Aniqlik - algoritm har doim aniq va aniqlangan qadamlardan iborat bo'lishi kerak.
2. Natijaning yakunlanishi - algoritm ma'lum bir vaqtda to'xtashi va natijani berishi kerak.
3. Elementarlik - algoritmdagi har bir qadam oson bajarilishi kerak.
4. Izchillik - algoritmda birma-bir bajarish uchun aniq ketma-ketlik bo'lishi lozim.
5. Universallik - algoritm turli xil muammolarni hal qila olishi kerak.
Algoritmlar asosan quyidagi tuzilishga ega bo'ladi:
1. Kirish ma'lumotlari
2. Asosiy algoritm
3. Chiqish ma'lumotlari
Algoritmlarni bajarishda turli xil usullar (takrorlash, shartli operatorlar, funksiyalar va h.k.) qo'llaniladi. Algoritmlarni yozish uchun maxsus tillar (masalan, psevdokod, kod) ishlatiladi.
Algoritmlarni qo'llash kompyuter fanining asosiy yo'nalishlaridan biri hisoblanadi. Ulardan turli dasturlar yaratishda, muammolarni hal qilishda, ma'lumotlarni qayta ishlashda, optimal echimlarni topishda keng foydalaniladi.
14. Algoritmdiń tolıq qurıw basqıshların sanap beriń
Algoritmni to'liq qurish uchun quyidagi asosiy bosqichlarni amalga oshirish lozim:
1. Muammoni aniqlash va tahlil qilish:
- Muammoning mohiyatini tushunish
- Muammoga tegishli ma'lumotlarni yig'ish
- Muammoning chegaralarini belgilash
2. Algoritm loyihasini tuzish:
- Algoritmning kirish va chiqish ma'lumotlarini belgilash
- Algoritmning asosiy bosqichlarini aniqlab olish
- Algoritmning mantiqiy tuzilishini yaratish (ketma-ketlik, tarmoqlanish, takrorlanish)
3. Algoritm kodini yozish:
- Algoritmning mantiqiy tuzilishini qo'llab-quvvatllovchi dasturlash tilida kod yozish
- Algoritmni qismlar (funksiyalar, modullar) bo'lib yozish
- Algoritm kodini testdan o'tkazish va qisqartirish
4. Algoritm samaradorligini baholash:
- Algoritm bajarilish vaqtini, xotiradagi o'rni, resurs sarfini hisoblash
- Algoritmning turli ma'lumotlarda ishlash qobiliyatini tekshirish
- Algoritm optimalligi va samaradorligini oshirish yechimlarini izlash
5. Algoritm hujjatlashtirish:
- Algoritm vazifalari, kirish-chiqish ma'lumotlari, qo'llanilgan usullar haqida ma'lumot yozish
- Algoritm kodlarini tushunarsiz joylarini sharhlash
- Algoritm qo'llanilish sohalari va qo'llanish yo'riqnomasini yozish
Ushbu bosqichlarni amalga oshirish natijasida samarali va ishonchli algoritm yaratish imkoni tug'iladi.
15. Algoritmik sheship bolmaytuǵın máselelerge mısal keltiriń
Algoritmik yechimga ega bo'lmaydigan masalalarga quyidagilarni misol qilib keltirish mumkin:
1. Halqaro Matematik Muammolar:
- Rimanning Gipotezasi
- Puankarening Taxmini
- Goldbaxning Taxmini
Bu kabi matematik muammolar shunday murakkabki, ularning algoritmik yechimi hali topilmagan. Ular algoritmik yechimga ega bo'lmasalar-da, matematik tadqiqotlar uchun juda muhim ahamiyatga ega.
2. Suniy Intellekt masalalari:
- Ong va ongsizlik masalasi
- Mashinaning hissiy va estetik sezgilari
- Mustaqil qaror qabul qilish qobiliyati
Bu kabi muammolar hozirgi kunda sun'iy intellekt rivojining asosiy yo'nalishlaridan biri bo'lsada, algoritmik yechimga to'liq ega emas.
3. Ijtimoiy va iqtisodiy masalalar:
- Fuqarolik urushlarining oldini olish
- Kambag'allik va ocharchilikni bartaraf etish
- Iqlim o'zgarishlarining oldini olish
Bu kabi global muammolarning algoritmik yechimi mavjud emas, chunki ularning ko'plab noaniq va subjektiv jihatlari bor.
Umuman olganda, algoritmik yechimi bo'lmaydigan masalalar, ko'pincha, murakkab tabiiy yoki ijtimoiy hodisalar bilan bog'liq bo'ladi. Ular hali to'liq o'rganilmagan yoki ularni algoritmlashtirish juda qiyin.
16. Algoritmdiń súwretlew usılları
Algoritmlarni tasvirlashda quyidagi usullardan foydalaniladi:
1. Psevdokod (Pseudo-code):
- Dasturlash tillaridan farq qiladigan, sho'x va tabiiy til ko'rinishidagi algoritm tasviri
- Algoritmdagi asosiy mantiqiy operatsiyalarni yozish uchun qo'llaniladi
- Algoritm bosqichlarini aniq va tushunarli bayon qilishga imkon beradi
2. Blok-sxemalar (Flowcharts):
- Algoritmdagi qadamlarni grafiklar, simllar, yassi va uchburchak shakllari orqali tasvirlash
- Algoritm mantiqini ko'rgazmali ravishda ifodalaydi
- Algoritmdagi tarmoqlanish va takrorlanish jarayonlarini aniq ko'rsatadi
3. Formal xususiyatlar (Formal Notations):
- Algoritmlar uchun maxsus shakllangan matematik belgilar, sintaksislar va qoidalar
- Algoritmni aniq va qat'iy matematik tilida ifodalashga imkon beradi
- Masalan, avtomat nazariyasi, rekursiv funksiyalar, Lambda hisoblash va boshqalar
4. Tayyor dasturlash tillari (Programming Languages):
- Algoritmni to'g'ridan-to'g'ri dasturlash tili yordamida yozish
- Dasturlash tili sintaksisi va qoidalaridan foydalanish
- Algoritmni shu tilda bajariladigan kodga aylantirib olish imkonini beradi
Yuqoridagi usullardan qaysi biri qo'llanilishi algoritmning murakkabligiga, undan foydalanuvchilarning malakasiga va qo'yilgan maqsadlarga bog'liq.
17. Algoritmlerdiń grafik formasında suwretleniwi
Algoritmlarning grafik ko'rinishda tasvirlanishi uchun eng ko'p qo'llaniladigan usul - blok-sxemalar (flowcharts) hisoblanadi. Blok-sxemalar algoritmdagi asosiy qadamlarni, tarmoqlanish va takrorlanish jarayonlarini grafik elementlar yordamida ko'rgazmali tarzda tasvirlaydi.
Blok-sxemada quyidagi asosiy grafik elementlardan foydalaniladi:
1. Proses bloki (Process block): Algoritmdagi ma'lum bir amaliyotni bajaruvchi blok. Odatda to'g'tburchak shaklida tasvirlanadi.
2. Qaror bloki (Decision block): Algoritmdagi tarmoqlanish yoki tanlash jarayonlarini ifodalaydi. Uchburchak shaklida tasvirlanadi.
3. Kirish/Chiqish bloki (Input/Output block): Algoritmdagi ma'lumotlarni olish yoki chiqarish amaliyotlarini ko'rsatadi. Parallelogrammalar yordamida tasvirlanadi.
4. Boshlash/Tugash bloki (Start/End block): Algoritm boshlanish va tugash nuqtalarini belgilaydi. Aylana yoki yassi uchburchak shaklidagi bloklar orqali ifodalanadi.
5. Bog'lovchi bloklar (Connector blocks): Bloklar orasidagi bog'lanishlarni ko'rsatadi. Odatda, strelkalar yordamida tasvirlanadi.
Bunday grafik tasvir algoritm tuzilishini aniq va ko'rgazmali qilib ko'rsatadi. Bu esa algoritm mantiqini tushunish va tahlil qilish imkonini beradi. Murakkab algoritmlarni blok-sxemalar yordamida tasvirlash optimal echimlar topishga yordam beradi.
18. Algoritmdiń sózler arqalı ańlatılıwı
Algoritmlarni so'zlar yordamida (psevdokod) yozish algoritmni tasvirlashning yana bir muhim usullaridan biridir. Psevdokod dasturlash tillaridan farq qiluvchi, sodda va tushunarli tabiiy tilda yozilgan algoritm tasviridir.
Psevdokodda algoritmdagi asosiy qadamlar, tarmoqlanish, takrorlanish va boshqa mantiqiy operatsiyalar yozib chiqiladi. Bunday usul algoritmni to'liq va aniq bayon qilishga imkon beradi.
Psevdokodda quyidagi asosiy elementlardan foydalaniladi:
1. Boshlash va tugash: "Boshla", "Tugatish" kabi kalit so'zlar orqali algoritm boshlanishi va tugashi belgilanadi.
2. Qadamlar: Algoritmning bir-ketin bajarilishi kerak bo'lgan amallar ketma-ketligi yoziladi.
3. Shartli operatsiyalar: "Agar..., u holda...", "Aks holda" kabi shartlar yoziladi.
4. Takrorlanish: "Qayta", "N marta", "Har safar" kabi takroriy operatsiyalar ifodalanadi.
5. Kiritish/Chiqarish: "Kiriting", "Chiqaring" kabi ma'lumotlarni olish va qaytarish operatsiyalari belgilanadi.
6. O'zgaruvchilar: Hisoblashlarda foydalaniladigan o'zgaruvchilar ta'riflangan holda qo'llaniladi.
Psevdokod algoritm mantiqini sodda va aniq bayon etishga imkon beradi. U dasturlash tilining qat'iy sintaktik qoidalaridan qutulgan holda algoritmni ifodalaydi. Bu esa algoritmni tushunish va tahlil qilishni yanada osonlashtiradi.
19. Kóp aǵzalılar mánislerin esaplawda Gorner sxeması.
Ko'p hadli ifodalarni hisoblashda Horner sxemasi juda qulay va samarali usullardan biridir. Horner sxemasi orqali ko'p hadli ifodani yig'indiga aylantirib, uni tezkor va samarali tarzda hisoblash mumkin.
Horner sxemasini qo'llashning asosiy bosqichlari quyidagicha:
1. Ko'p hadli ifodani x o'zgaruvchisi bo'yicha yoziladi:
a(x) = a0 + a1*x + a2*x^2 + ... + an*x^n
2. Eng yuqori darajali hadning koeffitsientidan boshlab, quyidagi rekursiv formula asosida qator bo'yicha hisoblash amalga oshiriladi:
y = a0
y = a1 + x*y
y = a2 + x*y
...
y = an + x*y
3. So'nggi qiymat y bo'ladi va bu a(x) ko'p hadli ifodaning qiymatidir.
Masalan, a(x) = 2 + 3*x - 4*x^2 + x^3 ko'p hadli ifodani hisoblash uchun Horner sxemasi quyidagicha:
y = 2
y = 3 + x*y // y = 3 + x*2
y = -4 + x*y // y = -4 + x*(3 + x*2)
y = 1 + x*y // y = 1 + x*(-4 + x*(3 + x*2))
Natijada, a(x) = y bo'ladi.
Horner sxemasi orqali ko'p hadli ifodalarni hisoblash tezkor, samarali va xatosiz amalga oshiriladi. Bu usul ayniqsa, yuqori darajali ko'p hadli ifodalarni hisoblab chiqishda qo'l keladi.
20. Sızıqlı algoritmler. Cikller.
Esaplaw processlerin shártli túrde sızıqlı hám tarmaqlanatuǵın túrlerge bolıw múmkin. Sızıqlı programmalastırıw procesi - bul esaplaw processleri bolıp, ol jaǵdayda esap-kitaplar esaptan tısqarı bolmaǵan qatań belgilengen izbe-izlik boyınsha ámelge asıriladı. Bunday processlerge aldınnan belgilengen tákirarlanıwshı sanı menen dáwirli processler kiredi. Bul túrdegi processler ushın mısal:
Mısal 1. Jıyındınıń mánisin esaplań
Máseleni beriliwinen kórinip turıptı, bul summanı esaplaw procesi hesh qanday quramalılıqqa iye emes, bálki birdey túrdegi esaplawlardı kóp ret tákirarlaw menen baylanıslı. Házirgi kúnde programmalastırıw kónlikpelerin jaqsı bilmegen adamǵa da bul esap-kitaplardı orınlaw qıyın. Endi hár bir az yáki kóp bilimli adam intuitiv túrde bunday máselelerge tezlik penen juwap beretuǵın qurallar bar ekenligin tusinip jetedi. Lift penen baylanıslı joqarıdaǵı mashqalada bolǵanı sıyaqlı: nege lift bolǵanında tekshedan onınshı qabatqa ter tógip shıǵıw kerek? Bul talaplar hár qanday orında, az yáki kóp quramalı máselelerge dus kelip rawajlanıwı kerek bolǵan psixologiyaning túri bolıp tabıladı. Ol mashqalanıń programmalıq sheshimlerin izlewi hám bunday programmalardı dúziwge ılayıq bolıwı kerek. Cikllik esaplawdı programmalastırıw procesin súwretlew ushın joqarıdaǵı jıyındını esaplawdıń blok-sxemasın suwretleymiz.
S=0 ; k=1
S=S+1/( +1)
k=k+1
|
