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

Екілік іздеу ағашы(ағылшын. binary search tree, BST) — барлық төбелері реттелгген, әрбір төбедесінен тек екі төбе шығатын(сол және оң), және түбірінен басқа барлықтөбелерінің ортақ төбесі, яғни аталық төбесі бар ағаш. Ұрпақтары жоқ төбелерді жапырақтар деп атайды.

Келесі шарттар орындалады:

• _Ішкі ағаштардың екеуі де(оң және сол) — екілік іздеу ағашытары болып табылады.

• _Қандай да бір X түйінінің сол жақ ішкі ағашының барлық түйіндерінің деректер кілттерінің мәндері, X түйінінің деректер кілттері мәнінен азболады.

• _{Сонымен} қатар, сол X түйінінің оң жақ ішкі ағашының барлық түйіндерінің деректер кілттерінің мәндері, X түйінінің деректер кілттері мәнінен азболмайды.

C/C++ тегі екілік іздеу ағашының құрылымы:

typedef int item_type;

typedef struct tree {

Item_type item;

struct tree *parent;

struct tree *left;

struct tree *right;

} tree;

Бинарлық ағаштарға қолданылатын амалдар:

1. Бинарлық ағащқа элемент қосу — ағаштың өлшеміне қатысты (logN) логарифмдік күрделілгі бар амал(операция). C++ тегі код мысалы:

Void insert_tree(tree **t, item_type item, tree *parent) {

tree *p;

if(*t == NULL) {

p = (tree *)malloc(sizeof(tree));

p->left = p->right = NULL;

p->parent = parent;

p->item = item;

*t = p;

return;

}

if(item < (*t)->item) {

insert_tree(&((*t)->left), item, *t);

} else {

insert_tree(&((*t)->right), item, *t);

}

}

2) Төбені іздеу:

tree *search_tree(const tree *t, item_type i) {

if(t == NULL) return NULL;

if(t->item == i) return i;

if(i < t->item) {

return search_tree(t->left, i);

} else {

return search_tree(t->right, i);

}

}

3) Жою

4) Жүріп шығу(обход)

3. Дейкстра алгоритмімен шешілетін есепке сипаттама беріңіз. Алгоритмді қолданып жалпылама мысал келтіріңіз.

Бұл алгоритм графтың барлық төбелері мен ұзындықтары арасында ең қысқа жолды табады. Графтың белгілі бір төбесі мен басқа төбелері арасындағы оптималды маршрутты табатын Дейкстра алгоритмінің жұмыс істеу принципін қарастырайық. Мысал үшін келесі G графын алайық:

Бұл графты келесі С матрицасы түрінде жазуға болады:

Басты төбе ретінде 1-төбені алайық. Бұл 1-төбеден басқа 2,3,4,5-төбелерге ең қысқа жолды іздейтінімізді білдіреді. Бұл алгоритм графтың барлық төбелеріне қадаммен барып, басты төбеден белгілі бір төбеге дейінгі ең минималды қашықтықты білдіретін жолға белгі қойып отырады.

1-төбеге басты төбе болғандықтан 0 белгісін қоямыз. Қалған төбелерге шексіздік белгісін қоямыз.

Минималды белгіге ие болатын төбені (W) деп белгілейміз (қазір ол 1-төбе), және W-төбеден тікелей жол бар басқа төбелерді қарастырамыз. W-төбесі мен келесі төбе қашықтығының суммасын тауып, алынған мән қарастырылған төбенің мәнінен кіші болса оны осы мәнмен ауыстырамыз. Егер сумма кіші болмаса алдыңғы белгіні өзгертусіз қалдырамыз.

