📄Работа №103973
Тема: О КОМБИНАТОРНЫХ СВОЙСТВАХ БЕСПОВТОРНЫХ ЯЗЫКОВ
Тип работы
Диссертация
Предмет
математика
Объем:
89 листов
Год:
2016
Просмотров:
162
5700
руб.
🛒 Купить работу
Не подходит эта работа?
Закажите новую по вашим требованиям
Узнать цену на написание
Закажите новую по вашим требованиям
Представленный материал является образцом учебного исследования, примером структуры и содержания учебного исследования по заявленной теме. Размещён исключительно в информационных и ознакомительных целях.
Workspay.ru оказывает информационные услуги по сбору, обработке и структурированию материалов в соответствии с требованиями заказчика.
Размещение материала не означает публикацию произведения впервые и не предполагает передачу исключительных авторских прав третьим лицам.
Материал не предназначен для дословной сдачи в образовательные организации и требует самостоятельной переработки с соблюдением законодательства Российской Федерации об авторском праве и принципов академической добросовестности.
Авторские права на исходные материалы принадлежат их законным правообладателям. В случае возникновения вопросов, связанных с размещённым материалом, просим направить обращение через форму обратной связи.
Настоящий учебно-методический информационный материал размещён в ознакомительных и исследовательских целях и представляет собой пример учебного исследования. Не является готовым научным трудом и требует самостоятельной переработки.
📋 Содержание
Введение 3
Предварительные сведения 4
Обзор исследований по теме диссертации 9
Обзор диссертации 17
1 Предмаксимальные слова 24
1.1 Общая схема построения предмаксимальных слов 24
1.2 Бинарный бескубный язык 27
1.2.1 Построение буферных слов 28
1.2.2 Доказательство корректности конструкции 31
1.2.3 Построение двусторонних предмаксимальных слов ... 38
1.3 Тернарный бесквадратный язык 39
1.3.1 Коды Пансьё и маршрутные коды 39
1.3.2 Обзор основной конструкции для предмаксимальных слов 42
1.3.3 Маршрутный код слова Аршона 44
1.3.4 Свойства слов р'п 46
1.3.5 Построение буферных слов и доказательство бесквад-
ратности 48
1.3.6 Построение предмаксимальных слов 53
2 Избегаемость буквенных шаблонов в бесквадратных словах 57
2.1 Построение бесквадратных кодов из слов Фибоначчи 58
2.2 Экспоненты слов, избегающих 5- и 6-буквенные шаблоны ... 61
2.3 Дальнейшие перспективы исследования буквенных шаблонов . 65
3 Структура префиксного дерева тернарного бесквадратного языка 66
3.1 Логарифмическая оценка длины фиксированного контекста . . 67
3.1.1 Короткие квадраты 67
3.1.2 Длинные квадраты 71
3.2 Частота ветвления префиксного дерева языка ЗБ 77
3.3 О возможном усилении Теоремы 14 78
Заключение 80
Список литературы 82
Предварительные сведения 4
Обзор исследований по теме диссертации 9
Обзор диссертации 17
1 Предмаксимальные слова 24
1.1 Общая схема построения предмаксимальных слов 24
1.2 Бинарный бескубный язык 27
1.2.1 Построение буферных слов 28
1.2.2 Доказательство корректности конструкции 31
1.2.3 Построение двусторонних предмаксимальных слов ... 38
1.3 Тернарный бесквадратный язык 39
1.3.1 Коды Пансьё и маршрутные коды 39
1.3.2 Обзор основной конструкции для предмаксимальных слов 42
1.3.3 Маршрутный код слова Аршона 44
1.3.4 Свойства слов р'п 46
1.3.5 Построение буферных слов и доказательство бесквад-
ратности 48
1.3.6 Построение предмаксимальных слов 53
2 Избегаемость буквенных шаблонов в бесквадратных словах 57
2.1 Построение бесквадратных кодов из слов Фибоначчи 58
2.2 Экспоненты слов, избегающих 5- и 6-буквенные шаблоны ... 61
2.3 Дальнейшие перспективы исследования буквенных шаблонов . 65
3 Структура префиксного дерева тернарного бесквадратного языка 66
3.1 Логарифмическая оценка длины фиксированного контекста . . 67
3.1.1 Короткие квадраты 67
3.1.2 Длинные квадраты 71
3.2 Частота ветвления префиксного дерева языка ЗБ 77
3.3 О возможном усилении Теоремы 14 78
Заключение 80
Список литературы 82
📖 Введение
Комбинаторика слов, относительно молодая и активно развивающаяся дисциплина, возникшая на рубеже XIX и XX веков, представляет собой важное
направление на стыке современной дискретной математики и теоретических
компьютерных наук, изучающее свойства символьных последовательностей
(слов). Методы и результаты, разработанные и полученные в комбинаторике слов, широко применимы во многих областях, например, в теории групп,
теории кодирования, теории игр, биоинформатике, сжатии данных.
Одним из основных объектов исследований в комбинаторике слов являются бесповторные языки — множества слов, не содержащих внутри себя повторяющихся фрагментов, или, как говорят, избегающих определённые
структурные элементы. Норвежский математик Аксель Туэ в начале XX века занимался конструированием и изучением нескольких конкретных бесповторных языков, и принято считать, что именно с этих работ комбинаторика
слов берёт своё начало как самостоятельная дисциплина. Туэ рассматривал,
например, бескубный язык над двухбуквенным (бинарным) алфавитом и бесквадратный язык над трёхбуквенным (тернарным) алфавитом — эти языки
состоят из слов, не содержащих трёх и двух идущих подряд одинаковых
фрагментов, соответственно, — и получил ряд нетривиальных результатов,
касающихся, в первую очередь, вопроса о конечности или бесконечности того
или иного языка. Со времён Туэ тема бесповторных языков получила весьма
широкое развитие во многих направлениях: было обобщено понятие степени,
изучены алфавиты большей мощности, обобщено понятие избегаемости с простых повторов до шаблонов, абелевых степеней и т.д., получены результаты о
комбинаторной сложности бесповторных языков, рассмотрены бесповторные
слова с дополнительными ограничениями. Тем не менее, в отношении языков, рассмотренных Туэ, до сих пор остаётся множество открытых проблем.
Некоторые из них решены в данной диссертации.
Любой бесповторный язык является факториальным, то есть замкнутым
относительно операции взятия подслова. На множестве слов факториального
языка можно ввести три естественных отношения: «быть префиксом», «быть
суффиксом», «быть подсловом», относительно которых это множество частич-
3ВВЕДЕНИЕ 4
но упорядочено, и диаграммы этих частично упорядоченных множеств (ч.у.м.)
в первых двух случаях представляют собой деревья, в третьем — ациклический граф более общего вида. Изучение структуры таких ч.у.м. оказывается
очень интересной темой в исследовании бесповторных языков, проливающей
свет на их внутреннее устройство. Среди задач в этом направлении можно
назвать вопросы об изоморфизме поддеревьев, порождённых двумя данными словами в дереве префиксного (суффиксного) порядка, о существовании
поддеревьев или подграфов произвольной конечной высоты, о частоте и регулярности ветвления деревьев префиксного (суффиксного) порядка и другие.
Основная часть диссертации посвящена проблемам, связанным со структурой
ч.у.м. слов бинарного бескубного языка и тернарного бесквадратного языка.
направление на стыке современной дискретной математики и теоретических
компьютерных наук, изучающее свойства символьных последовательностей
(слов). Методы и результаты, разработанные и полученные в комбинаторике слов, широко применимы во многих областях, например, в теории групп,
теории кодирования, теории игр, биоинформатике, сжатии данных.
Одним из основных объектов исследований в комбинаторике слов являются бесповторные языки — множества слов, не содержащих внутри себя повторяющихся фрагментов, или, как говорят, избегающих определённые
структурные элементы. Норвежский математик Аксель Туэ в начале XX века занимался конструированием и изучением нескольких конкретных бесповторных языков, и принято считать, что именно с этих работ комбинаторика
слов берёт своё начало как самостоятельная дисциплина. Туэ рассматривал,
например, бескубный язык над двухбуквенным (бинарным) алфавитом и бесквадратный язык над трёхбуквенным (тернарным) алфавитом — эти языки
состоят из слов, не содержащих трёх и двух идущих подряд одинаковых
фрагментов, соответственно, — и получил ряд нетривиальных результатов,
касающихся, в первую очередь, вопроса о конечности или бесконечности того
или иного языка. Со времён Туэ тема бесповторных языков получила весьма
широкое развитие во многих направлениях: было обобщено понятие степени,
изучены алфавиты большей мощности, обобщено понятие избегаемости с простых повторов до шаблонов, абелевых степеней и т.д., получены результаты о
комбинаторной сложности бесповторных языков, рассмотрены бесповторные
слова с дополнительными ограничениями. Тем не менее, в отношении языков, рассмотренных Туэ, до сих пор остаётся множество открытых проблем.
Некоторые из них решены в данной диссертации.
Любой бесповторный язык является факториальным, то есть замкнутым
относительно операции взятия подслова. На множестве слов факториального
языка можно ввести три естественных отношения: «быть префиксом», «быть
суффиксом», «быть подсловом», относительно которых это множество частич-
3ВВЕДЕНИЕ 4
но упорядочено, и диаграммы этих частично упорядоченных множеств (ч.у.м.)
в первых двух случаях представляют собой деревья, в третьем — ациклический граф более общего вида. Изучение структуры таких ч.у.м. оказывается
очень интересной темой в исследовании бесповторных языков, проливающей
свет на их внутреннее устройство. Среди задач в этом направлении можно
назвать вопросы об изоморфизме поддеревьев, порождённых двумя данными словами в дереве префиксного (суффиксного) порядка, о существовании
поддеревьев или подграфов произвольной конечной высоты, о частоте и регулярности ветвления деревьев префиксного (суффиксного) порядка и другие.
Основная часть диссертации посвящена проблемам, связанным со структурой
ч.у.м. слов бинарного бескубного языка и тернарного бесквадратного языка.
✅ Заключение
Кратко подведём итоги работы по каждой из глав диссертации.
Предмаксимальные слова
Доказано существование конечных поддеревьев произвольной высоты в суффиксном (префиксном) дереве, а также конечных подграфов c цепями из суффиксных и префиксных ребёр произвольной длины в ациклическом подсловном графе языков бинарных бескубных слов CF и тернарных бесквадратных
слов SF.
Предмаксимальные слова
Доказано существование конечных поддеревьев произвольной высоты в суффиксном (префиксном) дереве, а также конечных подграфов c цепями из суффиксных и префиксных ребёр произвольной длины в ациклическом подсловном графе языков бинарных бескубных слов CF и тернарных бесквадратных
слов SF.
ИЛИ
Поиск аналога
📕 Список литературы
🛒 Оформить заказ
⚡ Работу высылаем в течении 5 минут после оплаты.