1. Algoritm tushunchasi. Algoritmlarni loyihalashning asosiy bosqichlari. Algoritm tahlili tushunchasi

Algoritmlarni loyihalash va tahlil qilish faniga kirish. Umumiy tushunchalar.
REJA:


1. Algoritm tushunchasi.
2. Algoritmlarni loyihalash.
3. Algoritmlarni loyihalashning asosiy bosqichlari.
4. Algoritm tahlili tushunchasi.
5. Boshlang’ich bеrilganlar sinflari.
6. Algoritm tahlining asosiy tushunchalari.

EHM larning paydo bo‘lishi ( XX asrning 2-yarmi) bilan ALGORITM

tushunchasi PROGRAMMALASHTIRISH tushunchasi bilan bog‘landi.
Ko‘plab algoritmik tillar paydo bo‘ldi: Fortran, Paskal, Beysik….
XII asrda Yevropada al – Xorezmi. matematik traktatining lotincha tarjimasi chiqdi. O‘sha paytlar Algoritm deganda o‘nlik sanoq sistemasida arifmetik amallarning bajarilash qoidalari nazarda tutilgan. Hozirgi davrda algoritm barcha soxalarda qo‘llanib kelinmoqda.
Ingliz matematigi Alan Tyuring 1935 – 1936 yillarda «mantiqiy hisoblash mashinasi» nazariyasini yaratdi. Ishlab chiqilgan «Tyuring Mashina»si bo‘lajak matematiklar va kompyuterщiklar uchun majburiy o‘qitiladigan bo‘ldi. London mehmonxonalarining birida : «Bu yerda kodlarning buzuvchisi va informatikaning pioneri Alan Tyuring (1912 – 1954), tug‘ilgan» deb yozib qo‘yilgan.
Rus matematigi Andrey Markov 1947 yil «normal algoritm» tushunchasini kiritdi va tizimlashgan va qat’iy algoritmlar umumiy nazariyasini yaratdi. Belgini qayta ishlashga mo‘ljallangan zamonaviy tillar (Prolog) Markovning «normal algoritm» lariga asoslanadi.
O‘nli sanoq sistemasida Butun sonlar va o‘nli kasr bilan arifmetik amallarning bajarilish qoidasi birinchi bo‘lib, buyuk olim Muxammad ibn Muso al-Xorazmi (arabchadan tarjimasi «Muxammad Muso o‘g‘li Xorazmdan», qisqa qilib Al-Xorazmiy deyiladi) tomonidan ishlab chiqilgan.
Al-Xorazmiy IX asrda Xiva shahrida yashab ijod qilgan. Arab tilida yozilgan asarlari yo‘qolib ketgan, ammo XII asrda lotin tiliga tarjima qilingan nusxalari saqlanib qolingan. Shu orqali Gʻarbiy Yevropa O‘nli sanoq sistemasida Butun sonlar va o‘nli kasr bilan arifmetik amallarning bajarilish qoidasi bilan tanishgan.
Algoritm ta’rifi. Elektron hisoblash mashinalarining vujudga kelishiga qadar algoritmga har xil ta’rif berib kelindi. Lekin ularning barchasi ma’no jihatdan bir-biriga juda yaqin bo‘lib, bu ta’rif hozirgi kunda quyidagicha talqin qilinadi.
Ta’rif. Algoritm deb, biror masalani yechish uchun ma’lum qoidaga asosan bajariladigan amallarning chekli ketma-ketligiga aytiladi yoki aniq natija beruvchi sodda hisoblashlar ketma-ketligi.
Yoki boshqacha aytsak algoritm-bu to‘g‘ri aniqlangan hisoblash jarayoni bo‘lib, natijada kirishda berilgan m-tlarni chiquvchi m-tlarga aylantirib beradi, ya’ni algoritm kiruvchi m-tlarni chiquvchi m-tlarga aylantiruvchi hisoblash qadamlari ketma-ketligidan iborat jarayondir. Masalan, amaliyotda juda ko‘p uchraydigan masalalardan biri bu -elementlar ketma-ketligidan ma’lum birlarini aniqlash masalasi ham aniq algoritm asosida yechiladi. Konkret masala: (4,6,-9,43,-11,7,91,-15) sonlar ketma-ketligidan manfiylarini aniqlash masalasida, kiruvchi ketma-ketlikdan chiquvchi (-9,-11,-15) ketma-ketlikni hosil qilish kerak bo‘ladi. Bunday masalalar ko‘pincha oraliq masala sifatida uchraydi. Ma’lumki, bu masalani bir necha hil algoritmlar yordamida echish mumkin. Bunday masalalarni juda ko‘p keltirish mumkin.
Algoritmlarni loyihalash. Algoritmni tanlash qo‘yilgan masalaning shartlari va boshqa bir nechta parametrlar asosida amalga oshiriladi: ular elementlar soni, elementlar joylashish tartibi, EHM axitekturasi, elementlarga qo‘yiladigan masala shartlari va b. bo‘lishi mumkin. Shuning uchun, algoritmni loyihalashda masalaning qo‘yilishi, qo‘llash mumkin bo‘lgan algoritmlar sinflari va yuqoridagi parametrlar juda chuqur o‘rganilishi kerak. Algoritm korrekt deyiladi, agar unng natijasi barcha kiruvchi mt lar uchun aniq chiquvchi mt larni tashkil etsa. Bu holda ihlatilgan korrekt algoritm berilgan masalani yechib beradi deyiladi. Agar algoritm nokorrekt bo‘lsa, uning natijasi ba’zi bir kiruvchi mt lar uchun noto‘g‘ri bo‘ladi yoki umuman natija bermasligi mumkin. Ba’zi hollarda, ya’ni xatoliklarni tekshirib turish imkoni bo‘lganda, nokorrekt algoritmlar ham foydali bo‘lishi mumkin. Ko‘pincha korrekt algoritmlardan foydalaish maqsadga muvofiq hisoblanadi.
Algoritm samaradorligi. Javob berilishi kerak bo‘lgan birinchi jiddiy savol: qanday qilib “samarali algoritm” tushunchasini aniqlash mumkin? Bir qarashda samaradorlikning ishchi ta’rifi quyidagicha ko‘rinishi mumkin.
1- ta’rif: algoritm samarador deb ataladi, agar ma’lumotlar kiritilganda uni amalga oshirish tezkor bajarilsa.
Albatta, samaradorlik nisbiy tushuncha bo‘lib, bir nechta algoritmlarni solishtirish orqali aniqlanadi.
Xossalari:
Tushunarlilik –algoritmda ijrochiga berilayotgan ko‘rsatmalar aniq mazmunda bo‘lishi;
Diskretlilik – algoritmlarni chekli qadamlardan tashkil qilib bo‘laklash imkoniyati ;
Cheklilik – bajarilayotgan algoritm chekli qadamlarda natijaga olib kelishi;
Natijaviylik - natijaning bo‘lishi;
Ommaviylik – har bir algoritm mazmuniga ko‘ra bir turdagi masalalarning barchasi uchun ham o‘rinli bo‘lishi .
Formallik –komandalarni mexanik bajarish imkoniyati.
Bu xossa robotlar, kompyuterlar va boshqa qurilmalarda komandalarning ketma-ket bajarilishini ta’minlaydi.
Algoritm turlari : Chiziqli algoritm - deb hech qanday shartsiz faqat ketma-ket bajariladigan jarayonlarga aytiladi.
Tarmoqlanuvchi algoritm - deb ma’lum shartlarga muvofiq bajariladigan ko‘rsatmalardan tuzilgan algoritmga aytiladi.
Takrorlanuvchi algoritm - deb biron bir shart tekshirilishi yoki biron parametrning har xil qiymatlari asosida takroriy xisblashlarni bajaradigan algoritmga aytiladi.
Chiziqli algoritm - deb hech qanday shartsiz faqat ketma-ket bajariladigan jarayonlarga aytiladi. Chiziqli algoritm strukturasi:

