Жартылай шешімнің болуы

Шекті уақыт ішінде егер расымен солай болса, сөйлемнің шынайы екендігін растайтын болмаса шексіз жұмыс істейтін алгоритм болатындығын білдіреді. Мысалы математиканың көп есебі барлық сан емес, санның нақты түріне ғана қолданылады.

Есептелу теориясында тоқтату проблемасы бұл шешімі болу проблемасы, оның мәнісі: алгоритм мен оның бастапқы деректері берілсін, осы деректермен алгоритмнің жұмысы аяқтала ма, жоқ тоқтаусыз жұмыс істей бере ме екендігін анықтау қажет.

1936 жылы Алан Тьюринг кез келген мүмкін болатын кірістік деректер үшін тоқтап қалудың проблемасын шешудің жалпы алгоритмі болмайтындығын дәлелдеді. Тоқтап қалу проблемасы Тьюринг машинасында шешілмейді.

Шешімі болмауды дәлелдеудің 2 әдісі бар: тікелей әдіс және жанама әдіс.

Алгоритмдер теориясында алынған нәтижелер екі аспектіде: теориялық және практикалық аспектілерде қолданылады. Теориялық аспект: Есептің алгоритмдік шешімі болатындығын немесе оны шешудің нақты алгоритмі болмайтындығына есепті зерттеу нәтижесінде алгоритмдер теориясының жауап беру мүмкіндігі теориялық аспектіге жатады. Алгоритмдік шешімі болмайтын есептер Тьюринг машинасын тоқтату есебіне келтіріледі. Ал алгоритмдік шешімі болатын есептер үшін олардың NP-толық есептер класына тиесілі ме екендігі анықталады. Егер тиесілі болса, онда бастапқы деректері үлкен болатын есептердің нақты шешімін алу үшін қанша уақыт кететінін анықтауға немесе оны шешудің жылдам нақты алгоритмі болмайтындығын айтуға мүмкіндік береді. Практикалық аспект: алгоритмдер теориясының, әсіресе асимптотикалық және практикалық талдаудың әдістері мен әдістемелері келесі мүмкіндіктерді береді: Берілген есепті шешуге арналған алгоритмдер жиынынан жасалатын программалық жүйедегі олардың ерекшелігін ескеретін тиімді алгоритмді таңдауға мүмкіндік береді. Күрделілік функциясы арқылы күрделі есептерді шешудің уақыттық бағалауларын алады. Белгілі уақыт ішінде қандай да бір есептің шешуі болмайтындығына шынайы баға беріледі. Ақпаратты өңдеу саласындаың маңызды деген есептерін шешудің тиімді алгоримтмдерін құру мен жетілдіру. Мысалы: алгоритмді жүзеге асыратын программаның орындалу уақытына немесе пайдаланатын минималды жад көлеміне шектеулер қойылғанда түрлі алгоритмдерден таңдау жасалынады; қиындық функциясы арқылы күрделі есептерді шешу уақыты анықталады; берілген уақыт ішінде есепті шешу мүмкін болмайтындығы шынайы бағаланады. Бұл қазіргі кезде криптографиялық әдістер үшін, ақпаратты өңдеу саласында практикалық жағынан маңызды есептерді шешудің тиімді алгоритмдерін жасау мен жетілдіру үшін аса сұранысқа ие болып отыр.(С инета)

1. Алгоритмнің бірігуі дегеніміз не?

Компьютердің логикалық элементтері дегеніміз – ЖƏНЕ, НЕМЕСЕ, ЕМЕС электрондық схемаларын айтамыз.

ЖӘНЕ құрамындағы бұл жалғауды әрқашан құраушы пікірлердің бәрін ақиқат деп ұйғарады. ЖƏНЕ элементінің көмегімен қарапайым екі Х1 мен Х2 айтылымдарының бір құрамдасқа бірігуі логикалық көбейту немесе конъюнкция (латынша conjunction-біріктіру), ал операцияның нəтижесі – логикалық көбейтінді деп аталады.

Белгіленуі: Х1∧Х2, Х1&Х2, Х1⋅Х2, Х1 AND Х2, Х1 жəне Х2

