Теоретическая кибернетика

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