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

Нажмите для полного просмотра!

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Методы построения и анализа алгоритмов. Общая идея структурного синтеза программ. Доклад-сообщение содержит 24 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

Слайд 2

Описание слайда:

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

Слайд 3

Описание слайда:

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

Слайд 4

Описание слайда:

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

Слайд 5

Описание слайда:

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

Слайд 6

Описание слайда:

Слайд 7

Описание слайда:

Слайд 8

Описание слайда:

Слайд 9

Описание слайда:

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

Слайд 10

Описание слайда:

Представление графа Представление графа Пусть задана вычислительная модель С=(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)}. Алгоритм планирования состоит из двух частей: восходящей и нисходящей.

Слайд 11

Описание слайда:

В восходящей части алгоритма строятся множества переменных и операций, используемых в термах из множества Т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

Слайд 12

Описание слайда:

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

Слайд 13

Описание слайда:

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

Слайд 14

Описание слайда:

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