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

• Мухина, Светлана Анатольевна
• кандидат физико-математических наук
• 2009

Оглавление диссертации кандидат физико-математических наук Мухина, Светлана Анатольевна

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;в) мощность антицепей.

Список литературы диссертационного исследования кандидат физико-математических наук Мухина, Светлана Анатольевна, 2009 год

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.