На правах рукописи
Мухина Светлана Анатольевна
Диаграмма Хассе частичного порядка
“быть фрагментом”
Специальность 01.01.09 - дискретная математика и математическая кибернетика
АВТОРЕФЕРАТ
Диссертация на соискание ученой степени
кандидата физико-математических наук
Москва – 2009
Работа выполнена на кафедре математических методов прогнозирования факультета Вычислительной математики и кибернетики Московского государственного университета им. М.В. Ломоносова.
Научный руководитель: доктор физико-математических наук, профессор В.К. Леонтьев
Официальные оппоненты: доктор физико-математических наук Ю.Г. Сметанин кандидат технических наук М.М. Ланге
Ведущая организация: Московский физико-технический институт (государственный университет)
Защита диссертации состоится “ ” 2009 г.
в час. мин. на заседании диссертационного совета Д 002.017. при Учреждении Российской академии наук Вычислительный центр им. А.А. Дородницына РАН по адресу: 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) описывается с помощью диаграммы Хассе, которая представляет собой граф с множеством вершин X = B, смежность которых определяется понятием “покрытия”. Другими словами a и b – смежны, если a < b и не существует вершины z с условием a < z < b. Таким образом, смежными на диаграмме Хассе являются “ближайшие” сравнимые вершины.
Важнейшими понятиями, связанными с частичным порядком (1) и диаграммой Хассе, являются следующие:
а) степени вершин;
б) длины цепей, соединяющих вершины a и b;
в) мощность антицепей.
Степени вершин. Описание степеней вершин связано с разложением произвольного слова на произведение блоков или, что то же самое, с серийным представлением слов из B.
Определение 1. Пусть i = i1 i1 +1... i1 +r – подслово (фактор) слова. Подслово i называется серией, если Ясно, что каждое подслово B имеет единственное представление в виде произведения (конкатенации) серий.
Длины цепей, соединяющих две вершины. Если a, b B и a < b, то любое множество элементов называется цепью. Цепь (2) называется максимальной или насыщенной, если в нее нельзя “вставить” ни одного элемента из B.
Определение 2. Длина l(C) конечной цепи C определяется равенством l(C) = |C| 1.
Определение 3. Если a, b B, то говорят, что элемент b покрывает элемент a, если a < b и ни один элемент z B не удовлетворяет условию Определение 4. Элемент a B называется максимальным (минимальным), если из того, что a x (x множество) P = (M, ) называется градуированным ранга n, если каждая максимальная цепь имеет одну и ту же длину n. В этом случае существует единственная ранговая функция : B {0, 1,..., n} такая, что (a) = 0, если a – минимальный элемент B, и (b) = (a) + 1, если b покрывает a в B.
В нашем случае множество (B, ) является градуированным, и ранговая функция слова x B – это просто длина слова x, т.е.
(x) = |x|.
максимальная длина цепи, принадлежащей этому интервалу, т.е.
l(x, y) = (y) (x) = |y| |x|.
Значительный интерес для последних исследований представляет мощность интервала [x, y]. Если то имеет место стандартное представление где свертка 2 (x, 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, то максимальная длина антицепи в этом множестве есть q n и эта единственная антицепь совпадает с верхним слоем диаграммы Хассе.
Глава 2. Бинарный алфавит В главе 2 рассматриваются бинарные слова с определенными характеристиками, а именно: слова конечной длины с заданным весом Хэмминга. Рассматривая частичный порядок “быть фрагментом”, мы находим для указанных слов соотношения для числа слов, содержащих слово в качестве фрагмента. Для найденного соотношения предоставляется ряд следствий.
Хорошо известным фактом является то, что число слов конечной длины n, содержащих в качестве фрагмента данное слово a, не зависит от вида слова и определяется лишь его длиной. Формально это утверждение выглядит следующим образом:
где |a| – длина слова a.
В главе 2 этот факт получает дальнейшее развитие. Принимая во внимание структурный состав слов (как самих слов x, так и заданного фрагмента a), а также учитывая тот факт, что число слов, которые содержат данное слово a в качестве фрагмента, определяется только структурой фрагмента, мы находим точное соотношение для определения данного числа слов.
где FN (m, n, k) – число слов длины N и веса Хэмминга m, содержащих в качестве фрагмента произвольное слово a длины n и веса Хэмминга k.
Далее, в качестве следствия доказывается утверждение, отражающее связь с ранее известным фактом (3).
В терминах диаграммы Хассе условие (3) выражает число путей из вершины a диаграммы Хассе частичного порядка “быть фрагментом” до вершин, расположенных на n-м слое диаграммы Хассе. Найденное условие (4) позволяет среди числа таких путей понять, сколько путей идет к вершинам, имеющим определенный вес Хэмминга m.
Глава 3. q-ичный алфавит В главе 3 частичный порядок “быть фрагментом” рассматривается в q-ичном алфавите. Как и для случая бинарного алфавита, находится число путей из вершины a диаграммы Хассе до вершин, расположенных на n-м слое диаграммы Хассе. Это число выражается в следующем утверждении.
Теорема 1. Справедливо соотношение где k = |a|.
Используя далее серийное представление слов, мы находим следующий параметр диаграммы Хассе – степень “захода” вершины a. Это число оказывается равным числу серий в слове a. Данное утверждение формально отображено в следующей лемме.
Лемма 1. Справедливо соотношение где s(a) – число серий слова a.
Найденное отношение позволяет определить число слов длины n над q-ичным алфавитом, имеющих ровно k серий. Это число определяется в следующей лемме.
Лемма 2. Число слов длины n над алфавитом B, имеющих ровно k Используя результаты леммы, мы далее определяем производящую функцию, математическое ожидание и дисперсию случайной величины n, равномерно распределенной на множестве B n, где B – q-ичный алфавит, и равной числу серий слова x B n. Данные величины определяются следующими утверждениями.
Лемма 3. Производящая функция Fn (z) случайной величины n имеет вид Следствие 1. Справедливы равенства:
Если обозначить множество всех фрагментов q-ичного слова x B через Tx и рассмотреть слово x = 11 22... kk в его серийном представлении, то можно найти верхнюю и нижнюю границу для числа фрагментов слова x.
Лемма 4. Справедливы неравенства В главе 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. Справедливо рекуррентное соотношение y=t1 r2,...,rq Индексы cуммирования y, r2,..., rq в (8) изменяются в тех пределах, для которых определены полиномиальный коэффициент и функция Fny.
Используя полученные характеристики диаграммы Хассе частичного порядка ”быть фрагментом” в теории антицепей, далее можно доказать теорему о мощности максимальной антицепи.
Теорема 3. Мощность максимальной антицепи ч.у. множества, ) равна q n, и эта единственная антицепь совпадает с верхним слоем диаграммы Хассе.
Диссертационная работа посвящена исследованию метрических фрагментом”.
Основные результаты диссертации, выносимые на защиту:
1) Получена точная формула, определяющая число слов в бинарном алфавите, заданной длины и веса Хэмминга, содержащих в качестве фрагмента произвольное бинарное слово с заданной длиной и весом Хэмминга.
2) Доказана рекуррентная формула, определяющая число слов в qичном алфавите с известной композицией, содержащих в качестве фрагмента произвольное q-ичное слово с заданной композицией.
Автор выражает благодарность своему научному руководителю Владимиру Константиновичу Леонтьеву.
1. Леонтьев В.К., Мухина С.А. О фрагментах слов // Пробл.
передачи информации. 2006. Т.42. №3. C.73-77.
2. Леонтьев В.К., Мухина С.А. О фрагментах слов над q-ичным алфавитом // Пробл. передачи информации. 2008. T.44. №3. С.63Леонтьев В.К., Мухина С.А. О фрагментах q-ичных слов // Тезисы докладов XV международной конференции ”Проблемы теоретической кибернетики” (Казань, 2-7 июня 2008 г). Под редакцией Ю.И. Журавлева. Казань: Отечество, 2008. С.74.
4. Мухина С.А. Нахождение числа слов фиксированной длины и фиксированного веса, содержащих в качестве фрагмента слово заданной длины и заданного веса // Сборник тезисов лучших дипломных работ 2005 года. М.: Издательский отдел Факультета ВМиК МГУ им. М.В. Ломоносова, 2005. С.59-60.