Matematyka Dyskretna
Andrzej Szepietowski
25 marca 2004 roku
Rozdział 1
Podstawowe pojęcia, oznaczenia
1.1 Sumy
Mając dany skończony ciąg a1, a2,... ak, sumę jego elementów zapisujemy jako
k
ai.
i=1
Niezbyt formalnie możemy to zapisać
k
ai = a1 + a2 + � � � + ak.
i=1
Jako przykład zastosujmy symbol sumy do zapisu wzoru na sumę ciągu arytmetycznego).
k
(k + 1)k
i = 1 + 2 + � � � + k = (1.1)
2
i=1
oraz wzoru na sumę ciągu geometrycznego).
k
xk+1 - 1
xi = 1 + x + x2 + � � � + xk = , (1.2)
x - 1
i=0
(wzór (1.2) jest słuszny dla każdego x = 1)

Będziemy też używać zapisu typu
ai = a1 + a2 + a3 + a4 + a5 + a6.
1d"id"6
W tym przypadku zbiór indeksów określony jest za pomocą warunku pod znakiem sumy.
Warunek określający indeksy, po których należy sumować może być bardziej skompliko-
wany, na przykład
ai = a2 + a4 + a6.
1d"id"6
i parzyste
3
4 Rozdział 1. Podstawowe pojęcia, oznaczenia
Stosować będziemy także zapis
ai
i"I
oznaczający sumę tych elementów ai, których indeksy należą do skończonego zbioru
indeksów I. Na przykład, jeżeli I = {1, 3, 5, 7}, to
ai = a1 + a3 + a5 + a7.
i"I
Możemy też sumować ciągi, których elementy zależą od dwóch indeksów,
aij = aija12 + a13 + a22 + a23 + a32 + a33.
1d"id"3
1d"id"3 2d"jd"3
2d"jd"3
Za pomocą podwójnej sumy możemy, na przykład, przedstawić uogólnione prawo roz-
dzielności mnożenia względem dodawania:
�ł �ł �ł �ł
�ł �ł
aiłł � bjłł = aibj (1.3)
1d"id"m
1d"id"m 1d"jd"n
1d"jd"n
a także wzór na podnoszenie sumy do kwadratu:
�ł �ł2
�ł
aiłł = a2 + 2aiaj (1.4)
i
1d"id"m 1d"id"m 1d"i1.2 Iloczyny
Aby zapisać iloczyn elementów ciągu a1, a2,..., ak, stosujemy zapis
k
ai.
i=1
Znów niezbyt formalnie możemy to zapisać jako
k
ai = a1 � a2 � � � � � ak.
i=1
1.3 Zbiory
" oznacza zbiór pusty, który nie zawiera żadnych elementów.
N oznacza zbiór liczb naturalnych N = {0, 1, 2, 3, . . .}.
Z oznacza zbiór liczb całkowitych.
1.3. Zbiory 5
Q oznacza zbiór liczb wymiernych.
R oznacza zbiór liczb rzeczywistych.
a " A oznacza, że elment a należy do zbioru A, a " A, że elment a nie należy do
/
zbioru A. Najprostszy sposób zdefiniowania zbioru polega na wypisaniu jego elementów
w nawiasach klamrowych. Na przykład zbiór {1, 2, 3} zawiera elementy 1,2,3. Inny spo-
sób definiowania zbioru polega na podaniu własności, którą spełniają elementy zbioru.
Na przykład {x | x " N, 3 < x < 7} oznacza zbiór liczb naturalnych większych od 3 i
mniejszych od 7.
|A| oznacza moc zbioru A, czyli liczbę jego elementów.
|{3, 6, 9}| = 3, |"| = 0.
A *" B oznacza sumę zbiorów, czyli zbiór zawierający elementy, które należą do A lub do
B:
A *" B = {x : x " A lub x " B}.
A zatem suma A *" B zawiera wszystkie elementy zbioru A i wszystkie elementy zbioru
B.
A )" B oznacza iloczyn lub przekrój zbiorów, czyli zbiór zawierający elementy, które
należą do obu zbiorów naraz.
A )" B = {x : x " A i x " B}.
A - B oznacza różnicę zbiorów, czyli zbiór zawierający elementy, które należą do A
i nie należą do B.
A - B = {x : x " A i x " B}.
/
Przykład 1.1 Dla A = {1, 2, 4} i B = {1, 4, 6} mamy:
A *" B = {1, 2, 4, 6}, A )" B = {1, 4}, A - B = {2}.
A ą" B oznacza, że zbior A zawiera się w zbiorze B, to znaczy wszystkie elementy zbioru
A należą do zbioru B.
{2, 1} ą" {1, 2, 3}
Dwa zbiory są równe jeżeli zawierają te same elementy, lub inaczej A = B wtedy i tylko
wtedy gdy A ą" B i B ą" A.
{1, 4, 2, 3} = {4, 1, 3, 2}.
Jak widać kolejność elementów w zapisie zbioru nie ma znaczenia. I tak na przykład
{1, 2} = {2, 1}. Taki zbiór dwuelementowy nazywamy parą nieuporządkowaną.
W poniższym lemacie zebrano podstawowe własności operacji sumy i iloczynu zbio-
rów.
Lemat 1.2 " A *" B = B *" A (przemienność sumy).
" A )" B = B )" A (przemienność iloczynu).
6 Rozdział 1. Podstawowe pojęcia, oznaczenia
" A *" (B *" C) = (A *" B) *" C (łączność sumy).
" (A )" B) )" C = A )" (B )" C) (łączność iloczynu).
" (A *" B) )" C = A )" C *" B )" C (rozdzielność sumy względem iloczynu).
" (A )" B) *" C = (A *" C) )" (B *" C) (rozdzielność iloczynu względem sumy).
" A *" " = A, A )" " = ", A *" A = A, A )" A = A,
Dowód: Udowodnimy tylko rozdzielność sumy względem iloczynu. W tym celu pokaże-
my dwa zawierania: (A *" B) )" C �" A )" C *" B )" C oraz A )" C *" B )" C �" (A *" B) )" C.
Aby udowodnić zawieranie (A *" B) )" C �" A )" C *" B )" C, weżmy dowolny element
x " (A *" B) )" C, wtedy x " A *" B oraz x " C, a to oznacza, że x nalezy do C i do
jednego ze zbiorów A lub B (lub do obu), czyli należy do A )" C lub do B )" C, a więc
x " A )" C *" B )" C. Pokazaliśmy więc, że dowolny element z (A *" B) )" C należy do
A )" C *" B )" C.
Aby udowodnić zawieranie A )" C *" B )" C �" (A *" B) )" C. weżmy dowolny element
x " A )" C *" B )" C, wtedy x " A )" C lub x " B )" C, a to oznacza, że x nalezy do C
i do jednego ze zbiorów A lub B (lub do obu), czyli należy do A *" B oraz do C, a więc
x " (A *" B) )" C. Pokazaliśmy więc, że dowolny element z A )" C *" B )" C należy do
(A *" B) )" C.
1.4 Różnica symetryczna zbiorów
A �" B oznacza różnicę symetryczną zbiorów, która zawiera elementy należące tylko do
jednego z dwóch zbiorów:
A �" B = (A - B) *" (B - A).
Przykład 1.3
{1, 2, 4} �" {1, 4, 6} = {2, 6}.
W poniższym lemacie zebrano podstawowe własności różnicy symetrycznej zbiorów.
Lemat 1.4 " A �" B = B �" A (przemienność).
" (A �" B) �" C = A �" (B �" C) (łączność).
" (A �" B) )" C = A )" C �" B )" C (rozdzielność względem iloczynu).
" A �" " = A, A �" A = ".
" Jeżeli A �" B = ", to A = B.
Dowód:
Udowodnimy, tylko dwie tożsamości, dowód pozostałych pozostawiamy czytelnikowi
jako ćwiczenie.
1.5. Iloczyn kartezjański 7
Aby pokazać, że różnica symetryczna jest łączna wystarczy zauważyć, że zbiór A �"
(B�"C) lub (A�"B)�"C zawiera te elementy, które należą do nieparzystej liczby zbiorów,
czyli te, które należą tylko do A, B lub C, plus te, które należą do przekroju A )" B )" C.
Udowodnimy teraz ostatnią implikację. Jeżeli A �" B = ", to
A = A �" " = A �" (A �" B) = (A �" A) �" B = " �" B = B.
Twierdzenie 1.5 Różnica symetryczna n zbiorów:
A1 �" A2 �" . . . �" An
zawiera elementy, które należą do nieparzystej liczby spośród zbiorów A1, A2, . . . , An.
Dowód przez indukcję ze względu na n. Twierdzenie jest oczywiste dla n = 1 lub
n = 2. Załóżmy teraz, że jest ono prawdziwe dla n i rozpatrzmy:
A1 �" . . . �" An �" An+1 = (A1 �" . . . �" An) �" An+1.
Zbiór ten zawiera te elementy, które należą do (A1 �" . . . �" An) i nie należą do An+1,
oraz te, które nie należą do (A1 �" . . . �" An) i należą do An+1. W pierwszym przypad-
ku są to elementy, które nie należą do An+1 i na mocy założenia indukcyjnego należą
do jakiejś nieparzystej liczby zbiorów spośród A1, . . . , An. W drugim przypadku są to
elementy, które należą do An+1, a także do pewnej parzystej liczby zbiorów spośród
A1, . . . , An. Razem mamy wszystkie elementy należące do nieparzystej liczby zbiorów
spośród A1, . . . , An+1.
1.5 Iloczyn kartezjański
Para uporządkowana jest to dwuelementowy ciąg (x, y). Mamy (x, y) = (u, v) wtedy i
tylko wtedy gdy x = u oraz y = v. Dopuszczalne jest także x = y.
A � B oznacza iloczyn kartezjański zbiorów A i B. Jest to zbiór wszystkich uporząd-
kowanych par (a, b), w których a " A i b " B. Inaczej
A � B = {(a, b) | a " A, b " B}.
Przykład 1.6 Dla A = {1, 3, 5} i B = {3, 4} mamy
A � B = {(1, 3), (1, 4), (3, 3), (3, 4), (5, 3), (5, 4)}.
Można łatwo wykazać, że
|A � B| = |A| � |B|.
8 Rozdział 1. Podstawowe pojęcia, oznaczenia
1.6 Rodzina zbiorów
Czasami będziemy mieli do czynienia ze zbiorem, którego elementami są zbiory. Przez
P(A) lub 2A
będziemy oznaczać zbiór wszystkich podzbiorów zbioru A.
Przykład 1.7 Dla A = {a, b}
P(A) = {", {a}, {b}, {a, b}}.
Zbiór zbiorów nazywamy czasami rodziną zbiorów. Na przykład A = {A1, A2, A3, A4}
jest rodziną zawierającą cztery zbiory A1, A2, A3 i A4, są to elementy zbioru A. Możemy
też zapisać A = {Ai | 1 d" i d" 4}.
Możemy sumować zbiory z rodziny. Suma
k
Ai
i=1
zawiera te elementy, które należą do któregoś ze zbiorów A1, A2, ... ,Ak, czyli
k
Ai = {x | "i 1d"id"k x " Ai}.
i=1
Inaczej możemy to zapisać:
k
Ai = A1 *" A2 *" . . . *" Ak.
i=1
Będziemy też używać zapisu
Ai
i"I
na oznaczenie sumy wszystkich zbiorów Ai, których indeksy należą do zbioru I. Zacho-
dzi wtedy
Ai = {x | "i"I x " Ai}.
i"I
Zbiór indeksów sumowania może być określony za pomocą warunku.
Ai = A2 *" A3 *" A4 *" A5.
1Dla sumy zbiorów zachodzi prawo rozdzielności sumy względem przekroju:
Lemat 1.8
C )" Ai = (C )" Ai)
i"I i"I
1.6. Rodzina zbiorów 9
Dowód: Wez
my dowolny element x " C )" Ai. Wtedy x należy do C i do któregoś
i"I
ze zbiorów Ai, czyli dla jakiegoś i " I, x należy do C )"Ai, a to znaczy, że x " (C )"
i"I
Ai).
Wez
my z kolei dowolny element x " (C )" Ai). Wtedy x należy do C )" Ai
i"I
dla jakiegoś i " I, czyli x nalez
y do C i do sumy Ai, czyli należy do przekroju
i"I
C )" Ai.
i"I
Możemy też brać przekroje zbiorów z rodziny. Przekrój
k
Ai
i=1
zawiera te elementy, które należą do wszystkich zbiorów A1, A2, ... ,Ak, czyli
k
Ai = {x | "i 1d"id"k x " Ai}.
i=1
Inaczej możemy to zapisać:
k
Ai = A1 )" A2 )" . . . )" Ak.
i=1
Będziemy też używać zapisu
Ai
i"I
na oznaczenie przekroju wszystkich zbiorów Ai, których indeksy należą do zbioru I.
Zachodzi wtedy
Ai = {x | "i"I x " Ai}.
i"I
Zbiór indeksów przekroju może być określony za pomocą warunku:
Ai = A2 )" A3 )" A4 )" A5.
1Przykład 1.9 Wez
my rodzinę złożoną z trzech zbiorów A1 = {4, 6, 8}, A2 = {4, 5, 6},
A3 = {4, 5, 8, 9}.
3 3
Ai = {4, 5, 6, 8, 9}, Ai = {4}.
i=1 i=1
Przykład 1.10 Niech I = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} będzie zbiorem indeksów. Dla każ-
dego i " I określamy zbór Ai = {x " N | 1 d" x d" i}. Mamy:
Ai = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, Ai = {1},
i"I i"I
Ai = {1, 2, 3, 4, 5, 6}, Ai = {1, 2}.
110 Rozdział 1. Podstawowe pojęcia, oznaczenia
1.7 Grafy (nieskierowane)
Definicja 1.11 Graf (nieskierowany) G = (V, E) jest to para składająca się ze skończo-
nego zbioru wierzchołków V oraz ze zbioru krawędzi E, gdzie krawędzie to pary wierz-
chołków.
E ą" {{u, v} | u, v " V, u = v}.

