Md1

Matematyka Dyskretna
Andrzej Szepietowski
25 czerwca 2002 roku
Rozdział 1
Oznaczenia
W tym rozdziale przedstawimy podstawowe oznacznia.

oznacza kwantyfikator ogólny "dla każdego". oznacza kwantyfikator szczegółowy
"istnieje".
1.1 Sumy
Majac dany skończony ciag , ,... , sum� jego elementów zapisujemy jako
� � e

Niezbyt formalnie możemy to zapisać

Jako przykład zastosujmy symbol sumy do zapisu wzoru na ciagu arytmetycznego).
sumę �

(1.1)

oraz wzoru na sumę ciagu geometrycznego).
�

(1.2)

(wzór (1.2) jest słuszny dla każdego )

B� też używać zapisu typu
edziemy

3
4 Rozdział 1. Oznaczenia
W tym przypadku zbiór indeksów określony jest za pomoca warunku pod znakiem sumy.
�
Warunek określajacy indeksy, po których należy sumować może być bardziej skompliko-
�

wany, na przykład

Stosować bedziemy także zapis
�

oznaczajacy sum� tych elementów , których indeksy należa do skończonego zbioru
� e �

indeksów . Na przykład, jeżeli , to

Możemy też sumować ciągi, których elementy zależą od dwóch indeksów,

Za pomocą podwójnej sumy możemy na przykład przedstawić uogólnione prawo roz-
dzielności mnożenia względem dodawania:

(1.3)

a także wzór na podnoszenie sumy do kwadratu:

(1.4)

1.2 Iloczyny
Aby zapisać iloczyn elementów ciagu , ,... , stosujemy zapis
�

Znów niezbyt formalnie możemy to zapisać jako

1.3. Zbiory 5
1.3 Zbiory

oznacza zbiór pusty, który nie zawiera elementów.
żadnych

oznacza zbiór liczb naturalnych .

oznacza zbiór liczb całkowitych.

oznacza zbiór liczb wymiernych.

oznacza zbiór liczb rzeczywistych.
,
oznacza, że elment należy do zbioru , że elment nie należy do

zbioru . Najprostszy sposób zdefiniowania zbioru polega na wypisaniu jego elementów

w nawiasach klamrowych. Na przykład zbiór zawiera elementy 1,2,3. Inny spo-

sób definiowania zbioru polega na podaniu własności, która spełniaja elementy zbioru.
� �

Na przykład oznacza zbiór liczb naturalnych wiekszych od 3 i
�

mniejszych od 7.

�
oznacza moc zbioru , czyli liczbe jego elementów.

oznacza sum� zbiorów, czyli zbiór, który zawiera elementy, które należą do lub
e

do :

lub

A zatem suma zawiera wszystkie elementy zbioru i wszystkie elementy zbioru
.
oznacza iloczyn lub przekrój zbiorów, czyli zbiór, który zawiera te elementy,
które należa do obu zbiorów naraz.
�

i

oznacza różnice zbiorów, czyli zbiór, który zawiera te elementy, które należa
� �
do i nie należa do .
�

i

Przykład 1.1 Dla i mamy:

oznacza, że zbior zawiera sie w zbiorze , to znaczy wszystkie elementy zbioru
�

należa do zbioru .
�

Dwa zbiory sa równe jeżeli zawieraja te same elementy, lub inaczej wtedy i tylko
� �
wtedy gdy i .

Jak widać kolejność elementów w zapisie zbioru nie ma znaczenia. I tak na przykład

. Taki zbiór dwuelementowy nazywamy czasami para nieuporzadkowana.
� � �
W poniższym lemacie zebrano podstawowe własności operacji sumy i iloczynu zbio-
rów.
6 Rozdział 1. Oznaczenia

Lemat 1.2 (przemienność sumy).

(przemienność iloczynu).

�
(łaczność sumy).

(łaczność iloczynu).
�

(rozdzielność sumy wzgledem iloczynu).
�

(rozdzielność iloczynu wzgledem sumy).
�

, , , ,
1.4 Różnica symetryczna zbiorów
� � �
oznacza różnice symetryczna zbiorów, która zawiera elementy należace tylko do
jednego z dwóch zbiorów:

Przykład 1.3

W poniższym lemacie zebrano podstawowe własności różnicy symetrycznej zbiorów.

Lemat 1.4 (przemienność).

(łaczność).
�

(rozdzielność wzgledem iloczynu).
�

, .

