1. Осн понятия. Варианти на алг. Влия-ние в/у произв-стта. Въведение в анализа Алгоритъм

Друг клас.пример е зад.за Ханойските кули

Дадени са 3 пръчки и N диска с дупки в ср. които мд се надяват на пръчките,дисковете са разл.по размер и първоначално са подре-дени на най-лявата от пръчките в ред най-големия диск(N)долу,най-малкия(1) горе. Зад.е да се преместят дисковете на следв. отдясно пръчка по => правила:

1)само 1 диск се премества в даден момент

2)в/у по-малък диск не мд се пост.по-голям

//Ние премест.кулата от дискове надясно чрез рекурсивно премест.наляво на всички с изкл.на най-долния,после премест.най-долния надясно,след което рекурсивно ме-стим кулата обратно в/у най-долния диск.

void hanoi ( int N, int d)

{ if ( N == 0) return;

hanoi ( N-1, -d);

shift (N, d);

hanoi ( N-1, -d); } //

Тази прог.дава рекурс.реш.на зад.Тя опр. кой диск трдб преместен при всяка стъпка и в коя посока (+ значи премести 1 пръчка надясно,прескачайки циклично към най-лявата,тръгвайки от най-дясната, а – значи 1 пръчка наляво,прескачайки циклично към най-дясната,тръгвайки от най-лявата)

Св-во. Рекурс.алг.разделяй и владей за зад. с Ханойските кули дават реш.с 2^N – 1 мест.

За реш.на Ханойските кули имаме реш.ли-нейно по време според размера на изхода. За Ханойските кули обикн.разгл.реш.като екпоненц.спрямо времето,защото разглежд размера на зад.от гл.т.на броя на дисковете.

Една съществена х-ка на алг.разделяй и владей е,че те разделят зад.на 2 незав.под-зад.Ако обаче подзад.не са незав.,реш.ста-ва по-трудно, защото преките рекурс.реа-лиз.и на най-простите алг.от този тип мд изискват немислимо мн.време.Разглеждаме техники за избягване на този проблем.

Пр. Рекурс.реализ.на Фибоначи

int F (int i)

{ if (i<1) return 0;

if (i==1) return 1;

return F(i-1) + F(i-2) }

Тази прог.,въпреки че е мн.компактна,не е полезна,защото изисква експоненц.време. Броят на рекурс.викания е точно F_N+1, но

F_N ≈ φ^N, където φ ≈ 1.618, златно сечение

Противно на това,лесно мд изчислим с лин. Време F_N с лин.време чрез изчисл.първите числа на Фибоначи и съхр.им в масив.

F[0] = 0; F[1] = 1;

for ( i = 2; i <= N; i++ )

F[i] = F[i-1] + F[i-2];

Мд изпълн.всяка рекурс.ф-я чрез изчисл.на всички функц.ст-сти последов.,започвайки от най-малката,като за всяка стъпка използ. предходните изчисл.ст-сти,за да изчислим текущата ст-ст.такава техника се нар.дина-мично прог.отдолу нагоре. Динамич.прог. отгоре надолу е по-прост поглед на техн, която позволява да изчисл.рекурс.ф-ии по автомат.н-н за същата цена(и по-малка). Тук даваме възмож.на прог.да съхранява всяка изчисл.ст-ст и да проверява съхране-ните ст-сти,за да избегне преизчисл.

int F (int i)

{int t;

if (i==0) t = 0;

if (i==1) t = 1;

if (i > 1) t = F[i-1] – F[i-2];

return known F[i] = t; }

Св-во. Динам.прог.редуцира времето за из-пълн.на 1 рекурс.ф-я дб max времето за из-пълн.на ф-ята за всички аргументи <= на даден арг.,третирайки разхода за рекурс. обръщение,като константа.

Предпочитаме дин.прог. отгоре надолу,защ

- то е механич.трансформ.на ест.реш.на зад

- редът на изчисл.на подзад.се спазва

- мд не е необх.да се реш.всички подзад.

Дин.прог.става неефективно,когато броят на възмож.функц.ст-сти,от които би могло да се нуждаем,стане толкова голям,че не мд си позволим да ги съхр.или изчислим

Дефиниращо св-во за дърво е,че има само 1 път свърващ всеки 2 възела.Ако има >1 път м/у 2 възела,тогава имаме граф.

Всеки възел,освен корена има точно 1 възел над себе си,родител,възлите директ-но под него се нар.негови деца.Възлите без деца,се нар.листа.

