Для установки нажмите кнопочку Установить расширение. И это всё.

Исходный код расширения WIKI 2 регулярно проверяется специалистами Mozilla Foundation, Google и Apple. Вы также можете это сделать в любой момент.

4,5
Келли Слэйтон
Мои поздравления с отличным проектом... что за великолепная идея!
Александр Григорьевский
Я использую WIKI 2 каждый день
и почти забыл как выглядит оригинальная Википедия.
Статистика
На русском, статей
Улучшено за 24 ч.
Добавлено за 24 ч.
Что мы делаем. Каждая страница проходит через несколько сотен совершенствующих техник. Совершенно та же Википедия. Только лучше.
.
Лео
Ньютон
Яркие
Мягкие

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

Из Википедии — свободной энциклопедии

Последовательность де Брёйна[1] — циклический порядок , элементы которого принадлежат заданному конечному множеству (обычно рассматривают множество ), такой, что все его подпоследовательности [2] заданной длины различны.

Часто рассматриваются периодические последовательности с периодом , содержащие различных подпоследовательностей , — то есть такие периодические последовательности, в которых любой отрезок длины является последовательностью де Брёйна с теми же параметрами и .

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

Свойства

Очевидно, что длина (период) такого цикла не может превосходить  — числа́ всех различных векторов длины с элементами из ; несложно доказать, что эта оценка достигается. Циклы этой максимально возможной длины обычно называют циклами де Брёйна (впрочем, иногда этот термин применяют и к циклам меньшей длины).

При существуют такие циклы де Брёйна с длиной, на единицу меньшей максимума, которые выражаются линейными рекуррентными соотношениями порядка : так, при соотношение порождает последовательности с периодом 7, например 0010111001011100… (цикл де Брёйна 0010111). На основе таких последовательностей построен, в частности, циклический избыточный код CRC32 (EDB88320).

Примеры

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

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

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

Количество циклов де Брёйна с параметрами и есть (частный случай теоремы де Брёйна — BEST-теорема (англ.), названная по фамилиям де Брёйна, Татьяны Эренфест, Седрика Смита и Уильяма Татта).

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

Существует удобная интерпретация последовательностей и циклов де Брёйна, основанная на так называемом графе де Брёйна — ориентированном графе с вершинами, соответствующими различных наборов длины с элементами из , в котором из вершины в вершину ребро ведёт в том и только том случае, когда (); при этом самому ребру можно сопоставить набор длины : . Для такого графа не проходящие дважды через одно и то же ребро эйлеровы пути (эйлеровы циклы) соответствуют последовательности (циклу) де Брёйна с параметрами и , а не проходящие дважды через одну и ту же вершину гамильтоновы пути (гамильтоновы циклы) — последовательности (циклу) де Брёйна с параметрами и .

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

Примечания

  1. Встречаются также написания «де Бройна» и «де Брюина».
  2. Если , то в циклическом порядке выбирается элемент с индексом
  3. de Bruijn N. G. A combinatorial problem // Koninklijke Nederlandse Akademie v. Wetenschappen. 1946. — v. 49. — pp. 758—764.
  4. Flye Sainte-Marie C. Question 48 // L’intermédiaire math. — 1894. — v. 1. — pp. 107—110.
Эта страница в последний раз была отредактирована 30 января 2021 в 21:01.
Как только страница обновилась в Википедии она обновляется в Вики 2.
Обычно почти сразу, изредка в течении часа.
Основа этой страницы находится в Википедии. Текст доступен по лицензии CC BY-SA 3.0 Unported License. Нетекстовые медиаданные доступны под собственными лицензиями. Wikipedia® — зарегистрированный товарный знак организации Wikimedia Foundation, Inc. WIKI 2 является независимой компанией и не аффилирована с Фондом Викимедиа (Wikimedia Foundation).