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

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

Асимптотикалық бағалау үшін жоғары жағынан функцияның классы қолданылады

Асимптотикалық бағалау үшін төменгі жағынан функцияның классы қолданылады

Асимптотикалық нақты бағалау үшін функцияның классы қолданылады

Келесі қатынастар орынды болып келеді

Ары қарай стандартты функцияларды білу қажет, оларды қиындылықты бағалау кезінде білу қажет. Полиномдар, экспоненттер, суперэкспоненттер, логарифмдер, суперлогарифмдер, факториалдар, Фибоначчи сандары. Өсу шапшаңдығы бойынша салыстыру меңзелінеді.

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

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

Сұрыптау дегеніміз массив элементтерін өсу не кему реті бойынша реттеу процесі. Мысалы, n элементтен тұратын X массиві оның элементтерінің мәні бойынша егер X₁ ≤ X₂ ≤...≤ X_n болса өсу реті, егер X₁ ≥ X₂ ≥... ≥ X_n. болса кему реті бойынша сұрыпталады.

Сұрыптау алгоритмдерінің түрі өте көп, бірақ олардың бәрі негізгі үш алгоритм бойынша құралады:

-алмастыру арқылы сұрыптау;

-таңдау арқылы сұрыптау;

-қою арқылы сұрыптау.

Мысал ретінде коллодаға карталарды реті бойынша салу керек деп алайық. Карталарды алмастыру арқылы сұрыптау үшін үстелге карталарды бет жағымен үстіне қаратып орналастырып, одан соң қате ретпен орналасқан карталардың орнын алмастыру арқылы карталар реті бойынша орналасқанға дейін қайталау арқылы жасауға болады.

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

Қою арқылы сұрыптау үшін колодадан екі карта алынады және бір-біріне қатысы бойынша қажетті ретпен орналастырады. Колодадан алынған әрбір кезекті карта бұрын реттелініп қойылған карталармен қатысы бойынша сәйкес орынға қойылуы тиіс.

Сұрыптау алгоритмдерін талдау, күрделілігін бағалау.

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

Алгоритмдер деректердің бастапқы сұрыпталуына тәуелді болады. Мысалы, реттелген массивтен минимал не максимал элементті табу оңай.

1. Таңдау арқылы сұрыптау

Таңдау арқылы сұрыптау – орындалуы ең жеңіл алгоритмдердің бір түрі. Оның идеясы:

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

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

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

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

- O(n^2) уақытты қажет етеді, яғни баяу

1. Таңдау арқылы сұрыптау мен Шейкер сұрыптауына талдау жаса. Қай сұрыптау тиімді?

44 ПЕН 47 ДЕН КАРАП ЖАЗУ КЕРЕК

1. Тьюринг машинасы­ дегеніміз не?

Тьюринг машинасы – бұл абстрактты орындаушы (абстрактты есептеу машинасы), 1936 жылы алгоритм ұғымын формальдау үшін Алан Тьюринг ұсынды. Басқаша Тьюринг машинасына мынадай анықтама береді. Ол – қатаң математикалық құрылым, белгілі бір есептерді шешуге арналған математикалық аппарат(дифференциалдық теңдеулер аппаратына ұқсас). Бұл математикалық аппарат құрамдас бөліктерінің сипаттамасы бойынша және функционалдауы(жұмысы) есептеуіш машиналарға ұқсас болу себебінен «машина» деп аталған. Тьюринг машинасының басқа есептеуіш машиналарынан басты айырмашылығы оның есте сақтауыш құрылғысы шексіз лента түрінде келеді: өмірде бола алатын есептеуіш машиналардың есте сақтау құрылғысы қандай да бір үлкен бола алады, бірақ Тьюринг машинасы сияқты шексіз бола алмайды. Міне осы лентаның шексіздігінен Тьюринг машинасын құрастыру мүмкін емес. Осындай мағынада ол кез келген мықты есептеуіш машиналардан мықты. Тьюринг машинасы ақырлы автоматтың кеңейтілу моделі болып табылады. Черч – Тьюринг тезисі бойынша, ол бір дискреттік жағдайдан екіншіге өтетін кез келген машинаны имитациялай алады.

