Слово параметра - Parameter word

В математическом исследовании комбинаторика слов, а слово параметра это нить над данным алфавит имея некоторое количество символы подстановки.^[1] Набор строк, соответствующих заданному слову параметра, называется набор параметров или же комбинаторный куб. Можно составить параметрические слова для получения меньших субкубов данного комбинаторного куба. У них есть приложения в Теория Рамсея и в компьютерных науках при обнаружении повторяющийся код.

Определения и обозначения

Формально ${ displaystyle k}$ -параметр слово длины ${ displaystyle n}$ , по заданному алфавиту ${ displaystyle A}$ , представляет собой последовательность ${ displaystyle n}$ персонажей, некоторые из которых могут быть взяты из ${ displaystyle A}$ и другие из которых ${ displaystyle k}$ отдельные символы подстановки ${ displaystyle * _ {1}, * _ {2}, ldots, * _ {k}}$ . Каждый подстановочный знак должен появляться хотя бы один раз, но может встречаться и несколько раз, и подстановочные знаки должны появляться в порядке, заданном их индексами: первый подстановочный знак в слове должен быть ${ displaystyle * _ {1}}$ , следующий, отличный от ${ displaystyle * _ {1}}$ должно быть ${ displaystyle * _ {2}}$ и т. д. Как частный случай, слово в данном алфавите без каких-либо подстановочных знаков называется словом с 0 параметрами. Для слов с одним параметром нижние индексы могут быть опущены, поскольку нет неоднозначности между различными символами подстановки. Набор всех ${ displaystyle k}$ -параметр слова закончились ${ displaystyle A}$ , длины ${ displaystyle n}$ , является обозначенный ${ Displaystyle А { tbinom {п} {к}}}$ .^[1]

А ${ displaystyle k}$ -параметр слово представляет собой набор ${ displaystyle | A | ^ {k}}$ строки (0-параметрические слова), полученные заменой символа ${ displaystyle A}$ для каждого подстановочного знака. Этот набор струн называется набор параметров из комбинаторный куб, и ${ displaystyle k}$ называется его размерностью. Одномерный комбинаторный куб можно назвать комбинаторная линия.^[1]

В комбинаторном кубе каждая копия определенного подстановочного символа должна иметь одинаковую замену. Обобщение слов параметров позволяет контролируемым образом заменять разные копии одного и того же символа подстановки разными символами алфавита. Если ${ displaystyle A}$ это алфавит и ${ displaystyle G}$ это группа с действие на ${ displaystyle A}$ , затем ${ displaystyle G}$ -помеченный слово параметра - это ${ displaystyle k}$ -параметр word вместе с назначением элемента группы каждому символу подстановки в слове. Первому появлению каждого подстановочного символа должен быть присвоен элемент идентичности группы. Затем строки, представленные помеченным параметрическим словом, получаются путем выбора символа ${ displaystyle A}$ для каждого символа подстановки и подстановки результата объединения этого символа с элементом группы, маркирующим каждую копию этого символа. Набор всех ${ displaystyle G}$ -помеченный ${ displaystyle k}$ -параметр слова закончились ${ displaystyle A}$ , длины ${ displaystyle n}$ , является обозначенный ${ displaystyle [A, G] { tbinom {n} {k}}}$ .^[1]

Пример

В игре крестики-нолики, клеткам игрового поля можно задать две целочисленные координаты ${ Displaystyle (х, у)}$ из алфавита ${ displaystyle {1,2,3 }}$ . Объединение этих двух координат дает строку, представляющую каждую ячейку, одну из девяти строк. ${ Displaystyle 11,12,13,21,22,23,31,32,}$ или же ${ displaystyle 33}$ . В этом алфавите семь однопараметрических слов длины два, слова ${ displaystyle 1 *, 2 *, 3 *, * 1, * 2, * 3,}$ и ${ displaystyle **}$ . Соответствующие комбинаторные линии образуют семь из восьми линий трех ячеек в ряду доски для игры в крестики-нолики; например, однопараметрическое слово ${ displaystyle 2 *}$ соответствует комбинаторной прямой ${ displaystyle {21,22,23 }}$ , а однопараметрическое слово ${ displaystyle **}$ соответствует комбинаторному линия ${ displaystyle {11,22,33 }}$ .^[2]

Однако в этом наборе комбинаторных линий отсутствует одна из восьми выигрышных линий игры в крестики-нолики: антидиагональный линия ${ displaystyle {13,22,31 }}$ . Можно получить эту строку как комбинаторную строку (без включения каких-либо других комбинаций ячеек, которые были бы недопустимыми для крестиков-ноликов), используя группу с двумя элементами и действие, в котором неидентификационный элемент меняет местами буквы алфавита ${ displaystyle 1}$ и ${ displaystyle 3}$ при выходе из элемента ${ displaystyle 2}$ на месте. Для этого действия существует восемь помеченных однопараметрических слов длины два, семь из которых получаются из немаркированных однопараметрических слов с использованием идентификационной метки для всех подстановочных знаков. Эти семь имеют те же комбинаторные линии, что и раньше. Восьмое обозначенное слово состоит из слова ${ displaystyle **}$ помеченный элементом идентичности для его первого ${ displaystyle *}$ и реверсивный нетождественный элемент для второго ${ displaystyle *}$ ; ее комбинаторная линия - это последняя выигрышная линия доски для крестиков-ноликов, ${ displaystyle {13,22,31 }}$ .^[2]

