24. Algoritmlar murakkabligi

M  algoritmik yechiladi” 

yoki  “Masala 

M  algoritmik yechilmaydi”  degan mulohaza olish. Bu yo`nalishda 

bir  qator fundamental natijalar  olindi. Bular orasida – 1952 yilda P.S.Novikov 

tomonidan 1912 yilda Den tomonidan qo`yilgan “chekli aniqlangan gruppa  uchun 

ayniyat”  klassik muammosini   salbiy yechilganligi.1890 yilda Gilbert tomondan 

e`lon qilingan mashhur  o`ninchi muammosi ( 23 ta boshqa muammolar ichidan) 

shunday ta`riflanadi (formulirovka qilinadi): “ 10. Diofant tenglamalarini ychilishi 

haqida masala. Ixtiyoriy sondagi noma`lumli va butun rasional son koeffisientli   

diofant tenglamasi berilgan  bo`lsin. Shunday usul ko`rsatish kerakki, chekli  

sondagi amallar  yordamida bu tenglama butun rasional sonlarda yechimga 

egaligini aniqlasin ”. 1970 yilda Yu.V. Matiyasevich tomonidan Gelbertning 10-

muammosi algoritmik yechilmaydigan   ekanligi isbotlandi. 

Hozirgi vaqtda algoritmlar  nazariyasi hisoblash fanlarida nazariy fundamentni 

taskil  qiladi.Algoritmlar nazariyasini  qo`llash, ilmiy natijalarni o`zidan foydalanib 

amalga oshirildi, yangi tushunchalarni  anglash  va eskilarini aniqlashtirish, kabi 

amalga oshiriladi (bu ayniqsa yaratilgan algoritmlarga tegishli).U yordamida 

isbotlanuvchanlik, effektivlik, yechiluvchanlik, hisoblanuvchanlik va boshqa  

bunday tushunchalar aniqlashtiriladi (tozalanadi). 

“algoritm” termini texnikada kibernetika bilan birga  kirib  kelgan. Masalan, 

algoritm tushunchasi boshqaruvchi signallar  ketma-ketligini effektiv berish nima 

ekanligini  aniqlashda yordam berdi. EHM ni qo`llash algorotmlar nazariyasini 

rivojlanishiga va algoritmik modellarni o`rganishda ishchi xarakteristikalarini ( 

amallar  soni, xotira sarfi) solishtirishda hamda  ularni optimallashtirish uchun 

stimul bo`lib xizmat qildi.   Algoritmlar nazariyasida muhim yo`nalishlar – 

algotimlar murakkabligi va hisoblanuvchanligi  paydo bo`ldi. Avvalo metrik 

algoritmlar nazariyasi yaratildi, u asosan masalalarni murakkablik sinfi bo`yicha 

---

4 

 

klassifikatsiyasidan iborat. Algoritmlar ularga tegishli  ishlar uchun aniq o`rganish 

ob`ekti bo`lib qoldi. Bu sohada masalalarni  tabiiy ravishda algoritmlar 

murakkabligini  quyi va  yuqori baholashlarni olishga bo`linadi. Bu  masalarni 

yechish  usullari tubdan bir-biridan farq qiladi. 

Yuqori baholash  olish uchun algoritmni intuitive tushunchasi  etarli  bo`ladi. 

Buning uchun aniq (konkret) masalani yechish  uchun formal bo`lmagan algoritm 

quriladi, so`ngra mos algoritmik modelni  ishlatish  uchun u formallashtiriladi. Bu 

algoritm  uchun hisoblash murakkabligi (vaqt yoki xotira)  mos funksiyaning 

argumentini barcha qiymatlarida uning qiymatlaridan ortib ketmasa, u  holda bu 

funksiya  qaralayotgan masalaning  yechimini murakkabligini yuqori  bahosi deb  

ataladi. Bu sohada aniq masalalar uchun yuqori baholash olishda ko`plab  muhim 

natijalar olindi. 

Bular ichida butun sonlarni  tez ko`paytirish algoritmi, ko`phadlar va matritsalarni 

tez ko`paytirish algoritmlari, chiziqli tenglamalar sistemasini traditsion 

algotimlarga nisbatan sezilarli darajada kam resurs talab etadigan algoritmlarni 

yaratilishidir. Quyi bohalashni topish (o`rnatish), bu  topilgan chegaradan hech 

