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

Язык ДРАКОН и линейные бинарные графы
https://forum.drakon.su/viewtopic.php?f=148&t=6693
Страница 1 из 1

Автор:  Владимир Паронджанов [ Суббота, 19 Октябрь, 2019 08:09 ]
Заголовок сообщения:  Язык ДРАКОН и линейные бинарные графы

Язык ДРАКОН
и линейные бинарные графы


Благодарю участника нашего форума PSV100, который вдохновил меня на создание этой темы.

PSV100 писал(а):
На форуме оживилась тема про школу Шалыто. В тех краях есть такая любопытная штуковина:
Вложение:

Так называемые линейные бинарные графы также планарны, как и ДРАКОН. Применяются не только для отображения структур логических формул, но и имеется методика построения общей схемы для "склеивания" нескольких формул, для чего и необходимо раскладывать явно "да/нет"-отношения.
В общем, это пример полезности такой возможности.

Схемы выражаются и по-драконовски.

Полный текст сообщения PSV100 читать здесь.

Автор:  Владимир Паронджанов [ Суббота, 19 Октябрь, 2019 08:30 ]
Заголовок сообщения:  Re: Язык ДРАКОН и линейные бинарные графы

Язык ДРАКОН
и линейные бинарные графы. Кадр 2


План моего рассказа

1. Сначала читаем работу Данилова
Цитата:
Данилов В.Р. Методы представления функции переходов при генерации автоматов управления на основе генетического программирования
Она выложена в предыдущем сообщении. Можно скачать.

2. Находим в работе Данилова на стр. 32 рисунок
Цитата:
Рис. 21. Линейные бинарные графы для формул на переходах

3. На рис. 21 выбираем верхнюю часть, где линейный бинарный граф описывает функцию f = ab V c (конъюнкция a и b, затем дизъюнкция с).

4. Далее я покажу, как этот бинарный граф превращается в дракон-схему.

Итак, начинаем.
Читаем рис. 21 и выбираем верхний линейный бинарный граф:

Изображение

5. На голубом рисунке (см. ниже) мы видим:

5.1. точную копию линейного бинарного графа для функции f = ab V c

5.2. тот же граф, повернутый на 90 градусов по часовой стрелке

5.3. тот же граф после равносильных преобразований

Вложение:
Дракон и линейн бинарные графы1 .png
Дракон и линейн бинарные графы1 .png [ 130.49 КБ | Просмотров: 7002 ]

В исходном линейном бинарном графе было 6 изгибов.
В результате равносильных преобразований удалены 3 изгиба.
В самом нижнем графе всего 3 изгиба.

Автор:  Владимир Паронджанов [ Суббота, 19 Октябрь, 2019 11:07 ]
Заголовок сообщения:  Re: Язык ДРАКОН и линейные бинарные графы

Язык ДРАКОН
и линейные бинарные графы. Кадр 3


План рассказа

6. На голубом рисунке (см. ниже) мы видим:

6.1. точную копию линейного бинарного графа, показанного в предыдущем сообщении (в самом низу)

6.2. убираем все стрелки, добавляем иконы Заголовок и Конец, рисуем жирный шампур.
В итоге получаем дракон-схему, эквивалентную исходному линейному бинарному графу.

Полученная дракон-схема описывает функцию f = ab V c,
что и требовалось доказать.

Вложение:
Дракон и линейн бинарные графы2.png
Дракон и линейн бинарные графы2.png [ 128.54 КБ | Просмотров: 6998 ]

Прошу критиковать

Автор:  Дмитрий Бардынин [ Суббота, 19 Октябрь, 2019 15:33 ]
Заголовок сообщения:  Re: Язык ДРАКОН и линейные бинарные графы

Красиво. И понятно. У графа Шалыто есть интересное преимущество: он компактный и линейный.

Автор:  Владимир Паронджанов [ Суббота, 19 Октябрь, 2019 17:26 ]
Заголовок сообщения:  Re: Язык ДРАКОН и линейные бинарные графы

Дмитрий Бардынин писал(а):
У графа Шалыто есть интересное преимущество: он компактный и линейный.
Вы правы: он компактный.
Но компактность не всегда является достоинством.

Часто приходится выбирать между компактностью и понятностью (ясностью, доходчивостью).

Язык ДРАКОН ставит на первое место понятность (доходчивость).

Преимущество ДРАКОНа в понятности (ясности, доступности).

Что касается линейности, то это свойство в равной мере относится и к бинарному графу и к эквивалентной ему дракон-схеме.

Автор:  LKom [ Воскресенье, 20 Октябрь, 2019 08:00 ]
Заголовок сообщения:  Re: Язык ДРАКОН и линейные бинарные графы

Цитата:
линейные бинарные графы
Кому это надо?
Где это используется?

Есть практические примеры? Без абстрактных: a, b, c, f.
Смысла в приведенных графах нет.

Автор:  Владимир Паронджанов [ Воскресенье, 20 Октябрь, 2019 08:23 ]
Заголовок сообщения:  Re: Язык ДРАКОН и линейные бинарные графы

LKom писал(а):
Цитата:
линейные бинарные графы
Кому это надо?
Где это используется?

Есть практические примеры? Без абстрактных: a, b, c, f.
Смысла в приведенных графах нет.
Это не так. Смысл есть, причем очень большой.

Это теория графов. Абстрактная математическая теория.

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

Как указывает Данилов, линейные бинарные графы, в частности, используются в задаче "Умный муравей".
Но они могут использоваться где угодно.

Это похоже на вопрос: Где используется теорема Пифагора?
Да где угодно — во множестве практических примеров.

Но. Некоторые теоретические результаты могут в отдельных случаях нигде не использоваться.

Они представляют теоретичнский интерес и служат развитию науки.

Автор:  Владимир Паронджанов [ Воскресенье, 20 Октябрь, 2019 08:37 ]
Заголовок сообщения:  Re: Язык ДРАКОН и линейные бинарные графы

Что такое линейный граф?

Цитата:
Path graph
From Wikipedia, the free encyclopedia
(Redirected from Linear graph)


In the mathematical field of graph theory, a path graph or linear graph is a graph whose vertices can be listed in the order v1, v2, …, vn such that the edges are {vi, vi+1} where i = 1, 2, …, n − 1. Equivalently, a path with at least two vertices is connected and has two terminal vertices (vertices that have degree 1), while all others (if any) have degree 2.

Paths are often important in their role as subgraphs of other graphs, in which case they are called paths in that graph. A path is a particularly simple example of a tree, and in fact the paths are exactly the trees in which no vertex has degree 3 or more. A disjoint union of paths is called a linear forest.

Paths are fundamental concepts of graph theory, described in the introductory sections of most graph theory texts.

Цитата:
Перевод на русский

математической области теории графов , А путь графа или линейный граф представляет собой график , чьи вершины могут быть перечислены в следующем порядке : V 1 , об 2 , ..., v п такие , что ребра являются { об я , v я + 1 } , где i = 1, 2,…, n - 1. Эквивалентно, путь, по крайней мере, с двумя вершинами связан и имеет две конечные вершины (вершины, имеющие степень 1), в то время как все остальные (если таковые имеются) имеют степень 2.

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

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

Цитата:

Автор:  Владимир Паронджанов [ Воскресенье, 20 Октябрь, 2019 10:09 ]
Заголовок сообщения:  Re: Язык ДРАКОН и линейные бинарные графы

См. важное понятие "Степень вершины"
viewtopic.php?f=148&t=6697

Локально линейный граф

Автор:  Владимир Паронджанов [ Воскресенье, 20 Октябрь, 2019 23:00 ]
Заголовок сообщения:  Re: Язык ДРАКОН и линейные бинарные графы

Я написал письмо Владимиру Рюриковичу Данилову

Цитата:
Линейные бинарные графы

сегодня, 22:49

Здравствуйте, Владимир Рюрикович!

Прочитал Вашу работу МЕТОД ПРЕДСТАВЛЕНИЯ АВТОМАТОВ ЛИНЕЙНЫМИ БИНАРНЫМИ ГРАФАМИ ДЛЯ ИСПОЛЬЗОВАНИЯ В ГЕНЕТИЧЕСКОМ ПРОГРАММИРОВАНИИ
Меня заинтересовали линейные бинарные графы.

Я сравнил их с представлением на языке ДРАКОН в теме:
Язык ДРАКОН и линейные бинарные графы

Обращаюсь к Вам с просьбой: если Вас не очень затруднит, высказать Ваше мнение

С уважением,
Владимир Данилович Паронджанов
Mobile: +7-916-111-91-57
Viber: +7-916-111-91-57
E-mail: vdp2007@bk.ru
Skype: vdp2007@bk.ru
Website: http://drakon.su
Webforum: http://forum.drakon.su

Автор:  Владимир Паронджанов [ Среда, 23 Октябрь, 2019 17:15 ]
Заголовок сообщения:  Re: Язык ДРАКОН и линейные бинарные графы

Получил ответ от Владимира Данилова
Цитата:
Re: Линейные бинарные графы

сегодня, 16:07

Добрый день,

Прошу прощения за поздний ответ. Насколько я понял, эти графы можно перерисовать в форму языка ДРАКОН, с сохранением их свойств, но это понятно и без меня

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

В нашей с ним работе это представление использовалось для генетических алгоритмов (преимущество тут в компактности по сравнению с полной таблицей). Не знаю, в какой работе Шалыто они упоминаются в первый раз, я ссылался на Шалыто А.А. "Логическое управление. Методы аппаратной и программной реализации алгоритмов".

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

Надеюсь, что смог хоть чем-то тут помочь.

С уважением,
Владимир

Страница 1 из 1 Часовой пояс: UTC + 3 часа
Powered by phpBB® Forum Software © phpBB Group
https://www.phpbb.com/