і
Список обозначений
В настоящей работе используется следующая система обозначений. Нумерация определений. утверждений, формул и рисунков начинается заново в каждой главе, и перед каждым номером ставится номер соответствующей главы. Таким образом, формулы в главе 1 будут иметь номера (1.1), (1.2) и т.д. В пределах каждой главы используется сплошная нумерация всех утверждений, например: теорема 1.1, теорема 1.2, лемма 1.3 и т.д. Следствия к теореме 1.2 будут иметь номера 1.2.1, 1.2.2 и т.д.
Конец доказательства обозначается символом ■
Ниже приводится список наиболее важных обозначений, используемых в работе. Для каждого из них (кроме общих) указана страница, на которой вводится данное обозначение. Там, где это возможно, приводится номер формулы, определения или теоремы, а также дается краткое пояснсиис.
Общие обозначения
= равенство по определению
и объединение непересекающихся множеств
1^ целая часть снизу действительного числа г
|*1 целая часть сверху действительного числа х
[п] множество {1,2,...,п}
[п]° множество {0,1,2,..., п}
Обозначения к главе 1
А и д-ичный алфавит {0,- 1}, ч > 2
А" и множество л-мерных векторов с элементами из алфавита А
12 множество всех СЛОВ х € -Дп, имеющих композицию с €
ВІп,(х,£>) 12, (1.7) 8-шар с центром х 6 Ап радиуса I) > 0
В<п)(х,с,£>) 12, (1.7) Д-шар фиксированной композиции е € С^п) с центром х Є Ап радиуса Р > 0
С 11, опр. 1.1 произвольный код
с<п> 12, (1.6) множество всех векторов композиций слов х € л°
с(х) 12 вектор композиции слова х € Ап
И метрика на алфавите А
11,(1.1) аддитивная метрика на Лп, соответствующая алфавитной метрике 8
11, (1.2) минимальное кодовое <5-расстоянис кода С
ен 14, (1.15) вероятностный вектор из Р, задающий вырожденное распределение, сконцентрированное в точке а Є А
14, (1.13) билинейный фуНКЦИОНаЛ ОТ ВеКТОрОВ V = (ъ», Vlt ..., и*-і) И = (ц.’о, . . . , Шд_|)
Ш 14, (1.14) квадратичный функционал, соответствующий билинейному Ті
2
р*1** 14« (1-14) максимум функционала Ті( р) по всем векторнім рбР
*?{р,г) 15, (1.21) функция, используемая в границе Элайса-1
ИРіР >г) Мі (1-17) функция, используемая в границе ЭлаВса-И
■И(р) 14, (1.13) энтропия вероятностного вектора р £ Р
*(р:р') 29,(1.60)
/С(р,р\г) 15, (1.18)
К(Р»Р*} 15» (1-19) величина, задающая область определения функции у>(р,р', г)
А4<п*(2>) 11, (1.4) максимальный объем кода длины п с ^-расстоянием О > 0
Л<1П)(С,Х>) 17, (1.31) максимальный объем кода длины п с ^-расстоянием О > О,
имеющего фиксированную композицию с € С<п>
(")
19, (1.43) полиномиальный коэффициент по композиции с €
Р 12, (1.5) множество вероятностных векторов на алфавите Л
1гИ 13 отображение Р -♦ С
Р|с(р,р', <1) 13, (Ы2) главный член показателя экспоненты функции Я^(с,с,| О)
^(Р. РГ.<0 *3, (1.12) главный член показателя экспоненты функции р]п^(с,р',/))
Р<ГГ(Р?Р,,<^ 13, (1-12) главный член показателя экспоненты функции Р]п^(р, р', О)
,е9В) 13,(1.11)
7><п)(е,РМ?) 13,(1.11)
Т>1*\р,р',0) 13,(1.11)
7?{(4) 11, (1.3) функция скорости кодов с заданным <$-расстоянием
7^*<р. Л) 17, (1.32) функция скорости кодов с заданным <5-расстоянием
п фиксированной композицией и 14, (1.16) вероятностный вектор из Р, задающий равномерное распределение
на А
У*(р,<0 13, (1.12) главный член показателя экспоненты функции У]п*(с, О)
У*(р,рг,<0 13, (1.12) главный член показателя экспоненты функции 1^п*(с,с', О)
У|’,,(с10) 13, (1.8) объем шара в|п){х,0), х С Лп(с)
у]л)(с,с',£>) 13, (1.8) объем шара в]п)(х,с\ />), х б Л"(е)
I 36 множество числовых векторов длины д, сумма координат которых
равна нулю
Обозначения к главе 2
Л
лп
<U<)
6и(а, 6)
*£**(*, у)
£(*.у)
*.<v)
К(у) к(Д) •^днк(^* А)
44 ç-ичный алфавит {0,1,...%q - 1}, q > 2
44 множество л-мерных векторов с элементами из алфавита А
48, (2.16) функция, характеризующая область положительных значений
скорости ?£*,(*, tf)
45, (2.4), (2.6) алфавитная метрика ш-подобия
46, (2.7) аддитивная метрика для векторов х.у € А*, соответствующая
алфавитной метрике tt’-подобия Sw 51 произвольная мера стабильности двойки ДНК, образованной
последовательностями ДНК х и у 46. (2.8) линейный функционал от числового вектора v = (vo, t'fl_j)
46, (2.8) квадратичный функционал от числового вектора v = (t\>, t»i,...,ц,_і)
57 максимальный объем кода ДІІК длины п с порогом и>-подобия à
57 максимальный объем кода ДНК длины п с параметрами «’-подобия
(5,Д)
3
Л41в)(д) 45
Л^1В)(5,Д) 45
45
м1п)(с,5,Д) 45
Яднк(<*) 57
Ядик{*. <*) 57
45, (2.3)
*„(«,<*) 45, (2.3)
*„(р,<0 45, (2.5)
тгч(р,8,<о 45, (2.5)
^днк(х-у) 54, (2.21)
&) 44, (2.1)
4г'(х.у) 44, (2.2)
&п)(х) 44
*$(С) 44, опр. 2
5Й1(С) 44, опр. 2
лЦ<с> 44, опр. 2
ц-(а) 44
48, (2.17)
максимальный объем кода длины п с порогом ш-подобия Л максимальный объем кода длины п с параметрами ш-подобия (5, Д) максимальный объем кода длины п с порогом ш-подобия Л, имеющего фиксированную композицию с € С*”) максимальный объем кода длины п с параметрами ш-подобия (5, Д), имеющего фиксированную композицию с £ функция скорости кодов ДНК с порогом ш-подобия функция скорости кодов ДНК с параметрами ш-подобия функция скорости кодов с порогом ш-подобия функция скорости кодов с параметрами ш-подобия функция скорости ходов фиксированной композиции с порогом ш-подобия
функция скорости кодов фиксированной композиции с параметрами ш-подобия 1.22) функция подобия ДНК алфавитная функция ш-подобия
аддитивная функция ш-подобия для векторов х,у 6 Ал функция и*-самоподобия для векторов х € А"
алфавитная весовая функция на алфавите А обратно сопряженный вектор к х £ Ап
Обозначения к главе 3
0(5,1, X) 60, (3.3), опр. 3.1 дизъюнктно разделяющее множество для пары
(5,Ь)€Т(М,*) в коде X 0;(5, Ь. ЛГ) 60, (3.4), опр. 3.2 списочно разделяющее множество для пары
(5,Ь)€Т(М.*) в коде X О'Чв.Ь.А') 60, (3.5), опр. 3.3 разделяющее множество для пары (5,Ь) € Т(£, я, /) в коде X Т)($>1УХ) 60, (3.6), опр. 3.1 дизъюнктное (з,^-расстояние кода X
!>($, X) 60, онр. 3.1 дизъюнктное ^-расстояние кода X: Р($, \,Х)
ТУ($91,Х) 60, (3.7), опр. 3.2 списочное (*, /)-расстояние кода X
1А) 60, (3.8), опр. 3.3 разделяющее (5,1)-расстояние кода X
£($, X) 60, опр. 3.2 максимальный объем списка силы з для кода X
N(1,() 61 минимальная длина дизъюнктного (з9 I)-кода объема *
71(з,() 61,(3.10) скорость дизъюнктных (*, I)-кодов
«$(,¥) 60» опр. 3.1 максимальная дизъюнктная сила кода X
Т(г, *,£) 59, (3.2) система пар подмножеств множества (*] заданного объема
А(гг, то, Л) 77 код Макулы, построенный на системах инцидентности
конечных множеств Х[п9 т9кчХ^1\шшш9Х^п1) 82 (т, Л)-произведение матриц
Обозначения к главе 4
вт(0 90, (4.10) полином Чсбышева-Эрмита степени т П дисперсия случайной величины
4
Лп
Е
Ш
*{і)
7 к
Пп
^п(ог)
Л»
|к|
к!
Л(*)
Рі(<)
*.(*>
Рг.(0
<?-(«)
*(«>
м<м)
ВД
*.(*)
91, (4.15)
математическое ожидание случайной величины
90. теор. 4.2, (4.14) функции, задающие коэффициенты разложений энтропий
по степеням п
91. (4.16) плоіность стандартного нормального распределения
90, (4.6) семиинвариант порядка к слагаемого Х3 85, (4.4), (4.5) энтропия Шеннона суммы 5П
88, (4.4), (4.5) энтропия Репьи порядка о > 1 суммы 5„
91, (4.13) функции, испольэусмыс в алгоритме построения /*,(<*)
90, (4.7) сумма координат вектора к € 2^
90, (4.7) произведение факториалов координат вектора к Є 2*
88, (4.2) распределение вероятностей слагаемых Х3 в дискретном случае, к £ 7.
88 плотность распределения слагаемых Х3 в абсолютно непрерывном
случае, * Є й
88, (4.3) распределение вероятностей суммы 5„ в дискретном случае, к € 2
88 плотность распределения суммы 5„ в абсолютно непрерывном
случае, ( € Л
92, (4.17) функции, используемые в формулировке локальной предельной теоремы
90, (4.9) функции, используемые в алгоритме построения /*,(о)
91, (4.12) функции, используемые в алгоритме построения /*,(о)
90, (4.8) специальное подмножество Я*
88, (4.1) сумма п независимых случайных величин Х$>...,Хп
89 дисперсия слагаемых X,
88 независимые одинаково распределенные случайные величины,
из которых составляется сумма 5п
90 множество всех целых неотрицательных чисел
90 множество векторов длины V с коэффициентами из
91, (4.15)
5
Введение
Глава 1
В данной главе рассматривается следующая задача. Фиксирован д-ичный алфавит А = {0,- 1}, на котором задана произвольная метрика Л(-, •). На множестве Ап, состоящем из всех векторов (слое) вида х = (*і,..гп)> х; € А, вводится аддитивная метрика
я
Л
£<п|(х, у) = £] %„*,), х,у€^п.
• = 1
Для произвольного подмножества (кода) С С Ап мы определяем минимально* S-расстояние £Н(С) = min<$W(x,y), где минимум берется по всем парам кодовых слов х,у € С, х =* у. Ставится задача об исследовании скорости кодов с заданным <5-расстоянием, т.е. функции
ад* д „>0,
п
где величина AfJ (D), D > 0, равна максимальному объему кода С С Ап, $М(С) > D.
Данную задачу можно отнести к фундаментальным вопросам теории информации. Главным образом она изучалась для метрики Хсммикга (<5(х,у) = 1 для всех г ф у) в связи с приложениями к теории передачи сообщений по каналу связи. До конца зта задача до сих пор не решена, т.е. функция Tl$(d) точно не известна. Для нее имеются лишь различные границы сверху и снизу. Соответственно* и результаты настоящей работы, описывающие случай произвольной метрики 6S заключаются в ряде верхних и нижних границ функции TZj(d).
Наиболее известная граница снизу для метрики Хсммиша получена методом Варшамива-Гильберта (или случайного кодирования). Для некоторых случаев она может быть улучшена.
Что же касается верхних границ, то для них ихіеется большое число различных методов. Классическими можно назвать границы Хемминга, Плоткина и Элайса '9]. Наилучшей же на сегодняшний момент является граница линейного программирования [16].
Задача об обобщении данных границ для случая произвольной метрики является достаточно естественной, однако ранее она практически не рассматривалась. По*видимому, причина лежит в отсутствии приложений, в которых возникала бы необходимость рассматривать другие метрики, и результаты такого типа были бы востребованы.
Одно из таких приложений возникло недавно в связи с некоторыми задачами молекулярной биологии. Оно подробно рассматривается во второй главе настоящей диссертации. При этом вводится новый тип кодов, называемых кодами подобия, скорость которых выражается через скорости кодов с расстоянием в некоторой специальной метрике, которую мы называем метри*сой подобия. Это обстоятельство и привело к необходимости построения границ функции скорости 7Zs(d) для различных метрик 6.
Обратим внимание на две сравнительно недавние работы, в которых рассматривается аналогичная задача. В '27] данный вопрос изучается с точки зрения связи между объемами кодов
б
с расстоянием и дизайнов в метрических пространствах с мерой. С помощью ортогональных полиномов там строятся универсальные границы скорости кодов. В работе [45; рассматривается произвольная метрика и строятся границы скорости, основанные главным образом на методах случайного кодирования и сферической упаковки.
Важным обстоятельством является то, что в обеих работах (27, 45] на метрику не накладывается условие аддитивности. Эго не позволяет использовать метод типов (т. е. коды фиксированной композиции) для получения требуемых оценок скорости. В настоящей работе с помощью данного метода и рассуждений, аналогичных применяемым в оценках Варшамова Гильберта (случайного кодирования), Хемминга. Илоткина и Элайса, мы получаем обобщения данных оценок для различных классов метрик. Также обсуждаются вопросы о сравнении границ друг с другом и об их численном построении. Заметим, что все полученные оценки выражаются через функции, входящие в показатели экспонент для вероятностей больших уклонений сумм некоторых случайных величин.
При »том границы случайного кодирования, Хемминга и Плоткина справедливы для любых метрик, а граница Элайса — только для тех, для которых выполнено специальное условие выпуклости среднего значения (опр. 1.3, стр. 14). В разделе 1.4.3 показано, что данному условии! удовлетворяют все метрики подобия, что позволяет в полной мере использовать полученные результаты для исследования кодов подобия. Вообще же вопрос о том, какие еще метрики удовлетворяют данному условию, остается открытым.
Результаты данной главы получены с использованием метода типов (кодов фиксированной композиции), стандартных методов исследования логарифмической асимптотики величин, различных методов построения границ скорости кодов с расстоянием (случайного кодировании, Варшамова-Гильберта. Хемминга, Плоткина и Элайса). теорем о больших уклонениях сумм независимых случайных величин, выпуклого анализа (одной из форм теоремы Куна-Таккера о решении выпуклых экстремальных задач с ограничениями).
Глава 2
В данной главе рассматривается задача, которая возникла из приложений молекулярной биологии. Сравнительно недавно в ней стали рассматриваться некоторые эксперименты, основанные на специальных свойствах определенных химических веществ (например, молекул ДНК и РНК). Совместно с группой отечественных и зарубежных ученых автор участвовал в построении математической модели, описывающей эти эксперименты. Оказалось, что основные математические объекты, подлежащие изучению, могут быть естественным образом описаны на языке кодов. Эти объекты были названы кодами подобия.
Данный биологический эксперимент подробно описан в §2.4, а его математическая модель имеет следующий вид. Рассматривается четверичный алфавит А = {0,1,2,3}. На нем задана весовая функция и»: и»(0) = ш(3) = 2, »(1) = Ц2) = 3. На ее основе определяется следующая бинарная алфавитная функция №-подобия 5и,:
= а.ЫА.
' (0, если г фу,
На множестве А* вводится соответствующая аддитивная функция и»-подобия для векторов:
У) = х,у€А\
1-1
В отличие от расстояния, которое измеряет степень различия между словами, функция подобия является некоторой мерой сходства между парой векторов. В некотором смысле данные функции являются взаимно обратными. Это обстоятельство лежит в основе используемого метода.
Ставится задача об исследовании кодов С С Ап> удовлетворяющих следующим свойствам для заданных чисел 5>0 и Д>0:
7
1) (х,х) > 5 + Д для каждого кодового слова х в С;
2) 5цГ^(х,у) < 5 для каждой пары кодовых слов х,у € С, х ф у.
Такие ходы мы называем кодами с параметрами и*-подобия (5, Д). Кроме того, про любой такой код мы говорим, что он нмеег порог и)-подобия Д.
Учитывая отмеченную выше связь между подобием и расстоянием, можно эаме1И1ь, что условие 2) близко к тому, что код поддерживает определенное минимальное расстояние между различными кодовыми словами. Условие 1) сводится к некоторому ограничению на композиции рассматриваемых слов, поскольку величина 5^(х,х), которую мы называех! самоподобием вектора х € Ап, полностью определяется композицией х.
Данная задача рассматривалась в работе [46]. Были получены некоторые оценки на функции скорости соответствующих кодов. Все они являются частными случаями более общих и точных границ, построенных в настоящей работе.
Далее мы обобщаем згу задачу, рассматривая произвольный алфавит А — {0, - 1}
и произвольную весовую функцию и» на кем, которая принимает строго положительные значения. Обозначим через Л4ш*(5, Д) максимальный объем кода С С Лп, их!еющего параметры ш-подобия (5, Д). Через Л1!»П^(Д) мы обозначим максимальный объем кода, имеющего порог гг-подобия Д. Определим функции скорости данных кодов следующим образом:
Задача заключается в исследовании данных функций. В работе показано, что эти функции выражаются через скорость кодов с расстоянием 7?Д</) в метрике б = которая имеет вид
Мы называем ее мгтрихой и?-подобия. Таким образом, для решения рассматриваемой задачи можно прихіенить результаты главы 1, в которой построены границы для данной функции. В работе показано, что для любой весовой функции и? метрика 6Ы обладает свойством выпуклости среднего расстояния, и поэтому для нее применимы все полученные результаты.
Практические приложения накладывают на код еще одно дополнительное условие, которое имеет следующий вид. На алфавите вводится операция сопряжения, т.е. каждому элементу а б А ставится в соответствие сопряженный ему элемент а € А (возхюжно, совпадающий с а), причем а = а для любого о € А. В частности, для исходного примера рассматривается следующее сопряжение: 0 = 3, 1 = 2, 2 = 1, 3 = 0.
Далее определяется операция обратного сопряжения лля векторов х Є Лп, которая имеет следующий вид: если х = ...,гпЬ т<> обратно сопряженным к нему называется век-
тор зГ = (*п,£і). Очевидно, что повторное применение данной операции к слову Зс переводит его обратно в х.
Код С С А* называется самосопряженным^ если, во-первых, он замкнут относительно данной операции, т.е. *х Є С для любого кодового слова х Є С, и, во-вторых, он не содержит самосопряженных слов, т.е. ф х для любого х С: С• В этох! случае можно считать, что код составлен из пар слов {х, х-}, причем оба слова во всех парах различны.
В исследуемой практической задаче молекулярной биологии возникает потребность в кодах подобия, которые удовлетворяют данному условию сахїосопряженности. Поскольку последнее является дополнительным ограничением, то очевидно, что скорость таких кодов не превосходит скорости кодов подобия, т.е. верхние оценки для нес сохраняют силу. В работе показано.
, я > О, л > О,
при г Ї уу г,у€Л
8
- Київ+380960830922