Jeżeli , to .

Dowód:
Udowodnimy, tylko dwie tożsamości, dowód pozostałych pozostawiamy czytelnikowi
jako ćwiczenie.

Aby pokazać, że różnica symetryczna jest łączna wystarczy zauważyć, że zbiór

�
lub zawiera te elementy, które należa do nieparzystej liczby zbiorów,
czyli te, które należa tylko do , plus te, które należa tylko do , plus te, które należa
� � �

tylko do , plus te, które należa do przekroju .
�

Udowodnimy teraz ostatnią implikację. Jeżeli , to

1.5. Iloczyn kartezjański 7
Twierdzenie 1.5 Różnica symetryczna zbiorów:

zawiera elementy, które należa do nieparzystej liczby spośród zbiorów , .
�

Dowód przez indukcje ze wzgledu na . Twierdzenie jest oczywiste dla lub
� �
. Załóżmy teraz, że jest ono prawdziwe dla i rozpatrzmy:

Zbiór ten zawiera te elementy, które należa do i nie należa do ,
� �

oraz te, które nie należa do i należa do . W pierwszym przypad-
� �

ku sa to elementy, które nie należa do i na mocy założenia indukcyjnego należa
� � �

do jakiejś nieparzystej liczby zbiorów spośród . W drugim przypadku sa to
�

elementy, które należa do , a także do pewnej parzystej liczby zbiorów spośród
�

. Razem mamy wszystkie elementy należace do nieparzystej liczby zbiorów
�

spośród .
1.5 Iloczyn kartezjański

Para uporzadkowana jest to dwuelementowy ciąg . Mamy wtedy i
�

tylko wtedy gdy oraz . Dopuszczalne jest także .

�
oznacza iloczyn kartezjański zbiorów i . Jest to zbiór wszystkich uporzadkowanych
par , w których i . Inaczej

Przykład 1.6 Dla i mamy

Można łatwo wykazać, że

1.6 Rodzina zbiorów
Czasami będziemy mieli do czynienia ze zbiorem, którego elementami są zbiory. Przez

lub

będziemy oznaczać zbiór wszystkich podzbiorów zbioru .

Przykład 1.7 Dla

8 Rozdział 1. Oznaczenia

Zbiór zbiorów czasami rodzina zbiorów. Na przykład
nazywamy �

jest rodzina zawierajaca cztery zbiory , , i , sa to elementy zbioru . Możemy
� � � �

też zapisać .

Możemy sumować zbiory z rodziny. Suma

zawiera te elementy, które należa do któregoś ze zbiorów , , ... , , czyli
�

Inaczej możemy to zapisać:

B� też używać zapisu
edziemy

na oznaczenie sumy wszystkich zbiorów , których indeksy należa do zbioru . Zacho-
�

dzi wtedy

Zbiór indeksów sumowania może być określony za pomoca warunku.
�

Możemy też brać przekroje zbiorów z rodziny. Przekrój

zawiera te elementy, które należa do wszystkich zbiorów , , ... , , czyli
�

Inaczej możemy to zapisać:

1.7. Słowa 9

B� też używać zapisu
edziemy

na oznaczenie przekroju wszystich zbiorów , których indeksy należa do zbioru . Za-
�

chodzi wtedy

Zbiór indeksów przekroju może być za pomoca warunku.
określony �

Przykład 1.8 Wezmy rodzine złożona z trzech zbiorów , ,
� �

.

Przykład 1.9 Niech bedzie zbiorem indeksów. Dla każ-
�

dego określamy zbór . Mamy:

1.7 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.10 Na przykład, jeżeli , to zawiera słowo puste , dwa słowa

jednoliterowe i , cztery słowa dwuliterowe , , i , osiem słów trzyliterowych

, , i , , , i , i tak dalej.

Długość słowa jest to liczba jego liter, będziemy ją oznaczać przez . Dłu-

gość słowa pustego . Zbiór wszystkich słów długości nad alfabetem oznacza-
my przez

Dla słów możemy określić operację konkatenacji, lub składania słów. Konkatenacja lub

złożenie dwóch słów , , oznaczana przez , jest to sklejenie słów i . Do słowa

dopisujemy na końcu słowo . Dla dowolnego słowa zachodzi .

10 Rozdział 1. Oznaczenia

Przykład 1.11 Konkatenacja słów i to sówo .

Słowo jest prefiksem lub przedrostkiem słowa , jeżeli istnieje takie słowo , że

