DRAKON.SU

Текущее время: Четверг, 28 Май, 2020 09:21

Часовой пояс: UTC + 3 часа




Начать новую тему Ответить на тему  [ Сообщений: 11 ] 
Автор Сообщение
СообщениеДобавлено: Суббота, 19 Октябрь, 2019 08:09 

Зарегистрирован: Воскресенье, 24 Февраль, 2008 15:32
Сообщения: 4698
Откуда: Москва
Язык ДРАКОН
и линейные бинарные графы


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

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

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

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

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


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Суббота, 19 Октябрь, 2019 08:30 

Зарегистрирован: Воскресенье, 24 Февраль, 2008 15:32
Сообщения: 4698
Откуда: Москва
Язык ДРАКОН
и линейные бинарные графы. Кадр 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 КБ | Просмотров: 747 ]

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


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Суббота, 19 Октябрь, 2019 11:07 

Зарегистрирован: Воскресенье, 24 Февраль, 2008 15:32
Сообщения: 4698
Откуда: Москва
Язык ДРАКОН
и линейные бинарные графы. Кадр 3


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

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

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

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

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

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

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


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Суббота, 19 Октябрь, 2019 15:33 

Зарегистрирован: Пятница, 08 Декабрь, 2017 18:24
Сообщения: 324
Откуда: Астрахань-Сочи
Красиво. И понятно. У графа Шалыто есть интересное преимущество: он компактный и линейный.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Суббота, 19 Октябрь, 2019 17:26 

Зарегистрирован: Воскресенье, 24 Февраль, 2008 15:32
Сообщения: 4698
Откуда: Москва
Дмитрий Бардынин писал(а):
У графа Шалыто есть интересное преимущество: он компактный и линейный.
Вы правы: он компактный.
Но компактность не всегда является достоинством.

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

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

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

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


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Воскресенье, 20 Октябрь, 2019 08:00 

Зарегистрирован: Среда, 07 Январь, 2015 14:53
Сообщения: 1082
Цитата:
линейные бинарные графы
Кому это надо?
Где это используется?

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


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Воскресенье, 20 Октябрь, 2019 08:23 

Зарегистрирован: Воскресенье, 24 Февраль, 2008 15:32
Сообщения: 4698
Откуда: Москва
LKom писал(а):
Цитата:
линейные бинарные графы
Кому это надо?
Где это используется?

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

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

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

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

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

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

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


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Воскресенье, 20 Октябрь, 2019 08:37 

Зарегистрирован: Воскресенье, 24 Февраль, 2008 15:32
Сообщения: 4698
Откуда: Москва
Что такое линейный граф?

Цитата:
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 

Зарегистрирован: Воскресенье, 24 Февраль, 2008 15:32
Сообщения: 4698
Откуда: Москва
См. важное понятие "Степень вершины"
viewtopic.php?f=148&t=6697

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


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Воскресенье, 20 Октябрь, 2019 23:00 

Зарегистрирован: Воскресенье, 24 Февраль, 2008 15:32
Сообщения: 4698
Откуда: Москва
Я написал письмо Владимиру Рюриковичу Данилову

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

сегодня, 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 

Зарегистрирован: Воскресенье, 24 Февраль, 2008 15:32
Сообщения: 4698
Откуда: Москва
Получил ответ от Владимира Данилова
Цитата:
Re: Линейные бинарные графы

сегодня, 16:07

Добрый день,

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

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

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

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

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

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


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 11 ] 

Часовой пояс: UTC + 3 часа


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Вся информация, размещаемая участниками на конференции (тексты сообщений, вложения и пр.) © 2008-2020, участники конференции «DRAKON.SU», если специально не оговорено иное.
Администрация не несет ответственности за мнения, стиль и достоверность высказываний участников, равно как и за безопасность материалов, предоставляемых участниками во вложениях.
Powered by phpBB® Forum Software © phpBB Group
Русская поддержка phpBB