Проектирование алгоритма через организацию таблицы векторов состояний данных

Разумовский А.И.,ктн, снс,

ИПУ РАН, Москва

Основной проблемой на пути планирования и реализации произвольного программного модуля САПР является разрешение цикличности условий и взаимозависимостей между функциональными элементами его алгоритма.

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

- определение свойств входящих данных, их формата, и возможности декомпозиции на элементарные объекты.

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

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

- определение квалификаторов, как объектов фиксации результатов взаимодействия среды данных (в определенном состоянии ) и среды условий, формируемых на этапе задания квалификаторов.

Рис. 1

Среда данных отделена от среды условий и квалификаторов (рис. 1). Таким образом, достигается независимость условных предложений от функционального поведения при возникновении произвольного состояния той или иной среды. Из этого следует также и тот факт, что число условий, участвующих во взаимодействии-анализе со средой данных, изначально не определено, то есть – произвольно, а значит, существует возможность организации управления такого взаимодействия на основании динамического встраивания в функционирующую систему вновь определенных условий. Это свидетельствует о независимости локальных алгоритмов и, вследствие этого, повышения надежности процесса проектирования алгоритма, если его модель сконфигурирована подобно описанному образом.

Квалификатор фиксирует состояние среды данных посредством изменения таблицы результатов условий и записи определенных результатов. (рис. 2)

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

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

Каждая квалификация осуществляется только один раз за такт изменения состояния среды данных. Однако, поскольку каждая квалификация может включать в себя одновременно несколько групп проверочных условий, необходимо гарантировать, чтобы проверочные условия формировались вне текущего такта изменения состояния. В противном случае, произойдет циклическая зависимость условий друг от друга. Также может произойти частичная квалификация, то есть вариант, при котором обрабатывается лишь одна группа условий, прочие же группы могут быть не обработаны вовсе по причине «несрабатывания» однотактных условий.

Однотактные условия – это условия, формируемые и востребованные в течение одного такта изменения состояния среды данных.

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

Порядок определения квалификаторов.

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

Цепь условий, используемая для положительной квалификации, обычно размещается в различных квалификаторах, часть из которых объектные, прочие – вторичные. Распределение проверочных условий по различным квалификаторам связано с возможной необходимостью организации нескольких цепей условий для различных квалификаций.

Порядок формирования условий

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

- определение количества существующих границ квалификатора (обычно не более двух);

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

- определение условия правой границы (и прочих определенных границ).

- определение условия «содержания», соотносимого с контролем над качеством каждого символа искомого элемента; при обнаружении нарушения качества может быть организован дополнительный bad-квалификатор для квалификации bad-элементов, либо аннулирование ожидаемого элемента и всех, связанных с процессом квалификации факторных и событийных условий.

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

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

Литература.

1. Артамонов Е.И., Хачумов В.М. Синтез структур специализированных средств машинной графики. М., Институт проблем управления.-1991