. Podobnie, słowo jest sufiksem lub przyrostkiem słowa , jeżeli istnieje takie

słowo , że .
Przykład 1.12 Na przykład jest prefiksem słowa , a słowo jest sufiksem

słowa . Słowo puste jest prefixem i sufiksem dowolnego słowa . Każde słowo

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 litera stoi przed . Możemy

też 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 , , 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 , albo jedno
ze słów jest prefiksem drugiego, wtedy wcześniejszy w porządku leksykograficznym jest
prefiks.
Przykład 1.13 W porządku leksykograficznym słowo jest wcześniejsze od słowa ,

a to jest wcześniejsze od .

Porządek leksykograficzny jest wygodny, jeżeli zbiór słów jest skończony. Zauważmy, że

w zbiorze wszystkich słów nieskończenie wiele słów (wszystkie słowa złożone

tylko z litery ) poprzedza słowo . Dlatego czasami stosuje się inny porządek, tak zwany

porządek kanoniczny.

Słowo poprzedza słowo w porządku kanonicznym, jeżeli:

albo ,

albo i poprzedza w porządku leksykograficznym.

Przykład 1.14 Początkowe słowa zbioru uporządkowane według porządku kano-

nicznego to:

1.8 Zaokr�
aglenia
Wprowadzmy dwa oznaczenia na zaokraglenie liczby rzeczywistej. Dla dowolnej liczby
�
rzeczywistej

oznacza zaokraglenie w góre do najbliższej liczby całkowitej.
� �

oznacza zaokraglenie w dół do najbliższej liczby całkowitej.
�

Zaokrąglenie nazywamy sufitem z , a zaokrąglenie nazywamy podłogą z .

1.9. Przedrostki 11
Przykład 1.15

1.9 Przedrostki
W przypadku bardzo dużych lub bardzo małych wartości używa sie czasami jednostek
�
miar bedacych wielokrotnościami lub podwielokrotnościami podstawowych jednostek.
� �
Takie jednostki wyraża sie przez dodanie do nazwy jednostki odpowiedniego przedrostka,
�
a do oznaczenia tej jednostki dodaje sie oznaczenie przedrostka. W nastepujacej tabeli
� � �
zebrano te przedrostki.

Przedrostek Oznaczenie Wielokrotność

exa E

peta P

tera T

giga G

mega M

kilo k

hekto h

deka da

Przedrostek Oznaczenie Podwielokrotność

decy d

centy c

mili m

mikro

nano n

piko p

femto f

atto a
Przykładami tak utworzonych jednostek sa: centymetr (cm), milimetr (mm), hehtopa-
�
skal, hektolitr, kilogram (kg), kilowat (kW). Do mierzenia predkości (zegara) procesora
�
używa sie megahertzów. Jeden megahertz (MHz) to jednostka cz równa miliono-
� estości
�

wi impulsów na sekunde. Kilobajtów, megabajtów i gigabajtów używa sie do mierzenia
� �

liczby komórek pamieci. Czesto przyjmuje sie, że kilobajt ma bajtów, megabajt
� � �

bajtów, a gigabajt bajtów.
1.10 Notacja asymptotyczna
W analizie jakiegoś algorytmu (programu) ważne jest oszacowanie jego czasu działania.
Jako przykład wezmy algorytm sortowania bąbelkowego, który ustawia elementy ciągu
wejściowego w porządku niemalejącym.
12 Rozdział 1. Oznaczenia
Algorytm sortowania bąbelkowego.

Aby posortować ciąg długości :

(1) wykonujemy co następuje razy:

(1a) wskazujemy na pierwszy element,

(1b) wykonujemy co następuje razy:
porównujemy wskazany element z elementem następnym,
jeżeli porównane elementy są w niewłaściwej kolejności, to zamieniamy je
miejscami,

wskazujemy na następny element.

W poniższej tabeli zilustrowano zastosowanie algorytmu dla ciągu .

4 1 2

3 1 2

3 1 2

1 2 4

1 2 4

1 2 4

2 3 4

1 3 4

1 2 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 (1) 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 (1) kolejny największy element znajdzie swoją wła-
ściwą pozycję.

Czas działania algorytmu zależy od liczby elementów w ciągu. Pętla zewnętrzna

(1) jest wykowywana razy. W każdej iteracji pętli zewnętrznej pętla wewnętrzna (1b)

również jest wykonywana 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 algorytm w

sumie wykonuje kroków, gdzie 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 i będą dwiema funkcjami określonymi na zbiorze liczb naturalnych o war-
tościach w zbiorze dodatnich liczb rzeczywistych

Wtedy:
1.10. Notacja asymptotyczna 13

, jeżeli istnieje dodatnia stała taka, że

dla prawie wszystkich , to znaczy istnieje , takie, że dla

każdego . W takim przypadku mówimy, że funkcja jest O duże od .

, jeżeli
. W takim przypadku mówimy, że funk-

cja jest o małe od .

, jeżeli istnieje dodatnia stała taka, że dla

prawie wszystkich . W takim przypadku mówimy, że funkcja jest Omega

duże od .

, jeżeli istnieją dwie dodatnie stałe takie, że

dla prawie wszystkich . W takim przypadku mówimy, że
funkcja jest Theta duże od .

Jeżeli , to mówimy, że funkcja ogranicza z góry funkcję (z

dokładnością do stałej), albo, że rząd funkcji jest nie większy od rzędu funkcji .
Przykład 1.16

Czas działania algorytmu sortowania bąbelkowego jest .

.

.

.

.

.

Będziemy dopuszcza ć notację asymptotyczną także wobec funkcji, które są dodatnie

dla prawie wszystkich liczb naturalnych. Na przykład .

Jeżeli , to mówimy, że jest niższego rzędu niż .
Przykład
1.17

.

.

.

Jeżeli , to i są tego samego rzędu, czyli oraz

.
Przykład
1.18

.
14 Rozdział 1. Oznaczenia

.
Następujący lemat jest bardzo użyteczny przy szacowaniu asymptotycznym. Jego do-
wód zostawiamy jako ćwiczenie.

Lemat 1.19 Jeżeli granica istnieje i jest właściwa (nie jest równa ), to

.

Wniosek 1.20 Jeżeli , to .
Następujący przykład pokazuje, że oszacowanie asymptotyczne może być zawodne.

Przykład 1.21 Wezmy dwie funkcje oraz . Mamy

, ale dla wszystkich , czyli dla wszystkich liczb mniejszych

od liczby atomów w naszej galaktyce (porównaj podrozdział duże liczby w rozdziale o
arytmetyce).
Z drugiej jednak strony oszacowanie asymptotyczne wystarczy do naszych celów i
jest łatwiejsze do uzyskania.

Przykład 1.22 Rozważmy trzy algorytmy: pierwszy działający w czasie ,

drugi w czasie i trzeci w czasie . Funkcje te określają czas

działania na pewnym konkretnym komputerze. Niech , i oznazczają długości

wejść, dla których algorytmy dają odpowiedz w ciągu jednej sekundy, to znaczy

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ż . Dla drugie-

go algorytmu działającego w czasie sześciennym możemy teraz obliczać 10 razy dłuższe

dane wejściowe, ponieważ . Dla trzeciego algorytmu działają-

cego w czasie wykładniczym możemy teraz obliczać tylko dane wejściowe o 10 dłuższe,

ponieważ .
1.11 Zadania

1. Oblicz dla .

2. Oblicz .

3. Oblicz .

4. Niech , i . Oblicz ,

, , , , .

5. Niech bedzie zbiorem indeksów. Dla każdego określamy
�

zbór . Oblicz , , oraz

.

1.11. Zadania 15

6. Niech , . Wypisz elementy oraz
,

7. Niech bedzie zbiorem indeksów. Dla każdego określamy
�

zbór oraz dzieli . Oblicz oraz .

8. Uporządkuj następujący zbiór słów [Fragment wiersza Ptasie radio Juliana Tu-
wima] według porządku leksykograficznego i kanonicznego: słowik, wróbel, kos,
jaskółka, kogut, dzięcioł, gil, kukułka, szczygieł, sowa, kruk, czubatka, drozd, siko-
ra i dzierlatka, kaczka, gąska, jemiołuszka, dudek, trznadel, pośmieciuszka, wilga,
zięba, bocian, szpak.
9. Udowodnij wzór (1.1) na sumę ciągu arytmetycznego.
10. Udowodnij wzór (1.2) na sumę ciągu geometrycznego.
11. Udowodnij wzór (1.3).
12. Udowodnij wzór (1.4).
13. Udowodnij lemat 1.19,
14. Udowodnij zależności z przykładów 1.16, 1.17, 1.18,

Wyszukiwarka

Podobne podstrony:
md1
Panasonic chassis MD1
md1

więcej podobnych podstron