ALGEBRA 1
IZ/INF/PPI
Struktury algebraiczne
Teresa Jurlewicz, styczeń 2006
Przykłady zastosowań
Cykliczny chaos
ZADANIE*
PODSTAWA TEORETYCZNA CYKLICZNEGO CHAOSU. Niech M2(Zk) będzie pierścieniem
macierzy stopnia 2, których elementy należą do pierścienia Zk .
a) Uzasadnić, że macierz A jest odwracalna w pierścieniu M2(Zk) wtedy i tylko wtedy, gdy element
det A jest odwracalny w pierścienu Zk (a więc, gdy liczby det A oraz k są względnie pierwsze.
b) Podać wzór na A-1 w pierścieniu M2(Zk).
c) Uzasadnić, że dla każdej macierzy odwracalnej A z pierścienia Zk zachodzi równość
AL = I
dla pewnej liczby naturalnej L. Kolejne potęgi A, A2, ..., AL-1, I macierzy A tworzą wówczas
względem mnożenia modulo k grupę cykliczną.
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 Mn(Zk) dla dowolnych wartości
n > 2.
OPIS CYKLICZNEGO CHAOSU
Kwadratowa plansza
Planszą wymiaru n nazywamy kwadratową pokratkowaną tablicę zawierającą n2 pól ułożonych w n
wierszach (poziomych rzędach) i n kolumnach (pionowych rzędach). Wiersze i kolumny planszy numeru-
jemy liczbami od 0 do n - 1. Położenie pola znajdującego się w wierszu o numerze i oraz w kolumnie
o numerze j opisujemy parą liczb ( 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 1). Ważnym przykładem planszy jest
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
0 element planszy ma współrzędne ( 1, 3 ), zaś szary
współrzędne ( 4, 2 ). Pozostałe pola planszy nie są
1
zapełnione.
2
3
4
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 n będzie wymiarem planszy oraz niech
îÅ‚ Å‚Å‚
a b
A =
ïÅ‚ śł
c d
ðÅ‚ ûÅ‚
będzie macierzą o elementach 0, 1, 2, ..., n - 1. Zakładamy, że macierz A jest odwracalna modulo n,
czyli jej wyznacznik det A = ad - bc jest liczbą względnie pierwszą z n.
Chaosem z macierzą A na planszy wymiaru n nazywamy takie przemieszczenie elementów planszy, w
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
= Å" .
ïÅ‚ śł ìÅ‚ ïÅ‚ śł ïÅ‚ śł ÷Å‚
j íÅ‚ c d j Å‚Å‚
ðÅ‚ ûÅ‚ ðÅ‚ ûÅ‚ ðÅ‚ ûÅ‚
mod n
Uwaga. Macierz A będziemy nazywać macierzą chaosu lub macierzą mieszającą. Dzięki odwracalności
macierzy A opisane przekształcenie jest różnowartościowe. To oznacza, że elementy z dwóch różnych pól
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 n macierzy chaosu, czyli macierze A, A2, A3, ... .
W pewnym jednak momencie L układ wróci do stanu początkowego . Zdarzy się to wtedy, gdy macierz
AL będzie równa modulo n macierzy jednostkowej. Opisany chaos jest bowiem procesem cyklicznym!!!
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 L całego cyklu. Ze względu na przedstawioną cykliczność
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 znalez
ć 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
ZADANIE*
îÅ‚ Å‚Å‚
1 1
Zagadki z DFN 2004. Niech A =
ïÅ‚ śł bÄ™dzie macierzÄ… chaosu.
1 2
ðÅ‚ ûÅ‚
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 aż do momentu, gdy czarne pola
utworzą pewien obrazek. Rozwiązanie zagadki polega na podaniu słownego opisu tego obrazka.