Файл: Вычислительная техника и прикладная математика.pdf

ISSN 1995-4565. Вестник РГРТУ. № 3 (выпуск 33). Рязань, 2010
39
ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА
И ПРИКЛАДНАЯ МАТЕМАТИКА
УДК 510.5
А.В. Пруцков
ЛИНЕЙНЫЕ НОРМАЛЬНЫЕ АЛГОРИТМЫ
Предложена модификация нормальных алгоритмов Маркова, которая
заключается в введении возможности последовательного выполнения под-
становок. Данная модификация позволила уменьшить количество подста-
новок и трудоемкость решения классических задач теории нормальных
алгоритмов Маркова.
Ключевые слова: алгоритмические модели, нормальные алгоритмы
Маркова, обобщения нормальных алгоритмов.
Введение. Задача обращения – задача с
линейной
трудоемкостью.
Целью данной работы является разработка модификации нормальных алгоритмов Маркова с числом выполненных подстановок, линейно зависящим от длины слова, что позволит сократить трудоемкость решения задач. Здесь и далее под трудоемкостью в отношении нормальных алго- ритмов Маркова и их модификаций понимается количество выполненных подстановок, необхо- димых для решения задачи.
Нормальные алгоритмы Маркова являются одной из алгоритмических моделей [1]. В теории нормальных алгоритмов Маркова рассматри- ваются две классические задачи: задача обращения и задача удвоения.
Введем обозначения: n – количество букв алфавита Z={Z
1
, Z
2
, …, Z
n
}; m – длина обра- щаемой строки (m > 0).
Рассмотрим задачу обращения. Пусть в k ячейках находится m пронумерованных шари- ков, при этом k ≥ 2m. Необходимо разместить их в обратном порядке. Для решения задачи необходимо взять предпоследний шарик и положить его за последним шариком (рису- нок 1). Затем взять следующий шарик слева и поместить его в первую пустую ячейку справа от последнего шарика и т. д.
1 2
3 4
Рисунок 1 – Метод решения задачи обращения
Очевидно, что для решения задачи необ- ходимо m – 1 операций поднятия и опускания шарика в ячейку, при этом последний шарик остается на месте. Трудоемкость описанного алгоритма является линейной.
Решим задачу обращения с помощью программы на алгоритмическом языке Паскаль.
Программа включает следующие строки: program p1; const a: string='abc'; b: string=''; var i,n: integer; begin n:=length(a); for i:=1 to n do b:=b+a[n-i+1]; writeln(b); end.
Очевидно, что алгоритм обращения строки, лежащий в основе данной программы, также является линейным по трудоемкости.
Однако известные нормальные алгоритмы решения задачи обращения являются полино- миальными по трудоемкости. Данное обстоя- тельство можно объяснить недостаточностью средств, предоставляемых теорией нормальных алгоритмов Маркова.
Известные
модификации
нормальных
алгоритмов Маркова. Рассмотрим некоторые известные модификации нормальных алгорит- мов Маркова.