Әрбір Тьюринг машинасында екі бөлік бар:

1) ұяшықтарға бөлінген екі жағына да шексіз лента;

2) ақырлы(конечный) санды күйі бар басқарушы құрылғы немесе автомат(программамен басқарылатын оқуға және жазуға арналған бас(головка)).

Әрбір Тьюринг машинасымен екі ақырлы алфавит байланысқан: енгізілетін символдардың алфавиті А= {a0, a1, …, an} және күйлер алфавиті Q = {q0, q1, …, qp}. Басқарушы құрылғы лента бойымен оңға солға қозғала алады, кейбір ақырлы алфавиттердің символдарын ұяшықтарға жаза және оқи алады. Басқарушы құрылғыда Тьюринг машинасымен орындалатын алгоритмді көрсететін өтулер кестесі орналасады. Кестедегі әрбір ереже ұяшыққа жаңа символды жазу, жаңа күйге өту, бір ұяшыққа оңға не солға қозғалуды машинаға бұйырады. Тьюринг машинасының кейбір күйлері терминальды болып белгіленуі мүмкін және олардың кез келгеніне өту жұмыстың соңын, алгоритмнің аяқталуын білдіреді.

Тьюринг машинасы детерминирленген деп аталады, егер кесетедегі әрбір күй комбинацияларына және ленталық символға бір ережеден көп сәйкес келмесе, басқа жағдайда детерминирленбеген болады.

1. Шейкер сұрыптауы

Шейкер сұрыптауы – көпіршікті сұрыптаудың модификациясы. Оның әртүрлі аты бар: шейкерлі сұрыптау, трансферттік сұрыптау, екі жаққа бағытталған көпіршікті сұрыптау. Міне осы соңғы оның аты затына сай. Оның жұмыс істеу принципі көпіршікті сұрыптаудағыдай бір ғана ерекшелікпен – алгоритмді сұрыптау көпіршіктегідей тек төменнен жоғары емес, алдымен төменнен жоғары, сосын жоғарыдан төменге қарай сұрыпталады. Сөйтіп массив екі жақтан кезек кезекпен сұрыпталады.

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

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

- Қарапайым көпіршікті сұрыптаудан екі есе жылдам

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

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

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

1. Шелл арқылы сұрыптау

Шелл сұрыптау алгоритмі немесе арақашықтығы кемитін кірістірулер арқылы сұрыптау. Оны 1959 жылы Дональд Шелл қарапайым кірістірулер арқылы сұрыптау алгоритмін жылдамдату үшін ұсынған. Оның идеясы тек қана жанындағы элементтер емес бір-бірінен қашықтықта орналасқан элементтерді салыстыру. Алдымен массивтегі элементтер саны есептеледі. Одан кейін n элементтер санын екіге бөледі. Сөйтіп бірінші d арақашықтығы шығады. Ол массивтердің салыстыру қашықтығы болып табылады. Сондай d арақашықтағы элементтерді салыстырып, қате орналасса орнын ауыстырамыз. Артынан екінші d арақашықтығын тауып, тағы да салыстырамыз. d=1 болғанда қарапайым кірістурулер әдісі арқылы сұрыптаймыз.

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

- Стекке жадының қажеттілігі жоқтығы;

- Деректерді қате терудегі деградациялардың жоқтығы;

- Орташа көлемді массивтерде жылдам

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

- Кіші және үлкен көлемді массивтерде баяу;

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

49. Іздеу ағашында орындалатын операциялар.(-)

50. Іздеудің екілік ағашы

Іздеудің екілік ағашы. 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.
қосымша уақытты Ο (h) биіктіктің h ағашы үшін сұрайды.

1. Концептуалдық программалау. (-)
2. Алгоритмдерді синтездеуғе кіріспе(-)
3. Концептуалдық программалауды іске асырудың негізгі әдістемелік принциптері

Теорема шешу жолдары

(М), ... ...

мундагы ... ... айнымалылар

... енгизилетин айнымалылар

... натижелер, ал М тапсырмалар шарты