Tarmoqlanuvchi va siklik algoritmlar




Algoritmlarning qo‘llanish soxalari. Algoritmlarni amalda juda ko‘p yo‘nalihlarda qo‘llash mumkin, masalan:
Inson genomini o‘qish masalasi-ya’ni inson DNK siga kiruvchi 100 ming genlar ketma-ketligini identifikasiya ilish; Internet; Elektron tijorat; Ishlab chiqarish va elektron tijoratda resurslardan optimal foydalanish va b.
Algoritmni ishlab chiqish va tahlil qilish usullari. Yuqoridan pastga qarab algoritmni loyihalash yoki ketma-ket (bosqichma-bosqich) algoritmni loyihalash usuli - bu asl muammo (algoritm) bir qator yordamchi pastki qismlarga bo‘linganida (subalgoritmlar) sodda va elementar operasiyalar nuqtai nazaridan hal qilingan holda algoritmlarni tuzish usuli hisoblanadi ( proseduralar).
"Pastdan-yuqoriga" usuli, aksincha, oldindan aniqlangan subalgoritmlarning to‘g‘ri to‘plamiga tayanib, funksional ravishda to‘liqroq bajariladigan kichik vazifalarni tuzadi, ulardan umumiyroq narsalarga o‘tadi va hokazo, biz echimni yoza oladigan darajaga yetguncha. Ushbu usul pastki qavatdagi dizayn usuli sifatida tanilgan.
Algoritmlarning tarkibiyli hosil qilish prinsiplari (algoritmlarni ishlab chiqishning tarkibiy usullari) algoritmlarni asosiy tarkibiy algoritmik birliklaridan hosil qilish, ularning ketma-ket ulanishi yoki bir-birlariga joylashtirilishi algoritmni o‘qilishini va bajarilishini kafolatlaydigan qoidalarni yuqoridan pastga va ketma-ketlikda bajarish tamoyillaridir.
Strukturalangan algoritm - bu asosiy algoritmik tuzilmalarni aniqlash va joylashtirish sifatida taqdim qilingan algoritmdir. Strukturalangan algoritmda statik holat (algoritmni yangilashdan oldin) va dinamik holat (yangilangandan keyin) bir xil mantiqiy tuzilishga ega, uni yuqoridan pastgacha kuzatib borish mumkin ("u ham o‘qiladi, ham bajariladi"). Algoritmlarning strukturali rivojlanishi bilan uning tuzilishi va bajarilishining har bir bosqichida algoritmning to‘g‘riligini kuzatish mumkin.
Algoritmlarni (dasturlarni) loyihalash va ishlab chiqishda keng qo‘llaniladigan usullardan biri bu modulli usul. Modul bu ma’lum bir algoritm yoki uning ba’zi bir bloklari bo‘lib, ularni ajratib va ​​yangilash mumkin bo‘lgan ma’lum nomga ega. Ba’zida modul barcha algoritmlar yordamchi bo‘lsa ham, yordamchi algoritm deb ataladi.
Modul xususiyatlari: funksional yaxlitlik va to‘liqlik (har bir modul bitta vazifani bajaradi, lekin to‘liq va to‘liq bajaradi); avtonomiya va boshqa modullardan mustaqillik (vorislik modulining avvalgi modul ishlashidan mustaqilligi; bundan tashqari, ularning aloqasi faqat parametrlarni uzatish / qabul qilish va boshqarish darajasida amalga oshiriladi);
Algoritmlarning modulli dizaynining afzalliklari:
-turli ijrochilar tomonidan katta hajmli algoritmni (algoritmik kompleks) ishlab chiqish imkoniyati; -eng ko‘p ishlatiladigan algoritmlar (subalgoritmlar) kutubxonasini yaratish va yuritish qobiliyati; algoritmlarni sinash va ularning to‘g‘riligini asoslash; dizaynni soddalashtirish va algoritmlarni o‘zgartirish; algoritmlarni (yoki algoritmlarning komplekslarini) ishlab chiqish (loyihalash) murakkabligini kamaytirish; algoritmlarni amalga oshirishda hisoblash jarayonining kuzatilishi.
Algoritmni sinash - bu maxsus belgilangan testlar yoki test misollarida algoritmning to‘g‘riligi yoki noto‘g‘riligini tekshirish - ma’lum ma’lumotlar va natijalar bilan bog‘liq muammolar (ba’zan ularni yaqinlashtirish etarli). Testlar to‘plami minimal va to‘liq bo‘lishi kerak, ya’ni kirish ma’lumotlar to‘plamining har bir alohida turini, ayniqsa alohida holatlarda, tekshirishni ta’minlaydi. Algoritmlarning ishlash vaqtlari:

