1 mavzu: kirish. Algoritmlash fani va algoritmlash san’ati

Bu begilar “katta O” va “kichik o” deb nomlanadi. Agar f(n)=O[g(n)] bo’lsa, ikkala funksiya ham bo’lganda bir xil tezlikda o’sadi.

Agar f(n)=O[g(n)] bo’lsa,unda g(n), f(n) nisbatan ancha tez o’sadi.

Demak, - qandaydir n o’zgaruvchidan bog’liq va k darajadagi polinom uchun yoki bo’lganda algoritm polynomial hisoblanadi, aks holda algoritm eksponensial.

Eksponensial algoritm yahshi ishlamaydigan deb hisoblanadi. Agar algoritmlar eksponensial bo’lsa, ular orasida eng samaralisini topish kerak, n kattalikdagi masalani qadamda yechadigan algoritm yoki qadamda masalani yechadigan algoritmdan afzalroq.

Dasturni tekshirish

Biz dasturni har bir qismini tekshiradigan kirituvchi ma’lumotlar to’plamini tanlashimiz kerak. Ko’p murakkab algoritmlarni matematik tomondan tadqiq qilish yoki juda qiyin yoki mumkin emas. Bunday holatlarda algoritmni faoliyat jarayonida va qiyinligi bo’yicha tekshiradi. Bundan tashqari dasturlarni hisoblash imkoniyatlarini aniqlash uchun ham testlash maqsadga muvofiq. Ko’p dasturlar qandaydir kiritiladigan ma’lumotlar bilan yahshi ishlasa, boshqalari bilan yomon ishlaydi. “Yahshi” lardan “yomon” larga o’tish “mayin” bo’lish kerak. Testlash uchun ma’lumotlar dasturning qiyinligiga, mavjud vaqt resurslariga, kiritish-chiqarishsoniga bog’liq holda tanlanadi. Bu yerda analitik va eksperimental tahlil bir-birini to’ldiradi.

Hujjatlashtirish

O’zingiz yozmagan dastur kodini o’qish juda qiyin. Bu muammoni hujjatlashtirish yordamida yechsa bo’ladi. Hujjatlashtirish o’z ichiga hamma yordamchi ma’lumotlarni oladi va dasturda nima bajarilishini tushuntirib beradi, xususan, blok-sxemalardagi boshqarishni uzatish, berilganlarni kiritish-chiqarish shaklini batafsil tavsif qilish, siklning parametrlari, yordamchi local va global proseduralarni bajarilishi va boshqalar.

Hujjatlashtirishning eng asosiy qoidasi bu “boshqalar yozgan dasturlarni qanday ko’rishni istasangiz, o’zingiz ham dasturni shunday ko’rinishda rasmiylashtiring”.

Takrorlash ucun savollar

1. Algoritmning qaysi ta’riflarinin bilasiz?

2. Algoritmni to’liq yaratish bosqichlarini aytib o’ting

3. Masalani qo’yishda va modelni yaratishdagi savollarni qanday aniqlash kerak?

5. Algoritmni va ularning murakkabligini tahlil qilishda nimalarga e’tibor berish kerak?

ALGORITMLARNI TAVSIFLASH TILI HAQIDA KELISHUV

Reja

1. Algoritmning umumiy ko’rinish

2. Tarmoqlanuvchi yoki shartli buyruqlar

3. Tanlash buyruqlari.

4. Takrorlash buyruqlari.

Algoritmlarni tavsiflash usullari haqida aytadigan bo’lsak, ular so’zlar bilan, jadvallar bilan, grafik yoki blok-sxemalar va maxsus sun’iy tilda berilishi mumkin.

So’zli tavsiflashda tabiiy til va matematik belgilar elementlari ishlatiladi. Jadvalli berilishida algoritm jadvallar va hisoblash formulalari shaklida ko’rsatiladi. Grafikli, blok-sxemali va graflar yordamida berilishda algoritm geometrik figuralar va bloklar yordamida tavsiflanadi.

Algoritmik til – bu algoritmlar va ular bajarilishini bir qolirda va aniq yozish uchun belgilar va qoidalar tizimi. Algoritmik til so’zlarni tuzishga xizmat qiladigan o’z lug’atiga ega bo’ladi. So’zlar algoritmni buyruqlarini yozish uchun ishlatiladi. Bundan tashqari tilning xizmat so’zlari ham bo’ladi, ularning berilishi va ma’nosi aniq belgilangan.

So’zli algoritmik tillarga misol bo’lib “Informatika” kursidagi maktab algoritm tili xizmat qilishi mumkin. Bu til yordamida ixtiyoriy algoritmni o’qishva tahlilga qulay ko’rinishda, hamda unga qandaydir qo’shimcha buyruqlar va konstruksiyalar kiritish imkoni bilan yozish mumkin.

Algoritmning umumiy ko’rinishi va shu tilning asosiy buyruqlari.

1. Algoritmning umumiy ko’rinishi:

Alg nomi (argumentlar va natijalar ruyhati).

Arg ruyhat.

Nat ruyhat.

Bosh

Buyruqlar ruyhati.

Tamom.

2. Tarmoqlanuvchi yoki shartli buyruqlar.

Agar shart.

Unda ruyhat 1.

Aks holda ruyhat 2.

Tamom.

3. Tanlash buyruqlari.

Tanlash

Shart 1: ruyhat 1.

Shart 2: ruyhat 2.

…………………

Shart N: ruyhat N.

Tamom.

4. Takrorlash buyruqlari.

1. toki shart.

Sikl bosh. ruyhat.

Sikl tug.

2. Takror ruyhat to shart .

3. i=n dan m gacha

sikl bosh ruyhat

sikl tug.

Bu tilda yozilgan algoritmlarni yuqori darajali dasturlash tiliga bevosita o’tkazish oson. Algoritmni tuzishda va tahlil qilishda bu yerda faqatgina qabul qilingan algoritmik tildagi konstruksiyaga mos buyruqlarni bajarish uchun kerak bo’ladigan vaqt va xotira muhim.

Takrorlash ucun savollar

1. Algoritmni tavsiflash uchun qaysi tillardan foydalansa bo’ladi?

2. Asosiy konstruksiyalarni blok-sxema yordamida ifodalang.

3. Asosiy konstruksiyalarni Paskal dasturlash tilida ifodalang.

4. Asosiy konstruksiyalarni C++ tilida ifodalang.