Algoritmlar nazariyasi — matematikabo‘limi bo‘lib, u algoritmlar ning umumiy xususiyatlari va qonuniyatlari hamda ularni ifodalashning turli formal modellarini o‘rganadi. Algoritmlar nazariyasining vazifalariga masalalarning algoritmik jihatdan yechilmasligini formal isbotlash, asimptotik tahlil algoritmlar murakkabliginibaholash, algoritmlarni murakkablik sinflaribo‘yicha tasniflash, algoritmlar sifatini qiyosiy baholash mezonlarini ishlab chiqish va hokazolar kiradi. matematik mantiq bilan birgalikda algoritmlar nazariyasi hisoblash fanlari, axborot uzatish nazariyasi, informatika, telekommunikatsiya tizimlari va fan-texnikaning boshqa sohalari uchun nazariy asosni tashkil etadi.
Tarixi
Algoritmlar nazariyasining rivojlanishi Kurt Gyodel tomonidan isbotlangan to‘liqsizlik teoremalari bilan boshlanadi. Bu teoremalar arifmetikani o‘z ichiga olgan formal tizimlarga taalluqli bo‘lib, ulardan birinchisi 1931-yildaisbotlangan. Ushbu teoremalar bilan bog‘liq holda ko‘plab matematik muammolarni algoritmik yo‘l bilan hal qilib bo‘lmasligi haqidagi taxmin paydo bo‘ldi (xususan, keltirib chiqarish muammosi predikatlar hisobida) algoritm tushunchasini standartlashtirish zaruratini yuzaga keltirdi. Ushbu tushunchaning dastlabki standartlashtirilgan variantlari 1930-yillarda Alan Tyuring, Emil Post va Alonzo Cherchishlarida ishlab chiqildi. Ular taklif qilgan Tyuring mashinasi, Post mashinasi va lambda-hisoblash o‘zaro ekvivalent ekanligi aniqlandi. Gyodel ishlariga tayangan holda, Stiven Klini kiritgan rekursiv funksiyatushunchasi ham yuqorida sanab o‘tilgan tushunchalarga ekvivalent bo‘lib chiqdi.
Algoritmning standartlashtirilgan eng muvaffaqiyatli variantlaridan biri — Andrey Markov tomonidan kiritilgan normal algoritmtushunchasidir. U Tyuring, Post, Cherch va Klini ishlaridan o‘n yil keyin, bir qator algebraik muammolarning algoritmik jihatdan yechilmasligi isbotlanishi munosabati bilan ishlab chiqilgan.
Keyingi yillarda algoritmlar nazariyasiga katta hissa qo‘shgan olimlar: Donald Knut, Alfred Aho va Jeffri Ullman.
Hisoblash modellari
- Tyuring mashinasi — abstrakt ijrochi (abstrakt hisoblash mashinasi). Uni taklif qilgan Alan Tyuring 1936-yilda formal ta’rif berish uchun algoritmga. Tyuring mashinasi chekli avtomatning kengaytmasi bo‘lib, Cherch–Tyuring tezisiga ko‘ra, o‘tish qoidalarini belgilash orqali bosqichma-bosqich hisoblash jarayonini amalga oshiradigan, har bir hisoblash qadami yetarlicha sodda bo‘lgan boshqa barcha ijrochilarni taqlid qila oladi.
- Lambda-hisoblash — bunda juftlik: λ-ifoda va uning argumenti ko‘rib chiqiladi; hisoblash deb juftlikning birinchi elementini ikkinchisiga qo‘llash, ya’ni applikatsiya qilish tushuniladi. Bu funksiya va uning qo‘llaniladigan obyektini bir-biridan ajratish imkonini beradi. Umumiyroq holatda hisoblash dastlabki λ-ifodadan boshlanadigan zanjirlar hisoblanadi; undan keyin λ-ifodalarning chekli ketma-ketligi keladi va ularning har biri avvalgisidan β-qisqartirish, ya’ni almashtirish.
- Kombinator mantiq — hisoblash talqini λ-hisoblashga o‘xshaydi, biroq muhim farqlari ham bor (masalan, qo‘zg‘almas nuqta kombinatori Y kombinator mantiqda normal shaklga ega, λ-hisoblashda esa ega emas). Kombinator mantiq dastlab paradokslarning tabiatini o‘rganish va matematikaning konseptual jihatdan ravshan asoslarini yaratish uchun ishlab chiqilgan. Bunda o‘zgaruvchi tushunchasi butunlay chiqarib tashlangan, bu esa o‘zgaruvchilarning roli va o‘rnini aniqlashtirishga yordam bergan matematikada.
- Registrli mashinalar, xususan, RAM-mashina — xotiraga ixtiyoriy murojaat qilish imkoniga ega kompyuter modelini ifodalovchi abstrakt hisoblash mashinasi. Algoritmlarni tahlil qilishda aynan shu hisoblash modeli eng ko‘p qo‘llanadi.
Cherch–Tyuring tezisi va algoritmik jihatdan yechilmaydigan muammolar
Alan Tyuring quyidagi taxminni ilgari surgan (u «Cherch–Tyuring tezisi» nomi bilan mashhur): har qanday algoritm — so‘zning intuitiv ma’nosida — unga ekvivalent bo‘lgan Tyuring mashinasiorqali ifodalanishi mumkin. Bunday mashina (va unga ekvivalent boshqa tushunchalar) asosida hisoblash mumkinligi haqidagi tasavvurning aniqlashtirilishi turli ommaviy masalalarning algoritmik jihatdan yechilmasligini qat’iy isbotlash imkonini berdi (bular shartlari ma’lum chegaralarda o‘zgarishi mumkin bo‘lgan masalalar sinfi uchun yagona yechim usulini topish muammolaridir).
Eng sodda misol — algoritmik jihatdan yechilmaydigan ommaviy masala — algoritmning qo‘llanish muammosi, ya’ni to‘xtash muammosibo‘lib, uning mazmuni quyidagicha: dasturi bilan berilgan ixtiyoriy Tyuring mashinasi va uning lentasining ixtiyoriy boshlang‘ich holati uchun mashina chekli sondagi qadamlardan so‘ng ishini yakunlaydimi yoki cheksiz davom ettiradimi, buni aniqlaydigan umumiy usulni topish talab etiladi?
Algoritmlar nazariyasi tarixining dastlabki o‘n yilligida yechimi yo‘q ommaviy masalalar faqat shu nazariyaning o‘zida (jumladan, yuqorida tasvirlangan «qo‘llanish muammosi») va matematik mantiq da (klassik predikatlar hisobidagi«keltirib chiqarish muammosi») aniqlangan edi. Shu sababli algoritmlar nazariyasi matematikaning «chekka» sohasi bo‘lib, uning «algebra» yoki «matematik tahlilVaziyat Andrey Markovning va Emil Postning 1947-yildagi ishlari natijasida o‘zgardi: ular algoritmik jihatdan yechilmasligini isbotlagan masala algebrada chekli hosil qilingan va chekli aniqlangan yarimgruppalar uchun tenglik muammosi, ya’ni (Tyue muammosi). Keyinchalik boshqa ko‘plab «sof matematik» ommaviy masalalarning ham algoritmik jihatdan yechilmasligi aniqlandi. Bu sohadagi eng mashhur natijalardan biri — Yuriy Matyasevich tomonidan isbotlangan Gilbertning o‘ninchi muammosining algoritmik jihatdan yechilmasligi.
Yo‘nalishlar
Algoritmlar nazariyasi, asosan, uch yo‘nalishda rivojlanadi:
- Klassik yo‘nalish:
- Masalalarni formal ifodalash;
- Tushuncha: qaror qabul qilish muammosi;
- Murakkablik darajalarini tasniflash («P», «NP» va boshqalar).
- Tahlil:
- Asimptotik:
- Resurs sarfi va bajarilish vaqtini baholash (xususan, rekursiv algoritmlar uchun);
- Ma’lumotlar hajmi ortishi bilan resurslarga (masalan, bajarilish vaqtiga) ehtiyojning o‘sishini baholash.
- Amaliy yo‘nalish:
- Hisoblash sarfining «aniq» funksiyalarini olish;
- Funksiyalarning interval tahlili ni;
- Sifat mezonlarini izlash;
- Maqbul tanlash metodikasi.
- Asimptotik:
Algoritmlarning hisoblash sarfini tahlil qilish
Tahlilning maqsadi — optimal algoritmni topish. Mezon — hisoblash sarfi (algoritm bajarishi kerak bo‘lgan elementar amallar soni). Hisoblash sarfi funksiyasi hisoblash sarfining kirish ma’lumotlariga bog‘liqligini ifodalaydi.
Kirish ma’lumotlarining quyidagi xususiyatlari hisoblash sarfiga turlicha ta’sir ko‘rsatishi mumkin:
- Hajmi;
- Qiymatlari;
- Kelish tartibi.
Algoritmlarning hisoblash sarfini tahlil qilishning soddalashtirilgan turlaridan biri — katta hajmdagi kirish ma’lumotlari uchun qo‘llanadigan asimptotik tahlil. Hisoblash sarfi funksiyasining ishlatiladigan bahosi — algoritmning «murakkabligi»bo‘lib, u hisoblash sarfi bilan ma’lumotlar hajmi o‘rtasidagi bog‘liqlikni aniqlash imkonini beradi. Algoritmlarning asimptotik tahlilida matematik asimptotik tahlilda qabul qilingan belgilashlardan foydalaniladi. Quyida murakkablikning asosiy baholari keltirilgan.
Algoritm murakkabligi funksiyasining asosiy bahosi (bu yerda n — ma’lumotlar hajmi, ya’ni «kirish uzunligi») quyidagicha ifodalanadi: :
agar g > 0 va n > 0 bo‘lganda musbat с1, с2, n0, quyidagi shart bajarilsa:
agar ; boshqacha aytganda, shunday va , shundayki, yetarlicha katta , — qiymati quyidagi ikki ifoda orasida joylashadi:
- va .
Bu holda yana shunday deyiladiki, funksiyasi uchun asimptotik jihatdan aniq baho hisoblanadi, chunki ta’rifga ko‘ra funksiyasi dan faqat doimiy ko‘paytuvchi bilan farq qiladi (qarang: asimptotik tenglik). Masalan, «heapsort» saralash usuli uchun hisoblash sarfi quyidagicha baholanadi:
- , ya’ni .
Quyidagi tenglikdan kelib chiqadiki, .
funksiya emas, balki funksiyalar to‘plami bo‘lib, ular funksiyasining o‘sishini doimiy ko‘paytuvchi aniqligida tavsiflaydi. bir vaqtning o‘zida funksiyaning o‘sishi uchun yuqori va quyi baholarni beradi. Ko‘pincha bu baholarni alohida ko‘rib chiqish zarur bo‘ladi. Baholash algoritm hisoblash sarfining yuqori asimptotik bahosini ifodalaydi. Quyidagicha deymiz: , agar:
- .
Boshqacha aytganda, yozuv shuni anglatadiki, funksiyalar sinfiga mansub bo‘lib, ular funksiyasidan tezroq o‘smaydi, doimiy ko‘paytuvchi aniqligida.
Quyi baho funksiyaning o‘sishi uchun quyi asimptotik bahoni belgilaydi hamda dan sekinroq o‘smaydigan funksiyalar sinfini belgilaydi, doimiy ko‘paytuvchi aniqligida. , agar:
- .
Masalan, yozuv funksiyalar sinfini anglatadi; bu funksiyalar dan sekinroq o‘smaydi. Bu sinfga darajasi birdan katta bo‘lgan barcha ko‘phadlar, shuningdek asosi birdan katta bo‘lgan barcha darajali funksiyalar kiradi.
Tenglik faqat va faqat shunda bajariladiki, va .
Algoritmlarning asimptotik tahlili nafaqat amaliy, balki nazariy ahamiyatga ham ega. Masalan, elementlarni juft-juft taqqoslashga asoslangan barcha saralash algoritmlari n ta elementni kamida .
Algoritmlarning asimptotik tahlili rivojiga muhim hissa qo‘shgan olimlar: Alfred Aho, Jeffri Ullman, Jon Hopkroft.
Murakkablik sinflari
Klassik nazariya doirasida masalalar murakkabligiga ko‘ra tasniflanadi (P-murakkab, NP-murakkab, eksponensial murakkab va boshqa masalalar):
- «P» sinfidagi masalalarni boshlang‘ich ma’lumotlar hajmiga polinomial bog‘liq vaqt ichida deterministik hisoblash mashinasi yordamida yechish mumkin (masalan, «Tyuring mashinasi»);
- «NP»:
- Yechimi polinomial vaqt ichida nodeterministik hisoblash mashinasi yordamida topilishi mumkin bo‘lgan masalalar (bunday mashinaning keyingi holati avvalgi holati bilan har doim ham bir qiymatli belgilanmaydi). Uning ishini har bir noaniqlikda tarmoqlanadigan jarayon sifatida tasavvur qilish mumkin: tarmoqlardan hech bo‘lmaganda bittasi javobga yetib borsa, masala yechilgan hisoblanadi;
- Bizga qo‘shimcha ravishda berilgan, uzunligi polinomial bo‘lgan ma’lumot yordamida yechimini polinomial vaqt ichida tekshirish mumkin bo‘lgan masalalar. Xususan, «NP» sinfiga yechimini tekshirish mumkin bo‘lgan barcha masalalar kiradi.
«P» sinfi «NP» sinfining tarkibiga kiradi. NP-masalaga klassik misol — «Sayohatchi sotuvchi masalasi».
«P» sinfi «NP» sinfining tarkibiga kirgani sababli, muayyan masalaning «NP» sinfiga mansubligi ko‘pincha ushbu masalani yechish usullari haqidagi hozirgi tasavvurimizni aks ettiradi va yakuniy xulosa hisoblanmaydi. Umuman olganda, biror NP-masala uchun P-yechim topib bo‘lmaydi, deb hisoblashga asos yo‘q. «P» va «NP» sinflarining ehtimoliy tengligi haqidagi savol (har qanday NP-masala uchun P-yechim topish mumkinligi) zamonaviy algoritmlar murakkabligi nazariyasidagi asosiy savollardan biri hisoblanadi; unga hozirgacha javob topilmagan. Bu savolni qo‘yish NP-to‘liq masalalartushunchasini kiritish tufayli mumkin bo‘lgan: har qanday NP-masalani shu masalalarga keltirish mumkin. Agar NP-to‘liq masala uchun P-yechim topilsa, barcha NP-masalalar uchun ham P-yechim topiladi. NP-to‘liq masalaga misol — «Kon’yunktiv normal shakl masalasi».
Algoritmlar murakkabligini o‘rganish ko‘plab klassik matematik masalalarni yechishga yangicha yondashish imkonini berdi. Ayrim masalalar (ko‘phadlar va matritsalarni ko‘paytirish, chiziqli tenglamalar sistemalarini yechish va boshqalar) uchun an’anaviy usullarga qaraganda kamroq resurs talab qiladigan yechimlar topildi.
Algoritmlar nazariyasining matematik tatbiqlari
Algoritmlar nazariyasining ayrim tatbiqlari:
- Ommaviy masalalarni tadqiq etish;
- Tatbiqlar — matematika asoslariga: konstruktiv semantika;
- Tatbiqlar — matematik mantiqqa: formal tillarni tahlil qilish: mantiq va arifmetika;
- Hisoblashli tahlil;
- Raqamlangan tuzilmalar;
- Tatbiqlar — ehtimollar nazariyasiga: tasodifiy ketma-ketlikni aniqlash;
- Tatbiqlar — axborot nazariyasiga: axborot miqdori tushunchasiga algoritmik yondashuv;
- Ayrim masalalarni yechish murakkabligini baholash;
- Algoritmlar nazariyasining algoritmik amaliyotga ta’siri.
Adabiyotlar
- Kormen, T., Leyzerson, Ch., Rivest, R., Shtayn, K. Algoritmlar: tuzish va tahlil qilish = Algoritmlarga kirish (Introduction to Algorithms) / I. V. Krasikov tahriri ostida. — 2-nashr — M.: Vilyams, 2005. — 1296 b. — ISBN 5-8459-0857-4.
- Donald Knut. Dasturlash san’ati, 1-jild. Asosiy algoritmlar = Dasturlash san’ati, 1-jild. Fundamental algoritmlar — 3-nashr — M.: Vilyams, 2006. — 720 b. — ISBN 0-201-89683-4.
- Kolmogorov A. N. Axborot nazariyasi va algoritmlar nazariyasi. — M.: Nauka, 1987. — 304 b.
- Markov A. A., Nagorniy N. M. Algoritmlar nazariyasi. — 2-nashr.. — M.: Fazis, 1996.