«Комбинаторные свойства частичных слов ...»

Уральский ордена Трудового Красного знамени

государственный университет имени А. М. Горького

На правах рукописи

Гамзова Юлия Васильевна

Комбинаторные свойства частичных слов

01.01.09 Дискретная математика и математическая кибернетика

Диссертация на соискание ученой степени

кандидата физико-математических наук

научные руководители кандидат физико-математических наук, доцент Шур А. М., кандидат физико-математических наук, доцент Суханов Е. В.

Екатеринбург 2006 Оглавление Введение 1. Понятие о частичных словах.................. 2. Определения и обозначения.................. 3. Краткий обзор исследований по частичным словам..... 4. Вопросы, рассматриваемые в диссертации.......... 5. Основные результаты диссертации.............. I Свойство взаимодействия периодов §1 Существование длины взаимодействия............ §2 Точные оценки в частных случаях............... §3 Формулировка прямой и обратной задачи. Бланки и расстановки.............................. §4 Решение обратной задачи.................... §5 Решение исходной задачи.................... II Статистические закономерности §6 Идея алгоритма......................... §7 Количество расстановок с заданной характеристической расстановкой............................. §8 Построение вспомогательных таблиц............. §9 Анализ полученных результатов................ III Свойство взаимодействия локальных периодов §10 Используемая техника...................... §11 Разрезы.............................. §12 Алгоритм проверки наличия в расстановке специальной подпоследовательности..................... §13 Модификации алгоритма.................... Введение 1. Понятие о частичных словах Символьные последовательности, или слова, представляют собой важный и популярный объект комбинаторных исследований. Задачи, связанные со словами, возникали в различных областях математики и других наук и привели к возникновению отдельного раздела дискретной математики, занимающейся изучением комбинаторных свойств слов. Историю комбинаторики слов принято отсчитывать от 1906 года, когда была опубликована работа [1]. С тех пор комбинаторика слов плодотворно развивалась и к настоящему времени обрела четкие контуры и собственную богатую проблематику. Имеющаяся литература весьма обширна. Упомянем здесь монографии [2–4], а также [5] и ряд других глав трехтомного Справочника по формальным языкам.

Частичные слова представляют собой естественное обобщение понятия обычного слова. Частичное слово это обычное слово, в котором часть букв по каким-то причинам отсутствует. Изучение комбинаторных свойств частичных слов в явном виде началось совсем недавно, в году, с работы [6].

Задачи, в которых возникают частичные слова, можно разделить на два типа. В задачах первого типа некоторая часть информации нам не важна (вне зависимости от того, доступна она или нет). Примером может служить задача поиска в тексте по шаблону, когда шаблон содержит символ (или символы) со значением что угодно. В задачах второго типа некоторая часть информации для нас важна, но по каким-либо причинам недоступна. По имеющейся части информации и некоторым дополнительным условиям необходимо полностью восстановить информацию.

Примером является задача восстановления фрагментов файлов, повреждённых при передаче или в результате порчи носителя. Очень интересными представляются также задачи молекулярной биологии (см. [7]), в частности, задача реконструкции нуклеотидных цепочек ДНК по частично расшифрованным фрагментам.

В данной работе изучаются комбинаторные свойства частичных слов, связанные с локальной и глобальной периодичностью.

2. Определения и обозначения 1. Пусть A конечный алфавит, A+ и A соответственно свободная полугруппа и свободный моноид над этим алфавитом. Элементы из A+ и A называются словами, а множества слов языками. Длина слова W обозначается через |W |. Для данной буквы a A обозначим через |U|a количество букв a в слове U. На слово длины n можно смотреть как на функцию из множества {1,..., n} в алфавит. Частичное слово длины n над алфавитом A это частичная функция Значение W (i) мы будем называть буквой в i-ой позиции слова W.

Слова (обычные и частичные) мы обозначаем буквами P, Q, R, S, T, U, V, W (с индексами), пустое слово обозначаем через.

