Полиномдық және экспоненциалдық күрделілік кластарына шолу

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

P=NP проблемасы), NP толықтық, есептердің эквиваленттілігін дәлелдеу

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

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

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

NP класының тағы бір анықтамасы: NP класына есептің шешімін қосымша ақпарат арқылы полиномды уақытта тексеруге болатын есептер жатады, яғни полиномды уақытта шешімін тексеруге болатын барлық есептер жатады. P класы NP класының құрамына кіреді.

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-толық есептері екі шарттың орындалуын талап етеді:

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

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

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

Полиномиалды есептерге мысал. Қарапайым идея бояу туралы есеп үшін ықтимал алгоритмді алуды мүмкін еткізеді. Ол одан да қарапайым есеп үшін полиномиалды шешімді қолданады. Кездейсоқ түрде әрбір төбе үшін оны бояй алатын бірнеше түстер белгілейік. Әрбір төбе үшін сәйкес келетін жұбын табу 2 / 3 құрайды, ал онда осындай «алдын ала бояуды» табу ықтималдылығы әрбір төбе үшін (2 / 3) болып келеді. Ал егер әрбір төбе үшін екі түстің бірін таңдау қажет болса, онда полиномиалды алгоритм қолдануға болады.

Сөйтіп, бірнеше рет осындай операцияны қайталау жұмыс уақытын O(1.5")-мен бағалаудың ықтималды алгоритмін береді. Сонымен бірге қате,тек теріс нәтиже орын алуы мүмкін.

1. Көпіршікті сұрыптау

)Көпіршікті сұрыптау – қарапайым сұрыптау алгоритмі. Көпіршікті болу себебі – судың бетіне көпіршіктер шығатындай, бұл алгоритмнің де «жеңіл» элементтері массивтің «бетіне» шығып сұрыпталады. Алгоритм идеясы:

Сұрыптау қадамдары массив бойымен төменнен жоғары қарай өтуден тұрады. Жолда жұп элементтер бір-бірімен салыстырылады. Егер жұптың элементтері қате ретпен орналасса, олардың орын ауыстырамыз.

Жақсы жақтары:

- Орындалу алгоритмі өте жеңіл

Жаман жақтары:

- Үлкен емес массивтерде ғана тиімді;

- Алгоритмнің күрделілігі – O(n^2)

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

1. Кук теориясы

Кук теоремасы бойынша: не барлық NP-тілдер Р класын тиесілі не олардың ешқайсысы тиесілі емес. Бұдан туындайтын Куктың проблемасы Р мен NP кластары бірдей ме, яғни тең бе (қысқаша P = NP?).

Күрделіліктің төменгі бағасы проблемасын шешуге NP-толықтық теориясы үлес қосуы мүмкін. осы теорияның артықшылығына жататындар:

- NP-толықтық теория күрделі болады-ау деген тілдердің аса көп түрлерін ұсынады (барлық NP-толық тілдер) и сол арқылы күрделі тілдердің үміткелерінің дефицитін болдырмайды.

- Полиномдық келтіру ұғымы мен Кук теоремасын дәлелдеу кезінде дамыған техника көп тілдерге (NP класына жатпайтын) арналған күрделіліктің аса жоғары төменгі бағалауын алуға мүмкіндік берді

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

- NP-толықтық теориясы күрделіліктің төменгі бағалауының проблемасының қиындығын тағы да көрсетті және бұл проблемаға қызығушылық шақырды.

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

Кук теоремасы:

«NP классы құрамында NP-толық тілдер бар. Бұл тіл диагональды процедурамен жасалмайды, ал NP- толық тіл ретінде нақты тілді —ВЫПОЛНИМОСТЬ КНФ қолдану ұсынылады. Бұл тіл орындалатын конъюнктивті нормальды формалардан тұрады. NP класына жататын кез келген тіл полиномды түрде ВЫПОЛНИМОСТЬ КНФ тіліне келтіріледі»

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

- сұқбат немесе файл арқылы бастапқы деректерді енгізу;

