Zřetězení

Zřetězení ( lat. concatenatio "připojení řetězy; vazba") je operace lepení předmětů lineární struktury, obvykle řetězců . Například zřetězením slov „mikro“ a „svět“ vznikne slovo „mikrosvět“.

V matematice

Zřetězení je binární operace definovaná na slovech dané abecedy . Označení:

$A$ - abeceda, sada písmen;
$\alpha$ , , - slova složená z písmen; $\beta$ $\gamma$
$a_{1}\ldots a_{n}$ a - psáno v řadě a číslována písmena dvou slov. $b_{1}\ldots b_{m}$

Jestliže a jsou slova v abecedě , pak zřetězení slov a , které v tomto článku označujeme jako , je slovo ve stejné abecedě definované rovností ${\displaystyle \alpha =a_{1}\ldots a_{n))$ ${\displaystyle \beta =b_{1}\ldots b_{m))$ $A$ $\alpha$ $\beta$ $\alpha \cdot \beta$ $\gamma$ $A$

${\displaystyle \gamma =\alpha \cdot \beta =a_{1}\ldots a_{n}b_{1}\ldots b_{m))$ .

Například, jestliže a jsou slova v abecedě obsahující všechna písmena latinské abecedy , pak $\alpha =media$ $\beta =wiki$ ${\displaystyle A=\{a,b,c,\ldots ,z\))$

$\gamma=\alpha \cdot \beta=media\cdot wiki=mediawiki$ .

Vlastnosti zřetězení

Operace zřetězení je asociativní . To znamená, že pokud potřebujete zřetězit tři slova, výsledek se nezmění umístěním závorek: , a zároveň . $(wiki\cdotmedia)\cdotpedia=wikimediapedie$ $wiki\cdot (media\cdot pedia)=wikimediapedie$
Operace zřetězení je nekomutativní . Opravdu , ale . Od permutace operandů se mění výsledek operace, což znamená její nekomutativnost. $wiki\cdotmedia=wikimedia$ $media\cdot wiki=mediawiki\neq wikimedia$
Prázdné slovo - , - je neutrální prvek (jednotka) operace zřetězení. To znamená, že pokud je prázdné slovo, pak rovnost platí pro jakékoli slovo: $\varepsilon$ $\varepsilon$ $\alpha$

$\varepsilon \cdot \alpha =\alpha \cdot \varepsilon =\alpha$ .

Množina všech slov v abecedě tvoří monoid (tzv. "volný monoid" ). $A^{*}$
Množina všech neprázdných slov v abecedě tvoří pologrupu . ${\displaystyle A^{*}\setminus \{\varepsilon \))$
Délka (počet písmen) zřetězení slov se rovná součtu délek operandů:

$|\alpha \cdot \beta |=|\alpha |+|\beta |$ .

Iterace

Operace zřetězení slov, stejně jako operace násobení čísel , generuje operaci iterace (neboli „umocnění“) . Nechť je nějaké slovo v abecedě a je nezáporné celé číslo . Potom bude mocninou slova označená jako slovo ve stejné abecedě definované rovností: $\alpha$ $A$ $n$ $n$ $\alpha$ ${\displaystyle \alpha ^{n))$ $\gamma$ $A$

${\begin{matrix}\gamma =\alpha ^{n}=&\underbrace {\alpha \cdot \ldots \cdot \alpha }\\&n\end{matrix))$

(slovo jednou zopakujte). Příklad: "a" 3 "aaa". $\alpha$ $n$

V tomto případě se stupeň podle definice rovná prázdnému slovu , . $n=0$ $\alpha ^{0}$ $\varepsilon$

V informatice

Operace zřetězení je definována pro datové typy , které mají sekvenční strukturu ( seznam , fronta , pole a řada dalších). V obecném případě je výsledkem zřetězení dvou objektů objekt získaný postupným přidáváním všech prvků objektu , počínaje prvním až po konec objektu . $A$ $B$ $C=A\cdot B$ $B$ $A$

Z důvodu pohodlí a efektivity se rozlišují dvě formy operace zřetězení:

Úprava zřetězení. Výsledek operace se tvoří v levém operandu.
Nemodifikující zřetězení. Výsledkem je nový objekt, operandy zůstávají nezměněny.

Viz také

Hledání ve slovníku