P класы

Классикалық теорияда есептер P-күрделі, NP- күрделі, экспоненциальды күрделі және т.б. сияқты күрделілік кластары бойынша жіктеледі.

P класына детерминделген есептеу машинасында (мысалы Тьюринг машинасында) бастапқы деректер көлеміне полиномды түрде тәуелді болатын уақытта шешілетін есептер жатады.

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

P класы мен NP класының эквиваленттілігі (яғни кез келген NP -есептің P –шешімін табу) туралы сұрақ қазіргі кезде алгоритм күрделілігінң теориясының басты сұрағы.

NP –толық есептер NP –есептердің ішкі класы, еректешелігі барлық NP –есептерді қандай да бір тәсілдермен NP –толық есептерге келтіруге болады.

Бұдан шығатын қорытынды: егер NP –толық есептер үшін P –шешімі табылса, онда барлық NP – класының есептері үшін P –шешім табылады.

NP –толық есептің мысалына конънктивті формадағы есеп жатады.

Р класы (полиномды күрделілігі бар кластар)

Есеп полиномды, яғни P класына жатады деп аталады, егер осы есепті O(nk) уақытта шешетін k константа мен алгоритм бар болса, мұндағы п алгоритмнің битпен берілген ұзындығы.

· Көптеген P класының нақты есептерінде константа k < 6;

P=NP проблемасы

P класының табиғи тұйықтығы бар (полиномдардың қосындысы мен көбейтіндісі де полином).

NP класы (полиномды уақытта тексерілетін есептер)

Алғаш Эдмондс жұмыстарында қарастырылып, күрделілілік кластарын енгізген соң, күрделілік теориясының негізгі проблемасы Р = NP айтылды. Мәнісі: Шешімі полиномды күрделілікпен тексерілетін барлық есептерді полиномды уақытта шешуге бола ма? Қазіргі кезде екеуінің тең не тең еместігінің теориялық түрде дәлелдеуі жоқ, тек жорамал бар: Р класы NP класының ішкі жиыны, яғни NP \ Р жиыны бос емес. Бұл жорамал негізінде ТУР-толық есептер класы қарастырылады.

Класс NPC класы (ЖР-толық есептер)

NP-толықтық ұғымын алғаш Кук (Stephen Cook, 1971) пенЛевиным (1973) тәуелсіз түрде енгізді. Ол бір есепті екіншісіне келтіруге негізделді: Егер бірінші есеп пен оны шешетін, нақты проблемаларда дұрыс жауап беретін алгоритм бар болса, ал екінші есептің алгоритмі белгісіз болса, онда екінші есепті бірінші есептің терминдерімен түрлендіріп, бірінші есептің алгоритмімен шешуге болады.

NPC класы мен NP-толық есептері екі шарттың орындалуын талап етеді:

1) есеп NP класына тиесілі болу керек

2) оған NP класының барлық есептері полиномды түрде келтірілуі тиіс.

Теорема NPC класына тиесілі полиномды шешу алгоритмі бар есеп бар болса, онда Р класы NP класымен тең болады, яғни P = NP ([2]).

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

Алгоритм[1], алгорифм (ағылшынша: algorіthm, algorіsmus — Әл-Хорезмидің атынан шыққан) — бастапқы берілген мәліметтермен бір мәнде анықталатын нәтиже алу үшін қай амалды (жұмысты) қандай ретпен орындау қажеттігін белгілейтін есептерді (мәселелерді) шешу (математикалық есеп-қисаптар орындау, техникалық объектілерді жобалау, ғылыми-зерттеу жұмысын жүргізу т.б.) тәсілдерінің дәл сипаттамасы. Алгоритм — математика мен кибернетиканың негізгі ұғымдарының бірі. Агоритмді орындау алгоритмдік процесс деп аталады.

Жалпы Алгоритм деп алдын ала не істеу керек екені дәл көрсетілген есептеу процесін айтады. Есептеу процесі қандай болса да алғашқы мәндерден бастап, сол арқылы толық анықталған қорытынды шыққанша жүргізіледі. Алгоритм ұғымының алғышартына алгоритмдік процеспен қатар мүмкін болатын алғашқы деректер жиынтығының нұсқауы және қорытынды алуға байланысты жүргізілген процестің аяқталғандығын көрсететін ереже енеді. Белгілі бір бастапқы деректердің жиынына қолданылған Алгоритм тиянақты қорытындыға келмеуі немесе есептеу барысы аяқталмай тоқталуы мүмкін. Егер есептеу процесі белгілі бір қорытынды алумен аяқталса (не аяқталмай қалса), онда Алгоритм мүмкін болатын бастапқы деректерге қолданылады (не қолдануға болмайды) деп ұйғарылады.

