Авторизация

Логин: Пароль:
Регистрация Забыли свой пароль?

Обсудим алгоритм проверки связей между множествами

Страницы: 1
Обсудим алгоритм проверки связей между множествами
#1
16.06.2010 22:58:50
Добрый вечер. Для начала опишу прогу, а потом проблему, с которой я столкнулась. Пользователем вводится число множеств в функции (максимум 10) Р (a;b;c;d;e;f;g;h;k;l), где Р – непосредственно булева функция, а {a;b;c;......} – частично упорядоченные множества. Затем вводится их мощность, допустим {a больше b} и {a больше c} программа проверяет соответствуют ли введеные пользователем соотношения аксиомам булевых функций (Для каждого элемента х∈Р ; х≤х (рефлексивность); Если х≤у; у≤х; х=у (антисимметричность); Если х≤y; y≤z; x≤z (транзитивность) ). И потом строит диаграмму Хассе (по-человечески граф), для примера приведенного выше выглядеть будет так (рис1). Когда множеств больше, выглядит это сложнее и связей гораздо больше, связи могут быть между любыми множествами.
Рисунок

Ввод количества функций происходит выбором из ComboBox нужного числа. Потом выводятся непосредственно функции, а точнее все какие могут быть отношения между ними. Сами функции пишутся в Label в Caption, а "<>" между ними выбирается также из ComboBox. Считать непосредственно то, где находятся связи я могу. А вот как проверить на правильность не знаю. Точнее общий алгоритм подобрать не могу. Не описывать же для каждого случая в отдельности.

Обращаюсь к Вам, может кто сталкивался с данной проблемой либо просто есть мысли на данный счет. Давайте обсудим.
 
 
#2
16.06.2010 23:55:46
Цитата
Ольга Кабушева пишет:
Считать непосредственно то, где находятся связи я могу. А вот как проверить на правильность не знаю.

Не совсем понятно, что все-таки требуется. Распишите задачу подробней
 
 
#3
17.06.2010 11:20:54
По моему и так достаточно подробно. Если я правильно понял, то основная проблема в проверки введенных соотношений аксиомам булевых функций.
Цитата
программа проверяет соответствуют ли введеные пользователем соотношения аксиомам булевых функций (Для каждого элемента х∈Р ; х≤х (рефлексивность); Если х≤у; у≤х; х=у (антисимметричность); Если х≤y; y≤z; x≤z (транзитивность) )
 
 
#4
17.06.2010 16:14:53
Чтобы проще было понять, что мне нужно, вот скрины проги. Не смотрите, что она в таком виде, просто в божеский вид я привожу уже после того как все работает.
Значит-с так. Это скрин того как выбирается количество множеств.

Рисунок

После выбора сразу вырисовываются все какие могут отношения между ними.

Рисунок

Дальше мы проставляем связи между ними, где нам нужно

Рисунок

Ну а после этого при нажатии кнопочки "Нарисовать граф" это все считывается (как показано ниже, сейчас просто выводится на экран то где понаставлены связи и все) и либо вырисовывается граф либо говорится, что связи проставлены не верно.

Рисунок

В данный момент у нас ошибка a<d, а должно быть a>d либо ничего поэтому поводу не сказано. Ошибка потому, что a>b и b>d -> a>d. Вот как это все проанализировать я не знаю. Точнее общий алгоритм этого найти не могу.
 
 
#5
17.06.2010 17:51:29
Если заметили, то у нас множества расписаны типа такой верхнетреугольной матрицы с побочной диагональю. Сначала меня посетила мысль, что проверять просто по диагоналям, но это идея отпала, так как у нас множеств может быть больше 4.
Кидайте все свои идеи обсудим и найдем решение. Помогите!!!!
 
 
#6
17.06.2010 17:52:46
Цитата
Артём Кулинич пишет:
По моему и так достаточно подробно. Если я правильно понял, то основная проблема в проверки введенных соотношений аксиомам булевых функций.
Цитата
программа проверяет соответствуют ли введеные пользователем соотношения аксиомам булевых функций (Для каждого элемента х∈Р ; х≤х (рефлексивность); Если х≤у; у≤х; х=у (антисимметричность); Если х≤y; y≤z; x≤z (транзитивность) )

Правильно поняли.
 
 
#7
17.06.2010 18:02:16
Пока я еще не полностью понял вашу проблему, но могу сказать, что такие задачи довольно хорошо решаются с помощью программирования в ограничениях. Бывают разные программы, где подобные проблемы можно решать
Изменено: motorway11 - 17.06.2010 18:02:31
Accende lumen sensibus, infude ainorem corbidus!
 
 
#8
17.06.2010 18:31:55
Цитата
motorway11 пишет:
решаются с помощью программирования в ограничениях.


Это как? Расскажите подробнее
 
 
#9
17.06.2010 18:53:13
Это достаточное новое направление в программировании, оно быстро развивается. Там в отличие от императивного, алгоритмического программирования задача представляется в виде модели, то есть совокупности связей, ограничений, накладываемых на переменные. Их может быть произвольное количество любого вида. Далее запускаются вычисления, и находится область решений, которая удовлетворяет этим ограничениям. Если же обнаружено противоречие, то выводится соотв. сообщение. Поэтому там учитываются все связи, и при этом не надо самому писать алгоритм. Могут быть логические условия, данные о множествах и др.
Есть разные системы, которые этот принцип реализуют. Из иностранных, напр. Newton, CLP, ILOG Solver. Но не уверен точно, сможете ли вы там это записать и решить.
Accende lumen sensibus, infude ainorem corbidus!
 
 
#10
17.06.2010 18:57:40
Интересно, а есть пример чего-нибудь реализованного?
 
 
#11
17.06.2010 19:01:32
Я сам пользуюсь одной разработкой уже давно, название не хотел бы говорить. Из иностранных пробовал ILOG Solver, но в нем не очень разобрался. Вот, кстати, задачи из теории чисел, о которых я говорил в соседней ветке, я пробовал там решать. Скорость весьма хорошая, но есть как раз ограничение по макс. целому числу. И я сделал версию этой программы с большими целыми числами, но пока не полную. Там можно писать уравнения в целых числах, добавлять к ним логич. условия и т.п. В обычных программах так легко этого не сделаешь.
Т.е., в принципе я могу проверить какую-то систему на совместность. Только насчет отношений, которые сверху указаны, не знаю точно - их надо как-то тоже записать в виде модели
Изменено: motorway11 - 17.06.2010 19:01:54
Accende lumen sensibus, infude ainorem corbidus!
 
 
#12
17.06.2010 19:20:19
Это прога для института. В ней нужно написать алгоритм проверки. Какую-то другую систему подключать не надо. Нужно сделать просто, но так чтобы работало.
 
 
#13
17.06.2010 21:17:10
Может быть сделать, что-то вроде сортировки? То есть допустим есть у нас элементы a,b,c,d,e,f И Тогда задавая связи между соседними элементами (проще говоря расставляя их в порядке возрастания/убывания) мы получим то что нам нужно.
 
 
#14
17.06.2010 21:36:55
Так связи необязательно должны быть между соседними и вообще не все обязательно описывать. В этом и трудность.
 
 
#15
17.06.2010 21:51:45
То есть связи могут быть не все? А как же тогда построить граф?
Про соседнии я написал, потому что так элементы проще расставлять в порядке возрастания/убывания.
 
 
#16
17.06.2010 22:47:31
Не все могут быть описаны. Они ведь исходят из аксиом. Граф и строиться по тем связям, которые мы описали.
 
 
#17
18.06.2010 08:05:53
Чтобы было больше понятно, вот пример. Есть у нас 5 функций: a, b, c, d, e. Связи задаем следующие: a>b, a>d, b>e, c>d, d>e. Получается следующее:
Рисунок
Не уверена в связи между а и с, а все остальное должно рисоваться так, как показано.
А если дописать связь c<e, то программа должна выдать ошибку, что данный граф нарисовать не возможно.
Изменено: Ольга Кабушева - 18.06.2010 08:16:22
 
 
#18
18.06.2010 17:30:17
Смутная идея такая - после задания связей выбирать произвольно числа, которые им удовлетворяют. А при задании следующих проверять в программе, выполняется ли это, с помощью обычных проверок условий if(c<e) ...
Либо искать все связи, относящиеся к данной переменной, выводить из них условия (на основе законов неравенств) и дальше делать проверки
Accende lumen sensibus, infude ainorem corbidus!
 
 
#19
18.06.2010 20:41:22
Ольга Кабушева,
a>b
b>c
a>d
c>d
А вот такая ситуация - нормальна или ошибочна?
 
 
#20
18.06.2010 20:45:13
Цитата
Иван Седаков пишет:
Ольга Кабушева,
a>b
b>c
a>d
c>d
А вот такая ситуация - нормальна или ошибочна?

Нормальна, они идут друг за другом вниз, ответвлений никаких нет.
 
 
#21
18.06.2010 21:11:40
Мысли пока такие:
1. Составляем квадратную матрицу, в программе например формируем ее так:
'1' означает, что множество соответствующее номеру строки больше множеству соответствующему номеру столбца
'-1' - наоборот
0- равно (если такое возможно по условию задачи, но это усложняет ее)
пустота - данных нет


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

3. далее сравнить эти вектора

либо
последовательно проходить по матрице и с каждым новым правилом заполнять недостающие элементы, а если в ячейке , для которой стало возможно определить соотношение уже есть введенное пользователем соотношение и они различаются, то выдать ошибку
 
 
#22
19.06.2010 14:43:18
Цитата
Иван Седаков пишет:
Мысли пока такие:
1. Составляем квадратную матрицу, в программе например формируем ее так:
'1' означает, что множество соответствующее номеру строки больше множеству соответствующему номеру столбца
'-1' - наоборот
0- равно (если такое возможно по условию задачи, но это усложняет ее)
пустота - данных нет

Не очень поняла. У нас сейчас в программе матрица верхнетреугольная по побочной диагонали. И формировать как Вы говорите не получится. Если для 5 множеств, то у нас вот такая матрица получается

a..b b..c c..d d..e
a..c b..d c..e
a..d b..e
a..e

Вместо ".." вставляется знак "</>"
 
 
#23
20.06.2010 15:14:28
Ольга Кабушева,
Код
   а   б   в   г   д
а -    <  >  <   >
б      -   <  >  <
в           -   <  >
г                -   >
д                     -

Матрицу формируем в таком виде. (Знаки <> в данном примере поставлены произвольно)
 
 
#24
20.06.2010 15:20:07
Думаю, что ввод связей оставлю как сейчас, а после в проге буду уже формировать такую матрицу.
 
 
#25
20.06.2010 15:22:02
Ольга Кабушева,
Цитата
Ольга Кабушева пишет:
Думаю, что ввод связей оставлю как сейчас, а после в проге буду уже формировать такую матрицу.

Я думаю, что Иван Седаков, так и имел ввиду
 
 
 
Страницы: 1
Читают тему (гостей: 1, пользователей: 0, из них скрытых: 0)