Изменения

Перейти к: навигация, поиск

Бинарное отношение

3468 байт убрано, 13:08, 7 февраля 2018
м
Свойства отношений
{{Определение|definition ='''Счетчик КнутаБинарным отношением''' (англ. ''Knuth's Counterbinary relation'') {{---}} структура данных, представленная избыточной двоичной системой счисления, где добавление единицы к числу выполняется за <tex>O(1)R</tex> из множества <math>A</math> в множество <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>aRb, где <tex>n</tex> обозначает количество разрядов в числе, <tex>d_i</tex> {{---}} <tex>i</tex>&ndash;й разряд числа <tex>(1 \leqslant i \leqslant n)</tex>langle x, причем <tex>d_i y \rangle\in \{0,1,2\}R</tex> и <tex>\sum\limits_{i=1}^n d_i \cdot 2^i = N.</tex>
Если отношение определено на множестве <tex>A</tex>, то возможно следующее определение:{{Определение|definition == Алгоритм =='''Бинарным''' (или '''двуместным''') '''отношением''' <tex>R</tex> на множестве <tex>A</tex> называется множество упорядоченных пар элементов этого множества.}}Примерами множеств с введёнными на них бинарными отношениями являются [[Ориентированный граф|графы]] и частично упорядоченные множества.
Оригинальный алгоритм предложен Кнутом== Свойства отношений ==Для <tex>R \subset A^2</tex> определены свойства:* [[Рефлексивное отношение|Рефлексивность]] (англ. ''reflexivity''): <tex>\forall x \in A \ (xRx)</tex>;* [[Рефлексивное отношение|Антирефлексивность]] (англ. ''irreflexivity''): <tex>\forall x \in A \ \neg(xRx)</tex>;* [[Симметричное отношение|Симметричность]] (англ. ''symmetry''): <tex>\forall x,y \in A \ (xRy \Rightarrow yRx)</tex>;* [[Антисимметричное отношение|Антисимметричность]] (англ. ''antisymmetry''): <tex>\forall x,y \in A \ (xRy \land yRx \Rightarrow x = y)</tex>;* [[Транзитивное отношение|Транзитивность]] (англ. ''transitivity''): <tex>\forall x,y,z \in A \ (xRy \land yRz \Rightarrow xRz)</tex>;* Связность (англ. ''connectivity''): <tex>\forall x, и состоит из двух правилy \in A \ (xRy \lor yRx)</tex>;* [[Антисимметричное отношение|Ассимметричность]] (англ. ''assymetric relation''):<tex>\forall x,y \in A \ (xRy \Rightarrow \neg (yRx))</tex>.
# Найти младший разряд <tex>d_i</tex> равный <tex>2</tex> и, если таковой имеется, заменить последовательность <tex>d_{i+1}d_i</tex> на <tex>== Виды отношений ==Выделяются следующие виды отношений:* квазипорядка (англ. ''quasiorder'') — рефлексивное транзитивное;* [[Отношение эквивалентности|эквивалентности]] (англ. ''equivalence'') — рефлексивное симметричное транзитивное;* [[Отношение порядка|частичного порядка]] (англ. ''partial order'') — рефлексивное антисимметричное транзитивное;* [[Отношение порядка|строгого порядка]] (англ. ''strict order'') — антирефлексивное антисимметричное транзитивное;* [[Отношение порядка|линейного порядка]] (d_{i+1}+1англ. ''total order'')0</tex>— полное антисимметричное транзитивное;# Заменить <tex>d_1</tex> на <tex>d_1+1</tex>* [[Отношение порядка|доминирования]] (англ. ''dominance'') — антирефлексивное антисимметричное.
Чтобы достичь необходимой оценки и не выполнять каждый раз поиск для первого правила== Примеры отношений ==*Примеры [[Рефлексивное отношение|'''рефлексивных отношений''']]: равенство, одновременность, сходство.*Примеры [[Рефлексивное отношение|'''нерефлексивных отношений''']]: «заботиться о», «развлекать», можно хранить «нервировать».*Примеры [[СписокТранзитивное отношение|односвязный список'''транзитивных отношений''']] позиций двоек в числе: «больше», «меньше», «равно», «подобно», «выше», «севернее». Тогда чтобы найти младший разряд равный двум нужно просто взять первый элемент списка*Примеры [[Симметричное отношение|'''симметричных отношений''']]: равенство (=), неравенство, отношение эквивалентности, подобия, одновременности, некоторые отношения родства (например, отношение братства). Также*Примеры [[Антисимметричное отношение|'''антисимметричных отношений''']]: больше, непосредственно перед изменением значений разрядов в правилах необходимо выполнять следующееменьше, больше или равно.*Примеры '''асимметричных отношений''':отношение «больше» (>) и «меньше» (<).
# Если <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>.В свою очередь такая ситуация получается из этой <tex>\dotsc 212\dotsc \rightarrow \dotsc 220\dotsc</tex>.Причем количество единиц между двойками может быть любое, в итоге это приведет к появлению тройки.Однако если между любой парой двоек всегда будет находится хотя бы один<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{{---}} Дискретная математика для программистов: Учебник для вузов. Tarjan3-е изд. New heap data structures. 1998* M. J. Clancy и D. E. Knuth. A programming and problem{{---solving seminar}} СПБ. Technical Report STAN: Питер, 2009 {{-CS-77-606, Department of Computer Sciencr, Stanford University, Palo Alto, 1977}} 50 с.* G[http://ru. Swikipedia. Brodal. Worst case priority queues. ''Proc. 7th annual ACMorg/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 Википедия {{-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://wwwru.cphstlmath.dkwikia.com/Paperwiki/Numeral%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 {{--systems/mfcs-13.pdf* [[Амортизационный анализ]}} Бинарное отношение]* [[Представление целых чиселhttps://studfiles.net/preview/952560/page: прямой код, код со сдвигом, дополнительный код]4/ Studfiles {{---}} Лекции по дискретной математике. Отношения и их свойства]
[[Категория: Дискретная математика и алгоритмы]][[Категория: Амортизационный анализОтношения ]]

Навигация