Ако всеки възел има опр.брой деца,явява-щи се в опр.ред,тогава имаме М-арно дър-во.Най-простият пр.е бинарното дърво.

Деф.Бинарно дърво е или външен възел или вътр.възел,свързан към чифт бинар.дъ-рвета,които се нар.ляво и дясно поддърво.

Представянето,което използ.за реализ.на прог.използващи бинар.дървета е структу-ра с 2 връзки за вътрешни възли.Подобни са на свърз.списъци,но имат 2връзки на въ-

зел,вместо 1.

typedef struct node *link

struct node { Item item; link l, r; }

Връзките са указатели към възли,а всеки възел се съст.от елем.и чифт връзки.

Деф.1 М-арно дърво е или външен възел или вътр.възел,свързан с наред.последов. от М-арни дървета

Деф.Наредено дърво е възел,нар.корен,свъ-рзан към последов.от несвърз.дървета.

Разликата м/у наредено дърво и М-арно дърво е,че възлите в наредените дърв.мд имат всякакъв брой деца,а М-арно дърво трд има точно М деца.

Деф.Дърво с корен(ненаредено дърво) е възел,нар.корен,свърз.към мултим-во от дървета с корени.

Деф.Граф е м-во от възли и ребра,които свърз.двойки разл.възли. Последов.от реб-ра,водеща от 1 възел към друг,като никой възел не се среща 2 пъти,се нар.прост път.

Графът е свързан,ако същ.прост път свърз-ващ всяка двойка възли.Път,който е прост, с изкл.на 1-я и посл.възел,които са еднакви се нар.цикъл. Един граф е дърво,ако удовл. едно от => усл.

- има N-1 ребра и няма цикли

- има N-1 ребра и е свързан

- точно 1 път свързва всяка двойка върхове

- свързан е,но не остава такъв,ако махнем 1 от ребрата

Св-во'>18.Матем.св-ва на двоичните дървета

Св-во. Бинарно дърво с N вътр.възела има N+1 външни възела

Док.се по индукция.Бин.дърво без вътр.въ-зли има 1 външ.възел=>изпълн.за N=0.

За N>0,всяко бин.дърво с N вътр.възли има К вътр.възли в лявото си поддърво и N-K-1

вътр.възли в дясното си поддърво,за К м/у 0 и N-1,тъй като коренът е вътр.възел.Спо-ред индукц.хипотеза,лявото поддърво има К+1 външ.възли,а дясното->N-K=>сум.N+1

Във вс.дърво с корен вс.възел освен корена има 1родител,а вс.ребро свързва възел с не-говия родител,така че има N-1 ребра,свърз. вътр.възли.Подобно вс.от N+1 външни възела има по 1 ребро към своя родител.

Деф.Нивото на възел в дърво е > от нивото на неговия родител.

Височина на дърво е max от нивата на въз.

Дължина на вътр.пътища в бинар.дърво е сума от нивата на вътр.му възли

Дължина на външ.пътища в бинар.дърво е сума от нивата на външ.му възли

Тези деф.са пряко свърз.с анализа на алг.

Св-во. Дълж.на външ.пътища в вс.бинар. дърво с N вътр.възела е с 2N по-гол. от дълж.на външ.пътища-Док.се по индукция

Св-во. Височ.на бинар.дърво с N вътр.въ-зела е >= от lgN и <= N-1

Док.Най-лошия сл.е дегенерирано дърво с 1листо,с N-1 връзки от корена до листото. Най-добрият сл.е балансирано дърво с 2 ⁱ

вътр.възли за всяко ниво i,освен за най-до-лното.Ако височ.е h,трд имаме:

2 ^h-1 < N+1 <= 2 ^h

Тъй като имаме N+1 външ.възела. Височ. в най-добрия сл.ще е = lgN

Св-во. Дълж.на вътр.пътища в бинар. дър-во с N вътр.въз.е>=Nlg(N/4) и <=N(N-1)/2

Бинар.дърв.се появяват мн.често в комп. прилож.и произв-стта е best при баланс.дър

Ще разгл.алг.за най-осн.обработваща дърв. ф-я:обхождане.При бин.дърв.имаме 2 връз-ки=>3 осн.последов.,по които да посет.въз.

- преред – посещ.възела,после лявото и дясното поддърво

- поред – посещ.лявото дърво,после възела и накрая дясното поддърво

- постред – посещ.лявото и дясното поддъ-рво и после възела

