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

Дружелюбный Русский Алгоритмический язык, Который Обеспечивает Наглядность/Надёжность

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

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


vershiny_i_linii_sxem_-_smysl_v_grafike_i_tekste

Это старая версия документа.


Вершины и линии схем: смысл — в ГРАФике И Тексте

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

Как следствие, по сравнению с блок-схемами некоторые формы блоков получают новые значения (к примеру, форма-трапеция – как основа хронизаторов реального времени), а другие (скажем, ромб) не используются.

В то же время композиция многофигурных вершин м.б. более стройной, если ввести общие законы их построения. Возможны следующие:

  • вертикалей окружения — вводятся условные оси, параллельные шампуру схемы и представляющие совокупные потоки управления процессов, взаимодействующих с алгоритмическим процессом, описываемым схемой;
  • событийного следования — фигуры в вершине и/или части её содержания упорядочиваются по шампуру в порядке исполнения.

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

В части второго предшествующие события представляются фигурами, расположенными ближе к началу шампура; кроме того, можно использовать уровни глубины, если допускать частичное перекрытие фигур в вершине.

Можно видеть, что в ШМ принято единственное правило — располагать фигуры вершины «лесенкой» всегда справа налево и направленные формы фигур направо - более простое, но не использующее информативность графики полностью.

Имеется в виду, что для графики вершин схем можно выделить информативные признаки её расположения:

  • направленность фигур — при наличии шампура существенна в направлении, перпендикулярном ему;
  • порядок следования нескольких фигур вершины (в направлении шампура);
  • относительная глубина фигур (проявляется, если фигуры могут перекрываться).

Также алфавит БС функционально шире, чем в ДРАКОНе. Блок-схемы предназначены для представления содержания всей программы (в смысле расширенного тезиса Вирта). Поэтому, кроме подалфавита импер-части (называемой в БС «схема алгоритма»), предусмотрен также подалфавит для деклар-части («схемы данных»). Имеются также средства для представления материальных действий («техпроцессов» по Паронджанову) и структур (актив-части). Однако назначение ДРАКОНа — представлять только императивные знания; поэтому остальной алфавит здесь не нужен.

Важно понимать, что графика шампур-схемы представляет лишь часть формализуемого знания о предмете шампур-визуализации. Остальная часть представляется содержанием вершин (и, возможно, рёбер). Т.е. за схемой всегда стоит некий целостный язык представления (ЯПЗ), изначально полностью текстовый. Именно на него мы и указываем префиксом. Не принимать во внимание этот язык можно, лишь рассматривая абстрагированные шампур-схемы (литеральные и «слепыши»). Конкретный же графит-язык «гибриден», т.е. образуется «скрещиванием» ЯПЗ с шампур-языком (схем-«слепышей»). При этом часть синтаксиса текстового ЯПЗ представляется графикой вершин и рёбер, а часть — их содержанием (как ещё говорят, разметкой графа). Образуется т.н. гибридный язык — который д.б. эквивалентен чисто текстовому.

Если же мы не указываем ЯПЗ, но считаем, что схема конкретная (гибридная) — это лишь значит, что мы принимаем для содержания её рёбер и/или вершин синтаксис некоего гибридного ЯПЗ, выбираемого «по умолчанию». Разумно считать таким естественный язык описания деятельности, родной для сочинителя (и, конечно, читателя) схемы. Однако этот язык для удобства дальнейшей формализации обычно как-то структурируется (ограничивается). Как — покажем при определении лексики языка.

Далее рассмотрим дракон-алфавит с позиций структурного анализа и синтеза.

Начало азбуки ДРАКОНа-1: вроде, как в БС... да не как в БС

С учётом определения «от блок-схем» начать, конечно, стоит с вершин, представляющих эквиваленты БС-алфавита. Их определения даны на рисунке ниже.

Видно, что дракон-алфавит богаче БС уже в этой части. Причиной тому в первую очередь разнообразие способов представления ветвлений (т.н. предикатных вершин в терминах блок-схем).

Для уточнения (расширения) смысла вершины, включённой в шампур, в шампур-методе используют добавочные вершины-боковики, присоединяемые справа и/или слева к вершине, находящейся на шампуре (в цепочке следования). Возможность присоединения мы показываем отрезком линии сбоку. Так же показываются точки включения в вертикаль (вход и/или выход[ы] вершины).

Возвращаясь от формы к сути, заметим для начала, что алфавитные знаки индексируются не так, как в исходном техноязыке. Это связано и с их смысловой группировкой, и с тем, что ДРАКОН — лишь один из нужных для визуализации языков. Это следует из упомянутых классификаций — уже в ГРАФИТ-ФЛОКС, как было сказано, имеется два языка. Поэтому же в текст вершины Заголовок включён префикс языка — каждая схема составляется на одном языке, но языков, у потребляемых для описания одного и того же предмета, м.б. более одного… Почему - сказано ранее в «Отступлении о языках...».

Далее, в техноязыке принято включать в заголовок имя схемы. По сути, это имя алгоритмического процесса. Имеющего некий внешний контекст, в котором он вызывается, для чего создаётся собственный контекст процесса. Для указания контекста в техноязыке обычно используют боковики.

Процесс может и не иметь конца — тогда говорят, что он «зацикленный». В техноязыке в этм случае используют специальную форму дракон-схемы, которую рассмотрим в другом разделе.

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

  • вызывающий — когда данный процесс был вставкой (во вставку во вставку и т.д… - если уровней вызова много) в другой процесс;
  • «родительский» - когда данный процесс порождён как часть системы т.н. совместно протекающих взаимодействующих процессов (как ещё говорят, асинхронных или параллельных — понятие см. в Ч.I, Гл. 6 «Концепций и принципов...» В.Ш. Кауфмана).

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

В диспозитивной модели суть асинхронности (параллелизма) — в допущении более чем одной «рабочей точки» для системы процессов. Каждая точка развёртывает свою схему, и при необходимости процессы взаимодействуют. Первичный процесс в этом случае понимается как базовый; он может контролировать ход порождённых им процессов и при необходимости «снимать» их — досрочно прекращать исполнение.

Понятно, что в обоих моделях в каждом процессе, если он нелинейный, проходится один маршрут. Также понятно, что в ранговой модели ни один процесс, кроме первичного, не м.б. «зацикленным». Взаимодействие же в диспозитивной модели м.б. как прямым - через управление ходом процесса, так и опосредованным - через передачи чего-либо или использование в условиях одного процесса величин, на значения которых могут влиять другие процессы.

В определении действия мы видим повторяющуюся структуру. Хотя бы одно действие всегда записано в вершине; но можно записать два и больше. Это удобно для смысловой группировки цепочки действий в одной или более вершинах. При этом считаем, что действия выполняются в том порядке, как они написаны в вершине.

Что такое маршруты процесса? Это возможные цепочки действий от начала до конца процесса. На дракон-схеме маршрут получается, если пройти путь от начала её к концу. Если такой путь м.б. только один, то процесс (и маршрутная структура) линейный. Однако в жизни чаще одного результата можно ( или нужно) достигать разными путями — вспомним о существовании условий решения задачи. Они м.б. начальными (грубо говоря, когда стоит начинать процесс и что при этом нужно «принять по умолчанию») и граничными — что нужно соблюдать в процессе решения (возможно, когда прекратить процесс, не дойдя до результата).

В нелинейных процессах и структура маршрута нелинейна. Чтобы её выразить, используется прежде всего условный (т.н. предикатный, как говорят математики) тип вершин. В условной вершине выбирается один из возможных маршрутов. В техноязыке для этого служит виоп Развилка.

Уточним, что в РБНФ-итераторах (как помним из определения РБНФ-метаязыка, так называется операция, обозначаемая фигурными скобками) N служит обозначением натурального (иногда — целого, т.е. включающего и ноль) числа — предела повторений вхождения. Число это каждый раз м.б. разным — на что указывает конкретизирующий индекс при N.

В нелинейной схеме «самый-самый» по какому-то критерию (или ряду критериев) маршрут удобно принять за главный. В шампур-методе принято, что он всегда идёт по прямой — т.е. через главные выходы всех развилок. Как упорядочиваются остальные маршруты — поговорим дальше (в этой статье).

С использованием двух следующих вершин строится дракон-переключатель — иная форма визуализации условия ветвления.

Какие конструкции можно строить из этих «кубиков»? Чтобы это понять, далее рассмотрим следующую группу знаков и конструкций шампур-схем.

Детальное определение (раскрытие текста действия) фактически вводит три уровня формальности языка. Мы уже их обсудили выше.

