OberonCore

Библиотека  Wiki  Форум  BlackBox  Компоненты  Проекты
Текущее время: Среда, 23 Август, 2017 09:05

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




Начать новую тему Ответить на тему  [ Сообщений: 15 ] 
Автор Сообщение
СообщениеДобавлено: Воскресенье, 18 Январь, 2015 18:29 

Зарегистрирован: Пятница, 13 Март, 2009 16:36
Сообщения: 552
Откуда: Казань
Например, требуется упростить,
2*x*3*(y+1) - 6*x
до
6*x*y
В принципе запрограммировать данное упрощение можно, но при этом не совсем понятно какие структуры данных и алгоритмы лучше для этого использовать.

Может быть кто-нибудь читал какую-нибудь статью или книгу, где описывается подобный алгоритм и детально описываются применяемые структуры данных?


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Воскресенье, 18 Январь, 2015 19:02 
Администратор

Зарегистрирован: Вторник, 15 Ноябрь, 2005 01:14
Сообщения: 4017
Откуда: Россия, Орёл
Символьные вычисления это. https://ru.wikipedia.org/wiki/%D0%A1%D0 ... 0%B8%D1%8F

Литературу не посоветую, но область этих алгоритмов уже хорошо обкатана в коммерческих (Maple, Mathematica и т.п.) и некоммерческих (Maxima) продуктах. А кое-кто и сам такие алгоритмы программирует...


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Воскресенье, 18 Январь, 2015 19:49 
Аватара пользователя

