Инфологическое обеспечение | Когнитивное | Графит-букварь
Стр. 1 2 3 4 5 6 7 8 9 10 11 12
Содержание
Нешампур-вершины: Конец, Адрес, Петля цикла и Петля силуэта, границы цикла ДЛЯ
Нешампур-вершины: Конец, Адрес, Петля цикла и Петля силуэта, границы цикла ДЛЯ
В алгоритме нужно показать нелинейности, отличающиеся от ветвления. Во-первых, это повторы отдельных фрагментов (участков маршрута) при некоторых условиях. Во-вторых, это соединения отдельных частей алгоритма на плоскости. Для этого используются структуры, основанные на безусловных переходах, допустимых в техноязыке; будем называть их разрешёнными (Р-БП).
В алгоритмике традиционно особо выделяют цикл с числовым параметром как конечный инвариант любых итераций. В техноязыке он именуется цикл ДЛЯ, а его границы (по главной вертикали) показывают особые виопы. Имея один вход и один выход, они тем не менее не вводятся в шампур поодиночке.
Начнём с вершин перехода, сопрягаемых с вершинами-петлями.
Адрес. Означает команду разрешённого БП по петле силуэта на ветку, указанную в тексте. Параметр команды (адрес перехода) символически представлен текстом-именем ветки; в предметной форме параметром служит адрес, с которого располагается эта ветка в памяти исполнителя.
Конец. Виоп имеет значение команды возвратного БП; меткой для него служит вершина Вставка в вышележащем алгоритме. Для внешнего визуала в дракон-модели (т.е. когда выйти более некуда) виоп трактуется как останов работы исполнителя; фактически это справедливо обычно лишь для алгоритма управляющего процесса (программы), при завершении любых других программ управление передаётся ей.
При возврате из вставки-функции возвращается также значение (единственное, но любого типа и соответственно любой мыслимой конечной структуры, определённой по правилам деклар-языка). Это значение можно указывать в тексте вершины Конец (или присоединённой сбоку вершины Формальные параметры); тем самым будет чётко выделяться случай функции.
Строго говоря, вершины-петли – это определённые подсхемы, т.е. вершины с присоединёнными линиями. Некоторые вершины имеют более одного входа или выхода.
Свободные концы вершин можно считать временно (до вставки петли в дракон-схему) присоединёнными к особым вершинам-туннелям, имеющим только один вход (или выход). Текст туннелей поясняет вхождение петли.
Смысл петли силуэта – сопряжение вершин разрешённого БП. Под этим понимается простой переход (типа goto в текстовых прогязыках). Он состоит из псевдооператора-метки (в техноязыке – вершина Имя ветки; меткой служит её текст) и оператора-команды перехода на данную метку (в техноязыке – виоп Адрес). Возможно, что команда перехода на данную метку в силуэте не единственная; метки же в одном силуэте уникальны (что мы пояснили формулами на рисунке).
Виоп Петля силуэта в техноязыке показывается упрощённо: вершины, не являющиеся операторами, не изображаются, а только подразумеваются. Снимем упрощения; в результате получим схему, показанную на рисунке.
Структура петли силуэта как бинарного графа
Здесь мы использовали исключительно бинарные вершины разветвления/соединения. Нижняя схема на рисунке раскрывает смысл структуры «шапочного разбора», изображаемой по правилам техноязыка упрощённо в виде «гребёнки».
Важно понимать, что вершина-разветвитель «шапочного разбора» логически представляет развилку по условию. В данном случае условие формулируется от номера заземлённой лианы, с которой переходим на данную ветку в текущем маршруте; это можно представить сложным ветвлением, показанным внизу. Номер должен храниться в служебной переменной, значение которой устанавливается при выходе из лианы в петлю; именно это имел в виду Паронджанов, говоря в /1, с.100/ о том, что без силуэта укладка маршрутов требует переменной-идентификатора ветки. Здесь она именуется b (от branch — ветка).
Реально в силуэте, конечно, такая переменная не используется; петля силуэта строится без развилок, а их роль выполняет особая структура безусловных переходов, которая охватывает и шапку, и подвал. Здесь мы не будем касаться принципа её построения; читатель может попробовать сделать это сам.
При раскрытии «шапочного разбора» мы показали структуру с участием только обязательных вершин; дополнительные входы (относящееся к ним дано в пунктирных линиях), во-первых, необязательны, а во-вторых, имеют смысл, связанный с заголовком и концом силуэта, т.е. сущностями вне петли; поэтому допвходы следует рассматривать в рамках всего силуэта.
Также развилки здесь организованы цепочкой по горизонтали; для этого входы виопов Вопрос расположены слева, т.е. «не по шампуру». Это сделано для визуального соответствия древесным точкам; кроме того, такая структура лучше компонуется.
Видно, что обычная вершина-соединитель раскрывается как кратный БП (здесь назван Цикл). Также раскрываются соединители в дереве «подвального сбора»; здесь мы не будем показывать получаемую структуру; можно видеть её далее при разборе переключателя в п/п 2.1.3.11.
Можно показать и заготовку-силуэт без упрощений. При этом заголовок и конец являются своего рода вершинами с одним выходом (входом). В реальности их можно трактовать как связи с неким надалгоритмом, охватывающим данный.
Заметим также, что РБНФ-графит-определение в принципе допускает отсутствие всех веток, кроме первой. Этот случай, строго говоря, к силуэтам не относится — такая структура представляет т.н. зацикленный примитив, имеющий своё значение в алгоритмике (см. п/п 2.3.1.1) - а по шампур-методу должна образовываться удалением конечной вершины примитива. В то же время можно говорить об «одноветочном силуэте», получаемом при удалении правой из двух веток силуэта (в классической версии шампур-метода, изложенной в /1, Гл.15/, такая возможность не оговорена). Тем самым получаем разные возможности вывода одного типа структур.
Виоп Петля цикла имеет в основе вершину-соединитель, к которой присоединены три ребра, как показано на схеме слева.
Структура петли цикла как бинарного графа
Мы можем предложить и иное представление этой вершины. Преобразуем её подобно петле силуэта: покажем не только древесную точку, но и переходы (безусловные). Получится схема справа. Видно, что посредством БП совершается как вход в цикл (сверху по шампуру), так и очередная итерация (против шампура); дублирующую ветвь имени можно убрать (что показано пунктиром), т.к. на самом деле это имя (метка начала вертикали) одно.
Оба перехода совершаются по одному адресу (но с разных маршрутов, из которых каждый раз исполняется один); тем самым образуется «пул» переходов, который назовём многократным (или просто кратным) БП. Так реально (на уровне командного моделирования) воплощается смысл вершины-соединителя.
Здесь в отличие от петли силуэта кратный БП Цикл показан сокращённым (оставлена одна метка для всех БП на общий адрес, причём форма её вершины изменена).
Вершина Начало цикла ДЛЯ замещает собой цепочку из оператора начальной установки параметра цикла и вершины-присоединителя петли цикла. Вершина Конец цикла ДЛЯ замещает собой цепочку из оператора наращения параметра цикла и оператора проверки условия цикла; последний одновременно служит вершиной-разветвителем на петлю цикла.
Как и в любой развилке, в тексте условия цикла мы можем записать арифметическое выражение наращения параметра, тем самым сделав отдельный оператор для этого ненужным.
В данном случае сама петля не показывается, но подразумевается, что она присоединяется к границам и охватывает тело цикла – шампур-блок, находящийся между ними.
Графика виопа Адрес ветки является отражением по вертикали контура имени ветки:
Графика вершин-петель оригинальная и следует визуальным упрощениям дракон-схем, снятие которых мы показали выше. Исходный соединитель петли в обоих случаях показывается стрелкой.
Графика виопа Конец и вершин-границ цикла ДЛЯ взята из ГОСТ с сохранением значения.
Как видно, текст границ структурирован по графит-методу (с применением РБНФ). Формат примерно соответствует немаршрутной части границ цикла в русской алгонотации.
В начало страницы | Оглавление | Версия для печати
Copyright © Жаринов В.Н.
