Texnologiyalari va kommunikatsiyalarini rivojlantirish vazirligi muxammad al-xorazmiy nomidagi toshkent

1. Algoritmik yechilmaydigan muammolar

Fizika qonunlarida aytilganidek, doimiy harakatlanuvchi mashinani ixtiro qilish mantiqsiz. Vaqti-vaqti bilan paydo bo'ladigan doimiy harakatlanuvchi mashinalarning ixtirochilari fizikani bilishmaydi yoki uning qonunlarini inkor etishadi. Algoritmlar nazariyasida doimiy harakatlanuvchi mashinaning analogi algoritmik ravishda hal qilinmaydigan muammolar - ularni hal qilish algoritmini ishlab chiqishning mumkin emasligi (va shunga mos ravishda dastur yaratish) isbotlangan muammolardir.

Algoritmlar nazariyasining asosiy vazifasi ma'lum bir masalani yechish algoritmi mavjudligini aniqlashdir. Agar ha bo'lsa, unda quyidagi savol tug'iladi: uni amalda hisoblash texnologiyasining rivojlanish darajasi bilan ishlatish mumkinmi? Ya'ni, kompyuter oqilona vaqt ichida natija olishga qodirmi? Masalan, shaxmat o'yinida faqat cheklangan sonli pozitsiyalar bo'lishi mumkin va shuning uchun faqat turli xil o'yinlarning cheklangan soni. Demak, nazariy jihatdan barcha mumkin bo'lgan o'yinlarni saralash va agar kim to'g'ri o'ynagan bo'lsa g'alaba qozonishini aniqlash mumkin - oq yoki qora. Biroq, variantlarning soni shunchalik ko'pki, zamonaviy kompyuterlar bunday sanashni oqilona vaqt ichida amalga oshira olmaydi.

Algoritmik ravishda hal qilinmaydigan muammolardan biri bu algoritmlarning o'z-o'zini tatbiq etishidir, ya'ni. boshqa dasturlarning xususiyatlarini tahlil qilish uchun dasturlarni qo'llash. Bayonot. Dastur matnidan nima qilishini aniqlaydigan algoritmni tuzish mumkin emas.

Rays teoremasi "Dasturlar haqidagi barcha ahamiyatsiz bayonotlar algoritmik ravishda yechib bo'lmaydigan bo'lib chiqadi".

Ushbu bayonotning pragmatik talqini ancha pessimistik ko'rinadi: dastur matniga ko'ra (shu jumladan, kiritilgan ma'lumotlar), rasmiy usullar uning xulq-atvori va xususiyatlari to'g'risida hech narsani tasdiqlay olmaydi (masalan, bu saralash dasturi).

Aslida, biron bir dasturga (uning matniga) tegishli umumiy algoritmni yaratish mumkin emas. Bunday muammolarning echilayotgani bu echimlarning faqat maxsus holatlar uchun yaroqli ekanligini yoki aniq algoritm shaklida shakllantirish mumkin bo'lmagan norasmiy (masalan, intuitiv) yondashuvlarga asoslanganligini anglatadi. Afsuski (va baxtiga insoniyat nuqtai nazaridan) dasturiy ta'minotni ishlab chiqishning asosiy bosqichlari algoritmik jihatdan erimaydigan muammolarga olib keladi.

"Radio komponentlari sumkasi" usuli. Agar boshqa dasturlarni yaratadigan dasturni ishlab chiqish imkonsiz bo'lsa, unda muammoga boshqa tomondan murojaat qilish mumkin: rasmiy ravishda barcha mumkin bo'lgan dasturlarni yaratish, so'ngra keraksizlardan keraksizlardan, o'ngni noto'g'ri bilan ajratish. Darhaqiqat, ehtimollik nazariyasi nuqtai nazaridan, agar siz tasodifan radio komponentlarning sumkasini silkitib qo'ysangiz, ular rangli televizorga o'ralishi mumkin. Aytgancha, dasturlash tillari nuqtai nazaridan buni amalga oshirish mumkin. Masalan, rasmiy grammatika bu ushbu tilda barcha mumkin bo'lgan sintaktik to'g'ri dasturlarning sintaksisining tavsifidir. Shunday qilib, bunday g'oya nafaqat iqtisodiy nuqtai nazardan, balki nazariy jihatdan ham ishlamaydi: "qo'ylarni echkidan" ajratish uchun dasturiy filtr yaratish mumkin emas, chunki dasturning "foydaliligi" yana uning ahamiyatsiz xususiyatidir.