МОДИФИКАЦИЯ АЛГОРИТМА МОДЕЛИРОВАНИЯ ПЕРИОДИЧЕСКИХ ГРУПП

Аннотация

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

Полный текст

Ранее был предложен алгоритм [1], позволяющий моделировать периодические группы [2] посредством специального объекта - системы, изменяя параметры которой, можно управлять структурой получаемой группы. Одним из ключевых звеньев указанной сис- темы является алгоритм n-апериодичности, который преобразует слова, содержащие n-периодичности, в n- апериодические слова. Дадим несколько определений. Под алфавитом будем понимать конечный упорядоченный набор сим- волов. Слово - это конечная последовательность сим- волов из алфавита. Пусть В = {в1, в2 ,…, вk} - алфавит Если выражение (1) не выполняется, делаем проверку неравенства: i < (l - jn + 1) . (2) Если выражение (2) выполняется, то уве- личиваем значение параметра i на единицу i = i + 1, смещая тем самым слова xk на один индекс вправо в w. Затем возвращаемся к п. 5. Если выражение (2) не выполняется, про- веряем истинность неравенства j < [l / n] . (3) Если неравенство (3) выполнятся, то и w = v1v2 …, vl - слово в этом алфавите, vi ÎB j = j + 1. Возвращаемся к п. 4. (i = 1, 2, …, l). Натуральное число l будем называть длиной слова v. Функция L(v) определена на множест- ве всех слов и равна длине слова v, т. е. L(v) = l для слова v, указанного выше. Говорят, что слово x входит в слово w, если можно указать такие слова p и q, что w = pxq. Если при этом слово p (слово q) пусто, то говорят, что x есть начало (конец) слова w. Слово вида Если неравенство (3) не выполняется, w - n-апериодическое слово. Алгоритм завершен. Разработанный алгоритм n-апериодичности отли- чается от базового тем, что поиск n-периодических подслов осуществляется от их максимально возмож- ной длины до 1. Описание данного алгоритма пред- ставлено ниже. K w = xx x 123 n раз будем называть n-периодическим. Слово Задаем исходное слово w. Вычисляем длину слова w: L(w) = l. w будем называть n-апериодическим, если в него не входит никакое непустое слово вида xn, т. е. w ¹ pxxK xq . 14243 n раз Базовый алгоритм n-апериодичности, который преобразует любое слово w в n-апериодическое, со- кращая всевозможные слова вида xn в w, представлен ниже. Задаем исходное слово w. Вычисляем длину слова w: L(w) = l. Если l < n, то слово w заведомо является n- апериодическим. Алгоритм завершен. Если l ≥ n, тогда задаем n последовательно идущих в w слов x1x2…xk…xn одинаковой длины, т. е. w = px1x2…xk…xnq, L(x1) = L(x2) =…= L(xn). Длину и месторасположение слов xk (k = 1, 2, …, n) в слове w зададим посредством двух параметров i и j, где j = 1, 2, …, [l/n] ([l/n] - целая часть от отношения l/n) - параметр, задающий длину слов xk; i = 1, 2,…, (l-jn + 1) - параметр, задающий месторасположение слов xk в слове w. Таким образом, xk = wi + j(k-1)…wi + jk-1. Задаем начальное значение длин слов xk: j = 1. Задаем начальное месторасположение слов xk: i = 1 (при i = 1 последовательность слов xk начинается сна- чала слова w, т. е w = x1x2…xk…xnq). Сравниваем слова: x1 = x2 = ... xn . (1) Если выражение (1) выполнятся, то слово w сокращается, т. е. w = px1x2…xk…xnq → w = pq. Воз- вращаемся к п. 2. Если l < n, то слово w заведомо является n- апериодическим. Алгоритм завершен. Если l ≥ n, тогда задаем n последовательно идущих в w слов x1x2…xk…xn одинаковой длины, т. е. w = px1x2…xk…xnq, L(x1) = L(x2) =…= L(xn). Длину и месторасположение слов xk (k = 1, 2, …, n) в слове w зададим посредством двух параметров i и j, где j = 1, 2, …, [l/n] ([l/n] - целая часть от отношения l/n) - параметр, задающий длину слов xk; i = 1, 2 ,…, (l-jn + 1) параметр, задающий месторасположение слов xk в слове w. Таким образом, xk = wi + j(k-1)…wi + jk-1. Задаем начальное значение длин слов xk: j = [l/n]. Задаем начальное месторасположение слов xk: i = 1 (при i = 1 последовательность слов xk начинается с начала слова w, т. е w = x1x2…xk…xnq). Сравниваем слова: x1 = x2 = ... xn . (4) Если выражение (4) выполнятся, то слово w сокращается, т. е. w = px1x2…xk…xnq → w = pq. Воз- вращаемся к п. 2. Если выражение (4) не выполняется, делаем проверку неравенства i < (l - jn + 1) . (5) Если неравенство (5) выполняется, то уве- личиваем значение параметра i на единицу i = i + 1, смещая тем самым слова xk на один индекс вправо в w. Затем возвращаемся к п. 5. Если неравенство (5) не выполняется, проверяем истинность неравенства j > 1 . (6) image 1 Работа выполнена при поддержке гранта Президента РФ для поддержки молодых ученых (МК-2494.2008.1). Если неравенство (6) выполнятся, то j = j - 1. Возвращаемся к п. 4. Если неравенство (6) не выполняется, w - n-апериодическое слово. Алгоритм завершен. Данная модификация алгоритма n-апериодичности позволила сократить время расчета элементов и соот- ношений в бернсайдовых (В(2, 3), В(2, 4), В(3, 3)) [3] и других периодических группах на 18 %.