Algoritmni loyihalash va tahlil qilishga kirish

1. 
   Algoritmni loyihalash va tahlil qilishga kirish
   

Reja:

1. 
   Algoritmlar nazariyasining paydo bo'lishi.
   
2. 
   Hisoblash modellari.
   

1. 
   Algoritmlar nazariyasining paydo bo'lishi.
   

Algoritmlar nazariyasi - bu algoritmlarning umumiy xususiyatlari va qonuniyatlarini va ularni aks ettirish uchun turli xil rasmiy modellarni o'rganadigan fan. Algoritmlar nazariyasining muammolari qatoriga algoritmik hal etilmaslikni rasmiy isbotlash, algoritmlarning murakkabligini asimptotik tahlil qilish, algoritmlarni murakkablik sinflariga muvofiq tasniflash, algoritmlar sifatini qiyosiy baholash mezonlarini ishlab chiqish va boshqalar kiradi. Algoritmlar nazariyasining rivojlanishi K.Godelning rasmiy tizimlarning, shu jumladan arifmetikaning to'liqsizligi haqidagi teoremalarni isbotlashidan boshlanadi, ulardan birinchisi 1931 yilda isbotlangan. Ushbu teoremalar bilan bog'liq holda ko'plab matematik masalalarni algoritmik ravishda echish mumkin emas degan taxmin (xususan, predikatlarni hisoblashda chegirma muammosi) algoritm tushunchasini standartlashtirish zarurligini tug'dirdi. Ushbu kontseptsiyaning birinchi standartlashtirilgan versiyalari XX asrning 30-yillarida A. Turing, A. Cherch va E. Post asarlarida ishlab chiqilgan. Ular tomonidan taklif qilingan Turing mashinasi, Post mashinasi va Cherkovning lambda hisobi bir-biriga teng bo'lib chiqdi. Godel asarlaridan kelib chiqqan holda, S. Kleen rekursiv funktsiya tushunchasini kiritdi, u ham yuqoridagilarga teng bo'lib chiqdi.
Algoritmning eng muvaffaqiyatli standartlashtirilgan variantlaridan biri bu A.A.Markov tomonidan kiritilgan normal algoritm tushunchasidir. U Turing, Post, Cherch va Kleen ishlaridan o'n yil o'tgach, bir qator algebraik masalalarning algoritmik hal qilinmasligini isbotlash bilan bog'liq holda ishlab chiqilgan.
D. Knut, A. Aho va J. Ullman tomonidan yaratilgan algoritmlar nazariyasiga katta hissa qo'shganligini ham ta'kidlash lozim. Ushbu mavzu bo'yicha eng yaxshi ishlardan biri Tomas X. Kormen, Charlz I. Leyzerson, Ronald L. Rivest, Klifford Shtaynning "Algoritmlar: qurilish va tahlil" kitobidir.
2. Hisoblash modellari.
• Turing mashinasi
• Lambda hisobi - juftlik ko'rib chiqiladi - b ifodasi va uning argumenti, - va hisoblash bu juftlikning birinchi a'zosining ikkinchisiga qo'llanishi yoki qo'llanilishi. Bu sizga funktsiyani va unga tegishli bo'lgan narsalarni ajratish imkonini beradi. Umuman olganda, hisoblash asl λ-ifodadan boshlanadigan zanjir, keyin λ-ifodalarning cheklangan ketma-ketligi bo'lib, ularning har biri oldingisidan β-reduksiyani qo'llagan holda olinadi, ya'ni almashtirish qoidasini oladi.
• Kombinatorial mantiq - hisoblashning talqini b-hisobiga o'xshaydi, ammo muhim farqlar ham mavjud (masalan, sobit Y nuqta kombinatori kombinatorial mantiqda normal shaklga ega, ammo b-hisobda yo'q). Kombinatorial mantiq dastlab paradokslarning mohiyatini o'rganish va matematikaning kontseptual jihatdan aniq asoslarini yaratish uchun ishlab chiqilgan bo'lib, o'zgaruvchining kontseptsiyasi butunlay chiqarib tashlandi, bu o'zgaruvchilarning matematikadagi o'rni va o'rnini aniqlashga yordam berdi.
• Mashinalarni ro'yxatdan o'tkazish (ing.)
o RAM-mashina (inglizcha) - xotiraga tasodifiy kirish imkoniyatiga ega bo'lgan kompyuterni simulyatsiya qiladigan mavhum hisoblash mashinasi. Algoritmlarni tahlil qilishda ko'pincha ushbu hisoblash modeli qo'llaniladi.

2.