Перейти к содержанию

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


Рекомендуемые сообщения

 

Цитата

 

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

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

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

 


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

Ссылка на сообщение
Поделиться на другие сайты

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

 

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

  • Like (+1) 2
Ссылка на сообщение
Поделиться на другие сайты
Цитата

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

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

Ссылка на сообщение
Поделиться на другие сайты

Пожалуйста, войдите, чтобы комментировать

Вы сможете оставить комментарий после входа в



Войти
×
×
  • Создать...