DRAKON.SU
https://forum.drakon.su/

Автоматы и алгоритмы
https://forum.drakon.su/viewtopic.php?f=62&t=1152		 Страница 1 из 3
Автор:  TAU [ Суббота, 30 Август, 2008 21:08 ]
Заголовок сообщения:  Автоматы и алгоритмы
Илья Ермаков писал(а):
Другой пример - если реализуется какой-то протокол (например, некий клиент-серверный), то наилучший способ его увидеть-понять - формализовать его в Дракон-схеме

Очень спорное заявление. В таком случае более интересны визуальные нотации, основанные на состояниях (из тех же SDL, UML или ISO МЭК 61131-3). Если же протокол имеет временные ограничения - тут потребуются уже средства UML 2.0.

Илья Ермаков писал(а):
Дракон включает в себя автоматное программирование в удобной и наглядной форме

Это как же, простите? Не различаете диаграммы состояний и блок-схемы (управляющие графы программ)?
Автор:  Илья Ермаков [ Суббота, 30 Август, 2008 23:41 ]
Заголовок сообщения:  Re: что такое язык дракон
Состояние = ветка. Силуэт - чистой воды автомат. А в рамках одной ветки имеем обычное алгоритмическое управление. Мы ж тут это много обсуждали.
Автор:  TAU [ Понедельник, 01 Сентябрь, 2008 13:50 ]
Заголовок сообщения:  Re: что такое язык дракон
Илья Ермаков писал(а):
Состояние = ветка. Силуэт - чистой воды автомат. А в рамках одной ветки имеем обычное алгоритмическое управление. Мы ж тут это много обсуждали.

Можно много обсуждать и не понимать основ. В блок-схемах и в Драконе прямоугольник обозначает процесс, а в графах конечных автоматов вершины обозначают состояния. Разницу между процессом и состоянием Вы осознаете или нет?
Автор:  Борис Рюмшин [ Понедельник, 01 Сентябрь, 2008 13:56 ]
Заголовок сообщения:  Re: что такое язык дракон
TAU писал(а):
Можно много обсуждать и не понимать основ. В блок-схемах и в Драконе прямоугольник обозначает процесс, а в графах конечных автоматов вершины обозначают состояния. Разницу между процессом и состоянием Вы осознаете или нет?

Прочитайте внимательнее:
Илья Ермаков писал(а):
Состояние = ветка. Силуэт - чистой воды автомат.
Автор:  Valery Solovey [ Понедельник, 01 Сентябрь, 2008 14:19 ]
Заголовок сообщения:  Re: что такое язык дракон
Вообще-то, вершина графа конечного автомата не обязана быть состоянием.
Автор:  Илья Ермаков [ Понедельник, 01 Сентябрь, 2008 15:31 ]
Заголовок сообщения:  Re: что такое язык дракон
TAU писал(а):
Можно много обсуждать и не понимать основ. В блок-схемах и в Драконе прямоугольник обозначает процесс, а в графах конечных автоматов вершины обозначают состояния. Разницу между процессом и сосостоянием Вы осознаете или нет?


Действительно, перечитайте внимательно. Подумайте над вопросом, что такое силуэт в Драконе, с формальной точки зрения? Именно КА. И если мы хотим выразить его на императивном языке, то напишем:
VAR state: INTEGER;
REPEAT
CASE state OF
ветка1: .... state := ветка2 ... state := ветка3
ветка2:
ветка3: ... state := конец
UNTIL state = конец;

Конечный автомат - очень общий формализм. Состояния тоже могут иметь сколь угодно общую трактовку. В рамках одного крупного состояния может быть много мелких. Описанных не только в виде КА, но и алгоритмическими конструкциями. Семантику действий можно вешать не только на вершины, но и на переходы (не помню точно названий, но один тип - автоматы Мили, другие - ещё кого-то..).
В конце концов, обычная программа - тоже разновидность автомата. Если структурная - то это автомат с сильными ограничениями на топологию. Если goto - то вообще произвольный. Дракон - промежуточный вариант.

А КА как способ синт. анализа (допуск/не допуск входной цепи знаков-сигналов) - только узкий частный случай.

