Matematyka Dyskretna
dr Stefan Grabowski [e-mail]
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) E" g(n) f jest asymptotycznie równoważne g(n)
istnieją stałe dodatnie c1, c2 oraz liczba naturalna n0, takie że dla
każdego n > n0 jest spełniona nierówność
0 d" c1g(n) d" f (n) d" 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)) f jest conajwyżej rzędu g(n)
( asymptotyczna granica górna)
istnieje stała dodatnia c oraz liczba naturalna n0, takie ze
dla każdego n >n0 jest spełniona nierówność
0 d" f (n) d" c g(n)
Przykłady: 3n + (a - 2)n2 = O (n2) (2n + ln n)2 = O (n2)
&! - 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 n0, takie ze dla każdego n
e" n0 jest spełniona nierówność
0 d" c g(n) d" f (n)
Przykłady: an 2 +5n = &!(n), (an + ln n) 2 - n2 = &! (n ln n)
Twierdzenie:
f (n) E" g(n) wtedy i tylko wtedy ,
gdy f (n) = O (g(n)) i jednocześnie f (n) = &! (g(n)).
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 n0 taka, ze dla
każdego n >n0 jest spełniona nierówność
0 d" f (n) d" c g(n)
Przykłady: 2n(n+5) - 2n2 = o(n2 ) ln n = o(n3)
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 = + " to g (n) = o( f (n))
g (n) = O ( f(n) ) ale nie f (n) = O (g(n))
E = c > 0 to f (n) = Åš g(n) ( lub inaczej: f (n) E" g(n) )
E = 0 to f (n) = o (g(n)
f (n) = O ( g(n) ) ale nie g(n) = O ( f (n))
Przykłady zastosowań
1 + 22 + 32 + ... + n2 = Åš( n3 ) = n3/3 + O( n2 )
= n(n+1)(2n+1) /6
1 + 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 Eulera i ł = 0,577215664...
Å‚
Å‚
Å‚
W-1, Matematyka dyskretna
3
Przykłady liczbowe :
n 10 30 50 70 100
Hn -(ln n +Å‚) 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 5 30 50 70 100
´(n) 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
n2 - kwadratowa
n3 - sześcienna
n2, n3 - ogólnie: wielomianowa
n log n - podwykladnicza
2n - wykładnicza 2n
n! - wykładnicza n!
Pułapki
a) f(n) = nlog n g(n) = 20n - obliczenia dla n < 32000
b) ls = as nlog n +O(n) as = 2/loge H" 1,4 lw = n2/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
...
= n(n-1)...2*T(1) + n(n-1)...2 +...+ n(n-1) + n=
= n(n-1)...2 + n(n-1)...3 +...+ n(n-1) + n=
= n!*[ 1 + 1/2! + 1/3! + ... + 1/(n-1)! ] =
= n!*[ 1 + 1/2! + 1/3! + ... + 1/(n-1)! +1/n!]  1H"
H" (e-1)*n! -1 H" (e-1)*n! -1 H" 1,7*n!
e  podstawa log naturalnego
n T(n) (e-1)*n! -1
1 0 0,718...
2 2 2,437...
3 9 9,310...
4 40 40,24_...
5 205 205,19_...
b) T(1) = 1
T(n) = T(n-1) + n
T(n) = T(n-1) + n
= T(n-2) + n-1 + n=
= T(n-3) + n-2 + n-1 + n=
...
= T(1) + 2 + 3 + ... + n-1 + n=
= 1 + 2 + 3 + ... + n-1 + n= (1/2) n (n+1)
zadanie (n)
zadanie(n/2)

