Комбинаторика слов и ее приложения

Комбинаторика слов (символьных последовательностей) является одной из современных и быстро развивающихся дисциплин теоретических компьютерных наук.

Целями курса являются:

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

Краткое описание курса

Символьные последовательности (слова), являющиеся основным объектом исследования комбинаторики слов, окружают нас повсюду. Это лексемы, фразы и тексты на естественных языках, исходники программ и библиотеки, логи серверов и протоколы обмена данными, математические и химические формулы, молекулы ДНК и белков, символические траектории точек в фазовом пространстве, записи чисел в позиционной системе счисления, и многое другое. Для эффективной работы с таким изобилием и разнообразием слов необходим соответствующий математический аппарат, который и предоставляет комбинаторика слов. Зарождение комбинаторики слов связывают с выдающимися работами норвежского математика А. Туэ (1863-1922) о бесповторных словах. Оформление комбинаторики слов как самостоятельной дисциплины произошло в начале 1980-х, когда группа французских математиков под руководством М. Шютценберже написала книгу “Combinatorics on words” в рамках проекта “Энциклопедия математики и ее приложений”. В настоящее время комбинаторика слов - динамично развивающаяся дисциплина на стыке дискретной математики и компьютерных наук. В рамках учебного курса невозможно изложить научную дисциплину целиком, поэтому наша основная цель – дать слушателям представление об основных особенностях слов и о том, как и зачем нужно изучать слова (в том числе бесконечные, циклические и частичные). Большое внимание в курсе уделено связям “внутренних” объектов и результатов с “внешними” постановками задач из различных разделов математики и компьютерных наук.

Материал курса сгруппирован вокруг следующих свойств и понятий:

• некоммутативность умножения слов и ее следствия;
• лексикографический порядок на словах, его свойства и использование;
• повторы в словах: периоды и свойства периодических слов, квадраты, палиндромы;
• бесповторность и другие варианты избегаемости;
• функции подсчета слов;
• коды и кодирование (если успеем).