magisterij.tex

%*****************************************************************
%   Vzorec za pisanje diplomskega dela,
%   ki vsebuje navodila za izdelavo diplomskega dela
%
%   UNIVERZA V LJUBLJANI
%   Fakulteta za računalništvo in informatiko
%
%   Pripravila: Peter.Peer@fri.uni-lj.si
%               Franc.Solina@fri.uni-lj.si
%*****************************************************************

\documentclass[12pt,a4paper,openany,twoside]{book}

%Uporabljeni paketi
\RequirePackage{pdf14}
\usepackage{cmap}
\usepackage[utf8]{inputenc}
\usepackage{type1ec}
\usepackage[T1]{fontenc}
\usepackage{graphicx,epsfig}
\usepackage[slovene]{babel}
\usepackage{cite}
\usepackage{enumitem}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{listings}
%\usepackage{url}
\usepackage[pdftex,colorlinks,citecolor=black,filecolor=black,linkcolor=black,urlcolor=black]{hyperref}
\usepackage[top=2cm, bottom=3cm, inner=3cm, outer=2cm]{geometry}
\usepackage{fancyvrb}
\usepackage{incgraph}
\usepackage[a-1b]{pdfx}
%\usepackage[backend=bibtex]{biblatex}

%\addbibresource{magisterij.bib}

%Nastavitev glave in repa strani
\pagestyle{myheadings}

% stil odstavkov
\setlength{\parindent}{0cm}
\setlength{\parskip}{5mm plus2mm minus2mm}

%\input{cc}

%********************************************
% kratice, simboli
\newcommand{\abbrlabel}[1]{\makebox[3cm][l]{\textbf{#1}\ \dotfill}}
\newenvironment{abbreviations}{\begin{list}{}{\renewcommand{\makelabel}{\abbrlabel}}}{\end{list}}
%********************************************

\begin{document}

%********************************************
% platnica
\thispagestyle{empty} 
\begin{center}
             {\large UNIVERZA V LJUBLJANI\\
                     FAKULTETA ZA RAČUNALNIŠTVO IN INFORMATIKO\\}
\vspace{3cm} {\large Iztok Jeras}\\
\vspace{2cm} {\large \textbf{Predslike 2D celičnih avtomatov}}\\
\vspace{2cm} {MAGISTRSKO DELO\\ NA UNIVERZITETNEM ŠTUDIJU}\\
\vfill       {\Large Ljubljana, 2016}
\end{center}
\newpage
\ \thispagestyle{empty}
\newpage
%********************************************

%********************************************
% stran 1 med uvodnimi listi
\thispagestyle{empty} 
\begin{center}
             {\large UNIVERZA V LJUBLJANI\\
                     FAKULTETA ZA RAČUNALNIŠTVO IN INFORMATIKO\\}
\vspace{3cm} {\large Iztok Jeras}\\
\vspace{2cm} {\large \textbf{Predslike 2D celičnih avtomatov}}\\
\vspace{2cm} {MAGISTRSKO DELO\\ NA UNIVERZITETNEM ŠTUDIJU}\\
\vspace{2cm} {\Large Mentor: prof. dr. Branko Šter}
\vfill       {\Large Ljubljana, 2016}
\end{center}
\newpage
\ \thispagestyle{empty}
\newpage
%********************************************

%********************************************
% stran 2 med uvodnimi listi
\thispagestyle{empty}

\vspace*{5cm}
{\small \noindent
To magistrsko delo je ponujeno pod licenco \textit{Creative Commons Attribution-ShareAlike 4.0 International}
\footnote{http://creativecommons.org/licenses/by-sa/4.0/} ali v slovenščini \textit{priznanje avtorstva in deljenje pod enakimi pogoji 4.0 mednarodna}
\footnote{http://www.ipi.si/sl/creative-commons-cc/o-uporabi-licence}. Po želji se lahko uporabnik poslužuje novejše različice.
To pomeni, da se tako besedilo, slike, grafi in druge sestavine dela kot tudi rezultati magistrskega dela lahko prosto distribuirajo,
reproducirajo, uporabljajo, dajejo v najem, priobčujejo javnosti in predelujejo, pod pogojem, da se jasno in vidno navede avtorja in naslov tega
dela in da se v primeru spremembe, preoblikovanja ali uporabe tega dela v svojem delu, lahko distribuira predelava le pod
licenco, ki je enaka tej.
Uporabljena je mednarodna licenca, čeprav obstaja verzija prilagojena za slovenski pravni red, to pa zato, ker slovenska verzija ni vzdrževana.
Podrobnosti licence so dostopne na spletni strani \url{http://creativecommons.org}
ali na Inštitutu za intelektualno lastnino, Streliška 1, 1000 Ljubljana.
\begin{center}
\includegraphics[width=5cm]{by-sa.png}
\end{center}
}

\vspace*{1.5cm}
{\small \noindent
Izvorna koda programske opreme, razvite za potrebe magistrskega dela, je ponujena pod licenco \textit{Unlicense} \footnote{http://unlicense.org/}.
To pomeni, da se lahko prosto uporablja, distribuira in/ali predeluje, brez kakšnih koli obveznosti.
Avtor se odpoveduje vsem pravicam in tako omogoča uporabnikom izvorne kode, da se izognejo preverjanju pravnih obveznosti.
}

\begin{center} 
\ \\ \vfill
{\em Besedilo je oblikovano z urejevalnikom besedil \LaTeX.\\
Slike in grafi so narisani s pomočjo programa za vektorske ilustracije Inkscape \footnote{https://inkscape.org}.}
\end{center}

\newpage
\ \thispagestyle{empty}
\newpage
%********************************************

% stran 3 med uvodnimi listi
\incgraph[documentpaper][width=\paperwidth,height=\paperheight]{original_izdane_teme_magistrskega_dela.jpg}
%\includepdf{original_izdane_teme_magistrskega_dela.pdf}
%\thispagestyle{empty}
%Namesto te strani {\bf vstavite} original izdane teme magistrskega dela s podpisom mentorja in dekana ter žigom fakultete, ki ga magistrant
%dvigne v študent\-skem referatu,  preden odda izdelek v vezavo!
%\newpage

%********************************************
% stran 4 med uvodnimi listi je prazna 
\ \thispagestyle{empty}
\newpage

%********************************************
% stran 5 med uvodnimi listi

\thispagestyle{empty}

\vspace*{2cm}
\begin{center}
{\Large \textbf{IZJAVA O AVTORSTVU \\ \vspace{0.5cm} magistrskega dela}}
\end{center}
\vspace{1cm}

Spodaj podpisani \textbf{Iztok Jeras},
z vpisno številko \textbf{63030393},
sem avtor magistrskega dela z naslovom:

\vspace{1cm}
\hspace{1cm}\textbf{Predslike 2D celičnih avtomatov}
\vspace{1cm}

S svojim podpisom zagotavljam, da:
\begin{itemize}
\item sem magistrsko delo izdelal samostojno pod vodstvom mentorja \textbf{prof. dr. Branka Štera},
\item so elektronska oblika magistrskega dela, naslova (slov., angl.), povzetka (slov., angl.) ter ključne besede (slov., angl.) identični s tiskano obliko magistrskega dela
\item in soglašam z javno objavo elektronske oblike magistrskega dela v zbirki »Dela FRI«.
\end{itemize}

\vspace{3cm}
V Ljubljani, dne 30. avgust 2016 \hfill Podpis avtorja:
\newpage 

%********************************************
% stran 6 med uvodnimi listi je prazna pri dvostranskem tiskanju
\ \thispagestyle{empty}
\newpage

%********************************************
% stran 7 med uvodnimi listi

\chapter*{Zahvala}
\thispagestyle{empty}
Zahvaljujem se prof. dr. Andreju Dobnikarju za pomoč pri pisanju člankov
o algoritmih za štetje in izpis predslik pri enodimenzionalnih celičnih avtomatih.
\newpage

%********************************************
% stran 8 med uvodnimi listi je prazna pri dvostranskem tiskanju
\ \thispagestyle{empty}
\newpage

%********************************************

\renewcommand\thepage{} 
\tableofcontents 
\renewcommand\thepage{\arabic{page}}

\thispagestyle{empty}

%********************************************

\chapter*{Seznam uporabljenih kratic in simbolov}

\thispagestyle{empty}

% simboli

\begin{abbreviations}
\item[1D] enodimenzionalen
\item[2D] dvodimenzionalen
\item[3D] tridimenzionalen
\item[CA] celični avtomati (angl. cellular automata)
\item[GoL] Conwayeva igra življenja (angl. Conway's Game of Life)
\item[GoE] rajski vrt (angl. Garden of Eden)
\item[trid] okolica CA, sestavljena iz treh celic na heksagonalni mreži
\item[quad] okolica CA, sestavljena iz štirih celic na kvadratni mreži
\item[DFS] iskanje v globino (angl. depth first search)
\item[SAT] problem izpolnjivosti (angl. boolean satisfiability problem)
\vspace{10mm}
\item[\(C\)] poljubna konstanta
\item[\(S\)] nabor stanj celice
\item[\(|S|\)] število možnih stanj celice
\item[\(c\)] stanje posamezne celice (celoštevilska vrednost)
\item[\(c(x,y)\)] stanje celice na koordinatah \((x,y)\) znotraj 2D polja celic
\item[\(c^t\)] stanje celice v sedanjosti
\item[\(c^{t+1}\)] stanje celice v prihodnosti (en korak)
\item[\(N_x\)] velikost pravokotnega 2D polja celic v dimenziji X
\item[\(N_y\)] velikost pravokotnega 2D polja celic v dimenziji Y
\item[\(N\)] število celic v 1D ali 2D polju
\item[\(M_x\)] velikost pravokotne 2D okolice celice v dimenziji X
\item[\(M_y\)] velikost pravokotne 2D okolice celice v dimenziji Y
\item[\(M\)] število celic v 1D ali 2D okolici
\item[\(n\)] stanje okolice posamezne celice (celoštevilska vrednost)
\item[\(n(x,y)\)] stanje okolice celice na koordinatah \((x,y)\) znotraj 2D polja celic
\item[\(n^{t-1}\)] stanje okolice celice v preteklosti (en korak)
\item[\(n^t\)] stanje okolice celice v sedanjosti
\item[\(f\)] tranzicijska funkcija, ki definira časovno evolucijo avtomata
\item[\(f^{-1}\)] obratna tranzicijska funkcija
\item[\(o_{\leftrightarrow}\)] prekrivanje okolic v dimenziji X
\item[\(o_{\updownarrow}\)] prekrivanje okolic v dimenziji Y
\item[\(o_{\times}\)] prekrivanje okolic v diagonalni smeri
\end{abbreviations}

%\cleardoublepage

\clearpage{\pagestyle{empty}\cleardoublepage}

%********************************************
%zacno se glavni listi, ki so numerirani z arabskimi stevilkami

\setcounter{page}{1}
\pagenumbering{arabic}

\chapter*{Povzetek}

\addcontentsline{toc}{chapter}{Povzetek}

Medtem ko je računanje predslik 1D celičnih avtomatov dobro raziskan in
podrobno dokumentiran problem, je to področje pri 2D celičnih avtomatih manj raziskano.
Za 1D problem poznamo algoritme za štetje in izpis predslik s
procesno zahtevnostjo linearno odvisno od velikosti problema.
Možno je tudi določiti, ali je 1D celični avtomat reverzibilen in
kakšen je regularen jezik vseh stanj brez predslik.
Pri 2D problemu sicer poznamo nekaj algoritmov za iskanje predslik,
vendar so slabo teoretično raziskani.
Vemo tudi, da je problem reverzibilnosti 2D celičnih avtomatov na splošno neodločljiv.

Mreža predslik, ki sem jo v preteklosti razvil za potrebe analize predslik 1D celičnih avtomatov,
se je izkazala za praktično orodje pri razlagi algoritmov in pri dokazovanju njihove pravilnosti.
Tukaj opišem kako se mrežo predslik tvori za 2D celične avtomate.
Če je bila ta mreža za 1D problem navaden graf, je za 2D problem razširjena v tretjo dimenzijo.
Predslike so namesto poti v grafu ploskve na mreži.
Robni pogoj se spremeni iz uteži za vozlišča, ki zaključujejo pot v 1D problemu,
v uteži za sklenjeno pot okoli ploskve predslike v 2D problemu.

Pri razvoju algoritma se je izkazalo, da štetja predslik 2D celičnega avtomata
ni mogoče izvesti v linearni odvisnosti od velikosti problema.
Zahtevnost podanega algoritma narašča eksponentno z velikostjo problema v eni dimenziji.
Podani algoritem se ne razlikuje dosti od obstoječih.
Celični avtomat razdeli na vrstice in išče predslike za posamezno vrstico od prve do zadnje.
Vrstične rezultate nato združi v rešitev za celoten 2D problem.
Podobno kot pri algoritmu za 1D probleme je analiza razdeljena v dva prehoda.
V prvem prehodu po vrsticah algoritem prešteje predslike,
v drugem opcijskem prehodu pa predslike izpiše.
Drugi prehod poteka v obratni smeri kakor prvi prehod.
Tudi procesiranje posamezne vrstice poteka iz drugega zornega kota.

Glavni napredek algoritma vidim v uporabi učinkovitih rešitev za 1D problem pri analizi vrstic ter
v uporabi progresivnega kodiranja vmesnih rezultatov, kar lahko zmanjša porabo pomnilnika.

\vspace{1.3cm}
\noindent
{\large \bf Ključne besede:}

\vspace{0.5cm}
\noindent
celični avtomati, predslike, predhodniki, računska zahtevnost, reverzibilnost, rajski vrt, Conwayeva igra življenja, trid, quad
\newpage

% prazna stran
\ \thispagestyle{empty}
\newpage

\chapter*{Abstract}

\addcontentsline{toc}{chapter}{Abstract}

While computing preimages of 1D cellular automata is a well researched and documented problem,
for 2D cellular automata there is less research available.
For the 1D problem we know algorithms for counting and listing preimages
where computational complexity is a linear function of the size of the problem.
It is possible to determine whether a 1D cellular automaton is reversible,
and what is the Garden of Eden sequence regular language.
For the 2D problem we know a few algorithms,
but they are poorly theoretically researched.
We also know that the reversibility problem is
in general undecidable for 2D cellular automata.

The preimage network, first developed for 1D cellular automata,
was proved to be a useful tool for explaining algorithms and for constructing proofs.
Here I explain how to construct the preimage network for 2D cellular automata.
While for the 1D problem this network is a normal graph,
for 2D it was extended into the third dimension.
Preimages are transformed from paths in the graph in 1D into surfaces on the network in 2D.
Edge conditions are transformed from weights for vertices ending a path in the 1D problem
into weights for the closed path around a preimage surface in the 2D problem.

While developing the algorithm, it proved impossible
to count preimages of 2D cellular automata
with processing requirements growing linearly with problem size.
Instead, processing requirements grow exponentially
with the size in one of the dimensions.
The described algorithm does not differ much from the existing ones.
The cellular automaton is split into rows,
the preimage list is first determined for each row from the first to the last.
The row results are then combined into the result for the whole 2D problem.
In a similar fashion to the 1D approach,
the algorithm splits into two passes.
In the first pass preimages are counted,
in the second optional pass preimages are listed.
The second pass is performed in the opposite direction,
while rows are also observed from the opposite side.

I see the main advantage of the described algorithm
in using existing solutions for row processing.
Solutions proved to be effective in solving the 1D problem.
Using progressive encoding of intermediate solutions
also enables reducing memory consumption.

\vspace{1.3cm}
\noindent
{\large \bf Key words:}

\vspace{0.5cm}
\noindent
cellular automata, preimages, predecessors, ataviser, computational complexity, reversibility, Garden of Eden, Conway's Game of Life, trid, quad
\newpage

% prazna stran
\ \thispagestyle{empty}
\newpage

%********************************************

\chapter{Uvod}

\section{Motivacija}

\subsection{Celični avtomati kot model vesolja}

Ker lahko vsak univerzalen sistem modelira vsak drug univerzalen sistem, lahko predpostavimo,
da lahko z univerzalnimi \emph{celičnimi avtomati} (angl. \emph{cellular automata, CA}) modeliramo vesolje. Samo modeliranje vesolja
je še izven našega dosega, poizkuša pa se vsaj približati teorijo CA teoretični fiziki.
S strani informacijske teorije in termodinamike je predvsem zanimiv model gravitacije
kakor entropijske sile (angl. Entropic gravity) \cite{Verlinde2010}, ki predpostavlja, da je
3D vesolje projekcija procesov, ki se odvijajo na 2D ploskvi. Z druge strani pa CA tudi omogočajo
opazovanje abstraktnega kopiranja informacij (replikacija) in evolucije \cite{Salzberg2004}.
Oba sta pomembna informacijska pojava v našem vesolju.

\subsection{Informacijska dinamika}

Informacijsko dinamiko CA se najpogosteje opisuje samo kakor reverzibilno ali ireverzibilno.
Obstaja tudi nekaj člankov, ki opazujejo entropijo sistema.
Pri reverzibilnem avtomatu se vsa informacija ohranja. Vsako stanje ima natanko eno prihodnost in eno preteklost.
Za reverzibilen celični avtomat lahko tudi definiramo pravilo oziroma funkcijo,
s katero preprosto procesiramo avtomat v preteklost namesto v prihodnost.
Za reverzibilne CA je torej računanje predslik (preteklosti)
trivialno in ne potrebuje tukaj opisanega algoritma.
Za ireverzibilne CA tako reverzno pravilo ne obstaja.
Trenutno stanje ima lahko nobeno, eno, ali več predslik.
Opisani algoritem je namenjen štetju in izpisu predslik za dano sedanje stanje CA.
Za take avtomate pravimo, da s časom izgubljajo informacijo,
ker ne moremo enolično določiti preteklega stanja.

Pogosto je tudi opazovanje dinamike delcev pri \emph{Igri življenja} (angl. \emph{Game of Life, GoL}) \cite{WikiGoL} (slika \ref{gospers_glider_gun})
in elementarnem pravilu 110 \cite{WikiRule110} (slika \ref{ca110-interaction2}).
Pištole, trki delcev in podobni konstrukti obstajajo tako v GoL kakor pri elementarnem pravilu 110
in na splošno pri vsakem univerzalnem celičnem avtomatu.
Pištole (slika \ref{gospers_glider_gun}) oddajajo delce, izvor in oddani delci skupaj rastejo v neskončnost.
S tem se informacija, potrebna za opis sistema, povečuje.
Slika \ref{ca110-interaction2} prikazuje dve različni interakciji med dvema delcema.
V levem primeru se delca srečata, si nekaj časa delita skupen prostor in nato nadaljujejta pot vsak zase.
V desnem primeru se delca srečata in po trku nastane nov delec.
Veliko poklicnih in amaterskih raziskovalcev proučuje delce v GoL in njihovo dinamiko.
S pomočjo osnovnih gradnikov je mogoče skonstruirati kompleksnejše sisteme, med katerimi so
najzanimivejši Turingov stroj \cite{Rendell2001} in univerzalni konstruktor \cite{Greene2013}.

\vspace{5mm}
\begin{figure}[htb]
\centerline{\includegraphics[width=8cm]{gospers_glider_gun}}
\caption[Gosperjeva pištola.]
{Gosperjeva pištola z nekaj izstreljenimi drsalci.}
\label{gospers_glider_gun}
\end{figure}

\vspace{5mm}
\begin{figure}[htb]
\centerline{\includegraphics[width=13.9cm]{ca110-interaction2}}
\caption[Trk delcev v pravilu 110.]
{Trk para delcev v pravilu 110. Razlika v začetnem stanju med slikama je v razdalji (fazi) med delcema.}
\label{ca110-interaction2}
\end{figure}

\vspace{5mm}
Celične Avtomate sta si zamislila matematika John von Neumann in Stanislaw Ulam,
da bi lahko oblikovala teorijo univerzalnega konstruktorja \cite{WikiVonNeumannUniversalConstructor},
ki je sposoben iz zapisa na traku narediti kopijo samega sebe.
Christopher Langton je vzel del univerzalnega konstruktorja in ga poenostavil v preprosto zanko \cite{WikiLangtonLoops},
ki kopira samo sebe na podlagi informacije zapisane v notranjosti telesa (slika \ref{langtons_loop}).

\vspace{5mm}
\begin{figure}[htb]
\centering
\begin{BVerbatim}
  2 2 2 2 2 2 2 2 
2 1 7 0 1 4 0 1 4 2
2 0 2 2 2 2 2 2 0 2
2 7 2         2 1 2
2 1 2         2 1 2
2 0 2         2 1 2
2 7 2         2 1 2
2 1 2 2 2 2 2 2 1 2 2 2 2 2
2 0 7 1 0 7 1 0 7 1 1 1 1 1
  2 2 2 2 2 2 2 2 2 2 2 2 2
\end{BVerbatim}
\caption[Langtonova zanka.]
{Langtonova zanka. Številke so stanja posamezne celice. Spodaj desno iz zanke raste nova zanka.}
\label{langtons_loop}
\end{figure}
\vspace{5mm}

Zgoraj našteti primeri nekako opisujejo informacijsko dinamiko v CA.
Ne obstaja pa še splošna teorija dinamike informacij v CA,
ki bi dinamiko opisala kvantitativno in prostorsko.
V svojem članku \cite{JerasDobnikar2007} in prispevkih na konferencah \cite{DBLP:conf/iccS/JerasD06, DBLP:conf/automata/Jeras08, Jeras2008-pyca}
sem grafično upodobil predslike trenutnega stanja za 1D problem.
Iz upodobitve (slika \ref{network_rule110_quiescent}) je videti, da se ponekod izgubi več informacije kakor drugod,
kar kaže na možnost izpeljave splošne teorije dinamike informacij.
Na žalost se ta možnost še ni udejanila. Podobno je možno grafično upodobiti predslike 2D CA,
ter iz grafov sklepati o izgubi informacije v 2D CA.

\vspace{10mm}
\begin{figure}[htb]
\centerline{\psfig{figure=network_rule110_quiescent,width=16cm}}
\caption[Mreža predslik 1D CA.]
{Mreža predslik 1D CA (pravilo 110) za tiho ozadje s cikličnim zaporedjem 00010011011111.
Vsaka od dveh poudarjenih poti med levim in desnim predstavlja predsliko.
V enem delu sta si predsliki enaki, drugod se razlikujeta.
Laično lahko sklepamo, da se tam, kjer se predsliki razlikujeta, izgubi 1 bit informacije.}
\label{network_rule110_quiescent}
\end{figure}
\vspace{5mm}

\subsection{Atraktorjevo korito}

Pomembno orodje za analizo časovno in prostorsko diskretnih dinamičnih sistemov
je \emph{atraktorjevo korito} (angl. \emph{basin of attraction}) (slika \ref{basin_of_attraction}).
Andrew Wuensche že leta proučuje atraktorjeva korita naključnih binarnih mrež in celičnih avtomatov \cite{Wuensche1992, WuenscheDDLab}.
To je graf, kjer so vozlišča stanja cikličnega končnega CA,
usmerjene poti pa povezujejo vsako stanje z njegovim časovnim naslednikom.
Vsa stanja se lahko zberejo v eno ali več korit, odvisno od sistema.
V vsakem CA, ki ni lokalno injektiven, se pojavljajo stanja brez predslik,
imenovana \emph{rajski vrt} (angl. \emph{Garden of Eden, GoE}) \cite{Moore1962, Myhill1963}.
Stanja GoE so listi v grafu korita.

Sam atraktor je cikel v grafu korita.
To je časovno periodično stanje, v katerem se končna časovna evolucija vsakega končnega diskretnega dinamičnega sistema.
Cikel lahko vsebuje eno ali več stanj, njihovo število imenujemo perioda atraktorja.
Atraktor predstavlja tudi stabilne objekte v neskončnem CA.
Za GoL obstajajo katalogi takih objektov, kjer so ti urejeni po velikosti, periodi in hitrosti premikanja.
Kot primer bi navedel \emph{mrtvo ozadje} (angl. \emph{quiescent background}) (perioda 1)
in \emph{drsalca} (angl. \emph{glider}) (perioda 4).

\begin{figure}[htb]
\centerline{\psfig{figure=basin_of_attraction_rule110_conf00010011011111,width=15cm}}
\caption[Atraktorjevo korito.]
{Atraktorjevo korito za elementarno pravilo 110 in konfiguracijo 00010011011111 znotraj atraktorja.
Korito vsebuje osrednji cikel atraktorja ter drevesa, ki rastejo iz cikla in se končujejo z listi (stanja GoE).
Slika je narejena s programom \url{www.ddlab.com}.}
\label{basin_of_attraction}
\end{figure}

\section{Algoritmi za štetje in izpis predslik CA}

Doslej sem že razvil napredne algoritme za štetje in izpis predslik 1D CA \cite{JerasDobnikar2007}.
Skozi zgodovino so taki algoritmi napredovali, tako da je padala njihova
računska zahtevnost in opisna/implementacijska zahtevnost:
\begin{enumerate}[noitemsep,nolistsep]
 \item algoritmi s \emph{surovo silo} (angl. \emph{brute force}) \cite{WikiBruteForce} imajo zahtevnost \( O(C^N) \),
 \item algoritmi z \emph{iskanjem v globino} (angl. \emph{depth first search, DFS}) \cite{WikiDFS}, \\
       algoritmi s \emph{sestopanjem} (angl. \emph{backtacking}) \cite{WikiBacktracking}, \\
       algoritmi, ki rešujejo \emph{problem izpolnjivosti} (angl. \emph{Boolean satisfiability problem, SAT}) \cite{WikiSAT},
 \item optimalni algoritmi, kjer sta izpis in štetje strogo ločena.
\end{enumerate}

Bistvo optimalnega algoritma je, da je proces štetja predslik optimalen.
Za 1D CA je to doseženo, saj je zahtevnost štetja
linearno odvisna od velikosti problema \(O(N)\) (\(N\) je število opazovanih celic). 
Raziskave algoritma za štetje predslik 2D CA sem se lotil s predpostavko,
da je tudi tu možno opraviti štetje predslik z linearno zahtevnostjo.
Izkaže se, da 2D problem ni tako preprost.
Predstavljeni so primeri, iz katerih je razvidno,
da algoritem z linearno zahtevnostjo ne more pravilno opisati vseh situacij.
Zahtevnost opisanega algoritma sicer raste eksponentno z velikostjo ene
od dimenzij polja CA \( O(C^{N_x}) \), in linearno z velikostjo druge dimenzije \( O(N_y) \)
(\(C\) je konstanta, odvisna od števila stanj celice in velikosti okolice, ne pa tudi od velikosti polja).
Ker pa nisem dokazal optimalnosti opisanega algoritma za štetje,
dopuščam možnost, da obstaja algoritem z nižjo kompleksnostjo.

Proces izpisa predslik ima vedno eksponentno rastočo komponento.
Ker število vseh stanj sistema raste eksponentno z velikostjo problema,
posledično tudi povprečje števila predslik skozi vsa stanja raste eksponentno.
Optimalen algoritem za izpis predslik je časovno in pomnilniško linearno odvisen od števila predslik.
Moja algoritma za izpis predslik 1D in 2D CA sta optimalna in
omogočata izpis predslik brez slepih poti,
kar je posledica podrobne analize problema ob štetju.

Ostali znani algoritmi spadajo v drugo kategorijo.
Večinoma izkoriščajo le lokalno znanje o sistemu (lokalno štetje predslik),
ne pa tudi globalnih števcev.
Zato zahajajo v slepe poti in se morajo vračati v prejšnje stanje
ali pa opuščajo neustrezne rešitve, katerim so že namenili procesni čas.

Pomembno vlogo pri razvoju opisanega algoritma ima mreža predslik.
To je grafična upodobitev problema, katere cilj je lažje razumevanje problema in rešitve.
Osnova za oblikovanje mreže predslik so De Bruijnovi diagrami.
Posamezen De Bruijnov diagram je mreža predslik ene celice.
Mreže posameznih celic se nato povezujejo,
tako da na koncu opisujejo celotno polje celic.

McIntosh in njegovi učenci so bili pobudniki uporabe De Bruijnovih diagramov za analizo 1D CA \cite{McIntosh1991}.
Uporabljali so jih za štetje in izpis predslik ter za analizo delcev in njihovih interakcij.
Paulina Léon in Genaro Martínez (McIntoshev učenec) \cite{PaulinaGenaro2016}
sta začetnika apliciranja De Bruijnovih diagramov na 2D CA,
vendar jih ne uporabljata za štetje in izpis predslik.

Največ raziskav s področja predslik 2D CA je bilo opravljenih ravno s ciljem iskanja stanj GoE v avtomatu GoL.
S stališča algoritma za štetje predslik je stanje GoE tako stanje, katerega število predslik je nič.
Algoritem za štetje predslik je možno pretvoriti v manj zahteven algoritem za preverjanje, ali je dano stanje stanje GoE,
tako da se operacije nad celimi števili pretvori v logične operacije nad Boolovimi stanji.

\subsection{Implementacija algoritma}

Algoritem je implementiran kot računalniški program v jeziku C \cite{Jeras2016-algirithm}.
Knjižnica GMP \footnote{The GNU Multiple Precision Arithmetic Library \url{https://gmplib.org/}}
je uporabljena za zapis celih števil, večjih od 64 bitov.
Poleg samega algoritma za štetje in izpis predslik sem pripravil tudi
orodje za simulacijo binarnega CA z okolico quad \cite{Jeras2016-quad},
ki temelji na simulatorju za GoE \cite{webgl-gol}.
Simulator se lahko zažene kar v internetnem brskalniku.
%in orodje za prikaz poljubne mreže predslik \cite{Jeras2016-network}.

\subsection{Primeri in ilustracije}

Večina primerov in ilustracij opisuje binarni 2D CA z majhno okolico quad
(štiri celice na kvadratnem polju, Toffoli 2008 \cite{Toffoli2008}).
Večina primerov in sploh ilustracije za GoL bi bile zaradi
\(2^{3 \cdot 3}=512\) možnih stanj okolice preveč kompleksne in nepregledne (glej dodatek \ref{GoLmatrika}).
V nasprotju ima binarna okolica quad le \(2^{2 \cdot 2}=16\) možnih stanj.

Želel sem sicer uporabiti kako določeno pravilo za okolico quad,
tako ki bi omogočalo zanimivo dinamiko delcev, vendar na tem področju še ni kaj dosti raziskav.
Obstaja le dokaz univerzalnosti za binarni avtomat z okolico trid (Powley 2008 \cite{Powley2008}).

Na slikah je uporabljena izometrična projekcija,
saj je za potrebe analize osnovnemu 2D polju dodana tretja dimenzija,
ki opisuje prostor predslik (mreža predslik).

\section{Pregled vsebine}

V poglavju \ref{definicija} podajam definicijo 1D in 2D CA.
V poglavju \ref{mreža} opišem konstrukcijo mreže predslik za 2D CA
in razložim njen odnos z naborom predslik za dano konfiguracijo.
V poglavju \ref{algoritem} opišem na novo razvit algoritem za štetje in izpis predslik
ter razložim, zakaj algoritem z linearno zahtevnostjo ni možen.
V poglavju \ref{pregled} opravim pregled obstoječih algoritmov
ter jih v poglavju \ref{sklep} primerjam s svojim algoritmom.
Tukaj še navedem doprinos tega magistrskega dela k področju celičnih avtomatov
in naštejem nekaj problemov, ki bi jih rad raziskal v prihodnje.
V dodatku \ref{primer} navedem primer delovanja algoritma in
v dodatku \ref{koda} navedem izvorno kodo algoritma.




\chapter{Definicija celičnih avtomatov}
\label{definicija}

V delu se omejujemo na celične avtomate, ki so:
\begin{itemize}[noitemsep,nolistsep]
 \item prostorsko diskretni (celice),
 \item časovno diskretni (korak),
 \item homogeni (pravila so enaka za vse celice in vse celice se posodobijo naenkrat) in
 \item deterministični (novo stanje je odvisno le od trenutnega stanja).
\end{itemize}

Vsaka celica ima diskretno vrednost \(c\) iz nabora stanj celice \(S\).
Stanja so oštevilčena:

\begin{equation}
c \in S
\quad \textrm{in} \quad
S = \{ 0, 1, \ldots, |S|-1 \}
\end{equation}

Za potrebe implementacije algoritma je pomembno,
da smo stanje elementov CA, kakor so pravilo, vrednost okolice in podobno,
sposobni indeksirati.
Uporabljena je metoda, ki je bila v osnovi namenjena zapisu pravila.
Posplošeno, vrednosti celic \(c(i)\) so zložene v niz \(A=[c(0),c(1), \ldots, c(|A|-1)\)] dolžine \(|A|\),
ki je interpretiran kakor \(|A|\) mestno pozitivno celo število \(num\) v
\(S\)-iškem številskem sestavu:

\begin{equation}
num = \sum_{i=0}^{i=|A|-1} |S|^i \cdot c(i)
\end{equation}

Za podane primere so uporabljeni binarni CA kjer je \(S=2\),
tako da so števila v dvojiškem sestavu.

\section{Definicija 1D celičnih avtomatov}

Definicijo 1D CA povzamemo po \cite{JerasDobnikar2007}.
Za 1D CA se celice združujejo v regularen niz.
Na splošno je dolžina niza lahko neskončna,
bolj običajni pa so končni nizi dolžine \(N\).
Nize zapisujemo z malimi grškimi črkami \(\alpha\) ali \(\beta\),
kjer je \(c(x)\) celica na koordinati \(x\):

\begin{equation}
\alpha = [c(0), c(1), \ldots, c(N-1)]
\end{equation}

\subsection{Okolica}

Za potrebe enostavnosti implementacije se okolica celice širi le v pozitivni smeri (slika \ref{neighborhood_1d}).
Torej je za celico \(c(x)\) njena okolica velikosti \(M\) enaka
\(n(x) = \{c(x), c(x+1), \ldots, c(x+M-1)\}\).
V praksi se podana definicija okolice razlikuje od
bolj običajne centrirane okolice le v tem,
kako je časovno sosledje stanj poravnano v grafični upodobitvi.
Nekoliko neobičajno definicijo sem uporabil zato,
ker ne potrebuje ločene interpretacije za okolice sode velikosti.
Hkrati sem se tako izognil uporabi negativnih števil v implementaciji algoritma.

\begin{figure}[htb]
\centerline{\psfig{figure=neighborhood_1d,width=16cm}}
\caption[Okolica 1D CA.]{Okolica 1D CA velikosti \(M=3\).}
\label{neighborhood_1d}
\end{figure}
\vspace{5mm}

Indeks okolice \(n(x)\) in nabor možnih okolic sta:

\begin{equation}
n(x) = \sum_{i=0}^{i=M-1} |S|^i \cdot c(x+i)
\end{equation}
\begin{equation}
n \in \{0, 1, \ldots, |S|^M-1\}
\end{equation}

\subsection{Prekrivanje okolic}

Dana okolica \(n(x)\) se za \(M-1\) celic prekriva z okolicama sosednjih celic (slika \ref{overlap_1d}).
Na levi imamo prekrivanje \(o_{\leftarrow}(x)\) med okolicama \(n(x-1)\) in \(n(x)\).
Na desni imamo prekrivanje \(o_{\rightarrow}(x)\) med okolicama \(n(x)\) in \(n(x+1)\).

\begin{figure}[htb]
\centerline{\psfig{figure=overlap_1d,width=12cm}}
\caption[Prekrivanje okolic 1D CA.]{Prekrivanje okolic 1D CA velikosti \(M-1=2\).}
\label{overlap_1d}
\end{figure}

Indeksa levega prekrivanja \(o_{\leftarrow}(x)\) ter desnega prekrivanja \(o_{\rightarrow}(x)\) in nabor možnih prekrivanj so:

\begin{equation}
o_{\leftarrow}(x) = \sum_{i=0}^{i=M-2} |S|^i \cdot c(x+i)
\end{equation}
\begin{equation}
o_{\rightarrow}(x) = \sum_{i=1}^{i=M-1} |S|^i \cdot c(x+i)
\end{equation}
\begin{equation}
o \in \{0, 1, \ldots, |S|^M-2\}
\end{equation}

\subsection{Lokalna tranzicijska funkcija in pravilo}

Preslikava sedanje okolice \(n^{t}(x)\) v prihodnjo istoležno celico \(c^{t+1}(x)\) je definirana
s tranzicijsko funkcijo \(f\), ki vsaki vrednosti okolice pripiše vrednost celice:

\begin{equation}
c^{t+1}(x) = f(n^{t}(x))
\end{equation}

Za potrebe iskanja predslik je zanimiva obratna funkcija \(f^{-1}\), ki ob
podanem stanju trenutne celice \(c^{t}(x)\) vrne množico okolic \(n^{t-1}(x)\),
ki se preslikajo v to vrednost:

\begin{equation}
f^{-1}(c^{t}(x)) = \{ n^{t-1}(x) \in S^m \ \arrowvert \ f(n^{t-1}(x)) = c^{t}(x) \}
\end{equation}

Tranzicijsko funkcijo je možno definirati s pravilom  \(r\).
Pravilo je indeks izbrane funkcije znotraj celotnega nabora \(|S|^{|S|^M}\) funkcij.
Definirano je kakor celo število v \(S\)-iškem številskem sestavu,
kjer so cifre zaporedje vrednosti celic v katere tranzicijska funkcija
preslika vsako od \(|S|^M\) možnih okolic:

\begin{equation}
r = \sum_{n=0}^{n=|S|^M-1} |S|^n \cdot f(n)
\end{equation}
\begin{equation}
r \in \{0, 1, \ldots |S|^{|S|^M}-1\}
\end{equation}

Globalna tranzicijska funkcija se pogosto zapisuje kakor tranzicijska tabela,
ki navaja vrednost tranzicijske funkcije \(f(n)\) za vsako okolico \(n\).

\subsection{Robni pogoji}

Neskončen niz celic nima roba in zanj ne potrebujemo definicije robnih pogojev.
Hkrati pa v praksi ne moremo računati z neskončnostjo,
zato obravnavamo končne nize celic.

Če smatramo opazovani končen niz za del neskončnega niza,
potem se moramo opredeliti, kako bomo obravnavali vrednosti celic izven opazovanega niza.
Tukaj je opisan samo odprt robni pogoj, kjer celice izven roba niso definirane,
oziroma lahko zasedejo poljubno vrednost.
Za niz dolžine \(N\) je potemtakem definiranih le \(N-(M-1)\) okolic.

Drugi običajen robni pogoj je cikličen, kjer je niz celic sklenjena zanka.
Ciklično koordinato celice \(x_{\circlearrowright}\) izračunamo iz \(x\) po modulu \(N\):

\begin{equation}
x_{\circlearrowright} = x \bmod N
\end{equation}

\subsection{Globalna tranzicijska funkcija}

Globalna tranzicijska funkcija \(F\) s pomočjo lokalne tranzicijske funkcije \(f(n)\)
preslika vsako okolico \(n^t(x)\) iz niza celic \(\alpha^t\) v času \(t\)
v celico \(c^{t+1}(x)\) iz niza celic \(\beta^{t+1}\) v času \(t+1\):

\begin{equation}
\beta^{t+1} = F (\alpha^t)
\end{equation}

Za odprti robni pogoj vrne globalna funkcija za vhodni niz dolžine \(N\)
izhodni niz dolžine \(N-(M-1)\), za cikličen robni pogoj pa niz dolžine \(N\).

\subsection{Predslike}

Vsaka predslika \(\beta^{t-1}\) dolžine \(N+M-1\) danega niza \(\alpha^t\) dolžine \(N\) mora ustrezati dvema pogojema:
\begin{enumerate}
\item Za vsako celico \(c^{t}(x)\) mora okolica \(n^{t-1}(x)\) ustrezati inverzni tranzicijski funkciji \(f^{-1}\):
\begin{equation}
\forall x : c^{t}(x) = f(n^{t-1}(x))
\end{equation}
\item Vsak par okolic \(\{n^{t-1}(x), n^{t-1}(x+1)\}\) se mora ujemati v prekrivanju:
\begin{equation}
\forall x : o^{t-1}(x) = o_{\rightarrow}^{t-1}(x) = o_{\leftarrow}^{t-1}(x+1)
\end{equation}
\end{enumerate}
Opazovanje prekrivanja okolic je glavni element algoritmov za iskanje predslik.

\section{Definicija 2D celičnih avtomatov}

Za 2D CA se celice združujejo v regularno 2D polje.
Mreža polja je lahko pravokotna, šestkotna ali celo kvazikristalna.
Tukaj se bomo omejili na pravokotno mrežo.
Na splošno je velikost polja lahko neskončna,
bolj običajna pa so končna polja,
definirana kakor pravokotnik velikosti \(N_x \times N_y\).
Skupno število celic v končnem polju je \(N=N_x \cdot N_y\).

Za potrebe indeksiranja elementov CA so ploskve razdeljene v vrstice,
nato pa so vrstice sestavljene v niz, ki je interpretiran kakor število.
Cifre v številu si sledijo od spodaj levo do zgoraj desno znotraj okolice
(sliki \ref{neighborhood_index_moore} in \ref{neighborhood_index_quad}).

\subsection{Okolica}

Prihodnje stanje neke celice \(c_(x,y)\) s koordinatami \((x,y)\)
je odvisno od trenutnega stanja pripadajoče okolice \(n_(x,y)\) (slika \ref{neighborhood}).
Tudi pri obliki okolice se bomo omejili na pravokotnik velikosti \(M_x \times M_y\).
Število celic v okolici je \(M=M_x \cdot M_y\).
Indeks okolice (sliki \ref{neighborhood_index_moore} in \ref{neighborhood_index_quad})
in nabor možnih okolic sta:
\begin{equation}
n(x,y) = \sum_{\substack{i=0 \\ j=0}}^{\substack{i=M_x-1 \\ j=M_y-1}} |S|^{M_x j + i} \cdot c(x+i,y+j)
\end{equation}
\begin{equation}
n \in \{0, 1, \ldots, |S|^{M_x M_y}-1\}
\end{equation}

\begin{figure}[htb]
\centerline{\psfig{figure=neighborhood_index_moore,width=12cm}}
\caption[Indeksiranje okolice \(3 \times 3\).]{Indeksiranje okolice celice z dimenzijama \(M_x=M_y=3\).}
\label{neighborhood_index_moore}
\end{figure}

\begin{figure}[htb]
\centerline{\psfig{figure=neighborhood_index_quad,width=10cm}}
\caption[Indeksiranje okolice \(2 \times 2\).]{Indeksiranje okolice celice z dimenzijama \(M_x=M_y=2\).}
\label{neighborhood_index_quad}
\end{figure}

Običajno se smatra, da je celica poravnana s sredino svoje okolice.
Tukaj pa je celica poravnana v levi spodnji kot svoje okolice.
To omogoča uporabo enake definicije tudi za sode velikosti okolic in
odpravlja potrebo po uporabi negativnih števil v algoritmu.

\begin{figure}[htb]
\centerline{\psfig{figure=neighborhood,width=16cm}}
\caption[Celica in pripadajoča okolica.]{Celica \(c(x,y)\) in pripadajoča okolica \(n(x,y)\) z dimenzijama \(M_x=M_y=3\).}
\label{neighborhood}
\end{figure}

\subsection{Prekrivanje okolic}

Okolice se v smeri dimenzije X prekrivajo za ploskev velikosti \((M_x-1) \times M_y\) (sliki \ref{overlap_dimension_moore} in \ref{overlap_dimension_quad}).
To ob indeksiranju da nabor:
\begin{equation}
o_{\leftarrow}(x,y) = \sum_{\substack{i=0 \\ j=0}}^{\substack{i=M_x-2 \\ j=M_y-1}} |S|^{(M_x-1) j + i} \cdot c(x+i,y+j)
\end{equation}
\begin{equation}
o_{\rightarrow}(x,y) = \sum_{\substack{i=1 \\ j=0}}^{\substack{i=M_x-1 \\ j=M_y-1}} |S|^{(M_x-1) j + i} \cdot c(x+i,y+j)
\end{equation}
\begin{equation}
o_{\leftrightarrow} \in \{0, 1, \ldots, |S|^{(M_x-1)M_y}-1\}
\end{equation}

Okolice se v smeri dimenzije Y prekrivajo za ploskev velikosti \(M_x \times (M_y-1)\) (sliki \ref{overlap_dimension_moore} in \ref{overlap_dimension_quad}).
To ob indeksiranju da nabor:
\begin{equation}
o_{\downarrow}(x,y) = \sum_{\substack{i=0 \\ j=0}}^{\substack{i=M_x-1 \\ j=M_y-2}} |S|^{M_x j + i} \cdot c(x+i,y+j)
\end{equation}
\begin{equation}
o_{\uparrow}(x,y) = \sum_{\substack{i=0 \\ j=1}}^{\substack{i=M_x-1 \\ j=M_y-1}} |S|^{M_x j + i} \cdot c(x+i,y+j)
\end{equation}
\begin{equation}
o_{\updownarrow} \in \{0, 1, \ldots, |S|^{M_x(M_y-1)}-1\}
\end{equation}

\vspace{5mm}
\begin{figure}[htb]
\centerline{\psfig{figure=overlap_dimension_moore,width=8cm}}
\caption[Prekrivaje okolic \(3 \times 3\) v smeri dimenzij X in Y.]
{Prekrivanje okolic sosednjih celic v smeri dimenzij X in Y, za velikost okolice \(M_x=M_y=3\).
Okolice se prekrivajo v 6 celicah od 9.}
\label{overlap_dimension_moore}
\end{figure}

\vspace{5mm}
\begin{figure}[htb]
\centerline{\psfig{figure=overlap_dimension_quad,width=8cm}}
\caption[Prekrivaje okolic \(2 \times 2\) v smeri dimenzij X in Y.]
{Prekrivanje okolic sosednjih celic v smeri dimenzij X in Y, za velikost okolice \(M_x=M_y=2\).
Okolice se prekrivajo v 2 celicah od 4.}
\label{overlap_dimension_quad}
\end{figure}

\vspace{5mm}
Okolice se v diagonalni smeri prekrivajo za ploskev velikosti \((M_x-1) \times (M_y-1)\) (sliki \ref{overlap_diagonal_moore} in \ref{overlap_diagonal_quad}).
To ob indeksiranju da nabor:
\begin{equation}
o_{\swarrow} = \sum_{\substack{i=0 \\ j=0}}^{\substack{i=M_x-2 \\ j=M_y-2}} |S|^{(M_x-1) j + i} \cdot c(x+i,y+j)
\end{equation}
\begin{equation}
o_{\searrow} = \sum_{\substack{i=1 \\ j=0}}^{\substack{i=M_x-1 \\ j=M_y-2}} |S|^{(M_x-1) j + i} \cdot c(x+i,y+j)
\end{equation}
\begin{equation}
o_{\nwarrow} = \sum_{\substack{i=0 \\ j=1}}^{\substack{i=M_x-2 \\ j=M_y-1}} |S|^{(M_x-1) j + i} \cdot c(x+i,y+j)
\end{equation}
\begin{equation}
o_{\nearrow} = \sum_{\substack{i=1 \\ j=1}}^{\substack{i=M_x-1 \\ j=M_y-1}} |S|^{(M_x-1) j + i} \cdot c(x+i,y+j)
\end{equation}
\begin{equation}
o_{\times} \in \{0, 1, \ldots, |S|^{(M_x-1)(M_y-1)}-1\}
\end{equation}

\vspace{5mm}
\begin{figure}[htb]
\centerline{\psfig{figure=overlap_diagonal_moore,width=10cm}}
\caption[Prekrivanje okolic \(3 \times 3\) - diagonalno.]
{Prekrivanje okolic sosednjih celic v diagonalni smeri, za velikost okolice \(M_x=M_y=3\).
Okolice se prekrivajo v 4 celicah od 9.}
\label{overlap_diagonal_moore}
\end{figure}

\vspace{5mm}
\begin{figure}[htb]
\centerline{\psfig{figure=overlap_diagonal_quad,width=8cm}}
\caption[Prekrivanje okolic \(2 \times 2\) - diagonalno.]
{Prekrivanje okolic sosednjih celic v diagonalni smeri, za velikost okolice \(M_x=M_y=2\).
Okolice se prekrivajo v eni celici od 4.}
\label{overlap_diagonal_quad}
\end{figure}

\subsection{Lokalna tranzicijska funkcija in pravilo}

Preslikava sedanje okolice \(n^{t}(x,y)\) v prihodnjo istoležno celico \(c^{t+1}(x,y)\) je definirana
s tranzicijsko funkcijo \(f\), ki vsaki vrednosti okolice pripiše vrednost celice:

\begin{equation}
c^{t+1}(x,y) = f(n^{t}(x,y))
\end{equation}

Za potrebe iskanja predslik je zanimiva obratna funkcija \(f^{-1}\), ki ob
podanem stanju trenutne celice \(c^{t}(x,y)\) vrne množico okolic \(n^{t-1}(x,y)\),
ki se preslikajo v to vrednost:

\begin{equation}
f^{-1}(c^{t}(x,y)) = \{ n^{t-1}(x,y) \in S^m \ \arrowvert \ f(n^{t-1}(x,y)) = c^{t}(x,y) \}
\end{equation}

Tranzicijsko funkcijo je možno definirati s pravilom  \(r\).
Pravilo je indeks izbrane funkcije znotraj celotnega nabora \(|S|^{|S|^{M_x M_y}}\) funkcij.
Definirano je kakor celo število v \(S\)-iškem številskem sestavu,
kjer so cifre zaporedje vrednosti celic, v katere tranzicijska funkcija
preslika vsako od \(|S|^{M_x M_y}\) možnih okolic:

\begin{equation}
r = \sum_{n=0}^{n=|S|^{M_x M_y}-1} |S|^n \cdot f(n)
\end{equation}
\begin{equation}
r \in \{0, 1, \ldots |S|^{|S|^{M_x M_y}}-1\}
\end{equation}

\subsection{Robni pogoji}

Neskončno polje nima roba in zanj ne potrebujemo definicije robnih pogojev.
Hkrati pa v praksi ne moremo računati z neskončnostjo,
zato obravnavamo končna polja celic.

Če smatramo opazovano končno polje za del neskončnega polja,
potem se moramo opredeliti, kako bomo obravnavali vrednosti celic izven opazovanega polja.
Tukaj je opisan samo odprt robni pogoj, kjer celice izven roba niso definirane,
oziroma lahko zasedejo poljubno vrednost.
Za polje velikosti \(N_x \times N_y\) je potemtakem definiranih le \((N_x+(M_x-1)) \times (N_y+(M_y-1))\) okolic.

Drugi običajen robni pogoj je cikličen, kjer je polje celic torus.
Ciklično koordinato celice \((x_{\circlearrowright},x_{\circlearrowright})\) izračunamo iz \((x,y)\) po modulu \(N_x\) oziroma \(N_y\).

\begin{equation}
x_{\circlearrowright} = x \bmod N_x
\hspace{10mm}
y_{\circlearrowright} = y \bmod N_y
\end{equation}

\subsection{Globalna tranzicijska funkcija}

Globalna tranzicijska funkcija \(F\) s pomočjo lokalne tranzicijske funkcije \(f(n)\)
preslika vsako okolico \(n^t(x,y)\) iz niza celic \(A^t\) v času \(t\)
v celico \(c^{t+1}(x)\) iz niza celic \(B^{t+1}\) v času \(t+1\).

\begin{equation}
B^{t+1} = F (A^t)
\end{equation}

Za odprti robni pogoj vrne globalna funkcija za vhodno polje velikosti \(N_x \times N_y\)
izhodno polje velikosti \((N_x+(M_x-1)) \times (N_y+(M_y-1))\),
za ciklični robni pogoj pa polje velikosti \(N_x \times N_y\).

\subsection{Predslike}

Vsaka predslika \(B^{t-1}\) velikosti \((N_x+1) \times (N_y+1)\) danega polja \(A^t\) velikosti \(N_x \times N_y\) mora ustrezati naslednjim pogojem:
\begin{enumerate}
\item Za vsako celico \(c^{t}(x,y)\) mora okolica \(n^{t-1}(x,y)\) ustrezati invezni funkciji \(f^{-1}\):
\begin{equation}
\forall x,y : c^{t}(x,y) = f(n^{t-1}(x,y))
\end{equation}
\item Vsak par okolic v dimenziji X \(\{n^{t-1}(x,y), n^{t-1}(x+1,y)\}\) se mora ujemati v prekrivanju:
\begin{equation}
\forall x,y : o_{\leftrightarrow}^{t-1}(x,y) = o_{\rightarrow}^{t-1}(x,y) = o_{\leftarrow}^{t-1}(x+1,y)
\end{equation}
\item Vsak par okolic v dimenziji Y \(\{n^{t-1}(x,y+0), n^{t-1}(x,y+1)\}\) se mora ujemati v prekrivanju:
\begin{equation}
\begin{align}
\forall x,y : o_{\updownarrow}^{t-1}(x,y) &= o_{\downarrow}^{t-1}(x,y+1) \\
                                          &= o_{\uparrow}  ^{t-1}(x,y+0)
\end{align}
\end{equation}
\item Vsaka četvorka diagonalnih okolic \(\{n^{t-1}(x,y), n^{t-1}(x+1,y), n^{t-1}(x,y+1), n^{t-1}(x+1,y+1)\}\) se mora ujemati v prekrivanju:
\begin{equation}
\begin{align}
\forall x,y : o_{\times}^{t-1}(x,y) &= o_{\searrow}^{t-1}(x+0,y+1) = o_{\swarrow}^{t-1}(x+1,y+1) \\
                                    &= o_{\nearrow}^{t-1}(x+0,y+0) = o_{\nwarrow}^{t-1}(x+1,y+0)
\end{align}
\end{equation}
\end{enumerate}

Za potrebe nekaterih ilustracij je uporabljena bolj splošna definicija inverzne lokalne tranzicijske funkcije.
Za vsako celico je lahko definiran lasten nabor predslik \(n^{t-1} \in S^M\),
ki je na splošno neodvisen od stanja celice.
Ta posplošitev je uporabljena za konstrukcijo umetnih mrež predslik,
ki poudarjajo konkretne probleme, povezane s kompleksnostjo algoritma.

\subsection{Prekrivanje predslik in prerez}

Če polje 2D celičnega avtomata razdelimo na dva dela,
lahko definiramo predsliko za vsak del posebej.
Tukaj se bomo omejili na ravne prereze polja,
čeprav je na splošno mogoče definirati poljuben prerez.

Indeks prereza v smeri dimenzije X na koordinati \(y\) in njegov nabor sta definirana kot:
\begin{equation}
e_{\leftrightarrow}(y) = \sum_{\substack{i=0 \\ j=0}}^{\substack{i=N_x+M_x-1 \\ j=M_y-1}} |S|^{(N_x-1) j + i} \cdot c(i,y+j)
\end{equation}
\begin{equation}
e_{\leftrightarrow} \in \{0, 1, \ldots, |S|^{(N_x+M_x-1)(M_y-1)}-1\}
\end{equation}
Indeks prereza v smeri dimenzije Y na koordinati \(x\) in njegov nabor sta definiran kakor:
\begin{equation}
e_{\updownarrow}(x) = \sum_{\substack{i=0 \\ j=0}}^{\substack{i=M_x-1 \\ j=N_y+M_y-1}} |S|^{(N_x-1) j + i} \cdot c(x+i,j)
\end{equation}
\begin{equation}
e_{\updownarrow} \in \{0, 1, \ldots, |S|^{(M_x-1)(N_y+M_y-1)}-1\}
\end{equation}

Prerezi se uporabljajo za zapis vmesnih rezultatov pri algoritmih za iskanje predslik 2D CA.

\subsection{Primeri}

\subsubsection{Klasične 2D okolice}

Za klasične 2D CA sta definirani von Neumannova in Mooreova okolica (slika \ref{neighborhood_classic}).
Von Neumanova okolica je podmnožica Mooreove okolice, kjer so stanja vogalnih okolic ignorirana.
To pomeni, da tukaj opisana splošna definicija zaobjame obe klasični okolici.

\vspace{5mm}
\begin{figure}[htb]
\centerline{\psfig{figure=neighborhood_classic,width=10cm}}
\caption[Klasične 2D okolice.]
{Klasični 2D okolici, von Neumannova (levo) in Mooreova (desno).}
\label{neighborhood_classic}
\end{figure}

\subsubsection{Okolica quad}

V primerih je uporabljen binarni \((|S|=2)\) 2D CA z okolico quad \(M_x=M_y=2\) (slika \ref{neighborhood_index_quad}).
V okolici \(n\) je \(M=M_x \cdot M_y=2 \cdot 2=4\) celic, kar da nabor velikosti \(|S|^4=16\).
V prekrivanjih \(o_{\leftrightarrow}\) in \(o_{\updownarrow}\) v smereh X in Y
sta \(M=(M_x-1) \cdot M_y=M_x \cdot (M_y-1)=2\) celici, kar da nabor velikosti \(|S|^2=4\).
V prekrivanjih \(o_{\times}\) v diagonalnih smereh
je \(M=(M_x-1) \cdot (M_y-1)=1 \cdot 1=1\) celic, kar da nabor velikosti \(|S|^1=2\).

\subsubsection{Conwayev GoL}

GoL je binaren celični avtomat \((|S|=2)\), ki uporablja Mooreovo okolico \(M_x=M_y=3\) (slika \ref{neighborhood_index_moore}).
V okolici \(n\) je \(M=M_x \cdot M_y=3 \cdot 3=9\) celic, kar da nabor velikosti \(|S|^9=512\).
V prekrivanjih \(o_{\leftrightarrow}\) in \(o_{\updownarrow}\) v smereh X in Y
je \(M=(M_x-1) \cdot M_y=M_x \cdot (M_y-1)=6\) celic, kar da nabor velikosti \(|S|^9=64\).
V prekrivanjih \(o_{\times}\) v diagonalnih smereh
je \(M=(M_x-1) \cdot (M_y-1)=2 \cdot 2=4\) celic, kar da nabor velikosti \(|S|^4=16\).

Nabor vseh pravil \(n\) za to okolico je velikosti \(|S|^{|S|^{M}}=2^{512}\).
Lokalna tranzicijska funkcija je definirana opisno \cite{WikiGoL}.
Stanji celice sta opisani kakor mrtvo \((c=0)\) in živo \((c=1)\).
V vsakem časovnem koraku se z vsako celico zgodi naslednje:
\begin{enumerate}
\item živa celica z manj kakor dvema živima sosedoma umre,
\item živa celica z dvema ali tremi živimi sosedi živi naprej v naslednji korak,
\item živa celica z več kakor tremi živimi sosedi umre,
\item mrtva celica z natanko tremi živimi sosedi oživi.
\end{enumerate}
Pravilo GoL je 512-bitna binarna vrednost, v šestnajstiškem zapisu je \(r\):
\begin{verbatim}
00000000000100010001000101170116000100010117011601170116177E1668
000100010117011601170116177E166801170116177E1668177E16687EE86880
\end{verbatim}




\chapter{Konstrukcija mreže predslik}
\label{mreža}

Mreža predslik je grafični konstrukt, ki omogoča upodobitev
okolice, prekrivanja okolic in tranzicijske funkcije
kot ločene grafične elemente (vozlišča, poti in ploskve).
Odnosi med temi elementi definirajo pravila,
na katerih se gradijo algoritmi za iskanje predslik.

\section{De Bruijnov diagram}

Osnovni element grafične upodobitve je nekoliko svobodna interpretacija De Bruijnovega diagrama \cite{WikiDeBruijn}.
V osnovi ta obravnava ciklične premike končnih zaporedij simbolov ter njihovo prekrivanje.
Harold V. McIntosh \cite{McIntosh1991} in njegova skupina \cite{Soto2008}
so priredili De Bruijnove grafe za potrebe analize 1D CA (slika \ref{de_bruijn_diagram} levo).
Vozlišča predstavljajo nabor možnih prekrivanj med okolicami,
poti med njimi pa okolice, ki se v vrednosti celic ujemajo s temi prekrivanji.
Tranzicijska funkcija pripiše vsaki okolici stanje celice;
posledično so poti med vozlišči označene z vrednostmi iz tranzicijske tabele.
De Bruijnove grafe nato razdelimo na podgrafe za vsako stanje celice.
Podgraf vsebujejo le tiste poti, katerih pripadajoče okolice se preslikajo v eno od stanj celice.
De Bruijnov podgraf predstavlja nabor vseh preteklosti celice z danim stanjem.

\begin{figure}[htb]
\centerline{\psfig{figure=de_bruijn_diagram,width=12cm}}
\caption[De Bruijnov graf, pravilo 110.]
{De Bruijnov graf za elementarni 1D CA, pravilo 110.
Na levi je McIntosheva upodobitev, na desni pa moja, ki omogoča nizanje.
S prekinjeno črto so predstavljene kopije vozlišč.}
\label{de_bruijn_diagram}
\end{figure}

\section{Mreža predslik 1D celičnih avtomatov}

Razvil sem modificirano upodobitve De Bruijnovega grafa,
kjer so originalna vozlišča (prekrivanja \(o\)) podvojena
in gredo poti (okolice \(n\)) vedno od originala \(o_{\leftarrow}\)
proti dvojniku \(o_{\rightarrow}\) (slika \ref{de_bruijn_diagram} desno) \cite{JerasDobnikar2007}.
Tako upodobitev sem poimenoval \textbf{graf predslik}.

Graf predslik omogoča \textbf{nizanje} grafov v \textbf{mrežo predslik}.
Dvojniki vozlišč za trenutno celico \(o_{\rightarrow}(x)\) se ujemajo z
originalnimi vozlišči za naslednjo celico \(o_{\leftarrow}(x+1)\) (slika \ref{network_rule110_quiescent}).
Medtem ko osnovni De Bruijnov graf opisuje okolico ene same celice,
nizan graf opisuje okolice niza celic.
Nizan graf sem poimenoval mreža predslik,
saj predstavlja nabor vseh predslik celotne konfiguracije.
Število predslik je enako številu vseh poti,
ki povezujejo en in drugi rob.

\textbf{Robni pogoji} 1D CA so definirani na levem in desnem koncu,
ki omejujeta končno število celic znotraj neskončnega niza (premica).
Robni pogoj definira, katera prekrivanja \(o_{\leftrightarrow}\)
in s kakšnimi utežmi so dovoljena ob robu.
Lahko si jih predstavljamo tudi kakor vpliv pol neskončnega niza celic (poltraka),
ki sega izven roba opazovane konfiguracije.
Podrobneje so robni pogoji 1D CA definirani v \cite{JerasDobnikar2007}.

\section{Mreža predslik 2D celičnih avtomatov}

\subsection{Graf predslik}

Za potrebe opisa 2D CA je bila elementom grafa predslik dodana nova dimenzija.
Povezave med vozlišči se spremenijo v ploskve,
vozlišča pa se spremenijo v robove ploskev.
Elementi celičnega avtomata, ki se preslikajo v graf, so:
\begin{itemize}[noitemsep,nolistsep]
\item nabor \textbf{okolic} (\(n\)) postane nabor \textbf{ploskev} (slika \ref{neighborhood_surfaces}),
\item nabor \textbf{prekrivanj v smeri dimenzij X in Y} (\(o_{\leftrightarrow}\) in \(o_{\updownarrow}\)) (slika \ref{overlap_dimension_quad}) postane nabor \textbf{povezav},
\item nabor \textbf{prekrivanj v diagonalni smeri} (\(o_{\times}\)) (slika \ref{overlap_diagonal_quad}) postane nabor \textbf{vozlišč}.
\end{itemize}

\begin{figure}[htb]
\centerline{\psfig{figure=network_single,width=12cm}}
\caption[Mreža ene celice.]{Mreža ene celice za binarni CA z okolico quad \(M_x=M_y=2\).}
\label{network_single}
\end{figure}

Graf predslik je postavljen na kvadrat, ki predstavlja okolico \(n\).
Nad vsakim vogalom je nabor vozlišč, ki predstavljajo nabor diagonalnih prekrivanj
\(o_{\swarrow}\), \(o_{\searrow}\), \(o_{\nwarrow}\) in \(o_{\nearrow}\).

Vozlišči sosednjih vogalov v dimenziji X (\(o_{\swarrow}\) in \(o_{\searrow}\)) sta povezani,
če sta del iste konfiguracije celic, ki predstavlja povezavo v smeri X (\(o_{\downarrow}\)).
Vozlišči sosednjih vogalov v dimenziji Y (\(o_{\swarrow}\) in \(o_{\nwarrow}\)) sta povezani,
če sta del iste konfiguracije celic, ki predstavlja povezavo v smeri Y (\(o_{\leftarrow}\)).

Nastali graf (slika \ref{network_single} desno) ima poleg vozlišč in povezav med njimi tudi ploskve.
Vogali \(o_{\swarrow}\), \(o_{\searrow}\), \(o_{\nwarrow}\) in \(o_{\nearrow}\)
pripadajo določeni ploskvi \(n\), če so del iste konfiguracije celic.
Podobno velja za robove; \(o_{\leftarrow}\), \(o_{\rightarrow}\), \(o_{\downarrow}\) in \(o_{\uparrow}\)
pripadajo določeni ploskvi \(n\), če so del iste konfiguracije celic.

Za primer je uporabljena binarna okolica quad.
Ploskev \(n=\bigl[\begin{smallmatrix} 0&1 \\ 1&0 \end{smallmatrix}\bigr]\)
ima vogale \(o_{\swarrow}=1\), \(o_{\searrow}=0\), \(o_{\nwarrow}=0\) in \(o_{\nearrow}=1\) ter robove
\(o_{\leftarrow}=\bigl[\begin{smallmatrix} 0 \\ 1 \end{smallmatrix}\bigr]\),
\(o_{\rightarrow}=\bigl[\begin{smallmatrix} 1 \\ 0 \end{smallmatrix}\bigr]\),
\(o_{\downarrow}=\bigl[\begin{smallmatrix} 0 & 1 \end{smallmatrix}\bigr]\) in
\(o_{\uparrow}=\bigl[\begin{smallmatrix} 1 & 0 \end{smallmatrix}\bigr]\).

\begin{figure}[htb]
\centerline{\psfig{figure=neighborhood_surfaces,width=16cm}}
\caption[Nabor ploskev.]{Nabor ploskev za vseh 16 možnih vrednosti okolic za binarni CA z okolico quad \(M_x=M_y=2\).}
\label{neighborhood_surfaces}
\end{figure}

\subsection{Mreža predslik}

Podobno kot je pri 1D CA možno grafe predslik nizati v mrežo predslik,
je pri 2D CA grafe predslik možno \textbf{tlakovati} v \textbf{mrežo predslik},
ki opisuje polje več celic.
Nabor predslik celotnega polja je ekvivalenten naboru vseh \textit{zveznih} ploskev,
ki prekrivajo celotno polje (zahteva po prekrivanju okolic)
in ki jih je možno sestaviti iz naborov ploskev diagramov posameznih celic
(zahteva po ujemanju z lokalno tranzicijsko funkcijo).

Preslikava iz zvezne ploskve v mreži predslik v konfiguracijo polja celic predslike \(B^{t-1}\) je enolična.
Iz ploskve vsake okolice \(n(x,y)\) vzamemo izhodiščno celico
\(c_{\swarrow}(x,y)\) (celica spodaj levo znotraj okolice).
Nato dodamo vrstico celic višine \(M_y-1\) iz zgornjega prekrivanja na vrhu \(o_{\uparrow}(x,y=N_y)\),
ter stolpec celic širine \(M_x-1\) iz desnega prekrivanja na skrajni desni \(o_{\rightarrow}(x=N_x,y)\).

Podani primeri uporabljajo binarni CA z okolico quad.
Za ta CA je velikost diagonalnega prekrivanja okolic ena sama celica (slika \ref{overlap_diagonal_quad});
posledično ima nabor vozlišč le dve vrednosti, ki neposredno predstavljata
vrednosti celic v predsliki (slika \ref{network_array}).

Pravilnost razširitve diagrama ene celice v mrežo lahko dokažemo z indukcijo.
Dokazati želimo, da je neka konfiguracija celic predslika dane sedanjosti,
\textit{če in samo če} je ta ekvivalentna zvezni ploskvi v mreži predslik.

\textbf{Prvi element:}
Iz definicije \textit{okolice/ploskve} velja,
da je za eno samo celico v mreži nabor ploskev enak naboru vseh predslik.
\textbf{Naslednji element:}
Obstoječi mreži predslik dodamo novo celico.
Ploskev iz nabora dodane celice se zvezno veže s ploskvijo
iz obstoječega nabora zveznih ploskev,
ko se z njo ujema v robu (vozliščema in povezavi med njima).
Robovi ploskev se ujemajo natanko v primeru, ko se ujemajo prekrivanja okolic.
Temu je tako, ker so indeksi vozlišč in povezav ekvivalentni
vrednosti prekrivanj okolic v diagonali in v smeri koordinatnih osi.

\begin{figure}[htb]
\centerline{\psfig{figure=network_array,width=14cm}}
\caption[Mreža polja celic.]{Mreža velikosti \(N_x=3\) in \(N_y=3\) za binarni CA z okolico quad.
Poudarjena je ena zvezna ploskev in njen zvezen rob. Konfiguracija pripadajoče predslike je izpisana.}
\label{network_array}
\end{figure}

\subsection{Robni pogoj}

Pri 2D CA je robni pogoj definiran kakor utež sklenjene poti okoli ploskve opazovane konfiguracije celic.
V mreži predslik za 2D CA povezave med vozlišči definirajo rob ploskve (slika \ref{network_array}).
Vsaka zvezna ploskev v mreži ima zvezen rob. Robni pogoj določa, kako je ta ploskev obravnavana,
oziroma, ali je sploh obravnavana.
Ker uporabna vrednost splošnega robnega pogoja še ni znana,
in bi splošnost izrazito povečala zahtevnost algoritma za iskanje predslik,
so tukaj vsi robovi obravnavani enako, z utežjo ena. Temu bomo rekli odprti rob,
ker ta ne definira nobenih omejitev, katere zvezne ploskve v mreži predslik
so dovoljene in katere ne.

Obstaja še en enostaven robni pogoj, ki je definiran za ciklično sklenjena končna polja CA (torus).
Ta tip robnega pogoja tukaj ne bo obravnavan, ker še dodatno poveča kompleksnost algoritmov.
Potrebno bi bilo namreč opraviti celoten postopek iskanja predslik za vsak začetni rob posebej.
Saj je zvezna ploskev predslika v cikličnem polju le, če se njen začetni in končni rob ujemata.
Pojma začetnega in končnega roba sta opisana v poglavju o algoritmu.
V članku \cite{JerasDobnikar2007} je podrobneje opisan ta problem za 1D CA.




\chapter{Algoritem za štetje in izpis predslik}
\label{algoritem}

Pri 1D CA \cite{JerasDobnikar2007} ima algoritem za štetje predslik
linearno \(O(N)\) procesno in pomnilniško zahtevnost.
Posplošeno to pomeni, da se vsaka celica pojavi v izračunu samo enkrat.
Vsak algoritem za štetje ima tudi logaritmično komponento,
saj število bitov, potrebnih za zapis števcev, raste logaritmično s preštetim številom.
Ta komponenta se pozna pri implementaciji,
šele ko velikost števcev preseže velikost registrov.
64 bitov zadošča za binarno polje celic \(8 \times 8\).

Za 2D CA se je izkazalo, da obstajajo problemi, ki niso rešljivi z linearno kompleksnostjo.
Prikazanemu algoritmu raste maksimalna procesna zahtevnost
eksponentno v odvisnosti od ene dimenzije in
linearno v odvisnosti od druge dimenzije,
torej \(O(C^{N_x} N_y)\) ali \(O(N_x C^{N_y})\) (\(C=|S|^M\) je konstantna velikost nabora okolic).
Za sedaj je še neznano, če obstoja algoritem z manjšo maksimalno kompleksnostjo.

Algoritem za izpis predslik ima ne glede na število dimenzij
neizogibno eksponentno kompleksnost \(O(C^N)\) (\(C\) je konstanta, odvisna od optimizacij),
saj maksimalno in povprečno število predslik raste eksponentno
v odvisnosti od števila celic.

\section{Štetje poti v grafu}

Algoritem za štetje uporablja principe iz teorije grafov \cite{DBLP:journals/corr/cs-DL-0309023}.
Število poti med dvema vozliščema v acikličnem usmerjenem grafu se računa tako,
da se vsakemu vozlišču pripiše utež \(w\).
V prvem koraku začetno vozlišče dobi utež \(w(zacetek)=1\).
Vse poti, ki izhajajo iz obteženega vozlišča,
imajo utež enako uteži izvornega vozlišča.
V naslednjih korakih se računajo uteži vozlišč tako,
da je izhodna utež vsota vhodnih uteži \(w_{izhod}=\Sigma w_{vhod}\).
Algoritem se zaključi, ko število opravljenih korakov doseže dolžino najdaljše poti.
Na koncu je utež končnega vozlišča \(w(konec)\)
enaka številu vseh poti med začetnim in končnim vozliščem.

Če želimo vedeti koliko od teh poti gre skozi posamezno vozlišče
ali po posamezni povezavi med vozlišči,
potem postopek ponovimo v obratni smeri.
Vlogi začetnega in končnega vozlišča se zamenjata,
in obrnejo se smeri vseh poti.
Skupna utež vozlišča je zmnožek uteži za naprej in nazaj
\(w_{skupna} = w_{naprej} \cdot w_{nazaj}\).

Pri celičnih avtomatih je opazovani graf mreža predslik, ki ima zelo regularno strukturo.
Dolžina najdaljše poti je enaka velikosti ene od dimenzij polja CA.
Poleg tega ob vsakem koraku opazujemo samo del vozlišč, ki pripadajo enemu prerezu.

\section{Štetje predslik}

Opisani algoritem razdeli polje celic na vrstice v dimenziji X.
Delitev po stolpcih v dimenziji Y bi bila ekvivalentna, tako da je to arbitrarna odločitev.
S stališča procesne zahtevnosti je najbolje izbrati krajšo dimenzijo.

Ker mreža predslik ni navaden graf, temveč je razširjen s pojmom ploskve,
je potrebno mrežo predslik pred začetkom štetja najprej preslikati v navaden graf.
Vozlišča predstavljajo vsi možni robovi \(e_{\leftrightarrow}(y)\) na vseh presekih med vrsticami.
Vozlišča so fiksni elementi v grafu, obstajajo ne glede na konfiguracijo in stanje predslik.

Povezave med vozlišči so ploskve med dvema roboma
\(e_{\leftrightarrow}(y)\) in \(e_{\leftrightarrow}(y+1)\).
Vsaka povezava predstavlja eno predsliko vrstice celic na koordinati \(y\).
Povezava v grafu obstaja, če obstaja ekvivalentna predslika vrstice,
torej je za izgradnjo grafa potrebno poiskati vse predslike za vsako vrstico.
Ker je vrstica v 2D polju 1D objekt, lahko problem pretvorimo v 1D CA in
uporabimo za izračun predslik vrstice algoritme za štetje in izpis predslik 1D CA.

Z uporabo Boolove algebre namesto operacij množenja in seštevanja
je možno poenostaviti iskanje predslik samo na njihov obstoj za opazovani robni pogoj.
Uteži postanejo binarne vrednosti \(w \in \{0, 1\}\).
Predslika ali delna predslika obstaja, če je njena utež neničelna \(w>0\).
Za preverjanje tega pogoja ni potrebno štetje, zadoščajo že logične operacije.

Tukaj opisana implementacija algoritma (izvorna koda je v dodatku \ref{koda}) ne išče vseh predslik za vrstico hkrati,
temveč se omeji le na predslike, ki so skladne z enim od možnih robov
\(e_{\leftrightarrow}\) in to naredi za vse robove, ki so na voljo.

\subsection{Procesiranje niza v dimenziji X}

Procesiranje se začne z 1D nizom celic (vrstico).
Vsaki celici v nizu pripada lastna mreža predslik, eno-dimenzionalnemu nizu celic
posledično pripada povezan niz mrež predslik (slika \ref{algorithm_line}, mreža \textbf{1}).
Vsak segment mreže v nizu ima svoj nabor veljavnih okolic,
ki je definiran s tranzicijsko funkcijo (ali pa je posplošeno poljuben nabor).
Na začetku se ploskve okolic sosednjih celic še ne povezujejo v
zvezno ploskev čez celoten niz. Izločiti je potrebno vse ploskve okolic,
ki se ne povezujejo z okolicami svojih sosednjih celic.

Ker se vsaka vrstica povezuje s predhodno in naslednjo vrstico, je potrebno
upoštevati tudi zveznost ploskev na prehodu med vrsticami.
Ta povezava med vrsticami je prerez opazovane ploskve na meji med vrsticama.
Vsako ploskev obravnavamo posebej in prerez izrazimo kakor robni pogoj.
Začetni robni pogoj \(e_{\downarrow}\) za vsako vrstico
je nabor poti med vozlišči na spodnji strani vrstice.
Vsak začetni pogoj obravnavamo posebej (slika \ref{algorithm_line}, mreža \textbf{2}, odebeljena pot).

Začetni robni pogoj \(e_{\downarrow}\) apliciramo tako,
da izločimo iz obravnave vse ploskve,
ki nimajo skupnega roba z robnim pogojem (slika \ref{algorithm_line},
prehod iz mreže \textbf{1} v mrežo \textbf{2}).
Po tem koraku so vse okolice definirane na spodnjem prekrivanju.
Do nezveznosti lahko prihaja le še na robu,
nasprotnem začetnemu robu \(e_{\uparrow}\).

Problem se reducira iz 3D mreže in procesiranja ploskev v 2D mrežo,
kjer se procesirajo poti med vozlišči (slika \ref{algorithm_line},
prehod iz mreže \textbf{2} v mrežo \textbf{3}).
To je problem, ekvivalenten štetju in izpisu predslik za 1D CA,
za kar sem uporabil algoritem, opisan v \cite{JerasDobnikar2007}.
Rezultat je nabor končnih robnih pogojev \(e_{\uparrow}\)
(slika \ref{algorithm_line}, mreža \textbf{4}, končni robni pogoj je odebeljen).

\begin{figure}[htb]
\centerline{\psfig{figure=algorithm_line,width=14cm}}
\caption[Algoritem procesiranja vrstice.]{Mreža vrstice velikosti \(N_x=3\) za binarni CA z okolico quad.
Nabor okolic/ploskev za posamezno celico je arbitraren. Izbran je tako, da poudari korake algoritma.}
\label{algorithm_line}
\end{figure}
\vspace{5mm}

Po procesiranju nabora vseh začetnih robnih pogojev \(e_{\downarrow}\)
nastane nabor vseh končnih robnih pogojev \(e_{\uparrow}\).
Ta nabor se v naslednjem koraku uporabi kakor začetni robni pogoj za naslednjo vrstico.

Zaradi procesa izpisa poti v grafu,
procesna zahtevnost raste eksponentno z dolžino vrstice \(O(C^{N_x})\).

\subsection{Procesiranje polja v dimenziji Y}

V drugi dimenziji se procesira zaporedje vrstic od prve do zadnje (slika \ref{algorithm_list}).
Vsaka vrstica se začne in konča z robnim pogojem.
Vsako vrstico je potrebno v drugi dimenziji procesirati le enkrat, kar pomeni,
da je računska zahtevnost linearno odvisna od števila vrstic \(O(N_y)\).

Vsakemu robnemu pogoju je pripisana utež. Začetni robovi za prvo vrstico imajo pripisano utež \(w=1\).
Na splošno se lahko več začetnih robov preslika v isti končni rob ene vrstice.
Utež, pripisana končnemu robu dane vrstice, je vsota uteži vseh začetnih robnih pogojev, ki se preslikajo vanj.
Utež tako predstavlja število vseh predslik za dano in prejšnje vrstice, ki se končajo z opazovanim robom.
Robovi, s katerimi se ne konča nobena od predslik, dobijo utež \(w=0\).

Za tem, ko so procesirane vse vrstice, je znan končni rob nabora vseh zveznih ploskev na celotni mreži predslik.
Vsota uteži vseh končnih robov daje število predslik celotne mreže.

\section{Izpis predslik}

Algoritem za izpis predslik (izvorna koda je v dodatku \ref{koda}) je nadaljevanje algoritma za štetje.
Začne z znanim številom predslik, ki ga je dalo štetje, in izpisuje predslike
po vrsticah v obratni smeri, kakor je potekalo štetje (od zadnje do prve vrstice).
Pridobljen seznam predslik je sortiran. Smer sortiranja je odvisna od smeri procesiranja.
Smer procesiranja je možno po potrebi spremeniti.

Ni nujno, da se vsak vrstični začetni pogoj preslika v nabor končnih pogojev.
Možno je, da nobena pot na končnem robu ne zadošča začetnemu pogoju in mreži predslik.
Torej po prejšnjih korakih še ni točno določeno, katere ploskve se združujejo v zvezno
celoto in katere ne. Možne so ploskve, ki prekrivajo polje samo do neke vrstice in ne naprej.

Procesiranje po drugi dimenziji poteka v obratni smeri kakor pri štetju;
začne pri zadnji vrstici in konča pri prvi vrstici (slika \ref{algorithm_list}).
Z vsakim korakom se izloča še preostale slepe poti iz mreže predslik.
Za vsako vrstico je potrebno ponovno rešiti 1D problem,
le da sta začetni in končni rob zamenjana.

Hkrati je možno še izpisovati predslike. Že na začetku procesiranja v obratni smeri
je znano število vseh predslik, kar omogoča rezervacijo pomnilnika in inicializacijo seznama predslik.
Končne robne poti in njihove uteži se uporabijo za popis tekoče vrstice celic v predslikah.
Indeks robne poti (določeno zaporedje prekrivajočih okolic) da vrednost celic v vrstici predslike.
Uteži, izračunane v smeri štetja pa dajo število predslik,
ki jih je potrebno popisati z dano vrednostjo za vrstico celic.

Z vsakim korakom v obratni smeri se popiše nova vrstica za vsako od preštetih predslik.
Ko pride algoritem spet do začetne vrstice, so vse predslike popisane.
Hkrati so iz mreže predslik izločene vse slepe poti; ostanejo le še ploskve,
ki tvorijo zvezne ploskve na celotnem polju celic.

\begin{figure}[htb]
\centerline{\psfig{figure=algorithm_list,width=8cm}}
\caption[Algoritem za izpis predslik.]{Potek smeri procesiranja pri algoritmu za štetje in izpis predslik.}
\label{algorithm_list}
\end{figure}

\section{Nezmožnost štetja z linearno zahtevnostjo}

Podan je primer, ki kaže, zakaj procesiranje z linearno zahtevnostjo ni mogoče.

Cilj raziskovalnega dela je bil poiskati
učinkovit algoritem za iskanje predslik 2D CA. Na podlagi izkušenj z 1D CA
sem optimistično pričakoval, da bo možno problem rešiti v linearnem času.

Algoritem v linearnem času bi vsako celico obravnaval le enkrat;
na splošno bi bilo število obravnav majhna konstanta (4-krat,
če se izvaja procesiranje skozi mrežo predslik v 4 smereh/prehodih).
Tak algoritem predpostavlja, da je možno celoten nabor začetnih
robnih pogojev upoštevati hkrati v enem samem prehodu.
V koraku \textbf{2} pri procesiranju vrstice (slika \ref{algorithm_line})
bi se izločilo le ploskve, ki ne ustrezajo nobenemu od začetnih robnih pogojev.
Po nekaj poizkusih sem ugotovil, da tak algoritem ne deluje pravilno.
Vsaj nekatere poti iz nabora je potrebno upoštevati ločeno.

V podanem primeru (slika \ref{algorithm_issue}) se prvi dve vrstici zaključita z
naborom dveh končnih poti \textbf{0110} in \textbf{1111}. Če bi ti dve poti
uporabili hkrati, kakor začetni robni pogoj za naslednjo vrstico, bi dobili
enak rezultat, kakor če bi bili del robnega pogoja tudi poti \textbf{0111} in \textbf{1110}.
To pa zato, ker algoritem, ki poti ne obravnava ločeno, ne more vedeti,
kje se je pot začela, da bi jo lahko tudi pravilno zaključil.
Posledično lahko linearen algoritem vzame začetek ene od poti in ga
na vozlišču, skupnem obema potema, nadaljuje po drugi poti.
Iz mreže je razvidno, da ti dve poti nista preseka neke zvezne ploskve.
Skratka, hkratno obravnavanje celotnega nabora robnih pogojev ni možno,
kar pomeni, da je število obravnav neke celice odvisno od števila poti
in posledično od eksponenta števila celic v vrstici.

Možno je, da obstajajo drugačne optimizacije algoritma, ki lahko zmanjšajo procesno kompleksnost.

\begin{figure}[htb]
\centerline{\psfig{figure=algorithm_issue,width=14cm}}
\caption[Ovira za procesiranje z linearno zahtevnostjo.]
{Ovira za procesiranje z linearno zahtevnostjo.
Veljavni robni pogoj je odebeljen, neveljavni pa črtkan.}
\label{algorithm_issue}
\end{figure}




\chapter{Pregled obstoječih algoritmov in implementacij}
\label{pregled}

Obstoječi algoritmi za predslike 2D CA se osredotočajo izključno na GoL.
Največ algoritmov je namenjenih iskanju stanj GoE,
tako da le-ti zgolj preverjajo obstoj predslik in jih ne štejejo ali izpisujejo.
Naslednja skupina algoritmov sicer izpisuje predslike,
ampak tega ne počne sistematično,
saj je njihov cilje poiskati le eno ali nekaj predslik.
Algoritmi, ki so namenjeni dejanskemu štetju in izpisu vseh predslik so redki.
Zelo redki so tudi akademski prispevki,
kjer bi bil kak algoritem povezan s predslikami 2D CA tudi strokovno opisan.

\section{Iskanje stanj GoE za GoL}

Conway je leta 1970 predstavil CA po imenu \emph{Game of Life},
ki je kmalu začel nabirati navdušence.
Del teh je zanimalo, če v GoL obstajajo stanja brez predslik imenovana \emph{Garden of Eden}.
Nekateri so se lotili raziskovanja in Martin Gardner je obstoj GoE stanj dokazal teoretično \cite{WikiGoE}.
Spet drugi so se lotili iskanja takega stanja.
Že leta 1971 sta Roger Banks in Steve Ward
predstavila prvo stanje GoE velikosti \(9 \times 33\) celic.
Odkritje je bilo objavljeno v \cite{Lifeline3}. Kasneje je Don Woods
\cite{Lifeline3, Lifeline4} s pomočjo računalnika dokazal, da je stanje res GoE.

Woodsov algoritem deluje po principu sestopanja (glej dodatek \ref{woods}). Polje celic razdeli v vrstice.
Začne z eno vogalno celico, katere nabor predslik je kar nabor okolic,
ki se preslikajo v stanje celice. V naslednjem koraku opazuje sosednjo celico v vrstici.
Za vse kombinacije okolic dodane celice in obstoječi nabor predslik preveri,
če se ujemajo, kjer se okolice prekrivajo. Če se ujemajo, doda sestavljeno predsliko v nabor,
sicer predslika izpade iz nabora. Ko pride algoritem do konca vrstice, nadaljuje v naslednji vrstici,
le da je sedaj prekrivanje med naborom predslik in okolico dodane celice drugačno (več sosednjih celic namesto ene).
Tako algoritem nadaljuje do konca celotne konfiguracije.
Če je končni nabor predslik prazen, je opazovana konfiguracija GoE.
Nabor predslik in s tem poraba pomnilnika in procesnega časa ostajajo
relativno majhni v primerjavi z naborom vseh stanj.
Temu je tako, ker imajo v praksi tudi deli konfiguracije GoE malo predslik.
Algoritem bi bil za konfiguracije z dosti predslikami veliko bolj pomnilniško in časovno potraten.

Nicolay Beluchenko je poiskal večje število stanj GoE velikosti \(11 \times 11\) \cite{FoE}.
Vsaj v enem primeru je uporabljal podoben algoritem kakor Woods \cite{oeis.org/A196447}.
Začel je z osrednjo celico in dodajal nove celice v spirali okoli osrednje.
Za vrednost dodane celice je uporabil tisto, ki je dala manjši nabor predslik.
Algoritem zaključi, ko z novo dodano celico ni več možno tvoriti predslik.

Leta 1974 je Duparc \cite{Duparc1972, Duparc1974} razvil drugačen algoritem,
ter z njim poiskal stanja GoE velikosti \(6 \times 122\) in \(6 \times 117\).
Algoritem uporablja teorijo končnih avtomatov in regularnih jezikov, ki je v
osnovi namenjena 1D sistemom.
Duparc je celice iz vrstice 2D polja združil v simbole regularnega jezika,
zaporedje več vrstic pa predstavlja besedo.
Duparcov algoritem ne obravnava vseh stanj vrstice enakovredno,
temveč se osredotoča na vrstice, ki zmanjšujejo nabor predslik.
Obravnavanje vseh stanj vrstic bi namreč preseglo pomnilniške sposobnosti
takratne in sedanje strojne opreme že za kratke vrstice.
Dokaže le, da za vrstice dolžine 1 ne obstaja stolpec, ki bi bil stanje GoE.
Originalni članek je v francoščini, tako da lahko algoritem opišem le na podlagi tega,
kako ga opisujejo drugi \cite{WikiGoE, Bickford2012}.

V zadnjih letih podoben algoritem uporablja Steven Eker (CSL, SRI International, California, USA) \cite{achim-orphan}.
Dokazal je, da za pravokotne konfiguracije višine 2 in 3 ne obstajajo stanja GoE.
Dokaz za konfiguracije višine 4 z danim algoritmom še vedno presega sposobnosti sodobne strojne opreme.
Število stanj avtomata, ki opisuje jezik GoE, namreč raste eksponentno z višino.
Elker je poiskal stanja GoE velikosti \(9 \times 11\), \(8 \times 12\) in \(5 \times 83\).
Na žalost raziskovalcu delodajalec prepoveduje objavo rezultatov in podrobnosti, dokler ni opravljen interni pregled.
Tako imamo za sedaj na voljo le zgoraj navedene podatke.

Drugačen algoritem uporablja Marijn Heule \cite{Hartman2013}.
S sodelavci je zapisal vsa prekrivanja za določeno stanje v obliki binarnih enačb.
Te je nato predal orodju za reševanje problemov SAT.
Če rešitev ne obstaja, pomeni, da je stanje GoE.
Uporabljena je dodatna predpostavka, da bo rešitev zrcalno simetrična v obeh dimenzijah,
kar občutno zmanjša velikost problema.
Algoritem je še dodatno optimiziran za iskanje stanj GoE in
omogoča pregled večjega števila podobnih stanj.
Ob spremembi vrednosti ene same celice omogoča uporabo delnih rezultatov prejšnjega izračuna.

\section{Nesistematično iskanje predslik GoL}

Erlan \cite{Erlan2012} je predstavil igro, pri kateri se za dano stanje
GoL išče predslike. To dejansko ni implementacija algoritma za iskanje predslik,
je pa vzpodbudil druge k iskanju takega algoritma.

Spletna stran \url{kaggle.com} je pripravila tekmovanje \cite{kaggle2013},
kjer so morali kandidati reševati problem iskanja predslik.
Podali so nabor stanj, za katere je treba poiskati predslike več korakov v preteklost.
Podali so tudi nabor učnih sekvenc.
Pričakovali so rešitev, ki temelji na strojnem učenju ali optimizaciji,
torej fokus ni bil na eksaktni rešitvi.
Cilj tudi nikakor ni bil prešteti ali izpisati vse predslike,
temveč so se morali kandidati le čim bolj približati učni sekvenci.

Pri iskanju implementacij algoritma, sem našel Atabot \cite{Borah2013},
Celični kronometer \cite{Duxbury2013} in program, baziran na metodi SAT \cite{Pigorsch2015}.
Cilj teh algoritmov sicer je iskanje predslik, ampak iskanje ni sistematično
in cilj ni nabor vseh možnih predslik.
Algoritmi se tudi poslužujejo določene hevristike pri iskanju.

Našel sem še aplikacijo, napisano v jeziku APL \cite{ionreq2013}.
Iz navedenega primera je razvidno, da je aplikacija sposobna izpisovati predslike.
Avtorja mi ni uspelo kontaktirati, tako da ne morem podati več podrobnosti.

\section{Sistematični algoritmi za štetje in izpis predslik}

Našel sem le eno aplikacijo, imenovano \emph{RetroGUI}, ki je namenjena štetju in izpisu vseh predslik \cite{Bickford2012}.
Neil Bickford prav tako kakor ostali procesira konfiguracijo
po vrsticah, znotraj vrstice pa lahko uporablja različne algoritme (Woods, Duparc).
Bickford opiše tudi algoritem, ki namesto procesiranja po vrsticah združuje predslike
kvadratnih podsklopov konfiguracij. Na žalost poda primerjavo med različnimi algoritmi
le kakor procesni čas za posamezno implementacijo, ne pa tudi bolj splošne
ocene maksimalne in povprečne procesne/pomnilniške zahtevnosti.



\chapter{Sklepne ugotovitve}
\label{sklep}

\section{Dokazovanje}

Magistrska naloga je bolj skopa z dokazi.
Za 1D CA sem uporabljal neposredno dokaze iz teorije grafov \cite{JerasDobnikar2007},
pri 2D CA pa mreža predslik ni običajen graf,
tako da dokazovanje s teorijo grafov ni tako preprosto.
Verjetno pa je možno pretvoriti dani graf v dualno obliko s transformacijo zvezda-trikot.
Če obstaja dualna oblika grafa, kjer ni ploskev, temveč samo vozlišča in povezave,
bi jo lahko uporabili za izpeljavo in dokazovanje dejanske računske kompleksnosti problema.

Nekajkrat sem preveril rezultate, ki jih daje implementacija algoritma.
Za dano vhodno stanje sem vsako predsliko s tranzicijsko funkcijo
pretvoril nazaj v sedanjost in rezultat primerjal z vhodnim stanjem.
Preveril sem še, če so vse naštete predslike enolične.
Za nekaj manjših primerov, sem tudi poiskal predslike z metodo surove sile.
Na ta način nisem našel nobene napake v algoritmu.

Nazadnje sem še primerjal rezultate s programom RetroGUI \cite{Bickford2012}
in ugotovil, da se ujemajo.

\section{Doprinos}

Večina znanih algoritmov (naprimer Woods) uporablja metodo sestopanja.
Izkažejo se, če je predslik relativno malo (naprimer iskanje GoE).
So pa neprimerni za situacije, ko je predslik relativno veliko,
ker hranijo vse predslike v pomnilniku ves čas izvajanja.
Morda bi bilo možno optimizirati porabo pomnilnika,
tako da bi algoritem hranil le tekoče razlike med predslikami, namesto da jih hrani v celoti.

Glavni doprinos magistrske naloge je aplikacija
naprednih algoritmov razvitih za 1D CA na 2D problem.
Tukaj opisan algoritem za štetje predslik ima predvidljivo porabo pomnilnika,
ki je asimptotično manjša od porabe pomnilnika pri sestopanju \(O(C^{N_x N_y})\) (podajam brez dokaza).
Algoritem za izpis predslik je striktno ločen od štetja in
ima linearno zahtevnost v odvisnosti od števila predslik, kar je optimalno.

Grafična upodobitev mreža predslik omogoča boljše razumevanje problema predslik
in lahko olajša dokumentiranje algoritmov.
Obtežena mreža predslik tudi nakazuje,
prostorsko razporeditev izgube informacije.

Na zadnje, je opisani algoritem zamišljen univerzalno, za poljuben 2D CA,
čeprav univerzalnost v praksi ni ravno pomembna,
saj izven raziskovalcev GoL ni dosti zanimanja za teoretične probleme,
kakor je iskanje predslik.

\section{Zanimivi tematsko povezani problemi}

Probleme, povezane z iskanjem predslik, lahko delimo v nivoje glede na zahtevnost:
\begin{enumerate}[noitemsep,nolistsep]
\item Določitev, ali obstajajo predslike za dano trenutno stanje sistema.
\item Štetje predslik za dano trenutno stanje sistema.
\item Naštevanje konfiguracij predslik.
\item Vprašanje reverzibilnosti sistema.
\item Jezik vseh stanj GoE.
\end{enumerate}

V magistrskem delu opišem algoritem, ki rešuje prve tri probleme.
Preostala problema sta si sorodna.
Problem reverzibilnosti je na splošno dokazano nerešljiv \cite{Kari1989}.
Problem jezika stanj GoE je za 1D preprosto rešljiv, za 2D pa je
verjetno podobno kakor vprašanje reverzibilnosti nerešljiv.

\subsection{Analiza 2D celičnih avtomatov s pomočjo končnih avtomatov}

Problem jezika stanj brez predslik bi potreboval teorijo 2D formalnega jezika, ki še ne obstaja.
Kljub temu je možno zastaviti probleme, ki se jih da preslikati v končni avtomat.
Na primer, če obravnavamo vrstice kakor simbole jezika, lahko sestavimo končni avtomat.
Simboli (stanja vrstic) definirajo prehode med stanji končnega avtomata. Stanja avtomata pa
so vsi možni nabori robov vrstice. Pomembna je le prisotnost roba, ne pa tudi utež.
Poln nabor vsebuje vse možne robove, prazen nabor pa ne vsebuje nobenega roba.
Vsako zaporedje vrstic (simbolov), ki v avtomatu pelje iz polnega v prazno stanje, je konfiguracija GoE.
Zanke v takem avtomatu pa so sorodne delcem.

Opisani pristop postane nepraktičen že za kratke vrstice.
Število vseh možnih robov raste eksponentno z dolžino vrstice \(N_x\).
To število, \(|S|^{(M_y-1)(M_x-1+N_x)}\), je enako številu vseh načinov,
na katere se lahko okolici dveh vrstic prekrivata.
Stanja avtomata pa so vsi možni nabori robov.
Nabor lahko opišemo kakor binarni niz, kjer vsak bit pomeni
prisotnost ali odsotnost enega od robov.
Vseh stanj končnega avtomata je tako \(2^{ |S|^{(M_y-1)(M_x-1+N_x)} }\).
Število stanj avtomata postane neobvladljivo že za kratke vrstice.

Najkrajša beseda GoE znotraj regularnega jezika stanj GoE je tista,
ki po najkrajši poti in brez zank pripelje iz polnega v prazen nabor.
Pri 1D CA se je izkazalo, da je dolžina najkrajše besede GoE povezana s kompleksnostjo
prostorsko-časovnih vzorcev, ki se pojavljajo pri danem pravilu.
Podobno so verjetno tudi pri 2D CA konfiguracije GoE večje pri pravilih,
ki omogočajo kompleksno dinamiko delcev. Verjetno bi bilo možno to izkoristiti
za iskanje zanimivih pravil v okolici quad.

\subsection{Izboljšave podanega algoritma}

Implementacijo algoritma je možno izboljšati, tako da zahtevnost
ne raste tako hitro z velikostjo problema.
Za sedaj vidim samo rešitev, ki se osredotoča na povprečno zahtevnost, namesto na maksimalno zahtevnost.
Na primer, sedaj algoritem rezervira pomnilnik za uteži vseh možnih robov,
dovolj pa bi bilo, če bi bil rezerviran pomnilnik samo za robove z utežjo večjo od nič.
Sploh pri iskanju stanj GoE je robov malo v primerjavi z vsemi možnimi.
Tak pristop bi dal dosti manjšo porabo pomnilnika
in verjetno tudi znižal čas procesiranja.

Morda bi bilo možno vnaprej določiti zgornjo mejo števila ne-ničelnih robov.
To bi omogočalo zgodnjo oceno, če je izračun za dan problem izvedljiv.
Na primer, če bi v vrstičnem procesiranju obravnavali vse začetne robove hkrati,
namesto vsakega posebej, bi dobili prevelik nabor končnih robov.
Tak nabor bi vedno vseboval vse pravilne končne robove in še nekaj napačnih.
Ampak skupno število bi bilo lahko občutno manjše od polnega nabora.
To število bi lahko uporabili za oceno porabe pomnilnika in časa.
Na ta način bi bilo možno reševati probleme, ki so na meji tega,
kar zmore sodobna strojna oprema.

Samo implementacijo algoritma je tudi možno optimizirati.
Univerzalnost algoritma, predvsem univerzalnost velikosti okolice,
prispeva dosti režijskih stroškov. Če bi bil algoritem specializiran
samo za quad ali GoL, bi se lahko izognil precej operacijam.
Podobno velja za nabor stanj celice. Za binarne CA je možno optimizirati
operacije, ki pretvarjajo 2D nize celic v cela števila in obratno.
Binarne podatke je možno kompaktno pakirati v pomnilnik.
Mogoče je tudi uporabiti logične operacije nad celo besedo celic,
namesto procesiranja vsake celice posebej.

Procesiranje v algoritmu poteka v gnezdenih zankah in v znanem vrstnem redu.
Le manjši del dostopov do pomnilnika je naključen.
Zaporednost podatkov že sama po sebi omogoča dobro optimizacijo dostopa do predpomnilnika,
tako da na tem področju ni dosti očitnih optimizacij.




%********************************************

\appendix

\chapter{De Bruijnov diagram za GoL}
\label{GoLmatrika}

Slika \ref{network_single_moore} prikazuje del De Bruijnovega diagrama za GoL.
Graf s 16 vozlišči in 64 povezavami je očitno preveč kompleksen, da bi bil primeren za razlago algoritma.
Število vseh možnih okolic (ploskev v diagramu) pa je celo 512.

\begin{figure}[htb]
\centerline{\psfig{figure=network_single_moore,width=13cm}}
\caption[Mreža ene celice za GoL.]{Mreža ene celice za binarni CA z Moorovo okolico \(M_x=M_y=3\).}
\label{network_single_moore}
\end{figure}




\chapter{Primer delovanja algoritma za CA z okolico quad}
\label{primer}

V naslednjem primeru je prikazano štetje in iskanje predslik
za binarni CA (celica ima lahko \(2\) stanji) z okolico velikosti \(2 \times 2\)
in pravilom številka \verb|0x725A|.

Majhna konfiguracija velikosti \(2 \times 2\) je shranjena v datoteki \verb|test_2x2.cas|.
Uporabil bi večjo konfiguracijo, a na žalost ne poznam pravila,
ki bi za večjo konfiguracijo dal majhno število predslik.

Uporabljen je program \cite{Jeras2016-algirithm} z verzijo \verb|v1|.

\begin{Verbatim}[fontsize=\footnotesize]
$ ./ca2d_preimages 2 2 2 0x725a 2 2 test_2x2.cas
CA parameters:
  sts  : 2
  ngb  : siz={2,2}, a=4, n=16
  ovl-y: siz={1,2}, a=2, n=4
  ovl-x: siz={2,1}, a=2, n=4
  rem-y: siz={1,2}, a=2, n=4
  rem-x: siz={2,1}, a=2, n=4
  ver  : siz={1,1}, a=1, n=2
  shf-y: siz={1,1}, a=1, n=2
  shf-x: siz={1,1}, a=1, n=2

RULE = 0x725a
  tab [0] = [[0,0],[0,0]] = 0
  tab [1] = [[1,0],[0,0]] = 1
  tab [2] = [[0,1],[0,0]] = 0
  tab [3] = [[1,1],[0,0]] = 1
  tab [4] = [[0,0],[1,0]] = 1
  tab [5] = [[1,0],[1,0]] = 0
  tab [6] = [[0,1],[1,0]] = 1
  tab [7] = [[1,1],[1,0]] = 0
  tab [8] = [[0,0],[0,1]] = 0
  tab [9] = [[1,0],[0,1]] = 1
  tab [A] = [[0,1],[0,1]] = 0
  tab [B] = [[1,1],[0,1]] = 0
  tab [C] = [[0,0],[1,1]] = 1
  tab [D] = [[1,0],[1,1]] = 1
  tab [E] = [[0,1],[1,1]] = 1
  tab [F] = [[1,1],[1,1]] = 0

CA configuration siz [y↓,x→] = [2,2]:
 1 0
 0 1

NETWORK: edge weights from forward/backward direction,
         summed preimages
net [dy=0][y=0] = [1 1 1 1 1 1 1 1 ]
net [dy=0][y=1] = [2 2 0 2 3 3 0 1 ]
net [dy=0][y=2] = [0 3 5 0 0 2 7 2 ]  cnt [0] = 19
net [dy=1][y=0] = [0 4 4 0 0 4 5 2 ]  cnt [1] = 19
net [dy=1][y=1] = [2 0 3 4 2 0 1 1 ]
net [dy=1][y=2] = [1 1 1 1 1 1 1 1 ]

preimage i=0:  CA configuration siz [y↓,x→] = [3,3]:
 1 0 0
 0 0 0
 0 1 0

preimage i=1:  CA configuration siz [y↓,x→] = [3,3]:
 1 0 0
 0 0 0
 0 1 1

preimage i=2:  CA configuration siz [y↓,x→] = [3,3]:
 1 0 0
 0 0 1
 0 1 0

preimage i=3:  CA configuration siz [y↓,x→] = [3,3]:
 1 0 0
 0 0 1
 0 1 1

preimage i=4:  CA configuration siz [y↓,x→] = [3,3]:
 0 1 0
 1 1 0
 1 0 0

preimage i=5:  CA configuration siz [y↓,x→] = [3,3]:
 0 1 0
 1 1 0
 1 0 1

preimage i=6:  CA configuration siz [y↓,x→] = [3,3]:
 0 1 0
 1 1 0
 0 1 1

preimage i=7:  CA configuration siz [y↓,x→] = [3,3]:
 0 1 0
 1 1 0
 1 1 1

preimage i=8:  CA configuration siz [y↓,x→] = [3,3]:
 1 0 1
 0 0 0
 0 1 0

preimage i=9:  CA configuration siz [y↓,x→] = [3,3]:
 1 0 1
 0 0 0
 0 1 1

preimage i=10:  CA configuration siz [y↓,x→] = [3,3]:
 1 0 1
 0 0 1
 0 1 0

preimage i=11:  CA configuration siz [y↓,x→] = [3,3]:
 1 0 1
 0 0 1
 0 1 1

preimage i=12:  CA configuration siz [y↓,x→] = [3,3]:
 0 1 1
 1 1 0
 1 0 0

preimage i=13:  CA configuration siz [y↓,x→] = [3,3]:
 0 1 1
 1 1 0
 1 0 1

preimage i=14:  CA configuration siz [y↓,x→] = [3,3]:
 0 1 1
 1 1 0
 0 1 1

preimage i=15:  CA configuration siz [y↓,x→] = [3,3]:
 0 1 1
 1 1 0
 1 1 1

preimage i=16:  CA configuration siz [y↓,x→] = [3,3]:
 0 1 1
 1 1 1
 1 0 0

preimage i=17:  CA configuration siz [y↓,x→] = [3,3]:
 1 1 1
 0 0 1
 0 1 0

preimage i=18:  CA configuration siz [y↓,x→] = [3,3]:
 1 1 1
 0 0 1
 0 1 1
\end{Verbatim}




%********************************************

\chapter{Opis algoritma Dona Woodsa}
\label{woods}

Prilagam pisno izmenjavo z avtorjem \footnote{Don Woods /url{http://www.icynic.com/~don/}} prvega algoritma za iskanje predslik GoL.

\begin{Verbatim}[fontsize=\footnotesize]

Don Woods <don@icynic.com>	Thu, Jul 28, 2016 at 11:45 PM
To: iztok.jeras@gmail.com
> Dear Mr. Woods,
>
> I am developing an algorithm for computing preimages of 2D CA. It is based
> on the latest research for computig preimages of 1D CA.
> I am using the 2x2 quad neighborhood in the examples instead of the 3x3
> neighborhood used in Life.
> https://github.com/jeras/fri-magisterij (work in progress and Slovene
> language)
> https://github.com/jeras/preimages-2D (not working yet)
>
> As part of my masters thesis I have to compare my algorithm to existing
> ones.
> You are known as the first person to prove a pattern to be a Garden of Eden
> orphan in the Game of Life.
> Could you send me some references to this proof? I was looking for an
> article to reference, but a generic description (preferably written by you)
> or source code would be as good.
>
> Regards,
> Iztok Jeras
>

Oof, it's been quite a while; let me see what I can remember.

The "proof" was programmatic, i.e. I wrote a program to compute
predecessors to a given position, and the program claimed there were no
predecessors to the particular position that someone had theorised was
a Garden of Eden.  I did not have a formal proof of correctness for the
program.  (I was a teenager when I wrote it!)  I don't think I still
have the source code anywhere, I'm afraid.  (I might have a paper
printout of it somewhere but don't have time to search right now.)

The program worked by considering each cell in turn and looking at all
possible 3x3 predecessors that would produce the given state.  It then
looked at the next cell to the right, looking for 3x3 predecessors that
were consistent with the 6 overlapping cells from the other, etc.  (In
practice, the 3x3 neighborhoods were indexed so that I could quickly
find which of the 8 possible righthand extensions worked.)  When it had
a 3x(N+2) predecessor for the top row of N, it continued at the left of
the next row, then across that row, etc.  Obviously in those later rows
there was only one new predecessor cell being introduced for each new
current cell after the leftmost, so the combinatoric explosion was not
excessive, particularly since the GoE pattern by design did not have
many potential predecessors even for subsections.  I also deliberately
oriented the target pattern with the short dimension going across, so
that I more quickly reached the point of extending the predecessor one
cell at a time in later rows.

My program normally included a 1-wide border around the area being
backtracked, to ensure there were no artifacts introduced, but for the
GoE proof I restricted it to the non-empty rectangular boundary, which
I think was 9 by 33?  Thus, as I think was mentioned at the time, what
I actually demonstrated was a stronger result: there was no predecessor
that led to a state that included the GoE as a 9x33 subsection.

I hope that helps.  Let me know if you have further questions.

        -- Don Woods

Don Woods <don@icynic.com>	Tue, Aug 16, 2016 at 6:42 PM
To: iztok.jeras@gmail.com
> I found the time to read your response just now.
>
> Your description of the algorithm confirms what I imagined based on third
> party descriptions.
> Your details regarding combinatorial explosion which affects memory
> consumption and processing time were extra helpful.
>
> May I cite this email in my master thesis, since there are no other direct
> sources I would know of?
>
> Regards,
> Iztok Jeras

Permission granted.  Good luck with your thesis!

        -- Don Woods
\end{Verbatim}




%********************************************

\chapter{Izvorna koda implementacije algoritma}
\label{koda}

Prilagam izvorno kodo, ki se sicer nahaja na naslovu:\\
\url{https://github.com/jeras/preimages-2D}

Zanimivi sta predvsem funkciji \verb|ca1d_net| in \verb|ca2d_net|
ki se nahajata proti koncu datoteke: \\
\verb|preimages–2D/ca2d_net.c|
\vspace{10mm}

\lstset{ %
%  backgroundcolor=\color{white},   % choose the background color; you must add \usepackage{color} or \usepackage{xcolor}
  basicstyle=\tiny,          % the size of the fonts that are used for the code
  breakatwhitespace=false,         % sets if automatic breaks should only happen at whitespace
  breaklines=true,                 % sets automatic line breaking
%  captionpos=b,                    % sets the caption-position to bottom
%  commentstyle=\color{mygreen},    % comment style
%  deletekeywords={...},            % if you want to delete keywords from the given language
  %escapeinside={\%*}{*)},          % if you want to add LaTeX within your code
%  extendedchars=true,              % lets you use non-ASCII characters; for 8-bits encodings only, does not work with UTF-8
  frame=single,	                   % adds a frame around the code
  keepspaces=true,                 % keeps spaces in text, useful for keeping indentation of code (possibly needs columns=flexible)
%  keywordstyle=\color{blue},       % keyword style
  language=C,                      % the language of the code
%  otherkeywords={*,...},           % if you want to add more keywords to the set
  numbers=none,                    % where to put the line-numbers; possible values are (none, left, right)
  numbersep=5pt,                   % how far the line-numbers are from the code
%  numberstyle=\tiny\color{mygray}, % the style that is used for the line-numbers
%  rulecolor=\color{black},         % if not set, the frame-color may be changed on line-breaks within not-black text (e.g. comments (green here))
%  showspaces=false,                % show spaces everywhere adding particular underscores; it overrides 'showstringspaces'
%  showstringspaces=false,          % underline spaces within strings only
%  showtabs=false,                  % show tabs within strings adding particular underscores
%  stepnumber=2,                    % the step between two line-numbers. If it's 1, each line will be numbered
%  stringstyle=\color{mymauve},     % string literal style
  tabsize=4,	                   % sets default tabsize to 2 spaces
  title=\lstname                   % show the filename of files included with \lstinputlisting; also try caption instead of title
}

\lstinputlisting[language=C, firstline=30]{preimages-2D/ca2d.h}
\lstinputlisting[language=C, firstline=30]{preimages-2D/ca2d.c}
\lstinputlisting[language=C, firstline=30]{preimages-2D/ca2d_array.h}
\lstinputlisting[language=C, firstline=30]{preimages-2D/ca2d_array.c}
\lstinputlisting[language=C, firstline=30]{preimages-2D/ca2d_base.c}
\lstinputlisting[language=C, firstline=30]{preimages-2D/ca2d_cfg.h}
\lstinputlisting[language=C, firstline=30]{preimages-2D/ca2d_cfg.c}
\lstinputlisting[language=C, firstline=30]{preimages-2D/ca2d_rule.h}
\lstinputlisting[language=C, firstline=30]{preimages-2D/ca2d_rule.c}
\lstinputlisting[language=C, firstline=30]{preimages-2D/ca2d_fwd.h}
\lstinputlisting[language=C, firstline=30]{preimages-2D/ca2d_fwd.c}
\lstinputlisting[language=C, firstline=30]{preimages-2D/ca2d_net.h}
\lstinputlisting[language=C, firstline=30]{preimages-2D/ca2d_net.c}


%********************************************

%\addcontentsline{toc}{chapter}{\protect Dodatki}

\newpage
\addcontentsline{toc}{chapter}{Seznam slik}
\addtocontents{toc}{\protect\vspace{-2ex}}
\listoffigures

%\newpage
%\addcontentsline{toc}{chapter}{Seznam tabel}
%\listoftables

%\listofalgorithms

%********************************************

\newpage

\bibliographystyle{slplainurl}
%\bibliographystyle{apsrevSLO}
\addcontentsline{toc}{chapter}{Literatura}
\label{stran_literatura}
\bibliography{magisterij} 

%\printbibliography

\end{document}