W1_Rzedy_wielk_i_rekur.pdf

(167 KB) Pobierz
“Matematyka Dyskretna”
dr Stefan Grabowski
Stefan.Grabowski@owsiiz.edu.pl
Literatura:
1.Kenneth A.Ross, Charles R.B.Wright -
Matematyka dyskretna,
PWN
Warszawa 2000
2. Ronald L.Graham, Donald E.Knuth, Oren Patashnik -
Matematyka
Konkretna
, PWN Warszawa 2001
3. Thomas H.Cormen, Charles E.Leiserson, Ronald L.Rivest -
Wpraowadzenie do algorytmów.
WNT, Warszawa, 1997
4. Maciej M.Sysło, Narsingh Deo, Janusz S.Kowalik -
Algorytmy
optymalizacji dyskretnej.
PWN, Warszawa, 1995
5. Pałka Zbigniew, Ruciński Andrzej – Wykłady z kombinatoryki, WNT
6. Gra yna Mirkowska -
Elementy matematyki dyskretnej
,
Polsko-Japońska Wy sza Szkoła Technik Komputerowych, 2003
W-1, Matematyka dyskretna
1
Porównywanie wielkości - notacja a ymptotyczna
Θ
- dokładnie rzędu (asymptotycznie
równowa ne)
f
(n) =
Θ
g(n)
f
jest dokładnie rzędu
g(n)
lub
f
(n)
≅
g(n)
f
jest asymptotycznie równowa ne
g(n)
istnieją stałe dodatnie
c
1
,
c
2
oraz liczba naturalna
n
0
, takie e dla
ka dego
n
>
n
0
jest spełniona nierówność
0
≤
c
1
g(n)
≤
f
(n)
≤
c
2
g(n)
Przykłady:
n(n+1)/2
=
Θ
(n
2
)
5n
3
+ 2n
2
+
n
=
Θ
(n
3
)
O
- co najwy ej rzędu
( asymptotyczna granica górna)
f
(n) =
O
(g(n))
f
jest conajwy ej rzędu
g(n)
( asymptotyczna granica górna)
istnieje stała dodatnia
c
oraz liczba naturalna
n
0
, takie ze
dla ka dego
n
>n
0
jest spełniona nierówność
0
≤
f
(n)
≤
c
g(n)
Ω
- co najmniej rzędu
(asymptotyczna granica dolna)
f
(n) =
Ω
(g(n))
f
jest conajmniej rzędu
g(n)
(asymptotyczna granica dolna)
istnieje stała dodatnia
c
oraz liczba naturalna
n
0
, takie ze dla ka dego
n
≥
n
0
jest spełniona nierówność
0
≤
c g(n)
≤
f
(n)
Przykłady: an
2
+5n
=
Ω(n),
(an + ln
n)
2
-
n
2
=
Ω
(n ln
n)
Twierdzenie:
f
(n)
≅
g(n)
wtedy i tylko wtedy ,
gdy
f
(n) =
O
(g(n)) i jednocześnie
f
(n) =
Ω
(g(n)).
Przykłady:
3n + (a
−
2)n
2
=
O
(n
2
)
(2n + ln
n)
2
=
O
(n
2
)
W-1, Matematyka dyskretna
2
o
- rzędu ni zego
( pomijalnie mała)
f
(n) =
o
(g(n))
f
jest rzędu ni szego ni
g(n)
(
f
pomijalnie mała w stosunku do
g(n)
)
dla ka dej stałej dodatniej
c
istnieje liczba naturalna
n
0
taka, ze dla
ka dego
n
>n
0
jest spełniona nierówność
0
≤
f
(n)
≤
c g(n)
Przykłady:
2n(n+5) - 2n
2
=
o(n
2
)
ln
n
=
o(n
3
)
Porównanie rzędów wielkości przez obliczenie granicy
Rzędy wielkości liczb często wygodnie jest określać przez obliczenie
granicy.
E
= lim (f (n) /
g(n))
przy
n
→ ∞
E
= +
∞
E
=
c
>0
E
= 0
to
g
(n) =
o( f
(n))
g
(n) =
O
(
f(n)
)
to
f
(n) =
Θ
g(n)
to
f
(n) =
o
(g(n)
f
(n) =
O
(
g(n)
)
ale nie
f
(n) =
O
(g(n))
( lub inaczej:
f
(n)
≅
g(n)
)
ale nie
g(n)
=
O
(
f
(n))
=
n
3
/3 +
O( n
2
)
=
n(n+1)(2n+1)
/6
1 + 2
5
+ 3
5
+ ... +
n
5
=
Θ(
n
6
) =
n
6
/6 +
O( n
5
)
H
n
= 1 + 1/2 + 1/3 + ... + 1/n =
Θ(ln(n))
= ln(n) +
O(
1 ) = ln(n) +
γ
+O( 1/n )
gdzie
γ
-
stała Eulera
i
γ
= 0,577215664...
Przykłady zastosowań
1 + 2
2
+ 3
2
+ ... +
n
2
=
Θ(
n
3
)
W-1, Matematyka dyskretna
3
Przykłady liczbowe :
n
H
n
−(ln
n
+γ)
10
30
50
70
100
4,9
⋅
10
-2
1,7
⋅
10
-2
1,0
⋅
10
-2
7,1
⋅
10
-3
5
⋅
10
-3
Wzór Stirlinga
n!
= (2
π
n
)
1/2
(n/e)
n
(1 +
O(1/n))
Przykłady liczbowe :
δ(n)
- błąd względny i
n!
ze wzoru Stirlinga gdy pominięte
O(1/n)
n
δ(n)
5
30
50
70
100
1,6
⋅
10
-2
2,8
⋅
10
-3
1,7
⋅
10
-3
1,2
⋅
10
-3
8,3
⋅
10
-4
Porządkowanie wyra eń ze względu na rząd wielkości
Oznaczenia
(umowa):
ln
x
= log
e
(x)
lg
x
= log
2
(x)
Uporządkowanie w zale ności od rzędów (od najni szego).
log
n
- logarytmiczna
n
- liniowa
nlog n
- liniowo - logarytmiczna
n
2
- kwadratowa
n
3
- sześcienna
n
2
,
n
3
- ogólnie: wielomianowa
n
log
n
- podwykladnicza
2
n
- wykładnicza 2
n
n!
- wykładnicza
n!
Pułapki
a)
f(n) = nlog n
g(n) = 20n - obliczenia dla
n
< 32000
b)
l
s
=
a
s
nlog n
+O(n)
a
s
= 2/loge
≈
1,4
l
w
=
n
2
/4 +
O(n).
- obliczenia dla
n=1000
i
n=
16
W-1, Matematyka dyskretna
4
Równania rekurencyjne
Rozpatrzymy typy:
1.
T(n)
w zale ności od
a)
T(n-1)
b)
T((n-1)/2)
(ogólniej (T(n-1)/b))
2.
T(n)
w zale ności od
T(n-1)
i
T(n-2)
Rozwiązanie równania - wyznaczenie
T(n)
w postaci jawnej
Oznaczenia:
- "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)
=
p
p
znane
T(n)
=
g(n)*T(n-1)
+
f(n)
Przykłady:
Zło oność obliczeniowa
a) Obliczanie wyznacznika metodą Laplace'a
T(1)
= 0
T(n)
=
n*T(n-1)
+
n
b) Rozwiązanie układu równań o macierzy trójkątnej
T(1)
= 1
T(n)
=
T(n-1)
+
n
Rozwiązania
a)
T(1)
= 0
T(n)
=
n*T(n-1)
+
n
T(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 dyskretna
5

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin