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

Согласно Ю.И.Манину, являющегося содиректором Боннского математического института, математика — это отрасль лингвистики или филологии, занимающаяся преобразованием конечных цепочек символов некоторого конечного алфавита в другие такие цепочки при помощи конечного числа грамматических» правил.

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

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

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

лекция 1


лекция 2

лекция 3

лекция 4

лекция 5