Darmowy fragment publikacji:
• Kup książkę
• Poleć książkę
• Oceń książkę
• Księgarnia internetowa
• Lubię to! » Nasza społeczność
Spis treści
Wstęp ������������������������������������������������������������������������������������������������������������������������� 6
1� W kolejce po bułki ����������������������������������������������������������������������������������������������������7
2� Spotkanie u Jacha i Krzycha �����������������������������������������������������������������������������������13
3� Czasu nie ma, są tylko zegary ��������������������������������������������������������������������������������17
4� Na skraju lasu �����������������������������������������������������������������������������������������������������������21
5� Pułapka na pana Czesława �������������������������������������������������������������������������������������29
6� Kalendarz w jednym wzorze ����������������������������������������������������������������������������������35
7� Jachu w pułapce jasnowłosej ����������������������������������������������������������������������������������39
8� Ile zarabia Totalizator Sportowy ����������������������������������������������������������������������������43
9� Nie psuj mi szyków �������������������������������������������������������������������������������������������������47
10� Wodne mistrzostwa piłkarskie ����������������������������������������������������������������������������55
11� Kanciaste kotki ������������������������������������������������������������������������������������������������������61
12� Karciana sztuczka �������������������������������������������������������������������������������������������������69
4
Spis treści
13� Ryby a statystyka ...................................................................................................75
14� Jak zostać oszustem ..............................................................................................79
15� Geometria bazgrołów ...........................................................................................83
16� Moc jedności .......................................................................................................101
17� Po co nam liczby pierwsze .................................................................................107
18� Karton na tik-taki ...............................................................................................113
19� Zbiory Julii ...........................................................................................................119
20� Ile liczb mieści się na końcu igły .......................................................................127
21� Pranie pieluch ......................................................................................................133
22� Jak szybko spada spadochroniarz .....................................................................143
23� Liczba Eugeniusza ...............................................................................................149
Bibliografia ����������������������������������������������������������������������������������������������������������� 164
Skorowidz ������������������������������������������������������������������������������������������������������������� 166
5
19.
Zbiory Julii
— Zabieram cię na wystawę obrazów generowanych komputerowo, której tytuł
brzmi Zbiory Julii — oznajmił uroczyście Jachu zdziwionemu niecodziennym po-
mysłem przyjacielowi.
— Dziś na wystawę jest wstęp wolny, a poza tym co jakiś czas trzeba mieć kontakt
ze sztuką, choćby i tworzoną przez komputer.
Krzychu poddał się milcząco rozporządzeniu Jacha i po krótkim marszu, dla zdro-
wia i zaoszczędzenia pieniędzy za przejazd, byli już na wystawie. Po obejrzeniu
pierwszych obrazów Krzychu nie krył swojego rozczarowania.
119
19
— Sądząc po nazwie, spodziewałem się tu zobaczyć obrazy kobiety, jakieś portre-
ty, surrealistyczne pejzaże, a tymczasem plamy jakieś widzę. Może to i ładne jest,
ale co ma do tego Julia?
— Julia [wym. Żulia] był francuskim matematykiem, który odkrył te plamy i po-
kazał, jak je otrzymywać jeszcze w erze przedkomputerowej. Ich powtórne odkry-
cie zawdzięczamy nieżyjącemu już matematykowi. Benoit Mandelbrot był twórcą
pojęcia fraktala — wymądrzał się Jachu, korzystając z treści wcześniej przeczyta-
nej ulotki, którą dostał przy wejściu na wystawę.
— Jak komputery mogą tworzyć te obrazy? — zastanawiał się Krzychu już w nie-
co lepszym humorze, bo choć to nie były obrazy, których się spodziewał, to wśród
licznie przybyłych na wystawę znalazł obiekty pięknie wyrzeźbione przez naturę,
którym mógł się długo przyglądać, tak były pochłonięte podziwianiem rozwie-
szonych wszędzie czarno-białych eksponatów.
— Patrz na tę w rogu po przeciwnej stronie sali — szepnął do Jacha, który zastana-
wiał się, czy jego przyjaciel ma na myśli obraz przypominający delikatną koronkę,
czy blondynkę o zamyślonej twarzy wpatrującą się w ten obraz. — Niezła figura.
Jachu jednak powoli przestawiał się na odbiór generowanych przez komputer ob-
razów i próbował sobie wyobrazić proces ich tworzenia. Przypominały mu chmu-
ry, bajkowe stwory, wzory tworzone na szybach przez mróz.
Komentarz
Spróbujemy wyjaśnić, jak komputer może generować obrazy, które bezsprzecznie
mają walory artystyczne. Ponieważ mówimy tu o obrazach tworzonych na płasz-
czyźnie, więc zajmijmy się na początek płaszczyzną. Zacznijmy od tego, że po
umieszczeniu na płaszczyźnie dwóch osi współrzędnych położenie każdego punk-
tu możemy określić za pomocą dwóch liczb, podobnie jak na osi liczbowej za po-
mocą jednej — jego odległości od punktu 0 wziętej ze znakiem plus albo minus
w zależności od położenia punktu względem zera. Podobnie też jak na liczbach
możemy rachować na parach liczb — możemy je dodawać, odejmować, mnożyć
i dzielić. Żeby wszystkie te działania były podobne do działań na liczbach rzeczy-
wistych, wyrażone są one za pomocą poniższych wzorów:
(
(
a
,
a
,
)
)
b
b
+
−
(
(
c
c
,
,
)
)
d
d
=
=
(
(
+
a c
−
a c
,
,
+
b d
−
b d
)
)
120
Zbiory Julii
)
⋅ + ⋅
a d b c
⋅ − ⋅
b c a d
2
2
d
c
+
,
, oprócz przypadku, gdy
(
(
(
a
,
a
,
c
,
,
b
d
=
) (
⋅
c
) (
c
/
)
(
d =
(
)
⋅ − ⋅
a c b d
,
⋅ + ⋅
a c b d
)
=
d
2
2
d
c
)
0, 0
.
+
b
,
a
a
a a
) 0
+ = + = oraz 1 1
a a
0 0
(
+ − = , a dla każdej liczby
Wyjaśnijmy krótko, co oznacza to podobieństwo. Wiemy ze szkoły, że cztery pod-
stawowe działania na liczbach rzeczywistych mają pewne własności. Dodawanie
i mnożenie są łączne. Istnieją dla nich tak zwane elementy neutralne, dla dodawa-
a
⋅ = ⋅ = dla każdej liczby
nia 0, dla mnożenia 1, takie że
rzeczywistej a. Dla każdej liczby rzeczywistej a istnieje też element przeciwny a− ,
1
⋅ = .
1
a
taki, że
a
Ponadto mnożenie jest rozdzielne względem dodawania. Czytelnik może spraw-
dzić, że wszystkie określone przez nas działania na parach liczbowych mają te
własności.
Możemy zatem stwierdzić, że daje się rachować na punktach płaszczyzny jak na
liczbach, a wynikiem tych działań jest również punkt na płaszczyźnie, zawsze jeśli
tylko nie będziemy dzielić przez (
0, 0 . Możemy zatem również podnosić punk-
ty do drugiej potęgi, jak w poniższych przykładach, i przyglądać się ruchowi, jaki
wykonał punkt w wyniku tego działania (zob. rysunek 19.1).
0a ≠ element odwrotny
1
a taki, że
a
)
⋅ + ⋅
⋅ − ⋅
2 2 1 1; 2 1 1 2
)
(
=
−
⋅
(
)
=
⋅
3; 4
)
0,5 0,5 0,4 0,4; 0,5 0,4 0,4 0,5
+
⋅
⋅
)
=
(
0,09; 0,4
)
0,5 0,5 0,4 0,4; 0,5 0,4 0,4 0,5
+
⋅
⋅
)
(
=
) (
(
⋅
2, 1
(
0,5; 0,4
(
=
1
2
)
2, 1
) (
⋅
0,5; 0,4
)
0,09; 0,4
1
⋅
2
3
2
3
2
;
;
=
⋅ −
1 1
2 2
3
2
⋅
3
2
;
⋅
1
2
3
2
+
3 1
⋅
2
2
= −
1
2
;
3
2
121
19
Rysunek 19.1. Jak zmieniły swoje położenie punkty podniesione do kwadratu
Zauważmy, że pierwszy punkt po podniesieniu do kwadratu zwiększył swoją od-
ległość od początku układu, drugi zmniejszył, a trzeci zmienił położenie, ale odle-
głość od początku układu nie zmieniła się. Można zadać pytanie, co by się działo,
gdybyśmy wielokrotnie powtarzali podnoszenie do kwadratu, wykonując je znów
na otrzymanym punkcie. Zauważmy, że wszystkie punkty będące w większej niż 1
odległości od początku układu „uciekną” w wyniku takiego działania do nieskoń-
czoności. Funkcja wyraża zmiany, jakie zachodzą dla punktów z chwili na chwi-
lę, kiedy dokonujemy kolejnych iteracji, czyli podstawiamy do funkcji wartość
otrzymaną z poprzedniego obliczenia i dokonujemy obliczenia wartości jeszcze
raz. Wybierając dowolny punkt płaszczyzny, możemy śledzić, co będzie się z nim
działo w wyniku działania funkcji. Taką dwójkę (
, gdzie C oznacza u nas
zbiór wszystkich punktów płaszczyzny, a f pewną funkcję określoną na tym zbio-
rze i mającą w nim swoje wartości, nazywamy układem dynamicznym. Po wybra-
,C
)
f
122
Zbiory Julii
z
;
0
n
)
;
0
;
2
(
f
=
f
z
3
z
2
=
)
;
)
)
)
)
(
)
z
1
0z
.
(
f z
(
f z
(
f z
+ =
1n
( )
f z
C∈ , czyli punktu należącego do płaszczyzny, i po doko-
niu dowolnego punktu
)
naniu na nim nieskończenie wielu iteracji z użyciem funkcji f (
) otrzy-
mamy nieskończony ciąg punktów płaszczyzny, niekoniecznie różnych, który na-
zywamy trajektorią punktu 0z i który możemy symbolicznie zapisać tak:
(
(
=
f
f z
z
0
0
( )
z= zauważyliśmy trzy różne zachowania się punk-
f z
W przypadku funkcji
tów w wyniku nieskończonej iteracji funkcji: punkty wnętrza koła o promieniu 1
i środku w początku układu współrzędnych zbiegają do punktu (
0; 0 , punkty
znajdujące się poza kołem uciekają do nieskończoności, a punkty leżące na brze-
gu koła pozostają na nim. Okrąg jednostkowy jest właśnie zbiorem Julii dla funk-
z= i stanowi granicę rozdzielającą punkty zbiegające do początku układu
cji
od tych uciekających do nieskończoności. Można przypuszczać, że różne funkcje
mają różne zbiory Julii i właśnie to dało twórcom wystawy, którą odwiedzili Jachu
i Krzychu, możliwość tworzenia piękna przy użyciu komputera. Tu opiszemy spo-
sób, w jaki możemy odróżnić od siebie punkty uciekające do nieskończoności (na-
zwijmy je „uciekinierami”) od tych, które nie uciekają (nazwijmy je „więźniami”).
Zrobimy to na przykładzie funkcji nieco bardziej skomplikowanych od naszej
funkcji kwadratowej użytej do wyjaśnienia pojęcia zbioru Julii, a mianowicie
( )
+ , gdzie c C∈ będzie pewnym ustalonym dla danej funkcji
f z
c
funkcji
punktem płaszczyzny
i chcąc obli-
(
)
=
x y
, możemy posłużyć się wzorami:
czyć
,f
f
= ⋅ − ⋅ +
y y
x x
⋅ + .
= ⋅
x y
y
2
c
. Biorąc dowolny punkt
( )
f z
x
y
x y
,c
x y
,
=
x
c
2
z
z
=
)
c
c
(
(
)
2
=
f
f
Obliczamy w ten sposób kolejne położenia punktu i jeśli ucieka on do nieskoń-
czoności, zaznaczamy punkt, od którego zaczęliśmy obliczenia, na biało na two-
rzonym obrazku, jeśli zaś nie ucieka, zaznaczamy go na czarno. W ten sposób po-
wstaje wygenerowany komputerowo obraz. Ponieważ jednak trajektoria punk-
tu ma nieskończenie wiele elementów, powstaje pytanie, jak stwierdzić, czy dany
punkt ucieknie do nieskończoności, czy nie. Otóż stwierdzono, że jeśli w pew-
)
nym momencie wartość
, wte-
dy punkt ucieka do nieskończoności. Trzeba zatem wykonać pewną liczbę itera-
cji, aby się o tym przekonać. Im jest ona większa, tym większą mamy pewność, że
punkt ucieka.
przekroczy wartość
max
, 2
R
=
+
=
(
x
y
z
c
2
2
123
19
Na rysunkach 19.2, 19.3 i 19.4 Czytelnik znajdzie kilka wygenerowanych przez
komputer obrazków. Pod nimi umieszczono informację, dla jakiej wartości c zo-
stały wykonane obliczenia.
Rysunek 19.2. Zbiór więźniów dla
)
c= -0, 745429; 0,113008
(
Rysunek 19.3. Zbiór więźniów dla
c= -0, 12256117; 0,74486177
(
)
124
Zbiory Julii
Rysunek 19.4. Zbiór więźniów dla
)
c= -1; 0
(
Jeśli zaś zechcemy przyjrzeć się z bliska wybranym fragmentom naszych rysun-
ków, to też jest to możliwe i może przynieść nam wiele niespodziewanych doznań
estetycznych. Spójrzcie tylko na rysunek 19.5.
Rysunek 19.5. Powiększony fragment rysunku 19.2
125
19
126
Skorowidz
A
abstrakcji, klasy, 92
Adelman, 110
algorytm spigot, 150
dla liczby e, 152, 153
dla liczby Eugeniusza, 161
Archimedesa, prawo, 57
arytmetyka modulo, 109
B
Barbier, E., 129, 131
bazgroły, 83, 84, 85, 86
cechy, 85
geometryczne przekształcenie
ścieżki na permutację, 90
liczbowe charakterystyki, 87
podobieństwo, 91, 92, 95, 96, 98
rozróżnianie, 91, 92, 93
stosunek kolorów, 87
symboliczny zapis, 88
ścieżka, 88, 89
zamiana ścieżki na permutację, 89
zmiana na graf, 93, 94
drzewo, wyznaczanie wysokości,
22, 23, 24
dynamiczny, układ, 122
E
e, liczba, 137
algorytm spigot, 152, 153
cyfry rozwinięcia dziesiętnego,
154
jako suma szeregu, 151
program, 153, 154
element neutralny, 121
element przeciwny, 121
estymacja statystyczna, 77
Eugeniusza, liczba, 149, 158, 159,
160
1950 miejsc za przecinkiem, 162
algorytm spigot, 161
program, 161, 162
F
Fisher, R.A, 78
geometryczne przekształcenie
ścieżki na permutację, 90
liczbowe charakterystyki, 87
podobieństwo, 91, 92, 95, 96, 98
rozróżnianie, 91, 92, 93
stosunek kolorów, 87
symboliczny zapis, 88
ścieżka, 88, 89
zamiana ścieżki na permutację, 89
zmiana bazgrołów na graf, 93, 94
graf planarny, 93
spójność, 93
spójny bez krawędzi, 95
spójny o czterech krawędziach, 96
spójny o dwóch krawędziach, 96
spójny o jednej krawędzi, 95
spójny o trzech krawędziach, 96
gry
Moc jedności, 102, 103, 104, 105
programowanie, 52
Szyki, 47, 48, 49, 50, 51, 53
w kości, 80, 81, 82
Guihaire, Benjamin, 53
D
de Buffon, 128
drugie prawo Newtona, 145
G
geometria bazgrołów, 83, 84, 85, 86
cechy, 85
H
hipergeometryczny, rozkład, 76
166
I
igła, wyznaczanie liczby π, 128, 129,
130, 131, 132
iloczyn liczb naturalnych od 1
do n, 10
impreza
czas trwania, 16
obliczenie liczby gości, 14, 15, 16
J
jednostka tysięczna, 27
jezioro, oszacowanie liczby ryb, 77
Julia, 120
Julii, zbiory, 119, 123
K
kalendarz, wzór na dzień tygodnia,
36, 37
karciana łamigłówka, 69, 70, 71,
72, 74
program, 72, 73
kąty
jednostka miary, 27
system mierzenia, 27
kino, rozmieszczenie widzów, 31, 33
klasy abstrakcji, 92
klucz jawny, 110
tworzenie, 110, 111
klucz tajny, 110
tworzenie, 110, 111
Knuth, Donald, 150
kolejka, sposób ustawienia, 7, 8,
komputer, generowanie obrazów,
koperta, rysowanie
otwarta, 41
zamknięta, 41
kratowe, punkty, 62, 63
kryptografia z kluczem publicznym,
9, 10
120
110
L
Leclerc, Georges-Luis, 128
liczba e, 137
algorytm spigot, 152, 153
cyfry rozwinięcia dziesiętnego, 154
program, 153, 154
liczba Eugeniusza, 149, 158, 159,
160
1950 miejsc za przecinkiem, 162
algorytm spigot, 161
program, 161, 162
liczba π, wyznaczanie, 128, 129, 130,
131, 132
liczby pierwsze, 108
definicja, 108
w postaci 6k+5, 31, 32
jest równy 7, 31, 32
loa3.5, program, 53
Lotto
liczby wymierne, których kwadrat
kwoty przeznaczone na wygraną,
44
regulamin, 44
szansa trafienia szóstki, 11
wpływy, 45
Skorowidz
NWD, Patrz największy wspólny
dzielnik
O
objętość
120
odległość
półkuli, 58, 59
pudła, 115
zanurzonej części piłek, 58
obrazy, generowane przez komputer,
od niedostępnego przedmiotu o
nieznanych wymiarach, 26
od przedmiotu o znanych
wymiarach, 27
osoby, ustawienie w kolejce, 7, 8,
9, 10
otwarta koperta, rysowanie, 41
Ł
łamigłówki
karty, 69, 70, 71, 72, 74
narysowanie figury bez odrywania
ołówka, 41, 42
M
Mandelbrot, Benoit, 120
MIA III, program, 53
Moc jedności, gra, 102, 104
cel gry, 105
pionki, 103
plansza, 102
punkty mocy, 103
remis, 105
wersja dla trzech lub czterech
osób, 105
zwycięskie układy pionów, 105
modulo, arytmetyka, 109
N
n!, symbol, 10
największy wspólny dzielnik, 109,
110
neutralne, elementy, 121
Newtona, drugie prawo, 145
niedostępny przedmiot
wyznaczanie odległości, 26
wyznaczanie wysokości, 24, 25
P
permutacje, przystawanie, 92
Picka, wzór, 62, 63
dowód, 64, 65, 66, 67
pieluchy, pranie, 133, 134, 135, 136,
137, 138, 139, 141, 142
koszt, 135
model matematyczny, 134
program, 140, 141
wynik dwukrotnego płukania, 135
wynik jednokrotnego płukania,
135
wynik trzykrotnego płukania, 136
pierwsze, liczby, 108
definicja, 108
w postaci 6k+5, 31, 32
planarny, graf, 93
spójność, 93
spójny bez krawędzi, 95
spójny o czterech krawędziach, 96
spójny o dwóch krawędziach, 96
spójny o jednej krawędzi, 95
spójny o trzech krawędziach, 96
pole wielokątów, 62, 63
półkula, objętość, 58, 59
pranie pieluch, 133, 134, 135, 136,
137, 138, 139, 141, 142
koszt, 135
model matematyczny, 134
program, 140, 141
wynik dwukrotnego płukania, 135
167
widzów, 31, 33
Sale, A.H.J., 150
Shamir, 110
spadochroniarz
działające siły, 145
prędkość spadania, 144, 145,
146, 147
spigot, algorytm, 150
dla liczby e, 152, 153
dla liczby Eugeniusza, 161
program, 153
statystyczna, estymacja, 77
symetryczne, szyfry, 110
system mierzenia kątów, 27
szachownica, ułożenie kostek
domina, 31, 32, 33
szóstka w Lotto, szansa trafienia, 11
szyfrowanie
klucz jawny, 110
klucz tajny, 110
RSA, 110, 111, 112
szyfry symetryczne, 110
szyfry asymetryczne, 110
szyfry
asymetryczne, 110
RSA, 110, 111, 112
symetryczne, 110
Szyki, gra, 47, 48
bicie, 50
cel gry, 53
niespójne układy pionków, 49
programy, 53
remis, 50, 51
spójne układy pionków, 48, 49
zasady poruszania się pionków,
49, 50
kwoty przeznaczone na wygraną, 44
regulamin, 44
szansa trafienia szóstki, 11
wpływy, 45
tratwa z piłek, 57, 59
liczba potrzebnych piłek, 58, 60
masa elementów, 58
objętość zanurzonej części
piłek, 58
szkic, 57
twierdzenie Talesa, 22
tysięczne, jednostka, 27
tysięcznych, wzór, 27, 28
U
układ dynamiczny, 122
W
widzowie, rozmieszczenie
w kinie, 31, 33
wielokąty, pole, 62, 63
Winands, Mark, 53
wymierne liczby, których kwadrat
jest równy 7, 31, 32
wysokość
drzewa, 22, 23, 24
niedostępnego przedmiotu, 24, 25
wzory
na dzień tygodnia, 36, 37
objętość półkuli, 59
Picka, 62, 63, 64, 65, 66
tysięcznych, 27, 28
Z
zamknięta koperta, rysowanie, 41
zbiory Julii, 119, 123
zegar, kąt prosty tworzony przez
wskazówki, 18, 19, 20
wynik jednokrotnego płukania, 135
wynik trzykrotnego płukania, 136
S
sala kinowa, rozmieszczenie
prawo Archimedesa, 57
programowanie gier, 52
programy
algorytm spigot dla liczby e, 153,
154
algorytm spigot dla liczby
Eugeniusza, 161, 162
gra w Szyki, 53
karciana łamigłówka, 72, 73
pranie pieluch, 140, 141
sposoby wydawania reszty, 11, 12
przeciwny, element, 121
przedmiot
wyznaczanie odległości, 26, 27
wyznaczanie wysokości, 24, 25
przystawanie, 92
pudło, największa objętość, 114,
115, 116
punkty kratowe, 62, 63
R
relacja równoważności, 92
reszta, sposoby wydania, 11
program, 11, 12
Rivest, 110
rozkład hipergeometryczny, 76
równanie różniczkowe, 146
równoważności, relacja, 92
różniczkowe, równanie, 146
RSA, szyfr, 110
odszyfrowanie, 111, 112
szyfrowanie, 111
tworzenie klucza jawnego, 110, 111
tworzenie klucza tajnego, 110, 111
wykorzystanie, 112
ryby, oszacowanie liczby, 77
rysowanie
figury bez odrywania ołówka,
41, 42
otwartej koperty, 41
zamkniętej koperty, 41
168
T
Talesa, twierdzenie, 22
Totalizator Sportowy
22
148
Pobierz darmowy fragment (pdf)