Algoritmni loyihalash va tahlil qilishga kirish

Algoritmik loyihalar uchun vaqtni optimallashtirish usullari

Reja:
1 Algoritmlarni ishlab chiqish va tahlil qilish usullari
2 Algoritmlashtirishning tarkibiy printsiplari
3 Algoritmni sinovdan o'tkazish
Algoritmlarni yuqoridan pastga loyihalash, "yuqoridan pastga" algoritmlarni loyihalashtirish yoki algoritmlarni ketma-ket (bosqichma-bosqich) yuqoridan pastga qarab ishlab chiqish - bu asl masala (algoritm) bir qator yordamchi kichik topshiriqlarga (subalgoritmlarga) bo'linib, sodda va oddiy amallar nuqtai nazaridan tuzilgan va echilgan holda algoritmlarni tuzish usuli. Ikkinchisi, o'z navbatida, yana sodda va oddiy elementlarga bo'linadi va shu bilan biz ijrochining buyruqlariga erishgunimizcha. Ushbu buyruqlar bo'yicha, bo'limlarning oxirgi bosqichida olingan subalgoritmlarni (ijrochining buyruqlar tizimining buyruqlari) ifodalash va bajarish mumkin.
Pastdan yuqoriga ko'tarish usuli, aksincha, ma'lum bir oldindan aniqlangan subalgoritmlarning to'g'ri to'plamiga asoslanib, funktsional jihatdan to'liq umumiy maqsadga muvofiq pastki muammolarni tuzadi, ulardan umumiyroq narsalarga o'tadi va hokazo, biz to'plamning echimi darajasiga yetgunimizcha. vazifalar. Ushbu uslub pastdan yuqoriga qarab loyihalash usuli sifatida tanilgan.
Algoritmiklashtirishning strukturaviy printsiplari (algoritmlashtirishning tizimli usullari) - bu algoritmlarni algoritmni yuqoridan pastgacha va ketma-ket o'qilishi va bajarilishini kafolatlaydigan ma'lum qoidalarga rioya qilgan holda ularning ketma-ket ulanishidan yoki uyalashidan foydalangan holda (asosiy, tizimli, takrorlanadigan) algoritmlarni shakllantirish tamoyillari.
Tuzilgan algoritm - bu asosiy algoritmik tuzilmalarning ketma-ketligi va joylashishi sifatida ifodalangan algoritm. Tarkibiy algoritmda statik holat (algoritmni yangilashdan oldin) va dinamik holat (yangilanishdan keyin) bir xil mantiqiy tuzilishga ega bo'lib, yuqoridan pastga qarab kuzatiladi ("o'qilgan va bajarilgan" kabi). Strukturaviy algoritmni ishlab chiqishda algoritmning to'g'riligini uning tuzilishi va bajarilishining har bir bosqichida kuzatish mumkin.
Teorema (tuzilish haqida). Har qanday algoritmni asosiy algoritmik tuzilmalardan tashkil topgan tuzilgan algoritm bilan teng ravishda ifodalash mumkin.
Algoritmlarni (dasturlarni) loyihalashtirish va rivojlantirishda keng qo'llaniladigan usullardan biri bu modul usuli (modulli texnologiya).
Modul - bu ma'lum algoritm yoki uning ba'zi bir bloklari bo'lib, ular yordamida uni ajratish va yangilash mumkin. Modul ba'zan yordamchi algoritm deb ham nomlanadi, garchi barcha algoritmlar yordamchi xarakterga ega. Ushbu nom algoritmning dinamik holatini ko'rib chiqishda mantiqan to'g'ri keladi; bu holda ma'lumotlar tomonidan ushbu dinamik algoritm tanasining bloki (tarkibiy qismi) sifatida ishlatiladigan har qanday algoritmni yordamchi deb atash mumkin. Modulning yana bir nomi ham ishlatiladi - subalgoritm. Dasturlashda sinonimlar - protseduradan foydalaniladi.
Modul xususiyatlari:
- funktsional yaxlitlik va to'liqlik (har bir modul bitta funktsiyani amalga oshiradi, lekin uni yaxshi va to'liq amalga oshiradi);
- boshqa modullardan avtonomlik va mustaqillik (voris moduli ishining oldingi modul ishidan mustaqilligi; bu holda ularning aloqasi faqat parametrlarni uzatish / qabul qilish darajasida amalga oshiriladi);
- rivojlanayotgan;
- foydalanuvchilar va ishlab chiquvchilar uchun ochiqlik (modernizatsiya va foydalanish uchun);
- to'g'riligi va ishonchliligi;
- modul tanasiga havola faqat modul nomi bilan sodir bo'ladi, ya'ni modulni chaqirish va yangilash faqat uning sarlavhasi orqali amalga oshiriladi.
Modulli algoritm dizayni xususiyatlari (afzalliklari):
- turli xil ijrochilar tomonidan keng ko'lamli algoritm (algoritmik kompleks) ishlab chiqish imkoniyati;
- eng ko'p ishlatiladigan algoritmlar (subalgoritmlar) kutubxonasini yaratish va saqlash qobiliyati;
- algoritmlarni sinashni osonlashtirish va ularning to'g'riligini asoslash;
- algoritmlarni loyihalash va modifikatsiyalashni soddalashtirish;
- algoritmlarni (yoki algoritmlar komplekslarini) ishlab chiqish (loyihalash) ning murakkabligini kamaytirish;
- algoritmlarni amalga oshirishda hisoblash jarayonining kuzatilishi.
Algoritmni sinash - bu algoritm ishlashining to'g'riligini yoki noto'g'riligini maxsus ko'rsatilgan testlarda yoki test misollarida tekshirish - ma'lum kirish ma'lumotlari va natijalari bilan bog'liq muammolar (ba'zan ularning taxminiy ko'rsatkichlari etarli). Sinov ishi minimal va to'liq bo'lishi kerak, ya'ni har bir turdagi test ishlarini, ayniqsa, alohida holatlarda sinovdan o'tkazishi kerak.
Misol. ax2 + bx + c = 0 kvadrat tenglamasini echish muammosi uchun bunday istisno holatlar, masalan:
1) a = b = c = 0;
2) a = 0, b, c - nolga teng bo'lmagan;
3) D = b2 - 4ac <0 va boshqalar.
Algoritmlarni sinash algoritmning barcha mumkin bo'lgan ma'lumotlar to'plamlari, ayniqsa etarli darajada murakkab algoritmlar uchun to'g'riligiga to'liq (100%) kafolat bera olmaydi.
Algoritmning to'g'riligining to'liq kafolati aksiomalar va xulosalar qoidalari tizimidan foydalangan holda algoritmning ishlashi va natijalarini tavsiflash yoki algoritmni tekshirish orqali berilishi mumkin.
Misol. Uzunligi n bit bo'lgan barcha har xil ikkilik xabarlarning (ikkilik ketma-ketliklar) sonini, ko'pi bilan bitta ko'paytirish amalidan foydalanib, topish algoritmini tuzamiz va ushbu algoritmning to'g'riligini isbotlaymiz.
Birinchidan, bunday barcha xabarlarning sonini toping. 1 uzunlikdagi ikkilik xabarlarning soni 2 = 21 (ular "0" va "1"), 2 uzunligi 4 = 22 ("00", "01", "10", "11"). Ushbu aniq faktlardan boshlab, biz matematik induktsiya usuli bilan n uzunlikdagi turli xil xabarlar soni 2n ga teng ekanligini isbotlaymiz. Ushbu induktiv xulosa algoritmning to'g'riligini isbotlaydi.
Bu so'zimiz n = k uchun to'g'ri bo'lsin. Keyin n = k + 1 uchun har bir bitni (0 yoki 1) k uzunlikdagi har qanday 2k xabarga qo'shish xabarlar sonining 2 barobar ko'payishiga olib keladi, ya'ni ularning soni 2 × 2k = 2k + 1 ga teng bo'ladi, shunda bizning induktiv gipotezamizni isbotlaydi.
Endi x = 2n sonini faqat bir marta ko'paytirish amalidan foydalanib hisoblash algoritmini tuzamiz.
So'nggi tenglikning logarifmini olaylik. Ln (x) = ln (2n) = n ln (2) ni olamiz.
exp (ln (x)) = x tenglikdan foydalanib, biz exp (ln (x)) = x = exp (n ln (2)) ga erishamiz.
Hozirgina x sonini hisoblashning eng oddiy algoritmini yozish qoladi.
Rem Xabarlar sonini hisoblang clsInput “Xabar uzunligini bit bilan kiriting”; nx = exp (n * log (2)) print "Xabarlar soni teng"; int (x) oxiri
Oddiy algoritmlar uchun testlarni malakali tanlash va to'liq sinovlar ishlashning to'liq tasvirini (ishlamasligi) berishi mumkin.
Tracing - bu ba'zi bir testlarda algoritmning dinamik holatini bosqichma-bosqich aniqlash usuli. U ko'pincha iz jadvallari yordamida amalga oshiriladi, unda har bir satr algoritmning ma'lum bir holatiga, ustun esa algoritm parametrlarining (kirish, chiqish va oraliq) ma'lum bir holatiga mos keladi. Tracing algoritmni tuzatishni va tushunishni osonlashtiradi.
Algoritmdagi xatolarni (aniq yoki yashirin) topish va tuzatish jarayoni algoritmni disk raskadrovka deb ataladi.
Murakkab dasturiy ta'minot tizimlaridagi ba'zi (yashirin, aniqlash qiyin) xatolar faqat ularning ishlashi paytida, xatolarni qidirish va tuzatishning so'nggi bosqichida - texnik xizmat ko'rsatish bosqichida paydo bo'lishi mumkin. Ushbu bosqichda ular hujjatlarni aniqlashtirish va takomillashtirish, xodimlarni algoritm (dastur) dan foydalanishga o'rgatishadi. Misol:
N = 2 testda shaklning algoritm fragmentining funktsiyasini aniqlaylik
dim x (n) x (1) = 4: x (2) = 9 k = 1s = x (1) uchun i: = 1 dan n gacha bo'lsa, agar s Agar jadval shaklida yozilsa,

