🗊Презентация Методы построения и анализа алгоритмов. Общая идея структурного синтеза программ

Общая идея структурного синтеза программ

Базой знаний в вычислительных моделях является множество алгоритмов, причем хороших алгоритмов (как тропинки в джунглях не прокладываются плохо, так и в вычислительных моделях накапливаются только хорошие алгоритмы). И комбинации хороших алгоритмов (путь x0x1z1x2x3 в джунглях) тоже могут быть хороши. Они хотя и не обязательно оптимальны, но и не самые худшие. Задача вывода приемлемого алгоритма становиться простой и сводится к ограниченному управляемому перебору на графе. Базой знаний в вычислительных моделях является множество алгоритмов, причем хороших алгоритмов (как тропинки в джунглях не прокладываются плохо, так и в вычислительных моделях накапливаются только хорошие алгоритмы). И комбинации хороших алгоритмов (путь x0x1z1x2x3 в джунглях) тоже могут быть хороши. Они хотя и не обязательно оптимальны, но и не самые худшие. Задача вывода приемлемого алгоритма становиться простой и сводится к ограниченному управляемому перебору на графе.

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

X={x, у, ..., z} конечное множество переменных, F={а, b, ..., с} конечное множество функциональных символов. Пара С=(X,F) называется вычислительной моделью. X={x, у, ..., z} конечное множество переменных, F={а, b, ..., с} конечное множество функциональных символов. Пара С=(X,F) называется вычислительной моделью.

Планирование алгоритма Разработано много различных алгоритмов планирования. Здесь рассматривается хорошо реализуемый алгоритм, который позволяет строить все термы из и имеет линейную временную сложность относительно числа дуг в графическом представлении ПВМ.

Представление графа Представление графа Пусть задана вычислительная модель С=(X,F), которая после трансляции представлена в виде двух таблиц ТХ и ОП. Каждая строка таблицы ТХ имеет вид (х,А(х),соmр(x)), а таблицы ОП ‑ (a,in(a),out(a)). Здесь хX, aF, comp(x)={aFxout(a)}, A(x)={aFxin(a)}. Алгоритм планирования состоит из двух частей: восходящей и нисходящей.

В восходящей части алгоритма строятся множества переменных и операций, используемых в термах из множества ТV=T(V,F). Обозначим V0=V, тогда В восходящей части алгоритма строятся множества переменных и операций, используемых в термах из множества ТV=T(V,F). Обозначим V0=V, тогда F0={aFin(a)V0} {aA(x)in(a)V0} содержит все операции ПВМ такие, что in(a)V0. Далее формируется множество V1={хХхout(а)aF0}V0, на основе V1 строится множество F1= {aА(х)in(a)V1} и т. д. до тех пор, пока при некотором целом положительном k не окажется, что Fk. На этом завершается восходящая часть алгоритма планирования. Множества Vi и Fi, i=0,...,k, содержат все переменные и операции, используемые в термах из множества ТV

Если WVk, то планирование можно прекращать, так как в этом случае существует переменная в W, которая не вычисляется никаким термом из множества ТV, и, следовательно, не существует алгоритма решения сформулированной задачи на основе имеющихся знаний о ПО. В этом случае говорим, что сформулированная задача синтеза неразрешима. В противном случае можно начать строить множества переменных и операций, используемых в термах из . Если WVk, то планирование можно прекращать, так как в этом случае существует переменная в W, которая не вычисляется никаким термом из множества ТV, и, следовательно, не существует алгоритма решения сформулированной задачи на основе имеющихся знаний о ПО. В этом случае говорим, что сформулированная задача синтеза неразрешима. В противном случае можно начать строить множества переменных и операций, используемых в термах из .

Обозначим F*= Fi, и определим множества: Обозначим F*= Fi, и определим множества: Построение множеств Gi и Hi завершается, когда при некотором целом положительном r окажется Gr = . Множества Gi и Hi, i = 1, ..., r, содержат все переменные и операции, используемые в термах из множества .

Построение множеств Gi и Hi завершается, когда при некотором целом положительном r окажется Gr = . Множества Gi и Hi, i = 1, ..., r, содержат все переменные и операции, используемые в термах из множества .

Рекомендуемые учебники

ВОПРОСЫ

ВОПРОСЫ