... шамалары тапсырма шартын канагаттандыру керек. Тапсырманы шешу ушин шарттын дурыс болганы жеткиликти. Онда бул теоремалар шешу жолы деп аталады.

Ал егер А, ... болса онда А формула болып табылады. Далелдеуди кажет етпеитин формула. Формула мен аксиомалар дурыс корытылган тури теорема деп аталады. Айтылгандардын барлыгы теорема синтаксисынын бир болиги гана. Енди симатикага назар аударайык. Симантиканы аныктауга тагы бир объект Л кажет. егер арбир тилдин магынасы Л объектисине байланысты болса онда оны тилдин интерпретациясы деп атайды. Нактылай келе Л-дын озинин аныкталган ишки курылымы болу керек. Тилдин формуласынын интерпретациясы тек кана акикат немесе жалган екенин гана аныктай алады. Аксиома болса аркашан акикат болады.

1. Концептуалдық программалауды іске асырудың негізгі әдістемелік принциптері.

Программа куру кезинде есепти шешу амалдарын 2ге болип карастыруга болады:

1. Бурынгы корген адистер мен кателиктерди ескере отырып тапсырманы шешу. Ен басты максаты аз кателик жиберу аркылы жасау.

2. Тапсырманы шешуден бурын жоспар куру, жоспар дурыс деп кабылданбай жумысты бастамау.

Есептеуге болатын тапсырмалар.

Есептеу тапсырмаларында айнымалылар колданылады, оларды идентификатор деп белгилейди.

Мысалы: х

Айнымалылар турли типте болады. Есептеу тапсырмаларына мысалдар карастырайык. Ушбурыш ауданын онын 3 кабыргасы бойынша есептеп шыгамыз деген тапсырманы айнымалылар комегимен жазуга болады. ушбурышты биле отырып ABC комегимен С-ти жане институттын барлык кызметкерлерин фамилиясын табу деген тапсырмада жастардын фамилиясы - айнымалы, ал кадрлар тапсырма шарты деп алсак онда кадрларды биле отырып жастар фамилиясын есептеп шыгаруга болады. Бул жагдайда тапсырмалар саны манызды болады. Бул тапсырмаларды келеси формулалармен жазуга болады.

... ...

мундагы ... ... айнымалылар

... енгизилетин айнымалылар

... натижелер, ал М тапсырмалар шарты

1. Логикалық программаның синтездеу негіздері. Теореманың шешу жолдары.

Теорема шешу жолдары

(М), ... ...

мундагы ... ... айнымалылар

... енгизилетин айнымалылар

... натижелер, ал М тапсырмалар шарты

... шамалары тапсырма шартын канагаттандыру керек. Тапсырманы шешу ушин шарттын дурыс болганы жеткиликти. Онда бул теоремалар шешу жолы деп аталады.

Ал егер А, ... болса онда А формула болып табылады. Далелдеуди кажет етпеитин формула. Формула мен аксиомалар дурыс корытылган тури теорема деп аталады. Айтылгандардын барлыгы теорема синтаксисынын бир болиги гана. Енди симатикага назар аударайык. Симантиканы аныктауга тагы бир объект Л кажет. егер арбир тилдин магынасы Л объектисине байланысты болса онда оны тилдин интерпретациясы деп атайды. Нактылай келе Л-дын озинин аныкталган ишки курылымы болу керек. Тилдин формуласынын интерпретациясы тек кана акикат немесе жалган екенин гана аныктай алады. Аксиома болса аркашан акикат болады.

1. Логикалық программаның синтездеу негіздері. Формальдық теорияға кіріспе.

Теорема шешу жолдары

(М), ... ...

мундагы ... ... айнымалылар

... енгизилетин айнымалылар

... натижелер, ал М тапсырмалар шарты

Осыған байланысты тұжырымдама айтуға болады: ... шамалары тапсырма шартын канагаттандыру керек. Тапсырманы шешу ушин шарттын дурыс болганы жеткиликти. Онда бул теоремалар шешу жолы деп аталады. Енді тапсырманы формальды турде карастырыйык:

М есептын шартын 2 предикат турынде карастырайык: Кырыстык шарт Р(х) жане шыгыстык шарт R(x,y). Теореманы шешу аркылы компактты турде корсетейык: . Еске салатын быр жагдай Формальдау теориясынын негызы. Кейбыр жиыннын магынасы жагынан жакын синтаксистегы тылдер жиынын формула деп атайды.

Ал егер А, ... болса онда А формула болып табылады. Далелдеуди кажет етпеитин формула. Формула мен аксиомалар дурыс корытылган тури теорема деп аталады. Айтылгандардын барлыгы теорема синтаксисынын бир болиги гана. Енди симатикага назар аударайык. Симантиканы аныктауга тагы бир объект Л кажет. егер арбир тилдин магынасы Л объектисине байланысты болса онда оны тилдин интерпретациясы деп атайды. Нактылай келе Л-дын озинин аныкталган ишки курылымы болу керек. Тилдин формуласынын интерпретациясы тек кана акикат немесе жалган екенин гана аныктай алады. Аксиома болса аркашан акикат болады.

1. Логикалық программаның синтездеу негіздері. Формуланы құрастыру.

ТОЖЕ САМОЕ ЧТО И 57

1. Программа және дәлелдеуі. Дәлелдеуді құру.

Дәлелденген есепті, қысқаша құрып, нәтижесін алуға арналған 2 идея бар:

1 - тапсырманың нәтижесін формальді теория түрінде алу арқылы аксиоманы арнайы схема түріде алу болып келеді. Әрбір тапсырманы, яғни есептің құрыымына байланысты нақтылау теориясы құрылады. Енді осыған теорма бір ғана жауабы жеткілікті. Жеке бөліп қарағанда аксиомадан бірнеше аксиома пайда болады. Егер есептің берілгеніне байланысты объект болса, 2- дәлелдеу кезінде оның тек есептеу құрамдығын құрылымдығына байланысты есептеу. операциялар реже бойынша дәлелденбейді. Егер кейбір объект аксомаға байланысты құрылады десе, есептеу ережесі дұрыс болып саналады. Жеке бөліп қарағанда әр түрлі амал орындалса, дұрыс нәтиже береді. Мұндай жағдайда шарттың дұрыс анықталғаны маңызды. жазылған сөйлем арқылы, аксиомаға шектеу қоюға болады.

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

2)

Мұндағы R,b – спецификациялық предикат. X, y орнына анықталған айнымалылар.

Rx және by предикатының программаны синтездеуді айнымалысы ретінде қолданады.

Дәлелдеуді құру. Ең қиын саты дәлелдеуді дедуктивті синтез арқылы құру болып табылады.

Программаны синтездеу кезінде аксиоманы есептету арқылы программада анықтау іске асырылады. Дәлелдеуді құру теориясының зерттеліп келе жатқанына 20жыл болды.

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

Сонымен қатар, берілген уақытта дәлелдеуді, жылдам алуға мумкіедік береді.

1. Программаның синтездеу құрылымы. Есептеуге арналған амалдар

Алгоритмді іздеу қорытындысына соңғы синтездеу құрылымының теориясы. Бұл пункте теориямен ғана шектелмейміз, онда тек қана қарастырылады. Бірақ практикада тапсырмалардың шешімін табу үшін әліде жеке жеке теори құру қажет пе? Ақырғы теорияда тапсырмаларың шарты бойынша ақырғы объект сайын анықтайды. Осындай алгритмдер үшін іздеу алгоритмі жасалған. қорытындыны төменнен жоғарыға дейін құрайық. аксиоманың мақсатқа дейін қорытынды жасап көрейік, предикатты объект жиынын іздеу барысында қолданылады. Х – предикат, дәлелденген формула. және D предикат болады, кірістік формула мынадай болады:

C₁…C:->D₁…D_q бастапқы жағдайда {x₁…x_n} берілген кез келген жағдайда {E₁…E_k} болса, онда

шығады.

Аналитикалық құрылымының қадамы анықталғанда тапсырмалардың ішіндегі есептеу мынадай болады: )

Есептеуді осы жағдайда қабылдау үшін келесі формуланы ескеру керек

онда

Дәлелдеу теориясының шешу жалпы мынадай: