Комбинаторный подход к перечислению и нумерации двоичных наборов

• Автор: Пережогин, Алексей Львович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 1999
• Место защиты: Новосибирск
• Количество страниц: 72 с.

Оглавление
Введение
1 Кодирующие последовательности
1.1 Определения
1.2 Конструкции кодирующих последовательностей
2 Циклические (ш, п)-нумерации
2.1 Постановка задачи
2.2 Нижняя оценка с(т, п)
2.3 Явная конструкция циклических (т, п)-слов
2.4 Порожденная циклическая (т,п)-нумерация и алгоритм ее вычисления
2.5 Верхняя оценка длины циклических (ш,п)-слов с ограничениями
2.6 Результаты машинных вычислений
3 Кодирующие последовательности множеств
3.1 Определения и простейшие утверждения
3.2 Необходимые условия существования кодирующей по-
следовательности множеств с предписанными расстояниями
3.3 Кодирующие последовательности множеств с периодом
3.4 Гамильтоновость обобщенных гиперкубов
Литература
Введение
В дискретной математике нередко возникает задача такого перечисления всех объектов некоторого множества М, при котором каждый объект встречается в этом перечислении один раз. При этом возникает естественная нумерация элементов из М, то есть обратимое отображение /, которое каждому натуральному числу г € {1,2
/ : % (&т Оп-Ъ ) 1)1
где (пп, <7П_1,
Часто требуется, чтобы нумерующая функция / удовлетворяла определенным ограничениям. В этом случае возникает вопрос о существовании и нахождении нужной нумерации. Обычно эти ограничения являются следствием условий, которым должно удовлетворять перечисление, порождаемое функцией /. Например, во многих практических задачах требуется перечислять объекты некоторого множества так, чтобы соседние объекты различались в определенном смысле незначительно или даже ”минимально”. При этом нумерующая функция / должна удовлетворять условию: /(г) и /(г + 1) ’’близки” при любом г. Преимуществом такого перечисления является возможность быстрого порождения соседних объектов, а следовательно и всего множества. В настоящее время область комбинаторики, посвящен-

ная такого типа перечислениях:, бурно развивается. При этом объектами упорядочения являются двоичные наборы [17. 15], перестановки [19], -элементные подмножества/(-элементного множества [12, 24, 30], представление целого числа п в виде суммы слагаемых [31], двоичные деревья [21] и др. Эти перечисления нашли свое применение в таких различных областях как циклическое тестирование [28], сигнальное Кодирование [22], сжатие данных [27], расположение процессоров в вершинах гиперкуба [13], подсчет перманента [24] и др. Обзоры полученных результатов и информацию по их применению можно найти в [29, 16].
Другим примером ограничения на нумерующую функцию является минимизация наибольшего абсолютного значения разности номеров, поставленных в соответствие ’’близким" объектам. В [18] показано, что для множества /" такая задача решается с помощью так называемой изопериметричегкой нумерации.
Задачу Нумерации двоичных наборов длины п можно рассматривать как задачу кодирования натуральных чисел {1,2,
{'«1, «2, —> {/' [ '£), = 1. 1 < г < в).
Произвольное перечисление двоичных наборов длины в, при котором соседние наборы различаются в единственной позиции, обычно называют "двоичным кодом Грея” или просто ’’кодом Грея". Для задач существования и эффективного задания кодов Грея оказался полезным язык символьных последовательностей с ограничениями на подслова [15, б, 3, 26]. При таком подходе вместо самого кода Грея рассматривается кодирующая его символьная последовательность, а ограничения на упорядоченность двоичных наборов формулируются в виде запретов на подслова. Получающиеся при этом задачи обычно просто формулируются, что позволяет либо решать задачи, либо

Используя (2.7), случай (ІХЬ) легко сводится к (1Ха), а именно

— е(Х о ~г 2 п У.. и -Х-м... а, У !>. и. "Г 1 -X, | | и -г 2 .г,1) л —г 1 X )
= е(Х' п + 2£і_і п+ 1 Хі-і п -+- 2nZnZi+l...nZj п п + 1 X")

Случаи (1Хс) и (ІХсі) сводятся к рассмотренным случаям (1Ха) и (ІХЬ) сдвигом подслова на одну букву (ан&погично случаю (IV)).
Таким образом, по предложению 1.2 слово У является циклическим кодирующим и теорема 2.1 доказана.
Используя эту теорему, получаем следующую оценку.
Следствие 2.1. При любом п, п > 3, справедливо неравенство
I 3/2(тг — 1)2“/2, если число п четно, п > 8,
«І» - .п) > ( / - - (2.12)
I (я - 1)2' ' 1 в противном случае.
Доказательство. Непосредственно проверяется, что 13231323 является циклическим (2,3)-словом, а 134234134234 - циклическим (3,4)-словом. Используя эти слова в качестве базы индукции, по теореме
2.1 получаем
с(я — 1,п) > (я- 1)2Г"/2'.
В случае четного п. п > 8, в качестве базы индукции можно взять следующее циклическое (7,8}-слово
123456782345671234-587123654718365471236847

123654782365471236587123456718345671234867.
Оно получено с помощью ЭВМ (см. раздел 2.6), а проверка того, что оно действительно является циклическим (7,8)-словом, может быть