Algorítm (lot. algorithmi — markaziy osiyolik matematik Al-Xorazmiynomidan) — muayyan turdagi masalalarni yechishga doir aniq belgilangan qoidalar majmui yoki ko‘rsatmalarto‘plami bo‘lib, ular muayyan masalani yechishda bajaruvchi harakatlarining tartibini tavsiflaydi. Avvalgi talqinda «tartib» o‘rniga «ketma-ketlik» so‘zi ishlatilgan, biroq kompyuterlarning parallel ishlashi rivojlanishi bilan «ketma-ketlik» so‘zi yanada umumiy «tartib» tushunchasi bilan almashtirila boshlandi. Mustaqil ko‘rsatmalar, agar bajaruvchilarning imkoniyatlari bunga yo‘l qo‘ysa, ixtiyoriy tartibda, jumladan, bir vaqtda bajarilishi mumkin.
Ilgari rus tilida «algorifm» deb ham yozilgan; hozir bunday yozilish kam qo‘llanadi, ammo ayrim istisnolar saqlangan (Markovning normal algorifmi Markov).
Ko‘pincha bajaruvchi vazifasini kompyuter bajaradi, biroq algoritm tushunchasi faqat kompyuter dasturlariga taalluqli emas. Masalan, taom tayyorlashning aniq yozilgan retsepti ham algoritmdir. Bunday holda bajaruvchi inson (yoki, masalan, to‘quv yoxud tokarlik dastgohi kabi raqamli boshqariladigan mexanizm).
Algoritmlar hisoblash (quyida asosan shular haqida so‘z yuritiladi) va boshqaruvalgoritmlariga ajratiladi. Hisoblash algoritmlari maʼlum bir funksiyani hisoblash orqali boshlang‘ich maʼlumotlarni natijaviy maʼlumotlarga aylantiradi. Semantika jihatidan boshqaruv algoritmlari ulardan sezilarli farq qilishi mumkin: ular belgilangan vaqtlarda yoki tashqi hodisalarga javoban zarur boshqaruv taʼsirlarini hosil qilishga qaratiladi (bunday holatda boshqaruv algoritmi, hisoblash algoritmidan farqli ravishda, cheksiz bajarilsa ham to‘g‘ri ishlashi mumkin).
Algoritm tushunchasi matematikaning dastlabki, asosiy va tayanch tushunchalaridan biridir. Algoritmik xususiyatga ega hisoblash jarayonlari (butun sonlar ustida arifmetik amallar bajarish, ikki sonning eng katta umumiy bo‘luvchisini topish va hokazolar) insoniyatga juda qadimdan maʼlum. Biroq algoritm tushunchasi aniq shaklda faqat XX asr boshlarida qaror topgan.
Algoritm tushunchasini qisman formallashtirishga urinishlar yechim topish muammosini (nem. Entscheidungsproblem) hal etish yo‘llarini izlashdan boshlangan. Bu muammoni David Hilbert esa 1928-yildailgari surgan. Formallashtirishning keyingi bosqichlari samarali hisoblash yoki «samarali usul» tushunchasini belgilash uchun zarur edi. Bunday yondashuvlarga jumladan, rekursiv funksiyalar — Gyodel — Erbran — Klini (ishlanmalar: 1930, 1934 va 1935-yillarda), λ-hisob — Alonzo Chyorch 1936 -yilda; «1-formulyatsiya» — Emil Postning 1936-yildagi ishlanmasi va Tyuring mashinasi.
Atama tarixi


