Различия

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

--- jazyk:soobschenija_o_jazyke_i_metode_ischislenija_ikon:drakon_shampur_ocenka [2012/03/22 16:37]
Владислав Жаринов [Упорядочение маршрутов]
+++ jazyk:soobschenija_o_jazyke_i_metode_ischislenija_ikon:drakon_shampur_ocenka [2012/03/22 16:51]
Владислав Жаринов [Структурная алгоритмизация и шампур-метод]
@@ Строка 7: / Строка 7: @@
-===== Структурная алгоритмизация и шампур-метод =====
-Недостаток силуэтной укладки как физической можно преодолеть, если перейти к логической укладке маршрутов. Имеется в виду, что вход в единицу укладки определяют не соединители, а условия выбора. Часто об условных переходах говорят, что их условие «охраняет» выход, соответствующий истинности (или просто называют условное выражение //**охраной**//). Тогда любой набор значений входящих в это выражение величин, при котором условие истинно, можно называть «паролем» охраны. Понятно, что паролей м.б. и больше одного — это зависит от выражения (вида условий, значений входящих переменных и констант).
-Проще говоря, нужно перейти от деления схемы соединителями к делению разветвителями. Фактически они присутствуют в «петле силуэта», но их условия (охраны) имеют смысл исключительно проверок совпадения значений адреса целевой ветки и имени текущей. Возможность и логической укладки (исключения межветочных БП), и отказа от явных БП в теле схемы даёт //**цикл Дейкстры**// (далее - ЦД) как иная форма универсальной программы. Это можно видеть на схемах ниже.
-{{ :jazyk:soobschenija_o_jazyke_i_metode_ischislenija_ikon:st_drakonsu_-_ocenka_texnojazyka_i_ishm_html_6ead9a8e.gif? |}}
-Для упрощения силуэт мы показали одноадресным и без дополнительных входов.
-Здесь фактически вводится новый тип устремлённого планарного графа, называемый //дейкстралом//. Он обеспечивает универсальность за счёт того, что ЦД-ветви можно выбирать в любом порядке (пока мы не вышли из цикла). Если представить, что телом каждой ветви служит простой шампур-блок (отдельный линейный участок) схемы алгоритма — скажем, примитива, — то это значит, что мы можем организовать в ЦД любой из порядков выбора, возможный в этой схеме.
-В силуэте реален как циклический (действительно идёт против шампура) только один переход — с конца на начало силуэта, когда он «зацикленный» (реагирующий). Остальные переходы на главном маршруте силуэта реально идут по шампуру. Поэтому разветвления для выбора их в петле силуэта фиктивны — никаких условных переходов на самом деле для этой цели не нужно. Как следствие, адрес перехода с главного выхода ветки предопределён — всегда на следующую справа ветку. Можно считать — хотя в шампур-методе это не оговорено, ибо он исходно определён только для «слепышей» — что тексты икон Адрес для главных выходов веток назначаются автоматически по правилу «чем правее, тем позже» — соответственно и циклы по этим выходам невозможны.
-В многоадресном силуэте побочные выходы, возможные в любой неконечной (т.е. заземлённой по шампуру) ветке, могут давать как прямые, так и возвратные переходы — всё зависит от желания сочинителя, т.к. он имеет право ввести в икону Адрес любое имя ветки данного силуэта. Если это имя текущей или более левой ветки — образуется ВМЦ. Вообще говоря, такие циклы тоже нельзя образовывать произвольно, если хотя бы два из них охватывают более, чем по одной ветке. Поскольку тогда возможно пересечение циклов, что в структурной алгоритмизации не допускается.
-В дейкстрале каждый переход между его ветвями реально циклический — т.е. идущий против шампура. Потому и выбор ветви реальный — каждый раз надо проверять условие на входе каждой ветви, начиная слева, пока не обнаружится первое истинное — в эту ветвь и войдёт исполнитель на очередной итерации цикла. Задача сочинителя — так сформулировать выражения охран, чтобы выбирались ветви, нужные по условию задачи. Конечно, и тела ветвей дейкстрала не обязаны быть линейными — в них также м.б. развилки (плечи которых не выходят за пределы тела ветви).
-В принципе можно организовать внутри ветви и один или больше локальных циклов — но часто бывает удобнее замкнуть все циклы алгоритма через кросс дейкстрала. Тогда тело простого цикла целиком будет телом какой-то ветви, а тело гибридного — двух ветвей (для ДО- и ПОКА-частей).
-Принцип практической реализации всех упомянутых типов схем можно показать совмещённо, как на следующем рисунке.
-{{ :jazyk:soobschenija_o_jazyke_i_metode_ischislenija_ikon:st_drakonsu_-_ocenka_texnojazyka_i_ishm_html_7405715d.gif? |}}
-Здесь можно видеть, чем представляются вершины кросса в системе команд типичного исполнитля алгоритмов — машины с адресной архитектурой. Это команды БП — простого и с возвратом.
-Использование ЦД возможно двумя путями:
-  * вывода тела дракон-схемы или его части как ЦД в рамках ШМ-правил (как варианта вложенного цикла);
-  * модификации метода для использования ЦД-организации схем, начиная с аксиом.
-Первый путь требует только единообразного порядка вложения при выводе схемы как примитива — новая ветвь ЦД добавляется вводом дракон-атома обычного цикла как ДО-подтела цикла предыдущего уровня вложенности.
-Второй путь предполагает определение заготовки для вывода схемы как ЦД, ЦД-атома, а также операций добавления/удаления ветви (аналогично добавлению/удалению ветки силуэта).
-Определённая сложность логической укладки в том, что структуру нужно логически выводить изначально, пользуясь методами т.н. доказательного программирования. Для неподготовленного сочинителя это может представлять известную проблему. Возможны следующие пути её решения:
-  * пользоваться известными методами формальной спецификации задачи, хорошо разработанными и допускающими эргономизацию;
-  * приводить разработанные силуэты и/или лианные макроблоки к форме ЦД.
-Среди первых можно выделить т.н. [[http://forum.oberoncore.ru/viewtopic.php?p=52313#p52313|автоматное программирование]]. Спецификации конечными автоматами естественны для задач управляющего (реагирующего) рода и рядом специалистов считаются наглядными.
-Показано, что дракон-силуэт можно преобразовать в ЦД-схему. Тем самым ЦД-укладка обратно совместима с силуэтной. Т.е. можно переводить «силуэтно-унаследованные» визуализации алгоритмов и потоков управления программ в ЦД-запись.
-Важное преимущество ЦД как замены силуэта в том, что его ветви имеют один выход. Тем самым отпадает нужда в ШМ-операции «заземление лианы». Кроме того, в рамках доказательного программирования Дейкстрой, Виртом и другими исследователями было показано, что в теле ЦД также не нужно употреблять явных БП, чтобы получить те же маршруты, что и с их использованием; соответственно не требуется операция «пересадка лианы». Как следствие, редактор, реализующий только логическую укладку, м.б. упрощён в плане как алгоритмов, так и структур данных; очевидно, это даст большую его производительность.
-Другое преимущество в том, что доказательность достигается с участием текста вершин. Тем самым сочинитель уходит от частичной корректности программы в визуализированной форме (которую только и обеспечивает ШМ, как указывал Паронджанов) к полной. Но визуализация может облегчать правильное построение программы и проверку корректности.
 ===== Разметка схем и гибридные техноязыки: ДРАКОН начинает, ГРАФИТ выигрывает =====

Визуальный язык ДРАКОН

Инструменты пользователя

Инструменты сайта

Различия

Инструменты страницы