n=	n	n*logn	n^2	n^3	1,5^n	2^n	n!
10	<1 s	<1 s	<1 s	<1 s	<1 s	<1 s	<4 s
30	<1 s	<1 s	<1 s	<1 s	<1 s	18min	10^25y
50	<1s	<1s	<1s	<1s	11min	36y	Juda kop
100	<1s	<1s	<1s	<1s	12892y	10^17y	----
1000	<1s	<1s	<1s	18min	---	----	----
10000	<1s	<1s	2min	12kun	--	---	---
100000	<1s	<2s	3soat	32y	---	---	---
1 mln.	<1s	20s	12kun	31710y	---	---	---

Yilda matematika va Kompyuter fanlari, an algoritm (tinglang) ning cheklangan ketma-ketligi aniq belgilangan, kompyuterda qo‘llaniladigan yo‘riqnomalar, odatda muammolar sinfini hal qilish yoki hisoblash uchun. Algoritmlar har doim aniq va ijro etish uchun texnik xususiyatlar sifatida ishlatiladi hisob-kitoblar, ma’lumotlarni qayta ishlash, avtomatlashtirilgan fikrlashva boshqa vazifalar.

Sifatida samarali usul, algoritm cheklangan miqdordagi makon va vaqt ichida ifodalanishi mumkin, va aniq belgilangan rasmiy tilda hisoblash uchun a funksiya. Dastlabki holatdan va dastlabki kirishdan boshlab (ehtimol bo‘sh), ko‘rsatmalar a ta’riflaydi hisoblash bu, qachon ijro etildi, cheklangan orqali keladi oxir-oqibat "mahsulot" ishlab chiqaradigan aniq belgilangan ketma-ket holatlar soni va yakuniy holatida tugatish. Bir holatdan ikkinchisiga o‘tish shart emas deterministik; sifatida ma’lum bo‘lgan ba’zi algoritmlar tasodifiy algoritmlar, tasodifiy kiritishni qo‘shib qo‘ying.
Algoritm tushunchasi antik davrdan beri mavjud. Arifmetik kabi algoritmlar bo‘linish algoritmi, qadimiy tomonidan ishlatilgan Bobil matematiklari v. Miloddan avvalgi 2500 va Misr matematiklari v. Miloddan avvalgi 1550 yil. Yunoniston matematiklari keyinchalik .da algoritmlardan foydalanilgan Eratosfen elagi tub sonlarni topish uchun, va Evklid algoritmi topish uchun eng katta umumiy bo‘luvchi ikkita raqamdan. Arab matematiklari kabi al-Kindi 9-asrda ishlatilgan kriptografik uchun algoritmlar kodni buzish, asoslangan chastota tahlili.
So‘z algoritm o‘zi 9-asr matematikasi nomidan kelib chiqqan Muhoammad ibn Muso al-Xuvrizmi, kimning nisba (uni kimligini aniqlash) Xorazm) lotinlashtirildi Algoritmi sifatida. Algoritmning zamonaviy konsepsiyasiga aylanadigan narsalarning qisman rasmiylashtirilishi echishga urinishlar bilan boshlandi Entscheidungsproblem (qaror muammosi) tomonidan qo‘yilgan Devid Xilbert 1928 yilda. Keyinchalik rasmiylashtirishlar "samarali hisoblash" yoki "samarali usul". Ushbu rasmiylashtirishlarga quyidagilar kiradi Gödel–Herbrand–Kleyen rekursiv funksiyalar 1930, 1934 va 1935 yillarda, Alonzo cherkovi"s lambda hisobi 1936 yil, Emil Post"s Formulyasiya 1 1936 yil va Alan Turing"s Turing mashinalari 1936–37 va 1939 yillar.
"Algoritm" so‘zi nisba lotinlashtirishda, uning geografik kelib chiqishini va Fors tili matematik Muhammad ibn Muso al-Xorazmiy ga algoritm. Al-Xorazmiy (Arablashgan Fors tili 780–850) matematik, astronom, geograf, va olim Donolik uyi yilda Bag‘dod, uning ismi "tug‘ilgan" degan ma’noni anglatadi Xorazm’tarkibiga kirgan mintaqa Buyuk Eron va hozirda O‘zbekiston.
Taxminan 825 yilda al-Xorazmiy an Arab tili traktat Hind-arab raqamlar tizimiga tarjima qilingan Lotin 12 asr davomida. Qo‘lyozma jumla bilan boshlanadi Diksit Algorizmi (’Al-Xorazmiy shunday aytgan’), bu erda "Algorizm" tarjimon bo‘lgan Lotinlashtirish Al-Xorazmiy nomidan.^[21] Al-Xorazmiy O‘rta asrlarning oxirlarida Evropada eng ko‘p o‘qilgan matematik, birinchi navbatda uning boshqa bir kitobi orqali Algebra. Oxirgi o‘rta asr lotin tilida, algoritm, Inglizcha ’algoritm’, uning ismining buzilishi shunchaki "o‘nlik sanoq sistemasi" ni anglatardi.^[23] XV asrda yunoncha Rryumθ (arifmos), ’raqam’ (qarz ’arifmetik’), lotincha so‘z o‘zgartirilgan algoritmva tegishli "algoritm" inglizcha atamasi birinchi marta 17-asrda tasdiqlangan; zamonaviy ma’no 19-asrda paydo bo‘lgan.
Ingliz tilida u dastlab taxminan 1230 yilda, keyin esa ishlatilgan Chaucyer 1391 yilda. Ingliz tili frantsuzcha atamani qabul qildi, ammo 19-asr oxirigacha "algoritm" zamonaviy ingliz tilidagi ma’noga ega bo‘ldi.
So‘zning yana bir erta ishlatilishi - 1240 yildan boshlab, qo‘llanmada Karmen de Algorismo tomonidan tuzilgan Aleksandr de Viledu. Bu bilan boshlanadi: