Abstrakcyjna grupa jest zbiór elelementów z binarną operacją iloczynu, która jest asocjatywna a.(b.c) = (a.b) . c, ogólnie nieprzemienna (niekomutatywna), czyli a . b się nie równa b .a . Każdy element „a” ma w grupie odwrotność, „a” razy „odwrotność a” równa sie „identycznosc”. Iloczyn grupowy znaczymy kropką, albo w ogóle znak operacji opuszczamy, czyli piszemy „ab” zamiast „a.b”. Jeśli jednak operacja jest przemienna, zamiast zamiast kropki piszemy „+” (plus). Mamy wtedy a+b = b+a, elementy komutują, odwrotność „a” znaczymy „-a”, identyczność „zero”. Grupy przemienne się też nazywają „abelowskie”.
W naszym antionowym programowaniu termin „przestrzeń” ma znaczenie „abelowska grupa” plus „zbiór generatorów”. Więcej o dyskretnych grupach, generatorach, generujacych relacjach, diagramach Cayleya, itp. mozna przeczytać w dodatku. Dla grupowej operacji nie piszemy „plus”, ale daszek „^”. Operacja daszka się stosuje do punktów i generatorów. Jest to pobitowe dodawanie modulo 2. Używamy znaku „^”, bo tak jest w jezyku „C”. Znak „+” w programach „C” jest zarezerwowany dla zwykłego dodawania liczb.
Iloczyn przestrzeni
Najprostszą przestrzenią jest jeden punkt, oznaczenie C1 (zobacz rysuknek poniżej). Narysowaliśmy pętlę wokół samodzielnego punktu na przypadek, żebyśmy w programie mieli operację t(0) (chociaż zero to nie generator …). Drugą najprostszą przestrzenią są dwa punkty i dwie przeciwnie skierowane krawędzie. Jest to 2-cykl, piszemy C2 . Symbolem Cn oznaczamy n-cykl, który jest złożony z „n” punktów.
Każda abelowska przestrzeń jest bądź samodzielnym cyklem (n-cyklem), albo kartezjańskim iloczynem cykli. Zapożyczając terminologię z algebry liniowej (wektorowej), jeden n-cykl to jest jak jednowymiarowa przestrzeń wektorowa. Iloczyn dwu cykli ma dwa „wymiary”, piszemy Cn x Cn = (Cn )2 , gdzie „x” jest symbol kartezjańskiego iloczynu. Jest to zbiór par (a1 , a2) , gdzie ” ai ” jest liczba „modulo n”, czyli zbiór liczb ze zbioru {0,1,2, … n-1}. Ogólnie „n” może być jakakolwiek liczba naturalną, ale my w programach będziemy rozważać tylko potęgi dwójki, czyli n-cykle dla n= 1,2,4,8,16,… .
Hiperkostka (n-kostka) jest właściwie iloczynem kartezjańskim 2-cykli. Elementami hiperkostki jako grupy są „entki” (a1 , a2, ….) . Piszemy je prosciej w postaci sekwencji bitów 0,1 (to są liczby modulo 2) bez przecinków i nawiasów. Na przykład piszemy 01101 zamiast (0,1,1,0,1). Hiperkostkę rysujemy jako graf z nieskierowanymi krawędziami. Krawędź bez strzałki to dwie równoległe krawędzie przeciwnie skierowane. Czyli 2-cykl.
Wracając do ogólnego sformułowania, nasza przestrzeń jest cos takiego jak
Cn1 x Cn2 x Cn3 x … x Cnk
gdzie „ni” sa liczby modulo jakaś potęga dwójki. Jest pytanie, do czego nam będa słuzyć takie ogólne przestrzenie, jak bedziemy z nimi manipulować w programach i jak bedziemy programować ruchy antionów. Odpowiedzią na pierwsze pytanie jest przykład macierzy „n x n” i programowanie macierzowych algorytmów. Weźmy konkretnie macierz 8 x 8 . Jej elementy umiescimy do 64 punktów przestrzeni C8 x C8 . Samą przestrzeń C8 x C8 = (C8 )2 najpierw umiescimy do 6-kostki (C2 )6 w podobny sposób, jak umiesciliśmy cykl Hamiltona C8 do 3-kostki (C2 )3 , czyli przy pomocy kodu Graya. Ogólnie to sie nazywa zanurzenie (włożenie, embedding) jednej przetrzeni do drugiej. Łatwo to wizualizować dla pojedynczego cyklu, C8 –>(C2 )3 ,tak jak to widać na rysunku w poprzednim rozdziale. Gorzej z taką wizualizacją dla iloczynów cykli. W tym nam będą pomocne wcześniej wprowadzone pojęcia bazy i podbazy. Bazą dla naszej przestrzeni z macierza 8 x 8 będzie „111111”. Kolumnom macierzy przyporządkujemy podbazę „111000”, wierszom podbazę „000111”. Ruchy antionów w (C8 )2 = C8 x C8 bedziemy programować przy pomocy operacji t(gtrans(subbase)). Antion, który siedzi w „currentpoint” przesunie się wzdłuz odpowiedniej kolumny, jesli subbase = 54. Przesunie się wzdłuz odpowiedniego wiersza, jesli subbase = 7. Przypomnijmy, że operacja t(gtrans(subbase)) w programie wykonują wszystkie antiony, które są rozmnozone w (C2 )6 . Czyli wszystkie antiony sie równoczesnie przesuną wzdłuz kolumn, względnie wierszy.
Jesli abstrahować od sposobu jak jest przestrzeń (C8 )2 = C8 x C8 zanurzona do 6-kostki, to można taka przestrzeń narysować w następujacy sposób:
Po zakręceniu kolumn mozna zobaczyc kształt rury. Z kolei jesli połączymy końce rury, otrzymamy kształt torusa. Matematycy od teorii grup nazywaja nasze cykle (w tym wypadku nasze kolumny i wiersze) „orbitami”. Mówia, że grupa (C2 )6 działa na 64-elementowy zbiór. Poprawna nazwa jest więc „orbity”.
Poniżej jest przykład jak wyglada przestrzeń C4 x C2 , jesli ja narysować razem z (C2 )3 , do której jest ta C4 x C2 zanurzona. Wybralismy podbazy 101 i 010. Ten wybór się przejawi podczas operacji t(gtrans(subbase)). Można to sprawdzić jako ćwiczenie. Napiszcie program z poczatkową ekspansją tx(1); tx(2); tx(4); potem weźcie A= currentpoint, dalej próbny ruch t(gtrans(5)). Po wydruku cout << ” currentpoint ” << currentpoint << ” A ” << A << ” \n ” zobaczycie, jak się przesunęła zmienna A w stosunku do „currentpoint”.
Na rysunku widzimy dwie orbity 0-1-5-4 i 2-3-7-6, po których sie przesuwa zmienna antionowa A w wyniku ruchu t(gtrans(5)) w podbazie „101”.
Transpozycja macierzy
Pokażemy program, który transponuje macierz 4 x 4 zanurzoną w 4-kostce. Rysunek przestrzeni C4 x C4 jest troche prostszy niz (C8 )2. Mozecie go sobie narysować sami. Możecie nawet spróbować narysować 4-kostkę (C2 )4 i włozyc do niej (C8 )2 , najlepiej innym kolorem. Transpozycja jest obrót wokół głównej przekatnej. Wybierzemy próbne wartości elementów macierzy takie, zeby po wykonaniu programu transpozycji było jasno widać, że rzeczywiście macierz się obróciła dookoła przekatnej. Wybralismy wartości 1,2,1,0, ktore damy do zmiennej „a” wzdłuż kazdego z czterech wierszy charakteryzowanych podbazą 0011. Tę sprawe nam łatwo załatwi program dla współczynników dwumianowych z poprzedniego rozdziału. W drugiej części programu jest podstawienie A= a i wykonamy program transpozycji. Wydruk wartosci antionowej zmiennej „A” nam da próbną sekwencję 1,2,1,0 wzdłuz czterech kolumn. I to będzie dowód, że się naprawde wykonała transpozycja.
Komentarz do programu. Zaraz po expansji tx(1); tx(2); tx(4); tx(8) dajemy do pierwszej kolumny a=1, do reszty a=0. Dalej jest cykl „for” dla inicjalizacji macierzy. Jeśli odkomentować pierwszy wydruk, otrzymamy
currentpoint 3 a = 1
currentpoint 11 a = 1
currentpoint 7 a = 1
currentpoint 15 a = 1
currentpoint 1 a = 2
currentpoint 9 a = 2
currentpoint 5 a = 2
currentpoint 13 a = 2
currentpoint 2 a = 0
currentpoint 10 a = 0
currentpoint 6 a = 0
currentpoint 14 a = 0
currentpoint 0 a = 1
currentpoint 8 a = 1
currentpoint 4 a = 1
currentpoint 12 a = 1
W wierszach macierzy są współczynniki dwumianu (1+x)2 , czyli „1,2,1,0”. Następuje cykl „whiele” i właściwa faza transpozycji. Wynik jest nastepujący
currentpoint 12 A = 1
currentpoint 14 A = 1
currentpoint 13 A = 1
currentpoint 15 A = 1
currentpoint 4 A = 2
currentpoint 6 A = 2
currentpoint 5 A = 2
currentpoint 7 A = 2
currentpoint 8 A = 0
currentpoint 10 A = 0
currentpoint 9 A = 0
currentpoint 11 A = 0
currentpoint 0 A = 1
currentpoint 2 A = 1
currentpoint 1 A = 1
currentpoint 3 A = 1
Wartości „1,2,1,0” się pojawiły w kolumnach macierzy. Trik algorytmu transpozycji polega na n/2 – krotnym (w danym przypadku 2-krotnym) użyciu pary instrukcji
które robią elementarne transpozycje w orbitach C2 x C2 . Więcej o tym mozna znaleźć w rozdziale „Obroty hiperkostki”. Funkcje fgoss(subbase) i ngoss(gen,subbase) są zadefiniowane w „bope”. Funkcja fgoss() wraca pierwszy generator podbazy. Funkcja ngoss() wraca następny generator podbazy po danym generatorze. Posuwamy się w podbazie z prawej strony w lewo. Cykl „while” sie kończy, kiedy sie skończy podbaza.