Математикада НЕМЕСЕ жалғаулары бар құрамды пікірді құрайтындардың кемінде біреуі ақиқат болса, ол ақиқат деп есептеледі. Ал құрмында жалған болса ол жалған деп есептеледі. Біріктіруші мағынада қолданылатын НЕМЕСЕ элементінің көмегімен қарапайым Х1 жəне Х2 айтылымдарының бір құрамдасқа бірігуі логикалық қосу немесе дизъюнкция (латынша disjunction-бөлу), ал операцияның нəтижесі – логикалық қосынды деп аталады. Белгіленуі: Х1∨Х2, Х1\Х2, Х1+Х2, Х1 OR Х2, Х1 немесе Х2.

ЕМЕС бастапқы пайымдау жалған болса, онда терістеу ақиқат ж\е керісінше егер бастапқы пайымдау ақиөат болса онда терістеу жалған.

1. Алгоритмнің зерттеу салалары

Алгоритммен келесі зерттеу салалары байланысты:

1. Алгоритмді талдау. Бұл саланың зерттеу пәніне алгоритм жұмысының сипаттамаларын анықтау жатады. Мысалы: әдетте алгоритмнің жылдам орындалуы талап етіледі (метод оптимизация)

2. Алгоритмдер теориясы. Бұл салада берілген шамаларды есептеудің тиімді алгоритмдердің болуы/болмау мәселелері қарастырылады.

Алгоритмдерді құру. Бұл сала алгоритмдерді жазуда қолданылатын стандартты әдістер мен тәсілдерді қарастырады. Мыс: Блок-схема.

Алгоритмдер теориясы алгоритмдердің жалпы қасиеттері мен заңдылықтарын, оларды көрсетудің түрлі формальды модельдерін зерттейтін ғылым саласы. Алгоритм ұғымын формальдау арқылы алгоритмдерді тиімділігі бойынша салыстыруға, эквиваленттілігін тексеруге, қолдану салаларын анықтауға болады.

Алгоритмдер теориясының міндеттеріне есептің алгоритмдік шешімі болмауын формальды түрде дәлелдеу, алгоритм күрделілігін асимптотикалық талдау, күрделілік кластарына сәйкес алгоритмдерді жіктеу, алгоритмдер сапасын салыстырмалы түрде бағалаудың өлшемдерін жасау және т.б. жатады.

1930-жылдары жасалған алгоритмдердің формальды модельдері (Пост, Тьюринг, Черч), 1950- жылдары жасалған Колмогоров пен Марковтың модельдері тең, өйткені олар бір біріне мына мағынада эквивалентті: бір модельде шешімі табылған проблемалардың кез келген класы, екінші модельде де шешімі болады.

Қазіргі кезде алгоритмдер теориясының негізінде алынған практикалық ұсыныстар программалық жүйелерді жасау мен жобалау саласында кеңінен қолданылуда.

1. Алгоритмнің күрделілігі дегеніміз не?

Күрделілілік тұрғысынан алгоритмдердің екі үлкен класы бар - қайталауы бар алгоритмдер және рекурсивті алгоритмдер.Бір есепті көптеген алгоритммен шешуге болады. Олардың әрқайсысының жұмысының тиімділігі әртүрлі сипаттаулармен сипатталады. Алгоритмді талдамас бұрын ең алдымен берілген алгоритм есепті дұрыс шешетінін дәлелдеуіміз керек. Егер есепті дұрыс шешпесе тиімділік мәселесінің мәні жоқ. Егер алгоритм қойылған есепті шешсе, оның қаншалықты тиімді екенін қарастыруымыз керек. Сондықтан оның тиімділігінін анықтау үшін алгоритмдерді талдауымыз қажет.

Қайталау алгоритмінің негізінде шартты өрнектер мен цикл жатыр; мұндай алгоритмдерді талдауда циклдын ішінде қолданылатын операция саны мен цикл итерациясының санын бағалау керек. Рекурсивтік алгоритмдер үлкен есепті фрагменттерге бөледі және әрбір фрагменттерді жеке қолдануға мүмкінлік береді. Осындай алгоритмдерді кейде «бөліп алда біле» алгоритмі деп айтайды және оларды қолдану өте тиімді болуы мүмкін. Үлкен есептердікішіге бөлу жолымен шешу үрдісінде үлкен емес, қарапайым және түсінікті алгоритм құрылады. Рекурсивті алгоритмді талдауда есепті бөлімге бөлуге қажетті операцияның санын санау, ірбңр бөлімдегі алгоритмнің орындалуы және есепті толық шешудегі әрбір бөлімнің нәтижесін біріктіру керек. Осы ақпараттарды және неше бөлік екенінің саны, олардың өлшемінен алгоритмнің күрделілігінің рекуррентік қатынасын шығарамыз.