2. Кроме конечных частичных слов, мы будем рассматривать также бесконечные частичные слова. Частичное Z-слово (-слово) над алфавитом A это частичная функция W : Z A (соответственно, 3. Через D(W ) обозначим область определения частичной функции W (i). Каждому частичному слову W над алфавитом A мы можем поставить в соответствие обычное слово W над расширенным алфавитом A = A { } следующим образом:

Отображение W W является биекцией. В дальнейшем под частичным словом мы будем понимать именно последовательность символов над алфавитом A { }.

Заметим, что роль символа существенно отличается от роли остальных алфавитных символов. Его значение таково: на этой позиции должен находиться алфавитный символ, неизвестно какой. В [6] символ назывался дырой. Мы используем термин джокер, который кажется нам более уместным. Отличные от джокера символы алфавита, будем, как обычно, называть буквами.

4. Обычное слово W имеет период p, если W (i) = W (i + p) для всех i = 1,..., |W | p. Понятие периода можно распространить на частичные слова двумя естественными способами, предложенными в [6]. Приведём соответствующие определения.

Частичное слово W имеет период p, если для любых i, j D(W ) Например, слово W = ab a cabc имеет период 3.

Частичное слово W имеет локальный период p, если для любого i такого, что i, i + p D(W ), выполняется W (i) = W (i + p). Для обычных слов наличие локального периода p всегда влечет наличие периода p, но это свойство не выполняется для частичных слов. Например, частичное слово W = abc bcd имеет локальный период 3, но не имеет периода 3. Заметим, что частичное слово имеет период p тогда и только тогда, когда в нём все джокеры можно заменить буквами так, что полученное обычное слово будет иметь период p.

5. Слово V называется подсловом слова W (или говорят, что W содержит V, обозначается V W ), если W = P V Q для некоторых слов P, Q. При этом мы говорим, что V является Если V подслово W, начинающееся в i-й и заканчивающееся в j-й позиции, то используется запись V = W (i... j).

Любое представление слова в виде произведения подслов мы называем разбиением этого слова.

6. Будем обозначать через n нижнее целое, через n верхнее целое числа n.

3. Краткий обзор исследований по частичным словам С момента возникновения комбинаторики частичных слов исследования по частичным словам велись довольно интенсивно и уже получено много интересных результатов. Комбинаторика частичных слов находится в начальной фазе развития, когда основной интерес представляет перенесение комбинаторных свойств обычных слов на более широкий класс частичных слов. Уже в [6] были получены для частичных слов аналоги некоторых комбинаторных свойств обычных слов. В частности, рассматривалось в частных случаях свойство взаимодействия периодов частичных слов. Исследование этого свойства продолжалось и в других работах. Свойство взаимодействия периодов тесно связано с нашими исследованиями; оно будет рассмотрено в следующем параграфе.

Рассматривались и другие свойства периодических частичных слов.

В частности, в [8] проводились исследования аналога теоремы о критическом разбиении. Введем необходимые определения. Число p N называется локальным периодом (обычного) слова W в позиции k, 0 < k < |W |, если слово W (n1... n2 ) имеет период p, где n1 = max{k p + 1, 1}, n2 = min{k + p, |W |}. Cмысл понятия локального периода таков: в pокрестности позиции k слово W ведет себя как периодическое с периодом Разбиение W = UV называется критическим, если минимальный локальный период слова W в позиции |U| совпадает с его минимальным периодом.

Теорема 0.1 (теорема о критическом разбиении, [9, 10]). Всякое слово W, имеющее минимальный период p и содержащее не менее двух различных букв, допускает критическое разбиение W = UV с условием |U| < p.

Из доказательства этой теоремы следует эффективный алгоритм построения этого разбиения.

Введем для частичных слов понятие, аналогичное понятию локального периода для обычных слов. Число p N называется точечным периодом частичного слова W в позиции k, 0 < k < |W |, если слово W (n1... n2 ) имеет период p, где n1 = max{k p + 1, 1}, n2 = min{k + p, |W |}. Заметим, что для данного определения можно использовать любое из двух определений периода частичного слова, т.к. длина периодической части слишком мала для того, чтобы успели проявиться различия между локальной и глобальной периодичностью.

В [8] доказан условный аналог теоремы о критическом разбиении для частичных слов с одним джокером, т.е. выявлены необходимые и достаточные условия наличия в слове критического разбиения. В [11] этот результат обобщен для частичных слов с любым количеством джокеров.

Также для частичных слов проводились исследования множества периодов. Обозначим через P(U) множество периодов слова U. Для обычных слов известен следующий результат.

Теорема 0.2 ([12]). Для любого слова U над алфавитом A существует слово V длины |U| над алфавитом {0, 1} такое, что P(V ) = P(U).

Доказательство этой теоремы, приведенное в [12], является довольно сложным. В [13] дается более простое конструктивное доказательство.

Алгоритм из [13] был обобщен в [14] для частичных слов с одним джокером, в [15] с двумя джокерами, в [16] с произвольным количеством джокеров.

Также изучались свойства примитивных частичных слов. Будем говорить, что частичное слово U содержится в частичном слове V (U V ), если |U| = |V |, D(U) D(V ) и U(i) = V (i) для всех i D(U). Частичные слова U и V называются совместимыми (U V ), если существует слово W, в котором содержатся и слово U, и слово V. Обычное слово U называется примитивным, если не существует слова V такого, что U = V n, n 2. Частичное слово U называется примитивным, если не существует слова V такого, что U V n, n 2. В [17] приведены для примитивных частичных слов аналоги известных свойств примитивных обычных слов. В [18] приведен для частичных слов аналог известного критерия примитивности обычных слов, позволяющий создать линейный по времени алгоритм проверки примитивности частичного слова.

Большой интерес представляет изучение множеств частичных слов (ч-языков). В 2004 году Ф. Бланше-Садри сделала первый шаг в изучении свойств ч-языков, введя понятие ч-кодов в статье [19].

Напомним, что непустое множество слов X A+ называется кодом, если для всех натуральных m, n и слов U1,..., Um, V1,..., Vn X выполняется Непустое множество частичных слов X A+ называется ч-кодом, если для всех натуральных m, n и частичных слов U1,..., Um, V1,..., Vn X выполняется В [19] приведены различные свойства ч-кодов. В [20] приводится алгоритм для проверки, является ли данный ч-язык ч-кодом.

П. Лёйпольд в статье [21] предложил несколько способов получения ч-языков, а также привел некоторые свойства этих языков.

Для получения k-проколотого языка в каждом слове обычного языка некоторые символы (не более k) заменяются джокерами. Проколотые языки можно генерировать (например, при помощи грамматик) двумя способами: либо сначала генерируется обычный язык, а затем выполняется прокалывание, либо джокер рассматривается как терминальный символ грамматики, порождающей сразу проколотый язык.

Обозначим через C (k ) класс всех k-проколотых языков, полученных с помощью прокалывания языков из класса языков C, а через C(k ) класс языков, порожденных грамматиками того же класса, что и класс языков C, с дополнительным терминальным символом. Обозначим через REG (CF, CS, RE) класс всех языков, порожденных регулярными (соответственно, контекстно-свободными, контекстно-зависимыми, любыми) грамматиками.

Предложение 0.1 ([21]). Для C {REG, CF, CS, RE} и любого натурального k класс языков C (k ) является собственным подмножеством класса C(k ).

В [21] также приведен несколько другой подход к рассмотрению кодов в случае частичных слов. В отличие от ч-кода, элементами которого являются произвольные частичные слова, k-проколотый код является замыканием обычного кода относительно всевозможных k-прокалываний.

Язык, порожденный проколотым кодом, содержит все частичные слова, которые могли быть получены из произведений исходных кодовых слов в результате потери некоторой части букв. В [21] приведены различные свойства k-проколотых кодов.

4. Вопросы, рассматриваемые в диссертации Перенесение свойств обычных слов на частичные слова приводит к постановкам разной значимости. Рассмотрение вместо обычных слов частичных слов может привести к расширению задачи или к ее сужению. Богатую проблематику для исследований по частичным словам предоставляет одно из ключевых свойств обычных периодических слов свойство взаимодействия периодов. Свойство взаимодействия периодов (в стандартной формулировке) заключается в том, что достаточно длинное слово с периодами p и q имеет также и производный период НОД(p, q).

Точная формулировка для обычных слов содержится в теореме ФайнаВильфа, которую мы приведём здесь в удобных для нас обозначениях.

Теорема 0.3 (Файн, Вильф [22]). Пусть p и q – натуральные числа, тогда каждое слово длины не менее, чем p + qНОД(p, q) с периодами p и q имеет период НОД(p, q). Указанная оценка является точной.

Свойство взаимодействия периодов интенсивно изучалось и был получен ряд обобщений теоремы Файна-Вильфа. В частности, были получены результаты для трех и более периодов ([23–27]), для абелевых периодов ([28]), для неравенств ([29]), а также для полупериодических слов ([30]), для двумерных слов ([31]), для слов на деревьях ([32–34]).

Для частичных слов выполнение свойства взаимодействия периодов зависит не только от длины слова, но и от количества и расположения в нем джокеров, причем задача может ставиться как для периодов, так и для локальных периодов. Все это приводит к разнообразию нетривиальных постановок задач. Вначале рассмотрим соответствующие постановки для периодов.

1. Верно ли, что частичное слово достаточно большой длины, имеющее периоды p и q и фиксированное число джокеров k, обязательно имеет период НОД(p, q)?

2. Если ответ на первый вопрос утвердительный, то какой длины должно быть частичное слово, имеющее периоды p, q и содержащее k джокеров, чтобы оно также гарантированно имело период НОД(p, q) (тривиальный случай длины k+1 исключим из рассмотрения)?

Наименьшую такую длину будем называть длиной взаимодействия периодов p и q при наличии k джокеров и обозначать L(k, p, q). Длину взаимодействия естественно рассматривать как функцию от k с параметрами p и q.

Как отмечалось в разных работах (см. [5, 6]), утверждения о взаимодействии произвольных периодов p и q тривиально следуют из аналогичных утверждений для взаимно простых периодов ввиду следующего наблюдения.

Наблюдение. В случае, когда НОД(p, q) = d > 1, можно заменить (частичное) слово U набором, состоящим из d (частичных) слов U1,..., Ud, где Ui = U(i)U(d + i)U(2d + i).... Каждое из этих слов будет иметь взаимно простые периоды p/d, q/d. При этом слово U будет иметь период d тогда и только тогда, когда все Ui имеют период 1.

Таким образом, достаточно исследовать свойство взаимодействия для взаимно простых периодов. В этом случае свойство взаимодействия периодов заключается в том, что в достаточно длинном слове с периодами p и q все буквы должны быть одинаковыми. В дальнейшем мы будем рассматривать только взаимно простые периоды, 2 q < p.

Свойство взаимодействия периодов можно обобщить следующим образом. Для данного частичного слова W рассмотрим множество частичных слов с теми же периодами и той же областью определения. Среди этих слов выберем слово U с максимальным количеством различных букв. Множество всех позиций слова U, содержащих одну и ту же букву, будем называть доменом W. Количество доменов слова W (т.е. количество различных букв в U) назовем размерностью слова W и обозначим через r(W ). Из определений следует, что количество букв в частичном слове не превышает его размерность, а две позиции могут содержать различные буквы только если эти позиции принадлежат разным доменам.

Обобщенное свойство взаимодействия периодов состоит в выполнении некоторых условий для множества доменов частичного слова. Например, выполнение свойства взаимодействия (взаимно простых) периодов в стандартной формулировке эквивалентно тому, что размерность слова равна единице.

Из определений следует, что размерность и множество доменов частичных слов определяются только периодами и областью определения.

Поэтому при изучении свойства взаимодействия периодов мы вместо частичных слов будем рассматривать расстановки. Расстановка R это слово над алфавитом {0, 1}, полученное из частичного слова W с помощью следующего гомоморфизма:

Все частичные слова, которым соответствует данная расстановка R, имеют одинаковую размерность и множество доменов, поэтому мы будем говорить о множестве доменов и размерности расстановки, понимая под этим множество доменов и размерность соответствующих частичных слов.

Следующее несложное предложение показывает одно из направлений обобщения результата теоремы Файна-Вильфа для обычных слов.

Предложение 0.2 ([5]). Если слово U имеет взаимно простые периоды p и q и |U| = p+qr, где 1 r q, то U содержит не более r различных букв.

Наличие в частичном слове W (глобального) периода p накладывает ограничения на множество его доменов: размерность W не превосходит p, т.е. W содержит не более p различных букв. Таким образом, глобальная периодичность является достаточно сильным условием. Для периодических частичных слов имеет смысл пытаться получить аналог приведенного выше предложения, т.е. считать, что обобщенное свойство взаимодействия периодов состоит в выполнении некоторых ограничений для размерности частичного слова.

Таким образом, следует исследовать расстановки, длина которых меньше длины взаимодействия. В этом случае расстановки одинаковой длины с одинаковым количеством джокеров могут иметь различную размерность, и интересным представляется вопрос о доле расстановок определенной размерности.

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

Теорема 0.4 ([6]). Пусть p и q – натуральные числа. Тогда любое частичное слово длины не менее, чем p + q с одним джокером и локальными периодами p и q имеет период НОД(p, q). Указанная оценка является точной.

Однако, если частичное слово содержит более одного джокера, то свойство взаимодействия локальных периодов может вообще не выполняться. Например, частичное слово U с периодами p и q, содержащее два джокера в позициях q+1 и p+1, может содержать в первой позиции любую букву. Приведенный пример показывает, что в частичном слове могут существовать некоторые локальные структуры, которые независимо от длины слова приводят к невыполнению свойства взаимодействия локальных периодов. Таким образом, для локально периодических слов более, чем с одним джокером, можно доказывать лишь условные теоремы. Такие результаты приведены в статьях [35,36]. Мы приведем здесь теорему в удобных для нас обозначениях. Будем называть специальными конечные подпоследовательности позиций джокеров, наличие которых приводит к невыполнению свойства взаимодействия локальных периодов во всем слове.

Теорема 0.5 ([36]). Пусть частичное слово U без специальных подпоследовательностей имеет взаимно простые локальные периоды p и q и содержит k джокеров. Тогда если то U также имеет период 1.

Таким образом, для локально периодических частичных слов, не содержащих специальных подпоследовательностей, выполняется свойство взаимодействия периодов. Однако в бесконечном частичном слове вероятность наличия специальных подпоследовательностей равна единице (если джокеры распределены равномерно, т.е. джокер с равной ненулевой вероятностью может находиться в любой позиции). Исследование специальных подпоследовательностей пока не производилось и представляет большой интерес.

Локальная периодичность накладывает на слово гораздо более слабые ограничения, чем глобальная. В частности, наличие у слова локального периода p не ограничивает размерность слова. Поэтому для локально периодических частичных слов имеет смысл рассматривать в качестве обобщенного свойства взаимодействия локальных периодов выполнение некоторых условий для множества доменов. Выполнение обобщенного свойства взаимодействия локальных периодов тесно связано с наличием в частичном слове специальных подпоследовательностей. Изучение специальных подпоследовательностей позволяет ответить на многие вопросы о множестве доменов частичного слова.

Обратимся теперь к проблемам, решаемым в диссертации. В первой главе диссертации дается ответ на ряд вопросов, связанных со свойством взаимодействия (глобальных) периодов частичных слов. Перечислим эти вопросы.

1. Верно ли, что длина взаимодействия L(k, p, q) существует для любых периодов p и q и количества джокеров k?

2. Какова критическая расстановка джокеров в частичном слове, длина которого на единицу меньше длины взаимодействия?

3. Как длина взаимодействия периодов зависит от количества джокеров в частичном слове?

Для ответа на последний вопрос предполагается 3.1. Оценить рост длины взаимодействия как функции от количества джокеров k в общем случае;

3.2. Вычислить эту длину точно в тех частных случаях, в которых Во второй главе рассматриваются периодические частичные слова, длина которых меньше длины взаимодействия. Для таких слов изучаются статистические закономерности выполнения обобщенного свойства взаимодействия периодов. Мы ответим на следующие вопросы.

1. Чем определяется размерность расстановки?

2. Какова доля расстановок данной размерности r среди всех расстановок длины L с k джокерами и периодами p, q?

Третья глава посвящена изучению свойства взаимодействия локальных периодов частичных Z-слов. Изучаются специальные подпоследовательности.

1. Какой вид имеют специальные подпоследовательности?

2. Каковы необходимые и достаточные условия наличия в слове специальных подпоследовательностей?

3. В каком случае частичное Z-слово содержит хотя бы один бесконечный домен?

4. В каком случае частичное Z-слово содержит только бесконечные 5. Основные результаты диссертации Первая глава диссертации посвящена изучению свойства взаимодействия периодов частичных слов (в стандартной формулировке).

В первом параграфе мы доказываем, что длина взаимодействия L(k, p, q) существует для любых периодов p и q и количества джокеров k и получаем для длины взаимодействия следующую оценку.

Теорема 1.1. Для любых взаимно простых p > q 2 и любого k Равенство достигается в двух случаях: когда k = 0 и когда q = 2 и p делит k.

Во втором параграфе мы находим точные оценки для длины взаимодействия в двух частных случаях: q = 2 и k = 2. Приведем здесь полученные результаты.

Теорема 1.2. Для любого нечетного p и любого k Теорема 1.3. Для любых взаимно простых p > q При более пристальном изучении длины взаимодействия L(k, p, q) как функции от k с параметрами p и q можно заметить, что она имеет, за исключением некоторого начального отрезка, регулярное поведение (см.

рис. 1.4). Если отбросить рассмотренный в Теореме 1.2 случай q = 2 и случай маленьких k, то можно значительно улучшить оценку для длины взаимодействия из Теоремы 1.1. В следующей теореме, являющейся центральным результатом главы 1, эта длина представлена в виде суммы линейной и периодической функций относительно k. Такое представление позволяет получить максимально точную общую (т.е. пригодную для любых p и q) оценку длины взаимодействия.

Теорема 1.4. Пусть p и q взаимно простые натуральные числа, p > q 3, а натуральное число k таково, что k 2p/3 1 при q=3 и k 3p/q +3 при q4. Пусть L(k, p, q) длина взаимодействия периодов p и q при наличии k джокеров. Тогда где функция (k, p, q) является периодической по k с периодом p + q и удовлетворяет следующим условиям:

1. для произвольных p и q 2. для любого периода q и любого > 0 существует p такое, что 3. для произвольных p и q Пример графика зависимости длины взаимодействия от числа джокеров, вместе с графиками верхней и нижней оценок из Теоремы 1.4 и графиком верхней оценки из Теоремы 1.1, приведен на рис. 1.4.

Следствие 1.1. В условиях Теоремы 1.4 длина взаимодействия удовлетворяет неравенству Функция, стоящая в правой части неравенства, является наилучшей верхней оценкой для L(k, p, q) в классе линейных по k функций с параметрами p и q.

Результаты Теорем 1.1 и 1.4 дополняют друг друга. Верхняя оценка для длины взаимодействия Теоремы 1.1 применима при любом количестве джокеров k 0 и любых значениях периодов. Оценка Теоремы 1.4 применима с некоторыми ограничениями, но она существенно точнее, является двусторонней, и позволяет локализовать длину взаимодействия внутри полосы, ширина которой меньше, чем 4q.

Заданные в Теореме 1.4 ограничения на k могут быть незначительно понижены (не более чем на единицу в общем случае, и несколько сильнее, если отдельно рассматривать разные случаи соотношения между p и q). Однако, такое понижение, не меняя сути результата, привело бы к значительному удлинению доказательства.

Полученные результаты позволяют провести интересное сравнение свойств локальной и глобальной периодичности с точки зрения свойства взаимодействия периодов. В отличие от глобальной периодичности, для локальных периодов в общем случае нельзя указать оценку для длины взаимодействия. Для того, чтобы можно было оценить длину взаимодействия, необходимо рассматривать только те расстановки, в которых размещение пропущенных символов удовлетворяет некоторому достаточно обременительному ограничению (см. обсуждение на с.11). Из Теоремы 0.5 следует, что в этом случае взаимодействие локальных периодов гарантировано, если доля пропущенных символов в слове не превосходит величину 2/(p + q), т.е. обратно пропорциональна большему периоду. В то же время, оценка из Теоремы 1.4 показывает, что допустимая (для гарантированного взаимодействия периодов) доля пропущенных символов в периодическом частичном слове может быть существенно большей; а именно, величина k/L (p + q 2)/pq обратно пропорциональна меньшему периоду.

Параграфы с третьего по пятый посвящены доказательству теоремы 1.4. В третьем параграфе формулируется обратная задача: задана длина слова L и его периоды p, q, необходимо найти минимальное количество джокеров, при котором слово может не иметь периода 1. В четвертом параграфе приводится решение обратной задачи. Мы определяем специальную расстановку джокеров в слове, доказываем, что при определенных условиях специальная расстановка является оптимальной, т.е именно при такой расстановке достигается искомое минимальное количество джокеров. Затем мы определяем количество джокеров в специальной расстановке. В пятом параграфе мы получаем решение исходной задачи.

Вторая глава посвящена статистическим закономерностям взаимодействия периодов.

Пусть взаимно простые периоды p и q, p > q фиксированы. Будем обозначать через M(r, L, k) множество всех расстановок длины L, содержащих k джокеров и имеющих размерность r. Если какой-то параметр заменен знаком, то это означает, что рассматривается объединение таких множеств по всем возможным значениям параметра.

Обозначим через P (r, L, k) долю расстановок длины L, содержащих k джокеров и имеющих размерность r, т.е. отношение мощности множества M(r, L, k) к мощности множества M(, L, k). Во второй главе описывается эффективный алгоритм для определения P (r, L, k). Время работы наивного алгоритма экспоненциально зависит от длины слова; время работы нашего алгоритма полиномиально зависит от L и p и экспоненциально от параметра q.

Основная идея алгоритма излагается в шестом параграфе. Она заключается в разбиении всех расстановок из множества M(r, L, k) на классы и эффективном перечислении классов и подсчете количества расстановок в каждом классе. Для того, чтобы разбить множество расстановок M(r, L, k) на классы, сопоставим каждой расстановке характеристическую расстановку длины pq. В шестом параграфе доказан следующий результат.

Предложение 2.1. Размерность расстановки совпадает с размерностью ее характеристической расстановки.

Таким образом, для определения P (r, L, k) необходимо найти все характеристические расстановки размерности r, а затем для каждой такой характеристической расстановки определить количество соответствующих ей расстановок из множества M(r, L, k).

В седьмом параграфе рассматривается задача вычисления мощности класса расстановок M(r, L, k), которым соответствует данная характеристическая расстановка H. В случае L = lpq эта мощность зависит только от L, k и количества единиц в H. В случае L = lpq + g, 0 < g < pq мощность зависит еще и от количества единиц в первых g позициях характеристической расстановки H. В седьмом параграфе приведены формулы для вычисления данной мощности и итоговая формула для величины P (r, L, k).

Восьмой параграф посвящен описанию алгоритма для определения P (r, L, k). Вначале вычисляются вспомогательные таблицы (время выполнения этого этапа полиномиально зависит от L и p и экспоненциально от параметра q), а затем по формуле вычисляется P (r, L, k) (время выполнения этого этапа полиномиально зависит от L, p и q).

В девятом параграфе приводятся и анализируются результаты, полученные с помощью программы, реализующей данный алгоритм. Назовем плотностью джокеров в конечном частичном слове отношение количества джокеров к длине слова. Плотность джокеров в бесконечном частичном слове определим как верхний предел плотности джокеров в его подсловах длины n при n. В частности, в девятом параграфе исследовалась зависимость доли неунарных расстановок (т.е. расстановок, размерность которых больше единицы) длины L с k джокерами от плотности джокеров в слове. Примеры графиков данной зависимости приведены на рис.2.2, 2.3.

Третья глава посвящена изучению свойства взаимодействия локальных периодов частичных Z-слов.

В десятом параграфе описывается используемая техника. Обычному Z-слову с периодами p, q можно сопоставить граф локальной периодичности – граф, вершины которого соответствуют позициям букв данного слова, а ребра соединяют вершины u, v такие, что разность номеров соответствующих позиций частичного слова составляет p или q. Этот граф можно изобразить на бесконечном цилиндре двумя системами спиралей (см.рис.3.2). Граф локальной периодичности частичного Z-слова получается из графа обычного слова удалением вершин, соответствующих позициям джокеров, и инцидентных им ребер. Множество доменов частичного слова совпадает с множеством компонент связности данного графа.

В одиннадцатом параграфе вводятся необходимые определения и доказываются некоторые свойства специальных конечных подпоследовательностей. Нас будут интересовать минимальные по включению специальные подпоследовательности. Такие подпоследовательности мы будем называть разрезами (т.к. множество позиций разреза частичного Zслова соответствует вершинному разрезу графа локальной периодичности обычного Z-слова). В одиннадцатом параграфе приводится классификация разрезов.

Двенадцатый параграф посвящен описанию алгоритма проверки наличия в частичном слове специальной подпоследовательности. Алгоритм ищет позицию, замыкающую разрез (это наибольшая в некотором линейном порядке из позиций разреза).

На множестве позиций частичного слова определим следующие отношения. Отношение : xy W (x) = W (y). Отношение ( быть соседом ): xy (x y = ap + bq, a, b {1, 0, 1}). Рассмотрим также отношение 1 =. Для каждой позиции x определим метку следующим образом Предложение 3.4. Позиция x, замыкающая разрез, имеет двух соседей y, z с одинаковой конечной меткой. При этом y x, z x.

На основании предложения 3.4 в двенадцатом параграфе приводится описание полиномиального алгоритма с конечной памятью для проверки наличия в частичном слове специальных подпоследовательностей, а также дается оценка сложности работы этого алгоритма. В этом алгоритме позиции частичного слова рассматриваются в порядке. Для текущей позиции вычисляется метка и проверяется выполнение условий из предложения 3.4. Если эти условия выполняются, то текущая позиция объявляется замыкающей разрез.

Теорема 3.1. Время работы алгоритма проверки наличия в частичном слове специальных подпоследовательностей линейно зависит от длины исследуемого слова. Используемый объем памяти линейно зависит от периодов p, q.

В последнем параграфе третьей главы приводятся две модификации алгоритма из предыдущего параграфа. Первая из них позволяет определить количество доменов в конечном частичном слове. Вторая модификация алгоритма предназначена для поиска специальных подпоследовательностей особого вида преград.

Таковы основные результаты диссертации. Они докладывались на международных конференциях Mathematical Foundations of Computer Science (Марианские Лазни, 2001), WORDS’03 (Турку, 2003), российской конференции Дискретный анализ и исследование операций (Новосибирск, 2004), международной алгебраической конференции (Екатеринбург, 2005) и научных семинарах Алгебраические системы (УрГУ) и Дискретная математика (УрГУ). Результаты опубликованы в работах [38–45]. В совместных работах [38–41] руководителю принадлежат постановка задачи и общая методика исследований, доказательства всех основных утверждений принадлежат автору.

Работа выполнена под руководством доцента Арсения Михайловича Шура и доцента Евгения Витальевича Суханова, которым автор выражает глубокую благодарность за постоянное внимание и всестороннюю поддержку.

Глава I Свойство взаимодействия периодов В данной главе изучается свойство взаимодействия периодов частичных слов. Основными результатами данной главы являются теорема о существовании длины взаимодействия L(k, p, q) для любых периодов p, q и количества джокеров k (§1) и теорема, дающая точную оценку длины взаимодействия при некоторых ограничениях (§3).

§1 Существование длины взаимодействия В данном параграфе мы доказываем, что длина взаимодействия L(k, p, q) существует для любых периодов p и q и количества джокеров k и получаем для длины взаимодействия линейную верхнюю оценку.

§1.1 Используемая техника При исследовании частичных слов удобно рассматривать бинарные отношения и их графы. Пусть частичное слово U длины L, имеющее периоды p, q, содержит k джокеров в позициях i1,..., ik. Будем соотносить с этим словом бинарные отношения Rp и Rq на множестве D(U). Отношение Rp (отношение Rq ) состоит из всех пар (s, t), где s t (mod p) (соответственно, s t (mod q)) и между s и t нет такого n D(U), что s n (mod p) (соответственно, s n (mod q)). Отношения Rp, Rq являются симметричными, поэтому пару (D(U), Rp Rq ) можно рассматривать как неориентированный граф. Этот граф мы будем называть графом периодичности. Отношение (Rp Rq ) (рефлексивно-транзитивное замыкание отношения Rp Rq ) является отношением эквивалентности. По определению периода в U на эквивалентных позициях обязательно стоят одинаковые буквы. Отношению эквивалентности R соответствует некоторое разбиение множества D(U). Количество классов этого разбиения равно количеству компонент связности соответствующего графа и равно размерности слова U.

Пример 1.1. Пусть n = 9, k = 3, i1 = 2, i2 = 4, i3 = 6, q = 3, p = 5. Тогда U = a1 a3 a5 a7 a8 a9. Граф обычного слова с такими периодами и граф U выглядят следующим образом:

Рис. 1.1: Графы обычного и частичного слова. Сплошные линии обозначают ребра, соответствующие отношению Rp, штриховые отношению Таким образом, максимальное возможное количество различных букв в U равно 2 (компоненты связности соответствующего графа {1, 7} и {3, 5, 8, 9}).

§1.2 Теорема о существовании длины взаимодействия Напомним, что мы рассматриваем взаимно простые периоды p, q, 2 q < p. Следующая теорема утверждает, что длина взаимодействия L(k, p, q) существует для любых периодов p, q и любого количества джокеров k.

Теорема 1.1. Для любых взаимно простых p > q 2 и любого k Равенство достигается в двух случаях: когда k = 0 и когда q = 2 и p делит k.

Замечание 1.1. Из Теоремы 1.1 следует, что для любого k, не являющегося степенью двойки, можно подобрать такие взаимно простые натуральные p и q, чтобы существовало частичное слово длины p+(k +1)q2, имеющее периоды p и q, но не имеющее периода 1. В этом случае можно положить p равным некоторому нечетному делителю k, а q равным 2.

Замечание 1.2. Для обычных слов (k = 0) Теорема 1.1 дает ту же оценку, что и теорема Файна-Вильфа для взаимно простых периодов.

Для доказательства первого утверждения Теоремы 1.1 необходимы две леммы. Первая из них является аналогом Теоремы 0.4 для глобальных периодов.

Лемма 1.1. Рассмотрим частичное слово U длины p + q, имеющее периоды p и q. Пусть джокеры в U расположены следующим образом ровно один джокер в позициях 1,..., q, p+1,..., p+q и любое количество джокеров в позициях q + 1,..., p. Тогда U имеет период 1.

Доказательство. Рассмотрим слово без джокеров длины p + q 1, имеющее периоды p, q. По теореме Файна-Вильфа это слово имеет период 1, поэтому соответствующий граф является связным. Рассмотрим,какие вершины могут быть смежными с некоторой вершиной t. Поскольку длина слова меньше, чем p+q +1, возможны следующие случаи: 1)t+q, t+p;

2)t + q; 3)t + q, t q; 4)t q; 5)t q, t p. Случаи 2) и 4) описывают вершины q и p соответственно; любая другая вершина имеет две смежных.

Так как граф связный, то он является цепью.

Добавим в граф вершину (p + q). Она смежна вершинам p и q. Таким образом, полученный граф является простым циклом.

Исследуем процесс размещения в слове джокеров. Когда мы ставим джокер в позицию t, q + 1 t p, граф изменяется следующим образом:

удаляются вершина t и ребра (t q, t) и (t, t + q), а вершины t q и t + q соединяются ребром. Таким образом, полученный граф тоже является простым циклом, причем он будет оставаться таковым при размещении в слове любого количества джокеров в позициях q + 1,..., p. Размещение джокера в префиксе или суффиксе длины q означает удаление соответствующей вершины из графа. Таким образом, полученный граф (граф U) является цепью, т.е. связен. Следовательно, U имеет период 1.

Наблюдение 1.1. Граница p + q является точной. Это связано с тем, что граф слова длины p + q 1 является цепью, поэтому джокер в любой из позиций 1,..., q 1, p + 1,..., p + q 1 разбивает эту цепь на две части.

В соответствии с Леммой 1.1 мы будем называть джокер существенным для слова U длины p+q, имеющего периоды p, q, если он расположен в префиксе или суффиксе длины q.

Лемма 1.2. Рассмотрим частичное слово U, имеющее периоды p и q.

Если в этом слове есть подслово длины p + q, в котором содержится только один существенный джокер, то U имеет период 1.

Доказательство. Предположим, что это подслово расположено в U на участке t + 1,..., t + p + q. По Лемме 1.1 буквы U(t + 1),..., U(t + p + q) равны некоторой букве (назовем ее a). Тогда достаточно показать, что любая буква из U равна a. Рассмотрим позицию s, не входящую в выбранный сегмент и пометим все позиции, равные s по модулю q.

Тогда помеченными окажутся одна из позиций t + 1,..., t + q и одна из позиций t + p + 1,..., t + p + q. По условию только одна из них может быть занята джокером; значит, хотя бы в одной из этих позиций стоит буква a. Все буквы в помеченных позициях должны быть равны. Таким образом, U(s) = a.

Доказательство Теоремы 1.1. Докажем, что любое частичное слово с периодами p и q, содержащее k джокеров и не имеющее периода 1, короче, чем приведенная граница. По Лемме 1.2 такое слово должно содержать по крайней мере 2 существенных джокера в каждом подслове длины p + q. Каждое подслово длины p + q содержит 2q позиций, в которых могут стоять существенные джокеры. Поэтому любой джокер может быть существенным только для 2q подслов. Более того, первый в слове джокер не может стоять на последнем месте в подслове, содержащем два джокера, поэтому он может являться существенным только для 2q подслов. То же самое по симметрии выполняется и для последнего джокера в слове.

Поскольку каждое подслово длины p + q должно содержать по меньшей мере два существенных джокера, количество подслов длины p + q в слове не должно превышать (2qk 2)/2, т.е. qk 1. С другой стороны, слово длины L содержит L p q + 1 таких подслов. Таким образом, откуда следует, что L p + (k + 1)q 2. Следовательно, частичное слово длины не менее p + (k + 1)q 1 имеет период 1. Первое утверждение Теоремы 1.1 доказано.

Теперь докажем второе утверждение. При k = 1 оценку можно улучшить до p + q по Лемме 1.1. Поэтому будем считать, что k 2. Прежде всего докажем, что оценка может быть точной только для q = 2.

Предположим противное: q 3 и существует частичное слово W длины p + (k + 1)q 2, имеющее периоды p и q и содержащее k джокеров, но не имеющее периода 1.

Рассмотрим в W подслова длины p + q. Поскольку длина W равна p + (k + 1)q 2, слово W содержит qk 1 подслов длины p + q. Т.к.

W не имеет периода 1, по лемме 1.2 каждое подслово W длины p + q содержит не менее 2 существенных джокеров. Это возможно только в случае, когда каждый джокер является существенным для максимально возможного количества подслов: первый и последний джокеры являются существенными для 2q1 подслов, остальные джокеры для 2q подслов (см. доказательство первого утверждения). Поэтому два первых джокера должны находиться в позициях p + q 1 и p + q. Кроме того, каждое подслово должно содержать ровно два джокера.

Можно представить, что мы рассматриваем слово W через окно, размер которого p + q символов. Окно разделено на три части, размер которых q, p q и q символов соответственно (см. Рис. 1.2а,б). В начале окно установлено в префиксе W. Далее окно посимвольно передвигается вправо. На каждом шаге в боковых частях окна должно находиться ровно два джокера.

Два первых джокера изначально находятся в двух крайних справа позициях окна и при передвижении окна вправо сдвигаются влево. Третий джокер должен появиться в окне в тот момент, когда первый джокер попадает в центральную часть окна (Рис. 1.2а). Таким образом, третий и четвертый джокеры находятся в слове W в позициях p + 2q 1,p + 2q (эти позиции существуют, так как |W | p + 3q 2 и между вторым и третьим джокером есть хотя бы одна буква, поскольку q 3).

Пока первый джокер проходит центральную часть окна, несколько раз может повториться подобная ситуация: когда текущая пара джокеров попадает в центральную часть, другая пара появляется справа на расстоянии q от текущей пары.

Когда первая пара джокеров попадает в левую часть окна, другая пара должна переходить в центральную часть (Рис. 1.2б). Пусть V слово, которое в этот момент находится в окне. С одной стороны, в V имеются джокеры, расположенные в позициях q, q + 1 и p, p + 1. С другой стороны, расстояние между первыми джокерами этих пар кратно q.

Тогда q делит p q, что противоречит предположению НОД(p, q) = 1.

Теперь предположим, что q = 2. Первые два джокера находятся в позициях p + 1 и p + 2. В рассмотренном ранее случае пары джокеров в W были разделены хотя бы одной буквой. Теперь в правой части окна только два символа, поэтому третий джокер возникает сразу после второго. Более того, можно заметить, что W содержит p последовательных джокеров в позициях p + 1,..., 2p. За ними следуют p букв, затем снова p джокеров и т.д. Таким образом, если k = sp для некоторого s, то длина W равна (2s + 1)p, что совпадает с предложенной оценкой p + (k + 1)q 2.

С другой стороны, если k = sp, то символ, следующий за k-ым джокером в W, тоже должен быть джокером. Таким образом, последним символом W должен быть джокер. Этот джокер является существенным только для одного подслова длины p + q, в то время как он должен являться существенным для 2q 1 подслов.

Мы доказали, что необходимые условия могут выполняться только при q = 2 и k = sp для некоторого s. Теперь докажем, что слово W длины (2s + 1)p, имеющее периоды 2 и p и содержащее sp джокеров, расположенных описанным выше способом, содержит по меньшей мере две различных буквы. Как уже было доказано, джокеры в W должны быть расположены следующим образом:

В соответствующем графе ребро соединяет вершины, равные по модулю 2 или по модулю p. В слове W на любых двух позициях, находящихся на расстоянии p друг от друга, расположены одна буква и один джокер.

Таким образом, одинаковые буквы находятся на расстоянии, кратном 2p.

Это означает, что граф имеет две компоненты связности, состоящие из вершин с четными и нечетными номерами соответственно. Следовательно, в W могут присутствовать две различные буквы. Таким образом, Теорема 1.1 доказана.

§2 Точные оценки в частных случаях В данном параграфе мы находим точные оценки для длины взаимодействия в двух важных частных случаях: q = 2 и k = 2.

Теорема 1.2. Для любого нечетного p и любого k Доказательство. Сначала рассмотрим случай k = sp для некоторого s N. Согласно теореме 1.1 в этом случае L(k, p, 2) = p + 2k + 1, что совпадает с доказываемой оценкой. Таким образом, существует слово W длины (L(k, p, 2) 1) = (p + 2k) с k джокерами и периодами 2 и p, не имеющее периода 1. Из доказательства теоремы 1.1 следует, что джокеры в W должны быть расположены следующим образом:

W = a1 a2... ap... a2p+1... a(2s1)p... a2sp+1 a2sp+2... a(2s+1)p.

При этом каждый джокер является существенным для максимально возможного количества подслов длины p + q: первый и последний джокеры являются существенными для 2q 1 подслов, остальные джокеры для 2q подслов.

Теперь рассмотрим случай k = sp + t, 0 < t < p. Как следует из доказательства теоремы 1.1, в этом случае невозможно расставить джокеры так, что каждый джокер будет существенным для максимально возможного количества подслов длины p+q. Рассмотрим слово W длины L(k, p, 2)1 с k джокерами и периодами 2 и p, не имеющее периода 1. В этом слове джокеры должны быть расставлены так, чтобы как можно больше джокеров являлись существенными для максимально возможного количества подслов длины p + q. Для этого sp джокеров должны быть расставлены в подслове длины p+2sp так же, как в предыдущем случае. Оставшиеся t джокеров должны стоять в позициях, соседних с этим подсловом, так как иначе в слове возникнет подслово длины p+q, в котором менее 2 существенных джокеров. Тогда |W | = (2s + 1)p + t = (2 k/p + 1)p + k mod p, а расстановка джокеров в слове W, например, такая:

W = a1 a2... ap... a2p+1... a(2s1)p... a2sp+1 a2sp+2... a(2s+1)p....

Теорема 1.3. Для любых взаимно простых p > q Доказательство. Вначале докажем, что L(2, p, q) p + 2q 1. Рассмотрим частичное слово U длины p+2q1, имеющее периоды p и q и содержащее 2 джокера. Докажем, что U имеет период 1. Для этого рассмотрим возможные варианты расстановки джокеров в слове U.

1. Предположим, что в U имеется джокер в одной из позиций q + 1,..., p, p + q + 1,..., p + 2q 1. Тогда в префиксе слова U длины p + q находится не больше одного существенного джокера. Аналогично, если джокер расположен в одной из позиций 1,..., q 1, 2q,..., p + q 1, то в суффиксе находится не больше одного существенного джокера. По Лемме 1.2 в этих случаях U имеет период 1.

2. Предположим, что в U имеется джокер в позиции t, причем p + t < 2q (этот случай невозможен при p + 1 2q). Тогда для подслова длины p + q, начинающегося с позиции t p + 1, этот джокер не является существенным, так как расположен в p-ой позиции. По Лемме 1.2 U в этом случае имеет период 1.