Сочинение

Для трех заданных целочисленных параметров ${ Displaystyle п geq м geq k}$ , можно комбинировать два параметрических слова, ${ displaystyle f in A { tbinom {n} {m}}}$ и ${ displaystyle g in A { tbinom {m} {k}}}$ , чтобы создать другое слово параметра ${ displaystyle f circ g in A { tbinom {n} {k}}}$ . Для этого просто замените каждую копию ${ displaystyle i}$ th подстановочный знак в ${ displaystyle f}$ посредством ${ displaystyle i}$ й персонаж в ${ displaystyle g}$ . Это обязательно даст слово длины ${ displaystyle n}$ который использует каждый из подстановочных знаков в ${ displaystyle g}$ хотя бы один раз в порядке возрастания, чтобы получить действительный ${ displaystyle k}$ -параметр слово длины ${ displaystyle n}$ . Это понятие композиции также может быть расширено до композиции помеченных слов параметров (как с использованием одного и того же алфавита, так и группового действия), применяя групповое действие к заменяемым символам без подстановочного знака и составляя групповые метки для подстановочных символов, заменяемых символами. Подмножество комбинаторного куба - это комбинаторный куб меньшего размера, если он может быть получен посредством композиции таким образом.^[1]

Комбинаторное перечисление

Количество слов параметров в ${ Displaystyle А { tbinom {п} {к}}}$ для алфавита размера ${ displaystyle r}$ является ${ displaystyle r}$ -Число Стирлинга второго рода ${ displaystyle textstyle left {{r + n at r + k} right } _ {r}}$ . Эти числа подсчитывают количество разделов целых чисел в диапазоне ${ Displaystyle [1, г + п]}$ в ${ displaystyle r + k}$ непустые подмножества такие, что первые ${ displaystyle r}$ целые числа принадлежат различным подмножествам. Перегородки этого типа можно разместить в биективная эквивалентность с параметрическими словами, создавая слово с символом для каждого из ${ displaystyle n}$ целые числа в диапазоне ${ Displaystyle [г + 1, п + г]}$ , устанавливая значение этого символа как целое число в ${ displaystyle [1, r]}$ принадлежащий одному и тому же подмножеству раздела, или подстановочный знак для каждого подмножества раздела, который не содержит целого числа в ${ displaystyle [1, r]}$ . В ${ displaystyle r}$ -Числа Стирлинга подчиняются простой отношение повторения по которому они могут быть легко рассчитаны.^[3]^[4]

Приложения

В Теория Рамсея, слова параметров и комбинаторные кубы могут быть использованы для формулировки Теорема Грэма – Ротшильда., согласно которому для каждого конечного алфавита и действия группы и каждой комбинации целочисленных значений ${ displaystyle m}$ , ${ displaystyle k}$ , и ${ displaystyle r}$ , существует достаточно большое число ${ displaystyle n}$ так что если каждый ${ displaystyle k}$ -размерный комбинаторный куб над строками длины ${ displaystyle n}$ назначается один из ${ displaystyle r}$ цветов, то существует ${ displaystyle m}$ -размерный комбинаторный куб, все ${ displaystyle k}$ -размерный субкубы имеют одинаковый цвет. Этот результат является ключевой основой для структурная теория Рамсея, и используется для определения Число Грэма, огромное количество используется для оценки стоимости ${ displaystyle n}$ для определенного сочетания значений.^[1]

В Информатика, в задаче поиска повторяющийся код, исходный код для данной процедуры или модуля может быть преобразован в слово параметра с помощью преобразование его в последовательность токенов, и для каждого имени переменной или подпрограммы, заменяя каждую копию того же имени одним и тем же подстановочным знаком. Если код дублируется, результирующие слова параметров останутся равными, даже если некоторые переменные или подпрограммы были переименованы. Более сложные алгоритмы поиска могут находить длинные повторяющиеся разделы кода, которые образуют подстроки более крупных репозиториев исходного кода, позволяя заменять друг друга подстановочными знаками.^[5]

Важный частный случай параметрических слов, хорошо изученный в комбинаторике слов, дается формулой частичные слова. Это строки с подстановочными знаками, которые можно подставлять независимо друг от друга, не требуя, чтобы некоторые из заменяемых символов были равны или контролировались групповым действием. На языке слов параметров частичное слово может быть описано как слово параметра, в котором каждый символ подстановки появляется ровно один раз. Однако из-за отсутствия повторения подстановочных символов частичные слова могут быть записаны проще, опуская нижние индексы подстановочных символов.^[6]