Содержание
Рассмотрим визуализацию разветвляющихся подструктур деятельности на техноязыке.
В основе определение ветвления в техноязыке совпадает с традиционным: это шампур-блок, содержащий одну или более развилок на основе икон ветвления, причем выполнение (или невыполнение) условия развилки ведет к передаче управления на тот или иной участок маршрута за ней. Условие зависит от обстановки выполнения алгоритма, т.е. включает к-л. из его величин. Структура связей внутри ветвления нелинейна (несводима к цепочке операторов).
Для нелинейных алгоритмов определение маршрутов будет более общим:
Маршрут визуала – путь от начала до конца, проходящий через иконы и соединительные линии, причем при каждом ветвлении выбирается один из выходов (вариантов).
Формула маршрута – последовательность литер, обозначающих иконы, и результатов проверки условий ветвления (ответов на вопросы развилок, вариантов переключателя).
Понятно, что нелинейный визуал будет иметь набор маршрутов, полученных перебором всех возможных сочетаний ответов для имеющихся икон ветвления. В совокупности все они отражают структуру управления алгоритма и по-разному относятся к его цели.
Главный маршрут – ведущий к цели нелинейного визуала (тому, что надо по условию задачи, решаемой данным алгоритмом) наверняка либо с наибольшей вероятностью.
Главный маршрут можно указать только для смысловой записи визуала.
Главное эргономическое требование к нелинейным визуалам: главный маршрут должен проходить по шампуру; тогда дракон-схему легче читать.
Основные нелинейные структуры при визуальном анализе мы будем сопровождать компактными схемами связей, своего рода «маршрутными картами» из фигурных стрелок. По-прежнему на схемах не показываем, а подразумеваем валентные точки (нейтральные) в середине каждого звена вертикали.
Этот тип структуры в техноязыке имеет эргономические особенности записи. Начнём с простого ветвления (см. диосцену далее). Формально его структура распадается на развилку, шампур-блоки альтернатив и точку слияния, связанные естественными переходами друг с другом. Введём определения (см. /1, Гл.15, Тезис 26, 27/):
Лиана – часть дракон-схемы, имеющая один вход – начало и один выход – конец. Началом лианы м.б. любой выход иконы Вопрос (выход любой иконы Вариант), если выход не соединён с петлёй цикла. Концом лианы м.б. точка слияния с другой линией, если эта точка не есть неразветвлённый вход иконы.
Нагруженная лиана – последовательность икон/макроикон, звеньев вертикали и ломаных линий (связей между иконами, включающих наряду с вертикальными также горизонтальные участки и изломы, не являющиеся вершинами дракон-схемы).
Ненагруженная лиана – не содержащая икон; есть звено вертикали или ломаная.
Отметим, что главная вертикаль также попадает под определение лианы.
Очевидно, что ломаные линии возникают только у лиан, содержащих побочные вертикали. Число изломов линии д.б. минимально; оправданным считается один излом.
Простое ветвление – формальная структура на техноязыке и «очная ставка»
Сложное ветвление по-человечески естественно изображать как мультиграф, используя условную вершину со многими выходами (мультиикону, см. схему-прототип); в техноязыке можно остаться в рамках бинарных ГСА и визуализировать эту вершину как цепочку развилок (см. внизу справа), однако получим неэргономичную и к тому же сравнительно громоздкую, плохо компонуемую конструкцию. Чтобы устранить эти недостатки, был разработан переключатель (общий вид см. внизу слева). На «очной ставке» (см. далее) видно, что запись цепочки развилок на языке блок-схем ещё усиливает отмеченные недостатки.
Из схемы множественного ветвления на базе мультииконы «Вопрос» легко выводится сложная развилка в минимальном базисе ГСА – мультиикона преобразуется в дерево индивидуальных условий на каждое направление. Из неё выводится переключатель – дерево условий замещается системой рёбер и вершин, образующих «шапку» переключателя, а на схеме в явном виде от системы выражений выбора остаются только объявление переменной выбора и её требуемых значений.
Множественное ветвление – происхождение и формальная структура в техноязыке
«Шапка» переключателя, как мы помним, логически остаётся единой (что показано взятием в контур-вопрос).
Множественное ветвление – «очная ставка» на техноязыке и языке блок-схем
Во всех случаях мы выделяем штрихпунктиром обобщённые блоки - составные части, на которые структурируем конструкции.
На отдельных схемах мы пользуемся ранее описанным приёмом – представлением обобщённого шампур-блока через шампур-икону Комментарий – для приведения драконоподобных схем к стандарту техноязыка.
Раскрытие структуры сложного ветвления в техноязыке
Видно, что конструкцию ветвления в целом можно свести к шампур-блоку независимо от её внутренней структуры.
В техноязыке нелинейные конструкции определяются как шампур-блоки через словарь макроикон, из которого нужно брать их начальные формы.
Если при визуализации реального алгоритма правило главного маршрута не соблюдено сразу, выполняют рокировку – перемену местами содержимого вертикалей схемы; при этом в развилке надо менять и формулировку вопроса на обратную, а в переключателе – варианты.
Рокировка не предусмотрена стандартом техноязыка; это технологическая операция, относящаяся к равносильным преобразованиям.
Рокировку можно определить и как замену содержания блоков ветвления в обобщённой записи (см. формальную структуру данной конструкции).
Ещё одна проблема смысла сложного ветвления - значение «любое другое». Прежде всего возникает вопрос — любое «вообще»? Конечно, нет — только в пределах области допустимых значений величины ИмяПерВыб; в информатике любая такая область конечна, поэтому конечна будет и область «любых других» значений. Рассматривая области изменения переменной выбора и вариантов как множества, можем говорить о «любом другом» как о разности множества ИмяПерВыб и множеств всех вариантов.
Следующий вопрос — как определяется «любое другое» в дракон-переключателе? На рисунках мы видим разницу между ним и записью сложного ветвления через развилки. Во втором случае вариант «любое другое» логически вытекает из совокупности отрицательных ответов на вопросы всех развилок и задан неотъемлемо, не требуя явной формулировки. В переключателе же имеем только то, что явно определили в иконах Вариант как константы или выражения выбора. Из последней схемы, где сняты эргономические упрощения, можно понять, почему так происходит: шапка переключателя есть также дерево, но его промежуточные вершины — не условные операторы, а древесные точки-соединители, которые не участвуют в выборе маршрута; эта роль отведена вершинам-листьям дерева - иконам Вариант.
Если позволить себе электрическую аналогию, то каждая икона Вопрос подобна тумблеру, соединяющему вход либо с главным выходом (по ответу «да» на тематический подвопрос развилки, т.е. совпадению текущего значения ИмяПерВыб со значением варианта), либо с побочным выходом (по ответу «нет»); икона Вариант же м.б. уподоблена кнопке, замыкаемой по совпадению значений. Тогда, если подать на схемы сложного ветвления ток, то он потечёт по тому маршруту, который предопределён значением ИмяПерВыб при заданных значениях вариантов.
Будучи поверхностной, эта аналогия для переключателя оказывается верной лишь частично: если «замкнуть» не один размыкатель-вариант, то и ток потечёт по всем замкнутым ветвям, тогда как вариант для исполнения д.б. выбран единственный. При пересечении значений разных вариантов это достигается тем, что варианты просматриваются для выбора в определённом порядке — слева направо (как читается текст в европейских естественных языках).
Как влияет эта особенность переключателя на алгоритмизацию? В принципе никак — просто если требуется выбор по «любому другому» значению ИмяПерВыб, то нужно вводить в переключатель отдельный вариант.
В реальных задачах зачастую «любое другое» значение вообще не должно присутствовать как возможность ветвления, т.к. вся область значений ИмяПерВыб должна исчерпываться явно заданными значениями вариантов (т.е. как результат пересечения их множеств со множеством значений ИмяПерВыб должно получаться пустое множество).
Далее для целей программирования из визуала получается импер-текст на некотором прогязыке.
Важно понимать, что в прогязыке сложное ветвление (case-оператор) реализуется именно через цепочку развилок (так требуется для информашины-исполнителя); поэтому вариант «любое другое» будет присутствовать всегда как последний по тексту ветвления (в некоторых прогязыках, скажем, в Perl, он явно выделяется в case-операторе как вариант «по умолчанию»). Поэтому если по логике задачи он не является «любым другим», то сочинитель должен сам обеспечить, чтобы область значений для этого варианта формировалась правильно — множества значений ИмяПерВыб и остальных вариантов д.б. такими, чтобы «остаток» от вычитания их из множества значений ИмяПерВыб давал нужное множество.
Итак, физическая реализация математической модели может накладывать определённые ограничения. Заметим, что наша электрическая аналогия показала именно это для уровня машинного исполнения сложного ветвления.
Возможна и по крайней мере одно ограничение уже при сочинении разветвлённой структуры (не обязательно сложной); это всё та же проблема компоновки реальных шампуров.
Физический размер вертикали определяется суммарной протяжённостью звеньев (их числом при заданной минимальной длине звена) и суммарной высотой икон (числом строк их текста при заданных параметрах вёрстки). Возможно, что некая побочная вертикаль физически длиннее охватываемого точками её присоединения участка главной вертикали (и вообще более правая вертикаль – длиннее более левой), если первая более насыщена иконами и/или её иконы – текстом. Тогда возникает задача согласования длин вертикалей на дракон-схеме.
По правилам топологии наклонные линии и изломы вертикалей «против шампура» (т.е. участки обратного следования) запрещены. Поэтому правильным решением будет «выключка», т.е. пропорциональное изменение звеньев вертикалей данного шампур-блока.
Поскольку мы определили, что нагрузкой любой вертикали ветвления м.б. любой шампур-блок, то как один из случаев это м.б. другое ветвление; так получается частный случай т.н. матрёшек – иерархически вложенных нелинейных конструкций.
Какие задачи приводят к матрёшкам? Очевидный случай – при сложном ветвлении у нас получилось более 16 вариантов выбора – такой переключатель запрещён в техноязыке в силу громоздкости. Для удобства восприятия он требует декомпозиции – представления в виде вложенных (входящих в вертикали друг друга) ветвлений.
Часто само множество вариантов выбора логически поддаётся классификации; иначе его можно разбить на подмножества принудительно и ввести переменную-критерий выбора между подмножествами. В результате визуализации такой системы условий у нас получатся переключатели, вложенные в другие переключатели. Аналогичная ситуация – условие ветвления у нас громоздкое, но его можно разбить на этапы проверки (подвопросы); эти этапы можно «разнести» по вложенным развилкам (и/или переключателям – это зависит от от того, до двух или более двух вариантов окажется в каждой группе классификации и можно ли поставить подвопрос как да-нетный). Однако это внешние (формальные) основания, связанные с формой представления визуала (здесь – с эргономизацией этой формы).
Может статься, что нам нужно за проверкой одного условия выполнить некие действия, а только потом проверять следующее; аналогично может понадобиться выполнить какие-то действия после прохождения ветвления перед следующим. Это уже внутренние (содержательные) основания для произвольного ветвления, вытекающие из логики решения задачи.
Перед и после ветвления м.б. и другие ветвления (развилки, переключатели), образуя цепочку. Вертикаль, частью которой является главная вертикаль некоего ветвления, определим как базовую вертикаль данного ветвления, а ветвление, которое уже не охватывается другим ветвлением (т.е. сверху его вершиной-разветвителем, а снизу его же точкой слияния), считаем внешним в данной матрёшке. Базовой вертикалью в конце концов всегда является шампур визуала, поэтому любая матрёшка, выделенная не относительно шампура, является лишь частью к.-л. матрёшки, базированной на шампуре; конечно, матрёшки, как и просто ветвления, в любой вертикали могут следовать подряд цепочкой.
Любая вертикаль ветвления (необязательно в матрёшке) м.б. пустой либо нагруженной шампур-иконами, визуализирующими операции решения данной задачи; назовём такую нагрузку линейной. Вертикаль матрёшки, содержащая ветвление с ненагруженной главной вертикалью, сама уже нагружена, но эта нагрузка чисто нелинейная, не совершающая действий для решения задачи. Наконец, в матрёшке возможна смешанная нагрузка вертикали (когда в неё входят и ветвления, и шампур-иконы).
В любом случае мы продумываем структуру ветвления как иерархию макроикон и только потом строим её, начиная «сверху», т.е. с внешней макроиконы; далее в её вертикали вставляем макроиконы следующего уровня иерархии и т.д. Затем в переключатели можно добавить варианты до нужного числа и вставлять шампур-иконы в вертикали, требующие линейной нагрузки. Напомним, что ненагруженной можно оставлять лишь одну вертикаль ветвления.
Теперь посмотрим, что приводит нас к необходимости пересадки лиан. Опять-таки простейший случай – в нагруженной развилке нам нужно перенести точку слияния выше (тогда часть содержимого главной вертикали становится «общим достоянием», выполняясь при любом результате ветвления как часть вертикали, базовой для данной развилки) либо ниже (тогда наоборот, часть содержимого базовой вертикали переходит внутрь развилки и не выполняется при выборе её побочной вертикали).
Более сложный случай – если нужно проделать то же в переключателе; тогда точка слияния переносится на вертикаль другого варианта (только соседнего справа или слева, т.к. иначе нарушится запрет на пересечения). Можно перенести точку и на вертикаль развилки (соседнюю).
Для конструкций такого рода мы не можем придумать статического описания (законченного визуала), исчерпывающего все случаи – на то они и произвольные. Можно лишь показать структуры, по возможности иллюстрирующие введённые понятия.
Подумаем теперь над смыслом двоичных деревьев. Для этого вспомним, что говорилось о безусловном переходе в текстовых алгоязыках. Очевидно, что каждую древесную точку сбора мы можем заменить БП-обходом с конца данной побочной вертикали переключателя на главную — в точку, предшествующую следующей за переключателем иконе. Также каждую древесную точку разбора вместе с её вариантом можно заменить на развилку, побочный выход которой оканчивается иконой БП на следующую вертикаль. Такое преобразование назовём прямым. Полученная схема показана рисунке (см. далее).
Можно преобразовать переключатель в квазилинейную структуру и иначе. Для этого сначала введём безусловные переходы, оторвав все вертикали от сложной развилки (дерева «шапочного разбора»). А затем заместим это дерево его представлением через цепочку развилок, преобразованную операцией «инверсия ответов» - разновидностью рокировки, перемещающей и нижележащие иконы Развилка — как бы «вывернем шапку» (подобную операцию, но не затрагивающую положения самих условных вершин, Паронджанов называет «да-нет»).
Получится, что все развилки лежат цепочкой на главной вертикали (проходятся по ответу «нет», ставшему главным), а побочный выход каждой из них (по ответу «да») ведёт к БП на «свой» вариант; после цепочки лежит шампур-блок варианта «любое другое». Такое преобразование назовём инверсным. Конструкция показана на рисунке (нижняя область).
Очевидно, то же самое можно проделать для простого ветвления; вся разница в числе вынесенных фрагментов (он будет единственным).
Что у нас получилось? Некий вариант произвольного следования; с его помощью мы создали возможность выкладки алгоструктуры ветвления в линию. Точно также, как и для произвольного следования, побочные варианты можно рассматривать как аналоги визуалов-вставок; также и варианты выкладки образуют множество перестановок на полученном наборе фрагментов. Это не что иное, как лиоформа разветвлённой дракон-схемы (шампур-блока).
Если имеются вставки в вертикали, они точно также раскладываются на фрагменты, и в результирующей лиоформе сочетаются БП обычные и с возвратом.
Прямое преобразование сложного ветвления в произвольное следование
Очевидно, эту операцию мы можем применить и к переключателю, т.к. ранее мы показали, что его можно свести к цепочке вложенных развилок.
Инверсное преобразование сложного ветвления в произвольное следование
С другой стороны, получилась визуализация «устройства» конструкции сложного ветвления (case-оператора) на программном уровне формализации (в форме машинного кода). При этом мы показываем то, что в текстовых операторах ветвления обычно «спрятано» - присутствие безусловного перехода для целей обхода вариантов, не выбираемых при ветвлении.
В некоторых прогязыках (диалектах) БП-обход в конце варианта не реализуется (напр. для классического Си); тогда возможности маршрутизации сужаются (можно только пропустить один или более вариантов, которые предшествуют по тексту выбранному; если за ним по тексту есть последующие, то они будут выполнены).
Теперь проясняется причина выбора именно такой графики икон обычного БП; тем самым подчёркивается необходимость его для выкладки ветвлений. При этом понятнее истинный смысл иконы Вариант в дракон-переключателе: это метка начала очередной вертикали, переход на которую содержится в команде ветвления, расположенной в предыдущей древесной точке разветвления (в ДРАКОНе подразумевается в «шапке»); аналогично точка конца лианы в «подвале» содержит команду БП на точку конца главной вертикали (лежащую на шампуре).
Все шампур-блоки перед выкладкой нужно свести к простым; при этом в общем случае имеем конструкцию произвольного ветвления.
В начало страницы | Оглавление | Главная | Версия для печати
Copyright © Жаринов В.Н.