3. Осталась одна возможность: джокеры расположены в q-ой и (p+q)ой позициях. Необходимо доказать, что в этом случае граф U является связным. Как уже указывалось, граф обычного слова длины p + q, имеющего периоды p и q, является простым циклом (см. доказательство Леммы 1.1). Вершины q и p + q являются смежными. Поэтому при удалении этих вершин из графа (т.е. размещении джокеров в позициях q и p + q) граф останется связным. Таким образом, префикс U длины p + q является связным. Симметрично, связным будет и граф суффикса. Эти подслова имеют p + 1 общих символов, т.е. по крайней мере одну общую букву. Отсюда следует, что граф U является связным.

Теперь докажем, что L(2, p, q) p+2q 1. Расмотрим слово W длины p + 2q 2, имеющее периоды p и q и содержащее два джокера в позициях q1,q (см. пример на Рис.1.3). Граф префикса длины p + q получен из простого цикла удалением двух несмежных вершин, поэтому он состоит из двух цепей, не связанных друг с другом. Вершина p + q + 1 смежна с вершинами p + 1 и q + 1. Эти вершины смежны вершине 1, поэтому они и так находятся в одной компоненте. Следовательно, полученный граф по-прежнему имеет две компоненты связности. Аналогично добавление вершин p + q + 2,..., p + 2q 2 не уменьшает количество компонент связности. Только добавление вершины p + 2q 1 делает граф связным, так как она соединяет вершины p + q 1 и 2q 1, которые не были связаны, поскольку W (q 1) =.

Рис. 1.3: Граф частичного слова, имеющего периоды q = 5, p = 7, длины p+2q 1 = 16. Удаление вершины 16 разбивает граф на две компоненты.

§3 Формулировка прямой и обратной задачи. Бланки и расстановки Если отбросить рассмотренный в Теореме 1.2 случай q = 2 и случай маленьких k, то можно значительно улучшить оценку для длины взаимодействия из Теоремы 1.1. В следующей теореме, являющейся центральным результатом главы 1, эта длина представлена в виде суммы линейной и периодической функций относительно k. Такое представление позволяет получить максимально точную общую (т.е. пригодную для любых p и q) оценку длины взаимодействия.

Теорема 1.4. Пусть p и q взаимно простые натуральные числа, p > q 3, а натуральное число k таково, что k 2p/3 1 при q=3 и k 3p/q +3 при q4. Пусть L(k, p, q) длина взаимодействия периодов p и q при наличии k джокеров. Тогда где функция (k, p, q) является периодической по k с периодом p + q и удовлетворяет следующим условиям:

1. для произвольных p и q 2. для любого периода q и любого > 0 существует p такое, что 3. для произвольных p и q Пример 1.2. График зависимости длины взаимодействия от числа джокеров при p = 13, q = 3, вместе с графиками верхней и нижней оценок из теоремы 1.4, приведены на рис. 1.4. Отметим, что, согласно теореме 1.4, эти оценки верны при k 7. Штриховая линия соответствует верхней оценке из теоремы 1.1. Эта оценка верна при любом k.

Далее в первой главе мы всюду считаем, что p > q 3. Для доказательства теоремы 1.4 рассмотрим обратную задачу:

задана длина слова L и его периоды p, q, необходимо найти минимальное количество джокеров, при котором слово может не иметь периода 1.

Заметим, что для каждого периода p произвольного слова U и для любого i, 1 i p, все буквы, находящиеся в позициях i, i+p, i+2p,...

равны независимо от расположения джокеров в этих позициях. Указанное множество позиций мы будем называть p-классом; оно содержится в i-ом классе вычетов по модулю p.

Мы рассматриваем случай двух различных периодов p, q у слова U, и, соответственно, будем рассматривать p- и q-классы. Заметим, что если две позиции из разных q-классов, занятые буквами, принадлежат одному p-классу (т.е. связаны при помощи периода p), то в этих q-классах содержится одна и та же буква. Если же любая пара позиций из данных q-классов, принадлежащая одному p-классу, содержит хотя бы один джокер, то эти q-классы могут содержать различные буквы.

Рис. 1.4: график зависимости длины взаимодействия от числа джокеров.

Таким образом, чтобы построить слово U длины L с периодами p и q, содержащее m различных букв (m q), нужно разбить q-классы (их q штук) на m групп и разместить джокеры так, чтобы период p связывал между собой только такие позиции, не занятые джокерами, которые принадлежат q-классам из одной группы.

Чтобы решить поставленную обратную задачу, надо найти наиболее экономный способ размещения джокеров для случая m = 2. Процедура построения слова U в этом случае будет выглядеть следующим образом.

Разделим q-классы на 2 группы: T и S, содержащие соответственно t и s классов (0 < t s, t + s = q). Договоримся отождествлять номера q-классов и сами q-классы. В частности, нам будет удобнее относиться к элементам множеств S и T как к номерам. Для каждого p-класса выберем одну из групп T или S и разместим джокеры во всех позициях этого p-класса, принадлежащих к q-классам из выбранной группы. Если мы хотя бы по разу выбрали каждую из групп, то в q-классах как из T, так и из S останутся позиции, не занятые джокерами. В них мы разместим буквы (одну для T, другую для S) и, тем самым, получим слово U, не имеющее периода 1. Несложно заметить, что число джокеров в U, которое мы стремимся минимизировать, зависит от t и от способа выбора групп для q-классов.

Опуская детали, вышеизложенную процедуру можно представить так:

имеется некоторый шаблон слова U, в котором мы по определённым правилам размещаем алфавитные символы (вначале джокеры, а затем буквы). Интуитивное понятие шаблона мы сейчас оформим в виде специальной числовой таблицы бланка, играющей ключевую роль в дальнейших рассмотрениях.

Запишем позиции слова U в таблицу, как показано на рис. 1.5а).

Занумеруем q-классы числами от 0 до q1 (так, что i-ый класс содержит позиции с номерами вида i + nq) и заменим в приведённой таблице каждую позицию на номер содержащего её q-класса. Полученную таблицу будем называть бланком. Она имеет вид, изображённый на рис. 1.5б) ( обозначает сложение по модулю q).

Для построения слова U мы заменяем некоторые номера в строках (строки соответствуют p-классам) джокерами так, чтобы в любой строке оставались номера классов только из группы S или только из группы T.

Пример 1.3. Пусть имеется слово длины 15, имеющее периоды 5,7. Минимальное количество джокеров, при котором такое слово может не быть унарным, равно 2 (Это следует из теоремы 1.3). Бланк для этого слова выглядит следующим образом (рис. 1.6а):

Легко убедиться, что наименьшее количество джокеров достигается при T = {2, 4} и S = {0, 1, 3}. Тогда нам необходимо поставить по одному джокеру в 4-ую и 5-ую строки, например, в позиции 4 и 5 (рис. 1.6б).

Теперь в каждой строке находятся номера q-классов, принадлежащих одной группе. Заменив номера из S на a, номера из T на b и записав буквы в обычном порядке, получим бинарное слово aba ababaababa.

Замечание 1.3. В связи с рассматриваемой задачей нас интересует только стадия размещения джокеров в бланке (и последующий подсчёт джокеров). Стадию размещения букв мы будем опускать.

Рис. 1.6: пример бланка и расстановки джокеров в нем.

Замечание 1.4. Параметры L, p, q (L > p > q > 1, НОД(p, q) = 1) однозначно задают бланк. Поэтому бланк будем обозначать через B(L, p, q).

Расстановкой джокеров в слове (бланке), или просто расстановкой будем называть множество позиций в слове или в бланке, на которых стоят джокеры. Пусть заданы периоды p, q и длина L. Расстановку джокеров в бланке B(L, p, q) будем называть допустимой, если слово длины L с периодами p, q и указанной расстановкой джокеров может не иметь периода 1 (т.е. содержать две различные буквы). Допустимую расстановку с минимальным количеством джокеров будем называть оптимальной, а число джокеров в ней обозначать через k. Рассматриваемая нами обратная задача состоит, таким образом, в вычислении k.

Для данного t (напомним, что t = |T |) рассмотрим все допустимые расстановки джокеров и выберем расстановку с минимальным количеством джокеров. Эту расстановку будем называть оптимальной при t, а количество джокеров в ней обозначать через k (t).

Будем называть специальной расстановку следующего вида: |T | = 1, во всех строках, кроме одной, джокерами заменяются все вхождения элемента из T и только они, а в оставшейся строке все вхождения элементов из S и только они. Специальная расстановка, очевидно, является допустимой.

Лемма 1.3. При q 3 и L 2p2 существует специальная расстановка в бланке B(L, p, q), оптимальная при t = 1.

Доказательство. В бланке B(L, p, q) не более двух одноэлементных строк.

Если такие строки есть, поместим в множество T q-класс, в них не встречающийся (такой найдётся, поскольку q-классов не менее трёх); если таких строк нет, поместим в T любой q-класс. Теперь в каждой строке элементов из T содержится не больше, чем элементов из S. Для фиксированного одноэлементного T рассмотрим допустимую расстановку, в которой джокеры заменяют элементы S более, чем в одной строке. Заменив в одной из строк джокерами элементы T вместо элементов S, вновь получим допустимую расстановку; количество джокеров при этом может лишь уменьшиться. Таким образом, при каждом фиксированном одноэлементном T некоторая специальная расстановка содержит минимальное количество джокеров. Следовательно, найдётся специальная расстановка, которая является оптимальной при t = 1.

Следствие 1.1. Для любого бланка B(L, p, 3) такого, что L 2p 2, существует оптимальная специальная расстановка.

Доказательство. Условие q = 3 необходимо влечёт t = 1. Таким образом, специальная расстановка, оптимальная при t = 1 (такая существует по лемме 1.3), является оптимальной.

Следующее предложение, позволяющее решить обратную задачу, является ключевым в данной главе.

Предложение 1.1. Для любого бланка B(L, p, q) такого, что q 4, L 3p + q, существует оптимальная специальная расстановка.

Замечание 1.5. В примере 1.3 выполняется k (1) = 3, и, таким образом, никакая специальная расстановка не оптимальна (но длина бланка в этом примере не удовлетворяет приводимым в предложении 1.1 ограничениям).

§4 Решение обратной задачи Данный параграф посвящён доказательству предложения 1.1, а также решению обратной задачи на основе подсчёта джокеров в оптимальной специальной расстановке.

Для доказательства предложения 1.1 разделим бланк на части следующим образом (см. рис. 1.7).

Часть бланка, соответствующую префиксу слова длины pq· pq, будем называть телом, а оставшуюся часть хвостом. Тело состоит из блоков прямоугольников высоты p и ширины q это части 1.

В хвосте выделим части 2 это прямоугольники высоты q, ширина которых равна L mod pq или L mod pq. Таких частей p штук. Кроме того, в бланке присутствуют одна часть 3 и одна часть 4. Часть прямоугольник ширины L mod pq и высоты (p mod q). Часть 4 пряp моугольник ширины 1 и высоты (L mod q), соответствующий суффиксу слова длины (L mod q).

Определим расстановку для части i как пересечение части i и расстановки в данном бланке. Определения допустимой и оптимальной (при t) расстановок для части i аналогичны соответствующим определениям для расстановок. Количество джокеров в оптимальной при t для части i расстановке будем обозначать через ki (t). Очевидно, что сумма значений ki (t) по всем частям бланка не превосходит k (t).

Для доказательства предложения 1.1 рассмотрим отдельно количество джокеров в расстановках, оптимальных для каждой части. Лемма 1.4 посвящена исследованию части 1, леммы 1.5-1.7 части 2, лемма 1. части 3. Рассмотрение расстановок для части 4 не представляет интереса: любая строка в этой части содержит только один элемент, а значит, оптимальная расстановка при любом t вообще не содержит джокеров.

Лемма 1.4. Для любого 2 t q/2 справедливо Доказательство. Рассмотрим часть 1. Каждая строка блока является перестановкой множества {0,..., q 1}. В самом деле, последовательность элементов первой строки имеет вид все элементы различны, так как НОД(p, q) = 1, а значит, является перестановкой множества {0,..., q 1}. Остальные же строки являются циклическими перестановками. Итак, в каждой строке блока номер каждого q-класса встречается ровно один раз. Таким образом, каждая строка содержит t элементов из T и s элементов из S.

Хотя бы в одной строке мы должны разместить t джокеров, хотя бы в одной s джокеров, и в каждой из оставшихся либо t, либо s джокеров. Поскольку t s, то оптимальная расстановка для части 1 следующая: по t джокеров в p 1 строке, и s = q t джокеров в оставшейся строке. Тогда общее количество джокеров в части 1 при оптимальной для неё расстановке равно При t 2 в части 1 необходимо поставить на k1 (t)k1 (1) = (p2)(t1) джокеров больше, чем при t = 1.

Перейдем к рассмотрению части 2.

Отличительная особенность частей, принадлежащих хвосту бланка, состоит в том, что они пересекают не все строки бланка (т.е. не все p-классы). Это значит, что в расстановке, оптимальной для такой части, джокеры могут во всех строках заменять только элементы из T :

строки, в которых джокерами заменяются элементы из S, обязательно присутствуют в бланке, но могут не пересекать данную часть. Наличие таких строк будет учтено ниже, в доказательстве предложения 1.1.

Обозначим ширину части 2 через w (1 w q). Для удобства рассмотрения дополним эту часть бланка до квадрата q q (см. рис. 1.8).

Тогда в первой строке полученной таблицы будет находиться рассмотренная выше перестановка, а в остальных строках все ее различные циклические перестановки (ср. доказательство леммы 1.4). Заштрихованные клетки на рисунке содержат элементы из T. Ясно, что для произвольного бланка перестановкой строк можно добиться того, чтобы эти элементы размещались лесенкой, как в примере на рис. 1.8. Ниже мы будем считать, что в рассматриваемой части вида 2 такая перестановка строк произведена.

Множеству T поставим в соответствие слово ZT длины q над алфавитом {0, 1}, которое получается из первой строки дополненной части заменой элементов T на 1 и элементов S на 0. Обозначим через ZT (w, j) префикс длины w циклической перестановки слова ZT, начинающейся с j-го символа. Слова ZT (w, j) соответствуют всем q строкам рассматриваемой части 2. Характеристическим числом j-ой строки назовём величину Рис. 1.8: пример дополненной части 2 (номера q-классов не проставлены).

Элементы T соответствуют заштрихованным клеткам, элементы S пустым.

Слева указаны характеристические числа строк.

где |ZT (w, j)|0, |ZT (w, j)|1 это число нулей (соответственно, единиц) в слове ZT (w, j). Для j-ой строки части 2 (j) равняется минимальному количеству джокеров, необходимому в этой строке для того, чтобы расстановка была допустимой. Характеристическим числом множества T (обозначается (T )) будем называть величину Таким образом, (T ) равно минимальному числу джокеров в части 2 в допустимой расстановке при данном множестве T.

Лемма 1.5. 1) Если t w/2, то (T ) = tw для любого множества 2) Если t > w/2, то (T ) = w для любого множества T такого, что ZT есть циклическая перестановка слова 1... 10... 0.

Множество T, такое что ZT есть циклическая перестановка слова 1... 10... 0, будем обозначать через T.

Доказательство. Первое утверждение леммы практически очевидно. В самом деле, при t w/2 в каждом слове ZT (w, j) единиц не более w/2, т.е. не больше, чем нулей. Следовательно, (j) = |ZT (w, j)|1 для всякого j. Каждая единица из ZT встречается в w словах ZT (w, j), а значит, всего этих словах содержится tw единиц, откуда (T ) = tw.

Перейдём к доказательству второго утверждения. Дополненная часть 2 в случае множества T перестановкой строк приводится к следующему виду (см. рис. 1.9).

Рис. 1.9: элементы T соответствуют заштрихованным клеткам. Слева указаны характеристические числа строк.

Строки, в которых содержатся элементы как из S, так и из T, то есть такие строки, в которых надо ставить джокеры, пересекаются с выделенными на рис. 1.9 частями a, b, c, d. Для строк, пересекающих часть a или часть d, (j) = |ZT (w, j)|1, т.е. джокерами нужно заменять элементы множества T (это клетки частей a и d). Для строк, пересекающих часть b и/или часть c, (j) = |ZT (w, j)|0, и джокерами нужно заменять элементы множества S (это клетки частей b и c). Таким образом, (T ) есть суммарное число клеток в частях a, b, c и d. Первое слагаемое приводимой формулы соответствует части a, второе b, третье с, четвертое Вычисляя значение суммы при нечётном w, получаем а при чётном w Лемма 1.6. При любом фиксированном t > w/2 выполняется где T таково, что ZT есть циклическая перестановка слова 1... 10... 0.

Доказательство. Вначале распространим определение слова ZT (w, j) на случай произвольного целого j. А именно, определим ZT (w, j) как префикс длины w циклической перестановки слова ZT, начинающейся с позиции (j mod q) (а если j mod q = 0, то с q-й позиции). Данное определение можно наглядно представить следующим образом: слово ZT циклическое, то есть за его последней буквой снова следует первая, и т.д. Тогда j-ая позиция как раз и совпадает с позицией (j mod q). Величину (j) при таком определении можно рассматривать как функцию Z N, периодическую с периодом q. Рассмотрим также вспомогательную функцию (j) = |ZT (w, j)|1 (это тоже периодическая с периодом q функция Z N). Заметим, что для произвольного m Z Нам будет удобно доопределить функции и на всей числовой прямой.

Функцию (x) определим как кусочно-линейную, построенную по точкам (j), а функцию (x) заменив j на x в равенстве (1.1). Рассмотрим свойства и график функций (x), (x) (пример приведён на рис. 1.10).

1) Поскольку число единиц (как и число нулей) в соседних словах ZT (w, j) отличается не более, чем на единицу, имеем для любого j Z откуда следует, что любой линейный участок графика (x) или (x) имеет угловой коэффициент 1, 0 или 1.

Рис. 1.10: график (x) (сплошная линия) и (x) (штриховая линия) на периоде.

2) Из (1.1) следует, что график (x) получается из графика (x) отражением относительно прямой y = w той его части, которая выше этой прямой.

3) Для любых m Z, x0 R выполняется Таким образом, при фиксированном t константа (x)dx не зависит от принимающая, вообще говоря, различные значения при различных T, минимальное значение принимает на множестве T, указанном в условии леммы.

Возьмем функции (x), (x), соответствующие множеству T. Тогда график функции (x) на некотором периоде будет иметь вид, приведенный на рис. 1.10 (штриховая линия). Константный промежуток со значением (x) = n2 соответствует максимальному количеству единиц в слове ZT (w, j) (или максимальному количеству элементов T в строке части 2), а константный промежуток со значением (x) = n1 соответствует минимальному количеству единиц в слове ZT (w, j) (или минимальному количеству элементов T в строке части 2). Согласно свойству 2), график (x) будет иметь вид, изображённый на рис. 1.10 сплошной линией.

Оценим константы n1 и n2. Пользуясь тем, что ZT циклическая перестановка слова 1... 10... 0, выберем j0 такое, что ZT (w, j0 ) является префиксом этого слова. Тогда ZT (w, j0 ) содержит максимальное количество (то есть n2 ) единиц. Если w t, то слово ZT (w, j0 ) целиком состоит из единиц, откуда n2 = w. Если же t < w, то данное слово содержит все t единиц, имеющихся в ZT, откуда n2 = t. В итоге, n2 = min{w, t}. Рассуждая аналогично, получаем n1 = max{0, ws}. Заметим, что для любого множества T (|T | = t) всякое слово ZT (w, j) содержит не более, чем t и не более, чем w единиц. Следовательно, (x) n2 для любого рассматриваемого T и для любого x R. Аналогично приходим к выводу, что (x) n1.

Кроме того, из условия t s следует, что n1 w n2, т.е. левый (на рис. 1.10) локальный минимум функции (x) находится выше правого.

В самом деле, если n2 = w, то t w, откуда s w и n1 = 0. Если же Обозначим X = {x| (x) w }, X < = {x| (x) < w }. Тогда Теперь возьмем произвольное слово ZT с условием |T | = t, рассмотрим соответствующие ему функции (x) и (x) и докажем, что Обозначим X = {x| (x) w }, X< = {x| (x) < w }. Условимся также обозначать через (M) длину (или меру) множества M, где M объединение конечного числа непересекающихся промежутков из отрезка [x0, x0 + q].

Как показано выше, n1 (x) n2. Если (x) w всегда, то ет y0 такое, что ({x| (x) < y0 }) > ({x| (x) < y0 }).

Оценим значение y0. Из непрерывности (x) следует, что она по крайней мере дважды на периоде принимает значение w ; в тех же точках (x) = w, т.е. (x) на периоде хотя бы дважды достигает максимального значения. Заметим, что функция (x) достигает значения w ровно дважды на периоде (с точках x0 и x1 ) и спускается до локальных минимумов с наибольшей возможной скоростью с постоянным угловым коэффициентом, равным 1. Следовательно, для любого y w n2 (как было доказано, это больший локальный минимум функции (x)) имеем ({x| (x) < y}) ({x| (x) < y}). Таким образом, y0 < w n2. Но в этом случае значения, не превосходящие y0, функция (x) принимает только в области X<, а функция (x) в области X <. В силу свойств функции (x) в области X < = (x1 ; x0 + q) (см. рис. 1.10) из неравенства ({x| (x) < y0 } X< ) > ({x| (x) < y0 } X < ) следует неравенство ({x| (x) < y} X< ) > ({x| (x) < y} X < ) для любого y w. Таким образом, (X< ) > (X < ). Но тогда (X ) > (X ), и из свойств функции (x) в области X (см. рис. 1.10) имеем Таким образом, чию. Таким образом, лемма 1.6 доказана.

Из лемм 1.5, 1.6 вытекает, что т.е. график зависимости k2 (t) выглядит следующим образом (рис. 1.11).

Лемма 1.7. Для любого 2 t q/2 справедливо Доказательство. а) w 4. Поскольку k2 (t) не убывает, Лемма 1.8. Для любого 2 t q/2 справедливо k3 (1) k3 (t) 1.

Доказательство. Рассмотрим часть 3. При любом одноэлементном множестве T в каждой строке находится не более одного элемента из T, а значит, в ней можно обойтись не более чем одним джокером. В некоторых строках оптимальной для части 3 расстановки при t > 1 может не быть джокеров; мы укажем допустимую расстановку при t = 1, в которой джокер стоит ровно в одной из таких строк. Тем самым лемма будет доказана.

Пусть значение k3 (t) (t > 1) достигается при множестве T. Если j-ая строка не содержит джокеров при соответствующей расстановке, то ZT (w, j) = 1... 1 или ZT (w, j) = 0... 0. Выберем в ZT какую-нибудь единицу, входящую в подслово 01 или 10. Среди строк, в которые попадает q-класс, соответствующий этой единице, не более чем в одной нет джокеров. Для t = 1 возьмём множество T, состоящее из выбранного q-класса. Соответствующая ему расстановка является искомой.

