Быстрая нумерация комбинаторных объектов, находящая применение в системах передачи и хранения информации

• Автор: Медведева, Юлия Сергеевна
• Шифр специальности: 05.13.17
• Научная степень: Кандидатская
• Год защиты: 2015
• Место защиты: Новосибирск
• Количество страниц: 113 с. : ил.

Оглавление
Введение

1 Постановка задачи и известные общие методы

1.1 Задача нумерации и денумерации комбинаторных объектов

1.1.1 Задача нумерации и денумерации комбинаторных объектов в общем виде

1.1.2 Нумерация слов с ограничением на длины серий единиц.

1.1.3 Нумерация слов языков Дика

1.1.4 Нумерация элементов грассманиана

1.2 Известные общие методы нумерации комбинаторных объектов .

1.2.1 Метод Т. Ковера

1.2.2 Метод Б. Я. Рябко
2 Нумерация слов языков Дика
2.1 Известный алгоритм нумерации слов языков Дика
2.2 Быстрый алгоритм нумерации слов языка Дика над алфавитом {ОД}
2.3 Быстрый алгоритм денумерации слов языка Дика над алфавитом {0,1}
2.4 Быстрый алгоритм нумерации слов языков Дика над алфавитом мощности 2т
2.5 Быстрый алгоритм денумерации слов языков Дика над алфавитом мощности 2т
2.6.........................................................Выводы
3 Нумерация элементов грассманиана
3.1 Известный алгоритм нумерации элементов грассманиана
3.2 Быстрый алгоритм нумерации элементов грассманиана
3.3 Быстрый алгоритм денумерации элементов грассманиана
3.4.........................................................Выводы
4 Нумерация <Шг-последовательностей
4.1 Известный алгоритм нумерации сШг-последовательностей
4.2 Быстрый алгоритм нумерации сШг-последовательностей
4.3 Быстрый алгоритм денумерации бШг-последовательностей
4.4..........................................................Выводы
Заключение
Список литературы Приложение А

Введение
Диссертационная работа посвящена созданию быстрых алгоритмов нумерационного кодирования для ряда классов комбинаторных объектов: слова с ограничением иа длины серий единиц, слова языков Дика, элементы грас-сманиана.
Актуальность темы исследования. Задача нумерационного кодирования в общем виде состоит в следующем: дан некоторый алфавит А и множество 5 слов длины п > 1, являющееся подмножеством всех слов длины п, состоящих из букв алфавита А. Метод нумерационного кодирования должен по данному слову ги Є Б вычислять его номер сос1е$(ю), т. е. число из промежутка [0, |5| — 1]. Причем номер со<іез(ги) записывается в двоичном виде и имеет длину |Д^2|5|] бит. Все слова сос1ез(ии) должны быть различными при разных іи Є в. Метод нумерационного декодирования должен по данному номеру слова сосіез{и;), т. е. числу из промежутка [О, І^І — 1], записанному в двоичном виде и имеющему длину [к^215|] бит, находить слово ъи є 5. Задача построения быстрых алгоритмов нумерации и денумерации имеет практическую и теоретическую значимость в кодировании данных на носителях и в каналах, имеющих ограничения, связанные с физическими свойствами носителя или канала, а также в сетевом кодировании и других областях теории

л°7 = о, а° = о.
Затем вычисляем, используя формулы (2.7):
1 5 1
Л = П, *2 = 5.
Рз = 2» ^ = 1.
4 - 9 А0 - -14’ 5’
= О, А° = 0,
2 _ 1 1 _ 1 Р1 ^1 Рз 2’
А? = |, А| = О,
з 1 .я
р1~14’ _ 7’
Используя (2.8), находим, что содещ(01010011) = А^ • |£)|| = | • 14 = 12. Таким образом, мы получили содер,а (го), номер слова 01010011 (Е И|.
Для исследования свойств алгоритма нумерации слов, принадлежащих множеству 5, определим несколько величин.
Обозначим через дтах максимальный знаменатель дробей
М${хХ2 . ■ . Х1)/Мз{%1Х2 ■ ■ ■ х...хп 6 Б, г = 1 Свойства
предложенного метода характеризует следующая теорема.
Теорема 1.1) Сложность кодирования слов множества Б длины п на одну кодируемую букву, измеряемая в битовых операциях, равна
О (log пМ (п log qmax)/n), где М(п) — время умножения двух слов длины п.
(2.12)