- бастапқы деректердің дұрыстығын тексеру;

- қойылған есепті шешу;

- алынған нәтижелерді көрсету (шығару).

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

Формальды жоғары деңгейлі процедуралық тілдерде келесі «элементар» операциялар бар деп есептейміз:

1) қарапайым меншіктеу: а <— 6;

2) бірөлшемді индексация: а[n]: (адрес(о) + n • элемент ұзындығы);

3) арифметикалық операциялар: {*, /, -, +};

4) салыстыру операциялары: а{ <, >, =, <, > }Ь;

5) логикалық операциялар: (/1) {or, and, not} (12);

6) күрделі деректер типтеріндегі адрестеу операциялары: (namel.name2).

Элементар операцияларға өту командасы, цикл командасы кірмейді, бұлар құрылымдық программалау талаптарына сай келу керек, әрі олар элементар операциялардан тұрады

31. Күрделіліктің негізгі бағалауларының түрлері қандай?

Алгоритмнің күрделілігінің f(n) функциясының негізгі бағалауы Q бағасы. Мұндағы n - деректер көлемінің шамасы немесе кірістің ұзындығын білдіреді.

Алгоритмнің күрделілігінің негізгі бағасы f(n)= Q (g(n))

егер g > 0, n > 0 болғанда мынандай оң с₁, с₂, n₀, болса: с₁ g(n) <= f(n) <= с₂ g(n)

n > n₀ болғанда мынандай с₁ мен c₂ табуға болады, үлкен n үшін f(n) мәні мына с₁ g(n) және с₂ g(n) екеуінің аралығында болады.

Бұл жағдайда g(n) функциясын f(n) функциясының асимтотикалық нақты бағасы деп атайды.

Мысалы heapsort сұрыптау әдісі үшін күрделілік бағасы f(n)= Q (nlogn) болады, яғни g (n) = n log n.

f(n)= Q (g(n)) теңдіктен g (n) = Q (f(n)) туындайды.

Маңыздысы: Q (g(n)) функция емес, функциялардың жиыны, ол f(n)-нің өсуін тұрақты көбейткішке дейін дәлдікпен көрсетеді.

Q бағасы бір мезгілде функция өсімінің жоғары және төменгі бағаны береді. Көбінесе бұл бағаларды жеке қарастыруға тура келеді.

О бағасы алгоритм қиындығының, яғни f(n) функциясының өсуінің жоғарғы асимптотикалық бағасын береді. f(n)= О (g(n)) болады, егер

орындалса.

Басқаша айтқанда тұрақты көбейткішке дейін дәлдікпен g(n) функциясына қарағанда f(n) функциясы жылдам өспейтін функциялар класын анықтайды.

W бағасы алгоритм қиындығының, яғни f(n) функциясының өсуінің төменгі асимптотикалық бағасын береді және тұрақты көбейткішке дейін дәлдікпен g(n) функциясына қарағанда f(n) функциясы баяу өспейтін функциялар класын анықтайды.

f(n)= W (g(n)) болады, егер

Егер f(n)= О (g(n)) және f(n)= W (g(n)) орындалса ғана, f(n)= Q (g(n)) теңдігі орындалады

Алгоритмдерді асимптотикалық талдауды практикалық та, теориялық та маңызы зор. Мысалы,элементтерді жұптап сұрыптауға негізделген

1. Кірістіру арқылы сұрыптау

Кірістірумен сұрыптау – жоғары есептеу күрделікті O(n^2) қарапайым сұрыптау алгоритмі. Алгоритмнің идеясы:

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

Жақсы жақтары:

- Он элементтен тұратын массивтерде ең тиімді;

- Жартылай сұрыпталған массивтерде тиімді;

- Сұрыпталған элементтердің ретін ауыстырмайтын орнықты сұрыптау алгоритмі

Жаман жақтары:

- Өте жоғары есептеу күрделікті O(n^2) алгоритм

1. Кірістіру арқылы сұрыптау мен Көпіршік арқылы сұрыптауға талдау жаса. Қай сұрыптау тиімді.? ТОЖЕ САМОЕ ЧТО И 32 ТИМДИ КИРИСТИРУ
2. Кірістіру арқылы сұрыптау мен Таңдау арқылы сұрыптауға талдау жаса. Қай сұрыптау тиімді?ТОЖЕ САМОЕ ЧТО И 32 ТАНДАУ ТИМДИ

35. Қазіргі заманғы алгоритмдер теориясының даму бағыттары мен шешетін негізгі міндеттері.

Қазіргі кезде алгоритмдер теориясы негізі 3 бағытта дамып келеді:

Алгоритмнің классикалық теориясы – есептерді формальды тілдер терминдерімен беру (формулировка задач) проблемасын зерттеді. Есептерді күрделілік кластары бойынша (P,NP, т.б) классификациясын жасайды, есептердің шешімін табу ұғымын енгізді. Алгоритмдерді асимтотикалық талдау теориясы. Алгоритмнің, соның ішінде рекурсивті алгоритмдердің, орындалуының уақытының немесе ресурстарының асимтотикалық бағасын алудың тәсілін қарастырады.

Асимтотикалық талдау енгізілетін деректер көлемінің өсуіне байланысты алгоритмдердің ресурстарға (мыс: орындалу уақыты) қажеттілігін бағалауға мүмкіндік береді.

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

Қазіргі заманғы алгоритмдер теориясының даму бағыттары мен шешетін негізгі міндеттері:

-«Алгоритм» ұғымын формальдау және формальды алгоритмдік жүйелерді (есептеулер модельдерін) зерттеу;

-Есептің алгоритмдік шешімі болмайтынын дәлелдеу;

-Алгоритмдердің дұрыстығы мен эквиваленттілігін формальды түрде дәлелдеу;

-Есептерді классификациялау, күрделілігі бар кластарды анықтау және зерттеу;

- Есептің күрделілігінің теориялық төменгі бағасын дәлелдеу;

-Тиімді алгоритмдерді құру әдістерін табу;

-Итерациялық алгоритмдердің күрделілігін асимптотикалық талдау;

-Рекурсивті алгоритмдерді зерттеу және талдау;-

-Алгоритмдердің қиындығының нақты функцияларын табу;

-Алгоритмдердің классификациясын жасау;

-Есептер мен алгоримдердің сыйымдылығы бойынша күрделілігін (жад ресурстары бойынша) зерттеу;

-Алгоритмдердің ресурстық тиімділігін салыстырмалы түрде бағалаудың критерийлерін және оларды салыстырмалы талдаудың әдістерін жасау.

Алгоритмдер теориясында алынған нәтижелер екі аспектіде: теориялық және практикалық аспектілерде қолданылады.

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

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

36. Күрделілік функциясы бойынша алгоритмдерді жіктеу.

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

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) болады. Өте баяу орындалатындықтан өте аз п үшін қолданылады.

37. Күрделілікті бағалаудың функциялары дегеніміз не?

Алгоритмнің күрделілігінің f(n) функциясының негізгі бағалауы Q бағасы. Мұндағы n - деректер көлемінің шамасы немесе кірістің ұзындығын білдіреді.

Алгоритмнің күрделілігінің негізгі бағасы f(n)= Q (g(n))

егер g > 0, n > 0 болғанда мынандай оң с₁, с₂, n₀, болса: с₁ g(n) <= f(n) <= с₂ g(n)

n > n₀ болғанда мынандай с₁ мен c₂ табуға болады, үлкен n үшін f(n) мәні мына с₁ g(n) және с₂ g(n) екеуінің аралығында болады.

Бұл жағдайда g(n) функциясын f(n) функциясының асимтотикалық нақты бағасы деп атайды.

Мысалы heapsort сұрыптау әдісі үшін күрделілік бағасы f(n)= Q (nlogn) болады, яғни g (n) = n log n.

f(n)= Q (g(n)) теңдіктен g (n) = Q (f(n)) туындайды.

Маңыздысы: Q (g(n)) функция емес, функциялардың жиыны, ол f(n)-нің өсуін тұрақты көбейткішке дейін дәлдікпен көрсетеді.

Q бағасы бір мезгілде функция өсімінің жоғары және төменгі бағаны береді. Көбінесе бұл бағаларды жеке қарастыруға тура келеді.

О бағасы алгоритм қиындығының, яғни f(n) функциясының өсуінің жоғарғы асимптотикалық бағасын береді. f(n)= О (g(n)) болады, егер

орындалса.

Басқаша айтқанда тұрақты көбейткішке дейін дәлдікпен g(n) функциясына қарағанда f(n) функциясы жылдам өспейтін функциялар класын анықтайды.

W бағасы алгоритм қиындығының, яғни f(n) функциясының өсуінің төменгі асимптотикалық бағасын береді және тұрақты көбейткішке дейін дәлдікпен g(n) функциясына қарағанда f(n) функциясы баяу өспейтін функциялар класын анықтайды.

f(n)= W (g(n)) болады, егер

Егер f(n)= О (g(n)) және f(n)= W (g(n)) орындалса ғана, f(n)= Q (g(n)) теңдігі орындалады

Алгоритмдерді асимптотикалық талдауды практикалық та, теориялық та маңызы зор. Мысалы,элементтерді жұптап сұрыптауға негізделген

38. Қызыл-қара ағаштар.

h биіктіктегі екі жақтыіздестіру ағашының негізгі операциясын O (h) іс-әрекеттері арқылы жүзеге асыруға болады.Егер ағаштардың биіктігі кішкене болса, нәтижелі болады. Операция нәтижесін арттыру үшін ағаштың биіктігі Ο (log n) өлшемінде керек болса,

ағаштарды салудың тиімді әдістері қолданылады. Бұндай әдістер ағаштарды тепе-теңдікте ұстау деп аталады. Тепе-теңдік сапасының әр түрлі өлшемдері қолданылады.

Ο (log n) өлшемдегі биіктікке қол жету үшін кепіл баға беретін іздеу ағаштарының теңестірілген бір түрі қызыл-қара ағаштар деп аталады.

Осындай теңестіру кезінде жиі кездесетіні АВЛ- теңестіру, онда әр бөліктегі сол жақ ағаш түбінің биіктігі оң жағынан бірлікке ғана ерекшеленеді.

Қызыл-қара ағаштар- іздеудің кеңейтілген екі жақты ағашы,биіктігі қара және қызыл болып бөлінеді:

Әр бөлігі не қара, не қызыл.

Әр парағы (nil-бөлігі)-қара.

Егер бөлігі қызыл болса, онда екі баласы қара.

1. Бас-басы түйіншек не қызыл, не қара.

2. Бас-басы парақ(nil- түйіншек) - қара.

3. Түйіншек қызыл, оның екі баласы қара.

4. Төмен түптен жапырақтарға, баратын барлық жолдар қара түйіншектің бірдей санын асырайды.

Түбірінен жапырақтарына дейінгі жолдар бірыңғай мөлшерде қара бөліктерді құрайды. 1-4 дейінгі қасиеттер RB-қасиеттері деп аталады. Қызыл-қара ағашының бөліктерін былай белгілейміз:

Node = (color, key, left, right, parent).

Айналу – бұл RB-қасиеттері бүлінген жағдайда қызыл-қара ағаштарды қалпына келтіру үшін жасалатын әрекеттер.Оларды Insert және Delete операцияларын жүзеге асыруда орындаймыз.Айналу кезінде бірнеше көрсеткіш ауысуы мүмкін, бірақ тәртібі сақталатын жүйелі операция болып табылады.1-суретте біржақты екі айналу түрі көрсетілген:сол жаққа және оң жаққа

1. Негізгі алгоритмдік проблемаларға нелер жатады?

Негізгі алгоритмдік проблемалар:

1. Өзіне өзін қолдану п ро­бле­масы.

2. Тоқтату п ро­бле­масы

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

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

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

3. Жалпырекурсивтілік п ро­бле­масы

4. [Род­жерс,1972,с.54] кез келген натурал x мәні үшін мына сұраққа жауап беретін алгоритм бар ма: " x номерлі j_x фун­кция тұрақты функция ма?".

5. [Род­жерс,1972,с.54] кез келген натурал (x,y) жұбы үшін мына сұраққа жауап беретін алгоритм бар ма: " y мәні j_x фун­кциясының мәндер жиынына жата ма?".

6. [Род­жерс,1972,с.54] кез келген (x,y,z) үшін мына сұраққа жауап беретін алгоритм бар ма: "j_x(y)=z теңдігі орындала ма?".

7. [Род­жерс,1972,с.54] кез келген (x,y) жұбы үшін мына сұраққа жауап беретін алгоритм бар ма: "j_x=j_y теңдігі орындала ма?".?".

8. [Род­жерс,1972,с.54] кез келген x мәні үшін мына сұраққа жауап беретін алгоритм бар ма: " j фун­кциясының мәндер жиыны шексіз бе?".

9. [Род­жерс,1972,с.54] нақты y₀ және кез келген x үшін мына сұраққа жауап беретін алгоритм бар ма:: " y₀ j_x фун­кциясының мәндер жиынына жата ма?".

10. [Род­жерс,1972,с.54] нақты x₀ және кез келген y үшін мына сұраққа жауап беретін алгоритм бар ма: «y₀ j_x0 фун­кциясының мәндер жиынына жата ма».

[Род­жерс,1972,с.54]). Теорема: Ал­го­рит­мдік про­бле­малар 1-10 ал­го­рит­мдік шешімі жоқ. не­раз­ре­ши­мы. 9-про­бле­ма кез келгене y₀ үшін шешімі жоқ, ал 10-про­бле­ма x₀.-ті таңдауға байланысты шешімі болуы да болмайы да мүмкін

1. Параллель алгоритмдердің күрделілігі.

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

Параллель алгоритмдердің күрделілігі мынада: алгоритмді орындау үшін пайдаланатын жад көлемі мен уақытта. Параллель алгоритмдер тағы бір ресурсты ескеруді талап етеді: түрлі процессорлар арасындағы байланыстардың ішкі жүйелері. Процессорлар арасында алмасудың екі түрі бар: ортақ жадты пайдалану және хабар жіберу жүйелері.

Параллель жүйелердегі тиімді программаларды жасау 3 негізгі компоненттен тұрады: параллель алгоритмдер, параллелдікті іске асыру құралдары, жөндеу (отладка) жүйесі.

Параллелдікті іске асыру құралдары деп параллел программалардың инфрақұрылымын құрайтын программалау тілдерін немесе кластар кітапханасын түсінеді. Мұндай жүйелер көп. Оларға Occam, MPI, HPF, OpenMP, DVM, OpenTS,Boost.Thread, Posix Threads және Intel компаниясының Integrated Performance Primitives кітапханасын жатқызады.

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

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

Кейбір алгоритмдер оңай тәуелсіз орындалатын фрагменттерге бөліне алады. Мысалы, распределение работы по проверке всех чисел от 1 - 100000 аралығындағы сандарды жай сандарға тексеру жұмыстарын үлестіріп беру әрбір процессорға осы сандар жиынын бөліп беріп, соңынан алынған нәтижелерді - жай сандар жиындарын біріктіруден тұрады, осылай GIMPS жобасы іске асқан.

Параллель алгоритмдер көп процессорлы жүйелерді дамыту үшін, қазіргі процессорлардағы ядролар санын арттыру үшін аса маңызды. Әдетте, өгімділіктері бірдей көптеген баяу жұмыс істейтін процессорлары бар компьютерге қарағанда, бір жылдам процессоры бар компьютерді құрастыру оңай. Алайда процссордың өнімділігі техпроцессорды жетілдіру арқылы іске асады, бұған микросхема элементтерінің размеріне және жылу бөлінуіне қойылатын шектеулер әсер етеді. Бұл шектеулерді көппроцессорлы өңдеу арқылы шешуге болады., бұл тіпті шағын есептеу жүйелеіне де тиімді болып шықты.

