Последовательность де Брёйна

Последовательность де Брёйна

Последовательность де Брёйна[1] — последовательность a_1,\;\ldots,\;a_t, элементы которой принадлежат заданному конечному множеству (обычно рассматривают множество \{0,\;1,\;\ldots,\;k-1\}), и все подпоследовательности a_{i+1},\;\ldots,\;a_{i+n} заданной длины n, различны.

Часто рассматриваются периодические последовательности с периодом T, содержащие T различных подпоследовательностей a_{i+1},\;\ldots,\;a_{i+n} — то есть такие периодические последовательности, в которых любой отрезок длины T+n-1 является последовательностью де Брёйна с теми же параметрами n и k.

Циклы де Брёйна названы по имени голландского математика Николаса де Брёйна, который рассматривал их в 1946 году[2], хотя они изучались и ранее[3].

Содержание

Свойства

Очевидно, что длина (период) такого цикла не может превосходить числа k^n всех различных векторов длины n с элементами из \{0,\;1,\;\ldots,\;k-1\}; несложно доказать, что эта оценка достигается. Циклы этой максимально возможной длины обычно называют циклами де Брёйна (впрочем, иногда этот термин применяют и к циклам меньшей длины).

При k=2 существуют такие циклы де Брёйна с длиной, на единицу меньшей максимума, которые выражаются линейными рекуррентными соотношениями порядка n: так, при n=3 соотношение x_n=x_{n-2}+x_{n-3}\pmod 2 порождает последовательности с периодом 7, например 0010111001011100… (цикл де Брёйна 0010111). На основе таких последовательностей построен, в частности, циклический избыточный код CRC32 (EDB88320).


Примеры

Примеры циклов де Брёйна для k=2 с периодом 2, 4, 8, 16:

  • 01 (содержит подпоследовательности 0 и 1)
  • 0011 (содержит подпоследовательности 00, 01, 11, 10)
  • 00010111 (000, 001, 010, 101, 011, 111, 110, 100)
  • 0000100110101111


Количество циклов де Брёйна

Количество циклов де Брёйна с параметрами n и k есть k!^{k^{(n - 1)}}/k^n (частный случай теоремы де Брёйна — Эренфест (англ.) — Смита (англ.) — Тутте (англ.), BEST-теорема (англ.)).

Граф де Брёйна

Существует удобная интерпретация последовательностей и циклов де Брёйна, основанная на так называемом графе де Брёйна — ориентированном графе с k^n вершинами, соответствующими k^n различных наборов длины n с элементами из \{0,\;1,\;\ldots,\;k-1\}, в котором из вершины (x_1,\;\ldots,\;x_n) в вершину (y_1,\;\ldots,\;y_n) ребро ведёт в том и только том случае, когда x_i=y_{i-1} (i=2,\;\ldots,\;n); при этом самому ребру можно сопоставить набор длины n+1: (x_1,\;\ldots,\;x_n,\;y_n)=(x_1,\;y_1,\;\ldots,\;y_n). Для такого графа не проходящие дважды через одно и то же ребро эйлеровы пути (эйлеровы циклы) соответствуют последовательности (циклу) де Брёйна с параметрами n+1 и k, а не проходящие дважды через одну и ту же вершину гамильтоновы пути (гамильтоновы циклы) — последовательности (циклу) де Брёйна с параметрами n и k.

Граф де Брёйна широко применяется в биоинформатике в задачах сборки генома.

Примечания

  1. Встречаются также написания «де Бройна» и «де Брюина».
  2. de Bruijn N. G. A combinatorial problem // Koninklijke Nederlandse Akademie v. Wetenschappen. 1946. — v. 49. — pp. 758—764.
  3. Flye Sainte-Marie C. Question 48 // L’intermédiaire math. — 1894. — v. 1. — pp. 107—110.



Wikimedia Foundation. 2010.

Игры ⚽ Нужна курсовая?

Полезное


Смотреть что такое "Последовательность де Брёйна" в других словарях:

  • Последовательность де Брюина — Последовательность де Брейна[1] последовательность , элементы которой принадлежат заданному конечному множеству (обычно рассматривают множество ) и все подпоследовательности заданной длины n различны. Часто рассматриваются периодические… …   Википедия

  • Последовательность де Брейна — Последовательность де Брейна[1]  последовательность , элементы которой принадлежат заданному конечному множеству (обычно рассматривают множество ), и все подпоследовательности заданной длины n, различны. Часто рассматриваются периодические… …   Википедия

  • Цикл де Брейна — Последовательность де Брейна[1] последовательность , элементы которой принадлежат заданному конечному множеству (обычно рассматривают множество ) и все подпоследовательности заданной длины n различны. Часто рассматриваются периодические… …   Википедия

  • Цикл де Брюина — Последовательность де Брейна[1] последовательность , элементы которой принадлежат заданному конечному множеству (обычно рассматривают множество ) и все подпоследовательности заданной длины n различны. Часто рассматриваются периодические… …   Википедия

  • Цикл де Бройна — Последовательность де Брейна[1] последовательность , элементы которой принадлежат заданному конечному множеству (обычно рассматривают множество ) и все подпоследовательности заданной длины n различны. Часто рассматриваются периодические… …   Википедия

  • Болгарский язык — Самоназвание: Български език Страны: Болгария, Украина …   Википедия

  • Български език — Болгарский язык Самоназвание: Български език Страны: Болгария и прилежащие к ней территории Румынии, Сербии, Македонии,Греции, Турции; этнические болгары в Молдавии и Албании,; болгарская диаспора в Испании, США, Канаде, Аргентине …   Википедия

  • Улица Рубинштейна (Санкт-Петербург) — Координаты: 59°55′50″ с. ш. 30°20′42″ в. д. / 59.930556° с. ш. 30.345° в. д.  …   Википедия

  • событие — я; ср. То, что произошло, случилось, значительное явление, факт общественной или личной жизни. Важное, знаменательное с. Историческое с. Международные события. Каждое выступление этого оркестра с. в жизни города. События на Ближнем Востоке.… …   Энциклопедический словарь

  • событийный — см. событие; ая, ое; ти/ен, ти/йна, ти/йно. С ая последовательность. Образная и с ая система художественного произведения. Жизнь кого л. не событийна (не богата событиями) …   Словарь многих выражений


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»