- •Np толық есептердің кластары.
- •Np толықтық деген не?
- •P класы
- •Алгоритм верификациясы
- •Алгоритм дұрыстығы.
- •Алгоритм күрделілігін бағалау.
- •Алгоритм талдауындағы белгілеу жүйесі. Белгілеулерге анықтама бер.
- •Алгоритм тиімділігі дегеніміз не?
- •Алгоритмдер теориясы дегеніміз не? Алгоритмдер теориясының шығу тарихы.
- •Алгоритмдер теориясына кіріспе. Алгоритм ұғымы, анықтамасы.
- •Алгоритм ұғымы, қасиеттері , түрлері
- •P класы.
- •Алгоритмдерді талдау дегеніміз не?
- •Алгоритмдік шешімі болу және болмау ұғымы туралы айт.
- •Алгоритмнің бірігуі дегеніміз не?
- •Алгоритмнің зерттеу салалары
- •Алгоритмнің күрделілігі дегеніміз не?
- •Бағдарламаның дұрыстығын дәлелдеу әдісмтемесі
- •Бинарлық іздеу
- •Бөліп ал да басқар принципіне негізделген алгоритмдерді талдау.
- •Верификация дегеніміз не? Оның әдістері туралы айт?
- •Графта іздеудің қандай әдістері бар?
- •Есептеліну және шешімі болу дегеніміз не?
- •Есептердің алгоритмдік күрделілілігін өлшеу.
- •Күрделіліктің негізгі бағалауларының түрлері қандай?
- •Кірістіру арқылы сұрыптау
- •Қазіргі заманғы алгоритмдер теориясының даму бағыттары мен шешетін негізгі міндеттері.
- •Күрделілік функциясы бойынша алгоритмдерді жіктеу.
- •Қызыл-қара ағаштар.
- •Негізгі алгоритмдік проблемаларға нелер жатады?
- •Параллель алгоритмдердің күрделілігі.
- •Пирамидалық сұрыптау
- •Сараң алгоритмдердің күрделілігін бағалау.
- •Сұрыптау алгоритмдерін талдау, күрделілігін бағалау
- •Таңдау арқылы сұрыптау
- •Тьюринг машинасы дегеніміз не?
- •Шейкер сұрыптауы
- •Шелл арқылы сұрыптау
- •Іздеу ағашында орындалатын операциялар.(-)
- •Іздеудің екілік ағашы
- •Концептуалдық программалау. (-)
- •Алгоритмдерді синтездеуғе кіріспе(-)
- •Концептуалдық программалауды іске асырудың негізгі әдістемелік принциптері
- •Логикалық программаның синтездеу негіздері. Формуланы құрастыру.
- •Программаның синтездеу құрылымы. Есептеуге арналған амалдар
Пирамидалық сұрыптау
Пирамидалық сұрыптау Дж. Уильямспен 1964 жылы ұсынылды. Бұл сұрыптауға керекті қосымша жад көлемі берілген деректердің көлеміне тәуелді емес. Алгоритмнің орындалу уақыты - O(n * log n). Алгоритмнің идеясы:
Пирамида – әрбір элементтің оған еншілес элементке мәні тең не үлкен болатын екілік ағаш. Ағашты солдан оңға қарай ретпен элементтермен толтырып, оны пирамидаға жеңіл сұрыптап алып айналдыруға болады. Пирамиданың ең үлкен элементі оның ұшында орналасады. Одан кейін пирамиданың ұшындағы элементпен массивтің соңғы элементі орын ауысады(өсу ретімен болғанда). Сөйтіп, массив артынан бастап сұрыпталады(оңнан солға қарай). Астындағы(еншілес) элементтер үстіндегі элементпен салыстырылып орын ауысады. Сөйтіп, ұшына екінші ең үлкен элемент келіп орналасады. Солайша сол ұшындағы үлкен элементті массивтің соңғы элементтінен кейінгі элементпен орын ауыстырамыз, өйткені ақырғы элемент сұрыпталып қойған. Сөйтіп массив элементтері оңнан солға қарай сұрыпталады.
Жақсы жақтары:
O(n * log n) нашар жағдайының дәлелденген бағасы бар;
Орнында сұрыптайды(пирамидалық сұрыптау – ішкі сұрыптаудың бір түріне жатады, ал ішкі сұрыптауда массивтер оперативті жадыда толығымен орналасады), яғни қосымша жадыны қажет етпейді
Жаман жақтары:
Орындалуы ауыр;
Сұрыпталуға жақын массивте хаосты деректертерді сұрыптағандай ұзақ;
Орнықсыз(неустойчив) – орнықтылығын қамтамассыз ету үшін кілтті кеңейту керек;
Әдіске тікелей рұқсат(доступ) керек, тізбекті рұқсатты қажет ететін тізіммен және басқа да жады құрылымдармен жұмыс істей алмайды
Қорытынды: алгоритмді орындау қиындығынан, оны тек үлкен көлемді n-де қолданған жөн. Үлкен емес n көлемді(бірнеше мыңға дейін) массивта Шелл сұрыптауы жылдамырақ.
Сараң алгоритмдердің күрделілігін бағалау.
Сараң алгоритмдер– алгоритмнің әрбір кезеңінде локальді оптимальді шешімдерді қабылдауға негізделетін алгоритм. Сонымен бірге ең соңғы шешім де оптимальді шығуы мүмкіндігін ұйғарады.
«Әр қадамда максимальды ұтыс» қағида бойынша істейтін алгоритмдер сараң (градиентті) алгоритмдер деп аталады. Осы тәріздес ең танымал есептердің бірі - оптимальді қаңқа туралы есеп.
Қолданылу шарттары: сараң алгоритмдер қолданатын есептерге екі ерекшелік тән: біріншіден, оларға сараң таңдау қағидасы қолдануға болады, екіншіден, олар қосалқы есептер үшін оптималдылық қасиетіне ие болады
Сараң таңдау қағидасы
Егер локальді оптимальді таңдаулар тізбегі глобальді оптимальді шешімін берсе, онда оптимизацилық есепке сараң таңдау қағидасын қолдануға болады. Әдеттегі жағдайда оптималдылықтың дәлелі келесі схемаға сәйкес болады: алдымен, сараң таңдау бірінші қадамда оптимальді шешімге келуге кедергі жасамайды екендігі дәлелденеді: әрбір шешімге сәйкес сараң таңдаумен үйлесімді және бірінші шешімнен жаман емес басқа шешім бар. Содан кейін, сараң таңдаудың бірінші қадамынан соң пайда болатын қосалқы есеп бастапқы есепке ұқсас екендігі көрсетіледі және пікір индукция бойынша бітеді.
Сараң алгоритмдердің тиімді шешім бермейтін есептері
NP класына жататын есептер қатары сараң алгоритмдер оптималды шешім бермейді. Оларға келесілер жатады:
Коммивояжер есебі;
Графтың минималды суреттеу есебі;
Графты қосалқы графқа бөлу есебі
Максималды кликті бөлу есебі
Кестені құрумен байланысты есептер
Дегенмен кейбір есептерде сараң алгоритмдер жаман емес жақын шешім береді.
Алгоритмдердің күрделілігін бағалау үшін қолданылатын функциялардың кластары
Төменде
қолданылған алгоритмдердің күрделілігін
бағалайтын барлық функциялар табиғи
аргументтің теріс емес асимптотикалық
функциясы деп есептеледі,
аргументінің кейбір мәнінен бастап.
Асимптотикалық бағалау үшін жоғары жағынан функцияның классы қолданылады
Асимптотикалық бағалау үшін төменгі жағынан функцияның классы қолданылады
Асимптотикалық нақты бағалау үшін функцияның классы қолданылады
Келесі қатынастар орынды болып келеді
Ары қарай стандартты функцияларды білу қажет, оларды қиындылықты бағалау кезінде білу қажет. Полиномдар, экспоненттер, суперэкспоненттер, логарифмдер, суперлогарифмдер, факториалдар, Фибоначчи сандары. Өсу шапшаңдығы бойынша салыстыру меңзелінеді.
.Қолданылу шарттары: сараң алгоритмдер қолданатын есептерге екі ерекшелік тән: біріншіден, оларға сараң таңдау қағидасы қолдануға болады, екіншіден, олар қосалқы есептер үшін оптималдылық қасиетіне ие болады. Жоғары және төменгі бағалауды және орташа бағалауды алу үшін амортизациялық бағалаулар жиі қолданылады.