Hisoblash algoritmining zamonaviy formal taʼrifi 30—50-yillarda ( XX asr ) quyidagi olimlarning ishlarida berilgan: Tyuring, Post, Chyorch (Chyorch–Tyuring tezisi), N. Viner, A. A. Markov.
«Algoritm» so‘zining o‘zi fors (xorazmlik) olimi Al-Xorazmiynomidan kelib chiqqan. Taxminan 825-yilda u «Kitob al-jabr val-muqobala» («Qo‘shish va ayirish haqidagi kitob») asarini yozgan. Asarning asl nomidagi «algebra» (al-jabr — to‘ldirish) so‘zi keyinchalik «algebra» atamasiga asos bo‘lgan. Bu kitobda Hindistonda yaratilgan o‘nlik pozitsion sanoq tizimi ilk bor tavsiflangan. Kitobning arabcha asl nusxasi saqlanmagan. Al-Xorazmiy yangi tizimda hisoblash qoidalarini bayon qilgan hamda son yozuvidagi bo‘sh xonani ko‘rsatish uchun, ehtimol, birinchi bo‘lib 0 raqamidan foydalangan (arablar uning hindcha nomini as-sifr yoki shunchaki sifrdeb tarjima qilgan; «sifra» va «shifr» kabi so‘zlar shu yerdan kelib chiqqan). Taxminan shu davrda boshqa arab olimlari ham hind raqamlarini qo‘llay boshlagan.
XII asrning birinchi yarmida Al-Xorazmiy kitobi lotincha tarjimada Yevropaga kirib borgan. Nomi bizgacha yetib kelmagan tarjimon asarni Algoritmi de numero Indorum («Hindcha hisoblash haqida Algoritmi») deb atagan. Shu tariqa markaziy osiyolik olimning lotinlashtirilgan ismi kitob sarlavhasiga aylangan. Hozir «algoritm» so‘zi Yevropa tillariga aynan shu tarjima orqali kirib kelgan, deb hisoblanadi. Keyingi bir necha asrda raqamlar yordamida hisoblash sanʼatini o‘rgatishga bag‘ishlangan ko‘plab asarlar paydo bo‘lgan va barcha sarlavhalarda « algoritmi » yoki « algorismi» so‘zlari uchragan.
Keyingi mualliflar Al-Xorazmiy haqida hech narsa bilmagan. Biroq kitobning ilk tarjimasi «Dixit algorizmi: …» («Al-Xorazmiy aytgan: …») so‘zlari bilan boshlangani uchun bu so‘z hali ham muayyan shaxsning ismi bilan bog‘langan. Kitob yunoncha kelib chiqqan degan qarash ham keng tarqalgan. XIII asrda sheʼriy shaklda yozilgan anglo-normand qo‘lyozmasida quyidagilarni o‘qiymiz:
Algorizm ixtiro qilingan joy — Yunoniston.
Bu — arifmetikaningbir qismidir. Uni Algorizm ismli usta yaratgan, U unga o‘z ismini bergan. Uning ismi Algorizm bo‘lgani uchun,
U kitobini «Algorizm» deb atagan.
Taxminan 1250-yilda ingliz astronomi va matematigi Ioann Sakrobosko arifmetikaga oid Algorismus vulgarisasarini yozgan. U ko‘p asrlar davomida Yevropaning ko‘plab universitetlarida o‘nlik pozitsion sanoq tizimida hisoblashga oid asosiy darslik bo‘lib xizmat qilgan. Kirish qismida Sakrobosko hisoblash ilmi asoschisi deb Algus (Algus) ismli donishmandni ko‘rsatgan. O‘rta asrlardagi mashhur «Atirgul haqida roman» (1275—1280) Jan de Men asarida «yunon faylasufi Algus» Platon, Aristotel, Yevklid va Ptolemeybilan bir qatorda tilga olinadi! Ismning Argus (Argus) tarzidagi yozilishi ham uchraydi. Qadimgi yunon mifologiyasiga ko‘ra, «Argo» kemasini Yasonqurgan bo‘lsa-da, kemaning qurilishi aynan shu Argoga nisbat berilgan.
«Usta Algus» (yoki Argus) o‘rta asr adabiyotida hisoblash sanʼatining timsoliga aylangan. Yuqorida tilga olingan «Atirgul haqida roman»da ham, Duranteyozgan mashhur italyancha «Gul» dostonida ham hatto «mestre Argus» oshiqlarning necha marta urishib, necha marta yarashganini sanay olmasligi aytilgan parchalar mavjud. Ingliz shoiri Jeffri Choser «Gersoginya kitobi» (1369 -yil) dostonida qahramonning dahshatli tushlariga kirgan maxluqlarni hatto «mashhur hisobchi Argus» (noble countour Argu) ham sanay olmasligini yozadi.
Biroq vaqt o‘tishi bilan bunday izohlar matematiklarni tobora kamroq qiziqtira boshladi va matematik asarlar nomida muntazam uchraydigan algorism (yoki algorismus) so‘zi arab raqamlari yordamida, yaʼni abakusdanfoydalanmay, qog‘ozda arifmetik amallarni bajarish usuli maʼnosini oldi. Aynan shu maʼnoda u ko‘plab Yevropa tillarigakirgan. Masalan, nufuzli ingliz tili lug‘ati Webster’s New World Dictionary(1957-yilgi nashri)da bu so‘z «eskirgan» belgisi bilan keltirilgan. Brokgauz va Yefron ensiklopedik lug‘ati esa quyidagicha talqin beradi: algorifm (inqilobgacha algoriѳmъshaklida, fitaharfi bilan yozilgan) «al-goretm», yaʼni «ildiz» degan arabcha so‘zdan kelib chiqqan.
Algoritm — raqamlar yordamida hisoblash sanʼatidir, lekin dastlab «raqam» so‘zi faqat nolni anglatgan. Mashhur fransuz truveri Gotye de Kuansi (Gautier de Coincy, 1177—1236) sheʼrlaridan birida algorismus-cipher (0 raqamini anglatuvchi) so‘zlarini mutlaqo befoyda odamni tasvirlash uchun metafora sifatida qo‘llagan. Aftidan, bu obrazni tushunish tinglovchilardan muayyan bilim talab qilgan. Bu esa yangi sanoq tizimi o‘sha paytdayoq ularga yaxshi tanish bo‘lganini bildiradi.
Ko‘p asrlar davomida abak amaliy hisoblashning deyarli yagona vositasi bo‘lgan. Undan savdogarlar, sarroflar va olimlar foydalangan. Hisoblash taxtasining afzalliklarini Orilyaklik Gerbert (938—1003) kabi buyuk mutafakkir ham o‘z asarlarida bayon etgan. U 999-yilda Rim papasi bo‘lib, Silvestr II nomini olgan. Yangi usul juda katta qiyinchilik bilan ommalashgan. Matematika tarixida arab raqamlari o‘rniga abakdan foydalanishni targ‘ib qilgan algorismchilar va abakchilar (baʼzan gerbekchilar deb atalgan) o‘rtasidagi keskin qarama-qarshilik maʼlum. Qizig‘i, mashhur fransuz matematigi Nikola Shyuke (Nicolas Chuquet, 1445—1488) Lion shahrining soliq to‘lovchilar reyestriga algorismchi (algoriste) sifatida kiritilgan. Yangi hisoblash usuli uzil-kesil qaror topishi uchun bir necha asr kerak bo‘lgan: umumiy qabul qilingan belgilarni ishlab chiqish, hisoblash usullarini takomillashtirish va qog‘ozda yozishga moslashtirishga shuncha vaqt sarflangan. G‘arbiy Yevropada hatto XVII asrgacha, masalan, matematik Nikkolo Tartalya (1500—1557).
Shunday qilib, hisoblash sanʼati haqidagi asarlar Algoritmlardeb atalgan. Ular yuzlab bo‘lgan. Ular orasida sheʼriy shaklda yozilgan Carmen de Algorismo risolasi (lotincha carmen so‘zining o‘zi «sheʼr» degan maʼnoni bildiradi; muallifi Aleksandr de Vill Dyei, Alexander de Villa Dei, vafoti 1240-yil) yoki venalik astronom va matematik Georg Purbax (Georg Peurbach, 1423—1461) yozgan Opus algorismi jocundissimi («Algoritm haqida eng quvnoq asar») darsligi kabi g‘ayrioddiy asarlar ham bor.
Asta-sekin so‘zning maʼnosi kengaygan. Olimlar undan nafaqat hisoblash, balki boshqa matematik amallarni ifodalash uchun ham foydalana boshlagan. Masalan, taxminan 1360-yilda fransuz faylasufi Nikolay Orem (Nicolaus Oresme, 1323/25-1382) Algorismus proportionum («Proporsiyalarni hisoblash») risolasini yozgan. Unda u birinchi bo‘lib kasr ko‘rsatkichli darajalarni qo‘llagan va amalda logarifmlar g‘oyasiga juda yaqin kelgan. Abak o‘rnini chiziqlar bo‘yicha hisoblash deb ataluvchi usul egallagach, unga bag‘ishlangan ko‘plab qo‘llanmalarga quyidagi nom berilgan: Algorithmus linealis, yaʼni chiziqlarda hisoblash qoidalari.
Dastlabki algorismi shakli vaqt o‘tishi bilan oxirgi harfini yo‘qotib, yevropaliklar talaffuzi uchun qulayroq algorismko‘rinishini olganiga eʼtibor berish mumkin. Keyinchalik bu shakl ham, ehtimol, inglizcha « arithmetic» so‘zining taʼsirida o‘zgargan.
1684-yilda Gotfrid Leybnits o‘zining Nova Methodvs pro maximis et minimis, itemque tangentibus… asarida «algoritm» (Algorithmo) atamasini birinchi marta yanada keng maʼnoda — differensial hisob masalalarini yechishning tizimli usuli sifatida qo‘llagan.
XVIII asrda Germaniyaning matematik lug‘atlaridan biri — Vollstandiges mathematisches Lexicon ( Leypsigda 1747-yilda nashr etilgan) — algorithmus atamasini hali ham to‘rtta arifmetik amal haqidagi tushuncha sifatida izohlagan. Biroq bu yagona maʼno bo‘lmagan, chunki o‘sha davrda matematika terminologiyasi endigina shakllanayotgan edi. Xususan, algorithmus infinitesimalis iborasi cheksiz kichik miqdorlar ustida amallar bajarish usullariga nisbatan ishlatilgan. «Algoritm» so‘zidan Leonard Eylerham foydalangan. Uning asarlaridan biri «Pell muammosini yechishda yangi algoritmning qo‘llanilishi» deb nomlangan (De usu novi algorithmi in problemate Pelliano solvendo). Demak, Eylerning algoritmni masala yechish usulining sinonimi sifatida tushunishi hozirgi taʼrifga juda yaqin bo‘lgan.
Shunga qaramay, so‘zning barcha eski maʼnolari isteʼmoldan chiqishi uchun yana qariyb ikki asr kerak bo‘lgan. Bu jarayonni «algoritm» so‘zining rus tiliga kirib kelishi misolida kuzatish mumkin.
Tarixchilar «Hisoblash donoligi» nomi bilan maʼlum qadimgi rus arifmetika darsligining bir qo‘lyozma nusxasini 1691-yilga taalluqli deb hisoblaydi. Bu asarning ko‘plab variantlari mavjud (eng dastlabkilari undan qariyb yuz yil avval yozilgan) va ular XVI asrning yanada qadimgi qo‘lyozmalariga borib taqaladi. Ularda arab raqamlari va ular ustida amal bajarish qoidalari haqidagi bilimlar Rusda asta-sekin qanday tarqalganini kuzatish mumkin. Darslikning to‘liq nomi «Yunoncha arifmetika, nemischa algorizma, ruscha esa raqamli hisoblash donoligi deb ataluvchi ushbu kitob» tarzida berilgan.
Shunday qilib, ilk rus matematiklari «algoritm» so‘zini G‘arbiy Yevropadagi kabi tushungan. Biroq bu atama mashhur Dal lug‘atidaham, yuz yil o‘tib Ushakov tahriri ostida chop etilgan «Rus tilining izohli lug‘ati»da (1935) ham yo‘q edi. Ammo «algorifm» so‘zi inqilobdan oldingi mashhur Aka-uka Granatlar ensiklopedik lug‘atidaham, Katta sovet ensiklopediyasining (KSE) 1926-yilda nashr etilgan birinchi nashrida ham uchraydi. Ikkalasida ham u o‘nlik sanoq tizimidagi to‘rt arifmetik amaldan birini bajarish qoidasi sifatida bir xil talqin qilingan. Biroq XX asr boshlariga kelib matematiklar uchun «algoritm» so‘zi qatʼiy belgilangan qoidalar bo‘yicha bajariladigan istalgan arifmetik yoki algebraik jarayonni bildirgan; KSEning keyingi nashrlarida ham shu izoh berilgan.