O krawędzi e = {u, v} mówimy, że łączy wierzchołki u i v, a o wierzchołkach u i v, że
są końcami krawędzi e. Wierzchołki połączone krawędzią nazywamy sąsiednimi. Stopień
wierzchołka v, oznaczany przez d(v), jest to liczba krawędzi wychodzących z v.
Graf przedstawiamy na rysunku jako zbiór punktów (lub kółek) połączonych odcin-
kami (lub łukami).
Rysunek 1.1: Przykład grafu
a c
b
d
g
e f
Przykład 1.12 Rysunek 1.1 przedstawia graf G = (V, E) ze zbiorem wierzchołków V =
{a, b, c, d, e, f, g} i zbiorem krawędzi
E = {{a, b}, {a, d}, {a, e}, {a, g}, {b, c}, {c, g}, {c, f}, {d, f}, {e, f}, {f, g}}. Sto-
pień wierzchołków a i f wynosi 4, wierzchołki c i g są stopnia 3, wierzchołki b, d i e
stopnia 2.
Graf H = (VH , EH) nazywamy podgrafem grafu G = (VG, EG), jeżeli VH ą" VG oraz
EH ą" EG.
Przykład 1.13 Graf przedstawiony na rysunku 1.3 jest podgrafem grafu z rysunku 1.1.
Graf pełny o n wierzchołkach, oznaczany przez Kn, jest to graf z n wierzchołkami,
w którym każde dwa wierzchołki połączone są krawędzią.
Droga lub ścieżka w grafie G = (VG, EG) jest to ciąg wierzchołków v0, v1, . . . , vk,
taki, że dla każdego i, 1 d" i d" k, wierzchołki vi-1, vi są połączone krawędzią, czyli
{vi-1, vi} " EG. O drodze v0, v1, . . . , vk mówimy, że łączy wierzchołki v0 i vk. Mówi-
my także, że wierzchołek vk jest osiągalny z wierzchołka v0. Droga jest zamknięta jeżeli
1.7. Grafy (nieskierowane) 11
Rysunek 1.2: Graf pełny K6.
a
b
c
d
e f
v0 = vk. Droga jest prosta, jeżeli wszystkie występujące w niej wierzchołki są różne.
Drogę v0, v1, . . . , vk nazywamy cyklem jeżeli v0 = vk, k e" 3 oraz wszystkie wierzchołki
v1, . . . , vk są różne.
Przykład 1.14 W grafie z rysunku 1.1 ciąg e, a, d, a, b, c, g jest drogą, a ciąg a, e,
f, d, a jest cyklem. Ciąg a, e, f, d, a, b, c, g, a jest drogą zamkniętą, ale nie jest cyklem.
Graf G jest spójny, jeżeli dla każdych dwóch wierzchołków u, v " VG istnieje ścieżka
łącząca u i v.
Lemat 1.15 Jeżeli istnieje droga łącząca wierzchołki u i v, u = v, to istnieje też droga