Тези 3 метода са за обхожд.в дълбочина.Те мд се реализ.чрез рекурс.прог:

void traverse (link h, void ( *visit)(link))

{ if h==NULL) return;

(*visit)(h);

traverse (h->l, visit);

traverse (h->r, visit); }

Тази рекурс.ф-я взема връзка към дърво ка-то арг.и вика ф-ята visit с арг.всеки от въз-лите на дървото.Ф-ята реализ.прередно об-хождане.Ако премест.викането на visit м/у рекурс.обръщ.,имаме поредно обхожд., а ако премест.след тях,имаме постред.обхож.

При използ.на нерекурс.,които използ.стек, правим опер.за вмъкване на дървото,които зав.от желаната последов.на обхожд:

- преред – вмък.в стека дясното поддърво после лявото и накрая възела

- поред – вмък.в стека дясното поддърво, после възела и накрая лявото поддърво

- постред – вмък.в стека възела,после дяс-ното поддърво и накрая лявото поддърво.

В стека не се вмък.нулевите връзки.

Друга стратегия за обхожд.е просто да по-сещаваме възлите отгоре надолу и отляво надясно – обхождане в широчина,защото вс.възли от дадено ниво се появяват заедно

void traverse (link h, void ( *visit)(link))

{ QUEUEinit(max); QUEUEput(h);

while ( !QUEUEempty())

{ (*visit)(h = QUEUEget());

if (h->l != NULL) QUEUEput (h->l);

if (h->r != NULL) QUEUEput (h->r);} }

При графите обхожд.се осъщ.рекурс. или се нар.още търсене в дълбочина.Това е прост рекурс.алг.Започв.от възел V,ние:

- посещаваме V;

- рекурс.посещ.вс.непосет.въз,достиж.от V

За да посетим вс.възли,свърз.към възел K в граф,ние го маркираме лкато посетен и то-гава рекурс.посещаваме вс.непосетени въз-ли от списъка на съседство на К.

void traverse (int k, void ( *visit)(int))

{ link t;

(*visit)(k); visited[k] = 1;

for ( t = adj[k]; t != NULL; t = t -> next)

if ( !visited[t->v]) traverse ( t ->v, visit); }

Разл.м/у търс.в дълбоч.и обобщ.обхожд.на дърво е,че е необх.да се предпазим изрич-но от посещ.на вече посетени възли.

Ако използ.опашка вместо стек,тогава има-ме търс.в широч.,което е аналогично на об-хождане в широч.на дърво.

Напр.за да посетим вс.възли,свърз.към въ-зел К в 1 граф,вмък.в К в опашка FIFO,по-сле влизаме в цикъл,където е следв.възел от опашката и ако не е посетен,го посеща-ваме и вмък.в опашката вс.непосетени въз-ли от списъка му на съседство.

void traverse (int k, void ( *visit)(link))

{link t;

while ( !QUEUEempty())

if (visited[k=QUEUEget()] == 0)

{(*visit)(k); visited[k] = 1;

for ( t = adj[k]; t != NULL; t = t -> next)

if (visited[t->v]==0) QUEUEput (t->v);} }

Бин.дърв.мд се обхождат по няколко н-на:

- преред – посещ.възела,после лявото и дясното поддърво

- поред – посещ.лявото дърво,после възела и накрая дясното поддърво

- постред – посещ.лявото и дясното поддъ-рво и после възела

-както и в широчина

Често е необх.да намерим ст-стите на разл. структурни парам.за 1 дърво,само по даде-на връзка връзка към дървото.Следв.прог. съдържа рекурс.ф-ии за изчисл.броя на въ-злите и височината на дадено дърво.

int count (link h)

{ if ( h==NULL ) return 0;

return count (h->l) + count (h->r) + 1;}

int height ( link h )

{ int u,v;

if ( h == NULL ) return -1;

u = height ( h->l ); v = height ( h->r);

if ( u > v ) return u+1; else return v+1; }

Др.ф-я ни показва рекурс.алг.за обхождане на дърво е този за отпечатване на дърво. Ако отпеч.елемента преди рекурс.викане, получаваме прередно обхожд.Тази прог.до-пуска че елем.в възлите са символи:

void printnode ( char c, int h )

{ int i;

printf (“%c\n”, c); }

void show ( link x, int h )

{ if ( x==NULL) {printnode(‘*’,h); return; }

show (x -> r, h+1);

printnode (x -> item, h);

show (x ->l, h+1); }

