\documentstyle[12pt]{article}

\begin{document}




\newcommand{\lek}{lek\'{e}pez\'{e}s}
\newcommand{\xN}{1,2,\dots, N}
\newcommand{\xU}{\bigcup_{i=1}^N F_i}
\newcommand{\xu}{\cup_{i=1}^N F_i}
\newcommand{\Fi}{\{F_i; \;\; i=\xN \}}
\newcommand{\Fix}{F_{\sigma_1}\circ\dots\circ F_{\sigma_n}}
\newcommand{\k} {k=1,2,\dots}
\newcommand{\rs} {r_{\sigma_1}\dots r_{\sigma_n}}
\newcommand{\Fsb} {F_{\sigma_1}\circ\dots\circ F_{\sigma_k}({\cal B})}
\newcommand{\Fsa} {F_{\sigma_1}\circ\dots\circ F_{\sigma_k}({\cal A})}
\newcommand{\Fsh} {F_{\sigma_1}\circ\dots\circ F_{\sigma_k}({\cal H})}
\newcommand{\Fsx} {F_{\sigma_1}\circ\dots\circ F_{\sigma_n}(x)}
\newcommand{\Fsy} {F_{\sigma_1}\circ\dots\circ F_{\sigma_n}(y)}
\newcommand{\Fsxk} {F_{\sigma_1}\circ\dots\circ F_{\sigma_k}(x)}
\newcommand{\FA} {F_i({\cal A})}
\newcommand{\si}{\sigma_1\sigma_2\dots\sigma_k\dots}
\newcommand{\ski}{\sigma_1\sigma_2\dots\sigma_k}
\newcommand{\FsK} {F_{\sigma_1}\circ\dots\circ F_{\sigma_n}({\cal A})}
\newcommand{\MW}{(MW)-rendszer}
\newcommand{\Fsi} {F_{\sigma_1}\circ\dots\circ F_{\sigma_i}(x)}
\newcommand{\sni}{\sigma_1\sigma_2\dots\sigma_n}
\newcommand{\oki}{\omega_1\omega_2\dots\omega_k}
\newcommand{\Fs} {F_{\sigma_1}\circ\dots\circ F_{\sigma_k}}


{\sf\LARGE III. \ \ K\'{O}DOK, GR\'{A}FOK \'{E}S FRAKT\'{A}LOK.}\\
\\  

Ha egy IFS $\cal A$ invari\'{a}ns halmaz\'{a}t digitaliz\'{a}ljuk, vagyis az $\cal A$ k\"{u}l\"{o}nb\"{o}z\H{o} r\'{e}szeihez
egy-egy jelsorozatot rendel\"{u}nk, akkor azt mondjuk, hogy k\'{o}doljuk az $\cal A$ invari\'{a}ns halmazt.
A k\'{o}dol\'{a}ssal megk\"{o}nny\'{\i}tj\"{u}k az $\cal A$ \'{e}rdekes r\'{e}szeinek a kiemel\'{e}s\'{e}t \'{e}s ford\'{\i}tva, lehet\H{o}v\'{e} v\'{a}lik
 k\'{o}doknak
(jelsorozatoknak) k\'{e}pi megjelen\'{\i}t\'{e}se. Ilyen a YU algoritmus a sz\'{a}m\'{\i}t\'{o}g\'{e}pes alkalmaz\'{a}sban,
 a n\'{e}gyzeth\'{a}l\'{o}s modell a "Frakt\'{a}ldimnzi\'{o}kr\'{o}l egyszer\H{u}en" c. anyagban a boxdimenzi\'{o} bevezet\'{e}s\'{e}re \'{e}s a 
 {\large 12.3}-ben sorra ker\"{u}l\H{o} DNS l\'{a}nccal ir\'{a}ny\'{\i}tott k\'{a}oszj\'{a}t\'{e}k. 
A k\'{o}dol\'{a}ssal kapcsolatos elj\'{a}r\'{a}sokat r\'{e}szben  gr\'{a}fok ir\'{a}ny\'{\i}tj\'{a}k.
\vspace{30mm}\\

\\
{\bf\Large Az $\cal A$ invari\'{a}ns halmaz k\'{o}dol\'{a}sa }\\
\vspace{5mm}
\\
{\bf\Large 12.1}\\
\\
{\Large\bf A k\'{o}dol\'{a}si elj\'{a}r\'{a}s}\\

Amikor kapcsolatot teremt\"{u}nk az $\cal A$ r\'{e}szhalmazai \'{e}s jelsorozatok k\"{o}z\"{o}tt, akkor $\cal A$ {\sf k\'{o}dol\'{a}s\'{a}t}
 v\'{e}gezz\"{u}k el.

 {\sf K\'{o}dnak} fogunk nevezni egy {\em v\'{e}gtelen} jelsorozatot. A jeleket {\sf bet\H{u}knek} {\em is} nevezz\"{u}k. V\'{e}ges hosszus\'{a}gu, 
(n-elem\"{u})
 jelsorozatot  (n-hossz\'{u}s\'{a}g\'{u}) {\sf sz\'{o}nak} vagy {\sf n-blokk}nak nevez\"{u}nk. Egy k\'{o}d els\H{o} $k$ jel\'{e}b\H{o}l 
(bet\H{u}j\'{e}b\H{o}l) alkotott sz\'{o} a k\'{o}d ($k$ hossz\'{u}) {\sf prefixe}. Az el\H{o}fordul\'{o} jelek halmaz\'{a}t {\sf ABC-nek} nevezz\"{u}k. 
Mivel a jelek alakja \'{e}rdektelen  sz\'{a}munkra, ez\'{e}rt egy $N$ jelb\H{o}l \'{a}ll\'{o} ABC bet\H{u}it 
a  \ $0,1,\dots ,N-1$ \  sz\'{a}mokkal fogjuk jel\"{o}lni.

Az elmondottak alapj\'{a}n  egy N-jel\"{u} ABC-b\H{o}l k\'{e}sz\"{u}lt n-blokkot ($n$ hossz\'{u} sz\'{o}t) igy
irunk fel a  matematika nyelv\'{e}n 
$$\sigma_1 \sigma_2 \dots \sigma_n ; \;\;  \;\; \sigma_i \in \{0,1,\dots,N-1\}. \leqno{(12.1)}$$

M\'{e}g egy fogalom amit haszn\'{a}lni fogunk: Legyen $\sum_N$ az $N$-jel\H{u} ABC-b\H{o}l alkotott szavak halmaza. 
Az $L\subseteq\sum_N$ halmazt, vagyis a $\sum_N$ valamely r\'{e}szhalmaz\'{a}t {\sf (form\'{a}lis) nyelvnek} nevezz\"{u}k.\\

Egy IFS $\cal A$ invari\'{a}ns halmaz\'{a}nak a szok\'{a}sos k\'{o}dol\'{a}sa arra \'{e}p\"{u}l, hogy 
$\cal A$ felbonthat\'{o} olyan vele hasonl\'{o} (affin) halmazok uni\'{o}j\'{a}ra, amelyek \'{a}tm\'{e}r\H{o}je tetsz\H{o}legesen 
kicsi {\em is} lehet. A {\large 6.fejezetben} t\'{a}rgyaltuk ezt  \'{e}s ott \'{u}gy fejezt\"{u}k ki ezt a 
tulajdons\'{a}got  hogy $\cal A$ hat\'{a}rtalanul nagyithat\'{o}. A k\'{o}dol\'{a}ssal mintegy folytatjuk az $\cal A$ halmaznak
a {\large 6.fejezetben} elkezdett vizsg\'{a}lat\'{a}t.
 
{\em A k\'{o}dol\'{a}s a k\"{o}vetkez\H{o}k\'{e}ppen t\"{o}rt\'{e}nik}.  Az $1,2,\dots ,N$ jelekhez hozz\'{a}rendelj\"{u}k az
$\{\FA ; \; i=\xN \}$ halmazokat, a 2 hossz\'{u} $ij$ szavakhoz  az $F_i\circ F_j({\cal A})$ halmazokat rendelj\"{u}k hozz\'{a},
 ahol  $i,j\in \{1,2,\dots ,N\}$. Hasonl\'{o} m\'{o}don rendelj\"{u}k hozz\'{a} a 3 hossz\'{u} szavakhoz az $\Fi$ h\'{a}rmas kompozici\'{o}it
 s.i.t. Pontosabban:\\

{\em Az $1,2,\dots ,N$ bet\H{u}kb\H{o}l alkotott (12.1) szavak mindegyik\'{e}hez hozz\'{a}rendel\"{u}nk egy $\cal A$-val hasonl\'{o}
 (affin) r\'{e}szhalmazt a k\"{o}vetkez\H{o}k\'{e}ppen}
$$\ski\rightarrow\Fsa \;\; \;\; \sigma_i\in \{1,2,\dots ,N\} . \leqno{(K)}$$
\\
{\large\bf P\'{e}ld\'{a}k.} \   A Sierpinski h\'{a}romsz\"{o}g egy ilyen k\'{o}dol\'{a}s\'{a}t a {\em 6.1  \'{a}bra}  mutatja be, a 
{\em 12.1  \'{a}br\'{a}n} pedig
egy m\'{a}sik \"{o}nhasonl\'{o} halmaz, a "csill\'{a}r" k\'{o}dol\'{a}s\'{a}t mutatjuk be. \"{O}naffin halmaz 
k\'{o}dol\'{a}s\'{a}ra p\'{e}lda a "fa" ({\em 12.2 \'{a}bra}).  Hosszabb szavakhoz egyre kisebb \'{a}tm\'{e}r\H{o}j\H{u} 
halmazok tartoznak. Vegy\"{u}k \'{e}szre, hogy a 
k\"{u}l\"{o}nb\"{o}z\H{o} szavakhoz tartoz\'{o} r\'{e}szhalmazok  v\'{a}ltozatosabbak a csup\'{a}n \"{o}naffin "fa" eset\'{e}ben,
 mint az  \"{o}nhasonl\'{o} Sierpinski h\'{a}romsz\"{o}g \'{e}s a csill\'{a}r k\'{o}dol\'{a}s\'{a}n\'{a}l.\\
 
Szavak helyett k\'{o}dokat ({\em  v\'{e}gtelen jelsorozatokat}) haszn\'{a}lva, a (K) \lek  \ kiterjeszt\'{e}s\'{e}vel,
{\sf az $\cal A$ pontjait is k\'{o}dolhatjuk}:
$$\sigma_1\sigma_2\dots\sigma_k\dots\rightarrow \bigcap_k \{\Fsa ; \; \k \} .\leqno{(12.2)}$$
A $\sigma_1\sigma_2\dots\sigma_k\dots$ k\'{o}dhoz ({\em  v\'{e}gtelen} jelsorozathoz) ezzel egyetlen pontot rendel\"{u}nk hozz\'{a}, mivel
$$F_{\sigma_1}\circ\dots\circ F_{\sigma_k}\circ F_{\sigma_{k+1}}({\cal A})\subset F_{\sigma_1}\circ\dots\circ F_{\sigma_k}({\cal A})
 \; \;\;\; \k $$
\'{e}s a kompakt $\{ \Fsa ; \; \;\;\; \k \}$ halmazok \'{a}tm\'{e}r\H{o}i a null\'{a}hoz tartanak $k\rightarrow\infty$ eset\'{e}n,
ahogyan azt a {\large 6.2}-ben \'{e}s  {\large 6.4}-ben megmutattuk.\\

A k\'{o}dol\'{a}shoz sz\"{u}ks\'{e}g van $\cal A$ ismeret\'{e}re. Ennek hi\'{a}ny\'{a}ban csak az $\Fsb $ halmazokat k\'{o}dolhatjuk, amikor
 ${\cal B}\supset{\cal A}$ \  \'{e}s $h[{\cal B}, \; {\cal A}]$ lehet\H{o}leg kicsi. Ekkor  $\Fsb $  is nagyobb mint $\Fsa $, az
elt\'{e}r\'{e}s\"{u}k viszont, a kompozici\'{o} n\"{o}vel\'{e}s\'{e}vel egyre kisebb lesz.

Vegy\"{u}k \'{e}szre, hogy az $\cal A$ {\sf pontjainak k\'{o}dol\'{a}sa minden  ${\cal B}\neq {\cal A}$ mellett is pontos!} Ugyanis
$$h[\Fsb \;\; \Fsa ]\leq r_{\sigma_1}r_{\sigma_2}\dots r_{\sigma_k} h[{\cal A}, {\cal B}]\leq \leqno{(12.3)}$$
$$r_{\sigma_1}r_{\sigma_2}\dots r_{\sigma_k} \mid{\cal B}\bigcup{\cal A}\mid $$
ahol  $\mid{\cal B}\bigcup{\cal A}\mid$ a  ${\cal B}\bigcup{\cal A}$ \'{a}tm\'{e}r\H{o}je \'{e}s   $r_{\sigma_1}r_{\sigma_2}\dots r_{\sigma_k}\rightarrow 0$.

A (12.3) alapj\'{a}n, az $\cal A$ hely\'{e}be {\em b\'{a}rmely} $\cal B$ halmazt helyettesitve a (11.2)-be, ugyanazt a pontot kapjuk.\\

 \'{I}gy, az $\{\xN\}$ ABC minden szav\'{a}hoz, a k\'{o}dol\'{a}s az $\cal A$-val hasonl\'{o} (affin) r\'{e}szhalmazt 
rendel hozz\'{a} \'{e}s az 
$\{\xN\}$ ABC-b\H{o}l alkotott minden v\'{e}gtelen $\si $ jelsorozathoz
(vagyis egy N-jel\H{u} k\'{o}dhoz), a k\'{o}dol\'{a}s az $\cal A$ egy-egy  $x(\sigma)$ pontj\'{a}t rendeli ($\sigma=\si $).

{\sf Vegy\"{u}k \'{e}szre,} hogy az $\cal A$ {\em pontjainak} \'{e}s az $\cal A$ {\em r\'{e}szhalmazainak} k\'{o}dol\'{a}sa k\"{o}z\"{o}tt
 a k\"{o}vetkez\H{o} 
nyilv\'{a}nval\'{o} kapcsolat van: Az $\cal A$-nak az $\ski$ sz\'{o}val k\'{o}dolt r\'{e}szhalmaza mindazon pontokb\'{o}l \'{a}ll, amelyek
 k\'{o}dj\'{a}nak $\ski$ a prefixe.\\
\\  \\
{\LARGE\bf **}\\
 Mikor 1-1 ez a \lek ?\\
\\
{\large\bf T\'{e}tel.} {\large I.}Ha 
$$F_i({\cal A})\cap F_j({\cal A})\neq\emptyset \;\; \;\; i\neq j.$$
akkor $\sigma\rightarrow x(\sigma)$ NEM 1-1.\\
 {\large II.} Ha az  $\Fi$ valamelyike NEM invert\'{a}lhat\'{o}, akkor $\sigma\rightarrow x(\sigma)$ NEM 1-1.\\
 {\large III.}Ha
$$F_i({\cal A})\cap F_j({\cal A})=\emptyset \;\; \;\; i\neq j.$$
\'{e}s $\Fi$ invert\'{a}lhat\'{o}k, akkor $\sigma\rightarrow x(\sigma)$ 1-1.\\
\\
{\large\bf Bizonyit\'{a}s.}  {\large I.} Ha $x\in F_i({\cal A})\cap F_j({\cal A})$ akkor $x$-nek van egy $i$ kezdet\H{u} \'{e}s egy $j$ kezdet\H{u}
 k\'{o}dja. Igy k\'{e}t k\"{u}l\"{o}nb\"{o}z\H{o} k\'{o}dhoz ugyanaz az $x$ tartozik.\\
 {\large II.} Ha $x\neq y$ \'{e}s $F_i(x)=F_i(y)$ akkor az
$$i\xi_1\xi_2\dots \;\; \;\; \'{e}s \;\; \;\; i\eta_1\eta_2\dots$$
k\'{e}t k\"{u}l\"{o}nb\"{o}z\H{o} k\'{o}dhoz ugyanaz a pont tartozik.\\
 {\large III.}  Legyen  $\Fi$ mindegyike invert\'{a}lhat\'{o}, $F_i({\cal A})\cap F_j({\cal A})$ \"{u}res minden $ i\neq j$ p\'{a}rra  \'{e}s
 $\sigma\neq\omega$. 

Legyen $k$ az els\H{o}  olyan index amelyre $\sigma_k\neq\omega_k$. Ekkor
$$ {F_{\sigma_k}\circ F_{\sigma_{k+1}}\circ\dots\circ F_{\sigma_n}({\cal A})\bigcap F_{\omega_k}\circ F_{\omega_{k+1}}\circ\dots
\circ F_{\omega_n}({\cal A})\subseteq $$
$$\subseteq F_{\sigma_k}({\cal A})\cap F_{\omega_k}({\cal A})=\emptyset.\leqno{(12.4)} $$
Az {\large F.2.8} megold\'{a}sak\'{e}nt meg\'{a}llapitottuk, hogy 
$$F({\cal B})\bigcap F({\cal C})= F({\cal B}\bigcap{\cal C})$$
b\'{a}rmely  ${\cal B}, {\cal C}$ p\'{a}rra,{\em pontosan akkor} ha $F$ 1-1. Ennek alapj\'{a}n, ha $n>k$ akkor
$$F_{\sigma_1}\circ F_{\sigma_2}\circ\dots\circ F_{\sigma_n}({\cal A})\bigcap F_{\omega_1}\circ F_{\omega_2}\circ\dots\circ
 F_{\omega_n}({\cal A})= \leqno{(12.5)}$$
$$F_{\sigma_1}\circ\dots\circ F_{\sigma_{k-1}}(F_{\sigma_k}\circ \dots\circ F_{\sigma_n}({\cal A}))\bigcap 
F_{\sigma_1}\circ\dots\circ F_{\sigma_{k-1}}( F_{\omega_k}\circ F_{\omega_{k+1}}\circ\dots\circ F_{\omega_n}({\cal A}))=$$
$$ F_{\sigma_1}\circ\dots\circ F_{\sigma_{k-1}}(F_{\sigma_k}\circ F_{\sigma_{k+1}}\circ\dots\circ F_{\sigma_n}({\cal A})
\bigcap F_{\omega_k}\circ F_{\omega_{k+1}}\circ\dots\circ F_{\omega_n}({\cal A})). $$
A (12.4) \'{e}s (12.5) \"{o}sszevet\'{e}s\'{e}b\H{o}l
$$F_{\sigma_1}\circ F_{\sigma_2}\circ\dots\circ F_{\sigma_n}({\cal A})\bigcap F_{\omega_1}\circ F_{\omega_2}\circ\dots\circ
 F_{\omega_n}({\cal A})=\emptyset.$$
vagyis minden $n>k$-ra $F_{\sigma_1}\circ F_{\sigma_2}\circ\dots\circ F_{\sigma_n}({\cal A})$ \'{e}s $F_{\omega_1}\circ F_{\omega_2}\circ\dots\circ
 F_{\omega_n}({\cal A})$ diszjunkt halmazok, amib\H{o}l "m\'{a}r b\H{o}ven" k\"{o}vetkezik, hogy az $\omega$ \'{e}s a $\sigma$
k\'{o}dokhoz k\"{u}l\"{o}nb\"{o}z\H{o} pontok tartoznak.\\
{\LARGE\bf **}\\

{\Large 12.2}\\
\\
{\large\bf Az $\cal A$ \'{e}rdekes r\'{e}szeinek kiemel\'{e}se. A parci\'{a}lis IFS.}\\

Az $\cal A$ k\'{o}dol\'{a}s\'{a}val minden
$$\sigma =\sigma_1 \sigma_2 \dots \sigma_n \dots  \;\;  \;\; \sigma_i \in \{0,1,\dots,N-1\}$$
jelsorozathoz tartozik az $\cal A$ halmaznak egy pontja. \'{I}gy,  ha bizonyos k\'{o}dokat "letiltunk" ebb\H{o}l a \lek b\H{o}l 
akkor az $\cal A$ k\"{u}l\"{o}nb\"{o}z\H{o} r\'{e}szhalmazait kaphatjuk. Ennek egy szok\'{a}sos m\'{o}dja, hogy megadunk szavakat \'{e}s mindazon 
pontokat t\"{o}r\"{o}lj\"{u}k az $\cal A$ halmazb\'{o}l, amelyek olyan k\'{o}doknak a k\'{e}pei, amelyek  tartalmazz\'{a}k ezeket a szavakat.\\
\\
{\large P\'{e}ld\'{a}k.} \ {\Large 1.} A Sierpinski h\'{a}romsz\"{o}gb\H{o}l  t\"{o}r\"{o}lj\"{u}k mindazokat a pontokat, 
amelyek k\'{o}dj\'{a}ban az $12$ sz\'{o} el\H{o}fordul. Ekkor mindazon kompozici\'{o}l\'{a}ncok t\"{o}rl\"{o}dnek, amelyekben $F_1\circ F_2$
el\H{o}fordul. A megmaradt l\'{a}ncokhoz tartoz\'{o} pontok halmaz\'{a}t a {\em 12.3a \'{a}br\'{a}n} l\'{a}thatjuk. Hasonl\'{o}
 m\'{o}don kapjuk a  {\em 12.3b \'{a}br\'{a}t}  a $22$ sz\'{o}t
tartalmaz\'{o} l\'{a}ncok t\"{o}rl\'{e}s\'{e}vel. A Sierpinski h\'{a}romsz\"{o}g {\em 12.3c \'{a}br\'{a}n} bemutatott r\'{e}szhalmaz\'{a}t akkor
kapjuk meg, ha   mindazokat a pontokat t\"{o}r\"{o}lj\"{u}k, amelyek k\'{o}dj\'{a}ban  {\em a $12$ vagy $22$ sz\'{o}} el\H{o}fordul.\\
\\
{\Large 2.} Ha a Sierpinski h\'{a}romsz\"{o}get a {\large 2.4 \ 2} p\'{e}ld\'{a}ban el\H{o}\'{a}llit\'{o} f\"{u}ggv\'{e}nyrendszerhez 
(IFS-hez) hozz\'{a}vessz\"{u}k az
$$F_3(x)= \left( \begin{array}{cc} 0.5 & 0 \\ 0 & 0.5 \end{array}\right) \left(\begin{array} {c} x_1 \\ x_2 \end{array}\right) + 
  \left(\begin{array} {c} 0.5 \\ 0.5 \end{array}\right). $$
f\"{u}ggv\'{e}nyt, akkor az igy kapott IFS $\cal A$ invari\'{a}ns halmaza a z\'{a}rt egys\'{e}gn\'{e}gyzet.\\ 

Ennek igazol\'{a}sa igen egyszer\H{u}. K\"{o}zvetlen\"{u}l bel\'{a}that\'{o}, hogy az egys\'{e}gn\'{e}gyzet invari\'{a}ns a $W=\cup_{i=1}^4 F_i$ \lek re
 ({\em 12.4 \'{a}bra}) \'{e}s az {\large 5.fejezetben} igazoltuk, hogy pontosan egy invari\'{a}ns halmaza van minden IFS-nek.\\

 Ennek az egys\'{e}gn\'{e}gyzetnek k\'{o}dol\'{a}s\'{a}t  mutatjuk
a {\em 12.5 \'{a}br\'{a}n}.  A $0, 1, 2, 3$ bet\H{u}kh\"{o}z tartoz\'{o} n\'{e}gyzetek 
  $$F_0({\cal A}), F_1({\cal A}), F_2({\cal A}), F_3({\cal A}).$$
   A {\12.5B \'{a}br\'{a}n} az $\cal A$-nak a  2 hossz\'{u} $ij$ szavakhoz tartoz\'{o}
$$F_i\circ F_j({\cal A}); \;\; i,j=1,2,3,4$$
  r\'{e}szhalmazait  l\'{a}thatjuk.
 
  A {12.5C \'{a}bra} azt mutatja,
hogyan kapjuk a  2 hossz\'{u} szavakhoz tartoz\'{o} r\'{e}szhalmazokb\'{o}l a 3 hossz\'{u} szavakhoz tartoz\'{o} r\'{e}szeket.
Ahogyan az \'{a}br\'{a}b\'{o}l is leolvashat\'{o}, a k\'{o}dol\'{a}st legegyszer\"{u}bben rekurziv m\'{o}don adhatjuk meg. Ha a  2 hossz\'{u}
 szavakkal m\'{a}r k\'{o}doltuk az $\cal A$ r\'{e}szhalmazait,
akkor a 3 hossz\'{u} szavaknak a k\"{o}vetkez\H{o} n\'{e}gyzetlapok felelnek meg: az $ij$-vel k\'{o}dolt n\'{e}gyzetet
 line\'{a}risan felezz\"{u}k \'{e}s az igy kapott n\'{e}gy uj n\'{e}gyzetlap rendre az $ij0, ij1, ij2, ij3$ k\'{o}dot kapja a cs\'{u}csokhoz \'{\i}rt
 jeleknek megfelel\H{o}en  (a {\em 12.5C  \'{a}br\'{a}n} $ij=21$).
 
  Pontosabban\\
\\
{\bf n=1} A n\'{e}gyzetlapot line\'{a}risan felezz\"{u}k \'{e}s 
az \'{\i}gy kapott n\'{e}gy n\'{e}gyzetlap k\'{o}djai a cs\'{u}csokhoz irt bet\H{u}k lesznek.\\
{\bf n}$\rightarrow$ {\bf n+1} \  az $n$ hossz\'{u} szavakkal k\'{o}dolt n\'{e}gyzeteket line\'{a}risan felezz\"{u}k \'{e}s 
az igy kapott n\'{e}gy uj n\'{e}gyzetlap k\'{o}djait \'{u}gy kapjuk, hogy  az $n$ hossz\'{u} szavakhoz hozz\'{a}f\H{u}zz\"{u}k
a megfelel\H{o} cs\'{u}csokhoz irt bet\H{u}ket.\\

  A {\em 12.6-9 \'{a}br\'{a}kon} bemutatott frakt\'{a}lhalmazok a n\'{e}gyzetlapb\'{o}l
alakultak \'{u}gy, hogy t\"{o}r\"{o}lt\"{u}k azokat a l\'{a}ncokat, amelyek az \'{a}bra mell\'{e} irt szavakat tartalmazz\'{a}k.

{\sf Vegy\"{u}k \'{e}szre,} hogy ez a n\'{e}gy f\"{u}ggv\'{e}nyb\H{o}l \'{a}ll\'{o} IFS azonos a "Frakt\'{a}ldimenzi\'{o}kr\'{o}l egyszer\H{u}en"
c. anyag n\'{e}gyzeth\'{a}l\'{o}s szerkeszt\'{e}s\'{e}vel.\\
\\  \\
{\large\bf Az \'{a}ltal\'{a}nos konstrukci\'{o}.}\\ 

 "Tiltott szavak" megad\'{a}s\'{a}val, ilym\'{o}don {\em b\'{a}rmely IFS $\cal A$ invari\'{a}ns halmaz\'{a}b\'{o}l},  kiemelhet\"{u}nk  sz\'{a}munkra
 \'{e}rdekes
 r\'{e}szhalmazokat. {\em A kiemel\'{e}s technik\'{a}ja \'{e}s elm\'{e}lete minden IFS-n\'{e}l l\'{e}nyeg\'{e}ben ugyanaz.}  Ez\'{e}rt
 {\sf csup\'{a}n a {\large\rm 2. p\'{e}lda} eset\'{e}re fogjuk \'{a}ll\'{\i}t\'{a}sainkat illusztr\'{a}lni, amikor $\cal A$ az egys\'{e}gn\'{e}gyzet.}\\

Elj\'{a}r\'{a}sunk eredm\'{e}nye a  parci\'{a}lis IFS. Pontosabban:

  Kiv\'{a}lasztunk  az  $1,2,\dots ,N$  ABC-b\H{o}l alkotott szavakat. Ezek lesznek a tiltott szavak.
A kiv\'{a}lasztott  szavak mindegyik\'{e}hez  hozz\'{a}rendel\"{u}nk egy 
$\Fi$ f\"{u}ggv\'{e}nyrendszer (IFS) elemeib\H{o}l alkotott kompozici\'{o}t a k\"{o}vetkez\H{o}k\'{e}ppen
$$\ski\rightarrow\Fs \;\; \;\; \sigma_i\in \{1,2,\dots ,N\} . \leqno{(K^*)}$$
Ekkor  mindazoknak a kompozici\'{o}l\'{a}ncoknak a halmaz\'{a}t, amelyek a  kiv\'{a}lasztott  szavak $(K^*)$ k\'{e}peit 
(vagyis a tiltott szavak $(K^*)$ k\'{e}peit)  NEM tartalmazz\'{a}k, }{\sf parci\'{a}lis IFS-nek}
{\em (parci\'{a}lis iter\'{a}lt f\"{u}ggv\'{e}nyrendszernek)} nevezz\"{u}k.  A parci\'{a}lis IFS-hez a (12.2) m\'{o}don hozz\'{a}rendelt
 pontok halmaz\'{a}t, a parci\'{a}lis IFS  {\em attraktor\'{a}nak} nevezz\"{u}k.
 ({\em partitioned IFS})\\
\\  \\
{\Large 12.3}\\
\\
{\bf\Large Elj\'{a}r\'{a}s parci\'{a}lis IFS  attraktor\'{a}nak el\H{o}\'{a}ll\'{\i}t\'{a}s\'{a}ra.}\\
   
El\H{o}sz\"{o}r egyetlen tiltott sz\'{o}val megadott parci\'{a}lis IFS  attraktor\'{a}nak a szerkeszt\'{e}s\'{e}t mutatjuk meg. Legyen ez a sz\'{o}  \ $\ski $ \ \'{e}s
$${\cal K}_0=\Fsa .$$
${\cal K}_0$ mindazoknak a pontoknak a halmaza amelyek k\'{o}dja a $\ski $  tiltott sz\'{o}val kezd\H{o}dik. 
$$W({\cal K}_0)=\cup_{i=0}^N F_i({\cal K}_0)$$ 
mindazon pontok halmaza amelyek k\'{o}dj\'{a}ban a m\'{a}sodik helyt\H{o}l a $\ski $ sz\'{o} \'{a}ll, 
$W^{[i]}({\cal K}_0)$  mindazon pontok halmaza amelyek k\'{o}dj\'{a}ban a $i+1$-edik helyt\H{o}l \'{a}ll $\ski $. Igy az $\cal A$-nak
 a r\'{e}szhalmaza, amely pontjainak k\'{o}dj\'{a}ban  {\em valahol szerepel} a $\ski $ sz\'{o} 
$${\cal M}=\bigcup_{i=0}^\infty W^{[i]}({\cal K}_0)\leqno{(12.6)}$$
ahol $W^{[0]}({\cal K}_0)={\cal K}_0$.

A $\ski $  tiltott sz\'{o}hoz tartoz\'{o} parci\'{a}lis IFS attraktora (invari\'{a}ns halmaza)
$${\cal A}-{\cal M}$$
vagyis az $\cal A$ mindazon pontjai,  amelyek NEM tartoznak $\cal M$-be.

T\"{o}bb tiltott sz\'{o}hoz tartoz\'{o} $\cal M$, az egyes szavak $\cal M$ halmazainak az uni\'{o}ja (egyes\'{\i}t\'{e}se).\\
\\

{\em Abban az  esetben,  amikor $\cal A$ az egys\'{e}gn\'{e}gyzet} ( {\large 12.2 2.} p\'{e}lda), a k\"{o}vetkez\H{o} geometriai szerkeszt\'{e}ssel
tudjuk az $\cal M$  halmazt el\H{o}\'{a}ll\'{\i}tani.

 ${\cal K}_0$: azon  $0.5^k$ \'{e}l\H{u} n\'{e}gyzetlap, amely a {\em 12.5 \'{a}bra} szerint  a $\ski $ sz\'{o}hoz tartozik.

A $W({\cal K}_0)$  halmazt \'{u}gy kapjuk, hogy $i=0,1,2,3$ \'{e}rt\'{e}kekre vessz\"{u}k a $P\in{\cal K}_0$  pontok \'{e}s az $i$ cs\'{u}cs felez\H{o}pontj\'{a}t, 
majd az \'{\i}gy kapott n\'{e}gy n\'{e}gyzetet egyes\'{\i}tj\"{u}k.

Az algoritmus els\H{o} l\'{e}p\'{e}se, hogy ilym\'{o}don  megadjuk a ${\cal K}_0\cup W({\cal K}_0)$  halmazt.\\ 
\\
Ezut\'{a}n rekurziv m\'{o}don folytatjuk:\\ 
{\sf $n+1$. l\'{e}p\'{e}s.} Az $n.$ l\'{e}p\'{e}sben kapott ${\cal H}_n$  halmaz pontjaira alkalmazzuk az el\H{o}z\H{o} szerkeszt\'{e}st.
 $i=0,1,2,3$ \'{e}rt\'{e}kekre vessz\"{u}k a $P\in{\cal H}_n$  pontok \'{e}s az $i$ cs\'{u}cs felez\H{o}pontj\'{a}t, 
majd az \'{\i}gy kapott n\'{e}gy halmazt egyes\'{\i}tj\"{u}k.

Az  algoritmus $n+1$. l\'{e}p\'{e}se, hogy ilym\'{o}don  megadjuk a ${\cal K}_0\cup W({\cal K}_0)$  halmazt.\\

Az elj\'{a}r\'{a}s a k\"{o}vetkez\H{o} egyszer\H{u} \'{e}szrev\'{e}telen alapul:\\
{\large\bf  T\'{e}tel.}  \ Legyen $F_i  \;  (i=0,1,2,3)$ a  {\large 13.1 2.} p\'{e}lda f\"{u}ggv\'{e}nyrendszere \'{e}s $P$ az $\cal A$ n\'{e}gyzet egy pontja. Ekkor
 $F _i(P)$ a $P$ \'{e}s az $i$ cs\'{u}cs felez\H{o}pontja.\\
 {\bf Bizony\'{\i}t\'{a}s.} Az $F_3(x)$ \'{\i}gy is \'{\i}rhat\'{o}
$$\left( \begin{array}{cc} 0.5 & 0 \\ 0 & 0.5 \end{array}\right)  \left(\left(\begin{array} {c} x_1 \\ x_2 \end{array}\right) +  
 \left(\begin{array} {c} 1 \\ 1 \end{array}\right)\right) $$
\'{e}s ez \'{e}ppen a $P(x_1, x_2)$ \'{e}s $P(1,1)$ felez\H{o}pontja.

 Nyilv\'{a}n hasonl\'{oan} indokolhat\'{o} az $i=0,1,2$ eset.\\
\\
{\large\bf  P\'{e}ld\'{a}k.} \  Az {\em 12.11 \'{a}br\'{a}n} a (12.6)-re vezet\H{o} elj\'{a}r\'{a}st l\'{a}tjuk, amikor
  a tiltott sz\'{o} a $20$. A {\em 12.12 \'{a}br\'{a}n} pedig  t\"{o}bb tiltott sz\'{o}hoz 
tartoz\'{o} elj\'{a}r\'{a}s folyamat\'{a}t mutatjuk. \\
\\  \\
{\Large 13.1}\\

{\large\bf A k\'{a}oszj\'{a}t\'{e}k}.\\

  Tekints\"{u}k a 
$(0, 0), (0, 1), (1, 0)$ h\'{a}romsz\"{o}get 
\'{e}s benne egy $P_0$ pontot. K\"{o}ss\"{u}k \"{o}ssze a $P_0$ pontot a 
h\'{a}romsz\"{o}g valamely v\'{e}letlenszer\H{u}en
v\'{a}lasztott cs\'{u}cspontj\'{a}val \'{e}s tekints\"{u}k a kapott egyenesszakasz 
felez\H{o}pontj\'{a}t.  Ez legyen $P_1$. Megism\'{e}telve ugyanezt a
szerkeszt\'{e}st az $P_1$ pontb\'{o}l ki\'{\i}ndulva, a kapott felez\H{o}pont 
legyen $P_2$ s.i.t. Pontosabban\\

$n=0,1,\dots$ {\em -ra, a $P_{n+1}$ pont az $[i, P_n]$ egyenesszakasz felez\H{o}pontja},} ahol $i$  a 
h\'{a}romsz\"{o}g valamely  cs\'{u}cspontja. A cs\'{u}cspontokhoz rendelj\"{u}k hozz\'{a} a $\{p_i; \;\; i=1,2,3\}$ 
val\'{o}sz\'{\i}n\H{u}s\'{e}geket ($p_1+p_2+p_3=1$).  Ekkor minden l\'{e}p\'{e}sn\'{e}l $p_i$ val\'{o}sz\'{\i}n\H{u}s\'{e}ggel v\'{a}lasztjuk
az $i$-edik cs\'{u}csot.( Ez \'{a}rnyal\'{a}st {\em is} ad a kialakul\'{o} Sierpinski h\'{a}romsz\"{o}gnek.)\\

Ez az  algoritmus, amit {\sf k\'{a}oszj\'{a}t\'{e}knak} nevez\"{u}nk,  a Sierpinski h\'{a}romsz\"{o}g pontjait \'{a}llitja el\H{o}. Ennek
 igazol\'{a}sa a k\"{o}vetkez\H{o}: 

Legyen $F_i(P)$ az a \lek  \  amely a $P$ ponthoz hozz\'{a}rendeli az $[i, P] \;\; (i=0.1,2)$  egyenesszakasz felez\H{o}pontj\'{a}t.
Ekkor $F_i \;\; (i=0,1,2)$ az $\cal S$ Sierpinski h\'{a}romsz\"{o}get el\H{o}\'{a}ll\'{\i}t\'{o} IFS f\"{u}ggv\'{e}nyei.

Ugyanis legyenek a h\'{a}romsz\"{o}g cs\'{u}cspontjai $(0,0), (1,0)$ \'{e}s $(0,1)$. Ekkor az $F_2$ m\'{a}trix alakja
$$\left( \begin{array}{cc} 0.5 & 0 \\ 0 & 0.5 \end{array}\right)  \left(\left(\begin{array} {c} x_1 \\ x_2 \end{array}\right) + 
  \left(\begin{array} {c} 0 \\ 1 \end{array}\right)\right). $$

  Ez\'{e}rt  $P_0\in {\cal S}$ eset\'{e}n,  a {\sf k\'{a}oszj\'{a}t\'{e}kkal}  kapott 
$$ F_{\sigma_1}(P_0), \;\; F_{\sigma_2}\circ F_{\sigma_1}(P_0), \;\;\dots ,  \;\;  F_{\sigma_n}\circ\dots\circ F_{\sigma_1}(P_0)\dots \;\; \;\; \sigma_i\in\{0,1,2\}$$
 az $\cal S$ Sierpinski h\'{a}romsz\"{o}g pontjai.   Ha $P_0\notin{\cal S}$, akkor az
 els\H{o} 7-8 elemt\H{o}l eltekintve, a sorozat elemei olyan k\"{o}zel vannak az $\cal S$ Sierpinski h\'{a}romsz\"{o}gh\"{o}z,
hogy nem tudjuk \H{o}ket megk\"{u}l\"{o}nb\"{o}ztetni az $\cal S$ pontjait\'{o}l  (F.13.1).\\
\\
{\large\bf P\'{e}lda.} Ha a v\'{e}letlenszer\H{u}en kiv\'{a}lasztott jelsorozat $12021101\dots$ akkor az algoritmus eredm\'{e}nye az
$$F_1(P_0), \;\; \;\; F_2\circ F_1(P_0),\;\; \;\;  F_0\circ  F_2\circ F_1(P_0),\;\; \;\; \dots ,  \;\; \;\;,
 F_1\circ F_0\circ F_1\circ F_1\circ F_2\circ F_0\circ  F_2\circ F_1(P_0)\dots \leqno{(13.1)}$$
pontsorozat ({\em 13.1 \'{a}bra}). 

Az \'{a}br\'{a}n a megfelel\H{o} pontok {\em k\'{o}djait} jel\"{o}lt\"{u}k.

Ha $P_0\in{\cal S}$, akkor (13.1) az   ${\cal S}$ Sierpinski h\'{a}romsz\"{o}g pontjai.
Figyelj\"{u}k meg, hogy {\em  m\'{a}r az els\H{o} n\'{e}h\'{a}ny l\'{e}p\'{e}sn\'{e}l},  a $F_i({\cal S}) \;\; (i=0,1,2)$ {\em mindegyik\'{e}be} jut
 pont a sorozatb\'{o}l.\\  

 A {\em 13.2 \'{a}br\'{a}kon}  egyre hosszabb l\'{a}ncokra kapott ponthalmazokat mutatunk meg. B\'{a}rmilyen messze is
megy\"{u}nk a k\'{a}oszj\'{a}t\'{e}k pontsorozat\'{a}ban, az $F_i({\cal A}) \;\; (i=0,1,2)$  mindegyik\'{e}ben keletkezhetnek ujabb
pontok. \'{U}gy l\'{a}tjuk, hogy a k\'{a}oszj\'{a}t\'{e}kkal nyert sorozat pontjai hamar sz\'{e}tsz\'{o}r\'{o}dnak a Sierpinski
h\'{a}romsz\"{o}gben \'{e}s \'{\i}gy  a  k\'{a}oszj\'{a}t\'{e}k egy gyors el\H{o}\'{a}ll\'{\i}t\'{a}s\'{a}t adja a Sierpinski
h\'{a}romsz\"{o}gnek.

A k\'{a}oszj\'{a}t\'{e}kot \'{a}ltal\'{a}nosithatjuk tetsz\H{o}leges IFS-re ({\large F.13.2}).\\
\\  \\
{\Large 13.2}\\

{\large\bf Egy DNS l\'{a}nccal vez\'{e}relt k\'{a}oszj\'{a}t\'{e}k}.\\

Az  \"{o}r\"{o}kl\H{o}d\'{e}si inform\'{a}ci\'{o}k egys\'{e}ges m\'{o}don DNS ({\it DNA}) l\'{a}ncok form\'{a}j\'{a}ban 
vannak t\'{a}rolva az \'{e}l\H{o}l\'{e}nyek sejtjeiben. A DNS n\'{e}gyf\'{e}le nukleinsav ({\it nucleic acid}) nagyon 
hossz\'{u} l\'{a}ncolat\'{a}b\'{o}l \'{a}ll \'{e}s ebben a l\'{a}ncban a nev\"{u}k kezd\H{o}bet\"{u}j\'{e}vel {\sf g, c, a} \'{e}s {\sf t} 
bet\"{u}kkel jel\"{o}lj\"{u}k meg a hely\"{u}ket. ({\em 13.3 \'{a}bra})

 A DNS-ben t\'{a}rolt inform\'{a}ci\'{o}t ezen nukleinsavaknak a sorrendje hat\'{a}rozza meg. Vagyis az, hogy a l\'{a}nc
milyen szavakb\'{o}l \'{a}ll \'{e}s ezek a szavak hol \'{e}s milyen s\H{u}r\H{u}n helyezkednek el a l\'{a}ncban. Ig\'{e}ny van arra, hogy
ezt a nagyon  hossz\'{u} l\'{a}ncot {\em egyetlen pillant\'{a}ssal \'{a}ttekinthet\H{o} k\'{e}pp\'{e}} alakitsuk, ahol 
vizu\'{a}lisan \'{e}s 
szignifik\'{a}ns m\'{o}don jelennek meg a szavak eloszl\'{a}s\'{a}nak jellegzetess\'{e}gei. (Ez az ig\'{e}ny a GENBANKi {\em 13.3 \'{a}br\'{a}ra}
 r\'{a}tekintve nagyon is nyilv\'{a}nval\'{o}.)

A legkisebb egys\'{e}g amelynek m\'{a}r jelent\'{e}se van h\'{a}rombet\H{u}s (ilyen a GAT, CTA). Igy fontos tudni, hogy ezek 
 hi\'{a}nyoznak-e ill. szignifik\'{a}nsan alulreprezent\'{a}ltak-e  a sokmilli\'{o} bet\H{u}b\H{o}l  \'{a}ll\'{o} l\'{a}ncban.  A genetika ezen kutat\'{a}s\'{a}val foglalkoz\'{o}k 
tapasztalata szerint
elegend\H{o}   a DNS l\'{a}ncnak "csak"  n\'{e}h\'{a}ny tizezer bet\H{u}b\H{o}l \'{a}ll\'{o} r\'{e}sz\'{e}t megvizsg\'{a}lni, ha ott alulreprezent\'{a}ltak bizonyos 
jellegzetes szavak, akkor ez a jelens\'{e}g \'{a}ll az eg\'{e}sz l\'{a}ncra is.

A DNS l\'{a}ncok ilyen ir\'{a}ny\'{u} vizsg\'{a}lat\'{a}ra egy gyorsan, glob\'{a}lisan \'{a}ttekinthet\H{o} geometriai modell a {\sf DNS  l\'{a}nccal 
vez\'{e}relt  k\'{a}oszj\'{a}t\'{e}k}, amelynek \"{o}tlete a {\large 13.1}-ben le\'{\i}rt k\'{a}oszj\'{a}t\'{e}kb\'{o}l sz\'{a}rmazik.
 A  DNS  l\'{a}nccal 
vez\'{e}relt  k\'{a}oszj\'{a}t\'{e}k a k\"{o}vetkez\H{o}  ({\em 13.4 \'{a}bra}).

A n\'{e}gyf\'{e}le nukleinsavat a z\'{a}rt egys\'{e}gn\'{e}gyzet n\'{e}gy cs\'{u}csa reprezent\'{a}lja amelyeket ezent\'{u}l {\em az  {\sf a, g, t} \'{e}s
 {\sf c} bet\H{u}k helyett a $0,1,2,3$ szimb\'{o}lumokkal jel\"{o}l\"{u}nk}. A modell  minden 
$$\sigma_1\sigma_2\dots\sigma_n  \;\; \;\;   \;\; \sigma_i\in\{0,1,2,3\}$$
sz\'{o}hoz egy $n$-elem\H{u} $\{P_k; \; k=1,2,\dots ,n\}$ pontsorozatot rendel hozz\'{a} a k\"{o}vetkez\H{o} {\em rekurziv} m\'{o}don:

{\em $P_1$ az  $[\theta ,\sigma_1]$ egyenesszakasz felez\H{o} pontja, ahol  $\theta$ az egys\'{e}gn\'{e}gyzet k\"{o}z\'{e}ppontja.  A
  $$P_k; \; \;  k=2,3,\dots ,n$$
pontok  a  $[P_{k-1} ,\sigma_k]$ egyenesszakaszok felez\H{o} pontjai.}

Haszn\'{a}lni fogjuk a k\"{o}vetkez\H{o} r\'{e}szletesebb jel\"{o}l\'{e}st is
$$P_k=P_{\sigma_1\sigma_2\dots\sigma_k}.$$

Igy minden a $\{0,1,2,3\}$ ABC-vel alkotott $n$ hossz\'{u} sz\'{o}nak megfelel $n$ pont az egys\'{e}gn\'{e}gyzetben. Nagyon
 hossz\'{u} szavakat, a DNS l\'{a}nc tizezres nagys\'{a}grend\H{u} prefixeit igy \'{a}br\'{a}zolva, el\H{o}fordul hogy 
(majdnem) \"{u}res foltok maradnak az egys\'{e}gn\'{e}gyzetben.
 Ebben az esetben "bizonyos szavak" nem, vagy alig fordulnak el\H{o} a  t\"{o}bbt\'{\i}zezres hossz\'{u}s\'{a}g\'{u} l\'{a}ncban. Ekkor \'{e}rdekes ez a reprezent\'{a}ci\'{o}.\\

Vannak olyan 2-8 bet\H{u}b\H{o}l \'{a}ll\'{o} szavak, amelyek a DNS l\'{a}nc olyan szakaszait jel\"{o}lik, amelyekhez olyan enzimek k\"{o}t\H{o}dnek,
amelyek felismerik az idegen DNS-t \'{e}s megakad\'{a}lyozz\'{a}k, hogy be\'{e}p\"{u}lj\"{o}n a l\'{a}ncba. A DNS l\'{a}nc ilyen
szakaszainak (szavainak) a hi\'{a}nya idegen DNS be\'{e}p\"{u}l\'{e}s\'{e}t \'{e}s ezzel idegen virus behatol\'{a}s\'{a}t teszik lehet\H{o}v\'{e}
 a szervezetbe. A DNS l\'{a}nc ilyen funkci\'{o}t bet\"{o}lt\H{o} szakaszainak ({\em recognition site})
ismeret\'{e}re sz\"{u}ks\'{e}g van akkor is, amikor \'{e}ppen a behatol\'{a}s megakad\'{a}lyoz\'{a}s\'{a}t kell 
megakad\'{a}lyozni, p\'{e}ld\'{a}ul  g\'{e}nmanipul\'{a}ci\'{o} eset\'{e}n.  A majdnem \"{u}res foltok ilyen DNS szakaszok 
hi\'{a}ny\'{a}t is jelezik.\\

A  {\em  13.5 \'{a}br\'{a}n} a k\'{a}oszj\'{a}t\'{e}k v\'{e}geredm\'{e}ny\'{e}t l\'{a}tjuk spec. DNS l\'{a}ncok eset\'{e}n. 
A (majdnem) feh\'{e}r foltok DNS szakaszok hi\'{a}ny\'{a}t jelzik \'{e}s a sz\"{u}rke egyre s\"{o}t\'{e}tebb \'{a}rnyalatai a 
ter\"{u}letre t\"{o}m\"{o}r\"{u}lt pontok s\H{u}r\H{u}s\'{e}g\'{e}t (gyakoris\'{a}got) jelzik.  Az  els\H{o}  \'{a}br\'{a}n} a majdnem 
\"{u}res foltok a {\sf ga} hi\'{a}ny\'{a}t jelzik.  Ez  a gerincesek genomj\'{a}ra  jellemz\H{o}.\\

Hogyan lehet  a kapott halmaz \"{u}res foltjaib\'{o}l meghat\'{a}rozni  a
hi\'{a}nyz\'{o} szavakat? 

P\'{e}ld\'{a}ul a {\em 13.6  \'{a}br\'{a}n} l\'{a}that\'{o} szerkeszt\'{e}ssel.  A $k$ hossz\'{u} l\'{a}ncok egy $2^k \times 2^k$ 
n\'{e}gyzetr\'{a}csban foglalnak helyet \'{e}s a k\"{o}vetkez\H{o} rekurziv  m\'{o}don szerkesztj\"{u}k \H{o}ket:

{\sf k=1:}  az ABC bet\H{u}i, $0, 1, 2, 3$,  n\'{e}gy $2^{-1}$ oldal\'{u}  n\'{e}gyzetben foglalnak helyet. 

{\sf k-1 $\rightarrow$ k:}   A $k-1$ hossz\'{u} szavak t\'{a}bl\'{a}zat\'{a}ban line\'{a}risan felez\"{u}nk minden 
n\'{e}gyzetet \'{e}s az igy kapott n\'{e}gy n\'{e}gyzetben a k\"{o}vetkez\H{o} $k$ hossz\'{u} szavak foglalnak majd helyet.
Ha a n\'{e}gyzetben  
$$\sigma_{k-1}\dots\sigma_2\sigma_1  \;\; \;\;   \;\; \sigma_i\in\{0,1,2,3\}$$
volt, akkor a n\'{e}gy \'{u}j n\'{e}gyzethez
$$
\left( \begin{array}{cc} 1 \; \sigma_(k-1)\dots\sigma_2\sigma_1 & 3 \; \sigma_(k-1)\dots\sigma_2\sigma_1 \\
 0 \; \sigma_(k-1)\dots\sigma_2\sigma_1 & 2 \; \sigma_(k-1)\dots\sigma_2\sigma_1 \end{array}\right) $$
$k$ hossz\'{u} szavak tartoznak.  ({\em 13.6 \'{a}bra}  ha $k=1,2,3$).

Ezzel a szerkeszt\'{e}ssel egy $\delta =2^{-n}$ m\'{e}ret\H{u} $\delta$-h\'{a}l\'{o}n elhelyezt\"{u}k az \"{o}sszes $n$-hossz\'{u} sz\'{o}t. Ezt a 
 DNS l\'{a}nc frakt\'{a}lk\'{e}p\'{e}re helyezve kimutathat\'{o}k  azok a {\em legfeljebb} $n$ hossz\'{u}}
 szavak, amelyek hi\'{a}nyoznak illetve alulreprezent\'{a}ltak a l\'{a}ncban \\
\\
MEGJEGYZ\'{E}S.  Egy  DNS  l\'{a}nccal vez\'{e}relt  k\'{a}oszj\'{a}t\'{e}k
a Sierpinski h\'{a}romsz\"{o}gre bemutatott algoritmusnak egy n\'{e}gyzet cs\'{u}csaira \'{e}p\'{\i}tett v\'{a}ltozata abb\'{o}l a c\'{e}lb\'{o}l,
hogy a DNS l\'{a}ncra fontos inform\'{a}ci\'{o}kat nyujthat\'{o} r\'{e}szhalmazokat jel\"{o}lj\"{o}n ki a n\'{e}gyzetlapb\'{o}l.\\ 

{\large\bf  Kapcsolat az $\cal A$ k\'{o}dol\'{a}sa \'{e}s a k\'{a}oszj\'{a}t\'{e}k k\"{o}z\"{o}tt.}\\

A {\em 13.6 \'{a}bra} \'{e}s a {\em 12.5 \'{a}bra} \"{o}sszevet\'{e}se rokons\'{a}got mutat az $\cal A$ k\'{o}dol\'{a}sa \'{e}s a k\'{a}oszj\'{a}t\'{e}k 
k\"{o}z\"{o}tt. Mindk\'{e}t
esetben az $\cal A$ pontjaihoz jelsorozattal jutunk el. A k\'{o}dol\'{a}sn\'{a}l minden $\sigma_1,\sigma_2,\dots ,\sigma_n,\dots$
k\'{o}dhoz egy
$$\{\Fsa ; \; \k \}\leqno{(*)}$$
sorozat tartozik \'{e}s a (*) sorozat a $\sigma_1\sigma_2\dots$ k\'{o}dhoz tartoz\'{o} {\sf ponthoz konverg\'{a}l}.

 A k\'{a}oszj\'{a}t\'{e}kn\'{a}l, {\em egyetlen}
$$F_{\sigma_k}\circ F_{\sigma_2}\circ F_{\sigma_1}(P_0); \;\; k=1,2,\dots \leqno{(**)}$$
sorozat van, amelynek minden elem\'{e}hez  tartozik az $\cal A$-nak pontja ("k\"{o}zel\'{\i}t\H{o}en).   

A (**) \'{a}ltal\'{a}ban NEM konverg\'{a}l  s\H{o}t, azt tapasztaljuk, hogy a  (**) sorozathoz tartoz\'{o} pontok "sz\'{e}tsz\'{o}r\'{o}dnak 
az eg\'{e}sz $\cal A$ invari\'{a}ns halmazon." (Ezt az \'{a}ll\'{\i}t\'{a}st NEM pontos\'{\i}tjuk \'{e}s NEM bizony\'{\i}tjuk.)\\
\\  \\
\\  \\
{\Large 13.3}\\

 {\large\bf Gr\'{a}ffal vez\'{e}relt k\'{a}oszj\'{a}t\'{e}k}\\

A k\'{a}oszj\'{a}t\'{e}k egy gyorsabb elj\'{a}r\'{a}s az IFS invari\'{a}ns halmaz\'{a}nak el\H{o}\'{a}ll\'{\i}t\'{a}s\'{a}ra,  mint az  eredeti,
 IFS modell n\'{e}ven, a {\large 3.} \'{e}s {\large 5.fejezetben} bemutatott elj\'{a}r\'{a}s.  Egy {\em parci\'{a}lis IFS-re}  hogyan alkalmazhatjuk
a k\'{a}oszj\'{a}t\'{e}kot?  Hogyan ker\"{u}lj\"{u}k el a tiltott szavakat tartalmaz\'{o} l\'{a}ncokat?

 A parci\'{a}lis IFS-hez szerkeszt\"{u}nk  egy (ir\'{a}ny\'{\i}tott) gr\'{a}ft, amelynek \'{e}leihez az IFS f\"{u}ggv\'{e}nyeit rendelj\"{u}k.  
 Ezzel  a  deBrujin gr\'{a}f   egyik \'{a}ltal\'{a}nos\'{\i}t\'{a}s\'{a}t kapjuk \'{e}s a parci\'{a}lis IFS kompozici\'{o}l\'{a}ncait ezen {\sf deBrujin tipus\'{u}
   gr\'{a}f  \'{u}tjaival} fogjuk kijel\"{o}lni..\\
\\
A  {\large\sf deBrujin gr\'{a}f}.  A $G(N,n)$  deBrujin gr\'{a}f \'{u}tjaib\'{o}l} leolvashat\'{o} egy N-jel\H{u} ABC-b\H{o}l alkothat\'{o} \"{o}sszes $n$ hossz\'{u} sz\'{o}.   
  A k\"{o}vetkez\H{o}  rekurziv elj\'{a}r\'{a}ssal t\"{o}rt\'{e}nik a  gr\'{a}f szerkeszt\'{e}se. 
  
   A $G(N,2)$ gr\'{a}f  cs\'{u}csait az
ABC bet\H{u}ivel jel\"{o}lj\"{u}k \'{e}s a megfelel\H{o} cs\'{u}csokat \"{o}sszek\"{o}t\H{o} \'{e}lek lesznek a $2$ hossz\'{u} 
szavak. Pontosabban, a gr\'{a}f cs\'{u}csai az $N$-elem\H{u} ABC  bet\H{u}i \'{e}s \'{e}lei az \"{o}sszes $2$ hossz\'{u}s\'{a}g\'{u} szavak.
Ha $i,j$ az ABC k\'{e}t bet\H{u}je, akkor az $(i,j)$ \'{e}lhez az $ij$ sz\'{o} tartozik. Minden cs\'{u}csp'�rhoz pontosan egy \'{e}l tartozik.

\'{I}gy a  $G(N,2)$  megadja egy N-jel\H{u} ABC-b\H{o}l alkothat\'{o}  k\'{e}t bet\H{u}b\H{o}l \'{a}ll\'{o} szavak mindegyik\'{e}t. 

Ha $n>2$ akkor $G(N,n)$ cs\'{u}csai a $N$ jel\H{u} ABC-b\H{o}l alkotott $n-1$ hossz\'{u} szavak \'{e}s a  $G(N,n)$ \'{e}leihez az
$n$ hossz\'{u} szavak tartoznak. Ezeket a k\"{o}vetkez\H{o}k\'{e}ppen szerkesztj\"{u}k:

 ha $\sigma_1\sigma_2\dots\sigma_{n-1}$ \'{e}s  $\omega_1\omega_2\dots\omega_{n-1}$
a $G(N,n)$ k\'{e}t cs\'{u}csa, akkor 
$$(\sigma_1\sigma_2\dots\sigma_{n-1}, \;  \omega_1\omega_2\dots\omega_{n-1})$$
egy \'{e}l pontosan akkor ha
$$\sigma_{k+1}=\omega_k;  \;\;   \;\; k=1,2,\dots ,n-2$$
({\em 13.7 \'{a}bra}).  Ekkor azt mondjuk, hogy a k\'{e}t sz\'{o}, $(\sigma_1\sigma_2\dots\sigma_{n-1}$ \'{e}s   $\omega_1\omega_2\dots\omega_{n-1})$
{\sf progressziven \'{a}tfed\H{o}} \'{e}s a  $(\sigma_1\sigma_2\dots\sigma_{n-1}, \;  \omega_1\omega_2\dots\omega_{n-1})$
 \'{e}lhez tartoz\'{o} sz\'{o}
$$\sigma_1\sigma_2\dots\sigma_{n-1}\omega_{n-1}=\sigma_1\omega_1\omega_2\dots\omega_{n-1}.$$

A {\em 13.8 \'{a}br\'{a}n} l\'{a}that\'{o}k a $G(N,n)$ gr\'{a}fok n\'{e}h\'{a}ny $N,n$ p\'{a}rra.\\
\\
{\LARGE\bf **}\\
{\large\bf T\'{e}tel.} A $G(N,n)$ \'{e}leihez hozz\'{a}rendelt $n$ hossz\'{u} szavak az  N jel\H{u} ABC $n$-hossz\'{u} szavainak
1-1 lek\'{e}pez\'{e}s\'{e}t adj\'{a}k a $G(N,n)$ \'{e}leinek a halmaz\'{a}ra.\\
\\
{\large\bf Bizony\'{\i}t\'{a}s.}  A  $G(N,n)$ szerkeszt\'{e}se minden \'{e}lhez egy\'{e}rtelm\H{u}en hozz\'{a}rendel  egy $n$ hossz\'{u} sz\'{o}t. 
Azt kell m\'{e}g bel\'{a}tni, hogy minden $n$ hossz\'{u} sz\'{o}hoz tartozik \'{e}l. V\'{a}gjuk le a sz\'{o} els\H{o} majd az utols\'{o}
bet\H{u}j\'{e}t. Igy k\'{e}t progressziven \'{a}tfed\H{o} $n-1$ hossz\'{u} sz\'{o}t kapunk. Ezek egy\'{e}rtelm\H{u}en 
meghat\'{a}rozz\'{a}k a  $G(N,n)$ egy \'{e}l\'{e}t.\\
{\LARGE\bf **}\\  
\\
A {\large\sf k\'{a}oszj\'{a}t\'{e}kot vez\'{e}rl\H{o} gr\'{a}f.}  Legyen egy $\cal P$   parci\'{a}lis IFS  tiltott szavainak hossza legfeljebb $k$
'es az IFS f"uggv'enyeinek sz'ama $N$. Ekkor,
a k\'{a}oszj\'{a}t\'{e}kot vez\'{e}rl\H{o} gr\'{a}f szerkeszt\'{e}se:\\
{\large  1.} \ megszerkesztj\"{u}k a $G(N,k)$ gr\'{a}ft \'{e}s t\"{o}r\"{o}lj\"{u}k a tiltott szavakhoz tartoz\'{o} \'{e}leket.\\
{\large 2.}  \  mindn cimke hely\'{e}re a cimke {\sf els\H{o} bet\H{u}je} ker\"{u}l.

Ezut\'{a}n a k\'{a}oszj\'{a}t\'{e}kot egy v\'{e}letlen s\'{e}t\'{a}hoz ({\em random walk}) tartoz\'{o} k\'{o}d ir\'{a}ny\'{\i}tja. Ez r\'{e}szletesebben  a k\"{o}vetkez\H{o}
elj\'{a}r\'{a}s:\\
{\large  1.} \ Megadjuk az $F_{\sigma_1}(P)$ pontot, ahol $P$ tetsz\H{o}leges \'{e}s $\sigma_1$ a s\'{e}ta els\H{o} \'{e}l\'{e}nek cimk\'{e}je.\\
{\large 2.}  \  Megadjuk az $F_{\sigma_2}\circ F_{\sigma_1}(P)$ pontot, ahol $\sigma_2$ a s\'{e}ta m\'{a}sodik \'{e}l\'{e}nek cimk\'{e}je.\\
{\large n.}  \  Megadjuk az $F_{\sigma_n}\circ\dots\circ F_{\sigma_2}\circ F_{\sigma_1}(P)$ pontot, ahol $\sigma_n$ a s\'{e}ta n-edik \'{e}l\'{e}nek cimk\'{e}je.
$(n=2,3,\dots )$\\

Ez a Sierpinski h\'{a}romsz\"{o}g vagy a DNS l\'{a}nccal vez\'{e}relt  k\'{a}oszj\'{a}t\'{e}k k\"{o}zvetlen \'{a}ltal\'{a}nos\'{\i}t\'{a}sa. ({\bf Mi\'{e}rt?})
Itt is az els\H{o} 10-12 pontot elhagyjuk. ({\bf Mi\'{e}rt?})

Az elj\'{a}r\'{a}st a k\"{o}vetkez\H{o} t\'{e}telek igazolj\'{a}k.\\
\\  \\
{\large\bf 1. T\'{e}tel.} \  Minden v\'{e}letlen s\'{e}t\'{a}hoz megengedett k\'{o}d tartozik.\\
\\
{\large\bf  Bizony\'{\i}t\'{a}s.} \  A $G(N,k)$ gr\'{a}f szerkeszt\'{e}se alapj\'{a}n, a s\'{e}ta $k$ hossz\'{u} prefixe cimk\'{e}inek els\H{o} bet\H{u}ib\H{o}l
alkotott sz\'{o},  megegyezik a s\'{e}ta kezd\H{o} \'{e}l\'{e}nek (deBrujin) szav\'{a}val.

Ez\'{e}rt, ha a s\'{e}t\'{a}hoz tartoz\'{o} k\'{o}d NEM megengedett, akkor van $k$ hossz\'{u} tiltott sz\'{o} benne. Vagyis, a s\'{e}t\'{a}ban van $k$ hossz\'{u} \'{u}t,
amelyhez tartoz\'{o} cimk\'{e}k els\H{o} bet\H{u}ib\H{o}l alkotott sz\'{o} tiltott. Ez viszont megegyezik a s\'{e}ta els\H{o} \'{e}l\'{e}hez tartoz\'{o}
(deBrujin) sz\'{o}val. Ez viszont lehetetlen, hiszen a tiltott szavakhoz tartoz\'{o} \'{e}leket t\"{o}r\"{o}lt\"{u}k.\\
\\   
{\large\bf 2. T\'{e}tel.} \ Minden megengedett k\'{o}dhoz tartozik v\'{e}letlen s\'{e}ta.\\
\\
{\large\bf  Bizony\'{\i}t\'{a}s.}  \  A k\'{o}d $k$ hossz\'{u} prefix\'{e}hez tartozik \'{e}l, hiszen a megengedett szavakhoz tartoz\'{o} \'{e}leket
NEM t\"{o}r\"{o}lt\"{u}k a A $G(N,k)$ gr\'{a}fban. Ugyanez \'{a}ll a k\'{o}d  $\sigma_2\dots\sigma_k\sigma_{k+1}$  szav\'{a}ra. A deBrujin digr\'{a}f
szerkeszt\'{e}se alapj\'{a}n, a $\sigma_1\dots\sigma_{k-1}\sigma_k$ \'{e}s a $\sigma_2\dots\sigma_k\sigma_{k+1}$szavakhoz tartoz\'{o} \'{e}lek
2 hossz\'{u} utat alkotnak.

Indukci\'{o}val: ugyanez \'{e}rv\'{e}nyes a k\'{o}d $\sigma_i\dots\sigma_{i+k-1}\sigma_{i+k}$  \  ($i=1,2,\dots)$ szav\'{a}b\'{o}l kezdve.\\
\\  \\
{\large\bf P\'{e}ld\'{a}k.} A {\em 13.9 \'{a}br\'{a}n} a $20$ ill. $20, 33, 11, 02$
tiltott szavakhoz tartoz\'{o} gr\'{a}fokat \'{e}s mellett\"{u}k a hozz\'{a}juk tartoz\'{o} frakt\'{a}lk\'{e}pet l\'{a}tjuk abban az esetben,
{\em amikor az IFS az a Sierpinski h\'{a}romsz\"{o}ggel kapcsolatos
 f\"{u}ggv\'{e}nyrendszer, amelynek invari\'{a}ns halmaza az egys\'{e}gn\'{e}gyzet}  ({\large 12.2 2.} p\'{e}lda). \\
MEGJEGYZ\'{E}S.  A frakt\'{a}lk\'{e}p
 kialakul\'{a}s\'{a}hoz t\"{o}bbtizezer pont sz\"{u}ks\'{e}ges amit csak sz\'{a}mit\'{o}g\'{e}pes elj\'{a}r\'{a}ssal lehet megfelel\H{o} 
id\H{o}n bel\"{u}l elv\'{e}gezni, mint a modern algoritmusok majdnem mindegyik\'{e}t.\\
\\   \\
{\Large 13.4}\\

{\large\bf Az elj\'{a}r\'{a}s egyszer\H{u}s\'{\i}t\'{e}se}\\

A {\large 13.3} szerint megszerkesztett $\cal G$ gr\'{a}f ir\'{a}ny\'{\i}tani tudja a k\'{a}oszj\'{a}t\'{e}kot, viszont
$k\geq 3$ eset\'{e}n t\'{u}ls\'{a}gosan nagym\'{e}ret\H{u} \'{e}s \'{\i}gy nehezen kezehet\H{o}. A $\cal G$ \'{e}leinek
a sz\'{a}ma sokszor nagym\'{e}rt\'{e}kben cs\"{o}kkenthet\H{o} a $\cal G$ szomsz\'{e}ds\'{a}gi m\'{a}trixanak 
alkalmaz\'{a}s\'{a}val \'{u}gy, hogy a s\'{e}t\'{a}khoz tartoz\'{o} szavak \'{e}s k\'{o}dok nem v\'{a}ltoznak.\\

Ha egy $\cal G$ gr\'{a}f   \'{e}leihez jeleket rendel\"{u}nk, akkor cimk\'{e}zett gr\'{a}fot kapunk.
Egy cimk\'{e}zett $\cal G$ gr\'{a}f  is t\"{o}k\'{e}letesen leirhat\'{o} (defini\'{a}lhat\'{o}) a {\sf szomsz\'{e}ds\'{a}gi m\'{a}trix\'{a}val} 
({\em adjacency matrix}).
 Az $A$ m\'{a}trix a cimk\'{e}zett  $\cal G$ gr\'{a}f szomsz\'{e}ds\'{a}gi m\'{a}trixa, ha
\begin{center}
$a_{ik}=$ az i-edik cs\'{u}csb\'{o}l a k-adik cs\'{u}csba mutat\'{o} \'{e}lek cimk\'{e}inek uni\'{o}ja (" \"{o}sszege "). 
\end{center}
(ha nincsenek az i-edik cs\'{u}csb\'{o}l a k-adik cs\'{u}csba mutat\'{o} \'{e}lek, akkor $a_{ik}=\bullet$ ahol $\bullet$ az
\"{u}res halmaz.)\\

A $\cal G$  cimk\'{e}zett digr\'{a}f m\'{e}rete akkor cs\"{o}kkenthet\H{o} ha a szomsz\'{e}ds\'{a}gi m\'{a}trix\'{a}nak 
 megegyez\H{o} oszlopai vannak. 
Ekkor,  {\em egy kiv\'{e}tel\'{e}vel},  t\"{o}r\"{o}lj\"{u}k  a megegyez\H{o} oszlopokat  
a nekik megfelel\H{o} sorokkal egy\"{u}tt, majd {\em a t\"{o}r\"{o}lt  sorok hely\'{e}re  egyetlen sort}, a t\"{o}r\"{o}lt 
sorok uni\'{o}j\'{a}t  (\"{o}sszeg\'{e}t)tessz\"{u}k.

Az igy kapott szomsz\'{e}ds\'{a}gi m\'{a}trixhoz tartoz\'{o} gr\'{a}f s\'{e}t\'{a}ihoz  tartoz\'{o} k\'{o}dok halmaza {\em v\'{a}ltozatlan} marad.\\
\\
{\large\bf P\'{e}ld\'{a}k.} \ {\Large 1.}  A {\em 13.9a/  \'{a}bra}  gr\'{a}f  szomsz\'{e}ds\'{a}gi m\'{a}trixa
$$\left( \begin{array}{cccc} 0 & 0 &  0 &  0 \\ 1 &  1 & 1 &  1 \\
 \bullet &  2 &  2 & 2 \\ 3 & 3 &  3 &  3  \end{array}\right)$$
a matrix 2., 3. \'{e}s  4. oszlopa megegyezik. T\"{o}r\"{o}lj\"{u}k a m\'{a}trix 3. \'{e}s 4. oszlop\'{a}t \'{e}s sor\'{a}t \'{e}s a 2. sor
hely\'{e}re irjuk a   2., 3. \'{e}s  4. sor uni\'{o}j\'{a}t (\"{o}sszeg\'{e}t). Az igy kapott szomsz\'{e}ds\'{a}gi m\'{a}trix
$$\left( \begin{array}{cc} 0 & 0 \\ 1+3 &  1+2+3 \end{array}\right)$$
ahol a $+$ azt jelenti, hogy a megfelel\H{o} cs\'{u}csok k\"{o}z\"{o}tt t\"{o}bb \'{e}l van k\"{u}l\"{o}nb\"{o}z\H{o} cimk\'{e}kkel. P\'{e}ld\'{a}ul, a m\'{a}sodik 
cs\'{u}csb\'{o}l 
az els\H{o}be k\'{e}t \'{e}l ir\'{a}nyul, az egyik $1$ a m\'{a}sik meg $3$ cimk\'{e}vel.

Ehez a m\'{a}trixhoz tartoz\'{o}
digr\'{a}f l\'{a}that\'{o} a {\em 13.10  \'{a}br\'{a}n}.  Itt is pontosan azokat a 
 k\'{o}dokat kapjuk az \'{e}lekhez tartoz\'{o} bet\H{u}k (cimk\'{e}k) \"{o}sseolvas\'{a}s\'{a}val, amelyek nem tartalmazz\'{a}k a 
$20$ sz\'{o}t.\\
 {\Large 2.}  A {\em 13.9b/ \'{a}bra}  gr\'{a}f  szomsz\'{e}ds\'{a}gi m\'{a}trixa
$$\left( \begin{array}{cccc} 0 & 0 &  \bullet & 0  \\ 1 &  \bullet & 1 &  1 \\
 \bullet &  2 &  2 & 2 \\ 3 & 3 &  3 & \bullet  \end{array}\right)$$
Itt nincsenek megegyez\H{o} oszlopok. A digr\'{a}f nem egyszer\H{u}sithet\H{o}.\\
\\
 
Ha megvizsg\'{a}ljuk, hogy a szomsz\'{e}ds\'{a}gi m\'{a}trix leirt \'{a}talakit\'{a}sa a gr\'{a}f milyen \'{a}talakit\'{a}s\'{a}nak
 felel meg, akkor vil\'{a}goss\'{a} v\'{a}lik, hogy az egyszer\H{u}sitett gr\'{a}fhoz tartoz\'{o} k\'{o}dok halmaza{\em v\'{a}ltozatlan} maradt.
  Ebb\H{o}l \'{a}ll az elj\'{a}r\'{a}s bizony\'{\i}t\'{a}sa. \\
\\
{\LARGE\bf **}\\
{\bf Az elj\'{a}r\'{a}st  a k\"{o}vetkez\H{o} t\'{e}tel igazolja.}\\
{\bf T\'{e}tel.} \ Legyen $A$ a $\cal G$ cimk\'{e}zett digr\'{a}f szomsz\'{e}ds\'{a}gi m\'{a}trixa, amelyre
$$a_{ij_1}=a_{ij_2}=\dots a_{ij_k} \;\; \;\, i=1,2,\dots ,n$$
vagyis az $A$ m\'{a}trix $j_1, j_2,\dots j_k$ oszlopai megegyeznek. T\"{o}r\"{o}lj\"{u}k a  $ j_2,\dots j_k$ oszlopokat \'{e}s sorokat, majd 
\'{\i}rjuk a $j_1$-edik sor hely\'{e}be a $j_1, j_2,\dots j_k$ sorok " \"{o}sszeg\'{e}t". Legyen az \'{\i}gy kapott m\'{a}trix $A^*$ \'{e}s a
hozz\'{a}tartoz\'{o} cimk\'{e}zett digr\'{a}f ${\cal G}^*$.

Ekkor $\cal G$ \'{e}s ${\cal G}^*$  ugyanazt a k\'{o}drendszert (k\'{o}dok halmaz\'{a}t) \'{a}ll\'{\i}tja el\H{o}\\
\\
{\bf Bizony\'{\i}t\'{a}s.} \  Ha a k\'{o}dhoz tartoz\'{o} s\'{e}ta olyan cs\'{u}csokon halad \'{a}t, amelyhez tartoz\'{o} oszlopot NEM
t\"{o}rl\"{u}nk az elj\'{a}r\'{a}s sor\'{a}n, akkor ezt a k\'{o}dot a m\'{o}dos\'{\i}tott gr\'{a}ffal vez\'{e}relt k\'{a}oszj\'{a}t\'{e}k is tartalmazni fogja.
Azokhoz a k\'{o}dhoz tartoz\'{o} s\'{e}t\'{a}kat kell csak megvizsg\'{a}lni, amelyek a $\cal G$ gr\'{a}f olyan cs\'{u}csain haladnak \'{a}t amelyeket az
elj\'{a}r\'{a}s folyam\'{a}n t\"{o}rl\"{u}nk a $\cal G$ szomsz\'{e}ds\'{a}gi m\'{a}trix\'{a}b\'{o}l.

Ha a  szomsz\'{e}ds\'{a}gi m\'{a}trix i-edik \'{e}s j-edik oszlopa megegyezik, akkor digr\'{a}f i-edik
 \'{e}s j-edik cs\'{u}cs\'{a}nak
be-\'{e}lei megegyeznek. Ez azt jelenti, hogy  pontosan akkor \'{e}rkezik
\'{e}l  a $v$ cs\'{u}csb\'{o}l  az i-edik cs\'{u}csba  $\sigma$ cimk\'{e}vel,  ha a $v$ cs\'{u}csb\'{o}l a j-edik cs\'{u}csba is \'{e}rkezik
\'{e}l ugyanazzal a $\sigma$ cimk\'{e}vel. \'{I}gy {\em minden}, az $i$ cs\'{u}cson \'{a}thalad\'{o} \'{u}thoz tartoz\'{o} k\'{o}dnak az $i$ cs\'{u}csig
tart\'{o} szakasza megegyezik a $j$ cs\'{u}cson \'{a}thalad\'{o} \'{u}thoz tartoz\'{o} k\'{o}dnak a $j$ cs\'{u}csig
tart\'{o} szakasz\'{a}val. 

ha kett\H{o}n\'{e}l t\"{o}bb oszlop  egyezik meg az $A$ szomsz\'{e}ds\'{a}gi m\'{a}trixban, legyenek ezek a $j_1, j_2,\dots j_k$ oszlopok,
akkor a  $j_1, j_2,\dots j_k$ cs\'{u}csokba ugyanazok az \'{e}lek futnak be (azonosak azok az \'{e}lek, amelyeknek megegyezik a kezd\H{o} 
\'{e}s v\'{e}gpontja \'{e}s a {\em cimk\'{e}je}). Ez\'{e}rt minden $j_1, j_2,\dots j_k$ cs\'{u}csokra illeszked\H{o} \'{u}tnak a cs\'{u}csokig
tart\'{o} r\'{e}sz\'{e}hez ugyanaz a sz\'{o} tartozik.

Ha a t\"{o}r\"{o}lt ki\'{e}leket a $j_1$ cs\'{u}csra f\"{u}ggessz\"{u}k, vagyis a 
$$(j_m, v); \;\; \;\; m=1,2,\dots ,k$$
\'{e}lek mindegyik\'{e}t, v\'{a}ltozatlan cimk\'{e}vel, $(j_1, v)$ \'{e}lre cser\'{e}lj\"{u}k, akkor egyetlen \'{u}t sem v\'{e}sz el.\\

{\LARGE\bf **}\\

A szomsz\'{e}ds\'{a}gi m\'{a}trix felhaszn\'{a}l\'{a}s\'{a}val kapott fenti \'{a}talak\'{\i}t\'{a}s ut\'{a}n a kapott (ir\'{a}ny\'{\i}tott) gr\'{a}f 
{\em minim\'{a}lis} abban
az \'{e}rtelemben, hogy a legkevesebb cs\'{u}csa van mindazon gr\'{a}fok k\"{o}z\"{o}tt, amelyek  a  k\'{o}doknak egy adott  halmaz\'{a}t 
reprezent\'{a}lj\'{a}k.\\
 \\   \\
{\Large 13.5}\\
\\
{\large\bf A frakt\'{a}lk\'{e}p (parci\'{a}lis IFS attrktor\'{a}nak) box-dimenzi\'{o}ja.}\\

\'{E}pp\'{u}gy mint az \"{o}nhasonl\'{o} IFS eset\'{e}n, el\H{o}sz\H{o}r az $r_i=r$ esetet vizsg\'{a}ljuk. Vagyis azt, amikor a 
kontraktivit\'{a}si t\'{e}nyez\H{o}k egyenl\H{o}k.\\
\\
{\large\bf  T\'{e}tel.} \ Legyen $B(n)$  az $n$ hossz\'{u} megengedett (NEM tiltott) szavak sz\'{a}ma. Ekkora box-dimenzi\'{o}
$$\lim_{n\rightarrow\infty} \frac {\log B(n)}{n\log r}$$
\\ 

 Ennek alapj\'{a}n, nagy $n$-re,
$$B(n)\approx r^{ns}=(r^s)^n \leqno{(*)}$$
ahol $s$ a box-dimenzi\'{o}. 

 A  (*)  alapj\'{a}n, a szavak sz\'{a}ma egy hatv\'{a}nyf\"{u}ggv\'{e}ny szerint n\"{o}vekedik
 mik\"{o}zben a sz\'{o} hossz\'{u}s\'{a}g\'{a}t n\"{o}velj\"{u}k.  A frakt\'{a}lk\'{e}p $s$ dimenzi\'{o}ja ezt a n\"{o}veked\'{e}st m\'{e}ri.

Ha nincsen tiltott sz\'{o}, akkor
 $$s=\frac{\log 4}{\log r}$$
  hiszen n\'{e}gy k\"{u}l\"{o}nb\"{o}z\H{o}  jelb\H{o}l alkothat\'{o} {\em \"{o}sszes} $n$ hossz\'{u} szavak 
sz\'{a}ma $4^n$. 
Ha csup\'{a}n egyetlen jelet enged\"{u}nk meg, akkor $s=0$. Minden m\'{a}s esetben $$0<s<\frac{\log 4}{\log r}$$. 
A tiltott szavakkal megadott nyelv ann\'{a}l gazdagabb, min\'{e}l nagyobb az $s$. 
 
 Ha meghat\'{a}rozzuk a parci\'{a}lis IFS frakt\'{a}lk\'{e}p\'{e}nek a box-dimenzi\'{o}j\'{a}t, akkor ezzel egy   f\"{u}ggv\'{e}nyt is
 meghat\'{a}roztunk, 
amely azt jelzi, hogy  $n\rightarrow\infty$ eset\'{e}n hogyan n\"{o}vekszik a {\em megengedett} $n$ hossz\'{u} szavak sz\'{a}ma.\\
\\
{\large\bf  A t\'{e}tel bizony\'{\i}t\'{a}sa.} \ Vegy\"{u}nk $\cal A$-val hasonl\'{o} $\delta=r^n$ lefed\'{e}seket. Ekkor

$$N^*_{r^n}=B(n).$$
({\bf Mi\'{e}rt?})
\\

Most megmutatjuk, hogy  {\em lesz\'{a}mol\'{a}s} helyett, mikor \'{e}s hogyan lehet {\em sz\'{a}mit\'{a}ssal}
 meghat\'{a}rozni a $B(n)$ \'{e}rt\'{e}k\'{e}t.

 Ha m\'{a}r
ismerj\"{u}k azokat a szavakat, amelyek a l\'{a}ncb\'{o}l hi\'{a}nyzanak, akkor a megfelel\H{o}  parci\'{a}lis IFS-hez tartoz\'{o}  $B(n)$ 
\'{e}rt\'{e}kek 
sz\'{a}mol\'{a}s\'{a}ra standard m\'{o}dszer van a ${\cal G}_P$ gr\'{a}freprezent\'{a}ci\'{o}  $A$ szomsz\'{e}ds\'{a}gi m\'{a}trix\'{a}n kereszt\"{u}l.

Az alapformula
$$B(n)= \sum_{i,j=1}^k(A^n)_{i,j} \leqno{(B^*)}$$
ahol $k$ az $A$ m\'{a}trix m\'{e}rete (sorainak ill. oszlopainak a sz\'{a}ma).  Ugyanis a gr\'{a}felm\'{e}letb\H{o}l ismert, hogy   $(A^n)_{i,j}$ az i-edik 
cs\'{u}csb\'{o}l a j-edik
 cs\'{u}csba
fut\'{o} $n$ hossz\'{u} utak sz\'{a}ma.\\
\\                                  
{\large\bf T\'{e}tel.}  Legyen $v$ a nem-negativ $A$ m\'{a}trixnak {\em pozitiv saj\'{a}tvektora}. Ekkor a hozz\'{a}tartoz\'{o} $\lambda$ 
saj\'{a}t\'{e}rt\'{e}k {\em pozitiv} \'{e}s 
$$a\lambda^n\leq   \sum_{i,j=1}^k(A^n)_{i,j} \leq b\lambda^n$$
ahol $a$ \'{e}s $b$ megfelel\H{o} konstansok. Ebb\H{o}l k\"{o}vetkezik, hogy a frakt\'{a}lreprezent\'{a}ci\'{o} box-dimenzi\'{o}ja
$$\lim _{n\rightarrow\infty}\frac{\log B(n)}{n\log r}=\frac{\log\lambda}{\log r}. \leqno{(B)}$$
\\
{\large\bf Bizony\'{\i}t\'{a}s.}  Ha $Av=\lambda v$ akkor $A^nv={\lambda}^n v \;\; (n=1,2,\dots  )$ \'{e}s \'{\i}gy a m\'{a}trixszorz\'{a}s szab\'{a}lya 
alapj\'{a}n
$$ �\sum_{j=1}^k(A^n)_{i,j}v_j= {\lambda}^n v_i  \; \; \;\; n=1,2,\dots \leqno{(13.3)}$$
amib\H{o}l m\'{a}r k�ovetkezik, hogy $\lambda$ pozit\'{\i}v.
 
Legyen $v_M$ a legnagyobb \'{e}s $v_m$ a legkisebb a $v$ koordin\'{a}t\'{a}i k\"{o}z\"{o}tt.  Ekkor a (13.3)-b\H{o}l
$$v_M \sum_{j=1}^k(A^n)_{i,j}\geq{\lambda}^n v_m  \;\; \;\; i=1,2,\dots , k\leqno{(13.4)}$$
\'{e}s
$$v_m \sum_{j=1}^k(A^n)_{i,j}\leq{\lambda}^n v_M  \;\; \;\; i=1,2,\dots , k.\leqno{(13.5)}$$
A  (13.4) \'{e}s (13.5) alapj\'{a}n
$$k\frac{v_m}{v_M}{\lambda}^n \leq\sum_{i,j=1}^k(A^n)_{i,j}\leq k\frac{v_M}{v_m}{\lambda}^n.$$
Legyen 
$$c=k\frac{v_m}{v_M} \;\; \;\; C=k\frac{v_M}{v_m}.$$
Ekkor, a $(B^*)$ figyelembe v\'{e}tel\'{e}vel
$$\frac{\log c}{n\log r}+\log\lambda\leq \frac{\log B(n)}{n\log r}\leq\frac{\log C}{n\log r}+\frac{\log\lambda}{\log r}$$
\'{e}s $n\rightarrow\infty$ mellett lesz (B).\\
\\
{\large\bf P\'{e}ld\'{a}k.} {\Large 1.} A Sierpinski h\'{a}romsz\"{o}g  \'{u}gy is felfoghat\'{o}, mint azoknak
a l\'{a}ncoknak a halmaza, amelyb\H{o}l hi\'{a}nyzik a "$3$" (F.12.5). Ez\'{e}rt a gr\'{a}freprezent\'{a}ci\'{o} a h\'{a}rom cs\'{u}ccsal
alkotott teljes (ir\'{a}ny\'{\i}tott) gr\'{a}f  aminek a szomsz\'{e}ds\'{a}gi m\'{a}trixa
 $$ \left ( \begin{array}{lcr} 1 & 1 & 1 \\1 & 1 & 1\\1 & 1 & 1 \\ \end{array}\right ).$$																													\right )
{\rm Ennek \; egyetlen \; pozitiv \; saj\'{a}t\'{e}rt\'{e}ke \; van:} \; $\lambda =3$. Igy 
$$\lim _{n\rightarrow\infty}\frac{\log B(n)}{n\log r}=\frac{\log 3}{\log 2}=1.5849\dots$$
ami megegyezik a direkt m\'{o}don kapott eredm\'{e}nnyel.\\
\\
{\Large 2.} A {\em 13.9a \'{a}bra} annak a k\'{o}dnak a frakt\'{a}lk\'{e}p\'{e}t \'{e}s digr\'{a}f reprezent\'{a}ci\'{o}j\'{a}t mutatja amelyben 
az egyetlen tiltott sz\'{o} $20$. A digr\'{a}f  szomsz\'{e}ds\'{a}gi m\'{a}trixa
$$ \left ( \begin{array}{lccr} 1 & 1 & 1 & 1\\1 & 1 & 1 &1\\
0 & 1 & 1 & 1\\ 1 & 1 & 1 & 1\\ \end{array}\right )$$
aminek  pozitiv saj\'{a}t\'{e}rt\'{e}kei $2+\sqrt 3$ \'{e}s $2-\sqrt 3$.  Igy  a box-dimenzi\'{o}
$$\frac{\log\lambda}{\log 2}= \frac{\log(2+\sqrt 3)}{\log 2}=1.899968627\dots .$$
( K\"{o}zvetlen\"{u}l bel\'{a}that\'{o}, hogy a $\lambda =2-\sqrt 3$ saj\'{a}t\'{e}rt\'{e}khez tartoz\'{o} saj\'{a}tvektor NEM pozitiv.)\\
\\
{\Large 3.} A {\em 13.9b \'{a}bra} annak a k\'{o}dnak a frakt\'{a}lk\'{e}p\'{e}t \'{e}s digr\'{a}f reprezent\'{a}ci\'{o}j\'{a}t mutatja amelyben 
 $20, 02, 11, 33$ a tiltott szavak. A digr\'{a}f  szomsz\'{e}ds\'{a}gi m\'{a}trixa
$$ \left ( \begin{array}{lccr} 1 & 1 & 0 & 1\\1 & 0 & 1 &1\\
0 & 1 & 1 & 1\\ 1 & 1 & 1 & 0\\ \end{array}\right )$$
aminek egyetlen pozitiv saj\'{a}t\'{e}rt\'{e}ke $\lambda =2.41\dots$. \\
\\
A fenti p\'{e}ld\'{a}k is illusztr\'{a}lj\'{a}k, hogy eset\"{u}nkben a box-dimenzi\'{o} a frakt\'{a}lreprezent\'{a}ci\'{o} m\'{e}rete 
mellett azt is  jelzi, hogy  a sz\'{o}hossz
n\"{o}vel\'{e}s\'{e}vel milyen m\'{e}rt\'{e}kben n\"{o}vekedik a sz\'{o}k\'{e}szlet.\\
\\  \\

\\  \\
{\large\bf Feladatok \'{e}s tov\'{a}bbi inform\'{a}ci\'{o}k.}\\
\\ 
{\Large F. 13.1} \  \  A k\'{a}oszj\'{a}t\'{e}kkal kapcsolatban:
\begin{itemize} 
\item I. Ha $P_0\not\in{\cal S}$, akkor mit mondhatunk  a k\'{a}oszj\'{a}t\'{e}kkal kapott $\{ P_n; \;\; n=1,2,\dots\}$ pontok \'{e}s
az $\cal S$ Sierpinski h\'{a}romsz\"{o}g kapcsolat\'{a}r\'{o}l?
\item II. V\'{e}grehajtva ezt a szerkeszt\'{e}st egy tetsz\H{o}leges h\'{a}romsz\"{o}gre, milyen rokons\'{a}got \'{e}s milyen 
elt\'{e}r\'{e}st tapasztalunk? 
\item III. Hogyan lehet el\H{o}\'{a}llitani a fenti k\'{a}oszj\'{a}t\'{e}khoz hasonl\'{o}an a (triadikus) Cantor halmaz pontjait ?
\end{itemize}  
\\
{\Large F. 13.2} \ \  Fogalmazzuk meg a k\'{a}oszj\'{a}t\'{e}kot tetsz\H{o}leges IFS-re.\\
\\
{\Large F. 13.3} \ \  Nyitva maradt annak az eld\"{o}nt\'{e}se, hogy a k\'{a}oszj\'{a}t\'{e}k, el\'{e}g hossz\'{u} ideig tart\'{o} 
m\H{u}k\"{o}d\'{e}s ut\'{a}n, az $\cal A$ b\'{a}rmely pontj\'{a}t el\H{o}\'{a}llitja-e. (Err\H{o}l 
a "frakt\'{a}lok \'{e}s diszkr\'{e}t dinamikus rendszerek" c. r\'{e}szben.)\\
\\
{\Large **F. 13.4} \ \  Igazoljuk, hogy a k\'{a}oszj\'{a}t\'{e}kban adott pontsorozat pontosan akkor konvergens,
 ha a k\'{a}oszj\'{a}t\'{e}kot ir\'{a}ny\'{\i}t\'{o} k\'{o}d, v\'{e}ges sok bet\H{u} kiv\'{e}tel\'{e}vel, ugyanazon
 bet\H{u}kb\H{o}l \'{a}ll. (P\'{e}ld\'{a}ul, adott helyt\H{o}l kezdve csupa $3$ \'{a}ll.)\\
\\
{\Large F. 13.5}  \  \  Igazoljuk azt az elj\'{a}r\'{a}st, amellyel a DNS l\'{a}nccal vez\'{e}relt k\'{a}oszj\'{a}t\'{e}k eredm\'{e}ny\'{e}b\H{o}l,
a kapott halmaz  (majdnem) \"{u}res foltjaib\'{o}l, meghat\'{a}rozhatjuk a hi\'{a}nyz\'{o} szavakat.\\
\\
,{\Large F. 13.6}  \  \  A DNS l\'{a}nc frakt\'{a}lk\'{e}p\'{e}b\H{o}l  nemcsak egyes szavak hi\'{a}ny\'{a}ra kaphatunk inform\'{a}ci\'{o}t, 
hanem inform\'{a}ci\'{o}t kaphatunk az el\H{o}fordul\'{o} szavak gyakoris\'{a}g\'{a}ra is.
Tekints\"{u}k p\'{e}ld\'{a}ul a $201$ ({\bf tag}) sz\'{o}t. Az ennek megfelel\H{o} ponth\'{a}rmas harmadik pontja a $201$ n\'{e}gyzet\'{e}ben van
({\em 13.11\'{a}bra}). 
A szerkeszt\'{e}sb\H{o}l k\"{o}vetkezik, hogy minden olyan sz\'{o} n\'{e}gyzete, amely $201$-re v\'{e}gz\H{o}dik, vagyis szuffixe $201$, 
a $201$ n\'{e}gyzet\'{e}nek {\em r\'{e}sze}. Ugyanis, ha az $\cal A$ n\'{e}gyzet {\em minden} pontj\'{a}ra alkalmazzuk a $201$ 
szerkeszt\'{e}s\'{e}t, akkor a  $201$ n\'{e}gyzet\'{e}t kapjuk ({\em 13.11\'{a}bra}). 
Igy ha a l\'{a}ncban ujra el\H{o}fordul a $201$ , akkor a megfelel\H{o} pont ujra a $201$ 
n\'{e}gyzet\'{e}be ker\"{u}l. Ennek alapj\'{a}n a $201$ gyakoris\'{a}g\'{a}t a $201$ n\'{e}gyzet\'{e}be t\"{o}rt\'{e}n\H{o} visszat\'{e}r\'{e}sek 
sz\'{a}m\'{a}val m\'{e}rhetj\"{u}k.\\
  \\
{\Large F. 13.7}  \  \  A DNS l\'{a}nc vez\'{e}relte k\'{a}oszj\'{a}t\'{e}kot alkalmazhatjuk b\'{a}rmely elegend\H{o}en hossz\'{u}
 {\sf irodalmi sz\"{o}veg frakt\'{a}lk\'{e}p\'{e}nek} 
megalkot\'{a}s\'{a}ra. Ebb\H{o}l a c\'{e}lb\'{o}l {\sf a sz\"{o}veget  egyetlen sz\'{o}k\'{e}nt} irjuk fel amely az ABC bet\H{u}inek
 nagyon hossz\'{u} l\'{a}ncak\'{e}nt jelenik meg \'{e}s (v\'{e}gtelen)  k\'{o}dnak tekinthet\"{u}nk}.

Egy angol sz\"{o}veg $25$ bet\H{u}b\H{o}l  \'{a}ll. Hogyan \'{a}ltal\'{a}nositjuk a DNS k\'{o}d vez\'{e}relte k\'{a}oszj\'{a}t\'{e}kot $N>4$ bet\H{u}re?

Egy ilyen elj\'{a}r\'{a}s a k\"{o}vetkez\H{o}:  Mivel minden t\'{e}glalap \"{o}naffin, ez\'{e}rt a {\large 12.1-2}-ben leirt elj\'{a}r\'{a}s
\'{a}ltal\'{a}nosithat\'{o} \'{u}gy hogy az egys\'{e}gn\'{e}gyzet helyett $\cal A$ egy megfelel\H{o} t\'{e}glalap legyen.
 Ekkor felosztjuk a t\'{e}glalapot $N$ azonos m\'{e}ret\H{u} n\'{e}gyzetre \'{e}s legyen $F_i$ az a f\"{u}ggv\'{e}ny (\lek )
amely a teglalapot az $i$-edik n\'{e}gyzetbe viszi. Ekkor a
$$\ski \;\; \;\; \sigma_i\in\{ 1,2,\dots ,N\}$$
sz\'{o}hoz hozz\'{a}rendelj\"{u}k a 
$$F_{\sigma_k}\circ\dots\circ F_{\sigma_2}\circ F_{\sigma_1}(\bullet )    \;\; \;\;  k=1,2,\dots $$
pontsorozatot, \'{e}ppen \'{u}gy mint $N=4$ esetben.\\

P\'{E}LDA.  Legyen $N=6$.  Ekkor egy alkalmas t\'{e}glalap m\'{e}rete \ $2a\times3a$ \  \'{e}s 
$$F_{kl}(x)= \left( \begin{array}{cc} 0.333 & 0 \\ 0 & 0.5 \end{array}\right) \left(\begin{array} {c} x_1 \\ x_2 \end{array}\right) + 
  \left(\begin{array} {c} ka \\ la \end{array}\right). $$
ahol \ $k=0,1,2$  \  \'{e}s  \  $l=0,1$  \  a {\em 13.12 \'{a}br\'{a}nak}  megfelel\H{o}en.\\
\\ 
\\
{\Large F. 13.8}  Adjunk meg egy olyan t\'{e}glalapot \'{e}s $\Fi$ affin \lek eket, amelyek egy $N=9$ bet\H{u}b\H{o}l 
\'{a}ll\'{o} ABC-b\H{o}l alkotott form\'{a}lis nyelv (valamely 9 bet\H{u}b\H{o}l \'{a}ll\'{o} sz\"{o}veg) frakt\'{a}lk\'{e}p\'{e}t \'{a}llitja
el\H{o}.\\
\\
{\Large F. 13.9} \ A geometriai szerkeszt\'{e}s f\"{u}gg a reprezent\'{a}ci\'{o} felbont\'{o} k\'{e}pess\'{e}g\'{e}t\H{o}l (ez az $n>9$ hossz\'{u}
 szavakn\'{a}k m\'{a}r nem szokott megfelel\H{o} lenni). A k\"{o}vetkez\H{o} bin\'{a}ris aritmetika b\'{a}rmeddig folytathat\'{o}.  K\'{\i}ndulunk
 a (0.1, 0.1) (bin\'{a}ris t\"{o}rt) "pontb\'{o}l"; ha a k-adik pont, $P_k$, bin\'{a}ris koordin\'{a}t\'{a}i
$$0.\sigma_k, \sigma_{k-1}\dots\sigma_11, \  0.\omega_k, \omega_{k-1}\dots\omega_11$$
\'{e}s a $k+1$-edik bet\H{u} a DNS l\'{a}ncban, bin\'{a}ris alakban $ij$ (p\'{e}ld\'{a}ul  \\ $10=2$) akkor $P_{k+1}$ bin\'{a}ris koordin\'{a}t\'{a}i
$$0.i\sigma_k, \sigma_{k-1}\dots\sigma_11, \  0.j\omega_k, \omega_{k-1}\dots\omega_11$$
(p\'{e}ld\'{a}ul  $0.0\sigma_k, \sigma_{k-1}\dots\sigma_11, \  0.1\omega_k, \omega_{k-1}\dots\omega_11)$.
 Igazoljuk ezt az elj\'{a}r\'{a}st!\\
\\
{\Large F. 13.10} \ K\"{o}zvetlen sz\'{a}mol\'{a}ssal igazolhatjuk, hogy ha  a $\lambda$ saj\'{a}t\'{e}rt\'{e}khez pozitiv saj\'{a}tvektor 
is tartozik, akkor
$\lambda$ a legnagyobb saj\'{a}t\'{e}rt\'{e}k. ( V\'{e}gezz\"{u}k el ezt a sz\'{a}mol\'{a}st.)

Ez\'{e}rt a $\lambda$ meghat\'{a}roz\'{a}s\'{a}ra a maxim\'{a}lis saj\'{a}t\'{e}rt\'{e}k meghat\'{a}roz\'{a}s\'{a}ra ismert algoritmusokat 
aj\'{a}nlatos alkalmazni.\\
\\
{\Large F.13.11} \ {\sf A  Perron Frobenius t\'{e}tel.}  \ Egy nemnegat\'{\i}v $A$ m\'{a}trixnak mind\'{\i}g van pozit\'{\i}v saj\'{a}tvektora \'{e}s 
a hozz\'{a}tartoz\'{o} saj\'{a}t\'{e}rt\'{e}k a legnagyobb saj\'{a}t\'{e}rt\'{e}ke $A$-nak. Ez ut\'{o}bbi eset\"{u}nkben azt jelenti, hogy  az $A$
minden $\mu$ saj\'{a}t\'{e}rt\'{e}k\'{e}re
$$|\mu |\leq \lambda.$$
\\ 
{\bf Az {\large F.13.12-14} feladatai a {\em 12.5 \'{a}bra} k\'{o}dolt n\'{e}gyzet\'{e}re vonatkoznak.}\\
\\
{\Large F.13.12}  \   T\"{o}r\"{o}lj\"{u}k mindazon n\'{e}gyzeteket, amelyek k\'{o}dja tartalmazza a  2003 sz\'{o}t. Mennyi lesz a 
megmarad\'{o} halmaz  box-dimenzi\'{o}ja?  Ha mindazokat a n\'{e}gyzeteket t\"{o}r\"{o}lj\"{u}k,
 amelyek k\'{o}dja a 23  sz\'{o}t  tartalmazza, akkor  mennyi lesz a megmarad\'{o} halmaz  box-dimenzi\'{o}ja?\\
\\
{\Large F.13.13}  \  Igaz-e, hogy b\'{a}rmely k\'{e}t bet\H{u}b\H{o}l \'{a}ll\'{o} tiltott sz\'{o} eset\'{e}n, a parci\'{a}lis IFS attraktor\'{a}nak 
boxdimenzi\'{o}ja megegyezik?\\
\\
{\Large F.13.14}  \  Melyik \'{e}rv\'{e}nyes a k\"{o}vetkez\H{o} \'{a}ll\'{\i}t\'{a}sok k\"{o}z\"{u}l.\\
{\large I.} \  B\'{a}rmilyen hossz\'{u}, a $\{0,1,2,3\}$ ABC-vel fel\'{\i}rt sz\'{o}t kiv\'{a}lasztva, mindazon n\'{e}gyzeteket t\"{o}r\"{o}lve a k\'{o}dolt
 n\'{e}gyzetben, amelyek 
k\'{o}dja ezt a sz\'{o}t tartalmazza, a kapott halmaz nulla m\'{e}rt\'{e}k\H{u} (a ter\"{u}lete b\'{a}rmely pozit\'{\i}v sz\'{a}mn\'{a}l is kisebb).\\
{\large II.}  \  Kiv\'{a}laszthatunk olyan,  a $\{0,1,2,3\}$ ABC-vel fel\'{\i}rt  
 sz\'{o}t, hogy mindazon n\'{e}gyzeteket t\"{o}r\"{o}lve a k\'{o}dolt n\'{e}gyzetben, amelyek 
k\'{o}dja ezt a sz\'{o}t tartalmazza, a kapott halmaz dimenzi\'{o}ja tetsz\H{o}legesen k\"{o}zel van a kett\H{o}h\"{o}z.\\
\\ 
{\Large F. 12.1} \  \  Jel\"{o}lj\"{u}k ki a  Sierpinski h\'{a}romsz\"{o}gben a
$$   F_3 ({\cal A}), \ \   F_3 \circ F_2 ({\cal A}), \ \   F_3 \circ F_2 \circ F_2({\cal A}), \ \ 
 F_3 \circ F_2 \circ F_2 \circ F_3 ({\cal A}),  $$
$$    F_3 \circ F_2 \circ F_2 \circ F_3 \circ F_1 ({\cal A}) $$
 halmazokat. 

 Folytassuk tov\'{a}bb ezt a  sorozatot \'{u}gy, hogy az a Hausdorff t\'{a}vols\'{a}gban konverg\'{a}ljon
egy $a\in {\cal A}$ ponthoz.\\
\\
{\Large F. 12.2} \  \ Az {\large F.12.1} k\'{e}rd\'{e}se a Koch g\"{o}rb\'{e}re  \'{e}s a csill\'{a}rra.\\
\\
{\Large F. 12.3} \  \  Legyen $\cal K$ egy z\'{a}rt g\"{o}mb amelyre
$$F_i({\cal K})\subset {\cal K}; \;\; \; i=1,2,\dots , N.$$
 A (12.2)-ben irjuk ezt a $\cal K$-t az $\cal A$ hely\'{e}be. Mi lesz ekkor az (12.2) halmazsorozat k\"{o}z\"{o}s r\'{e}sze?\\
\\
{\Large F. 12.4} T\"{o}bb \'{e}ven \'{a}t tart\'{o} megfigyel\'{e}s alapj\'{a}n kimutat\'{a}s k\'{e}sz\"{u}l az id\H{o}j\'{a}r\'{a}s naponk\'{e}nti 
alakul\'{a}s\'{a}r\'{o}l egy \"{u}d\"{u}l\H{o}helyi sz\'{a}lloda megbiz\'{a}s\'{a}b\'{o}l. A kimutat\'{a}s azt kiv\'{a}nja kimutatni, hogy 
azoknak a heteknek a sz\'{a}ma,
amikor es\H{o}s, h\H{u}v\"{o}s id\H{o}j\'{a}r\'{a}s uralkodik, eleny\'{e}sz\H{o}en csek\'{e}ly azokhoz a hetekhez k\'{e}pest,
 amikor v\'{e}gig naps\"{u}t\'{e}s van. Ha a napi id\H{o}j\'{a}r\'{a}s jelleg\'{e}t igy jel\"{o}lj\"{u}k\\
\\
{\sf\large 0} {\it napf\'{e}nyes, meleg}\\
{\sf\large 1} {\it r\'{e}szben felh\H{o}s}\\
{\sf\large 2} {\it v\'{a}ltoz\'{e}kony}\\
{\sf\large 3} {\it h\H{u}v\"{o}s, es\H{o}s}\\
\\
akkor azoknak a hetes blokkoknak a sz\'{a}ma a sok\'{e}vi megfigyel\'{e}st repezent\'{a}l\'{o} tobbezres l\'{a}ncb\'{o}l, amelyekben
nincsen $2, 3$ \'{e}s t\"{o}bbs\'{e}g\'{e}ben $0$ bet\H{u}t tartalmaznak, megadja a kellemes hetek sz\'{a}m\'{a}t.\\
\\
{\Large F. 12.11}  \  \  A (13.1) formul\'{a}val adott $\cal M$ halmaz, egy IFS-re vezet\H{o} sorozattal is el\H{o}\'{a}ll\'{\i}that\'{o}.
 Legyenek $\Fi$  affin f\"{u}ggv\'{e}nyek, amelyekkel egy iter\'{a}lt f\"{u}ggv\'{e}nyrendszert (IFS) adunk meg.
 Vegy\"{u}k ezekhez hozz\'{a}  az
$$F_0({\cal B})={\cal K}_0$$
 halmazf\"{u}ggv\'{e}nyt.  $F_0$ egy konstans halmazf\"{u}ggv\'{e}ny, amely minden kompakt $\cal B$ halmazhoz ugyanazt a ${\cal K}_0$ kompakt halmazt 
rendeli hozz\'{a}. Legyen
$$W^*=W\bigcup F_0$$
ahol $W$ a az $\Fi$  affin f\"{u}ggv\'{e}nyek uni\'{o}ja.
K\"{o}zvetlen sz\'{a}mol\'{a}ssal (felhaszn\'{a}lva a halmazf\"{u}ggv\'{e}nyek sz\'{a}mol\'{a}si szab\'{a}lyait)
$$W^{*[n]}({\cal B})=W^{[n]}({\cal B})\bigcup_{k=0}^{n-1} W^{[k]}({\cal K}_0)\;\; \;\; n=1,2,\dots \leqno{(12.8)}$$
\'{e}s a $\{W^{*[n]}({\cal B}), \;\; n=1,2,\dots\}$ (Hausdorff t\'{a}vols\'{a}gban) konverg\'{a}l, hiszen $F_0$ kontraktiv. 
Tov\'{a}bb\'{a}, szint\'{e}n k\"{o}zvetlen sz\'{a}mol\'{a}ssal
$$W^*({\cal M})={\cal M}.$$
\\
{\Large F.  12.12} \  \  Legyenek $F_i; \;\; (i=1,\dots, N)$ 
hasonl\'{o}s\'{a}gi lek\'{e}pez\'{e}sek \'{e}s $F_0$ konstans 
lek\'{e}pez\'{e}s. Adjuk meg az
$$\{F_i; \;\; i=0,1,\dots, N\}$$
f\"{u}ggv\'{e}nyeket \'{u}gy, hogy\\
I. \   Az IFS $\cal A$ invari\'{a}ns halmaza az {\em 1.11 \'{a}br\'{a}n} l\'{a}that\'{o} sorozat folytat\'{a}s\'{a}nak a 
hat\'{a}r\'{e}rt\'{e}ke legyen. \\ 
II.  \   Az IFS $\cal A$ invari\'{a}ns halmaza az  {\em 12.13 \'{a}br\'{a}n} l\'{a}that\'{o} sorozat folytat\'{a}s\'{a}nak a 
hat\'{a}r\'{e}rt\'{e}ke legyen. \\ 
\\
{\Large F.12.15}   \   ${\cal K}_0\bigcup_{i=1}^\infty W^{[i]}({\cal K}_0)$, a TILTOTT szavakat tartalmaz\'{o} k\'{o}dok ${\cal M}$
halmaza, nyilv\'{a}n val\'{o}di r\'{e}szhalmaza $\cal A$-nak, m\'{e}gis
$$h[{\cal K}_0\bigcup_{i=1}^\infty W^{[i]}({\cal K}_0), {\cal A}]=0.$$
Ugyanis  ${\cal M}$ az  ${\cal A}$ {\em s\H{u}r\H{u}} r\'{e}szhalmaza. Ez abb\'{o}l k\"{o}vetkezik, hogy  minden $n$-hez van 
$\omega\in{\cal M}$, amely {\em csak az $n$-edik jel ut\'{a}n tartalmaz tiltott sz\'{o}t}.\\
\\
{\Large F.12.16}   \  Legyen  $(\sum d_3)$ a $\{0,1,2\}$ jelekb\H{o}l  (bet\H{u}kb\H{o}l) alkotott k\'{o}dok tere \'{e}s
$$F_1(\sigma)=0\sigma  \;\; \;\; F_2\sigma)=2\sigma \;\; \sigma  = \sigma_1\dots\sigma_n\dots $$
Adjuk meg az $(F_1, F_2, \sum )$ IFS kontraktivit\'{a}si t\'{e}nyez\H{o}it \'{e}s attraktor\'{a}t.\\
\\
{\Large F.12.17}    \   Mi a kapcsolat az $(F_1, \; F_2 \; R^2)$ \'{e}s az $(F_1\circ F_1, \; F_1\circ F_2, \; F_2\circ F_1, \; F_2\circ F_2 \;  R^2)$
IFS attraktora k\"{o}z\"{o}tt?\\
\\
{\Large F.12.18}    \   Mi a kapcsolat az  $(F_1\circ F_1,\; F_1\circ F_2, \; F_2\circ F_1,\;  F_2\circ F_2 \;  R^2)$ \'{e}s az
$(F_1\circ F_1\circ F_2, F_1\circ F_2\circ F_2, F_2\circ F_1\circ F_1, F_2\circ F_2\circ F_1)  R^2$  IFS attraktora k\"{o}z\"{o}tt?





\end{document}