Algoritmlar olimlar eʼtiborini tobora ko‘proq jalb qila boshladi va asta-sekin bu tushuncha zamonaviy matematikada markaziy o‘rinlardan birini egalladi. Matematikadan yiroq odamlar esa qirqinchi yillarning boshlariga kelib bu so‘zni, ehtimol, faqat maktabda «Yevklid algoritmi» birikmasi orqali eshitgan. Shunga qaramay, algoritm hanuz tor doiradagi maxsus termin sanalgan. Buni kichikroq ensiklopediyalarda tegishli maqolaning yo‘qligi ham tasdiqlaydi. Masalan, atama hatto o‘n jildlik Kichik sovet ensiklopediyasida (1957) ham uchramaydi, bir jildli ensiklopedik lug‘atlar haqida esa gapirmasa ham bo‘ladi. Ammo oradan o‘n yil o‘tib, Katta sovet ensiklopediyasining uchinchi nashrida (1969) algoritm matematikaning «soddaroq tushunchalar orqali formal taʼrifga ega bo‘lmagan va bevosita tajribadan mavhumlashtirib olingan» asosiy kategoriyalaridan biri sifatida tavsiflangan. Ko‘rinib turibdiki, KSEning birinchi nashridagi talqindan farq juda katta! Qirq yil ichida algoritm matematikaning tayanch tushunchalaridan biriga aylandi. Buning eʼtirofi sifatida atama nafaqat ensiklopediyalarga, balki lug‘atlarga ham kiritildi. Masalan, akademik «Rus tili lug‘ati»da (1981) u aynan matematik termin sifatida berilgan.
Algoritm tushunchasining rivojlanishi bilan birga u sof matematika doirasidan boshqa sohalarga ham asta-sekin tarqala boshladi. Bunga kompyuterlarning paydo bo‘lishi turtki berdi: 1985-yilda «algoritm» so‘zi barcha maktab informatika darsliklariga kirib, yangi hayot boshladi. Umuman, bu atamaning hozirgi mashhurligi kompyuterlar qanchalik keng tarqalganiga bevosita bog‘liq. Masalan, «Bolalar ensiklopediyasi»ning uchinchi jildida (1959) hisoblash mashinalari haqida ko‘p yozilgan, ammo ular hali odatiy narsaga aylanmagan, balki yorqin, biroq ancha olis kelajakning belgisi sifatida tasavvur etilgan. Shu sababli unda algoritmlar biror marta ham tilga olinmagan. 1970-yillar boshida esa kompyuterlar g‘aroyib yangilik bo‘lmay qolgach, «algoritm» so‘zi tezda kundalik tilga kira boshladi. Bu ensiklopedik nashrlarda ham yaqqol aks etgan. «Kibernetika ensiklopediyasi»dagi (1974) «Algoritm» maqolasida u hisoblash mashinalarida amalga oshirish bilan bog‘langan. «Sovet harbiy ensiklopediyasi»da (1976) hatto alohida maqola paydo bo‘lgan: «Masalani EHMda yechish algoritmi».
So‘nggi bir yarim–ikki o‘n yillikda kompyuter hayotimizning ajralmas qismiga aylandi, unga oid so‘zlar esa tobora odatiy tus oldi. Bugun «algoritm» so‘zini deyarli hamma bilsa kerak. U so‘zlashuv tiliga ham ishonch bilan kirib keldi: gazetalarda va siyosatchilar nutqida «xulq-atvor algoritmi», «muvaffaqiyat algoritmi», hatto «xiyonat algoritmi» kabi iboralarni tez-tez uchratamiz. Akademik N. N. Moiseyev kitobini «Rivojlanish algoritmlari», mashhur shifokor N. M. Amosov esa asarlarini «Salomatlik algoritmi» va «Aql algoritmlari» deb nomlagan. Bu so‘z yashayotganini, yangi maʼnolar va mazmuniy nozikliklar bilan boyib borayotganini ko‘rsatadi.
Algoritmning taʼriflari
Algoritmlarning xususiyatlari
Algoritmning turli taʼriflarida ochiq yoki yashirin shaklda quyidagi umumiy talablar mavjud:
- Diskretlik — algoritm masalani yechish jarayonini sodda qadamlardan iborat tartibli ketma-ketlik sifatida ifodalashi kerak. Har bir qadamni bajarish uchun chekli vaqt talab etiladi, yaʼni boshlang‘ich maʼlumotlarning natijaga aylanishi vaqt bo‘yicha diskret sodir bo‘ladi.
- Deterministiklik (aniqlik). Har bir vaqtda keyingi qadam tizimning holati bilan bir maʼnoda belgilanadi. Shunday qilib, algoritm bir xil boshlang‘ich maʼlumotlar uchun bir xil natija (javob) beradi. Zamonaviy talqinda ayni algoritmning turli amalga oshirilishlarida izomorf grafbo‘lishi kerak. Boshqa tomondan, keyingi qadam tizimning joriy holati va hosil qilingan tasodifiy songa bog‘liq bo‘ladigan ehtimollik algoritmlari ham mavjud. Biroq tasodifiy sonlarni hosil qilish usuli «boshlang‘ich maʼlumotlar» ro‘yxatiga kiritilsa, ehtimollik algoritmi odatiy algoritmning bir turiga aylanadi.
- Tushunarlilik — algoritm faqat bajaruvchi bajara oladigan va uning buyruqlar tizimiga kiradigan buyruqlardan iborat bo‘lishi kerak.
- Yakunlanuvchanlik (cheklilik) — algoritm matematik funksiya sifatida torroq talqin qilinganda, to‘g‘ri berilgan boshlang‘ich maʼlumotlar uchun u maʼlum sondagi qadamlardan keyin ishini tugatib, natija berishi kerak. Donald Knut algoritmning yakunlanuvchanlikdan tashqari barcha xususiyatlariga javob beradigan protsedurani hisoblash usuli (ingl. computational method) deb ataydi. Biroq algoritm taʼrifiga ko‘pincha chekli vaqt ichida yakunlanish talabi kiritilmaydi. Bunday holda algoritm (hisoblash usuli) qisman funksiyani[ingl.]belgilaydi. Ehtimollik algoritmlari uchun yakunlanuvchanlik, odatda, algoritm istalgan to‘g‘ri boshlang‘ich maʼlumotlarda 1 ehtimollik bilan natija berishini anglatadi (yaʼni ayrim hollarda u tugamasligi mumkin, biroq bunday holatning ehtimolligi 0 ga teng bo‘lishi kerak).
- Ommaviylik (universallik). Algoritm turli boshlang‘ich maʼlumotlar to‘plamlariga qo‘llanishi kerak.
- Natijalilik — algoritm bajarilishining muayyan natija bilan yakunlanishi.
Formal taʼrif
Matematikaning turli nazariy muammolari hamda fizika va texnikaning tez rivojlanishi algoritm tushunchasiga aniq taʼrif berish zaruratini yuzaga keltirdi.
Algoritm tushunchasini aniqlashtirish va tadqiq qilishga dastlabki urinishlarni XX asrning birinchi yarmida Alan Tyuring, Emil Post, Jak Erbran, Kurt Gyodel, A. A. Markov, Alonzo Chyorchamalga oshirgan. Algoritm tushunchasining bir nechta taʼrifi ishlab chiqilgan, ammo keyinchalik ularning barchasi ayni bir tushunchani belgilashi aniqlangan (qarang: Chyorch–Tyuring tezisi)
Rossiyalik matematik, Sovet Ittifoqida strukturaviy tilshunoslik asoschilaridan biri V. A. Uspenskiy algoritm tushunchasi ilk bor Emil Borelning 1912-yilda aniq integral haqidagi maqolasida paydo bo‘lgan deb hisoblagan. Borel u yerda «amalda bajarish mumkin bo‘lgan hisoblashlar» haqida yozgan va «Men ko‘proq yoki kamroq amaliy faoliyatni ataylab chetda qoldiryapman; bu yerda mohiyat shuki, ushbu amallarning har biri ishonchli va bir maʼnoli usul yordamida chekli vaqt ichida bajarilishi mumkin», deb taʼkidlagan.
Tyuring mashinasi

