Комбинаторика слов: сложность и слова Штурма

Основным объектом комбинаторики слов являются конечные или бесконечные последовательности символов из конечного множества, называемого алфавитом. Это слова и тексты на естественных языках, компьютерные программы, молекулы ДНК и белков, записи чисел в двоичной системе счисления, и т. д. Комбинаторика слов представляет собой математический аппарат для работы с символьными последовательностями и является динамично развивающейся дисциплиной на стыке дискретной математики и компьютерных наук. В лекции мы рассмотрим понятие сложности слов, его связь с периодичностью, а также слова Штурма — слова минимальной сложности среди непериодических слов.

Анонс