i	S	x(i)	k	s	i<=n
				Нет	Да
				Да	Да
	—	—	—	—	Нет

u holda algoritmning vazifasi aniqroq bo'ladi - bu funktsiya qatorning maksimal elementi indeksini topishdan iborat. Ushbu bo'limning yakunida biz algoritmik qo'llab-quvvatlashning umumiy tuzilishini taqdim etamiz. Algoritmlarni tasniflashning mezonlari turlicha, shuning uchun quyida taklif qilingan sxema strukturaning asosiy elementlarini aks ettiradi va ba'zi hollarda shartli, ya'ni 29-rasmda ko'rsatilgan strukturaning bloklari "bir-biriga" tushishi mumkin. Algoritmlardan foydalanishning asosiy shakllari yakka, kutubxona, paketli.
Avtonom algoritm echilayotgan masala, foydalanilgan ma'lumotlar tuzilishi, algoritm qismlari (modullari) mantiqiy bog'lanishlari tuzilishi va algoritm berilgan va tavsiflangan psevdokod tili bilan belgilanadi.

29-rasm - Algoritmik qo'llab-quvvatlashning tuzilishi

Algoritmlar kutubxonasi kutubxonadan foydalangan holda echilgan vazifalar to'plami, ma'lum mavzudagi tipik masalalarni hal qilish algoritmlari to'plami va foydalanilgan ma'lumotlar tuzilishi bilan belgilanadi.

Algoritmlar to'plami, xuddi kutubxona kabi, to'plam yordamida hal qilingan vazifalar to'plami, ma'lum mavzular doirasidan tipik vazifalarni yoki ularning tarkibiy qismlarini echish algoritmlari to'plami, foydalanilgan ma'lumotlar tarkibi va vazifalar (modullar) o'rtasida ma'lumotlar almashinuvi, vazifa tuzilgan maxsus til bilan belgilanadi. (hal qilinayotgan muammoning bosqichlari ketma-ketligi, topshiriq vazifalarining ketma-ketligi).