Пример 1.4. Для бланка B(40, 11, 8) k3 (1) = 1, k3 (3) = 0 (достигается при T = {0, 2, 5}, см. рис. 1.12a)). Более того, заметим, что при указанном T минимальное количество джокеров в частях 3 и 4 в сумме равно 0, в то время как при t = 1 в частях 3 и 4 в совокупности нужно разместить 2 джокера.

Доказательство предложения 1.1. Для любого фиксированного бланка B(L, p, q) и любого t > 1 выполняется где k2,1 (t),..., k2, p/q (t) количества джокеров в оптимальных при t расстановках для соответствующих частей 2. Обозначим сумму в правой части через (t). Мы построим в бланке специальную расстановку (назовём её оптимизированной), количество джокеров в которой не превосходит (t). Тем самым, с учётом леммы 1.3, предложение будет доказано.

Любую специальную расстановку в бланке можно построить по следующему алгоритму:

1) выбрать некоторый q-класс в качестве единственного элемента T ;

2) заменить джокерами все вхождения выбранного элемента в бланк;

3) выбрать в бланке некоторую строку;

4) в выбранной строке удалить все джокеры, поставленные ранее, и поставить джокеры во всех оставшихся позициях.

Относительно расстановки, полученной на шаге 2), заметим, что её пересечение с любой частью 2 бланка является расстановкой для этой части, оптимальной при t = 1, а её пересечение с частью 4 бланка содержит не более одного джокера. Пересечение итоговой специальной расстановки с любой частью 1 бланка также является расстановкой для этой части, оптимальной при t = 1.

Оптимизированную расстановку построим таким образом: q-класс выберем так, чтобы минимизировать число джокеров в части 3, а строку так, чтобы увеличение числа джокеров на шаге 4) в бланке было минимальным. Отметим, что выбор в каждом из случаев может быть не единственным, т.е. для данного бланка может существовать несколько оптимизированных расстановок; зафиксируем одну из них. Количество джокеров в построенной расстановке обозначим через k.

Количество джокеров в каждой части 1 оптимизированной расстановки равно k1 (1). Количество джокеров в хвосте оптимизированной расстановки есть k2,1 (1) +... + k2, p/q (1) + k3 (1) плюс количество джокеров, поставленных на шаге 2) в части 4 (обозначим его через k4 ), плюс минимальная разность между количеством элементов из S и элементов из T в одной строке в хвосте бланка (обозначим её через ).

Заметим, что специальная расстановка, не являющаяся оптимизированной, не может содержать менее k джокеров: в ней может быть на джокер меньше только в части 4, но обязательно имеется дополнительный джокер в части 3 и/или за счёт.

Нам надо доказать, что (k1 (1)k1 (t)) + (k2,1 (1)k2,1 (t)) +... + (k2, Величина 1 есть сумма неположительных слагаемых согласно леммам 1.4 и 1.7. Поэтому мы вначале оценим величину 2. Если в хвосте бланка нет элементов из T, то k3 (1) = k4 = = 0, т.е. 2 0 и требуемое неравенство доказано. Предположим, что в хвосте есть элементы из T, а значит, на шаге 2) построения специальной расстановки в хвосте были поставлены джокеры. По построению k4 1, а по лемме 1.8 (k3 (1) k3 (t)) 1. Оценим. В хвосте бланка есть длинные строки, состоящие из ( (L mod pq)/p ) позиций, и короткие, из ( (L mod pq)/p ) позиций. Если на шаге 2) был поставлен джокер в короткой строке, то = (L mod pq/p) 2, и, таким образом, (L mod pq)/p. Если же на шаге 2) в коротких строках не появилось джокеров, то = (L mod pq)/p 1; но в этом случае k3 (1) = 0 (часть 3 состоит только из коротких строк). Следовательно, и в этом случае 2 (L mod pq)/p.

Теперь оценим 1, используя условие L 3p + q. Если в бланке есть часть 1, то по лемме 1. Поскольку 2 q 1, получаем, что требуемое условие 1 + выполнено.

Если же в бланке нет части 1, то в нём должна присутствовать часть 2 ширины не менее 4. Тогда по лемме 1. где w = (L mod pq)/p. Условие 1 + 2 0 снова выполнено. Предложение доказано.

Замечание 1.6. Оценка для L, приводимая в условии предложения 1.1, может быть незначительно понижена. Однако, точная оценка сильно зависит от соотношения между конкретными p и q. Отметим здесь, что при p > 2q условие L 2(p + q) является достаточным для существования специальной оптимальной расстановки (такая длина бланка обеспечивает наличие либо части 1, либо части 2 ширины 4, либо двух частей 2 ширины 3; в последнем случае применение леммы 1. также позволяет доказать предложение). В то же время, в бланке B(33, 11, 8) (см. рис. 1.12б)) любая специальная расстановка содержит не менее 5 джокеров, а оптимальная (при T = {0, 2, 5}) 4 джокера, поставленные вместо номеров, выделенных жирным шрифтом; т.е.

условие L 3p в общем случае не является достаточным.

Следующее предложение даёт решение обратной задачи. Через L обозначим длину хвоста бланка B(L, p, q), равную L mod pq.

Предложение 1.2. Для произвольного бланка B(L, p, q) такого, что q = 3, L 2p 2 или q 4, L 3p + q, выполняется c) если L p, то Доказательство. Согласно предложению 1.1 и следствию 1.1, достаточно подсчитать джокеры в оптимальной специальной расстановке; сделаем это в предположении, что такая расстановка построена по алгоритму, указанному в доказательстве предложения 1.1. Каждая часть 1 бланка содержит p+q2 джокеров при любой специальной расстановке. Минимальное количество джокеров во всём бланке, таким образом, достигается при минимуме джокеров в его хвосте.

В случае a) выберем элемент множества T так, чтобы он не встречался в хвосте бланка, а строку, в которой джокерами заменяются элементы из S чтобы она не пересекала хвост бланка (и то, и другое возможно, поскольку хвост содержит менее q символов). Тогда в хвосте не будет ни одного джокера, и мы получим указанную в случае a) оценку.

Поскольку всякий номер q-класса встречается в бланке ровно 1 раз в каждых последовательных q позициях, в случае b) выберем элемент множества T так, что на шаге 2) построения расстановки в хвосте будет поставлено L джокеров. Все они находятся в разных строках (каждая строка пересекается с хвостом бланка не более, чем по одному символу).

На шаге 3) выберем строку, содержащую джокер в хвосте, после чего на шаге 4) количество джокеров в хвосте уменьшится на 1. Это даёт нам требуемую оценку.

В случае c) заметим, что оценки снизу и сверху для k, в зависимости от параметров бланка, либо равны, либо различаются на 1. Первое слагаемое в обеих оценках есть количество джокеров в теле бланка, одинаковое для всех специальных расстановок. Аналогично случаю b), выберем элемент из T так, что в хвосте бланка на шаге 2) ставится L /q джокеров. Далее, на шаге 3) выберем строку, в которой в хвосте имеется джокер (тогда количество джокеров, добавляемых на шаге 4), будет меньше, чем если выбрать строку без джокеров в хвосте). При этом на шаге 4) в хвост бланка будет добавлено L /p 2 или L /p 1 джокеров в зависимости от того, короткая или длинная строка выбрана.

В итоге, если найдётся номер q-класса, который встречается в хвосте бланка только L /q раз и при этом хотя бы один раз в короткой строке, то k совпадает со значением левой части; если же всякий такой номер встречается только в длинных строках, то k больше на единицу. Докажем, что в последнем случае тем самым будет завершено доказательство случая c) и всего предложения.

Пусть L mod q = r. Тогда qr символов встречаются в хвосте редко, т.е. L /q раз. Поскольку эти символы встречаются только в длинных строках, то количество коротких строк не превосходит r (первые символы нижних r строк в хвосте бланка, очевидно, различны). С другой стороны, L mod p равно количеству длинных строк, т.е. p r. (Заметим, что случай r = 0 невозможен, так как при этом число L, меньшее pq по определению, оказывается общим кратным взаимно простых p и q.) В итоге, получаем §5 Решение исходной задачи В данном параграфе из решения обратной задачи мы получаем решение исходной задачи.

Доказательство теоремы 1.4. Прежде всего, отметим, что функция k = k (L, p, q), которую мы умеем вычислять (предложение 1.2), и длина взаимодействия L(k, p, q) связаны следующим соотношением:

Поскольку утверждение предложения 1.2 справедливо при некоторых ограничениях на L, необходимо проверить, что эти ограничения выполняются при имеющихся в теореме 1.4 условиях на k. Для удобства изложения, эта проверка будет проведена в конце доказательства.

Доказательство теоремы 1.4 начнём c доказательства того, что где функция (k, p, q) является периодической по k с периодом p + q 2.

Покажем, что В самом деле, бланки B(L+pq, p, q) и B(L, p, q) имеют одинаковые хвосты, а значит, в их хвостах при оптимальной специальной расстановке размещается одно и то же количество джокеров. Тело первого из бланков содержит на один блок больше в этом блоке будет размещено (p+q2) джокеров, что и требовалось. Отсюда следует, что Из (1.1) получаем откуда В дальнейшем мы обозначаем через L длину хвоста бланка, а через k количество джокеров в хвосте, т.е. предполагаем, что для некоторого Z выполняется Перейдём к доказательству условий для функции (k, p, q). Вначале докажем часть пункта 3) условия теоремы оценку снизу для функции (k, p, q).

С учётом (1.1), достаточно показать, что в хвосте бланка длиной L = pq(k +1) 1 оптимальная расстановка содержит не более k джокеров.

p+q Согласно пункту 3) предложения 1.2, эта расстановка содержит в хвосте не более L (p+q) 2 джокеров. Осталось заметить, что Оценка снизу доказана.

Пункт 1). Вначале докажем, что max((k, p, q)) < 4q 1. Для этого докажем, что данное неравенство справедливо в трёх частных случаях, после чего покажем, что при любом значении k применим один из этих частных случаев. Параметры w, и являются натуральными числами (параметр w соответствует ширине хвоста в бланке, т.е. w = L /p ; параметр соответствует количеству полных сегментов длины q в хвосте, k + (w 1) 2 = + w 3 по предложению 1.2. Из (1.1) следует, что для любого Тогда Знаменатель последней дроби положителен; докажем, что положителен и числитель. Числитель является квадратным трёхчленом относительно q, после раскрытия скобок приводящимся к виду Его дискриминант после упрощений оказывается равен что позволяет вычислить корни q1 = (2w )/4 и q2 = 2. Поскольку q1 < q по определению w и, q2 < q по условию теоремы и коэффициент при q 2 положителен, то квадратный трёхчлен при допустимых значениях q положителен, а значит, положительна и вся дробь. Таким образом, k + w 2 по предложению 1.2. Воспользовавшись (1.1), получаем для любого и производим аналогичные выкладки для :

Снова знаменатель последней дроби положителен, а числитель является квадратным трёхчленом относительно q; после раскрытия скобок он приводится к виду Вычисляя дискриминант, получаем отсюда находим корни q1 = (2w )/3 и q2 = 2. Как и в случае 1, при допустимых значениях q квадратный трёхчлен положителен, а значит, положительна и вся дробь. Таким образом, 3. Пусть L = q и p = q+ (т.е. w = 1). В этом случае в хвост бланка необходимо поставить (1) джокеров согласно пункту 2) предложения 1.2. Снова пользуясь (1.1), для любого имеем и проводим вычисления для :

