Диаграмма Хассе частичного порядка "быть фрагментом" тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

003464262

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

Мухина Светлана Анатольевна

Диаграмма Хассе частичного порядка "быть фрагментом"

Специальность 01.01.09 - дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ Диссертация на соискание ученой степени кандидата физико-математических наук

Москва - 2009

003464262

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

доктор физико-математических наук, профессор В.К. Леонтьев доктор физико-математических наук Ю.Г. Сметанин кандидат технических наук М.М. Ланге

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

Защита диссертации состоится " № " JlLQh/Ьй.- 2009 г. в ^ час. QQ мин. на заседании диссертационного совета Д 002.017.02 при Учреждении Российской академии наук Вычислительный центр им. A.A. Дородницына РАН по адресу: 119333, г. Москва, ул. Вавилова, Д.40.

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

Автореферат разослан " ^ " 2009 г.

Научный руководитель:

Официальные оппоненты:

Ведущая организация:

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

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

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

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

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

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

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

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

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

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

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

в диссертации. ■

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

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

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

Глава 1. Введение

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

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

Итак, пусть В — {а^ аг,..., а?} - </-ичнын алфавит и В* - множество всех слов конечной длины над алфавитом В. Если а 6 В*, то любое слово о', полученное из а удалением некоторых букв, называется фрагментом слова а. Это отношение задает частичный порядок на В*, который мы будем обозначать стандартным образом

а! < а, (1)

есди а' - фрагмент а.

Геометрически отношение (1) описывается с помощью диаграммы Хассе, которая представляет собой граф с множеством вершин X =

В*, смежность которых определяется понятием "покрытия". Другими словами а и Ь - смежны, если а < Ь и не существует вершины г с условием а < г < Ь. Таким образом, смежными на диаграмме Хассе являются "ближайшие" сравнимые вершины.

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

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

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

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

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

Определение 1. Пусть Vi = уг1ьц+1... г>,1+г - подслово (фактор) слова V. Подслово ы называется серией V, если

а) г^ = г>*1+1 = ... = = а3 £ В;

б) ^1-1 ф ав, ьк+г+1 -ф а„.

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

Длины цепей, соединяющих две вершины. Если о, Ь £ В* и а < Ь, то любое множество элементов

а < Ь\ < Ь2 < ... < Ьк < Ь (2)

называется цепью. Цепь (2) называется максимальной или насыщенной, если в нее нельзя "вставить" ни одного элемента из В*.

Определение 2. Длина 1(С) конечной цепи С определяется равенством 1{С) — \С\ — 1.

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

Определение 4. Элемент а £ В* называется максимальным (минимальным), если из того, что а ^ х (х ^ а), х £ В*, следует а — х.

Определение 5. Частично-упорядоченное множество (ч.у. множество) Р = (М, называется градуированным ранга п, если каждая максимальная цепь имеет одну и ту же длину п. В этом случае существует единственная ранговая функция р : J5* —> {0,1,...,п} такая, что р(а) = 0, если а - минимальный элемент В*, и р(Ь) — р(а) +1, если b покрывает а в В*.

В нашем случае множество (В*, является градуированным, и ранговая функция слова х £ В* - это просто длина слова х, т.е. р{х) = \х\.

По определению длина интервала [х, у], где х < у, - это максимальная длина цепи, принадлежащей этому интервалу, т.е. 1{х,у) = р(у) - р(х) = |у| - |4

Значительный интерес для последних исследований представляет мощность интервала [х, у]. Если

,, ч . х ^ Vi

О, если не так, то имеет место стандартное представление

е(х,у)= J2 l = IM]l = Card[x,y],

x^z^y

где свертка £2(х, у) определяется стандартным способом или в нашем случае

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

Мощность антицепей. Пусть В = {щ, аг,..., ад} - д-ичный алфавит с частичным порядком "быть фрагментом"

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

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

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

а) Если вершина х лежит на к-м слое диаграммы Хассе, т.е. |х| = к, то из нее "исходит" ровно (к + 1)(д — 1) + 1 ребер.

б) Если вершина х лежит на к-м слое диаграммы Хассе, то в нее "входит" ровно ребер, где - число серий слова х.

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

Глава 2. Бинарный алфавит

В главе 2 рассматриваются бинарные слова с определенными характеристиками, а именно: слова конечной длины с заданным

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

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

= (3)

На| 4 7

где |а| - длина слова а.

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

Р„(т,п,к)=тук( У'1 V \ (4)

' ' ; \n-k-lJ\N-т-п + к)' К '

где п, к) - число слов длины N и веса Хэмминга т, содержащих