В определении развилки мы снова видим разные уровни формальности. Правда, здесь выделены только два, дабы не перегружать читателя подробностями. Однако математический уровень существует — обычно представляется в виде функций исчисления высказываний (т.н. предикатов — откуда и название условных вершин в БС-языке). В практике алгоритмизации пока ещё принято «пропускать» этап выделения условных функций. Но для надёжной (гарантоспособной) формализации он необходим — их формулирование даёт возможность понимать логику формирования маршрутов и проверять её.

Понятно, что уровни формальности содержания вершин д.б. согласованы в пределах схемы (по крайней мере, законченной). Вряд ли есть смысл для исполнителя информатически строгого (реальной машины или её абстракции типа «машины Тьюринга») в действиях и вопросах, представленных как функции и/или неформальные предложения… ;-)

То же касается и согласования репертуара, багажа и реквизита схемы и предполагаемого исполнителя при должном уровне формальности языка.

Азбука ДРАКОНа-1 — сложные схемы и их описание

Сначала — замечания по синтаксису. Прежде всего видно, что мы ввели визуальный эквивалент РБНФ. Здесь он описывает повторы отдельных частей схем (знаков Д17 и Д18). Как — сказано выше в «Отступлении о синтаксисе…».

Снова вернёмся от представления к содержанию. С комментариями всё понятно. Или они указывают, «куда подшили» (скобочные), или «куда вставили» (вершинный). Вообще комментарий в формальном смысле - это часть текста, которую можно удалить без изменения значения (для исполнителя). Проще говоря — это часть описания, нужная для сочинителя, а не для исполнителя (второму она м.б. и непонятна). Но вершинный комментарий на практике иногда используют для размещения части описания, не выразимой на языке шампур-схемы. Это эргономически не лучшее решение — и м.б. только как временное в процессе построения полноценной системы языков (как описано в завершающем разделе статьи).

Далее у нас определены конструкции для нелинейных связей в схемах техноязыка. Причём подробно — вместе с вершинами. Поскольку в них выражена своя часть смысла — и нам интересная именно в связи с построением и чтением схем. После изучения языка этот смысл понятен — поэтому на практических схемах вершины можно не показывать (как и делается в книгах по техноязыку). Вот чего там не делалось (по крайней мере, до 2011 года :)) - это объяснения их смысла…

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

А вот гребёнок в исходном определении техноязыка читатель не найдёт. На их месте определяется как знак петля силуэта. Это - следствие структурного анализа шампур-схем — т.е. целесообразного выделения их частей. В самом деле, конструкции ветвления (и соответствующие атомы техноязыка), как можно видеть, содержат такие гребёнки. И при их отсутствии в словаре получается, что ветвление частично строится непонятно из чего… :-) Тогда как петля силуэта м.б. построена как раз из гребёнок и петли цикла — только в зеркальном отражении (для того оно и введено в алфавит). Как всё это делается — рассказано после раздела об атомах.

Азбука ДРАКОНа-1 — кое-что для реальных исполнителей алгоритмов

Ну и третья порция определений — остальные вершины исходного алфавита.

Здесь достаточно пёстрое собрание. Общее в них то, что синтаксис содержания строго задан — от уровня формальности зависит разве что состав текста (добавляются кое-где детали). В силу же различий можно выделить следующие группы.

Ввод и вывод представляют случаи обмена со внешней средой процесса (окружением исполнителя). В сущности, это разновидности действия - как и Полка действия.

Полка данных представляет псевдооператор. Он никаких действий при исполнении вызывать не должен - но согласно его содержанию определяются места для величин и, возможно, записываются их начальные значения.

Вершины-боковики представлены виопом Формальные параметры — он добавляет к заголовку схемы параметры вызова процесса как процедуры (вставки). Сама Вставка имеет вид действия. Только это действие расписано как отдельный визуал-вставка. А эта вершина показывает, откуда в данном визуале нужно совершить, как говорит Паронджанов, «акробатический прыжок» - перейти к исполнению вставки. При этом как раз параметры, перечисленные как формальные, получают реальные значения, используемые при работе вставки. И становятся фактическими.

Ещё один момент — кроме вызова, происходит и возврат. А он возможен (на то же место), если визуал-вставка имеет нормальное завершение (основной выход). Бывают и процессы «зацикленные» - сочиняемые без него (исключения не в счёт — они не обязаны вернуть управление именно по месту вызова). Если вызвать такой процесс — то продолжить работу вызывающего по логике вставки будет невозможно — ведь условием этого является возврат управления («рабочей точки») из вызванного. Здесь мы сталкиваемся с необходимостью различных «рабочих точек» для логически связанных процессов.

