2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Задача на бинарное отношение
Сообщение21.03.2006, 20:40 


07/02/06
96
Хочу сказать сразу, помогать или решать задачу мне не надо, я её уже решил. Просто предложите какие-либо версии по решению. А условие, собственно, такое: задано множество, а на нем бинарное отношение путем указания пар элементов, что принадлежат бинарному отношению. Задание: определить свойства бинарного отношения (рефлексивность, симметричность, и т.д.), а также в случае эквивалентности определить разбитие на классы.

 Профиль  
                  
 
 
Сообщение22.03.2006, 09:57 
Заслуженный участник
Аватара пользователя


17/10/05
3709
:evil:
Если памяти и времени не жалко, построим отношение в матричной форме. Несмотря на расточительность, работает неплохо на практике даже для относительно больших матриц (такие задачи встречаются при построении компиляторов).

 Профиль  
                  
 
 
Сообщение22.03.2006, 18:26 


07/02/06
96
Вообще-то по условию нам памяти на матрицу не хватает (ну чтобы жизнь простой не казалась). Поэтому сначала предлагалось хранить список пар элементов. Я рассудил, что проверять свойства будет долго и нудно, поэтому данные храню в таком виде. Есть список элементов множества, из каждого выходит список ссылок на элементы множества. Ну а потом проверка на свойства тривиальна, кроме сравнимости. Интересно, можно ли еще как-то хитрее извратиться.

 Профиль  
                  
 
 
Сообщение22.03.2006, 18:54 
Супермодератор
Аватара пользователя


29/07/05
8248
Москва
Можно попробовать сразу строить разбиение на классы эквивалентности. Есть общий список элементов, у каждого есть флаг - вложен ли уже этот элемент в какой-либо класс или нет (а лучше - номер класса). Берем произвольный элемент и строим список тех, которые входят с ним в один класс. Для этого перечисляем все, которые с ним находятся в отношении. Далее перемещаемся к следующему, добавляем все эквивалентные ему (кроме тех, которые уже добавили). И так до тех пор, пока не дойдем до конца списка. Одновременно с добавлением проверяем, что элемент сравним со всеми предыдущими. Как только находим несоответствие - возвращаем ошибку.

Когда заканчиваем с очередным классом, находим первый неучтенный элемент и строим новые классы начиная с него.

 Профиль  
                  
 
 
Сообщение22.03.2006, 19:43 
Заслуженный участник
Аватара пользователя


17/10/05
3709
:evil:
Упорствуя в своих заблуждениях, я предложу метаидею. По прежнему делать матрицу, но для нее посмотреть технику разряженных матриц. Таковых много, книжки умные писаны. А если матрица не разряженная, то работая со списками больше памяти проиграешь (на накладные расходы), чем выиграешь.

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

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



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

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


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

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group