Amaliy matematika” fakulteti “Amaliy matematika va informatika” kafedrasi “Algoritm nazariyasi” fanidan

I-BOB. Algoritm to’g’risida umumiy tushunchasi.

I.1 Algoritmning ta’rifi

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 bajarilayotgan amallarni mazmunini anglash shart emas. Algoritm tuzish jarayoniga algoritmlashtirish deyiladi.Algoritm tuzish jarayonida nazariy va amaliy nuqtai nazardan algoritmlash, dasturlash va Elektron Hisoblash Mashinalarni 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 muammolarini o’rganish. Bu jarayonlar algoritmni to’liq yaratish tushunchasiga olib keladi va quyidagi bosqichlarni belgilaydi:

1. Masalaning qo’yilishi. Masalani yechishdan oldin, uni berilishini aniq shakllantirib olish zarur.

2. Modelni yaratish.

Akademik A. N. Tixonov fikri bo’yicha matematik modellashtirish dunyoni bilish va o’rganishda kuchli qurollardan (vositalardan) biridir. Uning ta’rifi bo’yicha matematik model tashqi dunyoning xodisalar turkumini matematik belgilar yordamida taxminiy tavsifi.Xodisani tavsiflash uchun uning muhim xususiyatlarini, qonuniyliklarini, ichki aloqalarini, ayrim xossalarning ahamiyatini aniqlash zarur.Eng muhim faktorlari aniqlanganda, ahamiyatlari kamroq bo’lganlarini hisobdan chiqarish mumkin.Umuman, modelni tanlash fandan ko’ra, ko’proq san’at ishi deb hisoblanadi, yahshi tuzilgan modellarni o’rganish esa – modellashtirishda tajriba orttirishning eng yahshi usuli.

3. Algoritmni ishlab chiqish.

Algoritmlarni yaratish ijobiy ish, shuning uchun ixtiyoriy zarur algoritmlarni tuzish imkonini beradigan bir umumiy usul mavjud emas. Lekin algoritmlarni ishlab chiqishni asoslangan oddiy sxemalarini beradigan ko’pgina algoritmlashtirish nazariyalari bor. Bunday sxemalar va yangi algoritmlarni paydo qilishning o’rtasida qattai bog’liqlik kuzatiladi.

4. Algoritm to’g’riligini tekshirish.

5. Algoritmni amalga oshirish.

6. Algoritmni va ularning murakkabligini tahlil qilish.

7. Dasturni tekshirish.

Knuth strategiyasi.

Donald Knuth algoritmga talab sifatida qabul qilinadigan besh xususiyatning ro'yxatini tuzdi:

Aniqlik: "Algoritm har doim cheklangan sonli qadamlardan keyin tugashi kerak."

Aniqlik: "Algoritmning har bir bosqichi aniq belgilangan bo'lishi kerak; bajariladigan harakatlar har bir holat uchun qat'iy va aniq ko'rsatilishi kerak."

Kiritish: "... algoritm boshlanishidan oldin unga berilgan miqdorlar. Ushbu kirishlar belgilangan ob'ektlar to'plamidan olinadi."

Chiqish: "... kiritilgan ma'lumotlarga bog'liq bo'lgan miqdorlar."

Samaradorlik: "... algoritmda bajariladigan barcha operatsiyalar etarlicha sodda bo'lishi kerak, ular asosan qog'oz va qalamdan foydalangan holda aniq va cheklangan vaqt davomida bajarilishi mumkin."

Ikkita natural sonning eng katta umumiy bo'luvchisini aniqlash uchun Evklid algoritmi bunday algoritmga misol bo'lishi mumkin.

II.BOB TABIIY FANLAR SOHALARIGA XOS AN’ANAVIY MASALALARNING ALGORITMI.