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

является множество алгоритмов, причем хороших алгоритмов (как тропинки в

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

же как массив джунглей разбиваются тропинками на фрагменты, так

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

множество переменных, F={а, b, ..., с} конечное множество функциональных

символов. Пара С=(X,F) называется вычислительной моделью.

T1, T1⊆T(V,F). Впредь будем работать только с термами из

T1. Это конечные множества.
Множество термов ={t∈T1⎜out(t)∩W≠∅}.
Это множество задает все вычисления, которые основаны на V и завершаются в W.
Множество термов R⊆ такое, что ∀x∈W∃t∈R(x∈out(t)) называется (V,W)-планом вычислений. Ясно, что (V,W)-план задает детерминант вычислимой функции, которая вычисляет переменные W из переменных V

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

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

С=(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, тогда
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, которая не вычисляется никаким термом из множества ТV, и, следовательно, не существует алгоритма решения сформулированной задачи на основе имеющихся знаний о ПО. В этом случае говорим, что сформулированная задача синтеза неразрешима. В противном случае можно начать строить множества переменных и операций, используемых в термах из .

Fi, и определим множества:



Построение множеств Gi и Hi завершается,

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

завершается, когда при некотором целом положительном r окажется Gr

= ∅. Множества Gi и Hi, i = 1, ..., r, содержат все переменные и операции, используемые в термах из множества .

Fi и Vi, образовавшиеся в результате восходящей части алгоритма

планирования на ПВМ справа

(сверху) сформировались в нисходя-щей части алгоритма плани-рования. После завершения

планирования остаются лишь переменные и операции из множеств Gi и Hi , остальные удаляются (справа).

является ПВМ, оставшаяся от С после удаления “лишних” переменных

и операций. Множество не строится, подходящий в некотором смысле (V,W)-план Т строится в каждом конкретном случае процедурой выбора алгоритма.

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

задачи, т. е. либо уменьшить W, удалив из него невычислимые переменные, либо расширить V, включив в него такие новые переменные, что станут вычислимыми все переменные из W. Для уменьшения затрат на расширение V может быть использован алгоритм планирования. Для этого необходимо выполнить его нисходящую часть из множества переменных W'=W\Vk с использованием всех операций из F. Все переменные из построенных при этом множеств Hi, i=1, 2, ..., r, являются кандидатами на включение в V. Из них человек может выбрать те переменные, значения которых ему доступны.

что проверка условия in(a)⊆ Vi делается не более одного

раза для каждой входной дуги произвольно взятой операции а, а проверка условия out(a)∩Hi-1≠∅ - не более одного раза для каждой выходной дуги а. Понятно, что алгоритм планирования имеет линейную относительно числа дуг в графическом представлении ПВМ временную сложность, если в качестве элементарных шагов алгоритма взять проверки in(a)⊆Vi и out(a)∩ Hi-1 ≠∅.

и операции в ТХ и ОП могут кодироваться целыми

положительными числами. Для представления всевозможных множеств переменных — А(х), in(a), Vi, Fi и т. д., — можно использовать битовые шкалы. Шкала Vi, к примеру, содержит в k-й позиции единицу, если переменная номер k принадлежит Vi. Применение битовых шкал сводит проверку условий in(a)⊆Vi и out(а)∩Hi-1≠∅ к двум логическим операциям.

Ульман, Джеффри, Д. Структуры данных и алгоритмы. : Пер.

с англ. : Уч. пос. — М. : Издательский дом "Вильяме", 2000. — 384 с.
Кормен Т., Лейзерсон Ч., Риверс Р., Штайн К. Алгоритмы. Построение и анализ – М.: «Вильямс», 2012
В.Э.Малышкин, В.Д.Корнеев. Параллельное программирование мультикомпьютеров. – В серии «Учебники НГТУ», Новосибирск, изд-во НГТУ, 2011, 296 стр. (есть в библиотеке)

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

существует алгоритмов и программ, вычисляющих вычислимую функцию?
Задача, ее модель,

алгоритм решения
Задача управления движением на перекрестке и ее модель
Три подхода к решению комбинаторной задачи
Задача раскраски графа. Жадный алгоритм раскраски графа
Абстрактные типы данных. Что такое?

ВОПРОСЫ