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



страница1/5
Дата31.12.2017
Размер0.81 Mb.
  1   2   3   4   5
1. Основни понятия. Варианти на алгоритми. Влияние върху производителността. Въведение в анализа
Алгоритъм – формализирана методика за решаване на една задача. Лесно съпоста-вима с езиците за програмиране. Преди алгоритмиране трябва да имаме представа за данните и организацията им. Алг.за ре-шаване на дадена задача е последовател-ност от инструкции, всяка от които показва каква операция ще се извърши,с какви ар-гументи,с какъв резултат.Ефективността му зависи от времето за неговото изпълн. Важна е и последователността на изпълн.

Инструкциите биват:

-безусловни-можем да преминем към следващата инструкция без условие

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

Тази последователност от инструкции е алгоритъм,ако те реализират функциона-лна зависимост.Условно мд представим алг.като граф:възлите са инструкции (операции),а стрелките сочат следващата операция.Има начало и край



Свойства:

-Детерминантност - резултатите получени от дадена стъпка, трябва да се определят еднозначно от резултатите в предишните стъпки;при еднакви вх.данни за всяка стъпка трябва да има еднакви резултати.Ако това свойство се наруши-алгоритъмът става вероятностен(от краен брой стойности случайно се избира една).Всяка инструкция има код (КОП) и адрес,с които се указва.



-Крайност(финитност)-алг.и всяка негова стъпка се изпълняват за крайно време

-Дискретност- алг.във времето се изпълнява на интервали.В отделни моменти от интервала нямаме резултат.Това не е така при аналоговите устройства-при тях процесите протичат непрекъснато и м/у 2 момента мд имаме безкрайно много ст-сти,но точността е малка.Числата,с които работи ЦИМ се представят в краен интервал,в който мд представим краен брой стойности.



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

-Резултатност- всеки алг.дава множество от резултати. експериментален и аналити-чен начин за проверка верността на алг.



Видове:

1. според структурата:

неразклонени (линейни)- всички постъпили входни данни, се обработват по един и същ начин

разклонени-дават възможност за реализация на произволен алгоритъм

2. според това дали могат едновременно да се изпълняват инструкциите:

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

паралелни- в даден момент се изпълняват повече инструкции

3. според вероятността:

точни-изследват всички възможни случаи и дава оптимален резултат

приблизителни-изледва само случаите, които водят до оптимален резултат
2. Примерна задача – свързаност на обекти. Дефиниране на абстрактни операции в задачата. Начален алгоритъм. Алгоритъм за бързо намиране. Програмна реализация. Представяне в дърво.

Дадена е послед.от цели числа, всяко число представлява някакъв обект. Записът p – q означава p e свързано с q. Връзката е тран-зитивна,т.е ако p - q и q – r, то p - r. Иска се да премахнем ненужните двойки от множ., т.е.когато в прог.се въведе двойка p – q, тя трд я изведе само ако според досега въве-дените двойки p не е свърз. с q. Зад.ни е да се направи прог.която помни дост. инф. за постъпилите двoйки до момента и може да прецени дали има нова връзка м/у обекти.В зад.се иска да знае дали опр.двойка е свър-зана,а не да покаже 1 или всички пътища, които я свързват.Намира важни прил.напр. връзки в компютърна,ел.мрежа и др.______

От теорията на графите => N обекта са свързани ,когато има точно N – 1 изведени двойки в алг.на свързаност.

Св-во. Алг.с бързо намиране изпълнява поне MN инструкции,за да реши зад за свърз с N обекта,която вкл. M обединения

Абстрактни операции, необх. за алг. -

Намиране и Обединение

След като прочетем нова двойка p – q от входа,изпълн.опер.намиране за всеки член на двойката. Ако те са в едно множество, минаваме на следв.двойка. Ако не са, пра-вим опер.обединение и извежд. двойката



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

Алгоритъм за бързо намиране(БН)

P q 0 1 2 3 4 5 6 7 8 9

3 4 0 1 2 4 4 5 6 7 8 9

4 9 0 1 2 9 9 5 6 7 8 9

8 0 0 1 2 9 9 5 6 7 0 9

2 3 0 1 9 9 9 5 6 7 0 9

5 6 0 1 9 9 9 6 6 7 0 9

2 9 0 1 9 9 9 6 6 7 0 9

5 9 0 1 9 9 9 9 9 7 0 9

7 3 0 1 9 9 9 9 9 9 0 9

4 8 0 1 0 0 0 0 0 0 0 0

0 2 0 1 0 0 0 0 0 0 0 0

5 6 0 1 0 0 0 0 0 0 0 0

6 1 1 1 1 1 1 1 1 1 1 1

Осн. на този алг е масив с цели числа с св- вото,че p и q са свърз ,когато p и q ел. в масива са ≡.За да изпълним обедин p и q минаваме през масива като променяме вси-чки клетки с същата ст-ст като p да имат същата ст-ст като q.



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

#include

#define N 10 000

main ()

{ int I, p, q , t, id[N];

for( I = 0; I < N; I++) id[I] = I;

while(scanf(“%d, %d \n”, &p,&q) == край

{

if( id[p] == id[ q ] )continue;

for( t = id[p], I = 0; I

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)експоненти-ХАХВА+В ХАВА-В ;

ХNN =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   2   3   4   5


База данных защищена авторским правом ©obuch.info 2016
отнасят до администрацията

    Начална страница