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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Исправления)
Строка 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>aRb, \ \langle x, y \rangle\in R</tex>.
+
</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>.
  
== Ссылки ==
+
Проблемой может оказаться появление двух последовательных двоек, при этом перое правило может породить
* [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 22\dotsc \rightarrow \dotsc 30\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 - Бинарное отношение]
+
В свою очередь такая ситуация получается из этой <tex>\dotsc 212\dotsc \rightarrow \dotsc 220\dotsc</tex>.
* 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
 +
* [[Амортизационный анализ]]
 +
* [[Представление целых чисел: прямой код, код со сдвигом, дополнительный код]]
 +
 
 +
[[Категория: Дискретная математика и алгоритмы]]
 +
[[Категория: Амортизационный анализ]]

Версия 23:47, 15 июня 2014

Счетчик Кнута (англ. Knuth's Counter) — структура данных, представленная избыточной двоичной системой счисления, где добавление единицы к числу выполняется за [math]O(1)[/math].

Неотрицательное целое число [math]N[/math] в избыточной двоичной системе счисления записывается в виде последовательности разрядов [math]d_n d_{n-1} \dotsc d_2 d_1[/math], где [math]n[/math] обозначает количество разрядов в числе, [math]d_i[/math][math]i[/math]–й разряд числа [math](1 \leqslant i \leqslant n)[/math], причем [math]d_i \in \{0,1,2\}[/math] и [math]\sum\limits_{i=1}^n d_i \cdot 2^i = N. [/math]

Алгоритм

Оригинальный алгоритм предложен Кнутом, и состоит из двух правил:

  1. Найти младший разряд [math]d_i[/math] равный [math]2[/math] и, если таковой имеется, заменить последовательность [math]d_{i+1}d_i[/math] на [math](d_{i+1}+1)0[/math]
  2. Заменить [math]d_1[/math] на [math]d_1+1[/math].

Чтобы достичь необходимой оценки и не выполнять каждый раз поиск для первого правила, можно хранить односвязный список позиций двоек в числе. Тогда чтобы найти младший разряд равный двум нужно просто взять первый элемент списка. Также, непосредственно перед изменением значений разрядов в правилах необходимо выполнять следующее:

  1. Если [math]d_{i+1}=1[/math], то заменить первый элемент списка с [math]i[/math] на [math]i+1[/math], иначе удалить его.
  2. Если [math]d_1=1[/math], то добавить в начало списка [math]1[/math].

Проблемой может оказаться появление двух последовательных двоек, при этом перое правило может породить тройку. То есть недопустима следующая ситуация [math]\dotsc 22\dotsc \rightarrow \dotsc 30\dotsc[/math]. В свою очередь такая ситуация получается из этой [math]\dotsc 212\dotsc \rightarrow \dotsc 220\dotsc[/math]. Причем количество единиц между двойками может быть любое, в итоге это приведет к появлению тройки. Однако если между любой парой двоек всегда будет находится хотя бы один [math]0[/math], то такой ситуации не возникнет. Покажем, что что этот инвариант поддерживается после инкремента, рассмотрев возможные ситуации:

  1. Число двоек не изменяется
    1. [math]\dotsc 2\dotsc 0\dotsc 12\dotsc 0 \rightarrow \dotsc 2\dotsc 0\dotsc 20\dotsc 1[/math].
    2. [math]\dotsc 02\dotsc 1 \rightarrow \dotsc 10\dotsc 2[/math].
    3. [math]\dotsc 2\dotsc 02\dotsc 1 \rightarrow \dotsc 2\dotsc 10\dotsc 2[/math] (частный случай предыдущего).
    4. [math] \dotsc 12 \rightarrow \dotsc 21[/math].
  2. Пропадает одна двойка
    1. [math] \dotsc 02\dotsc 0 \rightarrow \dotsc 10\dotsc 1[/math].
    2. [math] \dotsc 02 \rightarrow \dotsc 11[/math].
  3. Появление новой двойки
    1. [math]\dotsc 1 \rightarrow \dotsc 2[/math] (имеется в виду появление единственной двойки).
    2. [math]\dotsc 12\dotsc 1 \rightarrow \dotsc 20\dotsc 2[/math].
    3. [math]\dotsc 2\dotsc 0\dotsc 12\dotsc 1 \rightarrow \dotsc 2\dotsc 0\dotsc 20\dotsc 2[/math] (частный случай предыдущего).

Таким образом мы видим, что 0 всегда сохраняется.

В таблице можно увидеть как будет изменятья представление при применении данных правил десять раз к нулю (представления чисел от [math]0[/math] до [math]9[/math]):

Шаг Представление
0 0
1 1
2 2
3 11
4 12
5 21
6 102
7 111
8 112
9 121

Обобщение на системы с произвольным основанием

В общем случае подобные счётчики называются [math]b[/math]-ричными избыточными счетчиками (ИС), которые похожи на счетчик Кнута, но основание системы может быть произвольным, то есть [math]d_i \in \{0,1,\dotsc ,b\}[/math] и [math]\sum\limits_{i=1}^n d_i \cdot b^i = N[/math] , где [math]b[/math] — основание. Такие счетчики позволяют прибавить единицу к любому разряду, то есть увеличить число на [math]b^i[/math] за [math]O(1)[/math] Назовем такое представление регулярным, если между дувумя разрядами равными [math]b[/math] есть хотя бы один разряд отличный от [math]b-1[/math]. Операция исправления (fix) разряда [math]d_i=b[/math] в регулярной [math]b[/math]-ричного счетчика [math]d[/math] увеличивает [math]d_{i+1}[/math] на [math]1[/math] и устанавливает [math]d_i[/math] в [math]0[/math], образуая новый регулярный счетчик, представляющий то же число, что и [math]d[/math]. Чтобы добавить [math]1[/math] к разряду [math]d_i[/math] регулярного ИС [math]d[/math], нужно сделать следующее:

  1. Если [math]d_i=b[/math], исправить [math]d_i[/math].
  2. Если [math]d_i=b-1[/math] и самый младший значащий разряд [math]d_j[/math], такой, что [math]j\gt i[/math] и [math]d_j \ne b-1[/math], равен [math]b[/math] (т.е. [math]d_j=b[/math]), применить операцию исправления к разряду [math]d_j[/math].
  3. Добавить 1 к [math]d_i[/math].
  4. Если [math]d_i=b[/math], исправить [math]d_i[/math].

Для реализации данной схемы, мы используем односвязный список разрядов от младших к старшим. В дополнение каждый разряд [math]d_i[/math] равный [math]b-1[/math] будет иметь указатель на самый младший разряд [math]d_j[/math], такой, что [math]j\gt i[/math] и [math]d_j \ne b-1[/math], если он равен [math]b[/math], иначе этот указатель будет на произвольный разряд [math]d_j[/math] ([math]j\gt i[/math]). Теперь, во время увеличения разряда [math]d_i[/math] на 1, будем проверять разряд по указателю вперед (п. 2).

Такое представление позволяет увеличиать произвольный разряд за константное время. Обновление указателя вперед происходит следующим образом: когда [math]d_{i+}[/math] становится равен [math]b-1[/math] при исправлении разряда [math]d_{i-1}[/math], устанавливаем указатель вперед разряда [math]d_{i}[/math] на [math]d_{i+1}[/math], если [math]d_{i+1}=b[/math], либо копируем указатель вперед из [math]d_{i+1}[/math] в [math]d_{i}[/math], если [math]d_{i+1}=b-1[/math]. При собственно добавлении единицы к разряду [math]d_i[/math], также необходимо обновлять его указатель вперед аналогичным образом, если этот разряд становится равен [math]b-1[/math].

Источники информации