- •Np толық есептердің кластары.
- •Np толықтық деген не?
- •P класы
- •Алгоритм верификациясы
- •Алгоритм дұрыстығы.
- •Алгоритм күрделілігін бағалау.
- •Алгоритм талдауындағы белгілеу жүйесі. Белгілеулерге анықтама бер.
- •Алгоритм тиімділігі дегеніміз не?
- •Алгоритмдер теориясы дегеніміз не? Алгоритмдер теориясының шығу тарихы.
- •Алгоритмдер теориясына кіріспе. Алгоритм ұғымы, анықтамасы.
- •Алгоритм ұғымы, қасиеттері , түрлері
- •P класы.
- •Алгоритмдерді талдау дегеніміз не?
- •Алгоритмдік шешімі болу және болмау ұғымы туралы айт.
- •Алгоритмнің бірігуі дегеніміз не?
- •Алгоритмнің зерттеу салалары
- •Алгоритмнің күрделілігі дегеніміз не?
- •Бағдарламаның дұрыстығын дәлелдеу әдісмтемесі
- •Бинарлық іздеу
- •Бөліп ал да басқар принципіне негізделген алгоритмдерді талдау.
- •Верификация дегеніміз не? Оның әдістері туралы айт?
- •Графта іздеудің қандай әдістері бар?
- •Есептеліну және шешімі болу дегеніміз не?
- •Есептердің алгоритмдік күрделілілігін өлшеу.
- •Күрделіліктің негізгі бағалауларының түрлері қандай?
- •Кірістіру арқылы сұрыптау
- •Қазіргі заманғы алгоритмдер теориясының даму бағыттары мен шешетін негізгі міндеттері.
- •Күрделілік функциясы бойынша алгоритмдерді жіктеу.
- •Қызыл-қара ағаштар.
- •Негізгі алгоритмдік проблемаларға нелер жатады?
- •Параллель алгоритмдердің күрделілігі.
- •Пирамидалық сұрыптау
- •Сараң алгоритмдердің күрделілігін бағалау.
- •Сұрыптау алгоритмдерін талдау, күрделілігін бағалау
- •Таңдау арқылы сұрыптау
- •Тьюринг машинасы дегеніміз не?
- •Шейкер сұрыптауы
- •Шелл арқылы сұрыптау
- •Іздеу ағашында орындалатын операциялар.(-)
- •Іздеудің екілік ағашы
- •Концептуалдық программалау. (-)
- •Алгоритмдерді синтездеуғе кіріспе(-)
- •Концептуалдық программалауды іске асырудың негізгі әдістемелік принциптері
- •Логикалық программаның синтездеу негіздері. Формуланы құрастыру.
- •Программаның синтездеу құрылымы. Есептеуге арналған амалдар
Шейкер сұрыптауы
Шейкер сұрыптауы – көпіршікті сұрыптаудың модификациясы. Оның әртүрлі аты бар: шейкерлі сұрыптау, трансферттік сұрыптау, екі жаққа бағытталған көпіршікті сұрыптау. Міне осы соңғы оның аты затына сай. Оның жұмыс істеу принципі көпіршікті сұрыптаудағыдай бір ғана ерекшелікпен – алгоритмді сұрыптау көпіршіктегідей тек төменнен жоғары емес, алдымен төменнен жоғары, сосын жоғарыдан төменге қарай сұрыпталады. Сөйтіп массив екі жақтан кезек кезекпен сұрыпталады.
Жақсы жақтары:
Орындалу алгоритмі өте жеңіл;
Қарапайым көпіршікті сұрыптаудан екі есе жылдам
Жаман жақтары:
Үлкен емес массивтерде ғана тиімді;
Алгоритмнің күрделілігі – O(n^2)
Шелл арқылы сұрыптау
Шелл сұрыптау алгоритмі немесе арақашықтығы кемитін кірістірулер арқылы сұрыптау. Оны 1959 жылы Дональд Шелл қарапайым кірістірулер арқылы сұрыптау алгоритмін жылдамдату үшін ұсынған. Оның идеясы тек қана жанындағы элементтер емес бір-бірінен қашықтықта орналасқан элементтерді салыстыру. Алдымен массивтегі элементтер саны есептеледі. Одан кейін n элементтер санын екіге бөледі. Сөйтіп бірінші d арақашықтығы шығады. Ол массивтердің салыстыру қашықтығы болып табылады. Сондай d арақашықтағы элементтерді салыстырып, қате орналасса орнын ауыстырамыз. Артынан екінші d арақашықтығын тауып, тағы да салыстырамыз. d=1 болғанда қарапайым кірістурулер әдісі арқылы сұрыптаймыз.
Жақсы жақтары:
Стекке жадының қажеттілігі жоқтығы;
Деректерді қате терудегі деградациялардың жоқтығы;
Орташа көлемді массивтерде жылдам
Жаман жақтары:
Кіші және үлкен көлемді массивтерде баяу;
Бұл алгоритмнің анализі – әлі күнге дейін толық жауабы жоқ күрделі математикалық есеп, сол себепті қандай арақашықтық ең тиімді көрсеткіш беретіндігі де белгісіз.
Іздеу ағашында орындалатын операциялар.(-)
Іздеудің екілік ағашы
Іздеудің екілік ағашы. Iздеудің екiлiк ағашы. Iздестiру екiлiк ағашы әрбiр түйiнiне өлшенген элемент сәйкестiкке орнатылған түбiрлiк екiлiк ағашы деп аталады. Әрбiр түйiн x үшiн келесi шартты орындайды. X түбiрi бар сол ағаш астындағы барлық х түйiндерiнiң салмағынан аз немесе тең, онының оң жақ ағаш астындасының түйiндерiнiң салмағы артық немесе түйiн x салмағына тең. Келесi түрдiң түйiндерiмен мұндай ағаш өкiлдiк етедi Node = (element, key, left, right, parent) T ағашқа рұқсат сiлтеме root көмегiмен жүзеге асырылады. Екiлiк iздестiру ағашымен орындалатын операциялары: Search, Minimum, Maximum, Successor және Predecessor уақытқа орындауға мүмкiндiк береді (h ), ағаштың биiктiгi h. 1. (Search ) iздестiру. Iздестiрудiң процедурасы k және x iздестiрудi iстелетiн ағаш астынданың түбiрiне көрсеткiш кiре берiске iзделiп отырған кiлт алады. Ол (егер болса) k немесе (егер мұндай шың жоқ жағдайда) nil кiлтпен шыңға көрсеткiштi қайтарады. Procedure Search (x, k); begin if(x = nil) or (k = key [x]) then Return x; if(k < key [x]) then Return Search (left[x], k) else Return Search (right[x], k) end. Бiз iздестiрудiң процесiнде түбiрден қозғаламыз, кілтті k кiлтпен салыстыра, x ағымдағы шың сақталған қозғаймыз. Егер ол тең болса, iздестiру аяқталады. Егер k < key[x], онда iздестiру x сол ағаш астындада созылады. Егер k > key[x], онда iздестiру оң ағаш астында созылады. Iздестiру жолының ұзындығы ағаштың биiктiгiн асып түспейдi, сондықтан iздестiрудiң уақыты (h - ағаштың биiктiгi) (h ) O бар. Іздестiру итерациясының процедурасы: Procedure IterativeSearch (x, k); begin While (x ≠ nil) and (k ≠ key [x]) do If k < key [x] then x:= left[x] else x:= right[x]; Return (x) end. Минимум және максимум. Iздестiру ағашында ең төменгi кiлтпен элемент табуға болады, көрсеткіш left түбiрден өте шыға nil-ге жеткенімізге дейін табуға болады. (x ) Minimum(x) процедура түбiрi бар ағаш астынданың табылған элементiне көрсеткiштi қайтарады. Procedure Minimum(x); begin While left [x] ≠ nil do x:= left[x]; Return (x) end. Алгоритм Maximum симметричен: Procedure Maximum(x); begin While (right [x] ≠ nil) do x:= right[x]; Return (x) end. Екі алгоритм O(h) уақытты (ағаш бойымен тек қана төмен қозғалғандықтан) ағаштың биiктiгi талап етедi. Келесi және алдыңғы элементтер. Егер х кейбір ағаштың көрсеткіші болса, сол Successor(x) рәсімі сілтегішті түйіншекке мен кейінгі x элемент немесе nil, егер көрсетілген элемент соңғы ағашқа қайтарады Procedure Successor(x); begin If (right[x] ≠ nil) then Return Minimum (right[x]); y:= p[x]; while(y ≠ nil) and (x=right [y]) do {x:= y; y:= parent[y]}; Return y end. Келтiрiлген процедура екi жағдайды бөлек қарастырылады. Егер шың x оң ағаш астындағысы бос болмаса, онда келесi x элементке - бұл ағаш астындада ең төменгi элемент және ([x ] right) Minimum тең бол. Болғанша, егер шың x оң ағаш астындасы бос болса, онда x жүр өз ата-анасын сол ұл болатын шыңды үстiне таппаймыз. Бұл (егер ол барып тұр) ата-ана және iзделiп отырған элемент болады. Процедура Successor ағашындағы жұмысын уақыты биiктiгінде(h ), өйткенi бiз тек - үстiне, немесе тек қана төмен қарай қозғаламыз. Predecessor процедура симметриялық. Элементтiң қосымшасы.Процедура Insert (T, z) ағаш T қолайлы орынына элемент берiлгенге толықсытады. екі уақиғаны қарайды. x шыңының оң тармағы бос, сол кейінгі x элементті - ең төмен элемент осы тармақтағы және Minimum(right[x]) тең. x шыңының оң тармағы бос болса, x жоғары жағына барамыз, шыңды тапқанша Procedure Insert(T, z); begin y := nil; x := root; while(x ≠ nil) do {y := x; if key[z] < key[x] then x := left[x] else x := right[x]}; p [z] := y; ify = nil then root := z else if key[z] < key[y] then left[y] := z else right [y]:= z end. Концептуалдық программалауды іске асырудың негізгі әдістемелік принциптері.
Программа куру кезинде есепти шешу амалдарын 2ге болип карастыруга болады:
1. Бурынгы корген адистер мен кателиктерди ескере отырып тапсырманы шешу. Ен басты максаты аз кателик жиберу аркылы жасау.
қосымша уақытты Ο (h) биіктіктің h ағашы үшін сұрайды.
