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

Общая информация
ЛекторА. М. Шур
Семестрвесна 2015
Дата начала18.03.2015
Количество пар12
Язык курсарусский
Вопросы к экзамену
Аннотация

Цели курса

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

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

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

1. Лекции 1. Введение и предварительные сведения
(18.03.2015 - 18:30 - 20:00)

Символьные последовательности в различных областях науки и практики, виды задач о символьных последовательностях. Уравнение коммутирования. Примитивные слова. Сопряженные слова. Уравнение сопряженности. Периодичность и взаимодействие периодов. Длина взаимодействия. Теорема Файна-Вильфа. Частичные слова и их периоды. Теорема взаимодействия для частичных слов. Другой взгляд: сервисный робот, китайские остатки и случайные графы.

Слайды: Лекция 1.

https://www.youtube.com/watch?v=jmowTApRhR0
2. Лекция 2. Введение и предварительные сведения (продолжение)
(18.03.2015 - 20:15 - 21:45)

Слайды: Лекция 2.

https://www.youtube.com/watch?v=EWBYeUWkrxc
3. Лекции 3. Упорядоченность
(19.03.2015 - 18:30 - 20:00)

Лексикографический порядок. Слова Линдона-Ширшова. Теорема Линдона о каноническом разбиении слова. Периодичность плюс порядок. Локальные периоды. Теорема о критическом разбиении. Задача поиска по образцу с использованием константной памяти. Критическое разбиение и алгоритм Крошмора. Алгоритм Бреслауэра для реального времени.

Слайды: Лекция 3.

https://www.youtube.com/watch?v=3b3eCD8U7Hg
4. Лекция 4. Упорядоченность (продолжение)
(19.03.2015 - 20:15 - 21:45)

Слайды:Лекция 4.

https://www.youtube.com/watch?v=b6jyZz1GLPY
5. Лекции 5. Перестановки
(21.03.2015 - 17:20 - 18:55)

Перестановки. Элементарные свойства. Преобразование Барроуза-Уилера (BWT). Эффективность обратного преобразования. Проверка корректности. “Параллельное” BWT: снова разбиение Линдона. Сжатие данных на основе BWT. Структуры данных на основе BWT:

https://www.youtube.com/watch?v=IGYazW4zhzA
6. Лекция 6. Перестановки (продолжение)
(21.03.2015 - 19:15 - 20:50)

https://www.youtube.com/watch?v=2M_FJ0lO4n8
7. Лекции 7. Повторы
(23.03.2015 - 18:30 - 20:00)

Повторы. Что считать повтором? Разбиение Лемпеля-Зива и метод LZ77. Online square detection. Максимальные повторения. Runs theorem: опять слова Линдона. Поиск всех максимальных повторений. Палиндромы. Богатые и бедные слова. Разбиение на палиндромы. Что содержится в случайных словах?

https://www.youtube.com/watch?v=jvdK7-Bzzms
8. Лекция 8. Повторы (продолжение)
(23.03.2015 - 20:15 - 21:45)

https://www.youtube.com/watch?v=4za3iv3ZAko
9. Лекции 9. Бесповторность
(26.03.2015 - 18:30 - 20:00)

Бесповторность. Квадраты и кубы. Слова Туэ-Морса, теорема о сильной бескубности. Избегаемые экспоненты. Слова Аршона, теорема о 7/4. Граничная теорема (гипотеза Дежан). Цилиндрические слова. Бесповторные раскраски графов. Циклические слова и граф К33 Шаблоны, их избегание. Неизбежные шаблоны. Слова Зимина. Критерий неизбежности (Бина- Эренфойхта-Макналти-Зимина). Алгоритмические проблемы о словах Зимина. Генератор случайных бесквадратных слов.

Слайды: Лекция 9.

https://www.youtube.com/watch?v=nvy0JFiMAnQ
10. Лекция 10. Бесповторность (продолжение)
(26.03.2015 - 20:15 - 21:45)

https://www.youtube.com/watch?v=U9JmvPXdNJM
11. Лекции 11. Комбинаторная сложность
(28.03.2015 - 17:20 - 18:55)

Комбинаторная сложность. Классы сложности. Слова/языки ограниченной сложности. Слово Фибоначчи и слова Штурма. Фибоначчи, Зимин и нетрадиционные системы счисления. Индекс роста и его свойства. Факториальные языки и антисловари. Комбинаторная сложность регулярных языков. Индексы роста граничных языков.

Слайды: Лекция 11.

https://www.youtube.com/watch?v=Ij53kBI_3-s
12. Лекция 12. Комбинаторная сложность (продолжение)
(28.03.2015 - 19:15 - 20:50)

https://www.youtube.com/watch?v=9Zdcegf11AA
Ваша оценка: Пусто Средняя: 4.9 (7 votes)
Share |
Арсений Шур и студенты