1
24.Algoritmlar. Algoritmlar murakkabligi
Ko`p vaqtlardan buyon “algoritm” tushuncha nafat matematiklar uchun, balki
oddiy insonlar uchun ham odatdagi tushuncha bo`lib qoldi. U ma`lumotlarni
qayta ishlash uchun konseptual asos hisolanadi.Bunday prosesslarni
avtomatlashtirish mos algoritmlarning borligini ta`minlaydi. Algoritm bilan
birinchi tanishish maktabda natural sonlar ustida arifmetik amallar bajarishni
o`rganishda ro`y beradi. “Algoritm”ni soddalashtirilgan tushunchasi – bu EHM
da dasturlash mumkin degani.
Algoritm so`zi o`zining tuzilishida geografik nom Xorazm so`zining
o`zgartirilganidir. “algoritm” termini kelib chiqishi o`rta asrlik Sharqlik buyuk
olim Muhammad ibn Musa al-Xorazmiy bilan bog`liq. U taxminiy 783 yildan 850
yillarda yashab o`tgan. 2013 yilda Xorazmda bu buyuk olimning tavallud
kunining 1230 yillik yubileyi bo`lib o`tdi. Al-Xorazmiyni arifmetika haqidagi
traktatini arabchadan lotin tilida tarjima qilishda Al-Xorazmi nomi algorismi
kabi transkribsiya qilingan. Mana shu yerdan “algoritm” kelib chiqqan. Boshida
arifmetikada o`nlik pozitsion sonli hisoblashlarni, so`ngra esa ixtiyoriy
jarayonlardagi masalalarni yechishlarda ketma-ket topiladigan miqdorlarni
berilanlar bo`yicha ma`lum qoida va ko`rsatma (instruksiya) lar yordamida
topishni algoritm deb atadilar.
XX asrning 30-yilarigacha algoritm tushunchasi intuitive tushuncha bo`lib
qolgan, matematik qiymatga ega bo`lmay, metodologik tushuncha edi. Shunday
qilib, XX asrning boshlarida algebra va sonlar nazariyasi fani algoritmga ko`plab
muhim misollar berdi. Ular orasida ikkita natural sonning yoki ikkita
ko`phadning eng katta umumiy bo`luvchisini topishni Evklid algoritmi,
tenglamalar sistemasini yechish uchun Gauss algoritmi, bitta o`zgaruvchili rasional
koeffisientli ko`phadning rasional ildizlarini topish algoritmi, haqiqiy koeffisientli
ko`phadning biror oraliqdagi haqiqiy ildizlari sonini topishni Shturm algoritmi,
chekli maydon ustidagi bitta o`zgaruvchili ko`phadni keltirilmaydigan
ko`paytuvchilarga yoyish algoritmlarini aytish mumkin.
2
Bu keltirilgan algoritmik muammolar konkret (aniq) yechish prosedurasini
ko`rsatish yo`li bilan yechildi.Ammo XX asr boshlarida shunday algoritmik
muammolar formulirovka qilingan (ta`riflangan) ediki, bularni yechimini topish
imkoniyati juda kam edi. Bunday muammolarni yechishda yangi logik aparat
(sredstvo) qo`llashni talab qildi. Bir ish yechiladigan algoritmni mavjudligini
isbotlash, buni algotitmni intuitive tushunchasidan foydalanib bajarish mumkin.
Boshqa, ikkinchi ish , bu algoritmni mavjudmas ekanligini isbotlash, buni uchun
albatta algoritmni nima ekanligini aniq bilish kerak bo`ladi.
Algoritm tushunchasining aniq ta`riflash masalasi XX asr 30-yillarida Gilbert,
Chyorch, Klini, Post, Tyuringlarning ilmiy ishlarida yechildi.Bu yechim ikkita
ko`rinishda (formada) bo`ldi: rekursiv funksiya tushunchasi asosida va algoritmik
prosessni yozish asosida. Rekursiv funksiya – bu shunday funksiyaki, uni
qiymatini argumentining ixtiyoriy qiymatlarida hisoblash algoritmi mavjud.
Rekursiv funksiyalarning biror formal sistemada qat`iy konkret (aniq) funksiyalar
sinfi aniqlandi (ta`riflandi).Tezis formulikovka qilindi ( “Chyorch tezisi”), Bunda
aytilishicha, bu berilgan rekursiv funksiyalar sinfi, argumentini qiymati bo`yicha
o`zini qiymatini hisoblash algoritmi bor bo`lgan funksiyalar to`plami bilan ustma-
ust tushadi.
Ikkinchi yo`nalish bo`yicha, algoritmik prosess bu shunday prosesski, konkret
qurilgan mashinada (Tyuring masinasida) bajariladi.Tezis formulirovka qilindi(
“Tyuring tezisi” deb ataladi). Bunda aytilishicha, ixtiyoriy algoritmni mos
Tyuring mashinasida realizatsiya qilish mumkin. Bu ikkita yo`nalishlar hamda
boshqa, uchinchi yo`nalish (Markov, Post)lar bitta algoritmik hisoblanuvchi
funksiyalar sinfiga keldi va Chyorch tezisi yoki Tyuring tezisi algoritmik
muammoni yechish uchun maqsadga muvofiq ekanligi tasdiqlandi.Rekursiv
funksiyaning tushunchasi qat`iy ekanligidan, bu holda odatdagi matematik
texnika bilan isbotlash mumkinki, yechilayotgan biror masalaning funksiyasi
rekursiv bo`lmasligi, bu qaralayotgan masala uchun yechilish algoritmning mavjud
emasligiga ekvivalent.
3
Xuddi shunday, biror masala uchun yechiluvchi mashina Tyuringni
mavjudmasligi,bu masala uchun yechiluvchi algoritmni yo`qligiga teng kuchli.
Bu keltirilgan natijalar deskriptiv(tavsiflovchi) algoritmlar nazariyasining asosi
hisoblanadi, Nazariyaning asosiy predmeti masalalarni algoritmik yechilish
belgisiga qarab klassifikatsiya qilish, ya`ni “ Masala