W-төбеден тікелей жол бар басқа төбелерді қарастырып болған соң, W-төбені қарастырылған төбе ретінде белгілейміз. Енді әлі қарастырылмаған төбелердің ішінен белгі мәні ең минималды төбені таңдап аламыз, бұл біздің келесі W-төбеміз болады. Қазір бұл төбе 2 немесе 5. Егер белгілері бірдей бірнеше төбе бар болса, W-төбе ретінде олардың кез-келгенін ала беруге болады. Біз 2-төбесін алайық. Бірақ одан шығатын бірде-бір төбе болмағандықтан оны бірден қарастырылған төбе ретінде белгілейміз де, келесі минималды белгісі бар төбеге көшеміз. Бұл жолы тек 5-төбесі минималды мәнге ие. 5-төбесінен шығатын тікелей қатынайтын жол бар төбелерді қарастырамыз, бірақ әлі қарастырылған төбе ретінде белгіленбеген төбелерді ғана. Тағы да W-төбесінің белгісі мен белгілі бір төбеге дейінгі қабырға суммасын табамыз. Егер бұл сумма алдыңғы белгіден аз болса, онда белгінің мәнін алынған суммаға өзгертеміз.

Суреттен 3 және 4 төбелерінің мәндері азайғанын көреміз. Демек, негізгі төбеден бұл төбелерге дейінгі әлдеқайда қысқа маршрут табылды. Енді 5-төбені қарастырылған төбе ретінде белгілеп, келесі минималды мәнге ие төбеге көшеміз. Барлық төбелерді қарастырып болғанша жоғарыда айтылған әрекеттерді қайталаймыз.

Барлық әрекеттерді орындай келе келесідей нәтиже аламыз:

4. Форд-Фалкерсон алгоритмімен шешілетін есепке сипаттама беріңіз. Алгоритмді қолданып жалпылама мысал келтіріңіз.

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

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

Форд-Фалкерсон тәсілінде негізгі рөлді екі түсінік құрайды: қалдық желілер және қосымша жолдар. Желі және ондағы ағыс берілсін. Сонда, қалдық желі, олардың бойындағы ағысты үлкейтуге болатын қабырғалардан (қалдық деп те аталатын) тұрады. Байқау керегі, қалдық қабырға бастапқы желінің қабырғасы болуы міндетті емес. Мұндай "қызық" қабырғалар кері бағытта сұйықтықтың ағымы кері бағытта болғанда пайда болады – ол ағымды кішірейтуге болады. Қосымша жол деп қалдық желідегі бастаудан ағып түсуге дейінгі қарапайым жолды атайық. Қалдық желінің анықтамасынан қосымша жолдың барлық қабырғаларымен біраз сұйықтықты, олардың өткізу қабілетін асырмай жіберуге болатыны шығады. Қосымша жолмен жіберуге болатын ең үлкен ағымның үлкендігін жолдың қалдық өткізу мүкіндігі деп атаймыз. Ол берілген жолға кіретін минималды қалдық қабырғаның мәніне тең болады.

Форд-Фалкерсон әдісінің әр итерациясын орындаған кезде, біз кейбір р үлкейткіш жолын табамыз, және берілген жолдың әр қабырғасының бойындағы f  ағысы с_f (р) қалдық өткізу қабілетінің үлкендігіне жоғарылайды. Бұл тәсілддің жүзеге асырылуы қабырғамен жалғанған әр қос төбе мен v арасыындағы f[u,v]  жаңарту арқылы G = (V, Е) графындағы максималды ағымды есептейді. Егер u және v төбелері ешбір бағытта қабырғамен байлансыпаса, анық емес түрде, f[u, v] = 0 екені болжамдалады. Өткізу қабілетінің мәндері графпен бірге беріледі деп және с (u, v) = 0 деп болжамдалады, егер (u, v) є Е болса. с_f (u, v)  қалдық өткізу қабілеті c_f (u, v) = с (u, v) - f (u, v) формуласы бойынша есептеледі.

Формалды сипаттау

Ford_Fulkerson(G, s, t)

1 for (әр) қабырға үшін (u, v) є E[G]

2 do f[u,v] «-0

3 f[v,u] «- 0

