Необычное применение последовательности де Брёйна

[rare]

 

Цитата

 

Последовательность де Брёйна — это циклический порядок элементов, принадлежащих заданному конечному множеству, такой, что все его подпоследовательности заданной длины различны. Это означает, что каждая возможная строка длины n из алфавита k появляется ровно один раз в последовательности.

Примером последовательности де Брёйна для алфавита k=2 (т.е. {0,1}) и длины подпоследовательности n=3 может быть 00010111. Здесь каждая возможная трехсимвольная строка (000, 001, 010, 011, 100, 101, 110, 111) появляется ровно один раз.

Существуют различные методы генерации последовательностей де Брёйна. Один из подходов заключается в использовании концепций теории графов. Начинаем с генерации набора узлов. Если мы работаем с последовательностью де Брёйна порядка n, то каждый узел содержит уникальную строку длины n-1 из нашего алфавита. Затем строим ориентированный граф, где каждый узел имеет ребро, выходящее из него и соединяющее его с узлом, который будет следующим в последовательности де Брёйна. Получившийся граф всегда будет иметь Эйлеров путь, который можно использовать для генерации последовательности де Брёйна.

 

Здравствуйте. Мне всегда казалось, что существует очень интересное применение последовательности де Брёйна, о котором мы еще не знаем. Хотелось услышать Ваше мнение о теории и возможные идеи, где это было бы интересно применить. Спасибо!

[E.K.]

Вы обо мне слишком хорошего мнения. Впервые слышу о такой последовательности...

[rare]

Жаль, мне казалось довольно популярный алгоритм в криптографии 😅

[E.K.]

Так я же крипрограф не настоящий! Был бы настоящим - до сих пор бы в погонах ходил, наверное. Не получился из меня криптограф, я в программисты пошёл...

 

Криптография (по моему разумению) - самая сложная математическая дисциплина. И чтобы получить одного неплохого криптографа надо обучить ... ну, наверное, два десятка очень толковых студентов-математиков. Только один из них станет Криптографом, остальные - в отвал (программирование, например). Я оказался с большинством...

[rare]

Цитата

Криптография (по моему разумению) - самая сложная математическая дисциплина. И чтобы получить одного неплохого криптографа надо обучить ... ну, наверное, два десятка очень толковых студентов-математиков. Только один из них станет Криптографом, остальные - в отвал (программирование, например). Я оказался с большинством...

Предлагаю закрыть тему на этой потрясающей цитате 😅
Спасибо!