Reja: Algoritm tushunchasi

Algoritmlarni loyihalashga kirish. Algoritmlarni ishlab chiqish va tahlil qilishning ilg'or usullari.

REJA:

1. 
   Algoritm tushunchasi.
   
2. 
   Algoritmlarni loyihalash.
   
3. 
   Algoritmlarni loyihalashning asosiy bosqichlari.
   

ЭҲМ ларнинг пайдо бўлиши ( XX асрнинг 2-ярми) билан АЛГОРИТМ

тушунчаси ПРОГРАММАЛАШТИРИШ тушунчаси билан боғланди.

Кўплаб алгоритмик тиллар пайдо бўлди: Фортран, Паскаль, Бейсик….

XII асрда Европада аль – Хорезми. математик трактатининг лотинча таржимаси чиқди. Ўша пайтлар Алгоритм деганда ўнлик саноқ системасида арифметик амалларнинг бажарилаш қоидалари назарда тутилган. Hozirgi davrda algoritm barcha soxalarda qo’llanib kelinmoqda.

Инглиз математиги Алан Тьюринг 1935 – 1936 йилларда «мантиқий ҳисоблаш машинаси» назариясини яратди. Ишлаб чиқилган «Тьюринг Машина»си бўлажак математиклар ва компьютерщиклар учун мажбурий ўқитиладиган бўлди. Лондон меҳмонхоналарининг бирида : «Бу ерда кодларнинг бузувчиси ва информатиканинг пионери Алан Тьюринг (1912 – 1954), туғилган» деб ёзиб қўйилган.

Рус математиги Андрей Марков 1947 йил «нормал алгоритм» тушунчасини киритди ва тизимлашган ва қатъий алгоритмлар умумий назариясини яратди. Белгини қайта ишлашга мўлжалланган замонавий тиллар (Пролог) Марковнинг «нормал алгоритм» ларига асосланади.

Ўнли саноқ системасида Бутун сонлар ва ўнли каср билан арифметик амалларнинг бажарилиш қоидаси биринчи бўлиб, bуюк олим Мухаммaд ибн Мусo ал-Хорaзми (арабчадан таржимаси «Мухаммад Мусo ўғли Хоразмдан», қисқа қилиб Ал-Хоразмий дейилади) томонидан ишлаб чиқилган.

Ал-Хоразмий IX асрда Хива шаҳрида яшаб ижод қилган. Араб тилида ёзилган асарлари йўқолиб кетган, аммо XII асрда лотин тилига таржима қилинган нусхалари сақланиб қолинган. Шу орқали Ғарбий Европа Ўнли саноқ системасида Бутун сонлар ва ўнли каср билан арифметик амалларнинг бажарилиш қоидаси билан танишган.

Алгоритм таърифи. Электрон ҳисоблаш машиналарининг вужудга келишига қадар алгоритмга ҳар хил таъриф бериб келинди. Лекин уларнинг барчаси маъно жиҳатдан бир-бирига жуда яқин бўлиб, бу таъриф ҳозирги кунда қуйидагича талқин қилинади.

Таъриф. Алгоритм деб, бирор масалани ечиш учун маълум қоидага асосан бажариладиган амалларнинг чекли кетма-кетлигига айтилади ёки аниқ натижа берувчи содда ҳисоблашлар кетма-кетлиги.

Yoki boshqacha aytsak aлгоритм-bu to’g’ri aniqlangan hisoblash jarayoni bo’lib, natijada kirishda berilgan m-tlarni chiquvchi m-tlarga aylantirib beradi, ya’ni aлгоритм 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 aлгоритм 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:

Тушунарлилик –алгоритмда ижрочига берилаётган кўрсатмалар аниқ мазмунда бўлиши;

Дискретлилик – алгоритмларни чекли қадамлардан ташкил қилиб бўлаклаш имконияти ;

Чеклилик – бажарилаётган алгоритм чекли қадамларда натижага олиб келиши;

Натижавийлик - натижанинг бўлиши;

Оммавийлик – ҳар бир алгоритм мазмунига кўра бир турдаги масалаларнинг барчаси учун ҳам ўринли бўлиши .

Формаллик –командаларни механик бажариш имконияти.

Бу хосса роботлар, компьютерлар ва бошқа қурилмаларда командаларнинг кетма-кет бажарилишини таъминлайди.

Алгоритм турлари : Чизиқли алгоритм - деб ҳеч қандай шартсиз фақат кетма-кет бажариладиган жараёнларга айтилади.

Тармоқланувчи алгоритм - деб маълум шартларга мувофиқ бажариладиган кўрсатмалардан тузилган алгоритмга айтилади.

Такрорланувчи алгоритм - деб бирон бир шарт текширилиши ёки бирон параметрнинг ҳар хил қийматлари асосида такрорий хисблашларни бажарадиган алгоритмга айтилади.

Чизиқли алгоритм - деб ҳеч қандай шартсиз фақат кетма-кет бажариладиган жараёнларга айтилади. Чизиқли алгоритм структураси:

Тармоқланувчи ва циклик алгоритмлар

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 identifikatsiya 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 operatsiyalar nuqtai nazaridan hal qilingan holda algoritmlarni tuzish usuli hisoblanadi ( protseduralar).

"Pastdan-yuqoriga" usuli, aksincha, oldindan aniqlangan subalgoritmlarning to'g'ri to'plamiga tayanib, funktsional 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 printsiplari (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: funktsional 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: