Asosiy hisoblash algoritmlarning murakkabligi

ASOSIY HISOBLASH ALGORITMLARNING MURAKKABLIGI

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:

Hisoblashning murakkabligi nazariya tasniflashga qaratilgan hisoblash muammolari ularning resurslaridan foydalanishga va ushbu sinflarni bir-biriga bog'lashiga qarab. Hisoblash muammosi - bu kompyuter tomonidan hal qilingan vazifadir. Hisoblash muammosi, masalan, matematik qadamlarni mexanik qo'llash orqali hal qilinadi algoritm.

Algoritmdan qat'i nazar, uning echimi muhim resurslarni talab qiladigan bo'lsa, muammo o'z-o'zidan qiyin deb hisoblanadi. Nazariya matematikani kiritish orqali ushbu intuitivlikni rasmiylashtiradi hisoblash modellari ushbu muammolarni o'rganish va ularning miqdorini aniqlash hisoblash murakkabligi, ya'ni vaqt va saqlash kabi ularni hal qilish uchun zarur bo'lgan resurslar miqdori. Murakkablikning boshqa o'lchovlaridan ham foydalaniladi, masalan, aloqa miqdori (ichida ishlatiladigan) aloqa murakkabligi), soni darvozalar zanjirda (ishlatilgan elektronning murakkabligi) va protsessorlarning soni (ishlatilgan parallel hisoblash). Hisoblash murakkabligi nazariyasining rollaridan biri bu kompyuterlar qila oladigan va qila olmaydigan narsalarning amaliy chegaralarini aniqlashdir. The P va NP muammosi, etti kishidan biri Ming yillik mukofoti muammolari, hisoblash murakkabligi sohasiga bag'ishlangan.^[1]

Nazariy kompyuter fanlari bilan chambarchas bog'liq sohalar algoritmlarni tahlil qilish va hisoblash nazariyasi. Algoritmlarni tahlil qilish va hisoblashning murakkabligi nazariyasining asosiy farqi shundaki, birinchisi muammoni hal qilish uchun ma'lum bir algoritm uchun zarur bo'lgan resurslar miqdorini tahlil qilishga bag'ishlangan, ikkinchisi ishlatilishi mumkin bo'lgan barcha algoritmlar haqida umumiyroq savol beradi. xuddi shu muammoni hal qiling. Aniqrog'i, hisoblashning murakkabligi nazariyasi tegishli ravishda cheklangan resurslar bilan hal qilinishi mumkin yoki mumkin bo'lmagan muammolarni tasniflashga harakat qiladi. O'z navbatida, mavjud resurslarga cheklovlar qo'yish - bu hisoblashning murakkabligini hisoblash nazariyasidan ajratib turadigan narsa: oxirgi nazariya, qanday muammolarni, asosan, algoritmik tarzda echish mumkinligini so'raydi.

A hisoblash muammosi ning cheksiz to'plami sifatida qaralishi mumkin misollar bilan birga yechim har bir misol uchun. Hisoblash muammosi uchun kirish satri muammoning misoli deb ataladi va uni muammoning o'zi bilan aralashtirib yubormaslik kerak. Hisoblash murakkabligi nazariyasida muammo echilishi kerak bo'lgan mavhum savolga ishora qiladi. Aksincha, ushbu muammoning bir misoli - bu aniq bir mulohaza bo'lib, u qaror qabul qilish muammosi uchun xizmat qilishi mumkin. Masalan, ning muammosini ko'rib chiqing dastlabki sinov. Namuna raqam (masalan, 15) bo'lib, agar raqam tub bo'lsa, aks holda "yo'q" (bu holda 15 asosiy emas va javob "yo'q") bo'lsa, "ha" bo'ladi. Boshqa yo'l bilan aytilgan misol muammoning o'ziga xos usuli hisoblanadi va yechim berilgan kirishga mos keladigan chiqishdir.

Muammo va misol o'rtasidagi farqni yanada ko'proq ta'kidlash uchun, qaror versiyasining quyidagi nusxasini ko'rib chiqing sotuvchi muammosi: Germaniyaning 15 ta eng yirik shaharlari bo'ylab eng ko'pi 2000 kilometrlik yo'l bormi? Muammoning ushbu misoliga miqdoriy javob muammoning boshqa misollarini hal qilish uchun juda kam foydalidir, masalan, barcha saytlar bo'ylab sayohat qilishni so'rash. Milan ularning umumiy uzunligi eng ko'pi bilan 10 km. Shu sababli, murakkablik nazariyasi hisoblash muammolarini va muayyan muammo misollarini emas.

Hisoblash muammolarini ko'rib chiqishda muammo misoli a mag'lubiyat ustidan alifbo. Odatda, alifbo ikkilik alfavit (ya'ni, {0,1} to'plam) deb qabul qilinadi va shu tariqa satrlar iplar. Haqiqiy hayotda bo'lgani kabi kompyuter, bit iplaridan tashqari matematik ob'ektlar mos ravishda kodlangan bo'lishi kerak. Masalan, butun sonlar bilan ifodalanishi mumkin ikkilik yozuvva grafikalar to'g'ridan-to'g'ri ular orqali kodlanishi mumkin qo'shni matritsalaryoki ularni kodlash orqali qo'shni ro'yxatlar ikkilik.

Murakkablik-nazariy teoremalarning ba'zi bir dalillari muntazam ravishda kirish kodlashning aniq tanlovini qabul qilsa ham, munozarani kodlash tanlovidan mustaqil bo'lish uchun etarli darajada mavhum tutishga harakat qiladi. Bunga turli xil vakilliklarni bir-biriga samarali ravishda o'zgartirilishini ta'minlash orqali erishish mumkin.

Qaror bilan bog'liq muammolar hisoblash murakkabligi nazariyasining asosiy tadqiqot ob'ektlaridan biridir. Qaror muammosi - bu javobning har ikkalasi ham bo'lgan hisoblashning maxsus turi ha yoki yo'q, yoki navbat bilan 1 yoki 0. Qaror bilan bog'liq muammoni a sifatida ko'rish mumkin rasmiy til, bu erda til a'zolari natijasi ha bo'lgan, a'zo bo'lmaganlar esa natijasi yo'q bo'lgan holatlar. Maqsad an yordami bilan qaror qabul qilishdir algoritm, berilgan kirish satri ko'rib chiqilayotgan rasmiy tilning a'zosi bo'ladimi. Agar ushbu muammoni hal qilish algoritmi javobni qaytarsa ha, algoritm kirish satrini qabul qiladi, aks holda kiritishni rad etadi deyiladi.

Qaror qabul qilish muammosiga misol sifatida quyidagilarni keltirish mumkin. Kirish o'zboshimchalik bilan grafik. Muammo berilgan grafigi yoki yo'qligini hal qilishdan iborat ulangan yoki yo'qmi. Ushbu qaror muammosi bilan bog'liq bo'lgan rasmiy til - bu barcha bog'langan grafikalar to'plamidir - bu tilning aniq ta'rifini olish uchun grafikalar qanday qilib ikkilik qator sifatida kodlanishini hal qilish kerak.

Turing mashinasi bu umumiy hisoblash mashinasining matematik modeli. Bu lenta lentasida joylashgan belgilar bilan manipulyatsiya qiluvchi nazariy qurilma. Turing mashinalari amaliy hisoblash texnologiyasi sifatida emas, balki hisoblash mashinasining umumiy modeli sifatida - rivojlangan superkompyuterdan tortib qalam va qog'oz bilan matematikgacha. Agar biror masalani algoritm yordamida echish mumkin bo'lsa, unda bu masalani hal qiladigan Turing mashinasi mavjud deb ishoniladi. Darhaqiqat, bu Cherkov-Turing tezisi. Bundan tashqari, ma'lumki, bugungi kunda bizga ma'lum bo'lgan hisoblashning boshqa modellarida hisoblash mumkin bo'lgan barcha narsalar, masalan RAM mashinasi, Konveyning "Hayot o'yini", uyali avtomatlar yoki istalgan dasturlash tilini Tyuring mashinasida hisoblash mumkin. Turing mashinalarini matematik jihatdan tahlil qilish oson va hisoblashning boshqa har qanday modeli kabi kuchli ekanligiga ishonganligi sababli, Turing mashinasi murakkablik nazariyasida eng ko'p ishlatiladigan modeldir.

Kabi murakkablik sinflarini aniqlash uchun Turing mashinalarining ko'p turlari qo'llaniladi deterministik Turing mashinalari, ehtimoliy Turing mashinalari, deterministik bo'lmagan Turing mashinalari, kvantli Turing mashinalari, nosimmetrik Turing mashinalari va o'zgaruvchan Turing mashinalari. Ularning barchasi printsipial jihatdan bir xil darajada kuchli, ammo resurslar (masalan, vaqt yoki makon) chegaralangan bo'lsa, ularning ba'zilari boshqalarga qaraganda kuchliroq bo'lishi mumkin.

Determinik Turing mashinasi - bu kelajakdagi harakatlarini aniqlash uchun qat'iy qoidalar to'plamidan foydalanadigan eng asosiy Turing mashinasi. Ehtimolli Turing mashinasi - bu qo'shimcha tasodifiy bitlarga ega bo'lgan deterministik Turing mashinasi. Ehtimoliy qarorlar qabul qilish qobiliyati ko'pincha algoritmlarga muammolarni yanada samarali hal qilishga yordam beradi. Tasodifiy bitlardan foydalanadigan algoritmlar chaqiriladi tasodifiy algoritmlar. Deterministik bo'lmagan Tyuring mashinasi - bu determinizmning o'ziga xos xususiyatiga ega bo'lgan deterministik Turing mashinasi bo'lib, u Turing mashinasiga berilgan holatdan kelajakda bir nechta mumkin bo'lgan harakatlarni amalga oshirishga imkon beradi. Determinizmni ko'rib chiqishning bir usuli shundaki, Turing mashinasi har bir qadamda ko'plab mumkin bo'lgan hisoblash yo'llariga bo'linadi va agar u ushbu tarmoqlarning birortasida muammoni hal qilsa, bu muammoni hal qildi. Shubhasiz, ushbu model jismoniy jihatdan amalga oshiriladigan model degani emas, bu shunchaki qiziqarli murakkablik sinflarini keltirib chiqaradigan nazariy jihatdan qiziqarli mavhum mashinadir. Masalan, qarang deterministik bo'lmagan algoritm.

Adabiyotlar:

1. 
   Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн «Алгоритмы. Построение и анализ» Вильямс, 2013 год, 1324 стр. Издание 3-е
   
2. 
   http://www.math.nsc.ru/LBRT/k5/OR-MMF/Kleinberg_Tardoc_algoritmy_razrabotka_i_primenenie.pdf
   
3. 
   https://e-maxx.ru/bookz/files/cormen.pdf
   
4. 
   https://studfile.net/preview/5535319/page:24/