40
ISSN 1995-4565. Вестник РГРТУ. № 3 (выпуск 33). Рязань, 2010
Н.М. Нагорный предложил обобщение нор- мальных алгоритмов Маркова (обобщенные нормальные алгоритмы Маркова, обобщения
Н.М. Нагорного) [2]. Первое обобщение (тип ) заключается в том, что алгоритм определяется конечным числом схем и на каждом шаге процесса вырабатывается указание того, какая схема должна выполняться на следующем шаге.
У второго обобщения (тип ') таких схем бесконечно много, и они порождаются некоторым нормальным алгоритмом. В третьем обобщении (тип '') бесконечны и сами схемы.
Подстановка обобщенного нормального алгоритма Маркова имеет следующий вид:
P
L
→ P
R
(I), где P
L
– левая часть подстановки; P
R
– правая часть подстановки; I – индекс перехода к другой схеме.
Рассмотрим принцип работы схемы типа  над словом R.
Алгоритм предписывает проверить, встре- чается ли одна из левых частей подстановок первой схемы системы в слове R. Если ни одна из левых частей не встречается в слове R, то алгоритм завершает работу. Если же левая часть одной из подстановок встречается в слове R, то данная подстановка применяется к слову. Если примененная подстановка имела индекс, равный нулю, то алгоритм завершает работу. Если же индекс примененной подстановки отличен от нуля, то происходит переход к схеме, указанной в индексе подстановки. Далее выполнение алгоритма происходит аналогично. Результатом работы алгоритма считается слово R после применения всех подстановок.
Ограничим описание обобщенных алгорит- мов Маркова типом . Принципы функцио- нирования алгоритмов типа ' и '' в данной статье не приводятся.
Также в работе [2] показано, что для любого обобщения типов , ' и '' может быть построен эквивалентный им нормальный алгоритм
Маркова.
И.А. Цветков предложил самомодифицируе- мые нормальные алгоритмы [3]. Самомоди- фицируемые нормальные алгоритмы являются обобщением нормального алгоритма Маркова, а также предложенных И.А. Цветковым алгорит- мов Маркова с самопополнением схемы, с самоудаляемыми подстановками, с одноразо- выми пополнениями.
Самопополняемые алгоритмы
Маркова могут иметь пополняемые подстановки, которые добавляются в схему во время выполнения нормального алгоритма. При пополнении в начало схемы (слева при записи схемы как слова) модификация называется самопополняе- мым слева алгоритмом Маркова. При попол- нении в конец схемы (справа при записи схемы как слова) модификация называется самопо- полняемым справа алгоритмом Маркова. Каждая пополняющая подстановка при применении добавляет в начало схемы или в ее конец одну простую или одну заключительную подстановку.
Любая подстановка (простая, заключительная, пополняющая) применяется неограниченное число раз. Количество пополнений не ограни- чено. Пополнения одноуровневые, то есть добав- ляется простая или заключительная, но не пополняющая подстановка.
В схеме нормального алгоритма с само- удаляемыми подстановками используются под- становки, которые удаляются из схемы автома- тически после их первого применения. В схеме такого алгоритма есть простые, заключительные и пополняющие подстановки, применяемые неограниченное число раз, а также простые и заключительные подстановки однократного при- менения. Количество пополнений не ограничено.
Пополнения одноуровневые.
В схеме алгоритма Маркова с одноразовыми пополнениями используются подстановки, кото- рые однократно автоматически добавляют в конец схемы одну простую или одну заклю- чительную подстановку. В схеме такого алго- ритма простые, заключительные и пополняющие подстановки применяются неограниченное число раз, но пополняющая подстановка произ- водит пополнение однократно. Пополнения одноуровневые.
На основе анализа перечисленных моди- фикаций выдвинем два требования к пред- лагаемой модификации:
1) модификация должна состоять из одной схемы в отличие от обобщенных нормальных алгоритмов Маркова;
2) схема алгоритма не должна изменяться в отличие от самомодифицируемых алгоритмов
Маркова.
Линейные нормальные алгоритмы. В алгоритмах существуют три типа вычисли- тельных процессов [4]: линейный, разветвляю- щийся и циклический.
Из-за особенности функционирования в нормальных алгоритмах Маркова возможна реализация только двух типов вычислительных процессов: разветвляющегося и циклического.
Ветвление в нормальных алгоритмах Мар- кова реализуется с помощью кодирования ситуаций левыми частями подстановок. В зависимости от сложившейся ситуации во время

