WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

загрузка...
   Добро пожаловать!

Pages:     || 2 |

На правах рукописи

Мухина Светлана Анатольевна Диаграмма Хассе частичного порядка “быть фрагментом” Специальность 01.01.09 - дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ

Диссертация на соискание ученой степени кандидата физико-математических наук

Москва – 2009

Работа выполнена на кафедре математических методов прогнозирования факультета Вычислительной математики и кибернетики Московского государственного университета им. М.В. Ломоносова.

Научный консультант: доктор физико-математических наук, профессор В.К. Леонтьев

Официальные оппоненты: доктор физико-математических наук Ю.Г. Сметанин кандидат технических наук М.М. Ланге

Ведущая организация: Московский физико-технический институт (государственный университет)

Защита диссертации состоится “ ” 2009 г.

в час. мин. на заседании диссертационного совета Д 002.017.02 при Учреждении Российской академии наук Вычислительный центр им. А.А. Дородницына РАН по адресу: 119333, г. Москва, ул. Вавилова, д.40.

С диссертацией можно ознакомиться в библиотеке ВЦ РАН.

Автореферат разослан “ ” 2009 г.

Ученый секретарь диссертационного совета Д 002.017.02 при ВЦ РАН доктор физико-математических наук В.В. Рязанов

Общая характеристика работы

Актуальность темы. Комбинаторная теория слов является одним из активно развивающихся разделов дискретной математики, имеющим широкие и глубокие связи с алгебраической топологией, математической лингвистикой, алгебраической теорией кодирования, математической генетикой и другими разделами математики и ее приложений. Основные проблемы комбинаторики слов связаны с изучением слов и словарных функций, а основными объектами изучения являются слова, части слова, множества слов и упорядоченность на множестве слов. Многие формулировки проблем сводятся к нахождению или описанию множеств слов, обладающих определенным перечнем свойств. В частности, сюда относятся способы описания слов, не содержащих или ”избегающих” запрещенные подслова. К этому же классу можно отнести проблемы описания слов по их структурированным тем или иным образом фрагментам.

Фрагмент как часть слова несет определенную информацию о всем слове, и с этой точки зрения комбинаторные исследования на множестве слов имеют вполне содержательную теоретико-информационную основу.

Исследования взаимосвязей между словами и их фрагментами актуальны и имеют практическую значимость в разных направлениях современной науки, таких как, например, исследование генетических последовательностей, теория кодирования и передачи информации с большой степенью надежности и высокой скоростью.

Изучение частичного порядка ”быть фрагментом” и его диаграммы Хассе позволяет определить, структурировать и формализовать характеристики, связывающие слова и их фрагменты. Такого рода исследования позволяют решать различные задачи на множестве слов. Во многих таких задачах фундаментальной является проблема нахождения числа слов из заданного множества, содержащих в качестве ”части” фрагменты другого, тем или иным способом определенного семейства слов. Классической здесь является задача о нахождении числа слов длины n, содержащих в качестве фрагмента фиксированное слово a длины m. Не лишне отметить, что решение этой задачи не дается какойто простой формулой и зависит от ”корреляционной” функции, связанной со словом a.

В диссертации рассматриваются метрические характеристики диаграммы Хассе частичного порядка ”быть фрагментом” для двоичного и q-ичного алфавитов.

Цель работы. Целью работы является исследование геометрических свойств диаграммы Хассе частичного порядка ”быть фрагментом” в двоичном и q-ичном алфавитах.

Научная новизна. В работе получены точные и рекуррентные формулы, позволяющие определить мощности множеств слов, содержащих в качестве фрагмента слово с заданной композицией.

Следствием этого результата являются, в частности, некоторые хорошо известные в теории информации факты, часто используемые для оценки мощности кодов, корректирующих ошибки. Кроме того, получен ряд новых результатов о диаграмме Хассе частичного порядка, определенного предикатом ”быть фрагментом”.

Методика исследования. Методы комбинаторного анализа.

Практическая ценность. Результаты работы могут быть применены в различных оптимизационных схемах теории кодирования, использующих отношение частичного порядка, изоморфное изученному в диссертации.

Апробация работы. Результаты диссертации докладывались на заседании кафедры математических методов прогнозирования факультета ВМиК МГУ. По теме диссертации опубликовано 4 работы.

Объем и структура работы. Диссертация состоит из введения, двух глав и списка литературы. Общий объем – 64 страницы.

Основное содержание работы

Глава 1. Введение Комбинаторика слов представляет собой важный раздел дискретной математики, имеющий глубокое внутреннее содержание, разнообразные связи со многими классическими областями современной математики и многочисленные приложения в теории информации, математической генетике, структурной лингвистике и т.д.

Диаграмма Хассе. Основным объектом исследования являются слова, множества слов, части слова, связь частей слова, упорядоченность на множестве слов.