Зарегистрирован: Суббота, 29 Март, 2008 19:27
Сообщения: 968
Откуда: Россия, Чебоксары
Rifat писал(а):
не совсем понятно какие структуры данных и алгоритмы лучше для этого использовать.
Литературу не посоветую.
Сам делал, представляя формулу в виде дерева.
Ключевые процедуры:
- определение эквивалентности веток (рекурсивная функция с перебором порядка следования подветок в узлах);
- приведение констант (отлавливаются случаи умножения на 1 и на 0, например, а также деление и вычитание одинаковых веток;
- вынесение общего множителя за скобку;
- раскрытие скобок;
- прочая специфика (тригонометрические преобразования в моём случае).

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


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Воскресенье, 18 Январь, 2015 22:33 

Зарегистрирован: Пятница, 25 Ноябрь, 2005 12:02
Сообщения: 7583
Откуда: Троицк, Москва
Тема большая, единого решения нет.
Надо смотреть на класс задач -- Вы же комп не для таких тривиальных выражений нужен.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Воскресенье, 18 Январь, 2015 22:39 

Зарегистрирован: Пятница, 13 Март, 2009 16:36
Сообщения: 552
Откуда: Казань
Да, Вы правы есть разные типы задач. Для начала хотелось определиться с уравнениями из целых переменных и целых констант.
В книгах описано много разных классов задач и алгоритмы для их решения. Но алгоритмы чаще всего даются в виде, который может выполнить человек. При программировании же этих алгоритмов возникает много вопросов, как лучше организовать структуру данных, как производить поиск совпадающего многочлена, например. Хотелось бы прочитать какую-нибудь статью или книгу где детально рассматриваются различные алгоритмы упрощения и подробно рассмотрены структуры данных для этого.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 19 Январь, 2015 01:07 
Аватара пользователя

Зарегистрирован: Суббота, 29 Март, 2008 19:27
Сообщения: 968
Откуда: Россия, Чебоксары
Rifat писал(а):
При программировании же этих алгоритмов возникает много вопросов, как лучше организовать структуру данных, как производить поиск совпадающего многочлена, например.
Задавайте конкретные вопросы, отвечу.

Про многочлен. На уровне верхнего узла это есть сумма слагаемых.
Сначала сравниваем количество слагаемых. Если одинаково, то рекурсивно сравниваем слагаемые (с перебором разного порядка следования слагаемых).

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


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Среда, 21 Январь, 2015 17:53 

Зарегистрирован: Пятница, 13 Март, 2009 16:36
Сообщения: 552
Откуда: Казань
Поискал в интернете по поводу упрощения выражений. Вообще, общий алгоритм для упрощения относится к term rewriting system, но детальное описание со структурами данных я не нашел. Во многих случаях для term rewriting используются функциональные языки, типа Lisp, видимо там это делается достоточно просто.
А так похоже надо будет реализовывать Ad hoc алгоритм.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Четверг, 13 Июль, 2017 15:23 

Зарегистрирован: Пятница, 13 Март, 2009 16:36
Сообщения: 552
Откуда: Казань
Много времени прошло со времени начального поста. Снова занялся той идеей.
И сформулировал требования к структуре данных, которую хочу реализовать:
1. Выражение должно представляться в виде дерева, но не бинарного. Например, если складываются несколько переменных, то должна быть одна вершина "сложение" и список переменных, которые складываются.
2. При печати дерева, выражение должно печататься в том же виде, как оно было введено пользователем. А внутри дерево может быть организовано, как будет удобнее.
3. Определение одинаковых подвыражений должно быть очень дешево.
4. Должна сохраняться версионность изменений, чтобы можно было посмотреть как выражение выглядело на каждом этапе.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Пятница, 14 Июль, 2017 01:22 

Зарегистрирован: Понедельник, 30 Июль, 2007 10:53
Сообщения: 1506
Откуда: Беларусь, Минск
А в чём польза от недвоичного дерева?


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Пятница, 14 Июль, 2017 09:37 

Зарегистрирован: Пятница, 13 Март, 2009 16:36
Сообщения: 552
Откуда: Казань
Допустим, нужно вычислить предикат x + y + z = z + y + x. Если у недвоичного дерева в вершине сложения будут перечислены: x, y, z, а у другой вершины z, y, x, то будет проще их привести к одинаковому виду, отсортировав имена переменных лексикографически. И сразу будет видно, что подвыражения одинаковые, и соответственно предикат TRUE.
Если же, представлять выражение в виде двоичного дерева, то приведение к одинаковому виду будет сложнее, так как нужно будет переставлять местами переменные из разных вершин. К тому же, структура двоичного дерева может отличаться, например, одно поддерево будет выглядеть как (x + y) + z, а другое как x + (y + z). И определение одинаковости этих подвыражений будет затруднено.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Пятница, 14 Июль, 2017 13:07 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 8772
Откуда: Россия, Орёл
А почему бинарное дерево обсуждается как "естественное", а другие - "экстравагантные"?

Как раз естественно сразу считать узел n-арным оператором.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Суббота, 15 Июль, 2017 16:22 

Зарегистрирован: Понедельник, 30 Июль, 2007 10:53
Сообщения: 1506
Откуда: Беларусь, Минск
Rifat писал(а):
Допустим, нужно вычислить предикат x + y + z = z + y + x. Если у недвоичного дерева в вершине сложения будут перечислены: x, y, z, а у другой вершины z, y, x, то будет проще их привести к одинаковому виду, отсортировав имена переменных лексикографически.
Выглядит надуманным. Польза минимальна, и работает это только со скалярными x, y и z. С другой же стороны, анализ поддерева, у которого всего две ветви, кажется более простым. Да и операция сложения, вообще-то, двухместная. А возможность перемены мест слагаемых - это правило, которое навешивается сверху на формулу целиком (или на двоичное дерево).


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Суббота, 15 Июль, 2017 18:18 

Зарегистрирован: Пятница, 13 Март, 2009 16:36
Сообщения: 552
Откуда: Казань
Спор по поводу бинарное или не бинарное дерево не так важен пока.
Сейчас думаю над тем как определить, что (x=y) & (y = z) & not (x = z) всегда False.
Кто как думает какой алгоритм и структуры данных нужны для этого.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Вторник, 25 Июль, 2017 19:40 

Зарегистрирован: Понедельник, 25 Июнь, 2012 17:26
Сообщения: 115
В качестве отправной точки можно взглянуть на изложения Поспелова (Поспелов Д.А. Ситуационное управление. Теория и практика. - 1986):
http://raai.org/about/persons/pospelov/ ... pravl.djvu

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


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Пятница, 28 Июль, 2017 13:27 

Зарегистрирован: Пятница, 13 Март, 2009 16:36
Сообщения: 552
Откуда: Казань
В статье на Хабрахабре описаны некоторые приёмы упрощения, там же, кстати, есть ответ почему n-арное сложение лучше бинарного: https://habrahabr.ru/post/150043/#simplification


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

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


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

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


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

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