if(id[I] == t) id[I] = id[q];
printf(“нова връзка”)
}}
Представ. в дърво.
Част II за дървото:
3. Свързаност на обекти – алгоритъм с бързо обединение. Програмна реализация. Анализ и сравнение с алгоритъма за бързо намиране. Представяне в дърво.
Този алг.е базиран на структура данни: ма-сив индексир по имена на обекти. Всеки обект сочи към друг обект от множ. в стру-ктура без цикли.За да определим дали 2 обекта са в едно и също множ. следваме указатели за всеки от тях, докато стигнем до обект,който сочи себе си.Ако не са в ед-но и също множ.,стигаме до разл.обекти, които сочат себе си. За да получим обеди-нение просто свърз.единия към другия.
Програмна реализ. за всяко p и q:
for ( I = p; I != id[I]; I = id[ I ]);
for ( j = q; j != id[ j ]; j = id [ j ]);
if( I == j ) continue; // двата указат. са //еднакви => свързани числа
id[I ] = j; // обединяваме
printf( “ %d %d \n”, p, q);
При обработване двойката p - q ние:
1.следваме указатели от p докато id[I]= = I
2.следваме указатели от q докато id[j]= = j.
3.ако I!= j => id[I] = id[j] => обединението е просто прилепяне към дърво
Анализ и сравнение
Алг.за БО е по бърз от този за БН,защото той не трд минава през целия масив за вся-ка входна двойка. Изпълн.на алг.за БО за-виси в гол.степен от х-ра на входа.Разлика-та м/у бързо обед. и намир. представлява подобрение, но недостатъка е че не може да се гарантира че подобрението в бързи-ната е значително защото вх. данни може да са такива че да направят намир. бавно.
Св-во. За M>N,алг.с БО мд отнеме повече от MN/2 инструкции, за да реши зад. за свързаност с M дв.от N обекта.
Док-во.Ако на вх. двойките идват подреде-ни така: 1-2, 2-3 и т.н След N-1 подобни дв. имаме N обекта в 1 и също множ,а дървото което се получило е права линия. Като N сочи към N -1, N – 1 сочи към N – 2 и т.н. За да изпълни опер.намиране за обекта N прог.трд мине през N-1 указателя. Ср. брой указатели е (N-1) /2. Ако останлите двойки свързват N с някакъв друг обект,опер.на-миране за всяка от тези дв. вкл. поне N – 1 указателя. Общата сума за М-те опер нами-ране за тази последов.от вх. дв е > МN/2
Представ в дърво.
Част II за дървото:
4. Свързаност на обекти – алгоритъм с претеглено бързо обединение. Представяне.
Част II за дървото:
3. Свързаност на обекти – алг. за бързо обединение(БО).Прог.реализ. Анализ и сравн. с алг. за БН. Предст.в дърво √
Този алг.е базиран на структура данни: ма-сив индексир по имена на обекти. Всеки обект сочи към друг обект от множ. в стру-ктура без цикли.За да определим дали 2 обекта са в едно и също множ. следваме указатели за всеки от тях, докато стигнем до обект,който сочи себе си.Ако не са в ед-но и също множ.,стигаме до разл.обекти, които сочат себе си. За да получим обеди-нение просто свърз.единия към другия.
Програмна реализ. за всяко p и q:
for ( I = p; I != id[I]; I = id[ I ]);
for ( j = q; j != id[ j ]; j = id [ j ]);
if( I == j ) continue; // двата указат. са //еднакви => свързани числа
id[I ] = j; // обединяваме
printf( “ %d %d \n”, p, q);
При обработване двойката p - q ние:
1.следваме указатели от p докато id[I]= = I
2.следваме указатели от q докато id[j]= = j.
3.ако I!= j => id[I] = id[j] => обединението е просто прилепяне към дърво
Анализ и сравнение
Алг.за БО е по бърз от този за БН,защото той не трд минава през целия масив за вся-ка входна двойка. Изпълн.на алг.за БО за-виси в гол.степен от х-ра на входа.Разлика-та м/у бързо обед. и намир. представлява подобрение, но недостатъка е че не може да се гарантира че подобрението в бързи-ната е значително защото вх. данни може да са такива че да направят намир. бавно.
Св-во. За M>N,алг.с БО мд отнеме повече от MN/2 инструкции, за да реши зад. за свързаност с M дв.от N обекта.
Док-во.Ако на вх. двойките идват подреде-ни така: 1-2, 2-3 и т.н След N-1 подобни дв. имаме N обекта в 1 и също множ,а дървото което се получило е права линия. Като N сочи към N -1, N – 1 сочи към N – 2 и т.н. За да изпълни опер.намиране за обекта N прог.трд мине през N-1 указателя. Ср. брой указатели е (N-1) /2. Ако останлите двойки свързват N с някакъв друг обект,опер.на-миране за всяка от тези дв. вкл. поне N – 1 указателя. Общата сума за М-те опер нами-ране за тази последов.от вх. дв е > МN/2
Представ в дърво.
Част II за дървото:
4. Свързаност на обекти–алг.с претегле-но бързо обединение(ПБО).Реализация. Анализ. Представяне в дърво. √
За избягване на лоши сл. при алг. за БО е създаден алг.за ПБО. Вместо случайно да се свързва II дърво към I при опер.oбедине-ние,се следят броя на върховете в всяко дърво и винаги свързваме по-малкото дър-. во към по-голямото Промяната изисква ма- лко повече код и още 1 масив, в който се държат броя на върховете, но ефективност-та съществено се подобрява.
Св-во. Алг. проследява най-много 2 lgN указателя за да определи дали 2 измежду N обекта са свързани.
Док-во:за k обекта имаме max lg k указате-ля. След обединение на множ.oт I върха с множ.oт J върха,увелич.броя на указатели-те,които трд се проследят в по-мал.множ. с 1,но сега те са в множ.с размер I+J,така че св-вото е запазено, защото:1+lgI=lg(I+I)<= <=lg(I+J).След N обединения, в най-тежък случай - 2 lg N за всички M двойки - max MlgN инстукции.Много по-добро от МN/2.
За големи числа -почти линеен алг.
възможни подобрения:
1.сплеск на дървото като всеки връх сочи директно корена(чрез смени на указатели)
2. всяко ребро се разглежда 1 път - не е нужно да се помни => спестяване на памет.
Реализация:
#include
#define N 10 000
main()
{ int I, j, p, q, id[N], sz[N];
for(I=0;I
{id[I] = I; sz[ I] = 1;}
while(scanf(“%d %d\n”,&p,&q) == край)
{for( I = p; I != id[ I ]; I = id[ I ]);
for( j = q; j != id[j ]; j = id[ j ]);
if (I == j ) continue;
if( sz [ I ] < sz [ j ])
{ id[ I ] = j; sz[ j ] += sz[ I ];}
else { id[ j ] = I; sz [ I ] += sz[ j ];}
printf ( % d %d \n”, p, q);}}
Представ в дърво:
част II на дървото.
5. Математически основи в анализа на алгоритми. Използвани формули с експоненти, логаритми, редици. Доказателства.
Основните причини,за да извършваме матем.анализ на алг. са:
-за да сравн.разл.алг.за една и съща зад.
-за да предвижд. произв-стта в нова среда
-за да задаваме ст-сти на парам на алг.
Алг.обикновено имат време за работа, пропорц. на една от следните ф-ии(N-главен параметър на нарастване):
1-инструкцията се изпълнява само веднъж или най-много няколко пъти, казваме че времето за работа на алг. е константа
log N-ако времето за работа на алг. е логаритмично,програмата става по-бавна с нарастването на N.Среща се при прог, които решават големи задачи.
N-времето е линейно,когато всеки вх еле-мент се обработва по малко.Както се про-меня N,така се променя и вр. за работа
N logN-такова време за работа се по-лучава,когато алг.решават зад.,като я раз-делят на по-малки подзадачи,решават ги независимо и после обединяват решението
N2-когато времето е квадратично,алг.мд се използва практически само за малки зад. Появява се в алг,в които се обра-ботват всички двойки от данни.
N3-ако алг.обработва тройка от данни,той има кубично вр.за работа,за малки задачи
2N-вр.за работа нараства експоненциално, тези алг.намират малко прилож в п-ката.
Осн.формули,които се използ при работа с експоненти, логаритми и редици са:
1)експоненти-ХАХВ=ХА+В ХА/ХВ=ХА-В ;
ХN +ХN =2(ХN); 2N +2N =2N+1
2)логаритми- XA=B, само ако logx B=A
--T1: loga B= logcB/logc A,при А,В,С>0,А!=1
док: нека Х=logc B; Y=logc A; Z=loga B; тъй като Сх = В,Сy =A, Az =B,то комбинираме: B=Cx = Az =(Cy)z -> X=Y*Z
--T2)logAB=logA+logB; за А,В>0
док:нека X=logA; Y=logB,Z=log AB; за база 2->2x =A,2y =B, 2z=AB->
2x*2y =AB=2z ->X+Y=Z.
3)редици-ΣNi=0 2i=2N+1-1;
ΣNi=0AI=(AN+1-1)/(A-1) при 0<А<1 то ΣNi=0AI<=1/(1-A); при N->безкр.,сумата клони към 1/(1-А)
Док: нека S=1+A+A2+..;тогава АS=A+A2+A3+…;то S-AS=1 и следователно S=1/(1-A)
-аритм.редици ΣNi=1I=(N(N+1))/2 ≈N2/2
и наистина 2+5+8+..(3к-1),което е 3(1+2+..+к)-(1+1+..+1),което е предст.и ка-то(к(3к+1))/2 => ((3к+1)к)/2=3(Х)-к =>
Х=(N(N+1))/2 ,което е ≈N2/2.
ΣNi=1I2=(N(N+1)(2N+1))/6 ≈N3/3
док: вярно за N=1=>вярно и за 1<=к<=N.Правим проверка за N+1:
ΣN+1i=1I2 = ΣNi=1I2+(N+1)2=
(N(N+1).(2N+1))/6+(N+1)2=
(N+1)*[(N(2N+1)/6)+(N+1)]=(N+1)*[(2N2+7N+6)/6]=[(N+1)(N+2)(2N+3)]/6.
Матем.озн,които се срещат във формулите, описващи поведението на алг са:
└х ┘- закръгляне отдолу
┌х┐-закръгляне отгоре
lgN-двоичен логаритъм
lnN-натурален логаритъм
N!-функция факториел
FN—числа на Фибоначи
0 1 1 2 3 5 8 13 21 34 55 ...
дефинирани по формулата
FN=FN-1+FN-2 za N>=2,F0=0,F1=1
HN—хармонични числа
НN=1+1/2+1/3+...+1/N.
6. Въведение в рекурсията. Основни свойства на рекурсията. Типове рекурсии, анализ на производителността и доказателства. Формални техники за преобразуване на рекурсивни в нерекурсивни алгоритми:опашна рекурсия; множествена рекурсия;
Рекурсивен алг.е този,който при изпълн.си се обръща към себе си пряко или косвено поне 1 път.За да реализираме рекурс.алг. използ.рекурс.ф-ии. Има 2 вида рекурсия:
- проста – в тялото си алг.се обръща поне 1 път към себе си пряко,но с др.аргументи, които постеп.намал.и се стига до кр.ст-сти, при които алг.не се обръща към себе си
- взаимна – алг.А1 се обръща на 1 или по-вече места към А2 и обратно. Мд има м/у повече от 2 алг.
Класич.пр.за рекурс.ф-я е факториел.
N!=N(N-1)! , N>=1 с 0!=1.
Int factorial(int N)
{ if (N==0) return 1;
return N*factorial(N-1); }
Рекурс.ф-ии мд дадат сигурност,компакт реализ.Тези ф-ии трд удовл.=>глав. св-ва:
-да реш.изрично осн.сл.(усл.за край)
-всяко рекурс.викане трд вкл.по-малка стойност на аргументите. Пример:
int F (int i)
{ if (i<1) return 0;
if (i==1) return 1;
return F(i-1) + F(i-2)
Рекурс.реализ.на тази зад.е изкл.неефекти-вна.Алг.е с експоненц.време(изкл.мн.повт)
Типове рекурсия и оценки:
А) премахва 1 елемент от N входящи числа при циклично прохождане Cn=Cn-1+N; C1=1
Док: Cn=Cn+1+N=Cn-2+(N-1)+N=
C1.. +2+..N=1+2+…+(N-2)+(N-1)+N=
=[N(N+1)]/2.=>Cn≈N2/2
Б)рекурсии с разполовяване на входния поток на всяка стъпка
Cn=2Cn/2+1 ; C1=1;
Док:некаN=2n(пр.битове за предст.на N)=>
C2n=C2n-1+1= C2n-2+1+1= C2n-3+3=
…=C20+n=n+1 =>
оценката на CN зависи от броя битове, необходими за представяне на N-> lgN
В)рекурсивни програми,разполовяващи входа,но преглеждащи всеки елемент
Cn=Cn/2+N; C1=0 ;
Док: разписва се като N+N/2+N/4+N/8+… =>Оценката е строго пропорц.на вх.->2N
Г)рекурсии с лин.обхождане на входа преди,по време или след разполов.на входа
Cn=2Cn/2+N;C1=0(алг.“разделяй и владей”)
Док: C2n=2C2n-1+2n ; делим на2
->: C2n/2n=[C2n-1/2n-1]+1=[2C2n-2+2n-1]/2n-1+1 =C2n-2/2n-2+2=…=n ->CN=NlgN
7. Оптимизации при взаимна рекурсия;
. Опасности при рекурс.алг. Формални техники за преобразуване на рекурс. в нерекурс.алг:опашнарекурсия,множест-вена рекурсия, рекурсия в средата, алг.решения с взаимна рекурсия
Рекурсивен алгоритъм е този, който решава проблем чрез решаването на един или по-малки екземпляри на същия проблем.За да реализираме рекурсивни алг, използваме рекурсивни функции-рекурсивна функция е тази,която вика себе си.Рекурентни връзки са рекурсивно дефинирани функции. Една рекурентна връзка дефинира функция,чиято деф. област е неотрицателните цели числа или чрез някакви начални стойнос-ти,или (рекурентно) от гледна точка на нейни собствени стойно-ти върху по-малки цели числа.Може би най-известната та-кава функция е функцията факториел,която се декларира чрез рекурентната връзка N!=N(N-1)! , за N>=1, 0!=1.
Ние използваме рекурсия,защото тя често ни помага да изразим сложни алг в ком-пактна форма,без да жертваме ефикас-ност.Но както се оказва много лесно е да напишем проста рекурсивна фунция,която е изключително неефективна и е необх да упражняваме грижата да избягваме да бъ-дем натоварени с труднообработваеми реализации.Ето пример за една рекурсия:
Int f(int x)
{ if (x==0) return 0;
else return (2*f(x-1)+x*x);
} т.е. f(0)=0; f(x)=2f(x-1)+x2 ;
За да използваме рекурсия ние трябва да се съобразяваме с някои правила,напр. За предпочитане е реализация с 1 for(ако е възможно), и никога в 1 стъпка повече от 1 рекурсия,защото тогава възниква опасност от т.нар. множествена рекурсия(като при числата на Фибоначи),f(N)=f(N-1)f(N-2);
пр: voidDoubleCountDown (int N)
{ if(N<=0);
{DoubleCountDown(N-1);
DoubleCountDown(N-1)}
/*времето се удвоява ???
нека имаме означението Т(N) и Т(0)=1; времето на изпълнение се подчинява на формулата:1+2Т(N-1)
N 0 1 2 3 4 10
T(N) 1 3 7 15 31 2047
виждаме Т(N) = 2N+1 – 1->O(2N)
Може също да се получи и индиректна рекурсия:пр. Криви на Шерпшински О(4N). При това се получава разход на памет:
Int BadForMemory()
{ int *x;
GetMemory(x,10 000);
BadForMemory(); }
Съществуват техники на формално преобразуване на рекурс в нерекурс алг.
1)Премахване на опашна рекурсия
procedure Recurse(A: Integer);
begin
//извършва нещо
Recurse(B)
end;
procedure NonRecurse(A: Integer)
begin
while(not done) do
begin
//извършва нещо
A:=B;
end;
end ;
2)Запаметяване на междинни резултати :
пр.: Fibonacci числа: за Fib(29)-> Fib(1) и Fib(0) се изчисляват 832 040 пъти??? Междинните резултати се съхраняват в таблица след първото изчисляване.
3)Подменяне посоката top-down към botton-up(пр. с Fibonacci числа)
При тази техника оценката за алг.на Fibonacci е О(N) за Fib(N) вместо O(Fib(N))
Напр. за Pentium 166 MHz и Fib(40)----155 sec с рекурсивен алгоритъм,докато с тази модификация Fib(1476) се смята за
4)Подмяна на алг.чрез преструктуриране на кода:оформяне proc. за съхраняване на информацията,стъпка и възстановяване:
пр.:procedure Recurse(num:Integer);
begin
Recurse(
)
end ;
преструктурираме:
procedure Recurse(num:Integer);
begin
Recurse(
)
end ;
и procedure Recurse(num:Integer);
var pc:Integer;
begin
pc:=1;
repeat
case pc of
begin
if(базов случай) then pc:=2 //прескачаме еркурсията
else begin //съхраняваме пром. за следрекурсивното викане и рс=2;устано-вяваме пром. нужни при рекурсия (напр. n:=n-1) и преход към начало на рекурсията:
pc:=1; end ; end;
begin
pc:=0; end;
//код след рекурсията
5)алг.промяна при сложни случаи на взаимна рекурсия:пр. криви на Шерпински:
при този случай се оформят отдел-ни процедури с взаимна рекурсия:
SierpA,SierpB,SierpC and SierpD.
Всяка от тях вика останалите,които от своя страна я викат рекурсивно.Всяка служи за изчертаване на горна,лява,долна и дясна част от общата картина .При рекурсивен вариант на всяка процедура оценкатана алгоритмичната сложност е О(4N).
Нерекурсивният вариант на същата прог. е с много по-добра оценка-О(N4),допустима е голяма дълбочина на вложеност,но разбираемостта на кода е по-лоша.
1>
Сподели с приятели: