Введение в комбинаторику слов

Общая информация
ЛекторА. Э. Фрид
Семестросень 2011
Дата начала15.10.2011
Количество пар5
Язык курсарусский
Вопросы к экзамену
Анонсы
Встреча ВКонтактеhttp://vkontakte.ru/event30688364
Анонс на сайте it-event.ruhttp://it-event.ru/2782/
Аннотация

В курсе рассматриваются несколько базовых понятий комбинаторики слов, как имеющих прямое отношение к прикладным алгоритмическим задачам, так и представляющих чисто эстетический интерес.

Существует ли слово над конечным алфавитом, в котором никогда не встречаются два одинаковых подслова подряд? Как оценить количество слов данной длины, в которых никогда не встречаются подслова заданного вида? Сколько разных слов может встречаться как подслова данного слова? А по арифметическим прогрессиям? Какая математика стоит за дискретизацией прямых с иррациональным наклоном?

Лекции Подсказка: слайды, видеозапись и другие материалы лекции доступны со страницы лекции, попасть на которую можно, нажав на её название.

1. Теория избегаемости
(15.10.2011 - 17:20 - 18:55)

Бесконечные слова, подслова, морфизмы и их неподвижные точки. Слова, избегающие степеней. Слова, избегающие паттернов. Алгоритмы оценки их количества. Вариации на тему избегаемости.

Существует ли бесконечное слово над конечным алфавитом, в котором нет двух одинаковых подслов подряд? А двух подслов, одинаковых по составу? А двух подслов, одинаковых по весу - если считать символы натуральными числами?

http://www.lektorium.tv/lecture/?id=13460
2. Автоматные слова
(15.10.2011 - 19:05 - 20:40)

Предположим, конечный автомат получает на вход $ k $-ичное разложение числа $ n $ и выдает символ $ w_n $. Последовательность символов $ w_0w_1w_2\dots $ называется $ k $-автоматным словом. Каковы свойства таких слов? Как еще их можно охарактеризовать? Какие их свойства могут быть проверены конечными автоматами, полученными из исходного — вот, скажем, относится ли к ним избегание паттернов из предыдущей лекции? http://www.lektorium.tv/lecture/?id=13461
3. Слова Штурма
(16.10.2011 - 11:15 - 12:50)

Слова Штурма появляются при дискретизации прямых и могут быть определены множеством эквивалентных способов. В частности, рассматривается быстрый способ их порождения с помощью цепных дробей. http://www.lektorium.tv/lecture/?id=13462
4. Слова Штурма (продолжение). Вращательные слова.
(16.10.2011 - 13:00 - 14:35)

Излагается способ подсчета количества всех слов Штурма длины $ n $ через подсчет количества граней в графе, образованном рациональными прямыми. Обсуждаются границы применения этого метода. Вводится более общее понятие вращательных слов. http://www.lektorium.tv/lecture/?id=13463
5. Комбинаторные определения сложности бесконечных слов
(16.10.2011 - 15:35 - 17:10)

Обсуждаются несколько родственных функций сложности бесконечных слов: комбинаторная или подсловная, арифметическая, максимальная шаблонная сложность. Их свойства. Метод биспециальных слов, метод бесконечных специальных ветвей. http://www.lektorium.tv/lecture/?id=13464
Ваша оценка: Пусто Средняя: 5 (5 votes)
Share |
Анна Эдуардовна Фрид