W1 Rzedy wielk i rekur, szkoła, Matematyka Dyskretna, Wykłady
[ Pobierz całość w formacie PDF ]
//-->“Matematyka Dyskretna”dr Stefan GrabowskiStefan.Grabowski@owsiiz.edu.plLiteratura:1.Kenneth A.Ross, Charles R.B.Wright -Matematyka dyskretna,PWNWarszawa 20002. Ronald L.Graham, Donald E.Knuth, Oren Patashnik -MatematykaKonkretna, PWN Warszawa 20013. Thomas H.Cormen, Charles E.Leiserson, Ronald L.Rivest -Wpraowadzenie do algorytmów.WNT, Warszawa, 19974. Maciej M.Sysło, Narsingh Deo, Janusz S.Kowalik -Algorytmyoptymalizacji dyskretnej.PWN, Warszawa, 19955. Pałka Zbigniew, Ruciński Andrzej – Wykłady z kombinatoryki, WNT6. Gra yna Mirkowska -Elementy matematyki dyskretnej,Polsko-Japońska Wy sza Szkoła Technik Komputerowych, 2003W-1, Matematyka dyskretna1Porównywanie wielkości - notacja a ymptotycznaΘ- dokładnie rzędu (asymptotycznierównowa ne)f(n) =Θg(n)fjest dokładnie rzędug(n)lubf(n)≅g(n)fjest asymptotycznie równowa neg(n)istnieją stałe dodatniec1,c2oraz liczba naturalnan, takie e dlaka degon>njest spełniona nierówność≤c1g(n)≤f(n)≤c2g(n)Przykłady:n(n+1)/2=Θ(n2)5n3+ 2n2+n=Θ(n3)O- co najwy ej rzędu( asymptotyczna granica górna)f(n) =O(g(n))fjest conajwy ej rzędug(n)( asymptotyczna granica górna)istnieje stała dodatniacoraz liczba naturalnan, takie zedla ka degon>njest spełniona nierówność≤f(n)≤cg(n)Ω- co najmniej rzędu(asymptotyczna granica dolna)f(n) =Ω(g(n))fjest conajmniej rzędug(n)(asymptotyczna granica dolna)istnieje stała dodatniacoraz liczba naturalnan, takie ze dla ka degon≥njest spełniona nierówność≤c g(n)≤f(n)Przykłady: an2+5n=Ω(n),(an + lnn)2-n2=Ω(n lnn)Twierdzenie:f(n)≅g(n)wtedy i tylko wtedy ,gdyf(n) =O(g(n)) i jednocześnief(n) =Ω(g(n)).Przykłady:3n + (a−2)n2=O(n2)(2n + lnn)2=O(n2)W-1, Matematyka dyskretna2o- rzędu ni zego( pomijalnie mała)f(n) =o(g(n))fjest rzędu ni szego nig(n)(fpomijalnie mała w stosunku dog(n))dla ka dej stałej dodatniejcistnieje liczba naturalnantaka, ze dlaka degon>njest spełniona nierówność≤f(n)≤c g(n)Przykłady:2n(n+5) - 2n2=o(n2)lnn=o(n3)Porównanie rzędów wielkości przez obliczenie granicyRzędy wielkości liczb często wygodnie jest określać przez obliczeniegranicy.E= lim (f (n) /g(n))przyn→ ∞E= +∞E=c>0E= 0tog(n) =o( f(n))g(n) =O(f(n))tof(n) =Θg(n)tof(n) =o(g(n)f(n) =O(g(n))ale nief(n) =O(g(n))( lub inaczej:f(n)≅g(n))ale nieg(n)=O(f(n))=n3/3 +O( n2)=n(n+1)(2n+1)/61 + 25+ 35+ ... +n5=Θ(n6) =n6/6 +O( n5)Hn= 1 + 1/2 + 1/3 + ... + 1/n =Θ(ln(n))= ln(n) +O(1 ) = ln(n) +γ+O( 1/n )gdzieγ-stała Euleraiγ= 0,577215664...Przykłady zastosowań1 + 22+ 32+ ... +n2=Θ(n3)W-1, Matematyka dyskretna3Przykłady liczbowe :nHn−(lnn+γ)103050701004,9⋅10-21,7⋅10-21,0⋅10-27,1⋅10-35⋅10-3Wzór Stirlingan!= (2πn)1/2(n/e)n(1 +O(1/n))Przykłady liczbowe :δ(n)- błąd względny in!ze wzoru Stirlinga gdy pominięteO(1/n)nδ(n)53050701001,6⋅10-22,8⋅10-31,7⋅10-31,2⋅10-38,3⋅10-4Porządkowanie wyra eń ze względu na rząd wielkościOznaczenia(umowa):lnx= loge(x)lgx= log2(x)Uporządkowanie w zale ności od rzędów (od najni szego).logn- logarytmicznan- liniowanlog n- liniowo - logarytmicznan2- kwadratowan3- sześciennan2,n3- ogólnie: wielomianowanlogn- podwykladnicza2n- wykładnicza 2nn!- wykładniczan!Pułapkia)f(n) = nlog ng(n) = 20n - obliczenia dlan< 32000b)ls=asnlog n+O(n)as= 2/loge≈1,4lw=n2/4 +O(n).- obliczenia dlan=1000in=16W-1, Matematyka dyskretna4Równania rekurencyjneRozpatrzymy typy:1.T(n)w zale ności oda)T(n-1)b)T((n-1)/2)(ogólniej (T(n-1)/b))2.T(n)w zale ności odT(n-1)iT(n-2)Rozwiązanie równania - wyznaczenieT(n)w postaci jawnejOznaczenia:- "podłoga" - zaokrąglenie do liczby całkowitej w dół- "sufit" - zaokrąglenie do liczby całkowitej w górę1. zadanie (n)zadanie(n-1)T(1)=ppznaneT(n)=g(n)*T(n-1)+f(n)Przykłady:Zło oność obliczeniowaa) Obliczanie wyznacznika metodą Laplace'aT(1)= 0T(n)=n*T(n-1)+nb) Rozwiązanie układu równań o macierzy trójkątnejT(1)= 1T(n)=T(n-1)+nRozwiązaniaa)T(1)= 0T(n)=n*T(n-1)+nT(n)=n*T(n-1)+n==n*[(n-1)T(n-2)+ (n-1)] +n==n(n-1)*T(n-2)+n(n-1)+n==n(n-1)[(n-2)*T(n-3)+ (n-2)] +n(n-1)+n==n(n-1)(n-2)*T(n-3)+n(n-1)(n-2)+n(n-1)+n=W-1, Matematyka dyskretna5 [ Pobierz całość w formacie PDF ] |