Просмотр кода страницы Конкатенация

'''Конкатена́ция''' ({{lang-la|concatenatio}} «присоединение цепями; сцепле́ние») — операция склеивания объектов линейной структуры<ref>{{Статья|ссылка=https://old.mccme.ru//circles//oim/mmks/works2024/zelenin2.pdf|автор=Борзенко Владимир Игоревич|заглавие=Кратная конкатенация|год=2024|язык=русский|издание=Школа №1553 им. В.И. Вернадского|страницы=1}}</ref>, обычно [[Строковый тип|строк]]. Например, конкатенация слов «микро» и «мир» даст слово «микромир».

== В математике ==
'''Конкатенация''' — [[бинарная операция]], определённая на [[слово#В математике|словах]] данного [[алфавит#В математике|алфавита]]. Обозначения:
* <math>A</math> — алфавит, набор букв;
* <math>\alpha</math>, <math>\beta</math>, <math>\gamma</math> — слова, составленные из букв;
* <math>a_1 \ldots a_n</math> и <math>b_1 \ldots b_m</math> — записанные подряд и пронумерованные буквы двух слов.
Если <math>\alpha=a_1 \ldots a_n</math> и <math>\beta=b_1\ldots b_m</math> — слова из алфавита <math>A</math>, то конкатенацией слов <math> \alpha</math> и <math> \beta</math>, которую обозначим в этой статье как <math> \alpha \cdot \beta</math>, будет слово <math> \gamma</math> из того же алфавита <math> A</math>, определяемое равенством

<center>
<math> 
\gamma = \alpha\cdot\beta = a_1\ldots a_n b_1 \ldots b_m</math>.
</center>

Например, если <math> \alpha = media</math> и <math> \beta = wiki</math> — слова из алфавита <math> A = \{a,b,c,\ldots,z\}</math>, содержащем все [[буква|буквы]] [[Латинский алфавит|латинского алфавита]], то

<center>
<math> 
\gamma = \alpha \cdot \beta = media \cdot wiki = mediawiki 
</math>.
</center>

=== Свойства конкатенации ===
* Операция конкатенации [[Ассоциативная операция|ассоциативна]]. То есть, если нужно выполнить конкатенацию трёх слов, то от расстановки скобок результат не изменится: <math> (wiki \cdot media) \cdot pedia = wikimediapedia </math>, и в то же время <math> wiki \cdot (media \cdot pedia) = wikimediapedia </math>.
* Операция конкатенации [[Коммутативная операция|некоммутативна]]. В самом деле, <math> wiki \cdot media = wikimedia</math>, но <math> media \cdot wiki = mediawiki \neq wikimedia</math>: от перестановки [[Операнд|операндов]] меняется результат операции, что и означает её некоммутативность.
* [[Слово (формальный язык)|Пустое слово]] <math> \varepsilon</math> — является [[нейтральный элемент|нейтральным элементом]] (единицей) операции конкатенации. То есть, если <math> \varepsilon</math> — пустое слово, то для любого слова <math> \alpha</math> выполнено равенство:

<center>
<math> 
\varepsilon \cdot \alpha = \alpha \cdot \varepsilon = \alpha</math>.
</center>

* Множество <math>A^*</math> всех слов в алфавите образует [[моноид]] (так называемый {{нп5|Свободный моноид|«свободный моноид»|en|Free monoid}}).
* Множество <math>A^*\setminus \{\varepsilon\}</math> всех непустых слов в алфавите образует [[полугруппа|полугруппу]].
* [[Слово#В математике|Длина]] (количество букв) конкатенации слов равна сумме длин [[Операнд|операндов]]:

<center>
<math> 
|\alpha\cdot\beta| = |\alpha| + |\beta| 
</math>.
</center>

=== Итерации ===
Операция конкатенации слов, подобно операции [[Умножение|умножения чисел]], порождает операцию '''итерации''' (или '''возведения в степень'''). Пусть <math> \alpha</math> — некоторое слово из алфавита <math> A</math>, а <math> n</math> — [[Целые числа|целое]] неотрицательное число. Тогда <math>n</math>-ой степенью слова <math>\alpha</math>, обозначаемой <math>\alpha^n</math>, будет слово <math>\gamma</math> в том же алфавите <math>A</math>, определяемое равенством:

<center>
<math>
\begin{matrix}
\gamma = \alpha^n = & \underbrace{\alpha\cdot\ldots\cdot\alpha} \\
& n
\end{matrix}
</math>
</center>
(повтор слова <math> \alpha</math> <math>n</math> раз). Пример: «a»<sup>3</sup>=«aaa».

В случае <math> n=0</math>, степень <math> \alpha^0</math> по определению полагается равной пустому слову, <math> \varepsilon</math>.

== В информатике ==
Операция '''конкатенации''' определяется для [[Тип данных|типов данных]], имеющих структуру последовательности ([[Линейный список|список]], [[Очередь (программирование)|очередь]], [[Массив (программирование)|массив]] и ряд других).В общем случае, результатом конкатенации двух объектов <math>A</math> и <math>B</math> является объект <math>C = A\cdot B</math><ref>{{Книга|ссылка=https://users.math-cs.spbu.ru/~okhotin/teaching/tcs3_2018/okhotin_tcs3_2018_l1.pdf|автор={{nobr|Александр Охотин}}|заглавие=Формальные языки и действия над ними. Регулярные
выражения. Детерминированные и недетерминированные
конечные автоматы. Детерминизация недетерминированных
автоматов, преобразование регулярных выражений к
автоматам∗|год=2018|язык=русский|страницы=2|страниц=12}}</ref>, полученный поочерёдным добавлением всех элементов объекта <math>B</math>, начиная с первого, в конец объекта <math>A</math>.

Из соображений удобства и эффективности различают две формы операции конкатенации:
# Модифицирующая конкатенация. Результат операции формируется в левом операнде.
# Немодифицирующая конкатенация. Результатом является новый объект, операнды остаются неизменными.

== См. также ==
{{wiktionary|конкатенация}}
* [[Перебор по словарю]]

== Примечания ==
{{примечания}}


{{compu-prog-stub}}
{{math-stub}}
{{нет ссылок|дата=2011-12-21}}

[[Категория:Математические операции]]
[[Категория:Алгоритмы]]
[[Категория:Операции в программировании]]