Бинарное отношение — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Исправления)
(Отмена правки 39364 участника Mtcomscxstart (обсуждение) Какой ещё счётчик Кнута?)
Строка 1: Строка 1:
−
'''Счетчик Кнута''' (англ. ''Knuth's Counter'') {{---}} структура данных, представленная избыточной двоичной системой счисления, где добавление единицы к числу выполняется за <tex>O(1)</tex>.
+
{{Определение
 +
|definition =
 +
'''Бинарным отношением''' (англ. ''binary relation'') <tex>R</tex> из множества <tex>A</tex> в множество <tex>B</tex> называется подмножество прямого произведения <tex>A</tex> и <tex>B</tex> и обозначается:
 +
<tex>R \subset A \times B</tex>.
 +
}}
  
−
Неотрицательное целое число <tex>N</tex> в ''избыточной двоичной системе счисления'' записывается в виде последовательности разрядов <tex>d_n d_{n-1} \dotsc  d_2 d_1</tex>, где <tex>n</tex> обозначает количество разрядов в числе, <tex>d_i</tex>  {{---}} <tex>i</tex>&ndash;й разряд числа <tex>(1 \leqslant i \leqslant n)</tex>, причем <tex>d_i \in \{0,1,2\}</tex> и <tex>\sum\limits_{i=1}^n d_i \cdot 2^i = N.
+
Часто используют инфиксную форму записи:
−
</tex>
+
<tex>aRb, \ \langle x, y \rangle\in R</tex>.
  
−
== Алгоритм ==
+
Если отношение определено на множестве <tex>A</tex>, то возможно следующее определение:
 +
{{Определение
 +
|definition =
 +
'''Бинарным''' (или '''двуместным''') '''отношением''' <tex>R</tex> на множестве <tex>A</tex> называется множество упорядоченных пар элементов этого множества.
 +
}}
 +
Примерами множеств с введёнными на них бинарными отношениями являются [[Ориентированный граф|графы]] и частично упорядоченные множества.
  
−
Оригинальный алгоритм предложен Кнутом, и состоит из двух правил:
+
== Свойства отношений ==
 +
Для <tex>R \subset A^2</tex> определены свойства:
 +
* [[Рефлексивное отношение|Рефлексивность]] (англ. ''reflexivity''): <tex>\mathcal {8} x \in A \  (xRx)</tex>;
 +
* [[Рефлексивное отношение|Антирефлексивность]] (англ. ''irreflexivity''): <tex>\mathcal {8} x \in A \  (\neg xRx)</tex>;
 +
* [[Симметричное отношение|Симметричность]] (англ. ''symmetry''): <tex>\mathcal {8} x,y \in A \  (xRy \Rightarrow yRx)</tex>;
 +
* [[Антисимметричное отношение|Антисимметричность]] (англ. ''antisymmetry''): <tex>\mathcal {8} x,y \in A \  (xRy \land yRx \Rightarrow x = y)</tex>;
 +
* [[Транзитивное отношение|Транзитивность]] (англ. ''transitivity''): <tex>\mathcal {8} x,y,z \in A \  (xRy \land yRz \Rightarrow xRz)</tex>;
 +
* Связность: <tex>\mathcal {8} x,y \in A \  (xRy \lor yRx)</tex>;
 +
* [[Антисимметричное отношение|Ассимметричность]] (англ. ''assymetric relation''): <tex>\mathcal {8} x,y \in A \  (xRy \Rightarrow \neg (yRx))</tex>.
  
−
# Найти младший разряд <tex>d_i</tex> равный <tex>2</tex> и, если таковой имеется, заменить последовательность <tex>d_{i+1}d_i</tex> на <tex>(d_{i+1}+1)0</tex>
+
== Виды отношений ==
−
# Заменить <tex>d_1</tex> на <tex>d_1+1</tex>.
+
Выделяются следующие виды отношений:
 +
* квазипорядка — рефлексивное транзитивное;
 +
* [[Отношение эквивалентности|эквивалентности]] — рефлексивное симметричное транзитивное;
 +
* [[Отношение порядка|частичного порядка]] — рефлексивное антисимметричное транзитивное;
 +
* [[Отношение порядка|строгого порядка]] — антирефлексивное антисимметричное транзитивное;
 +
* [[Отношение порядка|линейного порядка]] — полное антисимметричное транзитивное;
 +
* [[Отношение порядка|доминирования]] — антирефлексивное антисимметричное.
  
−
Чтобы достичь необходимой оценки и не выполнять каждый раз поиск для первого правила, можно хранить [[Список|односвязный список]] позиций двоек в числе. Тогда чтобы найти младший разряд равный двум нужно просто взять первый элемент списка. Также, непосредственно перед изменением значений разрядов в правилах необходимо выполнять следующее:
+
== Примеры отношений ==
 +
*Примеры [[Рефлексивное отношение|'''рефлексивных отношений''']]: равенство, одновременность, сходство.
 +
*Примеры [[Рефлексивное отношение|'''нерефлексивных отношений''']]: «заботиться о», «развлекать», «нервировать».
 +
*Примеры [[Транзитивное отношение|'''транзитивных отношений''']]: «больше», «меньше», «равно», «подобно», «выше», «севернее».
 +
*Примеры [[Симметричное отношение|'''симметричных отношений''']]: равенство (=), неравенство, отношение эквивалентности, подобия, одновременности, некоторые отношения родства (например, отношение братства).
 +
*Примеры [[Антисимметричное отношение|'''антисимметричных отношений''']]: больше, меньше, больше или равно.
 +
*Примеры '''асимметричных отношений''': отношение «больше» (>) и «меньше» (<).
  
−
# Если <tex>d_{i+1}=1</tex>, то заменить первый элемент списка с <tex>i</tex> на <tex>i+1</tex>, иначе удалить его.
+
== См. также ==
−
# Если <tex>d_1=1</tex>, то добавить в начало списка <tex>1</tex>.
+
* [[Композиция_отношений|Композиция отношений]]
  
−
Проблемой может оказаться появление двух последовательных двоек, при этом перое правило может породить
+
== Ссылки ==
−
тройку. То есть недопустима следующая ситуация <tex>\dotsc 22\dotsc \rightarrow \dotsc 30\dotsc</tex>.
+
* [http://ru.wikipedia.org/wiki/%D0%91%D0%B8%D0%BD%D0%B0%D1%80%D0%BD%D0%BE%D0%B5_%D0%BE%D1%82%D0%BD%D0%BE%D1%88%D0%B5%D0%BD%D0%B8%D0%B5 wikipedia.org — Бинарное отношение]
−
В свою очередь такая ситуация получается из этой <tex>\dotsc 212\dotsc \rightarrow \dotsc 220\dotsc</tex>.
+
* [http://ru.math.wikia.com/wiki/%D0%91%D0%B8%D0%BD%D0%B0%D1%80%D0%BD%D0%BE%D0%B5_%D0%BE%D1%82%D0%BD%D0%BE%D1%88%D0%B5%D0%BD%D0%B8%D0%B5 wikia.com - Бинарное отношение]
−
Причем количество единиц между двойками может быть любое, в итоге это приведет к появлению тройки.
+
* http://www.studfiles.ru/dir/cat14/subj266/file9092/view94463/page2.html
−
Однако если между любой парой двоек всегда будет находится хотя бы один
 
−
<tex>0</tex>, то такой ситуации не возникнет. Покажем, что что этот инвариант
 
−
поддерживается после инкремента, рассмотрев возможные ситуации:
 
−
# Число двоек не изменяется
 
−
## <tex>\dotsc 2\dotsc 0\dotsc 12\dotsc 0 \rightarrow \dotsc 2\dotsc 0\dotsc 20\dotsc 1</tex>.
 
−
## <tex>\dotsc 02\dotsc 1 \rightarrow \dotsc 10\dotsc 2</tex>.
 
−
## <tex>\dotsc 2\dotsc 02\dotsc 1 \rightarrow \dotsc 2\dotsc 10\dotsc 2</tex> (частный случай предыдущего).
 
−
## <tex> \dotsc 12 \rightarrow \dotsc 21</tex>.
 
−
# Пропадает одна двойка
 
−
## <tex> \dotsc 02\dotsc 0 \rightarrow \dotsc 10\dotsc 1</tex>.
 
−
## <tex> \dotsc 02 \rightarrow \dotsc 11</tex>.
 
−
# Появление новой двойки
 
−
## <tex>\dotsc 1 \rightarrow \dotsc 2</tex> (имеется в виду появление единственной двойки).
 
−
## <tex>\dotsc 12\dotsc 1 \rightarrow \dotsc 20\dotsc 2</tex>.
 
−
## <tex>\dotsc 2\dotsc 0\dotsc 12\dotsc 1 \rightarrow \dotsc 2\dotsc 0\dotsc 20\dotsc 2</tex> (частный случай предыдущего).
 
  
−
Таким образом мы видим, что 0 всегда сохраняется.
+
[[Категория:Дискретная математика и алгоритмы]]
−
 
+
[[Категория: Отношения ]]
−
В таблице можно увидеть как будет изменятья представление при применении данных правил десять раз к нулю (представления чисел от <tex>0</tex> до <tex>9</tex>):
 
−
 
 
−
{| class="wikitable"
 
−
|-
 
−
! Шаг
 
−
! Представление
 
−
|-
 
−
| 0
 
−
| 0
 
−
|-
 
−
| 1
 
−
| 1
 
−
|-
 
−
| 2
 
−
| 2
 
−
|-
 
−
| 3
 
−
| 11
 
−
|-
 
−
| 4
 
−
| 12
 
−
|-
 
−
| 5
 
−
| 21
 
−
|-
 
−
| 6
 
−
| 102
 
−
|-
 
−
| 7
 
−
| 111
 
−
|-
 
−
| 8
 
−
| 112
 
−
|-
 
−
| 9
 
−
| 121
 
−
|}
 
−
 
 
−
== Обобщение на системы с произвольным основанием ==
 
−
 
 
−
В общем случае подобные счётчики называются ''<tex>b</tex>-ричными избыточными счетчиками'' (''ИС''), которые похожи на счетчик Кнута,
 
−
но основание системы может быть произвольным, то есть <tex>d_i \in \{0,1,\dotsc ,b\}</tex> и <tex>\sum\limits_{i=1}^n d_i \cdot b^i = N</tex>
 
−
, где <tex>b</tex>  {{---}} основание. Такие счетчики позволяют прибавить единицу к любому разряду, то есть увеличить число на <tex>b^i</tex>
 
−
за <tex>O(1)</tex>
 
−
Назовем такое представление ''регулярным'', если между дувумя разрядами равными <tex>b</tex> есть хотя бы один разряд отличный от
 
−
<tex>b-1</tex>.
 
−
Операция ''исправления'' (''fix'') разряда <tex>d_i=b</tex> в регулярной <tex>b</tex>-ричного
 
−
счетчика <tex>d</tex> увеличивает <tex>d_{i+1}</tex> на <tex>1</tex> и устанавливает
 
−
<tex>d_i</tex> в <tex>0</tex>, образуая новый регулярный счетчик, представляющий то же число,
 
−
что и <tex>d</tex>.
 
−
Чтобы добавить <tex>1</tex> к разряду <tex>d_i</tex> регулярного ИС <tex>d</tex>,
 
−
нужно сделать следующее:
 
−
# Если <tex>d_i=b</tex>, исправить <tex>d_i</tex>.
 
−
# Если <tex>d_i=b-1</tex> и самый младший значащий разряд <tex>d_j</tex>, такой, что <tex>j>i</tex> и <tex>d_j \ne b-1</tex>, равен <tex>b</tex> (т.е. <tex>d_j=b</tex>), применить операцию исправления к разряду <tex>d_j</tex>.
 
−
# Добавить 1 к <tex>d_i</tex>.
 
−
# Если <tex>d_i=b</tex>, исправить <tex>d_i</tex>.
 
−
 
 
−
Для реализации данной схемы, мы используем односвязный список разрядов от младших
 
−
к старшим. В дополнение каждый разряд <tex>d_i</tex> равный <tex>b-1</tex>
 
−
будет иметь указатель на самый младший разряд <tex>d_j</tex>, такой,
 
−
что <tex>j>i</tex> и <tex>d_j \ne b-1</tex>, если он равен <tex>b</tex>,
 
−
иначе этот указатель будет на произвольный разряд <tex>d_j</tex> (<tex>j>i</tex>).
 
−
Теперь, во время увеличения разряда <tex>d_i</tex> на 1, будем проверять
 
−
разряд по указателю вперед (п. 2).
 
−
 
 
−
Такое представление позволяет увеличиать произвольный разряд за константное
 
−
время. Обновление указателя вперед происходит следующим образом: когда <tex>d_{i+}</tex> становится равен <tex>b-1</tex> при исправлении разряда <tex>d_{i-1}</tex>, устанавливаем указатель вперед разряда <tex>d_{i}</tex> на <tex>d_{i+1}</tex>, если <tex>d_{i+1}=b</tex>, либо копируем указатель вперед из <tex>d_{i+1}</tex> в <tex>d_{i}</tex>, если <tex>d_{i+1}=b-1</tex>.
 
−
При собственно добавлении единицы к разряду <tex>d_i</tex>, также необходимо обновлять его указатель вперед аналогичным образом,
 
−
если этот разряд становится равен <tex>b-1</tex>.
 
−
 
 
−
== Источники информации ==
 
−
* H. Kaplan и R. E. Tarjan. New heap data structures. 1998
 
−
* M. J. Clancy и D. E. Knuth. A programming and problem-solving seminar. Technical Report STAN-CS-77-606, Department of Computer Sciencr, Stanford University, Palo Alto, 1977.
 
−
* G. S. Brodal. Worst case priority queues. ''Proc. 7th annual ACM-SIAM Symposium on Discrete Algorithms (SODA 96)'', страницы 52-58. ACM Press, 1996.
 
−
* H. Kaplan и R. E. Tarjan. Purely functional representations of catenable sorted lists. ''Proceedings of the 28th Annual ACM Symposium of Computing'', страницы 202-211. ACM Press, 1996
 
−
* http://www.cphstl.dk/Paper/Numeral-systems/mfcs-13.pdf
 
−
* [[Амортизационный анализ]]
 
−
* [[Представление целых чисел: прямой код, код со сдвигом, дополнительный код]]
 
−
 
 
−
[[Категория: Дискретная математика и алгоритмы]]
 
−
[[Категория: Амортизационный анализ]]
 

Версия 00:04, 11 июля 2014

Определение:
Бинарным отношением (англ. binary relation) [math]R[/math] из множества [math]A[/math] в множество [math]B[/math] называется подмножество прямого произведения [math]A[/math] и [math]B[/math] и обозначается: [math]R \subset A \times B[/math].


Часто используют инфиксную форму записи: [math]aRb, \ \langle x, y \rangle\in R[/math].

Если отношение определено на множестве [math]A[/math], то возможно следующее определение:

Определение:
Бинарным (или двуместным) отношением [math]R[/math] на множестве [math]A[/math] называется множество упорядоченных пар элементов этого множества.

Примерами множеств с введёнными на них бинарными отношениями являются графы и частично упорядоченные множества.

Свойства отношений

Для [math]R \subset A^2[/math] определены свойства:

Виды отношений

Выделяются следующие виды отношений:

Примеры отношений

См. также

Ссылки

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Бинарное_отношение&oldid=39851»