21.Елементарни сортировки. Селект. сортировка. Сортиране чрез вмъкване

В много сортиращи прил. е възм. метода. к-то тр. да се избер. да е прост. алгорит. Поради сл. причини: 1 – во. Често сорт. прог. се изп. само веднъж и ако елем. сорт. не е по – бавна от др. части на прогр. не е нужно да се търси по – бърз метод. Ако бр. на сорт ел. не е мн. гол.(до няк. 100) също може да се избере пост метод. 2 – ро. Елементар. сорт са по удобни за малки фаилове. Бав. методи са добри също за почти сортирани фаилове. или такива които съдърж.голям бр.повтар. се ключове.

void selection (Item a[], int l, int r)

{ int i, j;

for (i = l; i< r; i++)

{ int min = i;

for (j = i+l; j <= r; j++)

if (less(a[j], a[min])) min = j;

exch (a[i], a[min]);

}}

Вътр. цикъл представлява само сравнение, за да провери текущия елем. с намер. наи малък. Вънщният цик. разменя елем. Броят на размените е N -1. Времето на изпълн. се доминира от бр. на размен. Този брой е пропорц на N квадр.Недостатък на сорт. е че вр. за изпълн зависи съвсем малко от вече подредените елем. Методът е добър за сортир. на фаилове с огромни елем. и малки ключове.

Този метод работи по сл. начин: елем. се разглеждат един по един вмъкв. всеки от тях на подходящ. място. сред вече сортир.(запазваики ги по този начин сортирани). Необходимо е да се направи място за вмъквания елем., като преместв. по – гол. елем с 1 поз надясно и после вмъкв. елем. във вакантната. поз.

void insertion(Item a[], int l, int r)

{ int i;

for (i = r; i >l; i--) compexch (a[i-1], a[i]);

for (i = l+2; l<=r; i++)

{ int j = i; Item v = a[i];

while (less(v, a[j-1]))

{ a[j] = a[j-1]; j--; )

a[j]= v; }}

Програмата първо поставя най – малкият елем.на мас. на 1 –ва поз. , така че този елем. да служи като ограничител. Във бтр цикъл тя прави просто присвояване в место размяна. Прогр. завърщ. втр. цикъл., корато вмъкв. елем. е в същата позиция. За всяко i тя сортира елем. a[i]…..a[i-1], които са по – гол. от а[i], след което поставя a[i] в подходяща позиция.

Преминава се през файла като разменяме съседните елем. които не са подредени,. Деиствието продължава докато фаила не се сортира. Главн. предимство на тази сорт. е лесното и реализиране. Но тя е по – бавна от селективната сорт. и сорт. чрез вмъкване.

Сортировк се извърщва на N паса.

Пример с числа.



Програмна реализация

void bubble (Item a[], int l, int r)

{ int i, j;

for (i = l; i

for (j = r; j>i; j--)

comexch(a[j-1], a[j]);

}

За всяко i от l до r-1 вътр. цикъл намира мин елем. сред елем a[i],…, a[r] чрез преминаване през тях от дясно на ляво, сравнявайки и евентуално разменяики последоват елем. и така го поставя в поз. a[i]. Най – малкият елем. минава през всички – така тои изплува като мехурче в началото на масива.

Селект. сорт, сорт чрез вмъкване и сорт по метода на мехурчето са алгоритми с квадратично вр. за изпълн. и за най – лошия , и за ср. сл. не изискват. допълн памет. В общия сл. времето за испълн. на алгор.за сорт е пропорц на бр. на сравн. които използва, на бр. пъти за които елем. се местят или разместват. или на двете.

Метод. на мехурчето и сорт. чрез вмъкване работят добре за неслучайни фаилове, които често се появяват в практиката. Общоцелеви сорт. обикновено са неизползв за такива прил.

Разгл. действието на сортировк чрез вмъкване за вече сортиран фаил. Всеки елем. моментално се определя, че е на нужното място в файла и общото време за изпълнение е линейно. Същото е вярно и за сортировка по мет. на мехурчето.

Деф. Инверсия е дв. ключове, които не са в необходим ред в файла.

Св. Сорт. чрез вмъкване и по метода на мехурчето изискват линеен брои сравнения и размени за фаилове с най – мн. константен. брой инверсии, съответни на всеки елемент.

Сортировката чрез вмъкване е подходяща за почти сортиране файлове, където трябва да се добявят няколко елем. Докато метода на мехурчето и селект. сортировка не са.