Помощь студентам в учебе
Учебно-методический материал.
Предоставляется в ознакомительных и исследовательских целях
Предоставляется в ознакомительных и исследовательских целях
📄 Образец работы №104005
Вычислительная сложность некоторых задач обработки строк
Материал размещён в информационных целях и представляет собой пример учебного исследования. Не является готовым научным трудом и требует самостоятельной переработки пользователем.
Тип работы
Диссертация
Предмет
математика
Объем
83 листов
Год подготовки
2016
Просмотров
165
5700
руб.
🛒 Купить работу
Представленный материал является образцом учебного исследования, примером структуры и содержания учебного исследования по заявленной теме. Размещён исключительно в информационных и ознакомительных целях.
Workspay.ru оказывает информационные услуги по сбору, обработке и структурированию материалов в соответствии с требованиями заказчика.
Размещение материала не означает публикацию произведения впервые и не предполагает передачу исключительных авторских прав третьим лицам.
Материал не предназначен для дословной сдачи в образовательные организации и требует самостоятельной переработки с соблюдением законодательства Российской Федерации об авторском праве и принципов академической добросовестности.
Авторские права на исходные материалы принадлежат их законным правообладателям. В случае возникновения вопросов, связанных с размещённым материалом, просим направить обращение через форму обратной связи.
📋 Содержание (образец)
1 Введение 5
1.1 Структура диссертации и организация текста 6
1.2 Предварительные сведения 9
1.2.1 Понятия из стрингологии 9
1.2.2 Модель вычисления ШоЫ-ИЛМ 10
1.2.3 Типы алгоритмических задач 11
1.2.4 Структуры данных 12
1.2.5 Исходные коды программ 13
1.2.6 Используемые структуры данных 13
1.3 Обзор результатов диссертации 15
1.3.1 Цели, задачи и основные результаты 16
1.3.2 Научная новизна, значимость и корректность результатов 17
1.3.3 Основные методы исследования 17
1.3.4 Апробация и публикации 17
1.4 Благодарности 19
2 Палиндромы 20
2.1 Введение 20
2.1.1 Определения и обозначения 21
2.2 Овердрево 21
2.2.1 Побуждающая задача: поиск подпалиндромов онлайн 21
2.2.2 Интерфейс структуры данных 26
2.2.3 Внутреннее устройство структуры данных 26
2.2.4 Простой онлайн-алгоритм 27
2.2.5 Некоторые свойства овердрева 29
2.2.6 Задачи, иллюстрирующие возможности овердрева 31
2.3 Вариации овердрева и некоторые их приложения 36
2.3.1 Совместное овердрево для нескольких строк 36
2.3.2 Поиск с откатами 38
2.3.3 Подсчёт палиндромно-насыщенных строк 42
2.3.4 Поиск подпалиндромов на дереве 45
2.4 Задачи о разбиении на подпалиндромы 47
2.4.1 Простое решение за O(kn + n log n) 48
2.4.2 Разбиение на k палиндромов и поиск палиндромной длины 49
2.4.3 Решение задачи о палиндромной длине 50
2.4.4 Гипотеза о линейном решении 55
3 Повреждённые строки 60
3.1 Введение 60
3.2 Предварительные сведения 61
3.2.1 Основные определения 61
3.2.2 Исторический обзор 61
3.3 Задача максимизации числа вхождений 63
3.3.1 Решение для неповреждённого текста 63
3.3.2 Решение для неповреждённого шаблона 64
3.3.3 Доказательство NP-трудности в общем случае 65
3.4 Задача минимизации расстояния Хэмминга 68
3.4.1 Случай неповреждённого текста 68
3.4.2 Случай неповреждённого шаблона 69
3.4.3 Случай частичных строк с циклическим текстом 69
3.4.4 Случай бинарного алфавита 70
3.4.5 Случай частичных строк и задача о мультиразрезе 71
3.4.6 Доказательство NP-трудности в общем случае 72
Заключение 75
Список литературы 77
Список иллюстраций
Список таблиц
1.1 Структура диссертации и организация текста 6
1.2 Предварительные сведения 9
1.2.1 Понятия из стрингологии 9
1.2.2 Модель вычисления ШоЫ-ИЛМ 10
1.2.3 Типы алгоритмических задач 11
1.2.4 Структуры данных 12
1.2.5 Исходные коды программ 13
1.2.6 Используемые структуры данных 13
1.3 Обзор результатов диссертации 15
1.3.1 Цели, задачи и основные результаты 16
1.3.2 Научная новизна, значимость и корректность результатов 17
1.3.3 Основные методы исследования 17
1.3.4 Апробация и публикации 17
1.4 Благодарности 19
2 Палиндромы 20
2.1 Введение 20
2.1.1 Определения и обозначения 21
2.2 Овердрево 21
2.2.1 Побуждающая задача: поиск подпалиндромов онлайн 21
2.2.2 Интерфейс структуры данных 26
2.2.3 Внутреннее устройство структуры данных 26
2.2.4 Простой онлайн-алгоритм 27
2.2.5 Некоторые свойства овердрева 29
2.2.6 Задачи, иллюстрирующие возможности овердрева 31
2.3 Вариации овердрева и некоторые их приложения 36
2.3.1 Совместное овердрево для нескольких строк 36
2.3.2 Поиск с откатами 38
2.3.3 Подсчёт палиндромно-насыщенных строк 42
2.3.4 Поиск подпалиндромов на дереве 45
2.4 Задачи о разбиении на подпалиндромы 47
2.4.1 Простое решение за O(kn + n log n) 48
2.4.2 Разбиение на k палиндромов и поиск палиндромной длины 49
2.4.3 Решение задачи о палиндромной длине 50
2.4.4 Гипотеза о линейном решении 55
3 Повреждённые строки 60
3.1 Введение 60
3.2 Предварительные сведения 61
3.2.1 Основные определения 61
3.2.2 Исторический обзор 61
3.3 Задача максимизации числа вхождений 63
3.3.1 Решение для неповреждённого текста 63
3.3.2 Решение для неповреждённого шаблона 64
3.3.3 Доказательство NP-трудности в общем случае 65
3.4 Задача минимизации расстояния Хэмминга 68
3.4.1 Случай неповреждённого текста 68
3.4.2 Случай неповреждённого шаблона 69
3.4.3 Случай частичных строк с циклическим текстом 69
3.4.4 Случай бинарного алфавита 70
3.4.5 Случай частичных строк и задача о мультиразрезе 71
3.4.6 Доказательство NP-трудности в общем случае 72
Заключение 75
Список литературы 77
Список иллюстраций
Список таблиц
📖 Введение (образец)
Строка (последовательность символов) — один из центральных объектов компьютерных наук.
Любые данные, имеющие линейную структуру (например, текст на естественном или искусственном языке, лог сервера или колебания курса валюты) можно представить в виде строки
и изучать особенности в этой строке. Начало активного изучения алгоритмов, связанных со
строками, приходится на 1970е годы. Раздел компьютерных наук, посвящённый изучению алгоритмов обработки строк, называется стрингологией (stringology). Впервые это название было
предложено в 1985 в работе [21], когда область уже имела какой-то набор результатов, но сложно было назвать её отдельной наукой. Однако уже в 90х годах наблюдается стремительный рост
числа публикаций по данной тематике. Одной из самых сильных предпосылок развития является появление биоинформатики, науки, изучающей «биологические строки» (ДНК, РНК, белки
и др.). Именно биоинформатика породила множество задач, изучаемых стрингологами. Не менее важным источником задач являются современные информационные технологии, требующие
эффективных алгоритмов анализа и обработки данных. Среди задач этой группы выделяются
задача поиска в массиве данных и задача сжатия данных. Кроме того, стрингология, относимая к фундаментальной информатике, решает большое число чисто математических задач, не
нашедших еще практического применения. Сюда относится, в частности, классификация задач
о строках по их вычислительной сложности. Многие теоретические задачи приходят в стрингологию из комбинаторики слов.
Развитость стрингологии как самостоятельной науки может показать, к примеру, наличие
ряда монографий [2, 12, 13, 48] и специализированных международных конференций и семинаров: String Processing and Information Retrieval (SPIRE), Combinatorial Pattern Matching (CPM),
5Prague Stringology Conference (PSC), StringMasters.
Данная работа сконцентрирована на двух классах задач из стрингологии. Первая — алгоритмы, связанные с поиском и анализом палиндромов1 в строках.
Любые данные, имеющие линейную структуру (например, текст на естественном или искусственном языке, лог сервера или колебания курса валюты) можно представить в виде строки
и изучать особенности в этой строке. Начало активного изучения алгоритмов, связанных со
строками, приходится на 1970е годы. Раздел компьютерных наук, посвящённый изучению алгоритмов обработки строк, называется стрингологией (stringology). Впервые это название было
предложено в 1985 в работе [21], когда область уже имела какой-то набор результатов, но сложно было назвать её отдельной наукой. Однако уже в 90х годах наблюдается стремительный рост
числа публикаций по данной тематике. Одной из самых сильных предпосылок развития является появление биоинформатики, науки, изучающей «биологические строки» (ДНК, РНК, белки
и др.). Именно биоинформатика породила множество задач, изучаемых стрингологами. Не менее важным источником задач являются современные информационные технологии, требующие
эффективных алгоритмов анализа и обработки данных. Среди задач этой группы выделяются
задача поиска в массиве данных и задача сжатия данных. Кроме того, стрингология, относимая к фундаментальной информатике, решает большое число чисто математических задач, не
нашедших еще практического применения. Сюда относится, в частности, классификация задач
о строках по их вычислительной сложности. Многие теоретические задачи приходят в стрингологию из комбинаторики слов.
Развитость стрингологии как самостоятельной науки может показать, к примеру, наличие
ряда монографий [2, 12, 13, 48] и специализированных международных конференций и семинаров: String Processing and Information Retrieval (SPIRE), Combinatorial Pattern Matching (CPM),
5Prague Stringology Conference (PSC), StringMasters.
Данная работа сконцентрирована на двух классах задач из стрингологии. Первая — алгоритмы, связанные с поиском и анализом палиндромов1 в строках.
✅ Заключение (образец)
В заключении, представив краткое резюме по каждой из двух основных глав, обсудим пути
дальнейшей возможной работы в соответствующих направлениях и сформулируем связанные
оставшиеся открытыми проблемы.
Палиндромы
В данной главе мы описали новую компактную и быструю структуру данных — овердрево. Рассмотрели его различные модификации, которые более эффективны в использовании времени,
либо памяти. Одна из модификаций позволяет сделать овердрево с откатами, другая делает его
персистентным. Разобрали множество возможных применений, получив теоретически быстрые
и практически легко реализуемые алгоритмы для ряда комбинаторных задач. Самыми существенными из представленных применений являются простая реализация разбиения строки на
палиндромы, перечисление палиндромно-насыщенных строк, а также поиск всех различных
подпалиндромов строки.
Дальнейшие исследования в этом направлении связаны с поиском новых приложений овердрева, а также с гипотезой о возможности линейного поиска палиндромной длины и с открытой
проблемой об оптимальной реализации овердрева.
Повреждённые строки
В данной работе рассмотрены две задачи о восстановлении повреждений в тексте и шаблоне.
Для обеих задач общий случай оказался NP-трудным, а случаи неповреждённого текста и
неповреждённого шаблона — эффективно разрешимыми. При этом во второй задаче, где критерием восстановления является минимизация суммарного расстояния Хэмминга, полиномиально
разрешимых частных случаев оказалось больше.
Отдельно отметим, что для решения различных частных случаев использованы совершенно
75разные полиномиальные алгоритмы, основанные на жадных стратегиях, преобразовании Фурье,
динамическом программировании и потоках в сетях.
Дальнейшее исследование предполагает продолжение изучения задачи о минимизации непохожести шаблона и текста для частичных строк (частный случай, оставшийся открытым), а
также выделение дополнительных частных случаев обеих задач с целью выявления более простых подходов к решению.
дальнейшей возможной работы в соответствующих направлениях и сформулируем связанные
оставшиеся открытыми проблемы.
Палиндромы
В данной главе мы описали новую компактную и быструю структуру данных — овердрево. Рассмотрели его различные модификации, которые более эффективны в использовании времени,
либо памяти. Одна из модификаций позволяет сделать овердрево с откатами, другая делает его
персистентным. Разобрали множество возможных применений, получив теоретически быстрые
и практически легко реализуемые алгоритмы для ряда комбинаторных задач. Самыми существенными из представленных применений являются простая реализация разбиения строки на
палиндромы, перечисление палиндромно-насыщенных строк, а также поиск всех различных
подпалиндромов строки.
Дальнейшие исследования в этом направлении связаны с поиском новых приложений овердрева, а также с гипотезой о возможности линейного поиска палиндромной длины и с открытой
проблемой об оптимальной реализации овердрева.
Повреждённые строки
В данной работе рассмотрены две задачи о восстановлении повреждений в тексте и шаблоне.
Для обеих задач общий случай оказался NP-трудным, а случаи неповреждённого текста и
неповреждённого шаблона — эффективно разрешимыми. При этом во второй задаче, где критерием восстановления является минимизация суммарного расстояния Хэмминга, полиномиально
разрешимых частных случаев оказалось больше.
Отдельно отметим, что для решения различных частных случаев использованы совершенно
75разные полиномиальные алгоритмы, основанные на жадных стратегиях, преобразовании Фурье,
динамическом программировании и потоках в сетях.
Дальнейшее исследование предполагает продолжение изучения задачи о минимизации непохожести шаблона и текста для частичных строк (частный случай, оставшийся открытым), а
также выделение дополнительных частных случаев обеих задач с целью выявления более простых подходов к решению.
📕 Список литературы (образец)
🛒 Оформить заказ
⚡ Работу высылаем на протяжении 30 минут после оплаты.