Итак, пусть B = {a1, a2,..., aq} – q-ичный алфавит и B – множество всех слов конечной длины над алфавитом B. Если a B, то любое слово a, полученное из a удалением некоторых букв, называется фрагментом слова a. Это отношение задает частичный порядок на B, который мы будем обозначать стандартным образом a a, (1) есди a – фрагмент a.

Геометрически отношение (1) описывается с помощью диаграммы Хассе, которая представляет собой граф с множеством вершин X = B, смежность которых определяется понятием “покрытия”. Другими словами a и b – смежны, если a < b и не существует вершины z с условием a < z < b. Таким образом, смежными на диаграмме Хассе являются “ближайшие” сравнимые вершины.

Важнейшими понятиями, связанными с частичным порядком (1) и диаграммой Хассе, являются следующие:

а) степени вершин;

б) длины цепей, соединяющих вершины a и b;

в) мощность антицепей.

Степени вершин. Описание степеней вершин связано с разложением произвольного слова на произведение блоков или, что то же самое, с серийным представлением слов из B.

Определение 1. Пусть i = i i +1... i +r – подслово (фактор) 1 1 слова. Подслово i называется серией, если а) i = i +1 =... = i +r = as B;

1 1 б) i -1 = as, i +r+1 = as.

1 Ясно, что каждое подслово B имеет единственное представление в виде произведения (конкатенации) серий.

Длины цепей, соединяющих две вершины. Если a, b B и a < b, то любое множество элементов a b1 < b2 <... < bk b (2) называется цепью. Цепь (2) называется максимальной или насыщенной, если в нее нельзя “вставить” ни одного элемента из B.

Определение 2. Длина l(C) конечной цепи C определяется равенством l(C) = |C| - 1.

Определение 3. Если a, b B, то говорят, что элемент b покрывает элемент a, если a < b и ни один элемент z B не удовлетворяет условию a < z < b.

Определение 4. Элемент a B называется максимальным (минимальным), если из того, что a x (x a), x B, следует a = x.

Определение 5. Частично-упорядоченное множество (ч.у.

множество) P = (M, ) называется градуированным ранга n, если каждая максимальная цепь имеет одну и ту же длину n. В этом случае существует единственная ранговая функция : B {0, 1,..., n} такая, что (a) = 0, если a – минимальный элемент B, и (b) = (a)+1, если b покрывает a в B.

В нашем случае множество (B, ) является градуированным, и ранговая функция слова x B – это просто длина слова x, т.е.

(x) = |x|.

По определению длина интервала [x, y], где x y, – это максимальная длина цепи, принадлежащей этому интервалу, т.е.

l(x, y) = (y) - (x) = |y| - |x|.

Значительный интерес для последних исследований представляет мощность интервала [x, y]. Если 1, x y, (x, y) = 0, если не так, то имеет место стандартное представление 2(x, y) = 1 = |[x, y]| = Card[x, y], x z y где свертка 2(x, y) определяется стандартным способом f · g (x, y) = f(x, z)g(z, y), x z y или в нашем случае 2(x, y) = (x, z)(z, y).

x z y Если опять обратиться к диаграмме Хассе, то мощность интервала [x, y] при x < y равна общему числу вершин, лежащих на всех путях, соединяющих x и y.

Мощность антицепей. Пусть B = {a1, a2,..., aq} – q-ичный алфавит с частичным порядком ”быть фрагментом” ( ).

Определение 6. Антицепь есть подмножество A ч.у. множества P, в котором любые два элемента несравнимы.

Определение 7. Мощность антицепи V – число элементов в ней.

Геометрические свойства диаграммы Хассе. Геометрия диаграммы Хассе частичного порядка “быть фрагментом” следующая:

а) Если вершина x лежит на k-м слое диаграммы Хассе, т.е. |x| = k, то из нее “исходит” ровно (k + 1)(q - 1) + 1 ребер.

б) Если вершина x лежит на k-м слое диаграммы Хассе, то в нее “входит” ровно s(x) ребер, где s(x) – число серий слова x.

в) Если рассматриваются q-ичные слова длины n, то максимальная длина антицепи в этом множестве есть qn и эта единственная антицепь совпадает с верхним слоем диаграммы Хассе.

Глава 2. Бинарный алфавит В главе 2 рассматриваются бинарные слова с определенными характеристиками, а именно: слова конечной длины с заданным весом Хэмминга. Рассматривая частичный порядок “быть фрагментом”, мы находим для указанных слов соотношения для числа слов, содержащих слово в качестве фрагмента. Для найденного соотношения устанавливается связь с ранее известными фактами, а также предоставляется ряд следствий.

Хорошо известным фактом является то, что число слов конечной длины n, содержащих в качестве фрагмента данное слово a, не зависит от вида слова и определяется лишь его длиной. Формально это утверждение выглядит следующим образом:

n n Fn(a) =, (3) i i=|a| где |a| – длина слова a.