Параллель алгоритмдерді мына есептерді шешуде қолдану мысалдары: матрицаны матрицаға көбейту, Дирихле есебі, Гаусс әдісімен және қарапайым итерация әдісімен сызықты теңдеулер жүйесін шешу (СЛАУ), n-өлшемді векторларды скаляр көбейту алгоритмі. Алгебралық және трансценденттік теңдеулердің түбірлерін табу және т.б. есептер.

1. Пирамидалық сұрыптау

Пирамидалық сұрыптау Дж. Уильямспен 1964 жылы ұсынылды. Бұл сұрыптауға керекті қосымша жад көлемі берілген деректердің көлеміне тәуелді емес. Алгоритмнің орындалу уақыты - O(n * log n). Алгоритмнің идеясы:

Пирамида – әрбір элементтің оған еншілес элементке мәні тең не үлкен болатын екілік ағаш. Ағашты солдан оңға қарай ретпен элементтермен толтырып, оны пирамидаға жеңіл сұрыптап алып айналдыруға болады. Пирамиданың ең үлкен элементі оның ұшында орналасады. Одан кейін пирамиданың ұшындағы элементпен массивтің соңғы элементі орын ауысады(өсу ретімен болғанда). Сөйтіп, массив артынан бастап сұрыпталады(оңнан солға қарай). Астындағы(еншілес) элементтер үстіндегі элементпен салыстырылып орын ауысады. Сөйтіп, ұшына екінші ең үлкен элемент келіп орналасады. Солайша сол ұшындағы үлкен элементті массивтің соңғы элементтінен кейінгі элементпен орын ауыстырамыз, өйткені ақырғы элемент сұрыпталып қойған. Сөйтіп массив элементтері оңнан солға қарай сұрыпталады.

Жақсы жақтары:

- O(n * log n) нашар жағдайының дәлелденген бағасы бар;

- Орнында сұрыптайды(пирамидалық сұрыптау – ішкі сұрыптаудың бір түріне жатады, ал ішкі сұрыптауда массивтер оперативті жадыда толығымен орналасады), яғни қосымша жадыны қажет етпейді

Жаман жақтары:

- Орындалуы ауыр;

- Сұрыпталуға жақын массивте хаосты деректертерді сұрыптағандай ұзақ;

- Орнықсыз(неустойчив) – орнықтылығын қамтамассыз ету үшін кілтті кеңейту керек;

- Әдіске тікелей рұқсат(доступ) керек, тізбекті рұқсатты қажет ететін тізіммен және басқа да жады құрылымдармен жұмыс істей алмайды

Қорытынды: алгоритмді орындау қиындығынан, оны тек үлкен көлемді n-де қолданған жөн. Үлкен емес n көлемді(бірнеше мыңға дейін) массивта Шелл сұрыптауы жылдамырақ.

1. Сараң алгоритмдердің күрделілігін бағалау.

Сараң алгоритмдер – алгоритмнің әрбір кезеңінде локальді оптимальді шешімдерді қабылдауға негізделетін алгоритм. Сонымен бірге ең соңғы шешім де оптимальді шығуы мүмкіндігін ұйғарады.

«Әр қадамда максимальды ұтыс» қағида бойынша істейтін алгоритмдер сараң (градиентті) алгоритмдер деп аталады. Осы тәріздес ең танымал есептердің бірі - оптимальді қаңқа туралы есеп.

Қолданылу шарттары: сараң алгоритмдер қолданатын есептерге екі ерекшелік тән: біріншіден, оларға сараң таңдау қағидасы қолдануға болады, екіншіден, олар қосалқы есептер үшін оптималдылық қасиетіне ие болады