sa chaos, Łamigłówki, obrazki logiczne
[ Pobierz całość w formacie PDF ]
Struktury algebraiczne
ALGEBRA 1
IZ/INF/PPI
Przykłady zastosowa
Teresa Jurlewicz, stycze
2006
Cykliczny chaos
ZADANIE*
PODSTAWA TEORETYCZNA CYKLICZNEGO CHAOSU.
Niech
M
2
(
Z
k
)
b
dzie pier
cieniem
2
Z
k
a)
Uzasadni
,
e macierz jest odwracalna w pier
cieniu
A
M
2
(
Z
k
)
jest odwracalny w pier
cienu (a wi
c, gdy liczby
wtedy i tylko wtedy, gdy element
det
A
Z
k
det
A
oraz s
wzgl
dnie pierwsze.
k
A
-1
M
2
(
Z
k
)
c)
Uzasadni
,
e dla ka
dej macierzy odwracalnej z pier
cienia zachodzi równo
w pier
cieniu
.
A
Z
k
A
L
=
I
dla pewnej liczby naturalnej . Kolejne pot
gi
L
A
,
A
2
, ...,
A
L
-1
,
I
macierzy tworz
wówczas
A
k
d)
Wykaza
,
e własno
z punktu
c)
maj
jedynie macierze odwracalne w rozwa
anym pier
cieniu.
e)
Uzasadni
,
e własno
ci
a)
-
d)
zachodz
tak
e w pier
cieniach
wzgl
dem mno
enia modulo grup
cykliczn
.
M
n
(
Z
k
)
dla dowolnych warto
ci
n
> 2
.
OPIS CYKLICZNEGO CHAOSU
Kwadratowa plansza
Plansz
wymiaru
nazywamy kwadratow
pokratkowan
tablic
zawieraj
c
pól uło
onych w
n n
2
n
wierszach (poziomych rz
dach) i kolumnach (pionowych rz
dach). Wiersze i kolumny planszy numeru-
n
jemy liczbami od do
0
n
- 1
. Poło
enie pola znajduj
cego si
w wierszu o numerze oraz w kolumnie
i
o numerze opisujemy par
liczb
j
(
i
,
j
)
, któr
nazywamy
współrz
dnymi
tego pola.
Na planszy rozmieszczamy pewne elementy (mog
to by
cyfry, litery lub inne znaki, kolory, fragmenty
obrazów, puzzle, figury, ...). Niektóre pola planszy mog
pozosta
puste. Plansza zawieraj
ca liczby jest po
prostu macierz
(wiersze i kolumny macierzy numeruje s
zwykle od ). Wa
nym przykładem planszy jest
1
popularny w
ród informatyków format obrazu, tzw. bitmapa.
i \ j 0 1 2 3 4
Plansza wymiaru
5
. Jej elementy s
literami alfabetu.
Wszystkie pola planszy s
zapełnione.
0
A B C D E
1
F G H I J
2
K L M N O
3
P Q R S T
4
U V W X Y
i \ j 0 1 2 3 4
Plansza wymiaru
5
. Jej elementy s
kolorami. Czarny
element planszy ma współrz
dne
( 1, 3 )
, za
szary
współrz
dne
( 4, 2 )
. Pozostałe pola planszy nie s
zapełnione.
0
1
2
3
4
macierzy stopnia , których elementy nale
do pier
cienia .
b)
Poda
wzór na
Układy czarno-białych lub kolorowych elementów tworz
na planszy pewne obrazy. Czasem s
to zupełnie sensowne
rysunki.
Plansza wymiaru
20
. Jej kolorowe elementy utworzyły
obrazek delfina z piłk
. Tego typu obrazki wyst
puj
w
popularnej łamigłówce o nazwie
obrazki logiczne
,
nanogramy
lub nazwie japo
skiej
tsunami
.
Chaos na kwadratowej planszy
Niech b
dzie wymiarem planszy oraz niech
A
=
Ç
È
a b
c d
×
Ø
b
dzie macierz
o elementach
0, 1, 2, ...,
n
- 1
. Zakładamy,
e macierz jest odwracalna modulo ,
A
n
czyli jej wyznacznik
det
A
=
ad
-
bc
jest liczb
wzgl
dnie pierwsz
z .
n
Chaosem z macierz
na planszy wymiaru
nazywamy takie przemieszczenie elementów planszy, w
A
n
którym element z pola o współrz
dnych
(
i
,
j
)
przechodzi na pole o współrz
dnych
(
i
,
j
)
, przy czym
È
i
Ø
=
Ä
Å
Ç
È
a b
Ø
×
Ç
È
i
Ø
Ô
Õ
mod n
.
j
c d
j
A
macierzy opisane przekształcenie jest ró
nowarto
ciowe. To oznacza,
e elementy z dwóch ró
nych pól
A
przejd
na dwa ró
ne pola. Oczywi
cie liczba zaj
tych pól nie zmieni si
, podobnie jak liczby elementów
tego samego typu (jednakowych kolorów, jednakowych znaków, itp.).
Iteracje, cykle i orbity chaosu
Po wykonaniu jednej iteracji chaosu na planszy pojawi si
nowy układ elementów, przy kolejnej iteracji
znowu inny, itd. Elementy b
d
si
stale miesza
tworz
c coraz to nowe układy. Ci
g kolejnych iteracji
chaosu uzyskamy bior
c kolejne pot
gi modulo macierzy chaosu, czyli macierze
n A
,
A
2
,
A
3
, ...
W pewnym jednak momencie
układ wróci do stanu pocz
tkowego
. Zdarzy si
to wtedy, gdy macierz
.
L
b
dzie równa modulo macierzy jednostkowej. Opisany chaos jest bowiem procesem
cyklicznym!!!
A
L
n
Poszczególne elementy planszy poruszaj
si
w tym procesie równie
w sposób cykliczny, po orbitach
ró
nych długo
ci b
d
cych dzielnikami długo
ci całego cyklu. Ze wzgl
du na przedstawion
cykliczno
L
procesu b
dziemy go nazywa
chaosem cyklicznym
.
Aplikacje komputerowe
Zagadnienie cyklicznego chaosu stało si
podstaw
kilku programów komputerowych napisanych w roku
2004 przez studentów Wydziału Informatyki i Zarz
dzania PWr.
Zostały one zaprezentowane w ramach VII
edycji Dolno
l
skigo Festiwalu Nauki. Mo
na je znale
na stronie
www.im pwr.wroc.pl/~tjurlew/sa.htm
Poni
ej podajemy dwie festiwalowe zagadki zwi
zane z tym tematem.
Ich rozwi
zania znajduj
si
na
stronie
www.im pwr.wroc.pl/~tjurlew/DFN2004.htm
n
×
×
×
Ç
Uwaga.
Macierz b
dziemy nazywa
macierz
chaosu
lub
macierz
mieszaj
c
. Dzi
ki odwracalno
ci
ZADANIE*
Zagadki z DFN 2004. Niech
A
=
Ç
1 1
1 2
×
Ø
b
dzie macierz
chaosu.
a)
UKRYTY OBRAZEK. Zmieni
układ
czarnych i białych pól znajduj
cych si
na
planszy obok wykonuj
c jedn
iteracj
chaosu
z macierz
mieszaj
c
A
. Czarne pola utworz
wówczas obrazek. Rozwi
zanie zagadki polega
na podaniu słownego opisu tego obrazka.
b)
UKRYTY OBRAZEK GIGANT.
Zmieni
układ czarnych i białych pól znajduj
cych si
na planszy
poni
ej wykonuj
c seri
iteracji chaosu z macierz
mieszaj
c
a
do momentu, gdy czarne pola
È
A
utworz
pewien obrazek. Rozwi
zanie zagadki polega na podaniu słownego opisu tego obrazka.
[ Pobierz całość w formacie PDF ]