T(1) = p p znane
T(n) = T( ) + T( îÅ‚n /2Å‚Å‚ ) + f (n)
podstawienie n = 2k.
Przy tym pamiętamy, że n /2 = 2k-1 oraz T(1) = T(20)
Częściej w postaci
T(n) = c*T(n/2) + f (n) gdzie c =1 lub c =2.
W-1, Matematyka dyskretna
6
Przykłady :
1) T(1) = 0
T(n) = T( ðÅ‚n / 2ûÅ‚) + p p- staÅ‚a
podstawienie n=2k k = log n
T ( 2k ) = T(2k-1) + c =
= (T(2k-2) + c) + c =
= ((T(2k-3) + c) + c) + c = ...
= T(20) + kc = c log n
2) T(1) = 1
T(n) = T( ) + n
ðÅ‚n / 2ûÅ‚
...
T(n) = 2n-1
Metoda rekurencji uniwer alnej
Równanie
T(n) = a T(n/b) + f(n)
gdzie a e" 1 i b > 1 są stałymi, f(n) funkcja asymptotycznie dodatnia.
Twierdzenie o rekurencji uniwersalnej
Niech a e" 1 i b > 1 są stałymi, f(n) pewną funkcją, T(n) określone
rekurencjÄ…
T(n) = a T(n/b) + f(n)
gdzie n/b oznacza ðÅ‚n/bûÅ‚ lub îÅ‚n/bÅ‚Å‚ . Wtedy funkcja T(n) może być
ograniczona asymptotycznie:
(tu wyjątkowo przyjęto oznaczenie: log a = log a)
b
1. Jeżeli f(n) = ź(n log a - µ) dla µ > 0, to T(n) = Åš(n log a)
2. Jeżeli f(n) = Åš(n log a) , to T(n) = Åš(n log aÅ"lg n)
3. Jeżeli f(n) = &!(n log a + µ) dla µ > 0 oraz a f (n/b) d" c f (n) dla pewnej
stałej c < 1 i wszystkich dostatecznie dużych n, to T(n) = Ś(f(n))
Rekurencje - (c.d.)
W-1, Matematyka dyskretna
7
 Wzory rekurencyjne typu
T(n) = aT(n-1) + bT(n-2) a, b - stałe. T(n) = ?
Postać rozwiÄ…zania T(n) = CÅ"rn
Po wstawieniu do równania
T(n) - aT(n-1) - bT(n-2) = 0
otrzymujemy
Crn - aCrn-1 - b Crn-2 =0
a stÄ…d
równanie charakterystyczne
r2 - ar -b = 0
Dwa przypadki rozwiÄ…zania:
1. Dwa różne pierwiastki , r1 `" r2 wtedy T(n) = C1r1n + C2r2n
2. RozwiÄ…zanie podwójne , r1 = r2 = r to T(n) = (C1 +C2Å"n) r n
Stałe C1 , C2 wyznaczamy ze znajomości początkowych wyrazów ciągu,
np. T(1) i T(2).
Przykład 1 :
Sn= Sn-1 +2Sn-2 dla n e" 2 oraz S0 = S1 = 3
RozwiÄ…zanie
Sn - Sn-1 - 2Sn-2 =0
Równanie charakterystyczne
r2 - r - 2 = 0
pierwiastki: r1 = -1 i r2 = 2. StÄ…d Sn = C1(-1)n + C2Å"2n.
Z warunków S0 = S1 = 3 wynika, że
C1 + C2 = 3 (S0 = 3)
-C1 +2C2 = 3 (S1 = 3)
skÄ…d C2 = 2, C1 = 1. CiÄ…g Sn w postaci jawnej to Sn = (-1)n + 2n+1.
Przykład 2 :
W-1, Matematyka dyskretna
8
Pn= 6Pn-1 -9Pn-2 dla ne"2 oraz P0 = 1 P1 = -3
RozwiÄ…zanie:
Pn - 6Pn-1 +9Pn-2 = 0
Równanie charakterystyczne
r2 - 6r +9 = 0
ma rozwiÄ…zanie podwójne : r1 = r2 = 3. StÄ…d Pn = (C1 + nC2)Å"3n.
Z warunków P0 = 1 P1 = -3 wynika, że
C1 = 1
(C1 + C2) Å"3 = -3 stÄ…d C2 = -2
CiÄ…g Pn w postaci jawnej to Pn = (1 -2n) 3n .
Zadania:
1. T0 = 2 T1 = -1 Tn= -Tn-1 +6 Tn-2 Odp. Tn = (-3)n + 2n
2. T0 = 1 T1 = 8 Tn= 4Tn-1 - 4Tn-2 Odp. Tn = (1+3n) 2n
Liczby Fibonacciego
Liczby Fibonacciego tworzą ciąg określony rekurencyjnie
F0=1 F1=1 Fn+1 = Fn + Fn-1
Kilka pierwszych liczb tego ciÄ…gu: 1, 1, 2, 3, 5, 8, 13, 21,...
Rozwiązując równanie rekurencyjne wyrazimy dowolny element tego
ciągu jako funkcję jego numeru. Równanie charakterystyczne
r2  r  1 = 0
ma dwa pierwiastki: .
Rozwiązanie jest więc postaci C1r1n + C2r2n . Znając F0 i F1
wyznaczamy stałe C1 i C2 .
C1 + C2 = 1
C1r1 + C2r2 = 1
StÄ…d a dalej
W-1, Matematyka dyskretna
9
Rezultat może nieco dziwić, bo wcześniej widzieliśmy że ciąg {Fn} jest
ciągiem liczb całkowitych, natomiast powyższy wzór sugeruje, że mamy
do czynienia z liczbami niewymiernymi. Rozpatrzmy jednak wyrażenie
f (n) = (a +b)n+1  (a -b)n+1 przy czym .
Dla n=3 f (n) = 8a3b + 8ab3 = b( 8a3 + 8ab2). Wyrażenie w
nawiasach jest liczbą wymierną, a całe wyrażenie f (3) jest równe .
Po wstawieniu do wzoru na Fn otrzymujemy F3 = 3.
4 2 2 4
Podobnie, dla n =4 f (4) = b(10a + 20 a b +2b ) , czyli
a następnie F4 = 5.
Otrzymany wzór pozwala na szybkie wyznaczenie dowolnej liczby
Fibonacciego bez konieczności obliczania wcześniejszych wyrazów
ciągu. Wystarczy policzyć wartość przy pominięciu drugiego członu we
wzorze i wynik zaokrąglić do najbliższej liczby całkowitej.
Uzasadnienie wynika z nierówności
. StÄ…d dla n e"1 jest i liczba Fn jest
najbliższą liczbą całkowitą dla wartości obliczonej z pierwszego członu
otrzymanego wzoru.
11
ëÅ‚1+ 5 öÅ‚
1
ìÅ‚ ÷Å‚
= 88,99775
Przykład: F10. Obliczamy, że . Stąd F10 = 89.
ìÅ‚ ÷Å‚
2
5
íÅ‚ Å‚Å‚
Inny sposób otrzymywania liczb Fibonacciego. Dla macierzy
Fn Fn-1
îÅ‚ Å‚Å‚
1 1
îÅ‚ Å‚Å‚
n
M =
M =
ïÅ‚F
ïÅ‚1 0śł
mamy własność :
Fn-2śł
ðÅ‚ ûÅ‚ ðÅ‚ n-1 ûÅ‚
Na przykład:
F4 F3 5 3
F2 F1 2 1 îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
4
2
M = =
M = =
ïÅ‚F F2 śł
ïÅ‚F F0 śł ïÅ‚1 1śł ïÅ‚3 2śł
ðÅ‚ 1 ûÅ‚ ðÅ‚ ûÅ‚ ðÅ‚ 3 ûÅ‚ ðÅ‚ ûÅ‚
F8 F7 34 21
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
8
M = =
ïÅ‚F F6 śł ïÅ‚21 13śł
ðÅ‚ 7 ûÅ‚ ðÅ‚ ûÅ‚
W-1, Matematyka dyskretna
10