Изменения

{{Определение|definition ='''Бинарным отношениемСчетчик Кнута''' (англ. ''binary relationKnuth's Counter'') {{---}} структура данных, представленная избыточной двоичной системой счисления, где добавление единицы к числу выполняется за <tex>R</tex> из множества <tex>A</tex> в множество <tex>B</tex> называется подмножество прямого произведения <tex>A</tex> и <tex>B</tex> и обозначается:<tex>R \subset A \times BO(1)</tex>.}}

Часто используют инфиксную форму записи:Неотрицательное целое число <tex>N</tex> в ''избыточной двоичной системе счисления'' записывается в виде последовательности разрядов <tex>d_n d_{n-1} \dotsc d_2 d_1</tex>, где <tex>n</tex>aRbобозначает количество разрядов в числе, <tex>d_i</tex> {{---}} <tex>i</tex>&ndash;й разряд числа <tex>(1 \ leqslant i \langle xleqslant n)</tex>, y причем <tex>d_i \in \rangle{0,1,2\in 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>\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:тройку. То есть недопустима следующая ситуация <tex>\dotsc 22\dotsc \rightarrow \dotsc 30\dotsc</tex>.В свою очередь такая ситуация получается из этой <tex>\dotsc 212\dotsc \rightarrow \dotsc 220\dotsc</rutex>.wikipediaПричем количество единиц между двойками может быть любое, в итоге это приведет к появлению тройки.org/wikiОднако если между любой парой двоек всегда будет находится хотя бы один<tex>0</%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 wikipediatex>, то такой ситуации не возникнет.org — Бинарное отношение]Покажем, что что этот инвариант* [httpподдерживается после инкремента, рассмотрев возможные ситуации:# Число двоек не изменяется## <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</rutex>.math## <tex>\dotsc 2\dotsc 02\dotsc 1 \rightarrow \dotsc 2\dotsc 10\dotsc 2</tex> (частный случай предыдущего).wikia## <tex> \dotsc 12 \rightarrow \dotsc 21</tex>.com# Пропадает одна двойка## <tex> \dotsc 02\dotsc 0 \rightarrow \dotsc 10\dotsc 1</wikitex>.## <tex> \dotsc 02 \rightarrow \dotsc 11</%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 wikiatex>.com - Бинарное отношение]* http:# Появление новой двойки## <tex>\dotsc 1 \rightarrow \dotsc 2</tex> (имеется в виду появление единственной двойки).## <tex>\dotsc 12\dotsc 1 \rightarrow \dotsc 20\dotsc 2</wwwtex>.studfiles.ru/dir/cat14/subj266/file9092/view94463## <tex>\dotsc 2\dotsc 0\dotsc 12\dotsc 1 \rightarrow \dotsc 2\dotsc 0\dotsc 20\dotsc 2</page2tex> (частный случай предыдущего).html

Таким образом мы видим, что 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* [[Амортизационный анализ]]* [[Представление целых чисел: прямой код, код со сдвигом, дополнительный код]] [[Категория:Дискретная математика и алгоритмы]][[Категория: Отношения Амортизационный анализ]]