Коды антигрея - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:03:45Z

rollbackEdits.php mass rollback

185.243.218.46 в 06:38, 1 сентября 2022

2022-09-01T06:38:17Z

80.239.140.98: /* Псевдокод */

2018-09-13T07:14:55Z

‎Псевдокод

Oxygen3 в 20:54, 21 ноября 2014

2014-11-21T20:54:33Z

Oxygen3 в 20:50, 21 ноября 2014

2014-11-21T20:50:49Z

Oxygen3 в 20:01, 21 ноября 2014

2014-11-21T20:01:20Z

Внесённые изменения

Oxygen3 в 12:16, 18 ноября 2014

2014-11-18T12:16:44Z

Savelin: /* Двоичный код антигрея */

2013-12-11T19:22:50Z

‎Двоичный код антигрея

Savelin: /* Доказательство корректности алгоритма */

2013-12-11T19:05:01Z

‎Доказательство корректности алгоритма

Dgerasimov в 10:35, 16 ноября 2013

2013-11-16T10:35:08Z

← Предыдущая		Версия 16:03, 4 сентября 2022
Строка 1:		Строка 1:
−	~~{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"~~
−	\|+
−	~~\|-align="center"~~
−	~~\|'''НЕТ ВОЙНЕ'''~~
−	~~\|-style="font-size: 16px;"~~
−	\|
−	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
−
−	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
−
−	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
−
−	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
−
−	~~''Антивоенный комитет России''~~
−	~~\|-style="font-size: 16px;"~~
−	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
−	~~\|-style="font-size: 16px;"~~
−	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
−	\|}
−
	{{Определение		{{Определение
	\|definition=		\|definition=

← Предыдущая		Версия 06:38, 1 сентября 2022
Строка 1:		Строка 1:
		+	{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
		+	\|+
		+	\|-align="center"
		+	\|'''НЕТ ВОЙНЕ'''
		+	\|-style="font-size: 16px;"
		+	\|
		+	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
		+
		+	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
		+
		+	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
		+
		+	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
		+
		+	''Антивоенный комитет России''
		+	\|-style="font-size: 16px;"
		+	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
		+	\|-style="font-size: 16px;"
		+	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
		+	\|}
		+
	{{Определение		{{Определение
	\|definition=		\|definition=

@@ Строка 44: / Строка 44: @@
 === Псевдокод ===
    '''function''' genBinAntiGray(n: '''int'''):
      '''for''' i = 1 '''to''' 2 ** (n - 1)
@@ Строка 51: / Строка 50: @@
        inverseBits(v)
        print(v)
-</code>
 === Доказательство корректности алгоритма ===

@@ Строка 69: / Строка 69: @@
 {{Определение
 |definition=
-'''Троичный код антигрея''' (англ. ''Trinary Anti-Gray Code'') {{---}} такое упорядочивание троичных векторов, что соседние отличаются во всех разрядах.
+'''Троичный код антигрея''' (англ. ''Ternary Anti-Gray Code'') {{---}} такое упорядочивание троичных векторов, что соседние отличаются во всех разрядах.
 }}
 В отличие от двоичного кода антигрея, здесь мы не сталкиваемся с проблемой однозначности "соседа" и можем привести такой код, соседние элементы которого будут отличаться во всех разрядах.
@@ Строка 84: / Строка 84: @@
    '''function''' genTernAntiGray(n: '''int'''):
      '''for''' v = <000..0> '''to''' <022..2> <span style="color:Green">// троичные вектора длины <tex>n</tex> </span>
-       '''for'''i = 0 '''to''' 2
+       '''for''' i = 0 '''to''' 2
          print(v)
          digitCircleShift(v)

@@ Строка 46: / Строка 46: @@
 <code>
    '''function''' genBinAntiGray(n: '''int'''):
-     '''for''' i = 1 to 2 ** (n - 1)
+     '''for''' i = 1 '''to''' 2 ** (n - 1)
        v = getMirrorGray(i, n)
        print(v)
@@ Строка 56: / Строка 56: @@
 Обозначим за <tex>G_i</tex> — <tex>i</tex>-ый вектор в зеркальном коде Грея, <tex>\overline G_i</tex> — его инверсию.
 Тогда вектора будут располагаться в таком порядке:
-:... <br>
+:<tex>\dots</tex> <br>
 :<tex>G_i</tex> <br>
 :<tex>\overline G_i</tex> <br>
@@ Строка 62: / Строка 62: @@
 :<tex>\overline G_{i+1}</tex> <br>
 :<tex>G_{i+2}</tex> <br>
-:...
+:<tex>\dots</tex>
 <tex>G_i</tex> и <tex>\overline G_i</tex> отличаются во всех битах. <br>
 Если <tex>G_i</tex> и <tex>G_{i+1}</tex> отличаются в <tex>k</tex>-ом бите, то инверсия <tex>G_i</tex> совпадает с <tex>G_{i+1}</tex> только в <tex>k</tex>-ом бите. То есть <tex>\overline G_i</tex> и <tex>G_{i+1}</tex> отличаются во всех позициях, кроме <tex>k</tex>-ой.
@@ Строка 69: / Строка 69: @@
 {{Определение
 |definition=
-'''Троичный код антигрея''' {{---}} такое упорядочивание троичных векторов, что соседние отличаются во всех разрядах.
+'''Троичный код антигрея''' (англ. ''Trinary Anti-Gray Code'') {{---}} такое упорядочивание троичных векторов, что соседние отличаются во всех разрядах.
 }}
 В отличие от двоичного кода антигрея, здесь мы не сталкиваемся с проблемой однозначности "соседа" и можем привести такой код, соседние элементы которого будут отличаться во всех разрядах.
@@ Строка 75: / Строка 75: @@
 === Алгоритм генерации ===
-Упорядочим все троичные вектора лексикографически. Тогда для первых <tex>3^{n-1}</tex> векторов будем выводить сначала сам этот вектор, потом <tex>2</tex> его поразрядных циклических сдвига (каждый отдельный бит увеличиваем на 1).
+Упорядочим все троичные вектора лексикографически. Тогда для первых <tex>3^{n-1}</tex> векторов будем выводить сначала сам этот вектор, потом <tex>2</tex> его поразрядных циклических сдвига (каждый отдельный бит увеличиваем на <tex>1</tex>).
 <br>Например, если мы имеем вектор <tex>021</tex>, то вы выведем: <tex>021</tex>, <tex>102</tex>, <tex>210</tex>.
@@ Строка 83: / Строка 83: @@
 <code>
    '''function''' genTernAntiGray(n: '''int'''):
-     '''for''' v = <000..0> to <022..2> // троицчные вектора длины n
+     '''for''' v = <000..0> '''to''' <022..2> <span style="color:Green">// троичные вектора длины <tex>n</tex> </span>
-       '''for'''int i = 0 to 2
+       '''for'''i = 0 '''to''' 2
          print(v)
          digitCircleShift(v)
@@ Строка 136: / Строка 136: @@
 Обозначим <tex>i</tex>-ый троичный вектор как <tex>G_i^0</tex>, его первый и второй циклический сдвиги как <tex>G_i^1</tex> и <tex>G_i^2</tex> соответственно. Получаем вектора в следующем порядке:
-:... <br>
+:<tex>\dots</tex> <br>
 :<tex>G_i^0</tex> <br>
 :<tex>G_i^1</tex> <br>
 :<tex>G_i^2</tex> <br>
 :<tex>G_{i+1}^0</tex> <br>
-:...
+:<tex>\dots</tex>
 <tex >G_i^0</tex> и <tex>G_i^1</tex>, равно как <tex>G_i^1</tex> и <tex>G_i^2</tex>, отличаются во всех битах. <br>
 Если говорить о векторах как о троичных числах, то <tex>G_{i+1}^0</tex> получено из <tex>G_i^0</tex> прибавлением единицы, это значит, что у <tex>G_{i+1}^0</tex> несколько разрядов справа на единицу больше (по модулю <tex>3</tex>), чем у <tex>G_i^0</tex> (по правилам сложения в столбик). С другой стороны <tex>G_{i}^2</tex> получено из <tex>G_{i}^0</tex> двумя циклическими сдвигами вперёд, что равносильно одному циклическому сдвигу назад. Таким образом, в числе <tex>G_{i+1}^0</tex> некоторые биты такие же, как в <tex>G_{i}^0</tex>, остальные на единицу больше; в числе <tex>G_{i}^2</tex> все биты на один меньше по сравнению с <tex>G_{i}^0</tex>, значит <tex>G_{i}^2</tex> и <tex>G_{i+1}^0</tex> различны во всех битах.

@@ Строка 1: / Строка 1: @@
 {{Определение
 |definition=
-'''Код антигрея (Anti-Gray Code)''' {{---}} такое упорядочивание <tex>k</tex>-ичных векторов, что [[расстояние Хэмминга]] между двумя соседними векторами максимально.
+'''Код антигрея''' (англ. ''Anti-Gray Code'') {{---}} такое упорядочивание <tex>k</tex>-ичных векторов, что [[расстояние Хэмминга]] между двумя соседними векторами максимально.
 }}
 Код антигрея может использоваться для обнаружения неисправностей в устройстве при переходе в соседнее состояние. Часто используется в приборах, устанавливающихся на улице. Такое кодирование позволяет вовремя выявить поломку или какое-то загрязнение и своевременно устранить неисправность.
@@ Строка 11: / Строка 10: @@
 '''Двоичный код антигрея''' {{---}} такое упорядочивание двоичных векторов длины <tex>n</tex>, что соседние отличаются не менее, чем в <tex>n-1</tex> битах.
 }}
 Заметим: упорядочивание векторов такое, что соседние отличаются во всех битах, возможно только для <tex>n = 1</tex>. Это объясняется тем, что для двоичного вектора существует ровно один вектор, отличающийся во всех битах, а в последовательности, где <tex>n > 1</tex>, таких векторов должно быть два.
@@ Строка 47: / Строка 45: @@
 === Псевдокод ===
-   genBinAntiGray(n)
+   function genBinAntiGray(n: '''int''')
-     for i = 1 to 2^(n-1)
+     '''for''' i = 1 to 2**(n-1)
        v = getMirrorGray(i, n)
        print(v)
@@ Строка 56: / Строка 54: @@
 === Доказательство корректности алгоритма ===
-Обозначим за <tex dpi = "140">G_i</tex> — <tex>i</tex>-ый вектор в зеркальном коде Грея, <tex dpi = "140">\overline G_i</tex> — его инверсию.
+Обозначим за <tex>G_i</tex> — <tex>i</tex>-ый вектор в зеркальном коде Грея, <tex>\overline G_i</tex> — его инверсию.
-Тогда вектора будут располагаться в таком порядке:
+Тогда вектора будут располагаться в таком порядке:<br>
-  ... <br>
+*... <br>
-  <tex dpi="120">G_i</tex> <br>
+*<tex>G_i</tex> <br>
-  <tex dpi="120">\overline G_i</tex> <br>
+*<tex>\overline G_i</tex> <br>
-  <tex dpi="120">G_{i+1}</tex> <br>
+*<tex>G_{i+1}</tex> <br>
-  <tex dpi="120">\overline G_{i+1}</tex> <br>
+*<tex>\overline G_{i+1}</tex> <br>
-  <tex dpi="120">G_{i+2}</tex> <br>
+*<tex>G_{i+2}</tex> <br>
-  ...
+*...<br>
-* <tex dpi = "140">G_i</tex> и <tex dpi = "140">\overline G_i</tex> отличаются во всех битах.
+<tex>G_i</tex> и <tex>\overline G_i</tex> отличаются во всех битах. <br>
-* Если <tex dpi = "140">G_i</tex> и <tex dpi = "140">G_{i+1}</tex> отличаются в <tex>k</tex>-ом бите, то инверсия <tex dpi = "140">G_i</tex> совпадает с <tex dpi = "140">G_{i+1}</tex> только в <tex>k</tex>-ом бите. То есть <tex dpi = "140">\overline G_i</tex> и <tex dpi = "140">G_{i+1}</tex> отличаются во всех позициях, кроме <tex>k</tex>-ой.
+Если <tex>G_i</tex> и <tex>G_{i+1}</tex> отличаются в <tex>k</tex>-ом бите, то инверсия <tex>G_i</tex> совпадает с <tex>G_{i+1}</tex> только в <tex>k</tex>-ом бите. То есть <tex>\overline G_i</tex> и <tex>G_{i+1}</tex> отличаются во всех позициях, кроме <tex>k</tex>-ой.
 == Троичный код антигрея ==
@@ Строка 73: / Строка 71: @@
 '''Троичный код антигрея''' {{---}} такое упорядочивание троичных векторов, что соседние отличаются во всех разрядах.
 }}
 В отличие от двоичного кода антигрея, здесь мы не сталкиваемся с проблемой однозначности "соседа" и можем привести такой код, соседние элементы которого будут отличаться во всех разрядах.
@@ Строка 104: / Строка 101: @@
 === Алгоритм генерации ===
-Упорядочим все троичные вектора лексикографически. Тогда для первых <tex>3^{n-1}</tex> векторов будем выводить все его поразрядные циклические сдвиги.
+Упорядочим все троичные вектора лексикографически. Тогда для первых <tex>3^{n-1}</tex> векторов будем выводить сначала сам этот вектор, потом 2 его поразрядных циклических сдвига.
 Утверждается, что выполняя эти действия мы получим троичный код антигрея.
@@ Строка 110: / Строка 108: @@
 === Псевдокод ===
-   genTernAntiGray(n)
+   function genTernAntiGray(n: '''int''')
-     for v = <000..0> to <022..2>
+     '''for''' v = <000..0> to <022..2>
        digitCircleShift(v)
-       while(v[0] != 0)
+       '''while'''(v[0] != 0)
          print(v)
          digitCircleShift(v)
@@ Строка 121: / Строка 119: @@
 === Доказательство корректности алгоритма ===
-Обозначим <tex>i</tex>-ый троичный вектор как <tex dpi="140">G_i^0</tex>, его первый и второй циклический сдвиги как <tex dpi="140" >G_i^1</tex> и <tex dpi="140">G_i^2</tex> соответственно. Получаем вектора в следующем порядке:
+Обозначим <tex>i</tex>-ый троичный вектор как <tex>G_i^0</tex>, его первый и второй циклический сдвиги как <tex>G_i^1</tex> и <tex>G_i^2</tex> соответственно. Получаем вектора в следующем порядке:
-  ... <br>
+*... <br>
-  <tex dpi="120">G_i^0</tex> <br>
+*<tex>G_i^0</tex> <br>
-  <tex dpi="120">G_i^1</tex> <br>
+*<tex>G_i^1</tex> <br>
-  <tex dpi="120">G_i^2</tex> <br>
+*<tex>G_i^2</tex> <br>
-  <tex dpi="120">G_{i+1}^0</tex> <br>
+*<tex>G_{i+1}^0</tex> <br>
-  ...
+*...
-* <tex  dpi = "140">G_i^0</tex> и <tex dpi = "140">G_i^1</tex>, равно как <tex dpi = "140">G_i^1</tex> и <tex dpi = "140">G_i^2</tex>, отличаются во всех битах.
+<tex >G_i^0</tex> и <tex>G_i^1</tex>, равно как <tex>G_i^1</tex> и <tex>G_i^2</tex>, отличаются во всех битах. <br>
-* Если говорить о векторах как о троичных числах, то <tex dpi = "140">G_{i+1}^0</tex> получено из <tex dpi = "140">G_i^0</tex> прибавлением единицы, это значит, что у <tex dpi = "140">G_{i+1}^0</tex> несколько разрядов справа на единицу больше (по модулю <tex>3</tex>), чем у <tex dpi = "140">G_i^0</tex> (по правилам сложения в столбик). С другой стороны <tex dpi = "140">G_{i}^2</tex> получено из <tex dpi = "140">G_{i}^0</tex> двумя циклическими сдвигами вперёд, что равносильно одному циклическому сдвигу назад. Таким образом, в числе <tex dpi = "140">G_{i+1}^0</tex> некоторые биты такие же, как в <tex dpi = "140">G_{i}^0</tex>, остальные на единицу больше; в числе <tex dpi = "140">G_{i}^2</tex> все биты на один меньше по сравнению с <tex dpi = "140">G_{i}^0</tex>, значит <tex dpi = "140">G_{i}^2</tex> и <tex dpi = "140">G_{i+1}^0</tex> различны во всех битах.
+Если говорить о векторах как о троичных числах, то <tex>G_{i+1}^0</tex> получено из <tex>G_i^0</tex> прибавлением единицы, это значит, что у <tex>G_{i+1}^0</tex> несколько разрядов справа на единицу больше (по модулю <tex>3</tex>), чем у <tex>G_i^0</tex> (по правилам сложения в столбик). С другой стороны <tex>G_{i}^2</tex> получено из <tex>G_{i}^0</tex> двумя циклическими сдвигами вперёд, что равносильно одному циклическому сдвигу назад. Таким образом, в числе <tex>G_{i+1}^0</tex> некоторые биты такие же, как в <tex>G_{i}^0</tex>, остальные на единицу больше; в числе <tex>G_{i}^2</tex> все биты на один меньше по сравнению с <tex>G_{i}^0</tex>, значит <tex>G_{i}^2</tex> и <tex>G_{i+1}^0</tex> различны во всех битах.
 Подобные рассуждения можно провести для любого <tex>k</tex>-ичного кода антигрея, где <tex>k \ge 3</tex>.
@@ Строка 141: / Строка 139: @@
 *[http://en.wikipedia.org/wiki/Talk%3AGray_code#Anti-Gray_Codes.3F Talk:Gray Code - Wikipedia, the free encyclopedia]

@@ Строка 12: / Строка 12: @@
 }}
-Заметим, что для <tex>n > 2</tex> невозможно такое упорядочивание двоичных векторов, что соседние отличаются во всех битах. Объясняется это тем, что для двоичного вектора существует ровно один вектор, отличающийся во всех битах. А в последовательности их должно быть 2.
+Заметим: упорядочивание векторов такое, что соседние отличаются во всех битах, возможно только для <tex>n = 1</tex>. Это объясняется тем, что для двоичного вектора существует ровно один вектор, отличающийся во всех битах, а в последовательности, где <tex>n > 1</tex>, таких векторов должно быть два.
 === Пример ===

← Предыдущая		Версия 10:35, 16 ноября 2013
Строка 1:		Строка 1:
−	~~== Определение ==~~
−
	{{Определение		{{Определение
	\|definition=		\|definition=