Tyuring mashinasining asosiy g‘oyasi juda oddiy. Tyuring mashinasi — belgilar yozilgan alohida kataklardan iborat lenta bilan ishlaydigan mavhum mashina (avtomat). Unda lenta bo‘ylab harakatlanadigan, kataklarga belgi yozish va ularni o‘qish uchun mo‘ljallangan kallak ham bor. Har bir qadamda mashina kallak ko‘rsatgan katakdagi belgini o‘qiydi va o‘qilgan belgi hamda ichki holatiga qarab keyingi qadamni bajaradi. Bunda mashina o‘z holatini o‘zgartirishi, katakka boshqa belgi yozishi yoki kallakni bir katak o‘ngga yoxud chapga siljitishi mumkin.
Ushbu mashinalarni tadqiq qilish asosida Tyuring tezisi (algoritmlar haqidagi asosiy gipoteza) ilgari surilgan:
Muayyan alifboda berilgan funksiyaning qiymatlarini topish algoritmi faqat va faqat ushbu funksiya Tyuring bo‘yicha hisoblanuvchi, yaʼni Tyuring mashinasida hisoblash mumkin bo‘lgandagina mavjud bo‘ladi.
Bu tezis aksioma, postulat hisoblanadi va uni matematik usullar bilan isbotlab bo‘lmaydi, chunki algoritm aniq matematik tushuncha emas.
Rekursiv funksiyalar
Har bir algoritmga u hisoblaydigan funksiyani mos qo‘yish mumkin. Biroq ixtiyoriy funksiyaga Tyuring mashinasini mos qo‘yish mumkinmi? Agar mumkin bo‘lmasa, qaysi funksiyalar uchun algoritm mavjud? Shu savollar ustidagi tadqiqotlar 1930-yillarda rekursiv funksiyalar nazariyasining yaratilishiga olib kelgan.
Hisoblanuvchi funksiyalar sinfi aksiomalar tizimiga tayangan aksiomatik nazariyani qurishga o‘xshash shaklda ifodalangan. Dastlab hisoblanishi ravshan bo‘lgan eng sodda funksiyalar tanlangan. So‘ng mavjud funksiyalar asosida yangi funksiyalar yaratish qoidalari (operatorlari) belgilangan. Kerakli funksiyalar sinfiga shu operatorlarni eng sodda funksiyalarga qo‘llash orqali hosil qilish mumkin bo‘lgan barcha funksiyalar kiradi.
Hisoblanuvchi funksiyalar nazariyasida Tyuring tezisiga o‘xshash gipoteza ilgari surilgan — Chyorch tezisi:
Sonli funksiya faqat va faqat qisman rekursiv bo‘lgandagina algoritmik hisoblanadi.
Hisoblanuvchi funksiyalar sinfi Tyuring bo‘yicha hisoblanuvchi funksiyalar bilan bir xil ekanini isbotlash ikki bosqichda amalga oshiriladi: avval Tyuring mashinasida eng sodda funksiyalarni hisoblash, keyin operatorlarni qo‘llash natijasida olingan funksiyalarni hisoblash isbotlanadi.
Shunday qilib, norasmiy maʼnoda algoritmni boshlang‘ich maʼlumotlardan (kirish) izlanayotgan natijaga (chiqish), agar u mavjud bo‘lsa, chekli sondagi qadamlarda olib boradigan diskret va deterministik jarayonni belgilovchi aniq ko‘rsatmalar tizimi deb taʼriflash mumkin. Agar izlanayotgan natija mavjud bo‘lmasa, algoritm hech qachon tugamaydi yoki boshi berk ko‘chaga kirib qoladi.
Markovning normal algoritmi (algorifmi)
Markovning normal algoritmi (muallif yozuvida «algorifm») — muayyan alifbo belgilaridan tuzilgan boshlang‘ich so‘zlardan yangi so‘zlar hosil qilish jarayonlarini amalga oshiradigan ketma-ket almashtirishlar tizimi. Tyuring mashinasi kabi, normal algoritmlar hisoblashni bevosita bajarmaydi: ular faqat belgilangan qoidalarga muvofiq harflarni almashtirish orqali so‘zlarni o‘zgartiradi.
Normal hisoblanuvchi deb normal algoritm yordamida amalga oshiriladigan funksiyaga aytiladi. Yaʼni bunday algoritm funksiya uchun ruxsat etilgan maʼlumotlar to‘plamidagi har bir so‘zni uning boshlang‘ich qiymatlariga aylantiradi.
Normal algoritmlar nazariyasining asoschisi A. A. Markov «Markovning normallashtirish prinsipi» deb atalgan gipotezani ilgari surgan:
Muayyan alifboda berilgan funksiyaning qiymatlarini topish algoritmi faqat va faqat funksiya normal hisoblanuvchi bo‘lgandagina mavjud bo‘ladi.
Tyuring va Chyorch tezislari singari Markovning normallashtirish prinsipini ham matematik usullar bilan isbotlab bo‘lmaydi.
Stoxastik algoritmlar
Biroq algoritmning yuqorida keltirilgan formal taʼrifi ayrim hollarda haddan tashqari qatʼiy bo‘lishi mumkin. Baʼzan tasodifiy miqdorlardanfoydalanish zarurati tug‘iladi. Ishlashiga boshlang‘ich maʼlumotlardan tashqari tasodifiy sonlar generatoridanolingan qiymatlar ham taʼsir qiladigan algoritm quyidagicha ataladi: stoxastik (yoki tasodifiylashtirilgan, ingl. randomized algorithm). Stoxastik algoritmlar ko‘pincha deterministik algoritmlardan samaraliroq bo‘ladi, ayrim hollarda esa masalani yechishning yagona usuli hisoblanadi.
Amaliyotda tasodifiy sonlar generatori o‘rniga quyidagidan foydalaniladi: psevdotasodifiy sonlar generatori.
Biroq stoxastik algoritmlarni katta ehtimollik bilan to‘g‘ri natija beradigan usullardan farqlash lozim. Usuldanfarqli ravishda, algoritm uzoq davom etgan ish jarayonidan keyin ham to‘g‘ri natijalar beradi.
Ayrim tadqiqotchilar stoxastik algoritm oldindan maʼlum ehtimollik bilan noto‘g‘ri natija berishi mumkinligini ham tan oladi. Bunday holda stoxastik algoritmlarni ikki turga ajratish mumkin:
- Algoritmlarning Las-Vegas turi har doim to‘g‘ri natija beradi, ammo ularning ishlash vaqti oldindan aniq emas.
- Algoritmlarning Monte-Karlo turiesa oldingi turdan farqli ravishda, maʼlum ehtimollik bilan noto‘g‘ri natija berishi mumkin.
Boshqa formallashtirish usullari
Ayrim masalalarda yuqorida sanalgan formallashtirish usullari yechim topish va tadqiqot o‘tkazishni qiyinlashtirishi mumkin. Bunday to‘siqlarni yengish maqsadida «klassik» sxemalarning o‘zgartirilgan turlari ham, algoritmning yangi modellari ham ishlab chiqilgan. Xususan:
- ko‘p lentali va nodeterministik Tyuring mashinalari;
- registrli mashina va RAM-mashina — zamonaviy kompyuterlar hamda virtual mashinalarning prototipi;
- chekli va uyali avtomatlar.
Algoritm turlari
Algoritmlarning mantiqiy-matematik vosita sifatidagi turlari inson faoliyatining yuqorida ko‘rsatilgan tarkibiy qismlari va yo‘nalishlarini aks ettiradi; algoritmlarning o‘zi esa maqsad, masalaning boshlang‘ich shartlari va uni yechish yo‘liga bog‘liq. Muayyan kirish maʼlumotlarini chiqish maʼlumotlariga aylantiruvchi hisoblash algoritmlari (yuqorida tilga olingan Tyuring va Post mashinalari, RAM-mashinalar, Markovning normal algoritmlari hamda rekursiv funksiyalar aynan shularni formallashtiradi) bilan interaktiv algoritmlar o‘rtasidagi tub farqni alohida taʼkidlash lozim. (Tyuringda ham C-mashina uchraydi; ingl. choice — «tanlash» degan maʼnoni bildiradi. Hisoblash boshlanishidan oldin barcha boshlang‘ich maʼlumotlari berilgan va natijalari hisoblash tugamaguncha olinmaydigan klassik A-mashinadan farqli ravishda, C-mashina tashqi taʼsirni kutadi). Interaktiv algoritmlar boshqariladigan obyekt bilan o‘zaro ishlashga mo‘ljallangan bo‘lib, undan keladigan signallarda aks etgan vaziyatga qarab boshqaruv taʼsirlarini to‘g‘ri shakllantirishi kerak. Baʼzan boshqaruv algoritmi ishning tugashini umuman nazarda tutmaydi (masalan, hodisalarni cheksiz kutish va ularga mos javob qaytarish siklini bajaradi), ammo shunga qaramay to‘liq to‘g‘ri hisoblanadi.
Shuningdek, quyidagi algoritm turlarini ajratish mumkin:
- Mexanik algoritmlaryoki boshqacha aytganda, deterministik, qatʼiy algoritmlar (masalan, mashina, dvigatel va shu kabilarning ishlash algoritmi) — aniq harakatlarni belgilaydi, ularni yagona va ishonchli ketma-ketlikda ko‘rsatadi va shu orqali algoritm ishlab chiqilgan jarayon yoki masala shartlari bajarilganda talab etilgan yoxud izlangan yagona natijani taʼminlaydi.
- Moslashuvchan algoritmlar, masalan, stoxastik, yaʼni ehtimollik va evristik algoritmlar.
- Ehtimollik (stoxastik) algoritmi masalani bir nechta yo‘l yoki usul bilan yechish dasturini beradi; bu yo‘llar natijaga ehtimoliy tarzda erishishga olib keladi.
- Evristik algoritm (yunoncha «evrika» so‘zidan) — qatʼiy asoslashlarsiz turli oqilona mulohazalardan foydalanadigan algoritm.
- Chiziqli algoritm — vaqt bo‘yicha bir-birining ortidan ketma-ket bajariladigan buyruqlar (ko‘rsatmalar) to‘plami.
- Tarmoqlanuvchi algoritm — kamida bitta shartni o‘z ichiga oladigan algoritm; shartni tekshirish natijasida bajarilish bir necha muqobil tarmoqqa ajralishi mumkin.
- Takrorlanuvchi (siklik) algoritm — ayni harakatning (ayni amallarning) ko‘p marta takrorlanishini nazarda tutadigan algoritm. Hisoblash va variantlarni ko‘rib chiqish usullarining aksariyati siklik algoritmlarga keltiriladi. Dastur sikli — ko‘p marta bajarilishi mumkin bo‘lgan buyruqlar ketma-ketligi (seriya, sikl tanasi).
- Yordamchi (bo‘ysunuvchi) algoritm (protsedura) — ilgari ishlab chiqilgan va muayyan masalani algoritmlashtirishda to‘liq ishlatiladigan algoritm. Baʼzan turli maʼlumotlar uchun bir xil buyruqlar ketma-ketligi mavjud bo‘lsa, yozuvni qisqartirish maqsadida ham yordamchi algoritm ajratiladi. Masalani algoritmlashtirishga tayyorlashning barcha bosqichlarida algoritmning strukturaviy tasviridan keng foydalaniladi.
- Strukturaviy blok-sxema, algoritmning graf-sxemasi — algoritmni strelkalar (o‘tish chiziqlari) bilan o‘zaro bog‘langan bloklar — grafik belgilar ko‘rinishida tasvirlash. Har bir blok algoritmning bitta qadamiga mos keladi. Blok ichida tegishli harakat tavsiflanadi. Algoritmning grafik tasviri masalani dasturlashdan oldin keng qo‘llanadi: uning ko‘rgazmaliligi dasturni yozish, xatolarni tuzatish va maʼlumotlarni qayta ishlash jarayonini tushunishni odatda osonlashtiradi. Hatto shunday fikr ham uchraydi: «Tashqi ko‘rinishidan algoritm sxema — ichida nimalar hisoblanishi, mashinaga nimalar kiritilishi va chop etish yoki axborotni ko‘rsatishning boshqa vositalariga nimalar chiqarilishi yozilgan to‘rtburchaklar hamda boshqa belgilardan iborat to‘plamdir».
Algoritmlarni raqamlash
Algoritmlarni raqamlash ularni tadqiq qilish va tahlil etishda muhim o‘rin tutadi. Har qanday algoritmni chekli so‘z ko‘rinishida (muayyan alifbo belgilarining chekli ketma-ketligi sifatida) ifodalash mumkin. Chekli alifbodagi barcha chekli so‘zlar to‘plami esa sanoqlibo‘lgani uchun barcha algoritmlar to‘plami ham sanoqlidir. Bu natural sonlar to‘plami bilan algoritmlar to‘plami o‘rtasida o‘zaro bir qiymatli moslik mavjudligini, yaʼni har bir algoritmga raqam berish mumkinligini anglatadi.
Algoritmlarni raqamlash bir vaqtning o‘zida barcha algoritmik hisoblanuvchi funksiyalarni ham raqamlashdir. Bunda har qanday funksiya cheksiz ko‘p raqamga ega bo‘lishi mumkin.
Raqamlashning mavjudligi algoritmlar bilan sonlar kabi ishlash imkonini beradi. Ayniqsa, boshqa algoritmlar ustida ishlaydigan algoritmlarni tadqiq qilishda raqamlash juda foydali.
Algoritmik yechimi mavjud bo‘lmagan masalalar
Algoritm tushunchasining formallashtirilishi yechimini topish algoritmi mavjud bo‘lmagan masalalarni tadqiq qilish imkonini yaratdi. Keyinchalik bir qator masalalarning yechimini algoritmik hisoblash imkonsizligi isbotlandi. Bu ularni istalgan hisoblash qurilmasida yechish mumkin emasligini anglatadi.
Funksiya hisoblanuvchi (ingl. computable) deb ataladi, agar Tyuring mashinasimavjud bo‘lib, u funksiyaning aniqlanish sohasidagi barcha elementlar uchun uning qiymatini hisoblasa. Agar bunday mashina mavjud bo‘lmasa, funksiya hisoblanmaydigan deb ataladi. Kirish maʼlumotlari to‘plamining faqat bir qismi uchun qiymatni hisoblay oladigan Tyuring mashinalari mavjud bo‘lsa ham, funksiya hisoblanmaydigan deb hisoblanadi.
Agar funksiya ning hisoblash natijasi «rost» yoki «yolg‘on» mantiqiy qiymati (yoki {0, 1} to‘plamidagi qiymat) bo‘lsa, bu holat masala deyiladi; masalaning yechilishi .
funksiyasining hisoblanuvchanligiga bog‘liq. Kirish maʼlumotlarining ruxsat etilgan to‘plamini aniq ko‘rsatish muhim, chunki masala bir to‘plam uchun yechiladigan, boshqasi uchun esa yechilmaydigan bo‘lishi mumkin.
Yechib bo‘lmasligi isbotlangan ilk masalalardan biri — to‘xtash muammosi. U quyidagicha ifodalanadi:
Tyuring mashinasi dasturining tavsifi va muayyan kirish maʼlumotlari berilganda, dastur chekli vaqt ichida to‘xtaydimi yoki cheksiz ishlaydimi, shuni aniqlash talab etiladi.
To‘xtash muammosining yechilmasligini isbotlash muhim, chunki boshqa masalalarni unga keltirish mumkin. Masalan, oddiy to‘xtash muammosini bo‘sh satrda to‘xtash masalasiga (berilgan Tyuring mashinasi bo‘sh satrda ishga tushirilsa, to‘xtaydimi-yo‘qmi, shuni aniqlash masalasiga) keltirib, ikkinchisining ham yechilmasligini isbotlash mumkin.
Algoritmlarni tahlil qilish
Axborot texnologiyalari keng tarqalishi bilan dasturiy nosozliklar xavfi ham oshdi. Algoritmlar va ularning amalga oshirilishidagi xatolardan saqlanish usullaridan biri tizimlarning to‘g‘riligini matematik vositalar yordamida isbotlashdir.
Algoritmlar va ularning amalga oshirilishini tahlil qilishda matematik apparatdan foydalanish formal usullar deb ataladi. Formal usullarda formal spetsifikatsiyalar hamda, odatda, spetsifikatsiyalarning sintaktik tahlili va xususiyatlarini isbotlash uchun vositalar to‘plami qo‘llanadi. Amalga oshirish tafsilotlaridan mavhumlashish tizim xususiyatlarini uning qanday amalga oshirilganidan qatʼi nazar aniqlashga imkon beradi. Bundan tashqari, matematik mulohazalarning aniqligi va bir maʼnoliligi tabiiy tillardagi ko‘p maʼnolilik hamda noaniqlikdan qochishga yordam beradi.
Richard Meys gipotezasiga ko‘ra, «xatolarni tuzatgandan ko‘ra ularning oldini olish yaxshiroq». Xoar gipotezasiga ko‘ra, «dasturlarni isbotlash to‘g‘rilik, hujjatlashtirish va moslik muammolarini hal qiladi». Dasturlar to‘g‘riligini isbotlash ularning barcha kirish maʼlumotlariga nisbatan xususiyatlarini aniqlashga imkon beradi. Shu maqsadda to‘g‘rilik tushunchasi ikki turga ajratilgan:
- Qisman to‘g‘rilik — dastur ishini yakunlagan hollarda to‘g‘ri natija beradi.
- To‘liq to‘g‘rilik — dastur barcha ruxsat etilgan kirish maʼlumotlari uchun ishini tugatadi va to‘g‘ri natija beradi.
To‘g‘rilikni isbotlashda dastur matni kirish va chiqish maʼlumotlari o‘rtasidagi istalgan munosabat spetsifikatsiyasi bilan taqqoslanadi. Xoar uslubidagi isbotlarda spetsifikatsiya dastlabki va yakuniy shartlar deb ataladigan tasdiqlar ko‘rinishida bo‘ladi. Dastur bilan birgalikda ular Xoar uchligi. Bu tasdiqlar quyidagicha yoziladi:
- {P}Q{S}
bu yerda P — Qdasturi ishga tushirilishidan oldin bajarilishi kerak bo‘lgan dastlabki shartlar, S esa dastur yakunlangandan keyin rost bo‘ladigan yakuniy shartlardir.
Formal usullar keng ko‘lamli masalalarda muvaffaqiyatli qo‘llanilgan. Xususan, elektron sxemalarni loyihalash, sunʼiy intellekt, temiryo‘lning avtomatik tizimlari, mikroprotsessorlarnitekshirish, standartlarni spetsifikatsiyalash, shuningdek, dasturlarni spetsifikatsiyalash va verifikatsiya qilishda ishlatilgan.
Ishlash vaqti