в качестве фрагмента произвольное слово а длины п и веса Хэмминга к.

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

В терминах диаграммы Хассе условие (3) выражает число путей из вершины а диаграммы Хассе частичного порядка "быть фрагментом" до вершин, расположенных на тг-м слое диаграммы Хассе. Найденное

условие (4) позволяет среди числа таких путей понять, сколько путей идет к вершинам, имеющим определенный вес Хэмминга т.

Глава 3. <?-ичный алфавит

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

Теорема 1. Справедливо соотношение

га = Е (")(?-1)п_<. (5)

где к = |а|.

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

Лемма 1. Справедливо соотношение

г(а) = в (а),

где я(а) - число серий слова а.

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

Лемма 2. Число слов длины п над алфавитом В, имеющих ровно к серий, равно —

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

£„, равномерно распределенной на множестве В", где В - д-ичный алфавит, и равной числу серий слова х £ Вп. Данные величины определяются следующими утверждениями.

Лемма 3. Производящая функция Рп(г) случайной величины £„ имеет вид

Следствие 1. Справедливы равенства:

п-1 (п-1)(д-1)

М£„ = п--, = *--

Я - Г . '

ЕсЛи обозначить множество всех фрагментов д-ичного слова х £ В* через Тх и рассмотреть слово х — 7|1722 ■ ■ -1к в ег0 серийном представлении, то можно найти верхнюю и нижнюю границу для числа фрагментов слова х.

Лемма 4. Справедливы неравенства

Ы2..лк< \ТХ\ < (1 + + ...(1 + 4). (7)

В главе 3 приводится аналог утверждения для функции ^(т, п, к) -числа слов длины N и веса Хэмминга т, содержащих в качестве фрагмента произвольное слово а длины п и веса Хэмминга к, для спичного алфавита. В случае д-ичного алфавита аналогом веса Хэмминга слова предлагается использовать понятие композиции слова, которая определяется следующим образом:

Определение 8. Пусть В = {аь а2,..., а,} и а £ В*. Через юк{а) мы обозначим число вхождений буквы а^ в слово а. Тогда вектор и](а) = {■и)\,'Ш2, ■ ■ ■ ,Мд) называется композицией слова а.

Вводя для д-ичного алфавита функцию -Рп(а, и)\, ги-2, •.., и)д), которая определяет число слов длины п и заданной композиции и), содержащих в качестве фрагмента слово а, мы сначала доказываем по аналогии

с бинарным алфавитом независимость данной функции от вида фрагмента а, т.е. Гп(а,юд) - ¿2,• • •,Ц,гох,ги2,• ■ •,щ), где ги(а) — (¿1, ¿2, • • • 11Ч) - композиция слова а. Затем для функции

мы находим рекуррентное соотношение, которое отображено в следующей теореме:

Теорема 2. Справедливо рекуррентное соотношение

¿2, • • •, Ц, гоь 1112, ■ ■ ■, го,) =

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

гп-у-

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

Теорема 3. Мощность максимальной антицепи ч.у. множества

равна и эта единственная антицепь совпадает с верхним слоем диаграммы Хассе.

Заключение

Диссертационная работа посвящена исследованию метрических характеристик диаграммы Хассе частичного порядка "быть фрагментом".

Основные результаты диссертации, выносимые на защиту:

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

2) Доказана рекуррентная формула, определяющая число слов в q-ичном алфавите с известной композицией, содержащих в качестве фрагмента произвольное д-ичное слово с заданной композицией.

Автор выражает благодарность своему научному руководителю Владимиру Константиновичу Леонтьеву.

1. Леонтьев В.К., Мухина С.А. О фрагментах слов // Пробл. передачи информации. 2006. Т.42. №3. С.73-77.

2. Леонтьев В.К., Мухина С.А. О фрагментах слов над д-ичным алфавитом // Пробл. передачи информации. 2008. Т.44. №3. С.63-69.

3. Леонтьев В.К., Мухина С.А. О фрагментах д-ичных слов // Тезисы докладов XV международной конференции "Проблемы теоретической кибернетики" (Казань, 2-7 июня 2008 г). Под редакцией Ю.И. Журавлева. Казань: Отечество, 2008. С.74.

4. Мухина С.А. Нахождение числа слов фиксированной длины и фиксированного веса, содержащих в качестве фрагмента слово заданной длины и заданного веса // Сборник тезисов лучших дипломных работ 2005 года. М.: Издательский отдел Факультета ВМиК МГУ им. М.В. Ломоносова, 2005. С.59-60.

Благодарности

Публикации по теме диссертации

Типография МГУ 119991, ГСП-1, Ленинские горы, д. 1,стр. 15 Заказ № 157 Тираж 100 экз.

