Викия

Математика

Последовательность де Брюина

1457статей на
этой вики
Добавить новую страницу
Обсуждение0 Поделиться

Обнаружено использование расширения AdBlock.


Викия — это свободный ресурс, который существует и развивается за счёт рекламы. Для блокирующих рекламу пользователей мы предоставляем модифицированную версию сайта.

Викия не будет доступна для последующих модификаций. Если вы желаете продолжать работать со страницей, то, пожалуйста, отключите расширение для блокировки рекламы.

Шаблон:Rq

Цикл де Брюина или последовательность де Брюина B(k,n), любая подпоследовательность длины n встречается один раз.

циклическая последовательность де Брюина с периодом 16

s=0000100110101111

Условно открыты де Брюином (de Bruijn) в 1946, но реально Flye-Sainte Marie ещё в 1894.

число циклических последовательностей де Брюина с периодом n в алфавите из k символов

k!^{k^n - 1}/k^n

пример для k=2, n=2,4,8,…

01
0011
00010111

существуют для любых n, k.

На основе этих циклов, задаваемых линейными рекуррентными формулами, построен CRC32 (с примитивным полиномом EDB88320)pl:Cykl de Bruijna

Викия-сеть

Случайная вики