Монотонный код Грея - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:23:49Z

rollbackEdits.php mass rollback

185.220.101.186 в 05:05, 1 сентября 2022

2022-09-01T05:05:16Z

Namenamich в 10:32, 24 июня 2019

2019-06-24T10:32:17Z

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

2016-12-19T18:41:52Z

‎Псевдокод

Shersh: /* Источники информации */

2016-12-19T18:41:09Z

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

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

2016-12-19T18:39:49Z

‎Псевдокод

Gpevnev в 12:01, 19 декабря 2016

2016-12-19T12:01:13Z

Gpevnev в 11:58, 19 декабря 2016

2016-12-19T11:58:35Z

Gpevnev в 13:53, 18 декабря 2016

2016-12-18T13:53:35Z

Gpevnev в 13:52, 18 декабря 2016

2016-12-18T13:52:27Z

@@ Строка 1: / Строка 1: @@
 {{Определение
 |definition =
-'''Монотонный код Грея''' (англ. ''Monotonic Gray Code'') {{---}} способ построения кода Грея, при котором <tex>\forall i < j</tex> <tex>\nexists g_i, g_j</tex>, что <tex>g_i</tex> содержит на <tex>2</tex> или больше единиц, чем <tex>g_j</tex>.
+'''Монотонный код Грея''' (англ. ''Monotonic Gray Code'') {{---}} способ построения кода Грея, при котором <tex>\forall i < j</tex> <tex>\nexists g_i, g_j</tex>, что <tex>g_i</tex> содержит на <tex>2</tex> или больше единиц, чем <tex>g_j</tex>.
 }}
 Монотонный код Грея преимущественно используется в теории связанных сетей, например для минимизации ожидания линейным массивом процессоров.<ref>[http://www.sciencedirect.com/science/article/pii/0097316595900918 C. D Savage and P. Winkler (1995). "Monotone Gray codes and the middle levels problem"page 7]</ref>

@@ Строка 1: / Строка 1: @@
 {{Определение
 |definition =
-'''Монотонный код Грея''' (англ. ''Monotonic Gray Code'') {{---}} способ построения кода Грея, при котором <tex>\forall i < j</tex> <tex>\nexists g_i, g_j</tex>, что <tex>g_i</tex> содержит на <tex>2</tex> или больше единиц, чем <tex>g_j</tex>.
+'''Монотонный код Грея''' (англ. ''Monotonic Gray Code'') {{---}} способ построения кода Грея, при котором <tex>\forall i < j</tex> <tex>\nexists g_i, g_j</tex>, что <tex>g_i</tex> содержит на <tex>2</tex> или больше единиц, чем <tex>g_j</tex>.
 }}
 Монотонный код Грея преимущественно используется в теории связанных сетей, например для минимизации ожидания линейным массивом процессоров.<ref>[http://www.sciencedirect.com/science/article/pii/0097316595900918 C. D Savage and P. Winkler (1995). "Monotone Gray codes and the middle levels problem"page 7]</ref>

@@ Строка 77: / Строка 77: @@
 <code>'''yield'''</code> {{---}} аналог <code>'''return'''</code> только для функций-генераторов. То есть генераторы это тоже итерируемые объекты, но прочитать их можно лишь один раз. Это связано с тем, что они не хранят значения в памяти, а генерируют их на лету.
-С конструкциями типа <code>(0,)</code> или <code>(1,)</code> все проще. Используя ее совместно с <code>'''yield'''</code> мы можем в изменять наш генерируемый объект. Например, <code>'''yield''' (0,)</code> допишет к генерируемому объекту (в нашем случае кортежу (англ. ''tuple'')) <tex>0</tex> в начало.
+С конструкциями типа <code>(0,)</code> или <code>(1,)</code> все проще. Используя ее совместно с <code>'''yield'''</code> мы можем изменять наш генерируемый объект. Например, <code>'''yield''' (0,)</code> допишет к генерируемому объекту (в нашем случае кортежу (англ. ''tuple'')) <tex>0</tex> в начало.
 {| border="0"
 |align="left" colspan="4"|

@@ Строка 125: / Строка 125: @@
   '''function''' monotonic('''int''' n): '''list<int[n]>'''
      '''for''' i '''in''' range(n)
-         '''for''' x '''in''' (p(n, i) '''if''' i % 2 == 0 '''else''' p(n, i, reverse=True))
+         '''for''' x '''in''' (p(n, i) '''if''' i % 2 == 0 '''else''' p(n, i, reverse=''true''))
              '''yield''' x
 </code>

← Предыдущая		Версия 18:41, 19 декабря 2016
Строка 161:		Строка 161:
	[[Категория: Дискретная математика и алгоритмы]]		[[Категория: Дискретная математика и алгоритмы]]
	[[Категория: Комбинаторика]]		[[Категория: Комбинаторика]]
		+	[[Категория: Комбинаторные объекты ]]

@@ Строка 116: / Строка 116: @@
                  '''yield''' (0,) + x
          '''else'''
-             '''for''' x '''in''' p(n - 1, j, reverse=True)
+             '''for''' x '''in''' p(n - 1, j, reverse=''true'')
                  '''yield''' (0,) + x
-             '''for''' x '''in''' p(n - 1, j - 1, reverse=True)
+             '''for''' x '''in''' p(n - 1, j - 1, reverse=''true'')
                  '''yield''' (1,) + '''tuple'''(x[k] '''for''' k '''in''' perm)
 </code>
-Генерация монотонного кода Грея при помощи уже написанного генератора <code>p</code>.
+Генерация монотонного кода Грея при помощи уже написанного генератора <tex>p</tex>.
 <code>
   '''function''' monotonic('''int''' n): '''list<int[n]>'''

@@ Строка 100: / Строка 100: @@
 Принимает <tex>n, j</tex>, а так же дополнительный параметр определяющий надо-ли переворачивать кортеж.
 <code>
-  '''function''' p('''int''' n, '''int''' j, '''bool''' reverse = ''false''):
+  '''function''' p('''int''' n, '''int''' j, '''bool''' reverse = ''false''): '''list<int[n]>'''
      '''if''' n == 1 and j == 0
          '''if''' '''not''' reverse
@@ Строка 123: / Строка 123: @@
 Генерация монотонного кода Грея при помощи уже написанного генератора <code>p</code>.
 <code>
-  '''function''' monotonic('''int''' n):
+  '''function''' monotonic('''int''' n): '''list<int[n]>'''
      '''for''' i '''in''' range(n)
          '''for''' x '''in''' (p(n, i) '''if''' i % 2 == 0 '''else''' p(n, i, reverse=True))

@@ Строка 1: / Строка 1: @@
 {{Определение
 |definition =
-'''Монотонный код Грея''' (англ. ''Monotonic Gray Code'') {{---}} способ построения кода Грея, при котором <tex>\nexists</tex> <tex>g_i, g_j</tex>, что <tex>g_i</tex> содержит на <tex>2</tex> или больше единиц, чем <tex>g_j</tex>.
+'''Монотонный код Грея''' (англ. ''Monotonic Gray Code'') {{---}} способ построения кода Грея, при котором <tex>\forall i < j</tex> <tex>\nexists g_i, g_j</tex>, что <tex>g_i</tex> содержит на <tex>2</tex> или больше единиц, чем <tex>g_j</tex>.
 }}
 Монотонный код Грея преимущественно используется в теории связанных сетей, например для минимизации ожидания линейным массивом процессоров.<ref>[http://www.sciencedirect.com/science/article/pii/0097316595900918 C. D Savage and P. Winkler (1995). "Monotone Gray codes and the middle levels problem"page 7]</ref>
@@ Строка 75: / Строка 75: @@
 Перед тем как писать псевдокод необходимо объяснить что такое <code>'''yield'''</code> и что понимать под выражениями типа <code>(0,)</code> или <code>(1,)</code>.
-<code>'''yield'''</code> - аналог <code>'''return'''</code> только для функций-генераторов. То есть генераторы это тоже итерируемые объекты, но прочитать их можно лишь один раз. Это связано с тем, что они не хранят значения в памяти, а генерируют их на лету.
+<code>'''yield'''</code> {{---}} аналог <code>'''return'''</code> только для функций-генераторов. То есть генераторы это тоже итерируемые объекты, но прочитать их можно лишь один раз. Это связано с тем, что они не хранят значения в памяти, а генерируют их на лету.
 С конструкциями типа <code>(0,)</code> или <code>(1,)</code> все проще. Используя ее совместно с <code>'''yield'''</code> мы можем в изменять наш генерируемый объект. Например, <code>'''yield''' (0,)</code> допишет к генерируемому объекту (в нашем случае кортежу (англ. ''tuple'')) <tex>0</tex> в начало.
 {| border="0"
 |align="left" colspan="4"|
-*Вспомогательная функция для генерации перестановки, циклически сдвигает битовый вектор направо <tex>n</tex> раз.
+Вспомогательная функция для генерации перестановки, циклически сдвигает битовый вектор направо <tex>n</tex> раз.
-*Принимает и возвращает котреж. Кортеж аналог списка, но в кортеже нельзя менять элементы, можно только добавлять.
+Принимает и возвращает кортеж. Кортеж аналог списка, но в кортеже нельзя менять элементы, можно только добавлять.
 <code>
-  rotateRight(x, n):
+  '''function''' rotateRight(x: '''int[n]'''): '''int[n]'''
      '''return''' x[-n:] + x[:-n]
 </code>
-*Рекурсивная генерация <tex>n</tex>-ой перестановки.
+Рекурсивная генерация <tex>n</tex>-ой перестановки.
-*Возвращает перестановку в виде кортежа.
+Возвращает перестановку в виде кортежа.
-*Если n становится меньше <tex>2</tex> дописывает в начало кортежа <tex>0</tex> и возвращает его.
+Если <tex>n</tex> становится меньше <tex>2</tex> дописывает в начало кортежа <tex>0</tex> и возвращает его.
 <code>
-  pi(n):
+  '''function''' pi('''int''' n): '''int[n]'''
-     '''if''' n <= 1:
+     '''if''' n <= 1
          '''return''' (0,)
      x = pi(n - 1) + (n - 1,)
-     '''return''' rotate_right('''tuple'''(x[k] '''for''' k '''in''' x), 1)
+     '''return''' rotateRight('''tuple'''(x[k] '''for''' k '''in''' x), 1)
 </code>
-*Рекурсивная генерация пути <tex>P_{n, j}</tex>.
+Рекурсивная генерация пути <tex>P_{n, j}</tex>.
-*Принимает <tex>n, j</tex>, а так же дополнительный параметр определяющий надо-ли переворачивать кортеж.
+Принимает <tex>n, j</tex>, а так же дополнительный параметр определяющий надо-ли переворачивать кортеж.
 <code>
-  p(n, j, reverse = ''false''):
+  '''function''' p('''int''' n, '''int''' j, '''bool''' reverse = ''false''):
-     if n == 1 and j == 0:
+     '''if''' n == 1 and j == 0
-         '''if''' '''not''' reverse:
+         '''if''' '''not''' reverse
              '''yield''' (0,)
              '''yield''' (1,)
-         '''else''':
+         '''else'''
              '''yield''' (1,)
              '''yield''' (0,)
-     '''elif''' j >= 0 '''and''' j < n:
+     '''else if''' j >= 0 '''and''' j < n
          perm = pi(n - 1)
-         '''if''' '''not''' reverse:
+         '''if''' '''not''' reverse
-             '''for''' x '''in''' p(n - 1, j - 1):
+             '''for''' x '''in''' p(n - 1, j - 1)
                  '''yield''' (1,) + '''tuple'''(x[k] '''for''' k '''in''' perm)
-             '''for''' x '''in''' p(n - 1, j):
+             '''for''' x '''in''' p(n - 1, j)
                  '''yield''' (0,) + x
-         '''else''':
+         '''else'''
-             '''for''' x '''in''' p(n - 1, j, reverse=True):
+             '''for''' x '''in''' p(n - 1, j, reverse=True)
                  '''yield''' (0,) + x
-             '''for''' x '''in''' p(n - 1, j - 1, reverse=True):
+             '''for''' x '''in''' p(n - 1, j - 1, reverse=True)
                  '''yield''' (1,) + '''tuple'''(x[k] '''for''' k '''in''' perm)
 </code>
-*Генерация монотонного кода Грея при помощи уже написанного генератора p.
+Генерация монотонного кода Грея при помощи уже написанного генератора <code>p</code>.
 <code>
-  monotonic(n):
+  '''function''' monotonic('''int''' n):
-     '''for''' i '''in''' range(n):
+     '''for''' i '''in''' range(n)
-         '''for''' x '''in''' (p(n, i) '''if''' i % 2 == 0 '''else''' p(n, i, reverse=True)):
+         '''for''' x '''in''' (p(n, i) '''if''' i % 2 == 0 '''else''' p(n, i, reverse=True))
              '''yield''' x
 </code>

@@ Строка 30: / Строка 30: @@
 <tex>
 P_{n+1,j} = 1P^{\pi_n}_{n,j-1}, 0P_{n,j}
-</tex>. То есть <tex>P_{n+1, j}</tex> это объединение множеств <tex>P^{\pi_n}_{n,j-1}</tex> с приписанной в начале 1 и <tex>P_{n,j}</tex> с приписанным в начале нулем.
+</tex>. То есть <tex>P_{n+1, j}</tex> это объединение множеств <tex>P^{\pi_n}_{n,j-1}</tex> с приписанной в начале <tex>1</tex> и <tex>P_{n,j}</tex> с приписанным в начале <tex>0</tex>.
 Здесь <tex>\pi_n</tex> это определенная перестановка элементов множества к которому она применена, а <tex>P^{\pi}</tex> это путь <tex>P</tex> к котрому была применена пересатновка  <tex>\pi</tex>.

@@ Строка 19: / Строка 19: @@
 Пусть <tex>Q_n(i)</tex> подграф <tex>Q_n</tex>, который является объединением двух смежных уровней, т. е. <tex>V_n(i) \cup V_n(i+1)</tex>, и пусть <tex>E_n(i)</tex> множество граней <tex>Q_n(i)</tex>.
-Тогда монотонным кодом Грея будет являтся [[:Гамильтоновы_графы|Гамильтонов путь]] в <tex>Q_n</tex>, при котором любое множество вершин <tex>\delta_1 , \delta_2</tex> такие, что <tex>\forall i, j : i \leqslant j</tex>, то <tex>\delta_1 \in E_n(i)</tex> идет перед <tex>\delta_2 \in E_n(j)</tex>.
+Тогда монотонным кодом Грея будет являтся [[:Гамильтоновы_графы#.D0.9E.D1.81.D0.BD.D0.BE.D0.B2.D0.BD.D1.8B.D0.B5_.D0.BE.D0.BF.D1.80.D0.B5.D0.B4.D0.B5.D0.BB.D0.B5.D0.BD.D0.B8.D1.8F|Гамильтонов путь]] в <tex>Q_n</tex>, при котором любое множество вершин <tex>\delta_1 , \delta_2</tex> такие, что <tex>\forall i, j : i \leqslant j</tex>, то <tex>\delta_1 \in E_n(i)</tex> идет перед <tex>\delta_2 \in E_n(j)</tex>.
 Ниже на катринке Гамильтонов путь в гиперкубе <tex>Q_4</tex> для <tex>n = 4</tex>, построенный по алгоритму Саважа-Винклера (англ. ''Savage-Winkler'').<ref>[http://www.sciencedirect.com/science/article/pii/0097316595900918 C. D Savage and P. Winkler (1995). "Monotone Gray codes and the middle levels problem"page 14]</ref>