АЛГОРИТМДЕР ТЕОРИЯСЫН ИНТЕЛЛЕКТУАЛДЫ ЖҮЙЕЛЕРДЕ ҚОЛДАНЫЛУЫНА ҚАТЫСТЫ ТЕРМИНДЕРГЕ ШОЛУ

Пән: Информатика, Программалау, Мәліметтер қоры
Жұмыс түрі: Материал
Тегін: Антиплагиат
Көлемі: 7 бет
Таңдаулыға:

Секция
МАТЕМАТИКА ЖӘНЕ ИНФОРМАТИКА

ӘОЖ 512.54.

АЛГОРИТМДЕР ТЕОРИЯСЫН ИНТЕЛЛЕКТУАЛДЫ ЖҮЙЕЛЕРДЕ ҚОЛДАНЫЛУЫНА ҚАТЫСТЫ ТЕРМИНДЕРГЕ ШОЛУ

Берілген мақалада студенттердің "Математика" пәні бойынша білім деңгейін, сонымен қоса әдістемелік жабдықтау мен зертханалық сабақтарды жақсартуда компьютерлік модельдеудің негізі, оның түрлері және компьютерлік модельдеуді алгоритмдерді құрудың негізгі кезеңдері қарастырылады.
Түйінді сөздер: алгоритм, асимптотикалық талдау, модель, компьютерлік модель, алгоритмдер классификациясы, адекваттылық, алгоритм
Қазіргі кезде алгоритмдер теориясының негізінде алынған практикалық ұсыныстар программалық жүйелерді жасау мен жобалау саласында кеңінен қолданылуда. Алгоритмдер теориясы алгоритмдердің жалпы қасиеттері мен заңдылықтарын, оларды көрсетудің түрлі формальды модельдерін зерттейтін ғылым саласы. Алгоритм ұғымын формальдау арқылы алгоритмдерді тиімділігі бойынша салыстыруға, эквиваленттілігін тексеруге, қолдану салаларын анықтауға болады.
Алгоритмдер теориясының міндеттеріне есептің алгоритмдік шешімі болмауын формальды түрде дәлелдеу, алгоритм күрделілігін асимптотикалық талдау, күрделілік кластарына сәйкес алгоритмдерді жіктеу, алгоритмдер сапасын салыстырмалы түрде бағалаудың өлшемдерін жасау және т.б. жатады. 1930-жылдары жасалған алгоритмдердің формальды модельдері (Пост, Тьюринг, Черч), 1950- жылдары жасалған Колмогоров пен Марковтың модельдері тең , өйткені олар бір біріне мына мағынада эквивалентті: бір модельде шешімі табылған проблемалардың кез келген класы, екінші модельде де шешімі болады.
Қазіргі кезде алгоритмдер теориясы негізі 3 бағытта дамып келеді: Алгоритмнің классикалық теориясы - есептерді формальды тілдер терминдерімен беру (формулировка задач) проблемасын зерттейді. Есептерді күрделілік кластары бойынша (P,NP, т.б) классификациясын жасайды, есептердің шешімін табу ұғымын енгізілді.
Алгоритмдерді асимтотикалық талдау теориясы. Алгоритмнің, соның ішінде рекурсивті алгоритмдердің, орындалу уақытының немесе ресурстарының асимтотикалық бағасын алудың тәсілін қарастырады. Асимтотикалық талдау енгізілетін деректер көлемінің өсуіне байланысты алгоритмдердің ресурстарға қажеттілігін бағалауға мүмкіндік береді. Есептеу алгоритмдерін практикалық талдау теориясы тиімді алгоритмдерді таңдау әдістемесін жасау, алгоритмдердің сапасын тексерудің практикалық өлшемдерін іздеу, функцияларды интервалдық талдау, күрделіліктің нақты функцияларын алу және т.б. сияқтарды есептерді шешумен шұғылданады.
Қазіргі заманғы алгоритмдер теориясының даму бағыттары мен шешетін негізгі міндеттері:
Алгоритм ұғымын формальдау және формальды алгоритмдік жүйелерді (есептеулер модельдерін) зерттеу;
Есептің алгоритмдік шешімі болмайтынын дәлелдеу;
Алгоритмдердің дұрыстығы мен эквиваленттілігін формальды түрде дәлелдеу;
Есептерді классификациялау, күрделілігі бар кластарды анықтау және зерттеу;
Есептің күрделілігінің теориялық төменгі бағасын дәлелдеу;
Тиімді алгоритмдерді құру әдістерін табу;
Итерациялық алгоритмдердің күрделілігін асимптотикалық талдау;
Рекурсивті алгоритмдерді зерттеу және талдау;
Алгоритмдердің қиындығының нақты функцияларын табу;
Алгоритмдердің классификациясын жасау;
Есептер мен алгоримдердің сыйымдылығы бойынша күрделілігін (жад ресурстары бойынша) зерттеу;
Алгоритмдердің ресурстық тиімділігін салыстырмалы түрде бағалаудың критерийлерін және оларды салыстырмалы талдаудың әдістерін жасау.
Алгоритмдер теориясында алынған нәтижелер екі аспектіде: теориялық және практикалық аспектілерде қолданылады.
Теориялық аспект: Есептің алгоритмдік шешімі болатындығын немесе оны шешудің нақты алгоритмі болмайтындығына есепті зерттеу нәтижесінде алгоритмдер теориясының жауап беру мүмкіндігі теориялық аспектіге жатады.
Алгоритмдік шешімі болмайтын есептер Тьюринг машинасын тоқтату есебіне келтіріледі. Ал алгоритмдік шешімі болатын есептер үшін олардың NP-толық есептер класына тиесілі ме екендігі анықталады. Егер тиесілі болса, онда бастапқы деректері үлкен болатын есептердің нақты шешімін алу үшін қанша уақыт кететінін анықтауға немесе оны шешудің жылдам нақты алгоритмі болмайтындығын айтуға мүмкіндік береді.
Практикалық аспект: алгоритмдер теориясының, әсіресе асимптотикалық және практикалық талдаудың әдістері мен әдістемелері келесі мүмкіндіктерді береді:
Берілген есепті шешуге арналған алгоритмдер жиынынан жасалатын программалық жүйедегі олардың ерекшелігін ескеретін тиімді алгоритмді таңдауға мүмкіндік береді.
Күрделілік функциясы арқылы күрделі есептерді шешудің уақыттық бағалауларын алады. Белгілі уақыт ішінде қандай да бір есептің шешуі болмайтындығына шынайы баға беріледі [1].
Ақпаратты өңдеу саласындаың маңызды деген есептерін шешудің тиімді алгоримтмдерін құру мен жетілдіру.Мысалы: алгоритмді жүзеге асыратын программаның орындалу уақытына немесе пайдаланатын минималды жад көлеміне шектеулер қойылғанда түрлі алгоритмдерден таңдау жасалынады; қиындық функциясы арқылы күрделі есептерді шешу уақыты анықталады; берілген уақыт ішінде есепті шешу мүмкін болмайтындығы шынайы бағаланады. Бұл қазіргі кезде криптографиялық әдістер үшін, ақпаратты өңдеу саласында практикалық жағынан маңызды есептерді шешудің тиімді алгоритмдерін жасау мен жетілдіру үшін аса сұранысқа ие болып отыр.
Алгоритм - өңдеудің қарапайым орындалатын тактілерін қолдануға негізделген қандай да бір әдістің нақты және шекті (ақырлы) сипаттамасы. Алгоритм - мүмкін болатын бастапқы деректер класына ортақ есептің шешімін табуға арналған нақты анықталған және орындалатын қарапайым операциялардың ақырлы тізбегінен тұратын, қандай да бір тілде жазылған ақырлы нұсқаулар.
Алгоритм ұғымының бірыңғай анықтамасы жоқ. Көптеген анықтамалардың ішінде неғұрлым сәтті берілгені орыс ғалымдары А.Н.Колмогоров пен А.А.Марковтың анықтамалары:
Анықтама 1. (Колмогоров): Алгоритм - нақты ережелермен қатаң түрде орындалатын, қандай да бір қадамдардан соң қойылған есептің шешіміне әкелетін есептеулердің кез келген жүйесі
Анықтама 2. (Марков): Алгоритм - өзгертілетін бастапқы деректерден ізделінді нәтижеге әкелетін есептеу процесін анықтайтын нақты ереже.
Бұл анықтамалардан алгоритмге қойылатын келесі ортақ талаптарды атап өтейік:
алгоритм қарапайым орындалатын саны шектеулі ережелерден тұруы тиіс, яғни жазбалардың шектеулі болуы талабын қанағаттандыруы тиіс;
алгоритм шектеулі қадамнан соң есепті шешуі тиіс, яғни әрекеттердің шектеулі болу талабын қанағаттандыруы тиіс;
алгоритм барлық мүмкін болатын бастапқы деректер үшін біреу ғана болуы керек, яғни әмбебаптық талабын қанағаттандыруы тиіс;
алгоритм қойылған есептің дұрыс шешімін табуы керек, яғни дұрыс болу талабын қанағаттандыруы тиіс.
Бұл анықтамаларда әрекетті орындаушы көрсетілуі тиіс және ол орындайтын қарапайым операцияларға не жататыны нақтылануы тиіс. Алгоритмді әртүрлі формада бейнелеуге , яғни беруге болады. Кейде әрекеттер ретін графикалық түрде көрсету түсінікті болады, ал оны сөзбен сипаттау қиынға түседі. Сондықтан алгоритмнің нақты формальды анықтамасы туралы ұғым арнайы математикалық конструкцияларды - формальды алгоритмдік жүйелер немесе Пост машинасы, Тьюринг машинасы, Черчтің рекурсивті-есептелінетін функциялары сияқты есептеулер модельдерін енгізумен, бұл формализмнің эквиваленттілігі туралы тезистің айтылуымен және алгоритм ұғымымен тікелей байланысты болды.
Z есебінің бастапқы деректерінің жиыны -- DZ, aл R -- мүмкін болатын нәтижелер жиыны болсын, онда алгоритм DZ R бейнелеуін іске асырады деп айтады. Егер алгоритм тек кейбір dDZ үшін ғана дұрыс нәтиже берсе, онда алгоритм жеке жағдайдың алгоритмі деп аталады. Егер алгоритм барлық dDZ үшін дұрыс нәтиже берсе, онда алгоритм толық алгоритм деп аталады.
Қойылған есептің шешімін арифметикалық амалдарды орындауға келтіретін алгоритмдер сандық алгоритмдер деп аталады. Д.Кнут Искусство программирования. Основные алгоритмы атты кітапта алгоритмнің бес маңызды қасиетін көрсеткен:
1) Ақырлы болуы - алгоритмнің ақырлы қадамынан соң аяқталуы тиіс;
2) Анықтылығы - алгоритмнің әр бір қадамы нақты анықталуы керек.
3) Енгізілетін деректердің болуы - алгоритм жұмысының басына дейін берілетін кірістік деректер болады немесе олар орындалу барысында динамикалық түрде анықталуы мүмкін
4) Шығыстық деректердің болуы - алгоритмде кірістік деректермен белгілі бір байланысы бар немесе бірнеше деректер болады.
5) Тиімділік [2].
Алгоритмдер классификациясы. Күрделілілік тұрғысынан алгоритмдердің екі үлкен класы бар қайталауы бар алгоритмдер және рекурсивті алгоритмдер. Бір есепті көптеген алгоритммен шешуге болады. Олардың әрқайсысының жұмысының тиімділігі әртүрлі сипаттаулармен сипатталады. Алгоритмді талдамас бұрын ең алдымен берілген алгоритм есепті дұрыс шешетінін дәлелдеуіміз керек. Егер есепті дұрыс шешпесе тиімділік мәселесінің мәні жоқ. Егер алгоритм қойылған есепті шешсе, оның қаншалықты тиімді екенін қарастыруымыз керек. Сондықтан оның тиімділігінін анықтау үшін алгоритмдерді талдауымыз қажет. Қайталау алгоритмінің негізінде шартты өрнектер мен цикл жатыр; мұндай алгоритмдерді талдауда циклдын ішінде қолданылатын операция саны мен цикл итерациясының санын бағалау керек.
Рекурсивтік алгоритмдер үлкен есепті фрагменттерге бөледі және әрбір фрагменттерді жеке қолдануға мүмкінлік береді. Осындай алгоритмдерді кейде бөліп алда біле алгоритмі деп айтайды және оларды қолдану өте тиімді болуы мүмкін. Үлкен есептерді ... жалғасы

Сіз бұл жұмысты біздің қосымшамыз арқылы толығымен тегін көре аласыз.