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

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

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

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

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

В рамках учебного курса невозможно изложить научную дисциплину целиком, поэтому наша основная цель – дать слушателям представление об основных особенностях слов и о том, как и зачем нужно изучать слова (в том числе бесконечные, циклические и частичные). Большое внимание в курсе уделено связям “внутренних” объектов и результатов с “внешними” постановками задач из различных разделов математики и компьютерных наук.

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

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

Примерный план лекций (по дням).

1. Введение и предварительные сведения. Символьные последовательности в различных областях науки и практики, виды задач о символьных последовательностях. Уравнение коммутирования. Примитивные слова. Сопряженные слова. Уравнение сопряженности. Периодичность и взаимодействие периодов. Длина взаимодействия. Теорема Файна-Вильфа. Частичные слова и их периоды. Теорема взаимодействия для частичных слов. Другой взгляд: сервисный робот, китайские остатки и случайные графы.
2. Упорядоченность. Лексикографический порядок. Слова Линдона-Ширшова. Теорема Линдона о каноническом разбиении слова. Периодичность плюс порядок. Локальные периоды. Теорема о критическом разбиении. Задача поиска по образцу с использованием константной памяти. Критическое разбиение и алгоритм Крошмора. Алгоритм Бреслауэра для реального времени.
3. Перестановки. Элементарные свойства. Преобразование Барроуза-Уилера (BWT). Эффективность обратного преобразования. Проверка корректности. “Параллельное” BWT: снова разбиение Линдона. Сжатие данных на основе BWT. Структуры данных на основе BWT: FM-индекс.
4. Повторы. Что считать повтором? Разбиение Лемпеля-Зива и метод LZ77. Online square detection. Максимальные повторения. Runs theorem: опять слова Линдона. Поиск всех максимальных повторений. Палиндромы. Богатые и бедные слова. Разбиение на палиндромы. Что содержится в случайных словах?
5. Бесповторность. Квадраты и кубы. Слова Туэ-Морса, теорема о сильной бескубности. Избегаемые экспоненты. Слова Аршона, теорема о 7/4. Граничная теорема (гипотеза Дежан). Цилиндрические слова. Бесповторные раскраски графов. Циклические слова и граф К33 Шаблоны, их избегание. Неизбежные шаблоны. Слова Зимина. Критерий неизбежности (Бина- Эренфойхта-Макналти-Зимина). Алгоритмические проблемы о словах Зимина. Генератор случайных бесквадратных слов.
6. Комбинаторная сложность. Классы сложности. Слова/языки ограниченной сложности. Слово Фибоначчи и слова Штурма. Фибоначчи, Зимин и нетрадиционные системы счисления. Индекс роста и его свойства. Факториальные языки и антисловари. Комбинаторная сложность регулярных языков. Индексы роста граничных языков.
7. Коды. Понятие кода. Задержка. Теорема о дефекте. Неравенство Крафта-Макмиллана. Критерий Шютценберже. Алгоритм Паттерсона-Сардинаса. Префиксные коды. Коды Хаффмана и их оптимальность для кодирования сообщений.

Этот курс является курсом Академического университета и читается при поддержке гранта фонда Династия.