Так что я не могу понять, что именно не понимаете Вы в обсуждении автоматности Дракона.
Автор:  Рэйлвэй Каген [ Понедельник, 01 Сентябрь, 2008 19:37 ]
Заголовок сообщения:  Re: что такое язык дракон
Как мне кажется, двусмысленность возникла из-за того, что кроме автоматов Мура(значения выходных переменных формируются в вершинах) существуют ещё автоматы Мили(значения выходных переменных формируются не в вершинах графов переходов, а на дугах). Вдобавок теория рассматривает ещё и их гибриды - автоматы Мура-Мили.

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

рис.4 Алгоритм "рыбная ловля" из книги Паронджанова,

где ветка завершается несколькими иконами "адрес". Жить не мешает, но конечным автоматом не является.
Автор:  Илья Ермаков [ Понедельник, 01 Сентябрь, 2008 22:13 ]
Заголовок сообщения:  Re: что такое язык дракон
Если ветка не завершается несколькими иконами "адрес", то говорить об автоматности вообще не приходится. Это просто последовательная декомпозиция на ветки.

Цитата:
где ветка завершается несколькими иконами "адрес". Жить не мешает, но конечным автоматом не является.


Является. Как раз автоматом Мура (операциями нагружены состояния). Как, по-вашему, должен определяться выбор очередного состояния, как не этими самыми несколькими выходными позициями у ветки? Это не "несколько выходов у одного перехода", а как раз несколько переходов, выбор между которыми производится алгоритмом, находящимся в вершине-состоянии. В SWITCH-технологии у Шалыто так же. Не говоря про то, что самый обычный структурный алгоритм (т.е. примитив Дракона) - это, в общем, тоже автомат. С ограничениями на топологию (рекурсивная древовидность полной развёртки. Аналогично конечно-рекурсивным ф-ям). В головке у машины тьюринга, в общем, тоже КА сидит. И уж физическая вычислимость вообще всегда основана на КА, не имеем другого способа. Не просто КА, а над памятью, конечно.

Цитата:
не будет конечным автоматом(строго по теории)

Чистая мат. модель - это замечательно. Но она бесполезна, пока не нагрузим её реальным, физическим смыслом. А нагружать можем по-разному, так, что математик и не признает дитятю :-)

Ну, в конце концов, отделите в своём воображении логику каждой ветки в отдельное "устройство".
Название ветки нарисуйте в кружочке, как состояние. А выходные адреса - как переходы из состояния. И каждый переход нагрузите условно неким входным символом, как в КА для синт. анализа.
И вообразите, что в момент перехода КА в некоторое состояние (ветку) активизируется внешнее устройство (алгоритм этой ветки), которое по окончании своей работы выдаёт символ-сигнал, по которому автомат переходит в следующее состояние. Так привычнее? Математически имеем полностью изоморфные конструкции.
Автор:  Рэйлвэй Каген [ Вторник, 02 Сентябрь, 2008 09:35 ]
Заголовок сообщения:  Re: что такое язык дракон
Илья Ермаков писал(а):
Как, по-вашему, должен определяться выбор очередного состояния, как не этими самыми несколькими выходными позициями у ветки?
Явной переменной(может и не одной), по которой в теле пойдет ветвление. При переходе к графу по рецепту Паронджанова(Ваш вариант такой же) эта переменная не сможет быть явно указана в кружочках-состояниях, её придётся прописывать на переходе. Никаких противоречий или минусов я здесь не вижу, в теорию нормально всё укладывается. С "не является" - признаю, погорячился.

Илья Ермаков писал(а):
..Название ветки нарисуйте в кружочке, как состояние.
Да с этим всё нормально. Рисовал ужЕ(где-то тут, на форуме).
Автор:  TAU [ Вторник, 02 Сентябрь, 2008 09:36 ]
Заголовок сообщения:  Re: что такое язык дракон
Борис Рюмшин писал(а):
Прочитайте внимательнее:
Илья Ермаков писал(а):
Состояние = ветка. Силуэт - чистой воды автомат

Да читал я. И прокомментировал - ерунда.

Силуэт - разновидность диаграммы ДРАКОНа. Кои по своей сути - описания потока управления (control flow, если так понятнее будет). Понимаете?

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

