Методы построения и анализа алгоритмов

Алгоритмы: Анализ и Построение
Общая идея структурного синтеза программ

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

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

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

Алгоритмы: Анализ и Построение

Алгоритмы: Анализ и Построение

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

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

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

Алгоритмы: Анализ и Построение
V={x1,x2},
W={x10}
Сверху множества Fi и Vi, образовавшиеся в результате восходящей части алгоритма планирования на ПВМ справа

Алгоритмы: Анализ и Построение
Множества Gi и Hi (сверху) сформировались в нисходя-щей части алгоритма плани-рования. После завершения планирования остаются лишь переменные и операции из множеств Gi и Hi , остальные удаляются (справа).

Алгоритмы: Анализ и Построение
Таким образом, результатом планирования является ПВМ, оставшаяся от С после удаления “лишних” переменных и операций. Множество не строится, подходящий в некотором смысле (V,W)-план Т строится в каждом конкретном случае процедурой выбора алгоритма.

Алгоритмы: Анализ и Построение
В случае, когда W⊄Vk, сформулированная задача синтеза оказывается неразрешимой и необходимо изменить формулировку задачи, т. е. либо уменьшить 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 стр. (есть в библиотеке)
Рекомендуемые учебники

Алгоритмы: Анализ и Построение
Что мы называем алгоритмом? Почему?
Сколько существует алгоритмов и программ, вычисляющих вычислимую функцию?
Задача, ее модель, алгоритм решения
Задача управления движением на перекрестке и ее модель
Три подхода к решению комбинаторной задачи
Задача раскраски графа. Жадный алгоритм раскраски графа
Абстрактные типы данных. Что такое?
ВОПРОСЫ