Компьютерные методы в комбинаторике слов

Последнее изменение: 24/10/2011 00:00:00

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

Шур Арсений Михайлович, доктор физико-математических наук, профессор кафедры алгебры и дискретной математики УрФУ

Студенческий коллектив:

  1. Петрова Елена Александровна
  2. Рубинчик Михаил Валентинович
  3. Тунев Игорь Николаевич

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

Задача 1 состоит в доказательстве, по крайней мере для некоторых алфавитов, экспоненциальной гипотезы, усиливающей гипотезу Дежан о границе между избегаемыми и неизбежными степенями для произвольных конечных алфавитов. Эта знаменитая гипотеза была сформулирована в 1972 году, а полностью доказана лишь в 2009. Усиление состоит в дополнительном требовании, чтобы число слов в избегающих языках было экспоненциально большим.

Задача 2 – это задача нахождения специальных «предмаксимальных» элементов в языках, избегающих степени. Предполагается решить ее для языка бесквадратных слов над трехбуквенным алфавитом – эта задача в явном виде поставлена в книге J.-P. Allouche, J. Shallit. Automatic Sequences: Theory, Applications, Generalizations, Cambridge Univ. Press, 2003.

Задачи 3 и 4 представляют собой варианты задачи о поиске подстроки в строке. В этих вариантах строка и искомый «образец» имеют повреждения – символы, которые можно восстановить не одним, а несколькими способами. В задаче 3 требуется убрать повреждения в строке и образце таким образом, чтобы образец имел максимальное количество вхождений в строку, а в задаче 4 – чтобы минимизировать «непохожесть» строки и образца в терминах расстояния Хэмминга.

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