Диаграмма состояний, например, вполне может иметь две вершины, соединенные взаимно противоположно направленными стрелками (туда и обратно), и не предполагать никакого результата.
Автор:  TAU [ Вторник, 02 Сентябрь, 2008 09:50 ]
Заголовок сообщения:  Re: что такое язык дракон
Илья Ермаков писал(а):
силуэт в Драконе, с формальной точки зрения?

Не понимаю я, что означает в вашем представлении "формальная точка зрения".
Я Вам описал вполне прозрачно "естественную" точку зрения. Процесс и состояние - разные понятия, как ни крути и сколько слов ни городи, как Вы. :lol:

Илья Ермаков писал(а):
Состояния тоже могут иметь сколь угодно общую трактовку

И зачем она нужна - "сколь угодно общая"? Если есть традиционная, и наиболее широко распространенная, подразумеваемая по умолчанию? Нет, я конечно, понимаю, что Вам нужно поспорить и тяжело признать собственную неправоту.

Илья Ермаков писал(а):
обычная программа - тоже разновидность автомата

Опять принципиальная ошибка.

Илья Ермаков писал(а):
что я не могу понять, что именно не понимаете Вы в обсуждении автоматности Дракона

Только то, что это (как и блок-схемы алгоритмов и программ вообще) - не автомат.
Вы можете сопоставить исполняемой программе состояния и нарисовать диаграмму переходов программы из одного состояния в другое. Иногда она будет весьма похожей на блок-схему. Но это - не одно и то же.
Автор:  TAU [ Вторник, 02 Сентябрь, 2008 10:01 ]
Заголовок сообщения:  Re: что такое язык дракон
Уважаемый Илья,

вынужден продолжить Вас поправлять.
Илья Ермаков писал(а):
операциями нагружены состояния
Не кажется, что это - нонсенс?
Состояние может возникать по завершению операции. Как бы Вам объяснить, чтобы было понятнее... Представьте себе, что каждое действие в блок-схеме выполняется не мгновенно, а имеет некоторую протяженность во времени.

Илья Ермаков писал(а):
Как, по-вашему, должен определяться выбор очередного состояния, как не этими самыми несколькими выходными позициями у ветки?
Кстати, в блок-схемах алгоритмов и программ (естественно и у Паронджанова) прямо выделены два разных вида блоков для действий и условий. И у действия один вход и один выход, а у условия - два выхода обязаны быть как минимум. Никакой прямой аналогии, естественно, в графах переходов автоматов нет.

Илья Ермаков писал(а):
В SWITCH-технологии у Шалыто так же
SWITCH-технология Шалыто описывает не все алгоритмы, а только их некоторый специальный класс.

Илья Ермаков писал(а):
самый обычный структурный алгоритм (т.е. примитив Дракона) - это, в общем, тоже автомат
Вот это "в общем" - нарушение строгости. Я считаю, недопустимое. Вносящее путаницу в принципиально различные понятия.

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

Илья Ермаков писал(а):
Чистая мат. модель - это замечательно. Но она бесполезна, пока не нагрузим её реальным, физическим смыслом
Уловка? :lol: Смысл у диаграммы состояний и управляющего графа программы - разный.
Автор:  Илья Ермаков [ Вторник, 02 Сентябрь, 2008 10:07 ]
Заголовок сообщения:  Re: что такое язык дракон
Не согласен. Дело не в личной правоте-неправоте. А в докапывании до природы вещей.

Цитата:
Идущая от одного прямоугольника (изображающего процесс) к следующему стрелка обозначает передачу управления, то есть изображается последовательность действий, направленная на преобразование некоторых исходных данных в результат (алгоритм).

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

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

Цитата:
Диаграмма состояний, например, вполне может иметь две вершины, соединенные взаимно противоположно направленными стрелками (туда и обратно), и не предполагать никакого результата.

Программа, в общем случае, с GoTo, может иметь любые переходы. Переходя к структурному программированию (или Дракону, с меньшими ограничениями), мы просто накладываем ограничения на то, какие циклы в графе смены состояний могут быть.

Само собой разумеется, что вычислительная ("управлительная") мощность произвольного автомата и автомата управления структурной программы одинаковы - если они работают над памятью.

Если Вы не хотите видеть однородности понятий - Ваше право. Но упёртость в таких случаях не позволяет докапываться до глубинной сути вещей.
Автор:  Илья Ермаков [ Вторник, 02 Сентябрь, 2008 10:09 ]
Заголовок сообщения:  Re: что такое язык дракон
TAU писал(а):
Илья Ермаков писал(а):
Чистая мат. модель - это замечательно. Но она бесполезна, пока не нагрузим её реальным, физическим смыслом
Уловка? :lol: Смысл у диаграммы состояний и управляющего графа программы - разный.

[quote]
Слово "состояние" у КА столь общее, что не имеет само по себе никакого смысла - реального. А грузится этим смыслом в конкретном применении.
Автор:  Илья Ермаков [ Вторник, 02 Сентябрь, 2008 10:13 ]
Заголовок сообщения:  Re: что такое язык дракон
TAU писал(а):
КА - сокращение слов "конечный автомат". Автомат над памятью может быть бесконечным. Кстати, у машины Тьюринга традиционно подразумевается бесконечная лента... "Физическая вычислимость всегда основана на конечном автомате" - простите, не так.

Над памятью - да, бесконечным! За счёт бесконечности состояний памяти. Управление в машине Тьюринга (её головке) определено конечно, имеет конечное множество состояний - может быть представлено конечной таблицей правил и соотв. КА. И реализует конечный алгоритм.
Структуры управления императивного языка программирования - это автомат. Есть конечное множество состояний управления выполнением, мы всегда знаем (в отличие от декларативного п-я), в каком состоянии находимся, имеем из него конечное множество переходов в другие состояния (в зависимости от ситуации - памяти/портов. Поставьте каждой ситуации знак - и нагрузите им переход.).
Автор:  Илья Ермаков [ Вторник, 02 Сентябрь, 2008 10:21 ]
Заголовок сообщения:  Re: что такое язык дракон
Цитата:
Илья Ермаков писал(а):
операциями нагружены состояния
Не кажется, что это - нонсенс?
Состояние может возникать по завершению операции. Как бы Вам объяснить, чтобы было понятнее... Представьте себе, что каждое действие в блок-схеме выполняется не мгновенно, а имеет некоторую протяженность во времени.

Это не нонсенс - это классический вид автоматов - автоматы Мура.
По поводу длительности - кто мешает её учесть при "нагружении" автомата? Естественно, что в отличие от чистой математики в реальности появляются доп. физические характеристики.
Вы, наверное, раскрашенные сети Петри тоже за сети Петри не признаете, ибо "смысл другой"?

Цитата:
Илья Ермаков писал(а):
В SWITCH-технологии у Шалыто так же

SWITCH-технология Шалыто описывает не все алгоритмы, а только их некоторый специальный класс.

Вы имеете в виду "оптимальна для применения в специальном классе"? Никто не спорит. По поводу "описывает" - автоматное программирование позволяет описать любой алгоритм.
А у Шалыто, как я помню, в CASE-инструменте состояние автомата нагружается обычным программным кодом, например, на С. Точно так же, как ветка у Паронджанова.

Цитата:
Илья Ермаков писал(а):
Чистая мат. модель - это замечательно. Но она бесполезна, пока не нагрузим её реальным, физическим смыслом
Уловка? :lol: Смысл у диаграммы состояний и управляющего графа программы - разный.

Диаграмма состояний - это конкретное наглядное представление КА. То, что она заточена для выражения иной семантики, чем граф программы, никак не отменяет того, что любая императивная программа - это автомат, нагруженный операциями над памятью.
Автор:  Alexey_Donskoy [ Вторник, 02 Сентябрь, 2008 12:23 ]
Заголовок сообщения:  Re: что такое язык дракон
TAU писал(а):
Процесс и состояние - разные понятия
Допустим, процесс можно определить через смену состояний. А вот что такое состояние? ;)

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

Так что рассуждения о "принципиальном различии" процесса и состояния... несостоятельны ;)
Такая точка зрения может иметь место только с точки зрения конкретной формальной системы (например, UML). И эта точка зрения не представляет большого теоретического интереса.

Впрочем, практического - тоже ;) Попробуйте положить на код одну лишь UML-скую диаграмму состояний! Сразу обнаружится, что необходим будет определённый процесс, который крутится в цикле внутри узла с состоянием и последовательно проверяет условия возможных переходов...

