Элементы теории алгоритмов. Абстрактный алфавит, алфавитный оператор, массовость, результативность, страница 6

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

Рассмотрим нормальные алгоритмы Маркова (НАМ). В качестве исходных данных и конечных результатов они используют строки букв, т. е. слова абстрактного алфавита А. Буквой в алфавите А называют букву, одинаковую с одной из букв, входящих в А. Слово, состоящее из букв в алфавите А, считают словом в этом алфавите. Пусть заданы два алфавита А и В. Если каждая буква А является буквой В, а хотя бы одна из букв В не является буквой в А, то алфавит В называется расширением алфавита А. Например, у4={БИС, СБИС, ЭВА}, Д={БИС, СБИС, ЭВА, РЭА, кристалл}, В—расширение алфавита А. Рассмотрим слово «микросхема». В нем можно, например, выделить м, ми, микро, ро, с, схема, 0 и т. п. Такие слова называются полсловами, они входят в рассматриваемое слово или являются вхождениями в него.

Марковской подстановкой называют операцию над словами, задаваемую парой слов (Р, Q). Суть ее в следующем. В исходном слове С определяется первое вхождение слова Ρ (если оно есть) и без изменения остальных частей слова С производится замена этого вхождения словом Q. Полученное новое слово С' является результатом подстановки (Р, Q) к слову С. Если не определяется ни одного вхождения Р и С, то слово С марковской подстановке не поддается. Например, если С= 832 457, (Ρ, β) =(32,00), то результат марковской подстановки (Р, Q} к слову С запишется С'=800457. Если С=СБИС, (Р, 0)=(С. 0). то С'==СБИС. Если С=БИС. (Ρ, β)=(0, 0), то С'=БИС. Если С=УБИС, (Р. β)=(Π, Μ), то слово С марковской подстановке не поддается. Считается, что символы «-»·» и « -> ·» не являются буквами в алфавите А. Тогда записи вида 1) Р-г Q и 2) Р ->· · Q называют записями марковской подстановки (Р, Q): первая—записью подстановкой, а вторая—заключительной подстановкой. Записи 1) и 2) называют формулами, различая в них левую часть Р и правую часть Q.

Записью НАМ в алфавите А называют столбец формул, левые и правые части которых будут словами в А. Работает НАМ следующим образом. Двигаясь по столбцу формул, определяют первую формулу, левая часть которой входит в преобразуемое слово. Если такой формулы нет, то процесс окончен. При наличии ее выполняется марковская подстановка, изменяющая преобразуемое слово. После этого проверяется, заключительная это подстановка или нет. Если да, то процесс окончен, если нет, то весь процесс повторяется с самого начала [41].

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

Для описания алгоритмов Ляпунова используют логические схемы алгоритмов (ЛСА). В ЛСА операторами называются действия алгоритма, перерабатывающие информацию. Их обозначают заглавными буквами, например А, В, С,... Малыми буквами обозначаются проверяемые логические условия. Последовательное выполнение нескольких операторов обозначается как произведение, причем сомножитель, стоящий справа, действует после сомножителя, стоящего слева. Логической схемой алгоритмов называются выражения, составленные из операторов и логических условий, следующих один за другим. От каждого логического условия начинается стрелка, которая оканчивается у какого-либо из операторов. Например,

Здесь знак  обозначает начало стрелки, а знак —ее конец. Одинаковыми номерами отмечаются начало и конец одной и той же стрелки. Порядок работы операторов ЛСА определяет в зависимости от входящих логических условий. Работа алгоритма начинается с выполнения самого левого члена. После того как некоторый член ЛСА выполнится, определяется, какой член должен следовать за ним. Если это был оператор, то за ним выполняется тот член ЛСА, который стоит непосредственно справа от него. Если последний выполнившийся член ЛСА был логическим условием, то возможны два случая. Если проверявшееся условие выполнено, то должен выполняться член, находящийся справа. Если оно нарушено, должен выполняться тот член, к которому ведет стрелка, начинающаяся после данного условия. Работа алгоритма оканчивается, когда последний из выполняющихся операторов содержит указание о прекращении работы либо на некотором этапе не оказывается члена, который должен выполняться. В ЛСА обычно выделяют операторы a₀и А_k, символизирующие начало и конец работы алгоритма соответственно.