Презентация на тему Студенттің өзіндік жұмысы

2.Алгоритм қасиеттері


Жоспар:

берілген мәліметтермен бір мәнде анықталатын нәтиже алу үшін қай

амалды (жұмысты) қандай ретпен орындау қажеттігін белгілейтін есептерді (мәселелерді) шешу (математикалық есеп-қисаптар орындау, техникалық объектілерді жобалау, ғылыми-зерттеу жұмысын жүргізу т.б.) тәсілдерінің дәл сипаттамасы. Алгоритм — математика мен кибернетиканың негізгі ұғымдарының бірі. Агоритмді орындау алгоритмдік процесс деп аталады.
алгоритм дегеніміз – жеке қадамдардан тұратын, формальды түрде жазылған реттелген нұсқаулар тізбегі. Алгоритм сөзі IX ғасырда өмір сүрген ұлы өзбек математигі Әл-Хорезмидің атымен аталған жазудың латындық формасы. Әл-Хорезми бірінші рет арифметикалық амалдарды орындаудың ережелерін тұжырымдаған ғалым. Алгоритм ұғымы кез-келген программа құру кезінде негізгі орын алады, себебі программа – енгізілген берілгендерді өңдеу үшін арнайы және қатаң түрде қандай да бір программалау тілінде дайындалған алгоритм. Кез-келген алгоритм қандай да бір орындаушыға негізделген. Орындалған командалар жиынтығы орындаушының командалар жүйесі болып табылады. Орындаушы ретінде – адамдар және техникалық құрылғылар, яғни роботтар, компьютерлер және автоматтар болуы мүмкін.

Кіріспе

орындалады. Бір есепті орындауға арналған екі немесе бірнеше алгоритмдердің

орындалу жылдамдығын салыстыру үшін қолданылатын критерий (өлшем) жүйелік тиімділік деп аталады. Бір компьютерде бірдей деректер жинағымен бұл алгоритмдерді орындату арқылы олардың орындалуына кеткен салыстырмалы уақытты анықтауға болады.Ол үшін ішкі жүйелік сағат қолданылады.
Ішкі жүйелік сағатты қолданып уақытты бағалау бұл бір ғана есептің орындалуына арналған алгоритмдердің әрқайсысының жүйелік тиімділігінің өлшемі болады.
Кейбір алгоритмдердің орындалуында жадқа қойылған шектеулер проблема тудырады. Орындалу барысында ұзақ уақыт сақтау үшін бастапқы көлемді қысу қажет болады.Қандай да бір алгоритм пайдаланатын ішкі жадтың салыстырмалы санының өлшемі — бұл кеңістіктің тиімділігі (space efficiency). Бұл критерий алгоритмді қандай типті компьютер орындай алатынын және алгоритмнің толық жүйелік тиімділігін көрсетеді. Жаңа компьютерлік жүйелердің жадтарының көлемінің ұлғаюна байланысты бұл критерий маңызды болмай қалды.
Үшінші тиімділік критерийі — бұл есептеу тиімділігі (computational efficiency), ол алгоритмнің ішкі құрылымын қарастырады, оның жасалуын және алгоритмде қолданылатын итерациялар мен меншіктеу операторларын салыстыратын тесттердің санын да талдайды.

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

лога­рифмдік (logarithmic) деп аталады. Мұндай күрделілік тізімдерді бірнеше рет

ішкі тізімдерге 1/2, 1/4, 1/8 етіп бөлгенде туындайды. Мысалы бинарлық бұтақтарда іздеу алгоритмдерінің күрделілігі орташа және нашар жағдайлар үшін O(log2n) болады.
Реті О(п2) болатын алгоритмдерквадраттық (quad­ratic) деп аталады. Шағын n үшін ғана практикада қолданылады. п екіге артқан сайын алгоритмнің орындалу уақыты 4-ке артады.
Реті О(n3) болатын алгоритмдер өте баяу орындалады, кубтық (cubic) уақытты қажет етеді. п екіге артқан сайын алгоритмнің орындалу уақыты 8 есе артады. Оның мысалына графтарға қолданылатын реті О(п3) болатынУоршел алго­ритмі жатады.
Күрделілігі О(2п) тең алго­ритмде экспоненциальды күрделілік (ex­ponential complexity) болады. Өте баяу орындалатындықтан өте аз п үшін қолданылады.