Algoritmni loyihalash va tahlil qilishga kirish

Algoritmlarni tahlil qilish va tahlil qilishning asosiy vazifalari.

Reja:

1. 
   Cherch-Turing tezisi va algoritmik ravishda hal qilinmaydigan muammolar.
   
2. 
   Algoritmlar nazariyasining tarixi.
   

Cherch-Turing tezisi va algoritmik ravishda hal qilinmaydigan muammolar.
Alan Turing so'zning intuitiv ma'nosidagi har qanday algoritmni teng keladigan Turing mashinasi bilan ifodalashni taklif qildi (Cherch-Turing tezisi deb nomlanadi). Turing mashinasi (va unga teng keladigan boshqa tushunchalar) kontseptsiyasiga asoslangan hisoblash kontseptsiyasining takomillashtirilishi turli xil massaviy muammolarning algoritmik hal etilmasligini qat'iy isbotlash uchun imkoniyatlarni ochib berdi (ya'ni shartlari ma'lum chegaralarda o'zgarishi mumkin bo'lgan ma'lum bir sinf muammolarini hal qilishning yagona usulini topish muammosi). Algoritmik ravishda echib bo'lmaydigan massa muammosining eng oddiy misoli algoritmni qo'llash masalasi (to'xtash masalasi deb ham ataladi). U quyidagilardan iborat: mashinaning o'z ishini cheklangan sonli bosqichda bajarishini yoki abadiy davom etishini aniqlash uchun o'zboshimchalik bilan Turing mashinasini (uning dasturi tomonidan berilgan) va ushbu mashinaning lentasining o'zboshimchalik bilan boshlang'ich holatini ta'minlashga imkon beradigan umumiy usulni topish talab qilinadi. Algoritmlar nazariyasi tarixining birinchi o'n yilligi davomida hal qilinmaydigan massa muammolari faqat shu nazariyaning o'zida topilgan (bunga yuqorida tavsiflangan qo'llanilish muammosi kiradi), shuningdek matematik mantiq doirasida (klassik predikat hisobida chegirma muammosi). Shuning uchun, algoritmlar nazariyasi matematikaning algebra yoki tahlil kabi klassik sohalari uchun ahamiyatsiz bo'lgan matematikaga ishongan. 1947 yilda A.A.Markov va E.L.Postlar algebrada cheklangan hosil qilingan va cheklangan aniqlangan yarim guruhlar uchun ma'lum bo'lgan tenglik muammosining algoritmik hal etilmasligini o'rnatgandan so'ng o'zgardi (Thue muammosi deb ataladi). Keyinchalik ko'plab boshqa "sof matematik" massaviy muammolarning algoritmik hal etilmasligi aniqlandi. Bu sohadagi eng mashhur natijalardan biri - Yu.V.Matiyasevich tomonidan isbotlangan Xilbertning o'ninchi masalasining algoritmik echimsizligi.
Algoritmlarni loyihalash va tahlil qilishning asosiy bosqichlari.
1. Vazifani tushunish. Algoritmni loyihalashtirishni boshlashdan oldin, topshiriqni to'liq tushunishingiz kerak.
2. Muammoni hal qilishning tarkibiy qismlarini tanlash.
2a. Hisoblash moslamasining imkoniyatlarini aniqlash. Algoritmlarning aksariyati buyruqlar ketma-ket ketma-ket bajariladigan kompyuterda ishlashga mo'ljallangan (ketma-ket algoritmlar). Shunga qaramay, bir vaqtning o'zida bir nechta buyruqlarni bajarishga qodir kompyuterlar mavjud, ular uchun parallel algoritmlar ishlab chiqilgan.
2b. Keyingi asosiy masala aniq yoki taxminiy algoritmni tanlashdir. Ikkinchisining foydasiga tanlov quyidagi sabablarga ko'ra bo'lishi mumkin: aniq echimning mumkin emasligi (masalan, chiziqli bo'lmagan tenglamalarni echish), aniq algoritmlar juda sekin (ayniqsa, katta o'lchamlarda), taxminiy algoritm boshqa algoritmning faqat bir qismi (balki aniq ham bo'lishi mumkin).
2c. Ma'lumotlar tarkibini tanlash. Ba'zi algoritmlar ma'lumotlarning aniq belgilangan tuzilishga ega bo'lishini talab qilmaydi, lekin aksariyat hollarda algoritm faqat ma'lum tuzilmalar bilan ishlashga mo'ljallangan. Ob'ektga yo'naltirilgan dasturlash dunyosida ma'lumotlar tuzilmalari loyihalash jarayonining muhim elementlaridan biri hisoblanadi.
2d. Algoritmlarni loyihalash usuli. Algoritmlar nazariyasida usullarning asosiy yondashuvlari va tamoyillari ko'rib chiqiladi.

3. 
   Algoritmlarni ishlab chiqish. Rivojlanish tanlangan printsiplar va usullar bo'yicha amalga oshiriladi va har qanday qulay tilda amalga oshirilishi mumkin: PL, psevdokod, tabiiy til, blok-diagramma shaklida va boshqalar. Tafsilotlar darajasi va taqdimotni tanlash ishlab chiquvchi va dasturchi o'rtasidagi aloqa qulayligi bilan belgilanadi.
   
4. 
   To'g'riligini baholash. Taklif etilgan algoritm cheklangan vaqt ichida har qanday to'g'ri ma'lumotlar uchun to'g'ri natijani berishini isbotlash kerak. Bu alohida vazifa, chunki ba'zi algoritmlarning to'g'riligini isbotlash juda qiyin. Matematik induksiya usuli to'g'riligini isbotlashning universal usuli hisoblanadi (ko'plab algoritmlar takrorlanuvchi). Algoritmni ko'p sonli misollarda sinab ko'rish hali uning to'g'riligini isbotlamaydi, faqat bitta ma'lumot to'plami algoritmning noto'g'ri ekanligini isbotlashi mumkin. Agar shunday bo'ladigan bo'lsa, algoritmni o'zgartirish yoki yanada tubdan, ilgari qabul qilingan printsiplar va yondashuvlarni qayta ko'rib chiqish kerak. Taxminan algoritmlar uchun, qoida tariqasida, ularning yaqinlashuvi isbotlangan (agar takrorlanuvchi bo'lsa) va chiqish ma'lumotlarining xatosi taxmin qilinadi.
   
5. 
   Algoritmni tahlil qilish. To'g'riligini tahlil qilgandan so'ng, u algoritm samaradorligini tahlil qilishga qiziqadi. Samaradorlikni baholashning 2 turi mavjud: vaqtinchalik samaradorlik (ish tezligining ko'rsatkichi, ko'pincha vaqt emas, balki oddiy operatsiyalar soni taxmin qilinadi) va fazoviy samaradorlik (ishg'ol qilingan RAMni baholash). Algoritmlar nazariyasi algoritmlarning samaradorligi bilan ham shug'ullanadi. Algoritmlarning yana bir muhim xususiyati uning soddaligi. Ushbu algoritmlarni tushunish va dasturlash osonroq, shuning uchun xatolar kamroq bo'ladi. Agar biror narsa sizga mos kelmasa (samaradorlik yoki soddalik), unda dizayn jarayoni yana boshlanadi (diagramaga qarang).
   
6. 
   Algoritmni amalga oshirish. Algoritmni kodlash vaqtida unga xatolar kirib ketishi mumkin yoki algoritmning samarasizligi aniqlanadi. Bundan tashqari, samarali algoritm samarasiz amalga oshirilishi mumkin. Bu erda siz bir qator qoidalarni bilishingiz kerak, masalan, tsikldan tashqari yig'indilardan ba'zi bir o'zgarmas ifodani chiqarib oling; ilmoqlarda keng tarqalgan subspressionlarni tanlang, sekin operatorlarni tezkor hamkasblari bilan almashtiring. Algoritmni amalga oshirish jarayonida sinov jarayoni muhim ahamiyatga ega. Bu alohida vazifa va test sinovlari uchun alohida adabiyotlar ajratilgan. Yaxshi algoritm, qoida tariqasida, mumkin bo'lgan o'zgartirishlar bilan bog'liq bo'lgan tsiklik ishlarni bajarish natijasida olinadi.
   

4.