Знаменатель последней дроби положителен, числитель приводится к виду 3q 2 + ( 8)q 2 + 4 с корнями q1 = (2 )/3, q2 = 2. Снова при всех допустимых значениях q дробь положительна, откуда Теперь возьмём произвольное k = (p + q 2) + k, k < (p + q 2).

Докажем, что (k, p, q) < 4(q 1). Если k +2 < p/q, положим = k +2, = p q и применим случай 3, получая неравенство (1.4).

Пусть k +2 > p/q. Предположим, что найдётся такое, что k + 4 = + q. Тогда, положив w = q и = wp q, мы можем применить случай 1 и вывести неравенство (1.2).

Предположим теперь, что указанного выше значения не существует.

Поскольку значения выражения + q с ростом на единицу увелиp чивается не более, чем на 2, то существует такое, что Положим w = и = wpq и убедимся в применимости случая 2. В самом деле, если w = = 1, получаем k +2 = < p/q, противоречие;

отсюда w 2. Из (1.5) и (1.6) следует, что (+1)q > q, откуда < q.

Итак, случай 2 применим. Получаем неравенство (1.3).

Теперь докажем, что max((k, p, q)) 2q. Пусть k = (p+q2). Из предложения 1.2 получаем L(k, p, q) = pq + 2q и (k, p, q) = pq + 2q pq = 2q.

Пункт 2). Произведём выкладки, аналогичные приведённым выше.

Пусть p = q + 1 и L = 2q. Тогда всякий q-класс встречается в хвосте ровно 2 раз, т.е. на шаге 2) построения специальной расстановки в хвосте будет поставлено 2 джокеров. В качестве T можно выбрать класс, встречающийся в строке длины 1, после чего на шаге 3) выбрать эту строку. Тогда на шаге 4) количество джокеров уменьшится на 1. В итоге, k = 21. Если же L = 2q 1, то выберем T = {0} этот класс встречается в хвосте 2 1 раз, в том числе в одноэлементной строке (а именно, в предпоследней, в силу выбора p). Таким образом, мы можем ограничиться 2 2 джокерами. Из (1.1) следует, что для любого Тогда Последняя дробь положительна, а при увеличении она стремится к нулю. Таким образом, при любом заданном > 0 и заданном q можно указанным способом выбрать p и k так, чтобы Пункт 3). Из предложения 1.2 следует, что k (pq1, p, q) = (p+q2) 1 и k (pq, p, q) = (p+q2). Из (1.1) получаем, что если k = (p+q2) 1, то L(k, p, q) = pq. Тогда (k, p, q) = pq/(p+q2) и, с учётом нижней оценки для (k, p, q), пункт 3) доказан.

Мы доказали все пункты теоремы. Осталось доказать правомерность применения предложения 1.2, т.е. выполнение приведённых в нём ограничений на L при заданных в теореме ограничениях на k. Пусть вначале q = 3.

Это означает, что что и требовалось. Если же q 4, то Отсюда получаем требуемое условие Доказательство теоремы завершено.

Предложение 1.3. Для фиксированных периодов p, q можно определить точный вид функции (k, p, q) за время, зависящее только от p Доказательство. Из теоремы 1.4 следует, что функция (k, p, q) является периодической по k с периодом p + q 2. Это означает, что достаточно определить (k, p, q) для всех целых k [k, k + p + q 2), где k = 2p/3 1 при q=3 и k = 3p/q +3 при q4, а для этого достаточно определить для данных значений k значения L(k, p, q). Для данного k значение L(k, p, q) на единицу больше, чем длина оптимальной расстановки. Из доказательства теоремы 1.4 следует, что при указанных значениях k существует оптимальная специальная расстановка. Таким образом, для определения для данного k значения L(k, p, q) достаточно определить максимум из длин всех допустимых специальных расстановок. Специальных расстановок для данного k всего q штук (в зависимости от выбора единственного элемента множества T ). Таким образом, время, необходимое для определения точного вида функции (k, p, q), зависит только от p и q.

Глава II Статистические закономерности взаимодействия периодов Зафиксируем взаимно простые периоды p, q. В данной главе рассматриваются расстановки, длина которых меньше длины взаимодействия. В этом случае выполнение свойства взаимодействия периодов зависит от расположения джокеров, и расстановки одинаковой длины с одинаковым количеством джокеров могут иметь различную размерность. Напомним используемые обозначения. Мы обозначаем через M(r, L, k) множество всех расстановок длины L, содержащих k джокеров и имеющих размерность r. Если какой-то параметр заменен знаком, то это означает, что рассматривается объединение таких множеств по всем возможным значениям параметра. Обозначим через P (r, L, k) долю расстановок длины L, содержащих k джокеров и имеющих размерность r, т.е. отношение мощности множества M(r, L, k) к мощности множества M(, L, k). Основным результатом данной главы является эффективный алгоритм для определения P (r, L, k). Время работы наивного алгоритма экспоненциально зависит от длины слова; время работы нашего алгоритма полиномиально зависит от L и p и экспоненциально от параметра q.

§6 Идея алгоритма В данном параграфе излагается основная идея алгоритма. Алгоритм основан на разбиении расстановок из M(r, L, k) на классы и вычислении их количества в каждом классе.

Для того, чтобы разбить расстановки на классы, сопоставим каждой расстановке G расстановку длины pq следующим образом. Пусть l = |G|/pq. Дополним расстановку G нулями до длины lpq. Тогда ее можно представить как конкатенацию расстановок Gi, i = 1,... l, где |Gi | = pq. Применим к словам Gi, i = 1,... l последовательно логическое ИЛИ. Полученную в результате расстановку длины pq назовем характеристической расстановкой.

Пример 2.1. Рассмотрим частичное слово с периодами 4,5 и соответствующую ему расстановку.

Характеристическая расстановка получается из исходной расстановки следующим образом:

1. Дополним исходную расстановку нулями до длины, кратной pq, и представим получившееся слово как произведение слов G1 и G2, |G1 | = |G2 | = pq:

11000001100000000010 000000011100 00000000.

2. К словам G1 и G2 применим последовательно логическое ИЛИ, получая характеристическую расстановку:

G = G2 = 11000001110000000010 характеристическая расстановка Предложение 2.1. Размерность расстановки совпадает с размерностью ее характеристической расстановки.

Доказательство. Рассмотрим p- и q-классы расстановки и характеристической расстановки. Напомним, что если две позиции из разных qклассов, занятые буквами, принадлежат одному p-классу (т.е. связаны при помощи периода p), то в этих q-классах содержится одна и та же буква. Если же любая пара позиций из данных q-классов, принадлежащая одному p-классу, содержит хотя бы один джокер, то эти q-классы могут содержать различные буквы.

Таким образом, размерность расстановки зависит от того, какие qклассы связаны между собой при помощи периода p. Заметим, что в характеристической расстановке единица присутствует в позиции, принадлежащей данным q- и p-классу тогда и только тогда, когда в исходной расстановке единица присутствует хотя бы в одной из позиций, принадлежащих тем же q- и p-классу. Поэтому в характеристической расстановке q- и p-классы связаны между собой так же, как в исходной, а значит размерности исходной и характеристической расстановок совпадают.

Пример 2.2. Продолжим рассмотрение примера 2.1. В соответствующих характеристической расстановке 11000001110000000010 словах множество позиций, в которых стоят буквы, состоит из 6 элементов: D = {1, 2, 8, 9, 10, 19}. Будем нумеровать 4-классы (5-классы) остатком от деления на 4 (соответственно, на 5) номеров позиций, принадлежащих этому классу. Первая и девятая позиции принадлежат первому 4-классу, девятая и девятнадцатая первому 5-классу, а значит, в этих позициях должна стоять одна и та же буква. Вторая и десятая позиции принадлежат второму 4-классу. Больше связей с помощью периодов между позициями из D нет. Значит, соответствующие характеристической расстановке частичные слова могут содержать не более 3 различных букв (например, ab a ). Поэтому размерность характеристиcab ческой (а значит, и исходной) расстановки равна 3.

Поставим в соответствие каждой расстановке ее характеристическую расстановку и разобьем расстановки на соответствующие классы. Тогда для определения P (r, L, k) необходимо найти все характеристические расстановки размерности r, а затем для каждой такой характеристической расстановки определить количество соответствующих ей расстановок из M(r, L, k). Характеристические расстановки можно находить, например, перебором (вычислительная сложность такого перебора зависит только от p и q, и не зависит от длины L, которая может быть сколь угодно большой по сравнению с периодами). Тем не менее, на практике и такой перебор достаточно затруднителен. Поэтому далее будет рассмотрен эффективный способ подсчета характеристических расстановок заданной размерности.

§7 Количество расстановок с заданной характеристической расстановкой Во данном параграфе рассматривается задача вычисления мощности класса расстановок, которым соответствует данная характеристическая расстановка. Из решения этой задачи будет следовать, что можно не перечислять все характеристические расстановки, а разбить их на классы так, что характеристическим расстановкам из одного класса соответствует одно и то же число расстановок, а затем подсчитать число характеристических расстановок в каждом классе. Возможны два варианта интересующей нас задачи:

1. Найти количество расстановок из множества M(, L, ) с данной характеристической расстановкой.

2. Найти количество расстановок из множества M(, L, k) с данной характеристической расстановкой.

Начнем с решения первого варианта задачи. Известно, что в позициях исходной расстановки, соответствующих позициям нулей в характеристической расстановке, должны находиться нули, в остальных позициях могут стоять и нули, и единицы, но каждой единице в характеристической расстановке должна соответствовать хотя бы одна единица в исходной расстановке.

Рассмотрим случай L = lpq. Тогда каждой единице в характеристической расстановке H соответствуют l позиций в исходной расстановке.

В каждой из этих позиций может находиться 0 или 1, что дает 2l комбинаций, однако во всех позициях нули находиться не могут, поэтому каждой единице характеристической расстановки соответствуют 2l комбинаций. Пусть h1 = |H|1 и h0 = |H|0. Таким образом, количество расстановок длины L = lpq, которым соответствует данная характеристическая расстановка H, равно В случае L = lpq + b, 0 < b < pq обозначим через H префикс слова H длины b. Тогда количество расстановок длины L = lpq + b, которым соответствует данная характеристическая расстановка H, равно Таким образом, решение первой задачи можно получить с помощью указанных выше формул за время O(pq), требуемое для вычисления h и h1.

Во втором варианте задачи рассматриваются не все расстановки, которым соответствует данная характеристическая расстановка H, а только те, которые содержат ровно k нулей.

Пусть l = L/pq, k = k lh0. Обозначим через d(k, h1 ) количество расстановок из M(r, L, k), соответствующих данной характеристической расстановке H. При фиксированном l эта величина зависит только от k и количества единиц в H (и не зависит от периодов p, q).

Обозначим через Ki,j множество всех представлений числа i в виде суммы j неотрицательных слагаемых, каждое из которых не превосходит l 1, а через znm m-е слагаемое из n-го представления.

Предложение 2.2. Если L = lpq, то Доказательство. В позициях, соответствующих нулям в характеристической расстановке H, в исходной расстановке также должны стоять нули. Таких позиций в исходной расстановке lh0. Оставшиеся k = k lh нулей нужно расставить в позициях, соответствующих единицам в H.