4 while p жолы болады s-тан t-ға G_f қалдық желісінде

5 do сf(р) «— min {c_f(u, v) : (u, v) тиесілі р-ға}

6 for (әр) қабырға үшін (u, v) in p

7 do f[u,v] «- f[u] + c_f(p)

8 f[v,u] «- -f[u,v]

1-3 жолдары f ағымын 0 мәнімен инициалдайды. 4-8 жолдарындағы while циклында G_f –тағы р үлкейтілетін жолының бірнеше іздеуі жүргізіледі, және р жолының бойындағы f ағымы C_f (р) қалдық өткізу қабілетіне жоғарылайды. Жоғарылататын жолдар болмаған кезде, f ағымы максималды болып табылады.

Қиындығын бағалау

Ford_Fulkerson процедурасын орындау уақыты 4 жолындағы р  үлкейтетін жолын іздеудің қалай орындалатына байланысты. Іздеудің сәтсіз әдісінде алгоритм аяқталмауы мүмкін: ағымның үлкендігі жүйеі түрде үлкейіп отырады, бірақ ол ағымның максималды мәніне сәйкес келмеуі де мүмкін.

1-3 жолдарын орындау (Е)-дегі уақытты алады. 4-8 жолдарындағы while циклі |f*| реттен артық емес орындалады, себебі ағым үлкендігі әр итерация үшін, ең болмағанда, бір бірлікке жоғарылайды. Қалдық желідегі жолды іздеу уақыты О (V + Е') = О (Е) құрайды, егер тереңдікке іздеу немесе ені бойынша іздеу пайдаланылса. while циклінің әр итерациясы О (Е) уақытын алады, сондықтан нәтижесінде жалпы орындалу уақыты О(Е|f*|)-ті құрайды, мұнда f* - берілген алгоритммен табылған максималды ағым.

Форда-Фалкерсонның негізгі алгоритмінің жұмысы (while циклінің жүйелі итерациясы). Әр суреттің сол бөлігінде ерекшеленген р үлкейтетін жолымен G_f  қалдық желісі көрсетілген; оң бөлігінде f_р –ны f –қа қосу нәтижесінде пайда болған f жаңа ағымы көрсетілген

5. Хештеу алгоритмімен шешілетін есепке сипаттама беріңіз. Алгоритмді қолданып жалпылама мысал келтіріңіз.

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

В общем случае однозначного соответствия между исходными данными и хеш-кодом нет в силу того, что количество значений хеш-функций меньше, чем число вариантов значений входного массива; существует множество массивов с разным содержимым, но дающих одинаковые хеш-коды-коллизии. Вероятность возникновения коллизий играет немаловажную роль в оценке качества хеш-функций.

Әр түрлі қасиеттермен көптеген хештеу алгоритмдері бар (разрядтылық, есептеу қиындығы және т.б.). Хеш-функцияның қарапайым мысалы ретінде тексеру суммасы мен CRC болып табылады. S қатарынан хеш-функцияны ең оңтайлы анықтау әдісі келесідей:

h(S) = S[0] + S[1] * P + S[2] * P^2 + S[3] * P^3 + ... + S[N] * P^N

P – кез-келген сан.

Хештің негізгі мақсаты long long немесе int64 сандарын ең үлкен сандық типте сақтау. Тармақ ұзындығы бойынша 20 символдан бастап толықтыру басталады. Біз хештің модулін 2^64 алып, бұл толықтыруларға мән бере бермейміз. Егер тек кіші латын әріптері қолданатын болсақ, хешті есептеу мысалы:

const int p = 31;

long long hash = 0, p_pow = 1;

for (size_t i=0; i<s.length(); ++i)

{

// 'a' әрпін қодтан барынша алып тастау

// 'aaaaa' хэші нөлдік болуы үшін тармаққа 1-ді қосып отырамыз

hash += (s[i] - 'a' + 1) * p_pow;

p_pow *= p;}