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

  if (I == j ) continue;

Основните причини,за да извършваме матем.анализ на алг. са:

-за да сравн.разл.алг.за една и съща зад.

-за да предвижд. произв-стта в нова среда

-за да задаваме ст-сти на парам на алг.

Алг.обикновено имат време за работа, пропорц. на една от следните ф-ии(N-главен параметър на нарастване):

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

log N-ако времето за работа на алг. е логаритмично,програмата става по-бавна с нарастването на N.Среща се при прог, които решават големи задачи.

N-времето е линейно,когато всеки вх еле-мент се обработва по малко.Както се про-меня N,така се променя и вр. за работа

N logN-такова време за работа се по-лучава,когато алг.решават зад.,като я раз-делят на по-малки подзадачи,решават ги независимо и после обединяват решението

N²-когато времето е квадратично,алг.мд се използва практически само за малки зад. Появява се в алг,в които се обра-ботват всички двойки от данни.

N³-ако алг.обработва тройка от данни,той има кубично вр.за работа,за малки задачи

2^N-вр.за работа нараства експоненциално, тези алг.намират малко прилож в п-ката.

Осн.формули,които се използ при работа с експоненти, логаритми и редици са:

1)експоненти-Х^АХ^В=Х^А+В Х^А/Х^В=Х^А-В ;

Х^N +Х^N =2(Х^N); 2^N +2^N =2^N+1

2)логаритми- X^A=B, само ако log_x B=A

--T1: log_a B= log_cB/log_c A,при А,В,С>0,А!=1

док: нека Х=log_c B; Y=log_c A; Z=log_a B; тъй като С^х = В,С^y =A, A^z =B,то комбинираме: B=C^x = A^z =(C^y)^z -> X=Y*Z

--T2)logAB=logA+logB; за А,В>0

док:нека X=logA; Y=logB,Z=log AB; за база 2->2^x =A,2^y =B, 2^z=AB->

2^x*2^y =AB=2^z ->X+Y=Z.

3)редици-Σ^N_i=0 2ⁱ=2^N+1-1;

Σ^N_i=0A^I=(A^N+1-1)/(A-1) при 0<А<1 то Σ^N_i=0A^I<=1/(1-A); при N->безкр.,сумата клони към 1/(1-А)

Док: нека S=1+A+A²+..;тогава АS=A+A²+A³+…;то S-AS=1 и следователно S=1/(1-A)

-аритм.редици Σ^N_i=1I=(N(N+1))/2 ≈N²/2

и наистина 2+5+8+..(3к-1),което е 3(1+2+..+к)-(1+1+..+1),което е предст.и ка-то(к(3к+1))/2 => ((3к+1)к)/2=3(Х)-к =>

Х=(N(N+1))/2 ,което е ≈N²/2.

Σ^N_i=1I²=(N(N+1)(2N+1))/6 ≈N³/3

док: вярно за N=1=>вярно и за 1<=к<=N.Правим проверка за N+1:

Σ^N+1_i=1I² = Σ^N_i=1I²+(N+1)²=

(N(N+1).(2N+1))/6+(N+1)²=

(N+1)*[(N(2N+1)/6)+(N+1)]=(N+1)*[(2N²+7N+6)/6]=[(N+1)(N+2)(2N+3)]/6.

Матем.озн,които се срещат във формулите, описващи поведението на алг са:

└^х ┘- закръгляне отдолу

┌_х┐-закръгляне отгоре

lgN-двоичен логаритъм

lnN-натурален логаритъм

N!-функция факториел

F_N—числа на Фибоначи

0 1 1 2 3 5 8 13 21 34 55 ...

дефинирани по формулата

F_N=F_N-1+F_N-2 za N>=2,F₀=0,F₁=1

H_N—хармонични числа

Н_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 входящи числа при циклично прохождане C_n=C_n-1+N; C₁=1

C₁.. +2+..N=1+2+…+(N-2)+(N-1)+N=

=[N(N+1)]/2.=>C_n≈N²/2

Б)рекурсии с разполовяване на входния поток на всяка стъпка

C_n=2C_n/2+1 ; C₁=1;

Док:некаN=2ⁿ(пр.битове за предст.на N)=>

C₂ⁿ=C₂^n-1+1= C₂^n-2+1+1= C₂^n-3+3=

…=C₂⁰+n=n+1 =>

оценката на C_N зависи от броя битове, необходими за представяне на N-> lgN

В)рекурсивни програми,разполовяващи входа,но преглеждащи всеки елемент

C_n=C_n/2+N; C₁=0 ;

Г)рекурсии с лин.обхождане на входа преди,по време или след разполов.на входа

C_n=2C_n/2+N;C₁=0(алг.“разделяй и владей”)

Док: C₂ⁿ=2C₂^n-1+2ⁿ ; делим на2

->: C₂ⁿ/2ⁿ=[C₂^n-1/2^n-1]+1=[2C₂^n-2+2^n-1]/2^n-1+1 =C₂^n-2/2^n-2+2=…=n ->C_N=NlgN

Рекурсивен алгоритъм е този, който решава проблем чрез решаването на един или по-малки екземпляри на същия проблем.За да реализираме рекурсивни алг, използваме рекурсивни функции-рекурсивна функция е тази,която вика себе си.Рекурентни връзки са рекурсивно дефинирани функции. Една рекурентна връзка дефинира функция,чиято деф. област е неотрицателните цели числа или чрез някакви начални стойнос-ти,или (рекурентно) от гледна точка на нейни собствени стойно-ти върху по-малки цели числа.Може би най-известната та-кава функция е функцията факториел,която се декларира чрез рекурентната връзка 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)+x² ;

За да използваме рекурсия ние трябва да се съобразяваме с някои правила,напр. За предпочитане е реализация с 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) = 2^N+1 – 1->O(2^N)

Може също да се получи и индиректна рекурсия:пр. Криви на Шерпшински О(4^N). При това се получава разход на памет:

Int BadForMemory()

{ int *x;

GetMemory(x,10 000);

BadForMemory(); }

Съществуват техники на формално преобразуване на рекурс в нерекурс алг.

1)Премахване на опашна рекурсия

procedure Recurse(A: Integer);

begin

//извършва нещо

end;

begin

begin

A:=B;

end ;

пр.: 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