В таком случае используют механизмы, специально предназначенные для неиерархических систем процессов. В техноязыке они представлены в дополнении для т.н. реального времени (ДРАКОН-2).

ДРАКОН-2: реальное время и его азбука

Время при моделировании в информатике протекает дискретно, по шагам алгопроцесса; на каждом шаге исполнитель совершает целостное действие, изменяющее объекты процесса и обстановку в целом. Его категории можно выделить так. Положим, что имеется конечный набор «обстоятельств времени» алгопроцесса, а при алгоритмизации конкретной задачи учитывается большая или меньшая их часть. Тогда можно построить следующую иерархию информатического времени:

  • абстрактное – временные соотношения в описании алгопроцесса игнорируются (предполагая, что процесс и каждый его шаг в любом случае начнётся и закончится тогда, когда нам это нужно, исходя из цели и условий обстановки);
  • условное – принимается во внимание, что шаги процесса имеют конечную длительность, а среда взаимодействия исполнителя процесса – определённую динамику; поэтому нужно контролировать время выполнения процесса и привязывать начало операторов взаимодействия (ввода-вывода) к определённым моментам;
  • реальное – также учитывается, что процесс может исполняться не сам по себе, а во взаимодействии с другими процессами, а исполнитель может одновременно выполнять не один, а несколько процессов, ведущих к различным целям (в общем случае ряд систем процессов распределяются между рядом координированных исполнителей); поэтому нужно обеспечивать межпроцессное взаимодействие и распределение работ между исполнителями.

В условном времени мы можем построить модель исполнения алгоритма — т.н. циклограмму. На ней все действия упорядочены по оси времени. Из циклограммы ясно, когда чем исполнитель загружен по данному алгопроцессу. А в окружении все действия исполнителя считаются вызывающими тоже известные по содержанию и времени процессы.

В реальном времени действует совершенно иной принцип — сочинитель не должен определять порядок действий во времени. Течение процесса определяется только отслеживаемыми исполнителем данными — т.е. величинами данного процесса и, возможно, какими-то дополнительными данными состояния исполнителя и его окружения. Что происходит в окружении (и в самом исполнителе кроме работы с величинами данного алгоритма) — определяется только по значениям величин состояния. Главный теоретический принцип здесь — шаги сочиняемого алгопроцесса и любых других могут перемежаться в любом порядке. И если мы уж хотим анализировать исполнение в реальном времени — то надо все эти порядки и рассматривать. И определять, какие из них ведут к нужным результатам, а какие нет. А дальше думать, можно ли исключить каждый такой порядок и как? И если нельзя, то как его обнаружить при исполнении и какие реакции заложить, чтобы результаты были всё-таки наиболее благоприятными (или хотя бы наименее неблагоприятными)?..

Как правило, «школьные» информатические задачи составляются для абстрактного времени. Но и в жизни, если это возможно, нужно стремиться к тому, чтобы «привязать» шаги алгопроцессов к конкретным моментам времени.

Пример. Хорошая иллюстрация деятельности в реальном времени – сцена из известного фильма Чаплина «Великий диктатор», где герой-парикмахер бреет клиента под музыку Брамса, привязывая определённые фазы бритья к музыкальным фразам. :-)

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

Предложенный создателем техноязыка состав лексики представлен на рисунке.

Первые четыре оператора представляют средства описания алгопроцессов, исполняемых в условном времени. Здесь заметим лишь, что в нелинейном алгоритме пуск таймера может нахдиться на маршруте, который реально не будет исполнен. Тогда первый же пускаемый по этому таймеру оператор, встретившийся дальше по ходу исполнения, будет блокирован. Так что процесс, управляющий таймером, должен как-то разрешать эту ситуацию (ясно, что это опять будет исключение). Отметим, что у этого алгопроцесса своя «рабочая точка» - т.е. он образует с алгопроцессами, синхронизируемыми по таймерам, систему (диспозитивную).

Следующий оператор уже является средством описания реального времени. Конкретно для данного случая вместо вставки используется создание экземпляра процесса, представленного другим визуалом. Это представляется как посылка оператором Д25 на имя визуала сообщения «Пуск» (возможно, с дополнительным идентификатором экземпляра — скажем, номером по порядку создания). Созданный визуал становится «партнёром», сотрудником и родительского, и всех визуалов, порождённых таким же образом.

Конечно, визуал-сотрудник не обязан быть «зацикленным». Тогда обычный (конечный) экземпляр при нормальном исполнении отработает до конца, после чего «снимется» (перестанет использовать ресурсы исполнителя), и взаимодействие с ним других процессов (ещё работающих) станет невозможным. Если же такое произойдёт (т.е. какой-то процесс отправит что-то на имя «снятого» процесса) — это также должно считаться исключением.

Заметим, что эти языковые средства разрабатывались автором техноязыка для конкретных задач и исполнителей (бортовых комплексов управления ракетами). С т. зр. теории алгоритмических процессов (и их систем) они не полны. Но для многих задач (допускающих математическое представление и информатизацию с теми же условиями) их вполне достаточно. Развитие же языка — дело будущего (и объективно уже идущий процесс). Рассмотрим некоторые его направления.

Дракон-лексика: уточним состав и смысл

Вставка как активная подстановка схем

Процесс, описываемый вставкой, м.б. алгоритмом-функцией — возвращать какое-то значение по завершении. Можно назвать его фактическим параметром возврата.

Также в программировании у вставки м.б. т.н. приёмник — параметр-сообщение одного из заранее заданных типов. Тогда в дракон-модели определяют визуал-вставку для работы с каждым типом приёмника — а при исполнении вызывается вставка, определённая для нужного типа. Фигурально говоря, на десерт у нас м.б. яблоки, апельсины и арбузы. Каждый из них можно съесть — но сам процесс будет в чём-то различаться. Вот программисты и придумали способ описания подобных различий с учётом свойств исполнителя-машины… :-)

Между прочим, всё это в техноязыке требует текстового описания — поэтому у вставки столько текстоэлементов. И это не все возможные — исполнение системы со вставками более сложно, чем одного процесса, содержащего тела всех вставок по местам подстановки. Визуал-вставка может менять и другие переменные величины, доступные и в вызывающем, и в других визуалах — это называется побочным эффектом. А может не менять, а просто пользоваться их значениями — если это не запрещено средствами языка. Если все величины всех визуалов ранговой дракон-модели можно использовать и менять в любом из этих визуалов — говорят, что у них единая область видимости. Между такой моделью и эквивалентным ей единым визуалом нет разницы при исполнении. Если в процессе-вставке и/или в головном процессе нельзя менять и/или читать величины, определённые за его пределами — говорят о различных областях видимости. В детали мы вдаваться не будем. Кстати, их нужно определять в рамках декларативного знания о системе процессов — т.е. за пределами техноязыка.

Для примера ниже показано определение «акробатического прыжка» для одного из современных языков программирования…

…и определения знаков, введённые для её записи:

Особо разъяснять эти рисунки мы не будем — для того и визуализация, чтобы перевести всё, что можно, в графику и поясняющий текст. ;-)

Разветвители и соединители в гребёнках

Теперь рассмотрим смысл разветвителей и соединителей. Для этого введём ещё две шампур-вершины:

Как упомянуто во введении, их можно понимать как БС-соединители в новой роли — внутрисхемных «контактов». Именно эта роль — оригинальное решение шампур-метода. Ибо оказывается, что с их помощью можно описать реализацию не только вершин, но и схем в целом. Правда, эти возможности в исходном ШМ использованы не полностью, но это нетрудно исправить.

Начнём с разветвителей:

Здесь применён ещё один приём записи текста — совмещение формального и неформального определений. Второе при этом выступает как т.н. «формальный комментарий» к первому. Т.е. структура текста вершины принимает вид:

<осн-текст-1>[' ≡ '<внутр-комм-1>]{<разд-ед><осн-текст-i>[' ≡ '<внутр-комм-i>]}

Здесь осн-текст — это текст любой вершины, данный по её определению. Т.е. внутренний комментарий можно добавить к каждой вершине, где сочинитель считает необходимым (для читателя; кстати, в этой роли он может выступать и сам :-)).

Первая идея, представленная на схеме — условная вершина есть эквивалент дракон-переключателя на два направления. При этом развилка — просто иное представление разветвителя гребёнки (верхней). На момент проверки условия имеют переменные выбора нужные значения (условие развилки истинно) — идём на главный выход. В противном случае — на побочный. Можно и наоборот — идти на главный по ложности условия. В техноязыке элементы разветвителя сокращаются, и получается тот вид, который принят в определении языка.