qanday algoritmni bundan kichik  murakkablikda    hisoblash mumkin emas  

ekanligini isbotlashdir. Bunday  turdagi natija  olish  uchun qaralayotgan 

algoritmik modelni aniq aniqlash zarur, va bunday natijalar faqat juda murakkab 

hisoblash  modellarida olingan.Bu  munosabat  bilan “nisbiy” quyi baholash 

muammosi rivojlana boshladi. Bu NP-to`liqlik nazariyasi deb ataladi, u qiyin 

yechiladigan qurilmali masalalar bilan bog`langan. 

Algoritmning intuitive tusunchasi aniqlik talab etadi. 

Algoritmga asosiy talablar. 

1.  Har  bir algoritm berilganlar – kiritilgan, oraliq va chiqarish ma`lumotlar 

bilan ishlaydi. Buning uchun  berilgan tushunchasini aniqlashtirish, buning  

uchun kiritilayotgan simvollarning ( sonlar, harflar va shundaylar)   chekli 

alfaviti fiksirlanadi va algoritmik  ob`ekt qurish  qoidasi ko`rsatiladi. Odatda 

foydalaniladigan usul bu induktiv qurishdir. Masalan, dasturlash tilida 

identifikator ta`rifi quyidagicha ko`rinishi mumkin: identifikator – bu yoki 

---

5 

 

harf, yoki undan o`ngda yoki harf yoki son yozilgan  identifikatirdir. Chekli 

alfavitdagi chekli uzunlikdagi soz` - bu algoritmik berilganlar  uchun eng 

yaqin odatdagi  tur, so`zdagi  belgilar soni -  berilganlarni tabiiy hajm 

o`lchovidir. Algoritmik ob`ektlarning boshqa holi – formulalardir. Bunga 

misollar  bo`lib, predikatlar va mulohazalar  algebrasi formulalari xizmat  

qilishi mumkin. Bu  holda alfavitdagi har  qanday  so`z  ham  formula 

bo`lavermaydi.  

2.  Algoritmda berilganlarni joylashtirish  uchun xotira kerak bo`ladi. Xotira  

odatda bir  jinsli va diskret hisoblanadi, ya`ni u bir  xil yacheykalardan 

tuziladi, har bi yacheyka bitta berilgan simvolni saqlashi mumkin. Shu 

sababli berilganlar hajmini o`lchov birligi  va xotira  hajmining o`lchov  

birligi moslashtirilishi lozim. 

3.  Algoritm alohida elementar qadamlardan tuziladi, ya`ni algoritm har xil 

qadamlarning chekli  to`plamidan tuziladi. Elementar qadamlarning 

to`plamiga  tipik misol – bu   EHMning buyruqlar sistemasidir. 

4.  Algoritmni qadamlar ketma-ketligi determinirlangan, ya`ni  har  bir  

qadamdan  keyin,qaysi qadam bajarilishi, qachon algoritm ishi tugallangan 

hisoblash  mumkin ekanli   ko`rsatiladi. 

5.  Algoritm natijaviy bo`lishi lozim, ya`ni chekli sondagi qadamdan keyin 

(boshlang`ich  shartlarga bog`liq holda) natija berish uchun to`xtatilishi 

lozim. Bu xossa ba`zida algoritmni yaqinlashuvchanligi  deyiladi. 

6.  Algoritm realizatsiya mexanizmiga ega bo`lishi, ya`ni algoritmni yozivi 

yordamida  berilgan boshlang`ichlar asosida hisoblash jarayoni tashkil 

qilinishi lozim. Algoritm yozivi  va uni realizatsiya qilish  mexanizmi chekli 

deb faraz qilinadi. 

Shuni  qayd qilish  mumkinki, hisoblash mashinasiga o`xshash, 1 talab EHM 

ning sonli tabiatiga moskeladi, 2 talab – EHM xotirasiga, 3 – talab mashina 

dasturiga, 4 – talab  uning mantiqiy tabiatiga, 5,6 –talablar hisoblash qurilmasi 

va uning imkoniyatlariga mos keladi.