prosta łącząca u i v.
Dowód: Niech u = v0, v1, . . . , vk = v, będzie najkrótszą drogę łączącą u i v. Droga
ta jest prosta. Przypuśćmy bowiem, że vi = vj, dla jakiegoś i < j; mielibyśmy wtedy
krótszą drogę u = v0, . . . , vi, vj+1, . . . , vk = v, łączącą u i v, wbrew założeniu.
Dowolne dwa wierzchołki w cyklu mogą być połączone dwoma drogami prostymi.
Na przykład w cyklu a, b, c, g, a na rysunku 1.1, wierzchołki a i c łączy droga a, b, c oraz
droga a, g, c. Tak, więc, jeżeli w grafie są cykle, to istnieją pary wierzchołkow, które są
połączone dwoma drogami prostymi. Ale i na odwrót.
Lemat 1.16 Jeżeli w grafie istnieją dwa wierzchołki u i v, u = v które można połączyć

dwoma różnymi drogami prostymi, to w grafie istnieje cykl.
Dowód: Niech u = v0, v1, . . . , vk = v oraz u = w0, w1, . . . , wl = v, będą dwoma
rożnymi prostymi drogami łączącymi u i v. Możemy założyć, że v1 = w1 (w przeciw-

nym przypadku możemy usunąć wspólny początek obu dróg). Niech vi będzie pierw-
szym wierzchołkiem po v0, który występuje w drodze w0, w1, . . . , wm, i niech vi = wj.
12 Rozdział 1. Podstawowe pojęcia, oznaczenia
Wierzchołki v1, . . . , vi-1 nie występują w drodze w0, w1, . . . , wm i droga v0, . . . , vi =
wj, wj-1, . . . , w1, w0 = v0 tworzy cykl (w drodze tej występują conajmniej trzy różne
wierzchołki v0, v1 oraz w1).
Z tego lematu wynika, że graf jest acykliczny (nie ma cykli) wtedy i tylko wtedy, gdy
każde dwa wierzchołki grafu można połączyć co najwyżej jedną drogą prostą.
1.8 Drzewa
Definicja 1.17 Spójny i acykliczny (bez cykli) graf to drzewo.
Rysunek 1.3: Przykład drzewa
a c
b
d
g
e f
Z rozważań z poprzedniego podrozdziału wynika:
Lemat 1.18 Graf jest drzewem wtedy i tylko wtedy, gdy każde dwa jego wierzchołki moż-
na połączyć dokładnie jedną prostą drogą.
1.9 Drzewa ukorzenione
Definicja 1.19 Drzewo ukorzenione to drzewo z wyróżnionym jednym wierzchołkiem.
Wyróżniony wierzchołek nazywamy korzeniem drzewa.
Każdy wierzchołek v różny od korzenia jest z nim połączony dokładnie jedną drogą
prostą. Sąsiad leżący na drodze do korzenia nazywamy ojcem wierzchołka v. Pozastali
sąsiedzi są synami wierzchołka v. Korzeń drzewa nie ma ojca, wszyscy jego sąsiedzi są
jego synami. Wierzchołek, który nie posiada syna nazywamy liściem.
Przykład 1.20 Jeżeli w drzewie z rysunku 1.3 wyróżnimy wierzchołek d jako korzeń, to
ojcem wierzchołka a jest wierzchołek d, synami wierzchołka a są wierzchołki e, g i b.
Wierzchołki f, e, g oraz c są liściami.
1.10. Grafy skierowane 13
Rysunek 1.4: Drzewo ukorzenione
d
f a
g
e
b
c
Zwykle drzewo ukorzenione rysujemy tak jak na rysunku 1.4. Korzeń jest na górze,
poniżej leżą jego synowie i ogólnie każdy wierzchołek leży poniżej swojego ojca i powyżej
swoich synów.
1.10 Grafy skierowane
Definicja 1.21 Graf skierowany (zorientowany) to dowolna para G = (V, E), ze skoń-
czonym zbiorem wierzchołków V i zbiorem krawędzi E ą" V � V .
Rysunek 1.5: Graf skierowany
a c
b
e
d
W grafie skierowanym krawędz
e = (u, v) jest skierowana od wierzchołka u do wierz-
chołka v. Wierzchołek u nazywamy początkiem krawędzi, a wierzchołek v końcem. Na
rysunkach krawędzie skierowane będziemy przedstawiać jako strzałki. Droga w grafie
skierowanym jest to ciąg wierzchołków v0, v1, . . . , vk, taki, że dla każdego i, 1 d" i d" k,
14 Rozdział 1. Podstawowe pojęcia, oznaczenia
wierzchołki vi-1, vi są połączone krawędzią, czyli (vi-1, vi) " E. Krawędz
typu (u, u),
w której początek i koniec pokrywają się, nazywamy pętlą.
1.11 Słowa
Słowa są to ciągi liter lub symboli z jakiegoś skończonego zbioru Ł. Zbiór Ł nazywamy
wtedy alfabetem. Zbiór wszystkich słów nad alfabetem Ł oznaczamy przez
Ł".
Wśród słów wyróżniamy słowo puste , które nie zawiera żadnych liter.
Przykład 1.22 Na przykład, jeżeli Ł = {a, b}, to Ł" zawiera słowo puste , dwa słowa
jednoliterowe a i b, cztery słowa dwuliterowe aa, ab, ba i bb, osiem słów trzyliterowych
aaa, aab, aba i abb, baa, bab, bba i bbb, i tak dalej.
Długość słowa w " Ł jest to liczba jego liter, będziemy ją oznaczać przez |w|. Dłu-
gość słowa pustego || = 0. Zbiór wszystkich słów długości n nad alfabetem Ł oznacza-
my przez
Łn.
Dla słów możemy określić operację konkatenacji, lub składania słów. Konkatenacja (lub
złożenie) dwóch słów u, v " Ł, oznaczana przez uv, jest to sklejenie słów u i v. Do słowa
u dopisujemy na końcu słowo v. Dla dowolnego słowa v " Ł" zachodzi v = v = v.
Przykład 1.23 Konkatenacja słów u = aaba i v = abba to sówo uv = aabaabba.
Słowo u jest prefiksem lub przedrostkiem słowa v, jeżeli istnieje takie słowo w, że
v = uw. Podobnie, słowo u jest sufiksem lub przyrostkiem słowa v, jeżeli istnieje takie
słowo w, że v = wu.
Przykład 1.24 Na przykład aba jest prefiksem słowa abaaab, a słowo ab jest sufiksem
słowa abaaab. Słowo puste jest prefixem i sufiksem dowolnego słowa v. Każde słowo v
jest swoim własnym prefiksem i sufiksem.
Zwykle alfabet jest zbiorem uporządkowanym, lub mówiąc inaczej mamy pewną ko-
lejność liter w alfabecie. Na przykład w zbiorze Ł = {a, b} litera a stoi przed b. Możemy
wtedy uporządkować zbiór słów nad alfabetem Ł.
Jeden porządek nazywa się porządkiem leksykograficznym. Jest to porządek słów w
słownikach. Aby porównać dwa słowa u, v " Ł, szukamy pierwszej pozycji, na której te
dwa słowa się różnią. Słowo, które ma na tej pozycji wcześniejszą literę, jest wcześniejsze
w porządku leksykograficznym. Jeżeli takiej pozycji nie ma, to albo u = v, albo jedno
ze słów jest prefiksem drugiego, wtedy wcześniejszy w porządku leksykograficznym jest
prefiks.
Przykład 1.25 W porządku leksykograficznym słowo ab jest wcześniejsze od słowa ababa,
a to jest wcześniejsze od abb.
1.12. Zaokrąglenia 15
Porządek leksykograficzny jest wygodny, jeżeli zbiór słów jest skończony. Zauważmy, że
w zbiorze wszystkich słów {a, b}" nieskończenie wiele słów (wszystkie słowa złożone
tylko z litery a) poprzedza słowo b. Dlatego czasami stosuje się inny porządek, tak zwany
porządek kanoniczny.
Słowo u poprzedza słowo v w porządku kanonicznym, jeżeli:
" albo |u| < |v|,
" albo |u| = |v| i u poprzedza v w porządku leksykograficznym.
Przykład 1.26 Początkowe słowa zbioru {a, b}" uporządkowane według porządku kano-
nicznego to:
, a, b, aa, ab, ba, bb, aaa, aab, aba, abb, baa, bab, bba, bbb, aaaa, . . .
1.12 Zaokrąglenia
Wprowadz
my dwa oznaczenia na zaokrąglenie liczby rzeczywistej. Dla dowolnej liczby
rzeczywistej x
x oznacza zaokrąglenie x w górę do najbliższej liczby całkowitej.
x oznacza zaokrąglenie x w dół do najbliższej liczby całkowitej.
Zaokrąglenie x nazywamy sufitem z x, a zaokrąglenie x nazywamy podłogą z x.
Przykład 1.27
4 = 4, 4.3 = 5, -4 = -4, -4.3 = -4.
4 = 4, 4.3 = 4, -4 = -4, -4.3 = -5.
1.13 Przedrostki
W przypadku bardzo dużych lub bardzo małych wartości używa się czasami jednostek
miar będących wielokrotnościami lub podwielokrotnościami podstawowych jednostek.
Takie jednostki wyraża się przez dodanie do nazwy jednostki odpowiedniego przedrostka,
a do oznaczenia tej jednostki dodaje się oznaczenie przedrostka. W następującej tabeli
zebrano te przedrostki.
16 Rozdział 1. Podstawowe pojęcia, oznaczenia
Przedrostek Oznaczenie Wielokrotność
exa E 1018
peta P 1015
tera T 1012
giga G 109
mega M 106
kilo k 103
hekto h 102
deka da 10
Przedrostek Oznaczenie Podwielokrotność
decy d 10-1
centy c 10-2
mili m 10-3
mikro � 10-6
nano n 10-9
piko p 10-12
femto f 10-15
atto a 10-18
Przykładami tak utworzonych jednostek są: centymetr (cm), milimetr (mm), hehtopa-
skal, hektolitr, kilogram (kg), kilowat (kW). Do mierzenia prędkości (zegara) procesora
używa się megahertzów. Jeden megahertz (MHz) to jednostka częstości równa miliono-
wi impulsów na sekundę. Kilobajtów, megabajtów i gigabajtów używa się do mierzenia
liczby komórek pamięci. Często przyjmuje się, że kilobajt ma 1024 bajtów, megabajt
1024 � 1024 bajtów, a gigabajt 1024 � 1024 � 1024 bajtów.
1.14 Notacja asymptotyczna
W analizie jakiegoś algorytmu (programu) ważne jest oszacowanie jego czasu działania.
Jako przykład wez
my algorytm sortowania bąbelkowego, który ustawia elementy ciągu
wejściowego w porządku niemalejącym.
Algorytm sortowania bąbelkowego.
Dane wejściowe: ciąg a1, a2, ... ,an.
Dane wyjściowe: elementy ciągu w porządku niemalejącym.
n - 1 razy wykonuj
(1) wskaż na pierwszy element,
(2) n - 1 razy wykonuj:
(2a) porównaj wskazany element z elementem następnym,
(2b) jeżeli porównane elementy są w niewłaściwej kolejności,
to zamień je miejscami,
(2c) wskaż na następny element.
W poniższej tabeli zilustrowano zastosowanie algorytmu dla ciągu (3, 4, 1, 2).
1.14. Notacja asymptotyczna 17
Ć
3 4 1 2
Ć
3 4 1 2
Ć
3 1 4 2
Ć
3 1 2 4
Ć
1 3 2 4
Ć
1 2 3 4
Ć
1 2 3 4
Ć
1 2 3 4
Ć
1 2 3 4
Kolejne wiersze przedstawiają ciąg po kolejnych porównaniach. Element aktualnie wska-
zany jest zaznaczony daszkiem.
Poprawność powyższego algorytmu wynika z faktu, że po pierwszym wykonaniu ze-
wnętrznej pętli (instrukcje (1) i (2)) największy element ciągu znajdzie się na końcu, po
drugim wykonaniu pętli drugi największy element ciągu znajdzie się na przedostatniej
pozycji, i tak dalej. Po każdym kolejnym wykonaniu pętli kolejny największy element
znajdzie swoją właściwą pozycję. Czas działania algorytmu zależy od n  liczby ele-
mentów w ciągu. Pętla zewnętrzna (instrukcje (1) i (2)) jest wykowywana n - 1 razy.
W każdej iteracji pętli zewnętrznej pętla wewnętrzna (instrukcje (2a), (2b) i (2c)) rów-
nież jest wykonywana n - 1 razy. W każdym kolejnym wykonaniu pętli wewnętrznej
algorytm wykonuje kilka kroków. Tak więc, aby posortować ciąg długości n algorytm w
sumie wykonuje c(n - 1)2 kroków, gdzie c jest pewną stałą.
Czas pracy powyższego algorytmu został oszacowany z dokładnością do stałej. Jest
to powszechna praktyka i będziemy tak postępować w tej książce. Do szacowania czasu
pracy algorytmu (jego złożoności czasowej) i do porównywania algorytmów pod wzglę-
dem czasu działania będziemy używać notacji asymptotycznej. Niech f i g będą dwiema
funkcjami określonymi na zbiorze liczb naturalnych o wartościach w zbiorze dodatnich
liczb rzeczywistych
f, g : N {x|x " R, x > 0}.
Wtedy:
" g(n) = O(f(n)), jeżeli istnieje dodatnia stała c > 0 taka, że g(n) d" c � f(n)
dla prawie wszystkich n " N, to znaczy istnieje n0, takie, że g(n) d" c � f(n) dla
każdego n e" n0. W takim przypadku mówimy, że funkcja g jest O duże od f.
g(n)
" g(n) = o(f(n)), jeżeli limn" f (n) = 0. W takim przypadku mówimy, że funk-
cja g jest o małe od f.
" g(n) = &!(f(n)), jeżeli istnieje dodatnia stała c > 0 taka, że g(n) e" c � f(n) dla
prawie wszystkich n " N. W takim przypadku mówimy, że funkcja g jest Omega
duże od f.
" g(n) = Ś(f(n)), jeżeli istnieją dwie dodatnie stałe c1, c2 > 0 takie, że c1 � f(n) d"
g(n) d" c2 � f(n) dla prawie wszystkich n " N. W takim przypadku mówimy, że
funkcja g jest Theta duże od f.
18 Rozdział 1. Podstawowe pojęcia, oznaczenia
Jeżeli g(n) = O(f(n)), to mówimy, że funkcja f ogranicza z góry funkcję g(n) (z
dokładnością do stałej), albo, że rząd funkcji g jest nie większy od rzędu funkcji f.
Przykład 1.28
" Czas działania algorytmu sortowania bąbelkowego jest O(n2).
" n = O(3n - 2).
" 3n - 2 = O(n).
" n3 + n2 - n = O(n3).
" n3 = O(2n).
" n2 log n = O(n3).
Będziemy dopuszczać notację asymptotyczną także wobec funkcji, które są dodatnie
dla prawie wszystkich liczb naturalnych. Na przykład n2 - 3n = O(n2).
Jeżeli g(n) = o(f(n)), to mówimy, że g jest niższego rzędu niż f.
Przykład 1.29 " n2 = o(n3).
" n = o(n log n).
" n3 = o(2n).
Jeżeli g(n) = Ś(f(n)), to g i f są tego samego rzędu, czyli g(n) = O(f(n)) oraz
f(n) = O(g(n)).
Przykład 1.30
" n2 = Ś(n2 + n).
" n = Ś(n + log n).
Następujący lemat jest bardzo użyteczny przy szacowaniu asymptotycznym. Jego do-
wód zostawiamy jako ćwiczenie.
g(n)
Lemat 1.31 Jeżeli granica lim istnieje i jest właściwa (nie jest równa "), to g(n) =
f (n)
O(f(n)).
Wniosek 1.32 Jeżeli g(n) = o(f(n)), to g(n) = O(f(n)).
Następujący przykład pokazuje, że oszacowanie asymptotyczne może być czasem zawod-
ne.
Przykład 1.33 Wez
my dwie funkcje f(n) = 300n oraz g(n) = n log2 n. Mamy f(n) =
o(g(n)), ale f(n) e" g(n) dla wszystkich n d" 2300, czyli dla wszystkich liczb mniejszych
od liczby atomów w naszej galaktyce (porównaj podrozdział duże liczby w rozdziale o
arytmetyce).
1.15. Wielomiany 19
Z drugiej jednak strony oszacowanie asymptotyczne wystarczy do naszych celów i
jest łatwiejsze do uzyskania.
Przykład 1.34 Rozważmy trzy algorytmy: pierwszy działający w czasie f1(n) = c1n,
drugi w czasie f2(n) = c2n3 i trzeci w czasie f3(n) = c32n. Funkcje te określają czas
działania na pewnym konkretnym komputerze. Niech n1, n2 i n3 oznazczają długości
wejść, dla których algorytmy dają odpowiedz
w ciągu jednej sekundy, to znaczy f1(n1) =
f2(n2) = f3(n3) = 1s.
Przypuśćmy teraz, że mamy 1000 razy szybszy komputer i pytamy jakie wejścia teraz
mogą być policzone przez te algorytmy w ciągu jednej sekundy.
Dla pierwszego algorytmu działającego w czasie liniowym możemy teraz obliczać
1000 razy dłuższe dane wejściowe, ponieważ f1(1000n1) = 1000f1(n1). Dla drugie-
go algorytmu działającego w czasie sześciennym możemy teraz obliczać 10 razy dłuższe
dane wejściowe, ponieważ f2(10n2) = 1000f2(n2). Dla trzeciego algorytmu działają-
cego w czasie wykładniczym możemy teraz obliczać tylko dane wejściowe o 10 dłuższe,
ponieważ f3(n3 + 10) = 1024f3(n3).
1.15 Wielomiany
Wielomian jest to funkcja postaci
P (x) = an � xn + � � � + a0,
gdzie x jest zmienną rzeczywistą, a a0, a1, ... ,an są stałymi rzeczywistymi, nazywanymi
współczynnikami wielomianu. Stopniem wielomianu P (x) jest największe takie k, że
ak = 0, stopień oznaczamy, przez st(W (x)). Zwykle pisząc P (x) = an � xn + � � � + a0

będziemy zakładać, że an = 0, czyli że stopień st(P (x)) = n. Używając symbolu sumy

wielomian możemy przedstawić w następujący sposób:
n
P (x) = aixi.
i=0
Wielomian, którego wszystkie współczynniki są równe zeru nazywamy wielomianem ze-
n n
rowym. Dwa wielomiany P (x) = aixi oraz Q(x) = bixi są równe jeżeli
i=0 i=0
mają takie same wspólczynniki, to znaczy jeżeli ai = bi dla każdego i.
Wielomiany można dodawać, odejmować lub mnożyć. Suma, różnica i iloczyn wie-
lomianów P (x) i Q(x) określone są następująco:
n
" P (x) + Q(x) = (ai + bi)xi,
i=0
n
" P (x) - Q(x) = (ai - bi)xi,
i=0
2n i
" P (x) � Q(x) = cixi, gdzie ci = ak � bi-k oraz ak = 0 i bk = 0
i=0 k=0
dla wszystkich k > n.
20 Rozdział 1. Podstawowe pojęcia, oznaczenia
Wzór na iloczyn wielomianów wygląda skomplikowanie, ale jest on równoważny szkol-
nemu sposobowi mnożenia wielomianów, gdzie wyrazy (jednomiany) obu wielomianów
wymnaża się każdy z każdym a następnie grupuje wyrazy według wykładników. Wielo-
mian P (x) można pomnożyć przez stałą a
n
a � P (x) = a � aixi.
i=0
Przykład 1.35 Niech P (x) = x2 + 2x + 1 oraz Q(x) = 2x2 + x. Wtedy
P (x) + Q(x) = 3x2 + 3x + 1
P (x) � Q(x) = 2x4 + 5x3 + 4x2 + x
3 � P (x) = 3x2 + 6x + 3
1.15.1 Dzielenie wielomianów
Wielomiany można też dzielić. Mamy
Twierdzenie 1.36 Dla dowolnych dwóch wielomianów W (x) i V (x) istnieją dwa wielo-
miany Q(x) i R(x) takie że
(a) W (x) = V (x) � Q(x) + R(x)
(b) st(R(x)) < st(V (x))
Wielomian Q(x) nazywamy ilorazem a R(x) resztą z dzielenia W (x) przez V (x). Iloraz
i reszta są wyznaczone jednoznacznie, to znaczy istnieje tylko jedna para Q(x), R(x)
spełniająca warunki (a) i (b).
Dowód: Najpierw przedstawimy
Algorytm dzielenia wielomianów
Dane wejściowe: Dwa wielomiany W (x) = anxn+� � �+a0 oraz V (x) = bmxm+� � �+b0.
Zakładamy przy tym, że an = 0 i bm = 0, czyli że W (x) jest stopnia n, a V (x) jest

stopnia m.
Dane wyjściowe: iloraz Q(x) oraz reszta R(x)
Podstaw Q(x) := 0 oraz R(x) := W (x);
dopóki st(R(x)) = k e" m wykonuj:
Niech ckxk będzie składnikiem R(x) z najwyższym wykładnikiem.
Podziel ckxk przez bmxm.
ck
Podstaw Q(x) := Q(x) + xk-m
bm
ck
Podstaw R(x) := R(x) - xk-m � V (x)
bm
Jeżeli st(R(x)) < m, to
koniec, para Q(x), R(x) spełnia warunki (a) i (b).
1.15. Wielomiany 21
Aby udowodnić, że przedstawiony algorytm poprawnie oblicza iloraz i resztę, poka-
żemy, przez indukcję, że warunek (a) jest spełniony po każdym kolejnym wykonaniu pętli
dopóki. Na początku welomiany Q(x) = 0 oraz R(x) = W (x) spełniają warunek (a).
Oznaczmy wartości wielomianów Q(x) i R(x) przed i -tym wykonaniem pętli dopóki
przez Q1(x) i R1(x), a wartości po i -tym wykonanu pętli przez Q2(x) i R2(x). Zakła-
damy przy tym, że W (x) = V (x) � Q1(x) + R1(x), że stopień st(R1(x)) e" m, oraz że
ckxk jest składnikiem R1(x) z najwieększym wykładnikiem. W trakcie i-tego wykonania
pętli nastąpią podstawienia
ck
Q2(x) := Q1(x) + xk-m
bm
oraz
ck
R2(x) := R1(x) - xk-m � V (x).
bm
Mamy teraz
ck
R1(x) := xk-m � V (x) + R2(x)
bm
oraz
ck
W (x) = Q1(x)�V (x)+R1(x) = (Q1(x)+ xk-m)�V (x)+R2(x) = Q2(x)�V (x)+R2(x),
bm
czyli Q(x) oraz R(x) spełniają warunek (a) po i tym wykonaniu pętli.
Zauważmy, że stopień wielomianu R2(x) jest mniejszy od stopnia wielomianu R1(x),
ck
ponieważ w wielomianie R2(x) = R1(x) - xk-m � V (x). współczynnik przy xk jest
bm
równy 0 i stopień st(R2(x)) < k. Tak więc pętla (3) nie może się wykonywać więcej niż
n - m razy. Po wyjściu z pętli stopień st(R(x) < st(V (x)), czyli spełniony jest warunek
(b).
Pokazaliśmy więc, że wielomian W (x) można przedstawić w postaci W (x) = Q(x) �
V (x) + R(x) tak, żeby st(R(x)) < st(V (x)). Teraz pokażemy, że iloraz Q(x) i reszta
R(x) są wyznaczone jednoznacznie. Przypuśćmy bowiem, że
W (x) = Q1(x)V (x) + R1(x)
oraz
W (x) = Q2(x)V (x) + R2(x)
i że st(R1(x)), st(R2(x)) < st(V (x)). Po odjęciu tych równości stronami otrzymamy
0 = (Q1(x) - Q2(x))V (x) + (R1(x) - R2(x)).
Jeżeli wielomiany Q1(x) = Q2(x), to wielomian (Q1(x) - Q2(x))V (x) ma stopień

większy lub równy od st(V (x)), a wielomian R1(x) - R2(x) ma stopień mniejszy od
st(V (x)), więc ich suma nie może być wielomianem zerowym. Doszliśmy więc do sprzecz-
ności, czyli Q1(x) = Q2(x), z tego zaś wynika, że R1(x) = R2(x).
Przykład 1.37 Podzielmy wielomian W (x) = 8x3 + 6x2 + 3x + 2 przez wielomian
V (x) = 2x - 1 według opisanego wyżej algorytmu.
22 Rozdział 1. Podstawowe pojęcia, oznaczenia
Najpierw podstawiamy Q(x) := 0 oraz R(x) := 8x3 + 6x2 + 3x + 2. Ponieważ
st(R(x)) = 3 > 1 = st(V (x)) przechodzimy do pętli dopóki Dzielimy składnik 8x3
przez 2x otrzymując 4x2 i podstawiamy
R(x) := R(x) - 4x2V (x) = 8x3 + 6x2 + 3x + 2 - 4x2(2x - 1) = 10x2 + 3x + 2.
oraz
Q(x) := Q(x) + 4x2 = 4x2.
Zauważmy, że spełniony jest warunek W (x) = Q(x) � V (x) + R(x).
Ponieważ st(R(x)) jest większy od 1 wykonujemy ponownie instrukcje pętli. Dzielimy
składnik 10x2 przez 2x otrzymując 5x i podstawiamy
R(x) := R(x) - 5xV (x) = 10x2 + 3x + 2 - 5x(2x - 1) = 8x + 2.
oraz
Q(x) := Q(x) + 5x = 4x2 + 5x.
(warunek W (x) = Q(x) � V (x) + R(x) jest spełniony).
Stopień st(R(x)) jest równy 1, więc wykonujemy ponownie instrukcje pętli. Dzielimy
składnik 8x przez 2x otrzymując 4 i podstawiamy
R(x) := R(x) - 4V (x) = 8x + 2 - 4(2x - 1) = 6.
oraz
Q(x) := Q(x) + 4 = 4x2 + 5x + 4.
Warunek W (x) = Q(x) � V (x) + R(x) jest spełniony i teraz stopień st(R(x)) = 0 < 1
więc algorytm kończy pracę. Wielomian Q(x) = 4x2 + 5x + 2 jest ilorazem a wielomian
R(x) = 6 resztą.
1.15.2 Schemat Horna
Aby obliczyć wartość wielomianu P (x) w jakimś konkretnym punkcie x0 moglibyśmy
n
bezpośrednio skorzystać ze wzoru P (x0) = aixi . W ten sposób potrzebujemy, w
i=0 0
najgorszym przypadku, około n2 mnożeń. Istnieje jednak sposób wymagający tylko n
mnożeń. Należy obliczać wartość wielomianu według schematu
P (x0) = ((. . . (an � x0 + an-1) � x0 + an-2) � x0 + � � � a1) � x0 + a0.
Jest to tak zwany schemat Horna. Dokładniej możemy go przedstawić następująco:
Algorytm obliczania wartości wielomianu, schemat Horna
Dane wejściowe: współczynniki a0, a1, ... ,an wielomianu P (x) = an � xn + � � � + a0
oraz argument x0.
Dane wyjściowe: wartość wielomianu y0 = P (x0) = anxn + � � � + a1x0 + a0.
0
y0 := an;
dla kolejnych i od 1 do n wykonuj
y0 := y0 � x0 + an-i
1.16. Zadania 23
1.15.3 Pierwiastki wielomianu
Pierwiastkiem wielomianu W (x) jest każda liczba rzeczywista a, która podstawiona do
wielomianu da wartość W (a) = 0. Zachodzi
Twierdzenie 1.38 (B�zout) Liczba a jest pierwiastkiem wielomianu W (x) wtedy i tylko
wtedy, gdy W (x) dzieli się przez x-a, czyli, gdy istnieje wielomian Q(x) taki, że W (x) =
Q(x)(x - a).
Dowód: Jeżeli W (x) = Q(x)(x - a), to W (a) = Q(a)(a - a) = 0.
Niech teraz W (a) = 0. Podzielmy W (x) przez x - a, otrzymamy
W (x) = Q(x)(x - a) + R(x)
przy czym stopień R(x) jest mniejszy od 1, czyli jest stałą R(x) = r. Wstawiając teraz a
do obu stron otrzymamy
0 = Q(a)(a - a) + r,
czyli r = 0 i W (x) = Q(x)(x - a).
Wniosek 1.39 Jeżeli wielomian nie jest tożsamościowo równy zero, to liczba jego pier-
wiastków nie jest większa od jego stopnia.
Dowód: Niech a1,...,ak będą różnymi pierwiastkami wielomianu W (x). Z twierdzenia
B�zout mamy W (x) = Q1(x)(x - a1). Po podstawieniu a2 mamy 0 = W (a2) =
Q1(a2)(a2 - a1), czyli a2, jest pierwiastkiem wielomianu Q1(x). Korzystając znowu
z twierdzenia B�zout otrzymamy W (x) = Q2(x)(x - a2)(x - a1), i tak dalej. W końcu
otrzymamy, że W (x) jest postaci W (x) = Q(x)(x - ak) � � � (x - a2)(x - a1), czyli
stopień W (x) musi być większy od k.
1.16 Zadania
4 3 4 3 2
1. Oblicz: a) i2i, b) k3, c) (n2 -1), d) ij2, e)
i=1 k=1 n=1 i=1 j=1
2 4
(k - n),
k=1 n=1
5 4 4
2. Oblicz: a) (i + 1), b) (2k + 1), c) (n2 - 1).
i=1 k=1 n=1
3. Niech A = {1, 2, 3, 4, 5}, B = {1, 3, 5, 7} i C = {4, 5, 6, 7, 8}. Oblicz A *" B *" C,
A )" B )" C, A - B, A )" (B - C), A �" B, A �" B �" C.
4. Niech I = {1, 2, 3, 4, 5} będzie zbiorem indeksów. Dla każdego i " I określamy
zbór Bi = {x " N | i d" x d" 2i}. Oblicz Bi, Bi, B1 �" B3 �" B5 oraz
i"I i"I
B1 �" B2 �" B3 �" B4 �" B5.
5. Niech I = {1, 2, 3, 4, 5}. Dla każdego i " I mamy Ai = {3i - 3, 3i, 3i + 3}.
Oblicz Ai, Ai, oraz A1 �" A2 �" B3 �" B4 �" A5.
i"I i"I
24 Rozdział 1. Podstawowe pojęcia, oznaczenia
6. Niech I = {1, 2, 3, 4, 5} będzie zbiorem indeksów. Dla każdego i " I określamy
zbór Ci = {x " N | 1 d" x d" 30 oraz i dzieli x}. Oblicz Ci oraz Ci.
i"I i"I
7. Niech A = {1, 2, 3, 4}, B = {1, 2, 3}. Wypisz elementy A � B, B � A oraz
{(a, b) " A � B | a < b}.
8. Niech X = {a, b, c}. Wypisz elementy X2, X3 oraz {(x, y) " X2 | x = y}.

9. Wypisz wszystkie podzbiory: a) zbioru pustego ", b) zbioru {a}, c) zbioru {a, b, c, d}.
10. Udowodnij, że A �" B wtedy i tylko wtedy gdy A )" B = A.
11. Narysuj wszystkie grafy ze zbiorem wierzchołków V = {a, b, c}. Które z nich są
spójne?
12. Narysuj wszystkie drzewa ze zbiorem wierzchołków V = {a, b, c}.
13. Narysuj wszystkie grafy skierowane ze zbiorem wierzchołków V = {a, b}.
14. Narysuj graf G = (V, E), ze zbiorem wierzchołków V = {a, b, c, d, e} i zbiorem
krawędzi E = {{a, b}, {a, c}, {b, c}, {a, d}, {d, e}}. Czy graf G jest spójny? Czy
posiada cykle?
15. Narysuj graf skierowany G = (V, E), ze zbiorem wierzchołków V = {a, b, c, d} i
zbiorem krawędzi E = {(a, b), (b, c), (c, b), (c, d), (d, d)}.
16. Wypisz 10 pierwszych słów zbioru {a, b, c}" według porządku leksykograficznego
i kanonicznego.
17. Wypisz wszystkie prefiksy i sufiksy słowa aaba.
18. Uporządkuj następujący zbiór słów według porządku leksykograficznego i kano-
nicznego: słowik, wróbel, kos, jaskółka, kogut, dzięcioł, gil, kukułka, szczygieł,
sowa, kruk, czubatka, drozd, sikora i dzierlatka, kaczka, gąska, jemiołuszka, dudek,
trznadel, pośmieciuszka, wilga, zięba, bocian, szpak. [Fragment wiersza Ptasie ra-
dio Juliana Tuwima]
19. Udowodnij wzory (1.1), (1.2), (1.3), (1.4).
20. Udowodnij lemat 1.31,
21. Udowodnij zależności z przykładów 1.28, 1.29, 1.30.
22. Niech x, y będą dowolnymi liczbami rzeczywistymi, a k dowolną liczbą całkowitą.
Udowodnij następujące zależności:
x + y e" x + y .
x + k = x + k.
x + y d" x + y .
x + k = x + k.
1.16. Zadania 25
23. Podaj przykład liczb rzeczywistych x i y, dla których zachodzi a) x + y > x +
y , b) x + y < x + y .
24. Podaj przykład liczby rzeczywistej x i liczby całkowitej k, dla których zachodzi
k � x < k � x .
25. Za pomocą algorytmu sortowania bąbelkowego posortuj ciągi: a) 1,3,5,4,2; b)
8,1,6,3,4,5,2,7.
26. Dane są dwa wielomiany U(x) = 4x3 +3x+2 oraz V (x) = 2x4 +x2 +3x. Oblicz
ich sumę oraz iloczyn. Oblicz według schematu Horna wartości U(1) oraz V (1).
27. Podziel wielomian U(x) = 4x4 + 3x2 + x - 2 przez V (x) = x2 + x.