Algoritmlar tizimli tahlili va ularning takomillashtirish usullari

Keywords: programming, looping, introduction to programming, initial task analysis, extreme programming.
Kirish. Ko'pincha dasturlashni boshlayotgan talabalar topshiriqni bajargandan so'ng, darhol to'g'ri echim topishga harakat qilib, kodni kiritishni boshlashlarini kuzatamiz. Ular amalga oshirish uchun muhim bo'lgan algoritmni tahlil qilish bosqichini o'tkazib yuborishadi. Talabalar, algoritm yetarlicha o'qilishi yoki samaraliroq bo'lishidan qat'i nazar, faqat ishlaydigan dasturni tuzishni maqsad qiladi. Bu kuzatishlar dasturlash musobaqalarida qatnashayotgan ilg‘or talabalar uchun ham to‘g‘ri keladi - hatto ular kamdan-kam hollarda birinchi navbatda tegishli algoritmni yaratish orqali o‘z ishlarini engillashtirishga intilishadi. Dasturchilarni amalga oshirishga bo'lgan yondashuvni va ishlab chiqish jarayonida olib boriladigan fikrlash jarayonini oldindan ko'rib chiqish foydaliligiga ishontirish qiyin. Algoritm dasturning yakuniy shaklining mantiqiy asosi bo'lib xizmat qiladi.
Xuddi shunday hodisani matematika o‘qitishda ham kuzatish mumkin. Ko'p yillar oldin algebraik ifodalarni intensiv va og'ir hisoblash zarurati hisob-kitoblarni minimallashtirish va optimallashtirish uchun ifodalarni soddalashtirishga intilishga olib keldi. Bugungi kunda bu tez-tez qo'llanilmaydi, chunki murakkablik bilan shug'ullanish zamonaviy kompyuterlar va IT texnologiyalari uchun muammo emas. Shunday qilib, bir nuqta bo'lishi mumkin: bizda etarlicha kuchli kompyuterlar mavjud bo'lganda, nima uchun algoritm haqida qayg'urishimiz kerakmi? Yangi texnologiyalar ko'plab afzalliklari bilan bir qatorda sezilarli kamchilikka ega: foydalanuvchilarning xatti-harakatlari ko'proq iste'molga asoslangan bo'lib, odamlarni dangasa qiladi va ijodiy fikrlash va intilishlarni rag'batlantirmaydi. Umumiy IT faoliyati ko'proq ijtimoiy tarmoqlarga qaratilgan bo'lib, bizni o'rab turgan hodisa va jarayonlar, jumladan, o'rganilishi kerak bo'lgan o'quv materiallari iste'molchi darajasida qabul qilinadi, bu esa o'quvchilarni faollik va fikrlashga majburlamaydi. Ammo bu ta'lim, xususan, dasturlash bo'yicha o'qitishga intiladi.
“Dasturlashtirishga kirish” kursida foydalaniladigan topshiriqlar va misollar toʻplami kirish qismi boʻlishi sharti bilan yetarlicha sodda. Shu ma'noda ular o'quvchilarni muammoga samarali yechim topishga majburlay olmaydilar. Shuning uchun muhim uslubiy masala - bu talabalarni kodlashga o'tishdan oldin turli xil algoritm alternativlarini ko'rib chiqish va baholash masalalariga yondashishga undaydigan topshiriqlar va misollarni sinchkovlik bilan tanlashdir.
Maqola quyidagicha tashkil etilgan: 1-kirish bo'limda algoritmik madaniyat muhokama qilinadi. 2-bo'lim Tajribada misol orqali ko'rib chiqilgan algoritmning tahlili muhokama qiladi. 3-bo'limda xulosalar keltirilgan
Algoritmik madaniyat: Muammoni hal qilish dasturlash bo'yicha o'qitishning majburiy elementidir. Yechimlarni izlash jarayonida talabalar nazariy bilimlarni amaliyotda qo‘llash ko‘nikma va odatlarini o‘zlashtiradilar. Bundan tashqari, muammolarni hal qilish qobiliyati nazariy bilimlarning yaxshi tushunilganligidan dalolat beradi. Amaliy nuqtai nazardan, vazifa aniq yoki yashirin savol bo'lib, uning javobi aniq emas va uni bosqichma-bosqich topish kerak.
O'quv jarayoni kontekstida vazifani hal qilish aslida maqsad emas; bu dasturlash ko'nikmalarining bir qismi sifatida harakat rejimlarini shakllantirishning kengroq maqsadiga erishishning bir vositasidir. Ushbu modellar o'qituvchining yo'l-yo'riqlari va taxminlarini taqdim etish orqali tuzilishi mumkin, ular nazoratsiz sinov-xato harakatlaridan so'ng baholash yoki o'z-o'zini baholash natijasi bo'lishi mumkin.[6] Harakat modellari o'quv jarayonining haqiqiy qiymati bo'lib, yechimni o'zi topmaydi. Aslida, yechim faqat harakat modeli to'g'ri ishlab chiqilganligining ko'rsatkichidir.
Vazifaning dastlabki tahlili bilan birgalikda mustahkam matematik ko'nikmalarning asosi dasturlash tilining integratsiyalashgan rivojlanish muhitida (IDE) to'g'ridan-to'g'ri kodlash orqali vazifani bajarishga urinishdan farqli o'laroq, to'g'ri harakatni modellashtirish jarayonini modellashtirish jarayonining asosiy muvaffaqiyat omili va zaruriy shartidir. ... Dastur ustida ishlayotgan dasturchi, ayniqsa yangi boshlanuvchilar, ular yaratgan dastur nafaqat foydalanuvchi uchun, balki dasturchining o'ziga ham yordam berishini hurmat qilishi kerak
Dasturchilar, shuningdek, dasturiy ta'minotni ishlab chiqish metodologiyalari, o'zgarishlarni boshqarish va dasturiy ta'minotning hayot aylanishining texnik bosqichida boshqa dasturchilar jamoalari kelajakda o'z kodlarini ko'rib chiqishlari va o'zgartirishlari mumkinligini taxmin qilishlari kerak. Bu, ayniqsa, turli dasturiy ta'minot loyihalarida integratsiya va moslashishda ishtirok etadigan qayta foydalanish mumkin bo'lgan dasturiy ta'minot birliklari va kutubxonalarni qurishning zamonaviy tendentsiyalari uchun ayniqsa muhim va dolzarbdir. Shunday qilib, zamonaviy dasturiy ta'minotning majburiy xususiyati o'qilishi, yaxlitligi, aniq belgilangan interfeyslar, kirish va chiqishlar, yo'q qilingan nojo'ya ta'sirlar, ob'ektga yo'naltirilgan dasturlash paradigmalari kontekstida qat'iy inkapsulyatsiya va hisoblash resurslaridan samarali foydalanishdir. Bu xususiyatlarning barchasi ko'p o'ylash, ko'p rejalashtirish, puxta qaror qabul qilish, dasturiy ta'minot kompaniyalari, ekspert guruhlari va umuman jamiyatda to'plangan eng yaxshi tajribalarni qabul qilishni talab qiladi. Xulosa qilib aytganda, dasturlash bo'yicha kirish kursi talabalarni bu ko'nikmalarning g'ishtlari va loylari aynan shu erda va hozir mustahkam poydevorda birlashtirilganligiga ishontirishi kerak.
O'qilishi nuqtai nazaridan, dasturlash birinchi qarashda ko'ringanidan ko'ra, tabiiy til matni tarkibiga yaqinroq jarayondir. Albatta, bu mavhum adabiy matnlar haqida emas, bu ko'proq ma'lumotli matnlar. Ular ustida ishlayotganda, o'quvchilar e'tiborini jalb qilish uchun shou sifati kerak edi. Tabiiy tillar fikrlarni ifodalash uchun o'zgaruvchan aniqlik bilan ishlatilishi mumkin - juda muvaffaqiyatli yoki juda ko'p emas - lekin algoritm yaratish yoki dastur tuzishda fikrni aniq ifodalash juda zarur.
Bu dasturning o'quvchilari kimligini ko'rib chiqish uchun sababdir. Eng aniq o'quvchi, birinchi navbatda, bu mashinaning o'zi. Mashina nuqtai nazaridan samaradorlik dastur matnining eng muhim sifat mezonidir. Dasturlash kurslarida ushbu sifat talabini hisobga olsak, dasturlash mavzusiga qanchalik chuqurroq kirsak, bu muammo shunchalik katta bo'lishini ko'rsatadi. E. Dijkstra [2] kompyuter dasturlari sifatini quyidagicha izohlaydi: “Bir tomondan...dasturlar jozibali va chuqur mantiqiy go‘zallikka ega bo‘lishi mumkin bo‘lsa, boshqa tomondan... ko‘pchilik dasturlar o‘ziga xos tarzda taqdim etilganligini tan olishga majbur. mexanik ijro, lekin go'zallikka ega bo'lsa ham, inson qadriga mutlaqo yaroqsiz.”
Dasturni ko'p o'quvchilari bor, ularning ba'zilari kelajakda uni o'zgarishlarni boshqarishning bir qismi sifatida ko'rib chiqadilar (shu jumladan muallifning o'zi), lekin ba'zi hollarda, ikkinchi o'quvchi dasturni yaratish vaqtida ko'rib chiqishi kerak bo'lishi mumkin. Qiziqarli misol zamonaviy agile dasturiy ta'minotni ishlab chiqish metodologiyalari [3] bilan bog'liq, xususan, "juft dasturlash" orqali yaxshi samaradorlikka erishiladigan Ekstremal Dasturlash (ED). ED bir kompyuterda ikkita dasturchi ishlashini talab qiladi, u erda biri kod tuzadi, ikkinchisi birinchisini kuzatadi va boshqaradi; ular vaqti-vaqti bilan o'z rollarini almashtirishlari mumkin. Ushbu yondashuv uchun motivatsiya "bir boshdan ikki bosh yaxshi".
Biz o'qitish uchun ishlatiladigan dasturlar va haqiqiy dasturiy ta'minotni ishlab chiqish muhitida yaratilgan dasturlar o'rtasidagi farqni bilishimiz kerak. O’qituvch o'quv dasturlarini tuzadi; shuning uchun ularni tushunish oson bo'lishi kerak.
1970-yillardan taʼlim metodologiyasi olimlari kompyuter va dasturlashning taʼlim mazmuniga taʼsiriga alohida eʼtibor qaratdilar. Ular algoritmlash tushunchasi dasturlashning negizida yotadi, aniq til yordamida algoritmni ishlab chiqish va tavsiflash jarayoni sifatida belgilandi. Insonning ko'pgina faoliyati ma'lum bir algoritmga amal qiladigan jarayon sifatida rasmiylashtirilishi va tavsiflanishi mumkin. Biroq, algoritmlash qo'llanilmaydigan ko'plab sohalar mavjud, masalan, ijodkorlik va sub'ektiv qarorlar qabul qilish bilan bog'liq faoliyatlar (jumladan, algoritmlarni yaratish jarayoni!). Algoritm nimani anglatishini o'quvchilarning tushunchasi turli fanlarni o'rganish jarayonida bevosita shakllanadi, eng muhimi matematika. Biroq, kompyuterlar va Axborot-kommunikatsiya texnologiyalari (AKT) paydo bo'lishi bilan bu tushuncha o'z-o'zidan o'z ichiga oladi va zamonaviy madaniyat va axborot asrining ta'siri ostida bo'ladi. 1980-yillarning oʻrtalaridan boshlab dasturlash kurslarining asosiy vazifasi oʻquvchilarning algoritmik madaniyatini shakllantirishdan iborat boʻldi.[5] Darhaqiqat, matematik algoritmni aniqlash, birlashtirish, tekshirish va to'g'ri bajarish qobiliyati har doim talabaning matematik madaniyatining asosiy tarkibiy qismi bo'lib kelgan, garchi "algoritm" atamasi tilga olinmagan bo'lsa ham. Shu nuqtai nazardan, matndan ma'lumot olish va sharhlash qobiliyati bo'lgan funktsional savodxonlikning etishmasligi to'g'ri algoritm va dasturni yaratishni qiyinlashtirishi mumkin.
Xulosa qilib shuni aytish mumkinki, algoritmik madaniyat talabalarda algoritmlashtirishni amalga oshirish uchun zarur bo'lgan ko'nikmalarni shakllantirish uchun zarur bo'lib, bu yaxshi tuzilgan va samarali kompyuter dasturlarini talab qiladi.
Tajriba:
Kirish qismida ta'kidlanganidek, kirish dasturlash kursining o'quv misollarining tabiatiga ko'ra, talabalarni muammoga yaxshi o'ylangan yechim bilan yondashishga ishontirish qiyin. Gal-Ezer va boshqalar. [4] Ushbu kontseptsiyani nisbatan erta joriy etish talabalarni muqobil algoritmlarni ko'rib chiqishga, ularni tahlil qilishga va to'g'ri shakllantirishga undaydi.
Keling, dastur samaradorligini oshirish bo'yicha tavsiyalarni ko'rsatadigan va nihoyat, yaxshi o'ylangan algoritmning foydasini ishonchli tarzda ko'rsatadigan misolni ko'rib chiqaylik.
Misol: Ikkita a va b butun sonlarni kirituvchi va [a, b] oraliqga tegishli barcha butun sonlarning o‘rtacha qiymatini ko‘rsatadigan va oraliqdagi butun sonlar sonini chiqaruvchi dastur tuzing.
Bu erda biz dasturning to'rtta versiyasini ko'rsatamiz, ularning har biri avvalgisini samaradorlik, soddaligi va o'qilishi nuqtai nazaridan yaxshilaydi. Bundan tashqari, dastlabki ikkita versiya halqalarni optimallashtirish bo'yicha muhokama qilish imkonini beradi.
Kuzatishlar shuni ko'rsatadiki, talabalarning deyarli 90% muammoga to'g'ridan-to'g'ri yondashadi, kodni birlashtirishga harakat qiladilar va o'rtacha qiymatga tayanadilar. Ta'rifga ko'ra, raqamlar ro'yxatining o'rtacha qiymati ro'yxat hajmiga bo'lingan raqamlar yig'indisi, boshqacha aytganda o'rtacha arifmetikdir. Ushbu ta'rif keng tarqalgan va o'rtachani topish bilan bog'liq boshqa vazifalarga qo'llanilishi mumkin bo'lgan o'rnatilgan algoritmni o'z ichiga oladi. Bu vazifani bajarish uchun [a, b] oraliqdagi butun sonlar yig‘indisini va shu oraliqdagi butun sonlar sonini topish kerak. To'g'ri yechim butun sonlar yig'indisini iterativ ravishda to'plash va xuddi shunday butun sonlarni hisoblashdir. Amalga oshirish uchun ikkita halqa va parametr kerak bo'lib, ular yig'indi va o'lchamni topish uchun doimiy ravishda interval raqamlaridan o'tadi.
//Version 1 C++
int main()
{
int sum=0,
son=0, i, a, b;
cin>>a>>b;
for (i=a; i<=b; i++)
sum+=i;
for (i=a; i<=b; i++)
son++;
double natija=(double) sum/son;
cout< return 0;
}
Sikllar eng muhim omillardan biri bo'lib, algoritm samaradorligi, murakkabligi va bajarilish vaqtiga ta'sir qiladi. Buning sababi shundaki, tana bayonotlari ko'p marta takrorlanadi va bajariladi va hisob-kitoblarning har qanday qisqarishi, hatto minimal bo'lsa ham, qisqartirish samarasini ko'p marta oshiradi. Ikki yoki undan ortiq siklni birida birlashtirish uchun sikllar sonini kamaytirishning bir usuli.Shunday qilib bajarish vaqti va zarur bo'lgan xotirani qisqartirish.Bu ko'pincha, talabalar kodlashdan oldin topshiriqni sinchkovlik bilan tahlil qilsalar aniq bo'ladi.
Yuqoridagi kodni hisobga olsak, 1-versiyada bir xil parametrlarga va sarlavha satrlariga ega bo'lgan ikkita tsikldan foydalanilganini ko'rish mumkin.Ushbu tsikllarning tanasini bitta tsiklga birlashtirish dastur samaradorligini oshiradi va quyida ko'rsatilgandek kodni qisqartiradi.
// Version 2
int main()
{
int sum=0, son=0, i, a, b;
cin>>a>>b;
for (i=a; i<=b; i++)
{
sum+=i;
son++;
}
double natija=(double) sum/son;
cout<return 0;
}
Yuqoridagi algoritmni keyingi tahlil qilish shuni ko'rsatadiki, [a, b] oraliqdagi raqamlar ketma-ket bo'lib, bu raqamni (b-a+1)/2 formula bo'yicha hisoblash imkonini beradi. Tahlil shuni ko'rsatadiki, sonlar yig'indisi aslida cheklangan arifmetik progressiyaning yig'indisidir. Bunday xulosaga kelish, agar o'quvchilarning matematik bilimlari mavjud va mustahkam bo'lsagina mumkin bo'ladi. Agar bu bilim etishmayotgan bo'lsa, o'qituvchining tahlili o'quvchilarni kuzatish va mantiq orqali ushbu faktni tushunishga undashi mumkin. Darhaqiqat, ro'yxatning o'rtasidagi simmetrik bo'lgan har bir juft sonning yig'indisi bir xil. Demak, [a, b] oraliqdagi sonlar yig‘indisi juft sonlar yig‘indisining juftlik soniga ko‘paytirilganiga teng bo‘ladi. Yondashuv boshqa Gauss summalarini hisoblashda qo'llaniladi. Quyidagi 3-versiyada bu mulohazalar tasvirlangan.
// Version 3
int main()
{
double sum;
int son, a, b;
cin>>a>>b;
sum=(a+b)*(b-a+1)/2;
son=(b-a+1);
double natija=sum/son;
cout<return 0;
}
3-versiyada yaxshilangan samaradorlik algoritmni sinchkovlik bilan tahlil qilish va baholash orqali erishiladi. Sinfda ushbu xulosalarga erishish va algoritmga kiritilgan oddiy formulani olishning muqobil yondashuvi o'rtacha ifodani batafsil qayd etish, so'ngra uni teng shartlarga e'tibor bergan holda soddalashtirishdir. Agar munozara har bir nosimmetrik juftlikning yig'indisi bir xil bo'lsa, har bir juftlikning o'rtacha ko'rsatkichi (2 ga bo'lingan yig'indi) bir xil bo'lishini hisobga olish uchun bir qadam oldinga siljish bo'lsa, xuddi shunday xulosaga kelish mumkin. Bu dasturning keyingi versiyasini o'z ichiga oladi:
// Version 4
int main()
{
int a,b;
cin>>a>>b;
double natija= (double) (a + b)/2;
cout<return 0;
}