Асимптотические задачи комбинаторной теории кодирования и теории информации

• Автор: Виленкин, Павел Александрович
• Шифр специальности: 01.01.05
• Научная степень: Кандидатская
• Год защиты: 2001
• Место защиты: Москва
• Количество страниц: 106 с. : ил

Список обозначении
В настоящей работе используется следующая система обозначений. Нумерация определений, утверждений, формул и рисунков начинается заново в каждой главе, и перед каждым номером ставится номер соответствующей главы. Таким образом, формулы в главе 1 будут иметь номера (1.1), (1.2) и т.д. В пределах каждой главы используется сплошная нумерация всех утверждений, например: теорема 1.1, теорема 1.2, лемма 1.3 и т.д. Следствия к теореме 1.2 будут иметь номера 1.2.1, 1.2.2 и т.д.
Конец доказательства обозначается символом ■
Ниже приводится список наиболее важных обозначений, используемых в работе. Для каждого из них (кроме общих) указана страница, на которой вводится данное обозначение. Там, где это возможно, приводится номер формулы, определения или теоремы, а также дается краткое пояснение.
Общие обозначения
= равенство по определению
У объединение непересекающихся множеств
[ж] целая часть снизу действительного числа х
| х | целая часть сверху действительного числа х
[»] множество {1,2,..., тг.}
[п]° множество {0,1,2,..., п}
Обозначения к главе
А 11 д-ичный алфавит {0,1, ...,#— 1},
Ап 11 множество п-мерных векторов с элементами из алфавита А
Лп(с) 12 множество всех СЛОВ X € Дп, имеющих КОМПОЗИЦИЮ С € с(п)
В <">(*, О) 12, (1.7) 8 -шар с центром х (Е Ап радиуса £> >
ВГ(х,с ,В) 12, (1.7) 8-шар фиксированной композиции с € с центром х € Ап радиуса И >
С 11, опр. 1.1 произвольный код
см 12, (1.6) множество всех векторов композиций слов х 6 Ап
с(х) 12 вектор композиции слова х € Ап
11 метрика на алфавите А
И, (1.1) аддитивная метрика на Ап, соответствующая алфавитной метрике
«»> (С) 11, (1.2) минимальное кодовое <5-расстояние кода С
е(а) 14,(1.15) вероятностный вектор из Р, задающий вырожденное распределение, сконцентрированное в точке а € Л
Тб(ч,уг) 14, (1.13) билинейный функционал от векторов V = (ио, VI, ... , И у = (го0,^1,...,-Юд-х)
ш 14, (1.14) квадратичный функционал, соответствующий билинейному Т&

■77“ 14, (1.14) максимум функционала ^(р) по всем векторам р € Р
^(р,г) 15, (1.21) функция, используемая в границе Элайса-
Р(Р.Р'.Г) 14, (1.1.7) функция, используемая в границе Элайса-Н
к(р) 14, (1.13) энтропия вероятностного вектора р € Р
И(р : р') 29, (1.60)
К(р,р',1-} 15, (1.18)
к(р, р') 15, (1.19) величина, задающая область определения функции <р(р,р', г)
М^(В) И, (1.4) максимальный объем кода длины п с 5-расстоянием Б >
М? с,В) / 17, (1.31) максимальный объем кода длины п с 5-расстоянием Б > 0, имеющего фиксированную композицию с е СН
0 19, (1.43) полиномиальный коэффициент по композиции с € С^
Р 12, (1.5) множество вероятностных векторов на алфавите Л
7г(п) 13 отображение Р С(п)
(р, р', <0 13, (1.!2) главный член показателя экспоненты функции р]п^(с, с', Б)
■рГ(р,р',й) 13, (1.12) главный член показателя экспоненты функции Т5] (с, р', Б)
У?Р(р,р',<2) 13, (1.12) главный член показателя экспоненты функции Р]п^(р,р', Б)
р|”>(с,с',С) 13, (1.11)
Р|")(с,Р,,-0) 13, (1.11)
р]п)(р,р',-0) 13, (1.11)
%(<г) 11, (1.3) функция скорости кодов с заданным 8-расстоянием
7гг(р,й) 17, (1.32) функция скорости кодов с заданным 5-расстоянием и фиксированной композицией
и 14, (1.16) вероятностный вектор из Р, задающий равномерное распределение на Л
%(р,<0 13, (1.12) главный член показателя экспоненты функции (с, Б)
У«(р,р',<2) 13, (1.12) главный член показателя экспоненты функции У|п^(с, с', Б)
13, (1.8) объем шара ВгП^(х, Л), х € -4”(с) объем шара (х,с',Б), х 6 Лп(с)
У<">(с,с',Д) 13, (1.8)
г 36 множество числовых векторов длины д, сумма координат которых
равна нулю
Обозначения к главе
Л 44 д-ичный алфавит {0,1,..., д — 1}, д >
Лп 44 множество л-мерных векторов с элементами из алфавита Л
<М*) 48, (2.16) функция, характеризующая область положительных значений
скорости 7£ц,(я, б£)
5ц, (а, 6) 45, (2.4), (2.6) алфавитная метрика го-подобия
40 (х, у) 46, (2.7) аддитивная метрика для векторов х, у 6 Л71, соответствующая
алфавитной метрике го-подобия 5ц,
£(х,у) 51 произвольная мера стабильности двойки ДНК, образованной
последовательностями ДНК х и у
КМ 46, (2.8) линейный функционал от числового вектора V = («о, *>1, • • •, ^д-1)
К{у) 46, (2.8) квадратичный функционал от числового вектора V = (г>о, г»х,..., ц9_
Ч"нк(А) 57 максимальный объем кода ДНК длины п с порогом го-подобия А
■^ДНК^ А) 57 максимальный объем кода ДНК длины п с параметрами го-подобия
(5,Д)

(А) 45 максимальный объем кода длины п с порогом го-подобия А
M^(S, А) 45 максимальный объем кода длины п с параметрами го-подобия
Л<1п)(с,Д) 45 максимальный объем кода длины п с порогом го-подобия А, имеющего фиксированную композицию с € С(п)
Mw{c, S, A) 45 максимальный объем кода длины п с параметрами го-подобия (5, А), имеющего фиксированную композицию с £ С^п)
■^днк(^) 57 функция скорости кодов ДНК с порогом го-подобия
■^днк(«»^) 57 функция скорости кодов ДНК с параметрами го-подобия
nw[d) 45, (2.3) функция скорости кодов с порогом го-подобия
nw{s, d) 45, (2.3) функция скорости кодов с параметрами го-подобия
'B'w (Pi d) 45, (2.5) функция скорости кодов фиксированной композиции с порогом го-подобия
^iu(Pi s, d) 45, (2.5) функция скорости кодов фиксированной композиции с параметрами го-подобия
5днк(х.У) 54, (2.21), (2.22) функция подобия ДНК
Sw(a,b) 44, (2.1) алфавитная функция го-подобия
s£x, y) 44, (2.2) аддитивная функция го-подобия для векторов х, у £ Лп
s£>(x) 44 функция го-самоподобия для векторов х £ Дп
stJ(C) 44, опр. 2.1 максимальное попарное гг-подобие С С Л!'
stJ(C) 44, опр. 2.1 минимальное го-самоподобие кода С С Лп
41(c) 44, опр. 2.1 порог го-подобия кода С С Лп
w(a) 44 алфавитная весовая функция на алфавите Л
Обозначения к главе
D(S,L,X) 60, (3.3), onp. 3.
D'(S,L,X) 60, (3.4), onp. 3.
D"(S,L,X) 60, (3.5), onp. 3.
V{s,£,X) 60, (3.6), onp. 3.
V(s, X) 60, onp. 3.
V'{s,£,X) 60, (3.7), onp. 3.
V"{s,£,X) 60, (3.8), onp. 3.
£{s, X) 60, onp. 3.
N{t, s, £)
TZ{s,£) 61, (3.10)
S(X) 60, onp. 3.
T(t, s, I) 59, (3.2)
X (a, m, h)
X{n,m,h,X^...,X(n))
(S,L) £ T[t, s,£) в коде X
списочно разделяющее множество для пары
(S, L) £ T(t, s, £) в коде X
разделяющее множество для пары (S, L) £ 1~(t, s,£) в коде X дизъюнктное (s, £)-расстояние кода X дизъюнктное 5-расстояние кода X: P(s, 1,-Х”) списочное (5, () -расстояние кода X разделяющее (s, £) -расстояние кода X максимальный объем списка силы 5 для кода X минимальная длина дизъюнктного (s, £) -кода объема t скорость дизъюнктных (s, -кодов максимальная дизъюнктная сила кода X система пар подмножеств множества [t] заданного объема код Макулы, построенный на системах инцидентности конечных множеств (m, h)-произведение матриц ...,
Обозначения к главе
Вт{^) 90, (4.10) полином Чебышева-Эрмита степени т
Б дисперсия случайной величины

3. при ж^(р, р') < д < ^(Р) рО функция монотонно убывает и определяется следующим параметрическим соотношением
<*(Р.Р ',*) = М^(р,р',А), ^<
■РГ(Р.Р'.<*(Р,Р'.А)) = Ам;(р,р',Л)-И(р,р',А),
где £/^(р, р', /1) обозначает частную производную функции Ы{р, р', К) по к; при этом значение к = О соответствует точке д = •7г<5(р,р,)> а предельный переход при к —> -со приводит к случаю 1.
Доказательство. Рассмотрим композицию с = тгМр £ СМ. Рассмотрим два случайных независимых вектора ъ = я(с) и ъ' = г(р'), распределения которых имеют вид (1.10) и (1.9) соответственно. Величина 7*^ (с, р', вп) (1.11) имеет вид
р]п)(с, рдп) = Рг|<^")(г, а*) < с/п| = Рг г[) < Слагаемые в последней сумме независимы, и при этом для каждого о € И. ровно са слагаемых имеют функцию распределения ^’(е(а^, р'), введенную выше. Таким образом, утверждение сразу вытекает из определения функции 7>|р(р,р', д) (1.12) и теоремы 1.14 о вероятности больших уклонений для неодинаково распределенных слагаемых. ■
С помощью соотношения (1.63) свойства функции У*(р, с2) можно сразу вывести из свойств функции ^Р(р, р;, д). При р' = и величины (1.75) имеют следующий вид
*1(Р>и) = о,
91(Р. “) = = 9~1’

г'(р,и) = ^(р,и) = д-1 У] 6(а,Ь)ра,
*,ЬеА
И(р, и, А) = ^2 paU(da и, А) = У] ра log
а£Л о£Д
£дМ(а,Ь)-

Таким образом, из равенства (1.63) и теоремы 1.16 вытекает следующий результат.
Следствие 1.16.1, Для произвольного фиксированного вектора р € Р функция V$(p,d) определена для всех значений d > 0, непрерывна, выпукла вверх и неубывает. Она имеет следующий вид:
1. Vj(p,0) = 0;
2. V<5(р, d) = 1 для всех d > ^(р, и);
3. при 0 < d < Fs(p, и) функция монотонно возрастает и определяется следующим параметрическим соотношением
d(p,k) = UL(p,n, к),
к< 0,
V,j(p,d(p,/i)) = kU'h{p, и, к) - И{р, и, к),
где U'h(р, и, к) обозначает частную производную функции U(p, и, к), определенной выше, по переменной к; при этом значение к = 0 соответствует точке V В заключение заметим, что полученные простые параметрические соотношения позволяют легко находить рассматриваемые функции численно.