Математическая модель алгоритма

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

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

Оценка вычислительной и емкостной сложности требует следующей информации:

• вид операций, их вычислительная сложность в функции от базисных и количество повторений этих операций;

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

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

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

• операторы управления и преобразования данных, их типы и вычислительная сложность;

• управляющие связи между операторами - отношения достижимости Д1(О, О) с учетом вероятности их реализации;

• исходные, промежуточные и окончательные данные, их размерности и, возможно, типы структур;

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

Для отображений компонентов 1-го вида и отношений между ними используется управляющий граф G (< X, p 0, q 0>, F 1 X) с двумя выделенными вершинами p 0 и q 0 (начало и конец).

Управляющий граф называется правильным, если все его вершины принадлежат хотя бы одному пути из p 0 в q 0.

Правила перехода от алгоритму к управляющему графу

1. Множество операторов поставим во взаимнооднозначное соответствие множеству вершин: O «X.

2. Тип (вычислительную сложность) оператора отобразим, задав однозначные, возможно, взаимно однозначные отображения:

R 1 - X R 1 T, R 2 - X R 2 Q.

3. Отношение достижимости операторов Д1(О, О) будет соответствовать двуместному предикату смежности F1(Х, Х) множества вершин:

Д1(О, О) ~ F1(Х, Х).

4. Вершинам, принадлежащим образам F 1 xi вершин разветвления потока управления, присвоим вес из множества L = { true, false }, определяющий связь со значением предиката, вычисленным в вершине проверки условия, и вес из множества Е – вероятностей переходов. Для чего, зададим однозначные отображения R 3 и R 4 подмножеств F 1 xi во множества L и E:

F 1 xi R 3 L, F 1 xi R 4 E.

5. Вершинам прообразов F 1-1 xi вершин разветвления потока управления, присвоим аналогичные веса:

F 1-1 xi R 5 L, F 1-1 xi R 6 E.

Получим ориентированный управляющий граф с взвешенными вершинами в множестве Х и в подмножествах, представляющих их образы и прообразы,

G у (< Х, T, Q >, {< F 1 Х, L, E >, < F 1 - 1 Х, L, E >})

В модели «оператор-данные» нет необходимости задавать связи между операторами, типы операторов (их вычислительную сложность), функциональные и предикатные символы или их интерпретацию, так как они уже отображены в графе G У.

Вторая часть модели алгоритма должна отображать связи данных с операторами. Компоненты алгоритма, которые будут сопоставляться вершинам графа, распадаются на два непересекающихся множества: данные и операторы: C ={ D, O }. Для связей операторов и данных существенно являются ли последние входными или выходными. Обозначим отношение операторы-данные и данные-операторы через Д2(О, D) и Д3(D, О) соответственно. Правила перехода к этой модели:

1. Множеству операторов алгоритма О поставим во взаимно однозначное соответствие подмножество вершин X Ì Z, а множеству данных D (символов переменных базиса DB) – подмножество вершин Y Ì Z:

O «X, D «Y, причем X Ç Y = Æ, X È Y = Z.

Здесь во множество данных D включены и промежуточные результаты работы алгоритма.

2. Отношения Д2(О, D) и Д3(D, О) будут соответствовать двуместным предикатам смежности F 2(Х, Y) и F 3(Y, Х):

Д2(О, D) ~ F 2(Х, Y) и Д3(D, О) ~ F 3(Y, Х).

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

G o.д ({ X, Y }, F 2 Х, F 2-1 Х, F 3 Y, F 3-1 Y).

Связи «данные-данные», задающие их зависимость, могут быть определены, используя образы и прообразы вершин этого графа. Пусть yk ↔ dk – промежуточный или окончательный результат. Множество Yk, на основании которого он был получен, определяется по схеме:

xk = F 3-1 yk, Yk = F 2 xk.

Интегральная модель Интегральной моделью алгоритма может служить граф:

G = G у È G o.д.

G (< Х,T, Q >, Y,< F 1 Х, L, E >,< F 1 - 1 Х, L, E >, F 2 Х, F 2-1 Х, F 3 Y, F 3-1 Y) =

= G у(< Х,T, Q >,< F 1 Х, L, E >,< F 1 - 1 Х, L, E >) È

G o.д ({ X, Y }, F 2 Х, F 2-1 Х, F 3 Y, F 3-1 Y).