С т. зр. синтаксиса, такое приравнивание даёт важный результат, представленный в нижнем ряду схем. А именно — ответы на вопрос развилки не обязательно понимать как тексты её выходных рёбер (плеч). Можно представить их и через контактные вершины — единообразно с переключателем. Справа дан вариант, сокращённый аналогично переключателю.

Разберёмся теперь с семантикой — что значит соединитель? Понятно, что некий переход по совпадению имён контактов. Его важное свойство — возможность и в случае, когда соединяемые части схемы не лежат на одной линии (не принадлежат линейному порядку, как говорят математики). Линия вертикали между соседними вершинами на шампуре тоже представляет переход — но его можно совершить только в линейном порядке. Можно назвать его естественным (Паронджанов при обсуждении шампур-метода говорил о «сочленении» в этом случае) — он реализуется механизмами исполнителя (скажем, в адресной машине по окончании текущей команды выбирается следующая записанная за ней в памяти, что обеспечивается устройством процессора). Межконтактный же переход имеет смысл безусловного (БП) — совершаемого не по порядку, а по имени-метке некоторой точки структуры.

Понимая это, рассмотрим представления вершин-соединителей:

Здесь мы видим использование семантики БП. В частности, очевидно, что команд с одной меткой м.б. много, а сама метка требуется только одна. По такому принципу можно представить и нелинейные знаки целиком с учётом расположения на диосцене. В частности, петлю цикла:

Из записи справа, помимо прочего, можно понять, зачем для вершин Имя/Адрес определено необязательное поле (с пунктирным контуром). Оно указывает, что переход по данному имени происходит против шампура, т.е. образует цикл. А текст поля сообщает, какой цикл в данной вершине Адрес начинается и какой цикл в данной вершине Имя заканчивается. Начинаться и/или заканчиваться в одной вершине может более одного цикла, если эти циклы т.н. вложенные — входят друг в друга, образуя своего рода «матрёшку».

Читателю, думается, нетрудно будет «достроить» структуру цикла, используя описания развилки выше.

Для нижней гребёнки представление очевидно — добавляется столько команд перехода (вершин Адрес), сколько «зубцов». Это можно понять из правила сокращения безусловных переходов, образующих цепочки. Оно показано на рисунке (для пары смежных БП-соединителей):

Для верхней всё не столь тривиально — но это имеет смысл рассмотреть отдельно для различных случаев употребления. Не забывая, как обычно, о тексте…

В целом случаи определяются логикой выбора выходов верхней гребёнки. Она возможна по И, ИЛИ, Исключающему ИЛИ.

Как известно, такой выбор подчиняется одной из стратегий:

  • «ленивой» — условия выбора вычисляются последовательно;
  • «усердной» - вычисляются все условия (м.б. одновременно).

Любая стратегия требует правил вычисления и отбора результатов. При «лени- вой» устанавливается порядок просмотра входов, который завершается при числе вариантов, допустимом по смыслу узла. При «усердной» выбирается столько ва- риантов, сколько допустимо по смыслу узла (случайно или по к.-л. критериям).

Конечно, содержание вершин и/или линий не всегда нужно учитывать. Поэтому дальше мы будем использовать и абстрактные схемы («слепыши»).

Итак, мы кое-что знаем о визуализации разветвляющихся и циклических конструкций алгоритмов. А какие конструкции нужно строить? По теории алгоритмов, любой алгопроцесс можно построить из структур следования (цепочек вершин типа действия) и циклов. Менее строго можно допустить ветвления. На сей счёт была доказана т.н. теорема Б<о|ё>ма-Джакопини. Интересующиеся могут найти её вкниге С.З. Свердлова (как можно видеть, мы для примера применили РБНФ к «обыденному») тексту — чтобы указать на разночтение имени одного из соавторов :-)).

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

И как же строятся схемы? Шампур-метод устанавливает правила на этот счёт — одни более строгие, другие менее. Начнём с более строгих — которые составляют основу метода и при некотором «графитном» понимании задачи сочинителем достаточны для вывода схем.

vershiny_i_linii_sxem_-_smysl_v_grafike_i_tekste.1347178408.txt.gz · Последние изменения: 2012/09/09 12:13 — Владислав Жаринов