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:
md1Panasonic chassis MD1md1więcej podobnych podstron