В главе 2 этот факт получает дальнейшее развитие. Принимая во внимание структурный состав слов (как самих слов x, так и заданного фрагмента a), а также учитывая тот факт, что число слов, которые содержат данное слово a в качестве фрагмента, определяется только структурой фрагмента, мы находим точное соотношение для определения данного числа слов.

m+n-2k y - 1 N - y FN(m, n, k) =, (4) n - k - 1 N - m - n + k y=n-k где FN(m, n, k) – число слов длины N и веса Хэмминга m, содержащих в качестве фрагмента произвольное слово a длины n и веса Хэмминга k.

Далее, в качестве следствия доказывается утверждение, отражающее связь с ранее известным фактом (3).

В терминах диаграммы Хассе условие (3) выражает число путей из вершины a диаграммы Хассе частичного порядка “быть фрагментом” до вершин, расположенных на n-м слое диаграммы Хассе. Найденное условие (4) позволяет среди числа таких путей понять, сколько путей идет к вершинам, имеющим определенный вес Хэмминга m.

Глава 3. q-ичный алфавит В главе 3 частичный порядок “быть фрагментом” рассматривается в q-ичном алфавите. Как и для случая бинарного алфавита, находится число путей из вершины a диаграммы Хассе до вершин, расположенных на n-м слое диаграммы Хассе. Это число выражается в следующем утверждении.

Теорема 1. Справедливо соотношение n n n |Ta | = (q - 1)n-i, (5) i i=k где k = |a|.

Используя далее серийное представление слов, мы находим следующий параметр диаграммы Хассе – степень “захода” вершины a. Это число оказывается равным числу серий в слове a. Данное утверждение формально отображено в следующей лемме.

Лемма 1. Справедливо соотношение r(a) = s(a), где s(a) – число серий слова a.

Найденное отношение позволяет определить число слов длины n над q-ичным алфавитом, имеющих ровно k серий. Это число определяется в следующей лемме.

Лемма 2. Число слов длины n над алфавитом B, имеющих ровно k n-серий, равно q(q - 1)k-1.

k-Используя результаты леммы, мы далее определяем производящую функцию, математическое ожидание и дисперсию случайной величины n, равномерно распределенной на множестве Bn, где B – q-ичный алфавит, и равной числу серий слова x Bn. Данные величины определяются следующими утверждениями.

Лемма 3. Производящая функция Fn(z) случайной величины n имеет вид n-(z - 1)(q - 1) Fn(z) = z 1 +. (6) q Следствие 1. Справедливы равенства:

n - 1 (n - 1)(q - 1) Mn = n -, Dn =.

q qЕсли обозначить множество всех фрагментов q-ичного слова x t1 t2 tk B через Tx и рассмотреть слово x = 1 2... k в его серийном представлении, то можно найти верхнюю и нижнюю границу для числа фрагментов слова x.

Лемма 4. Справедливы неравенства t1t2... tk < |Tx| < (1 + t1)(1 + t2)... (1 + tk). (7) В главе 3 приводится аналог утверждения для функции FN(m, n, k) – числа слов длины N и веса Хэмминга m, содержащих в качестве фрагмента произвольное слово a длины n и веса Хэмминга k, для qичного алфавита. В случае q-ичного алфавита аналогом веса Хэмминга слова предлагается использовать понятие композиции слова, которая определяется следующим образом:

Определение 8. Пусть B = {a1, a2,..., aq} и a B. Через wk(a) мы обозначим число вхождений буквы ak в слово a. Тогда вектор w(a) = (w1, w2,..., wq) называется композицией слова a.

Вводя для q-ичного алфавита функцию Fn(a, w1, w2,..., wq), которая определяет число слов длины n и заданной композиции w, содержащих в качестве фрагмента слово a, мы сначала доказываем по аналогии с бинарным алфавитом независимость данной функции от вида фрагмента a, т.е. Fn(a, w1, w2,..., wq) = Fn(t1, t2,..., tq, w1, w2,..., wq), где w(a) = (t1, t2,..., tq) – композиция слова a. Затем для функции Fn(t1, t2,..., tq, w1, w2,..., wq) мы находим рекуррентное соотношение, которое отображено в следующей теореме:

Теорема 2. Справедливо рекуррентное соотношение Fn(t1, t2,..., tq, w1, w2,..., wq) = y - = Fn-y(0, t2,..., tq, w1 - t1,..., wq - rq). (8) t1 - 1, r2,..., rq y=t1 r2,...,rq Индексы cуммирования y, r2,..., rq в (8) изменяются в тех пределах, для которых определены полиномиальный коэффициент и функция Fn-y.

Используя полученные характеристики диаграммы Хассе частичного порядка ”быть фрагментом” в теории антицепей, далее можно доказать теорему о мощности максимальной антицепи.

Теорема 3. Мощность максимальной антицепи ч.у. множества (B n, ) равна qn, и эта единственная антицепь совпадает с верхним слоем диаграммы Хассе.

Pages:     || 2 |






© 2011 www.dissers.ru - «Бесплатная электронная библиотека»