Важно понять, что любая (исполняемая) программа по определению есть конечный автомат.
А вот любое формальное представление (диаграмма состояний, или потоковая диаграмма, или алгоритм) есть не более чем частная проекция КА в данной формальной системе. Ущербная проекция, недостаточная для представления системы в целом.

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

Резюме: Состояние и процесс не имеют фундаментального значения, но есть лишь термины определённой формальной системы. Любой из упомянутых терминов бессмысленно рассматривать в отрыве от контекста. И друг без друга. А вот вместе - их уже достаточно для описания программы.
Автор:  TAU [ Среда, 03 Сентябрь, 2008 10:23 ]
Заголовок сообщения:  Re: что такое язык дракон
Alexey_Donskoy писал(а):
рассуждения о "принципиальном различии" процесса и состояния... несостоятельны... Резюме: Состояние и процесс не имеют фундаментального значения, но есть лишь термины определённой формальной системы. Любой из упомянутых терминов бессмысленно рассматривать в отрыве от контекста. И друг без друга. А вот вместе - их уже достаточно для описания программы.

Вижу, ребята, что признать свою принципиальную неправоту Вы неспособны практически так же, как женщины в споре :lol:

Наводите, понимаешь, тень на плетень...

Занимаясь проблематикой, достаточно связанной с состояниями и доказательством свойств программ (между прочим, совершенно не связанной с UML ;-) - есть многое на свете, друг Горацио...), не могу пройти мимо Ваших принципиальных... эээ... ошибочек и неточностей, которые Вы пытаетесь скрыть за туманом "многих букафф" и казуистикой.

Процесс и состояние - разные понятия. В рамках самого что ни на есть общепринятого понимания, а не некой искусственной и отвлеченной от реальной жизни формальной системы.
Отождествлять их неверно. Надо называть вещи своими правильными именами, как нас мудро учил еще товарищ Кон-Фу-Цзы.

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

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

Ну что, полдень наступил? Тени рассеялись? :P
Автор:  TAU [ Среда, 03 Сентябрь, 2008 10:37 ]
Заголовок сообщения:  Re: что такое язык дракон
Илья Ермаков писал(а):
Цитата:
Илья Ермаков писал(а):
операциями нагружены состояния
Не кажется, что это - нонсенс?

Это не нонсенс - это классический вид автоматов - автоматы Мура

Простите, Илья, но ни в классических автоматах Мили, ни в классических автоматах Мура никаких операций нет.

Илья Ермаков писал(а):
Вы, наверное, раскрашенные сети Петри тоже за сети Петри не признаете, ибо "смысл другой"?

Нет, признаю. Потому как раскрашивание дополняет семантику сетей Петри, а не имеет принципиально отличной семантики. Конечно же, при этом смысл изменяется, что позволяет описывать более сложные семантически системы.
Автор:  Alexey_Donskoy [ Среда, 03 Сентябрь, 2008 12:04 ]
Заголовок сообщения:  Re: что такое язык дракон
TAU писал(а):
Alexey_Donskoy писал(а):
Резюме: Состояние и процесс не имеют фундаментального значения, но есть лишь термины определённой формальной системы.

Занимаясь проблематикой, достаточно связанной с состояниями и доказательством свойств программ
О, раз такая пьянка, и раз Вы сказали "А", скажите и "Б" - то есть, расскажите подробнее всё, о чём начали говорить... если не ради флейма... то переубеждать никого не придётся ;) А Ваш опыт может оказаться очень интересным!

TAU писал(а):
"Операторы преобразуют состояния... Таким образом, о состояниях и их свойствах, т.е. о предикатах, которым удовлетворяют состояния, целесообразно говорить не во время исполнения операторов, а в промежутках между исполнением оператора-предшественника и оператора-преемника"
Совершенно справедливо. И не вижу никаких противоречий с тем, что нами было сказано выше! ;)

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

Поэтому я и говорю, что термины "процесс" и "состояние" семантически определены только в рамках этой формальной модели, не более того. И приписывать им фундаментальный смысл ("над всеми моделями") было бы неверно.

Но это всё так, в порядке флуда; а что Вы хотели сказать по существу? Мне, например, очень интересно послушать!
Страница 1 из 3 Часовой пояс: UTC + 3 часа
Powered by phpBB® Forum Software © phpBB Group
https://www.phpbb.com/