ISSN 1995-4565. Вестник РГРТУ. № 3 (выпуск 33). Рязань, 2010
41 решения задачи выбирается и выполняется соответствующая данной ситуации подстановка.
Циклический вычислительный процесс в нормальных алгоритмах Маркова определяется, как правило, двумя подстановками. Первая подстановка определяет тело цикла – подста- новку, выполняющуюся в цикле. Вторая подста- новка в своей левой части содержит условие окончания цикла. Таким образом, первая подстановка выполняется до тех пор, пока не выполнится вторая подстановка.
Очевидно, что для решения линейных задач с линейной трудоемкостью необходима возмож- ность реализации линейного вычислительного процесса.
Предлагается модификация нормальных алгоритмов Маркова, которая заключается в изменении структуры схемы и порядка выпол- нения подстановок. Данную модификацию назовем линейными нормальными алгоритмами.
Схема линейного нормального алгоритма имеет следующий общий вид:
P
1
:
)
1
(
1
)
1
(
1
Q
P

;
)
1
(
2
)
1
(
2
Q
P

; …;
)
1
(
k
)
1
(
k
1 1
Q
P

[•]
P
2
:
)
2
(
1
)
2
(
1
Q
P

;
)
2
(
2
)
2
(
2
Q
P

; …;
)
2
(
k
)
2
(
k
2 2
Q
P

[•]
…
P
d
:
)
d
(
1
)
d
(
1
Q
P

;
)
d
(
2
)
d
(
2
Q
P

; …;
)
d
(
k
)
d
(
k d
d
Q
P

[•]
В схеме обозначения P только с нижним индексом и P и Q с верхним и нижним индекса- ми являются подстроками; k
1
, k
2
, …, k d
= 1, 2, … .
Каждая строка схемы содержит метку P c нижним индексом и соответствующие данной метке одну или несколько подстановок.
Метка строки может не совпадать с левой частью первой подстановки в строке.
Алгоритм работает со строкой R следующим образом. Схема просматривается сверху вниз, и из схемы выбирается та строка схемы, метка P которой содержится в строке R. Если метка P найдена, то выполняются последовательно слева направо подстановки, соответствующие метке P, в строке R, то есть каждая подстановка выполняется только один раз. В следующий раз подстановка может быть выполнена только при следующем просмотре схемы. Таким образом, в линейных нормальных алгоритмах подстановки выполняются последовательно и при просмотре сверху вниз. Как и в нормальных алгоритмах
Маркова, подстановка заключается в замене в строке R первого вхождения слева подстроки из левой части подстановки на подстроку из правой части подстановки.
После того как все подстановки, соответствующие метке P, выпол- нены, схема просматривается вновь, начиная с первой подстановки.
Подстановки, помеченные пустым символом
, выполняются для любой строки R.
Алгоритм заканчивает выполнение в двух случаях:
1) ни одна метка P не встречается в строке R;
2) выполнена заключительная подстановка, заканчивающаяся символом «•».
Если алгоритм заканчивает свою работу
(прекращает выполнение) со строкой R, то алгоритм считается применимым к строке R.
Результатом работы алгоритма является стро- ка R после применения всех подстановок.
Если алгоритм никогда не заканчивает свое выполнение (зацикливается) со строкой R, то алгоритм считается неприменимым к строке R и результат работы алгоритма неопределен.
Вернемся к задаче обращения. Запишем схему нормального алгоритма обращения с использованием аппарата линейных нормальных алгоритмов. Будем использовать только одну вспомогательную букву. Схема состоит из следующих подстановок.
1) Z
i
: Z
i
 → ; → +Z
i
;i = 1, 2, …, n
2) :
 →  •
3) :
→ +
Указатель  устанавливается в конец строки
(подстановка 3).
Каждый символ строки, который находится слева от указателя , удаляется, а затем добавляется в конец строки
(подстановка 1). Таким образом, символы строки удаляются перед указателем  и появляются справа от него в обратном порядке. Условием окончания работы алгоритма является отсутст- вие символов слева от указателя  (подста- новка 2). При выполнении данного условия указатель  удаляется из строки.
Пример 1. Рассмотрим работу линейного нормального алгоритма обращения на примере числа 123 по шагам для алфавита Z = {1, 2, 3}. За один шаг может выполняться более одной подстановки.
0.
123 1.
3) : → +
123
2-3. 1) 3: 3 → ; → +3 123 4-5. 1) 2: 2 → ; → +2 132 6-7. 1) 1: 1 → ; → +1
321 8.
2) :  →  •
321
На последнем шаге алгоритма получено число 321 – обращение числа 123. □
Сравним данные о трудоемкости и о количестве подстановок предложенного алго- ритма обращения, а также обращающего нор- мального алгоритма, предложенного А.А. Мар- ковым и Н.М. Нагорным [1], и обращающего

