Sammankoppling

Sammanfogning ( lat. concatenatio "fastsättning med kedjor; länkning") är operationen av limning av föremål med en linjär struktur, vanligtvis strängar . Till exempel kommer sammanlänkningen av orden "mikro" och "värld" att ge ordet "mikrovärld".

I matematik

Sammankoppling är en binär operation definierad på orden i ett givet alfabet . Beteckningar:

$A$ - alfabetet, en uppsättning bokstäver;
$\alfa$ , , - ord som består av bokstäver; $\beta$ $\gamma$
$a_{1}\ldots a_{n}$ och - skrivna i rad och numrerade bokstäver med två ord. $b_{1}\ldots b_{m}$

Om och är ord i alfabetet , så är sammanlänkningen av ord och , som vi betecknar i denna artikel som , ett ord i samma alfabet , definierat av likheten ${\displaystyle \alpha =a_{1}\ldots a_{n))$ ${\displaystyle \beta =b_{1}\ldots b_{m))$ $A$ $\alfa$ $\beta$ $\alpha \cdot \beta$ $\gamma$ $A$

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

Till exempel, om och är ord i ett alfabet som innehåller alla bokstäver i det latinska alfabetet , då $\alpha =media$ $\beta =wiki$ $A=\{a,b,c,\ldots ,z\}$

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

Sammankopplingsegenskaper

Sammankopplingsoperationen är associativ . Det vill säga, om du behöver sammanfoga tre ord, kommer resultatet inte att ändras från placeringen av parenteser: , och samtidigt . $(wiki\cdotmedia)\cdotpedia=wikimediapedia$ $wiki\cdot (media\cdot pedia)=wikimediapedia$
Sammankopplingsoperationen är icke- kommutativ . Visserligen , men . Från permutationen av operanderna ändras resultatet av operationen, vilket innebär att den inte är kommutativ. $wiki\cdotmedia=wikimedia$ $media\cdot wiki=mediawiki\neq wikimedia$
Det tomma ordet - , - är ett neutralt element (enhet) i sammanlänkningsoperationen. Det vill säga, om är ett tomt ord, så gäller likheten för vilket ord som helst: $\varepsilon$ $\varepsilon$ $\alfa$

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

Mängden av alla ord i alfabetet bildar en monoid (den så kallade "fria monoiden" ). $A^{*}$
Uppsättningen av alla icke-tomma ord i alfabetet bildar en halvgrupp . $A^{*}\setminus \{\varepsilon \}$
Längden (antal bokstäver) av sammanlänkningen av ord är lika med summan av längden på operanderna:

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

Iterationer

Operationen av sammanlänkning av ord, som operationen av multiplikation av tal , genererar operationen för iteration (eller "höjning till en potens") . Låt vara något ord i alfabetet , och vara ett icke-negativt heltal . Då blir ordets e potens , betecknad med , ordet i samma alfabet , definierat av likheten: $\alfa$ $A$ $n$ $n$ $\alfa$ ${\displaystyle \alpha ^{n))$ $\gamma$ $A$

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

(upprepa ordet en gång). Exempel: "a" 3 = "aaa". $\alfa$ $n$

I fallet är graden per definition lika med det tomma ordet . $n=0$ $\alpha ^{0}$ $\varepsilon$

Inom datavetenskap

Sammankopplingsoperationen definieras för datatyper som har en sekvensstruktur ( lista , kö , array och ett antal andra). I det allmänna fallet är resultatet av sammanlänkningen av två objekt objektet som erhålls genom att sekventiellt lägga till alla element i objektet , med början från det första till slutet av objektet . $A$ $B$ $C=A\cdot B$ $B$ $A$

Av bekvämlighets- och effektivitetsskäl särskiljs två former av sammanlänkningsoperationen:

Ändring av sammanlänkning. Resultatet av operationen bildas i den vänstra operanden.
Icke-modifierande sammanlänkning. Resultatet är ett nytt objekt, operanderna förblir oförändrade.

Se även

Ordbokssökning