Algoritmlarni baholashning keng tarqalgan mezonlaridan biri — ishlash vaqti hamda kirish maʼlumotlari hajmiga qarab bu vaqtning o‘sish tartibidir.
Har bir muayyan masala uchun uning o‘lchami deb ataladigan son belgilanadi. Masalan, matritsalarni ko‘paytirish masalasida bu ko‘paytiriluvchi matritsalarning eng katta o‘lchami, graflarga oid masalalarda esa graf qirralarining soni bo‘lishi mumkin.
Masala o‘lchami ga bog‘liq ravishda algoritm sarflaydigan vaqt uning vaqt murakkabligi deb ataladi ( T(n). Masala o‘lchami oshganda bu funksiyaning xatti-harakati asimptotikasi asimptotik vaqt murakkabligi deb ataladi. Uni belgilash uchun katta O notatsiyasiqo‘llanadi. Masalan, agar algoritm o‘lchami bo‘lgan kirish maʼlumotlarini cn² vaqt ichida qayta ishlasa, bu yerda c — muayyan o‘zgarmasson, unda algoritmning vaqt murakkabligi O(n²).
deb aytiladi. Asimptotik murakkablikning ahamiyati shundaki, u algoritmning muayyan amalga oshirilishiga emas, algoritmning o‘ziga xos xususiyatdir. Algoritmni o‘zgartirmasdan amallarni «optimallashtirish» orqali faqat cko‘paytiruvchi koeffitsiyentini o‘zgartirish mumkin, asimptotikani emas. Odatda algoritm yecha oladigan masalalar o‘lchamini belgilovchi asosiy omil aynan asimptotik murakkablikdir.
Algoritmni ishlab chiqishda ko‘pincha eng yomon holatdagi asimptotik vaqt murakkabligini kamaytirishga harakat qilinadi. Amaliyotda esa «odatda» tez ishlaydigan algoritmning o‘zi yetarli bo‘ladigan holatlar ham uchraydi.
O‘rtacha asimptotik vaqt murakkabligini tahlil qilish usullarini shartli ravishda ikki turga bo‘lish mumkin: analitik va statistik. Analitik usul aniqroq natijalar beradi, ammo amaliyotda qo‘llash murakkab. Statistik usul esa murakkab masalalarni tezroq tahlil qilish imkonini beradi.
Quyidagi jadvalda keng tarqalgan asimptotik murakkabliklar izohlar bilan berilgan.
| Murakkablik | Izoh | Misollar |
|---|---|---|
| O(1) | O‘zgarmas ishlash vaqti masala o‘lchamiga bog‘liq emas | Kutiladigan qidiruv vaqti — xesh-jadval |
| uchunO (log log) | n | Talab qilinadigan vaqtning juda sekin o‘sishi n element orasida interpolatsion qidiruvning kutiladigan ishlash vaqti |
| O(log n) | Logarifmik o‘sish — masala o‘lchami ikki baravar oshsa, ishlash vaqti o‘zgarmas miqdorga ortadi | Darajani hisoblash: xn; ; ikkilik qidiruv ( n elementli massivda) |
| O(n) | Chiziqli o‘sish — masala o‘lchami ikki baravar oshsa, kerakli vaqt ham ikki baravar oshadi | Sonlarni qo‘shish/ayirish ( n xonali); chiziqli qidiruv ( n elementli massivda) |
| O(n log n) | Chiziqli-logarifmik o‘sish — masala o‘lchami ikki baravar oshsa, kerakli vaqt ikki baravardan biroz ko‘proq ortadi | Birlashtirish orqali saralash yoki uyum orqali saralash: n element; taqqoslashli saralashning quyi chegarasi: n element |
| O(n²) | Kvadratik o‘sish — masala o‘lchami ikki baravar oshsa, kerakli vaqt to‘rt baravar ortadi | Oddiy saralash algoritmlari |
| O(n³) | Kubik o‘sish — masala o‘lchami ikki baravar oshsa, kerakli vaqt sakkiz baravar ortadi | Matritsalarni odatiy ko‘paytirish |
| O(cn) | Eksponensial o‘sish — masala o‘lchami 1 taga oshsa, kerakli vaqt cbaravar ortadi; masala o‘lchami ikki baravar oshsa, kerakli vaqt kvadratga ko‘tariladi | Ayrim kommivoyajyor masalalari, barcha variantlarni to‘liq ko‘rib chiqish orqali qidirish algoritmlari |
Boshlang‘ich maʼlumotlar va muayyan natijaning mavjudligi
Algoritm — aniq belgilangan ko‘rsatma bo‘lib, uni boshlang‘ich maʼlumotlarga ketma-ket qo‘llash orqali masalaning yechimini olish mumkin. Har bir algoritm uchun boshlang‘ich maʼlumot sifatida qabul qilinadigan obyektlarning muayyan to‘plami mavjud. Masalan, haqiqiy sonlarni bo‘lish algoritmida bo‘linuvchi istalgan son bo‘lishi mumkin, ammo bo‘luvchi nolga teng bo‘la olmaydi.
Algoritm, odatda, bitta aniq masalani emas, balki masalalar sinfini yechishga xizmat qiladi. Masalan, qo‘shish algoritmi istalgan ikki natural songa tatbiq etiladi. Bunda uning ommaviylik xususiyati, yaʼni ayni algoritmni bir sinfdagi istalgan masalaga qayta-qayta qo‘llash imkoniyati namoyon bo‘ladi.
Algoritmlar va dasturlarni ishlab chiqish uchun algoritmlashtirish — qo‘yilgan amaliy masalalarni yechish algoritmlarini tizimli tuzish jarayoni qo‘llanadi. Algoritmlashtirish dasturlarni ishlab chiqish va EHMda masalalar yechish jarayonining majburiy bosqichi hisoblanadi. Amaliy algoritmlar va dasturlar uchun deterministiklik, natijalilik, ommaviylik hamda qo‘yilgan masalalar yechimlarining to‘g‘riligi ayniqsa muhimdir.
Algoritm — bajaruvchiga maqsadga erishish uchun harakatlar ketma-ketligini bajarishni buyuradigan tushunarli va aniq ko‘rsatma.
Algoritmlarni ifodalash
Algoritmni yozish shakllari:
- so‘zli yoki verbal: tabiiy tilda;
- algoritmik tilda: dasturlash tilida yoki psevdokodda;
- bevosita mashina kodida (EHM protsessori kodi);
- matematik belgilashda (yuqorida keltirilgan variantlarga qarang);
- sxematik shaklda:
- grafik shaklda (masalan, blok-sxemalar va DRAKON sxemalari);
- strukturogrammalar (Nassi–Shneyderman diagrammalari).
Odatda algoritm avval (g‘oya darajasida) so‘zlar bilan tavsiflanadi, ammo uni amalga oshirishga yaqinlashgan sari u tobora formalroq shaklga va bajaruvchi tushunadigan tildagi ifodaga ega bo‘ladi (masalan, mashina kodi).
Algoritmlarning samaradorligi
Algoritm taʼrifida natijaga erishish uchun faqat qadamlar sonining chekli bo‘lishi talab qilinsa-da, amalda juda ko‘p qadam bajarish dasturlarning uzoq ishlashiga olib keladi. Bundan tashqari, odatda boshqa cheklovlar ham mavjud (dastur hajmi, ruxsat etilgan amallar bo‘yicha). Shu bois algoritm murakkabligi (vaqt bo‘yicha, dastur hajmi bo‘yicha, hisoblash murakkabligi va boshqalar kabi tushunchalar kiritiladi.
Har bir masala uchun maqsadga olib boradigan ko‘plab algoritmlar mavjud bo‘lishi mumkin. Ularning samaradorligini oshirish informatikaningvazifalaridan biridir. Shu munosabat bilan 1940-yillardan boshlab anʼanaviy masalalar uchun asimptotik maʼnoda samaraliroq bo‘lgan bir qator algoritmlar ishlab chiqilgan (masalan, tez ko‘paytirish algoritmlari[ingl.], Chudnovskiy algoritmi sonini hisoblash uchun). ).
Misol
Yevklid algoritmi — eng katta umumiy bo‘luvchini (EKUB) hisoblashning samarali usuli. Yunon matematigi Yevklid sharafiga nomlangan; hozirgacha qo‘llanadigan eng qadimgi algoritmlardan biridir.
Yevklidning «Negizlar» asarida (taxminan miloddan avvalgi 300-yil), aniqrog‘i, VII va X kitoblarda tavsiflangan. VII kitobda butun sonlar uchun, X kitobda esa kesmalar uzunliklari uchun algoritm bayon etilgan.
Algoritmning bir nechta varianti mavjud. Quyida psevdokodda yozilgan rekursiv variant keltirilgan:
алг нод(a, b)
нач
если b = 0
возврат a
иначе
возврат нод(b, a mod b)
кон

1599 va 650 sonlarining EKUBi:
| 1-qadam | 1599 = 650*2 + 299 |
| 2-qadam | 650 = 299*2 + 52 |
| 3-qadam | 299 = 52*5 + 39 |
| 4-qadam | 52 = 39*1 + 13 |
| 5-qadam | 39 = 13*3 + 0 |
Adabiyotlar
- Tomas X. Kormen, Charlz I. Leyzerson, Ronald L. Rivest, Klifford Stayn. Algoritmlar: tuzilishi va tahlili = Introduction to Algorithms, Third Edition. — 3-nashr. — M.: «Vilyams», 2013. — 1328 bet. — ISBN 978-5-8459-1794-2.
- Donald Knut. Dasturlash sanʼati = The Art of Computer Programming, vol. 1. Fundamental Algorithms. — 3-nashr. — M.: «Vilyams», 2006. — Jild 1. Asosiy algoritmlar. — B. 720. — ISBN 0-201-89683-4.
- Tomas X. Kormen. Algoritmlar: kirish kursi = Algorithms Unlocked. — M.: «Vilyams», 2014. — 208 bet. — ISBN 978-5-8459-1868-0.
- Igoshin V. I. Matematik mantiq va algoritmlar nazariyasi. — 2-o‘zgartirilmagan nashr. — M.: «Akademiya» nashriyot markazi, 2008. — 448 bet. — ISBN 5-7695-1363-2.
Havolalar
- ««Algoritm» so‘zi: kelib chiqishi va rivojlanishi», V. V. Shilov, «Potensial» jurnali — tarixiy maʼlumotlar manbasi.
- Algoritm haqida (ishlamaydigan havola — tarix). «Krugosvet» ensiklopediyasida