City: Saint Petersburg Novosibirsk Kazan Language: Русский English

Word combinatorics and its applications
Saint Petersburg / spring 2015, посмотреть все семестры

Enroll in the course to get notifications and to be able to submit home assignments.
Register to enroll now Login

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

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

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

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

Символьные последовательности (слова), являющиеся основным объектом исследования комбинаторики слов, окружают нас повсюду. Это лексемы, фразы и тексты на естественных языках, исходники программ и библиотеки, логи серверов и протоколы обмена данными, математические и химические формулы, молекулы ДНК и белков, символические траектории точек в фазовом пространстве, записи чисел в позиционной системе счисления, и многое другое. Для эффективной работы с таким изобилием и разнообразием слов необходим соответствующий математический аппарат, который и предоставляет комбинаторика слов. Зарождение комбинаторики слов связывают с выдающимися работами норвежского математика А. Туэ (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. Коды. Понятие кода. Задержка. Теорема о дефекте. Неравенство Крафта-Макмиллана. Критерий Шютценберже. Алгоритм Паттерсона-Сардинаса. Префиксные коды. Коды Хаффмана и их оптимальность для кодирования сообщений.

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