1. Алгоритмдік теориядағы күрделілік кластары.

Алгоритмнің күрделілігі. Big-O-бағалау алгоритмнің орындалу уақытының өлшемін (runtime) береді. Әдетте алгоритмнің жақсы және нашар жағдайлар үшін есептеу тиімділіктері әртүрлі, сондықтан әр нақты жағдай үшін Big-О мәні есептеледі. Егер алгоритм реті —0(1) болса, оның реті коллекциядағы элементтер санына тәуелсіз болады. Бұл алгоритм тұрақты уақыт бірлігі ішінде орындалады, мысалы егер массив соңын көрсететін индекс сақталса, массив элементіне мән меншіктеу реті 0(1) болады. Алгоритм О(п) сызықты (linear). Оның күрделілігі тізім размеріне пропорционал. Реті log2n болатын алгоритмдер логарифмдік (logarithmic) деп аталады. Мұндай күрделілік тізімдерді бірнеше рет ішкі тізімдерге 1/2, 1/4, 1/8 етіп бөлгенде туындайды. Мысалы бинарлық бұтақтарда іздеу алгоритмдерінің күрделілігі орташа және нашар жағдайлар үшін O(log2n) болады. Реті О(п2) болатын алгоритмдер квадраттық (quadratic) деп аталады. Шағын n үшін ғана практикада қолданылады. п екіге артқан сайын алгоритмнің орындалу уақыты 4-ке артады. Реті О(n3) болатын алгоритмдер өте баяу орындалады, кубтық (cubic) уақытты қажет етеді. п екіге артқан сайын алгоритмнің орындалу уақыты 8 есе артады. Оның мысалына графтарға қолданылатын реті О(п3) болатын Уоршел алгоритмі жатады. Күрделілігі О(2п) тең алгоритмде экспоненциальды күрделілік (exponential complexity) болады. Өте баяу орындалатындықтан өте аз п үшін қолданылады. Төмендегі кестеде аталған алгоритмдердің ретінің бағалауы берілген, аз мәнді п үшін кубтық, экспоненциальдық алгоритмдерді қолдану тиімсіз.

1. Алгоритмдік шешімі болу және болмау ұғымы туралы айт.

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

Теория шешілетін деп аталады егер осындай алгоритм бар болса керісінше жағдайда шешімі жоқ теория деп атайды.

Алгоритм ұғымы және аксиомалық жүйелер антикалық дәуірде белгілі болса (Евклид диаметриясы) шешімі болудың формальды анықтамасы тек XX ғасырдың басында іске асты. Алғашқы зерттеген Гильберт. Ол есептеу және нәтиеженің қалыптастырды ұғымдарды, оның мақсаты (математиканы формальдау болды математиканың кез келген формуласын шынайлыққа тексеру). Гильберт жұмысты басшылыққа ала отырып Гедел алғаш рекурсивті функция класын сипаттайды сол арқылы өзінің толық еместік теориясын дәлелдеді.Кейінен Тьюринг машинасы есептеу сияқты рекурсивті функция эквивалентті формализм енгізілді.Олардың әр қайсысы есептегі функция ұғымының формальды эквиваленті. Бұл эквиваленттік Черчтің тезисінде айтылады. Есептеу алгоритм ұғымы анықталған сон түрлі теорияның шешімі болмауы туралы нәтиежелер алынды. Солардың бірі Новиков теориясы. Ол топтағы сөздердің проблемасы шешімі болмау туралы айтады.

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

Осылайша, Т - теоремасы үшін тібегін құруға болады.Мұндағы - не аксиома, не алдыңғы формуладан алыңған нәтиеже. Шешімі болу ұғымы: әрбір дұрыс құрылған Т- теория үшін шекті қадамнан соң бір мәнді түрде «ияә» (осы сөйлем есептеу шеңберінде қорытылып шығарылады) не «жоқ» (қорытылып шығарылмайды) алгоритмін болатындығын білдіреді.