1.1 Диаграмма Хассе.

1.1.1 Степени вершин.

1.1.2 Длины цепей, соединяющих две вершины.

1.1.3 Мощность антицепей.

1.1.4 Геометрические свойства диаграммы Хассе.

1.2 Бинарный алфавит.

1.3 д-ичный алфавит.

2 Бинарный алфавит

2.1 Основные понятия и определения.

2.2 Метод коэффициентов.

2.3 Установление связи между характеристиками частичного порядка "быть фрагментом".

2.3.1 Независимость от вида фрагмента.

2.3.2 Рекуррентное соотношение для ^(га, п, к).

2.3.3 Точное соотношение для ^(т, п, к).

2.3.4 Следствия.

2.3.5 Примеры.

3 д-ичный алфавит

3.1 Основные понятия и определения.

3.2 Число слов, содержащих в качестве фрагмента фиксированное слово а.

3.3 Серийное представление слов.

3.4 Число фрагментов д-ичного слова.

3.5 Композиция слов.

3.6 Примеры.

3.7 Мощность антицепей.

1.1 Диаграмма Хассе

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

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

Итак, пусть В — {ах, <22,., ад} - д-ичный алфавит и В* - множество всех слов конечной длины над алфавитом В. Если а Е В*, то любое слово а/, полученное из а удалением некоторых букв, называется фрагментом слова а. Это отношение задает частичный порядок на В*, который мы будем обозначать стандартным образома' < а, (1.1)есди а' - фрагмент а.

Геометрически отношение (1.1) описывается с помощью диаграммыХассе, которая представляет собой граф с множеством вершин X — В*, смежность которых определяется понятием "покрытия". Другими словами а и b - смежны, если а < b и не существует вершины 2 с условием а < z < Ъ. Таким образом, смежными на диаграмме Хассе являются "ближайшие" сравнимые вершины. Ниже изображена часть диаграммы Хассе для бинарных слов длины ^ 3.

ООО 001 010 100 011 101 110 111Важнейшими понятиями, связанными с частичным порядком (1.1) и диаграммой Хассе, являются следующие:а) степени вершин;б) длины цепей, соединяющих вершины а и 6;в) мощность антицепей.

1. Егорычев Г.П. Интегральное представление и вычисление комбинаторных сумм. Новосибирск: Наука, 1977.

2. Зенкин А.И., Леонтьев В.К. Об одной неклассической задаче распознавания / / Журнал вычислительной математики и математической физики. 1984, Т.24, №6, С.925-931.

3. Калашник В.В. Восстановление слова по его фрагментам // Вычисл. математика и вычисл. техника. Харьков, 1973. Вып.4. С.56-57.

4. Левенштейн В.И. Элементы теории кодирования. // Дискретная математика и вычислительные вопросы кибернетики. М.: Наука, 1974.

5. Леонтьев В.К. Задача восстановления слов по фрагментам и их приложения // Дискретный анализ и исследование операций. 1995, Т.2. №2 , С.26-48.

6. Леонтьев В.К. О спектрах бинарных слов // Методы комбинаторной оптимизации. М.: ВЦ РАН, 1997. С.37-46.

7. Леонтьев В.К. Распознавание двоичных слов по их фрагментам // Доклады РАН. 1993, Т.ЗЗО, №4, С.434-436.

8. Леонтьев В.К., Сметанин Ю.Г. О восстановлении векторов по набору их фрагментов// Доклады АН СССР. 1988, Т.302, №6.

9. Мак-Вильямс Ф.Дж., Слоэн Н.Дж.А. Теория кодов, исправляющих ошибки. М.: Связь, 1979.

10. Питерсон У. Коды, исправляющие ошибки. М.: Мир, 1964.

11. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. М.: Мир, 1980. С. 196-211.

12. Сметанич Я.С. О восстановлении слов // Доклады АН СССР. 1971, Т.201, №4, С.798-800.N

13. Сметанич Я.С. О восстановлении слов // Труды Математического института им. В.А. Стеклова. 1984, Т.24, №6, С.925-931.

14. Стенли Р. Перечислительная комбинаторика. Новосибирск: Наука, 1977.

15. Сачков В.Н. Введение в комбинаторные методы дискретной математики. М.: Наука, 1982.

16. Lothaire М. Applied Combinatorics on Words. Version March 11, 1998. http://www-igm.umv-mlv.fr/ berstel/Lothaire/lol.ps

17. Lothaire M. Combinatotics on words // Encyclopedia of Mathematic and its Applications. Reading.MIT: Addison Wisley Publ. CO, 1983.