Город: Санкт-Петербург Новосибирск Казань Язык: Русский English

Комбинаторика слов и ее приложения
Санкт-Петербург / весна 2015, посмотреть все семестры

Запишитесь на курс, чтобы получать уведомления и иметь возможность сдавать домашние задания. Для записи требуется регистрация на сайте.
Перейти к регистрации Войти

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

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

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

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

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

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

Дата и время Занятие Место Материалы
18 марта
18:30–20:00
Введение и предварительные сведения, Лекция ПОМИ РАН слайды,  видео
18 марта
20:15–21:45
Введение и предварительные сведения (продолжение), Лекция ПОМИ РАН слайды,  видео
19 марта
18:30–20:00
Упорядоченность, Лекция ПОМИ РАН слайды,  видео
19 марта
20:15–21:45
Упорядоченность (продолжение), Лекция ПОМИ РАН слайды,  видео
21 марта
17:20–18:55
Перестановки, Лекция ПОМИ РАН видео
21 марта
19:15–20:50
Перестановки (продолжение), Лекция ПОМИ РАН видео
23 марта
18:30–20:00
Повторы, Лекция ПОМИ РАН видео
23 марта
20:15–21:45
Повторы (продолжение), Лекция ПОМИ РАН видео
26 марта
18:30–20:00
Бесповторность, Лекция ПОМИ РАН слайды,  видео
26 марта
20:15–21:30
Бесповторность (продолжение), Лекция ПОМИ РАН видео
28 марта
17:20–18:55
Комбинаторная сложность, Лекция ПОМИ РАН слайды,  видео
28 марта
19:15–20:45
Комбинаторная сложность (продолжение), Лекция ПОМИ РАН видео