42
ISSN 1995-4565. Вестник РГРТУ. № 3 (выпуск 33). Рязань, 2010
самопополняемого слева алгоритма, предложен- ного И.А. Цветковым [3] (таблица 1).
Использование линейных нормальных алго- ритмов позволило изменить тип алгоритма с полиномиального на линейный, сократив трудо- емкость алгоритма, и уменьшить количество подстановок.
Таблица 1
Название алгоритма обращения
Трудоемкость
Количество подстановок алгоритма
Тип алгоритма
Нормальный алгоритм обращения
А.А. Маркова и Н.М. Нагорного m
2
/2 + 5m/2 + 1 8n
2
+ 8n + 15
Полиномиальный
Нормальный алгоритм обращения
И.А. Цветкова m
2
/2 + 3m/2 + 3 8n
2
+ 25
Полиномиальный
Линейный нормальный алгоритм обращения
2m + 2 2n + 2
Линейный
Сводимость
нормальных
алгоритмов
Маркова к линейным нормальным алгорит-
мам. Схему любого нормального алгоритма
Маркова можно привести к схеме линейного нормального алгоритма по следующим пра- вилам:
- добавить метку к каждой подстановке, причем метка равна левой части подстановки;
- если левая часть подстановки пустая, то обозначить метку пустым символом .
Таким образом, для нормальных алгоритмов
Маркова каждой метке соответствует строка только с одной подстановкой.
Пример 2. Приведем нормальный алгоритм удвоения, предложенный в работе [5], к линейному нормальному алгоритму.
Исходный нормальный алгоритм удвоения слова алфавита Z = {a, b} включает следующие подстановки.
1)
a → aa
2)
b → bb
3)
aa → aa
4)
ab → ba
5)
ba → ab
6)
bb → bb
7)
 → 
8)
 →  •
9)
→ +
Воспользуемся правилами приведения и получим следующие подстановки схемы линей- ного нормального алгоритма:
1)
a:
a → aa
2)
b: b → bb
3)
aa: aa → aa
4)
ab: ab → ba
5)
ba: ba → ab
6)
bb: bb → bb
7)
:
 → 
8)
:
 →  •
9)
:
→ + □
Возможность сводимости алгоритмов объяс- няется тем, что линейный нормальный алгоритм позволяет выполнять подстановки в том же порядке при просмотре сверху вниз, что и нормальный алгоритм Маркова.
Сводимость схемы любого нормального алгоритма Маркова к схеме линейного нормаль- ного алгоритма влечет два следствия:
1) любую задачу, которую можно решить с помощью нормального алгоритма Маркова, можно решить и с помощью линейного нормаль- ного алгоритма;
2) трудоемкость любого линейного нормаль- ного алгоритма будет не хуже трудоемкости нормального алгоритма Маркова, но не наобо- рот.
Обратная сводимость от линейных нормаль- ных алгоритмов к нормальным алгоритмам
Маркова возможна при выполнении двух условий:
1) в каждой строке схемы находится только одна подстановка;
2) метка строки равна левой части подста- новки строки.
Задача удвоения строки. Рассмотрим еще одну классическую задачу теории нормальных алгоритмов Маркова – задачу удвоения, которая заключается в преобразовании слова R в слово
RR.
Задачу удвоения можно решить и с помощью предложенных линейных нормальных алгоритмов. Для удвоения элементов строки необходимо добавлять последовательно в конец строки копии элементов, имеющихся в строке
(рисунок 2). Очевидно, что трудоемкость такого алгоритма будет линейной.
1 2
3 4
1 2
3 4
Рисунок 2 – Метод решения задачи удвоения

ISSN 1995-4565. Вестник РГРТУ. № 3 (выпуск 33). Рязань, 2010
43
Схема линейного нормального алгоритма решения задачи удвоения слова алфавита
Z = {a, b} будет состоять из следующих подстановок.
1) a: a → a;  → a
2) b: b → b;  → b
3)
:
 → ;  →  •
4)
:
→ +
В конец строки добавляются указатели  и 
(подстановка 4). Работа алгоритма заключается в перемещении указателя  влево и добавлении
(копировании) символа перед указателем  в конец строки, обозначенный указателем 
(подстановки 1-2).
После того как перед указателем  не остается символов, алгоритм заканчивает выполнение (подстановка 3).
Пример 3. Рассмотрим работу линейного нормального алгоритма удвоения на примере той же строки bab по шагам.
0. bab
1.
4) : → + bab
2-3. 2) b: b → b;  → b babb
4-5. 1) a: a → a;  → a babab
6-7. 2) b: b → b;  → b
babbab
8-9. 3) :  → ;  →  • babbab
На девятом шаге алгоритма получена строка babbab – удвоение строки bab. □
Трудоемкость и количество подстановок предложенного линейного алгоритма удвоения, а также нормальных алгоритмов удвоения слова алфавита Z = {a, b}, предложенных в работах
А.А. Маркова и Н.М. Нагорного [1] и В.А. Мо- щенского (см. пример 2) [5], представлены в таблице 2.
Таблица 2
Название алгоритма удвоения
Трудоемкость
Количество подстановок алгоритма
Тип алгоритма
Нормальный алгоритм удвоения
А.А. Маркова и Н.М. Нагорного m
2
/2 + 5m/2 + 2 10
Полиномиальный
Нормальный алгоритм удвоения
В.А. Мощенского m
2
/2 + 3m/2 + 2 9
Полиномиальный
Линейный нормальный алгоритм удвоения
2m + 3 7
Линейный
Использование линейных нормальных алго- ритмов и в случае задачи удвоения позволило снизить трудоемкость алгоритма, сделав его линейным, а также уменьшить количество подстановок схемы.
Сводимость линейных нормальных алго-
ритмов к обобщенным нормальным алгорит-
мам Маркова. Любой линейный нормальный алгоритм можно свести к схеме типа  обобщений Н.М. Нагорного. Сведение алгорит- мов выполняется по следующим правилам.
1. В схему 1 выписываются первые подста- новки каждой строки.
2. Если метке соответствует несколько подстановок, то каждая подстановка, кроме первой, записывается отдельной схемой, состоя- щей из одной подстановки. При этом схемы нумеруются соответствующими индексами, чтобы обеспечить их последовательное выпол- нение. Последняя подстановка, если она не явля- ется заключительной, имеет индекс 1, возвра- щающий управление схеме 1.
3. Если метка и левая часть первой подста- новки не совпадают, то в схему 1 включается незначащая подстановка P → P, где P – метка.
Первая подстановка и другие подстановки запи- сываются в отдельные схемы по принципу, опи- санному в правиле 2. Незначащая подстановка передает управление схеме с первой подста- новкой данной строки.
4. Заключительные подстановки имеют индексы 0.
Из данных правил следует, что количество схем обобщенного нормального алгоритма N
схем зависит от числа строк схемы с более чем одной подстановкой и числа строк схемы, в которых метка отличается от левой части первой подстановки строки, и вычисляется по формуле:
N
схем
= N
подст
– N
стр
+ N
мет
+ 1, где N
подст
– количество подстановок в строках схемы, в которых более одной подстановки; N
стр
– количество строк схемы, в которых более одной подстановки; N
мет
– количество строк схемы, в которых метка отличается от левой части первой подстановки строки; + 1 – основная схема (схема 1).
Пример 4. Сведем предложенный линейный нормальный алгоритм удвоения к обобщенному нормальному алгоритму Маркова. Воспользу- емся правилами сведения и получим следующие схемы.
Схема 1:
1) a → a (2)
2) b → b (3)