На главную страницу ЛШСМ-2003

Михаил Николаевич Вялый


Решение уравнений в словах

Продолжительность: 4 занятия.

Слово - последовательность символов из некоторого алфавита. Самая простая операция со словами: конкатенация, то есть дописывание одного слова после другого. Левая и правая часть уравнения в словах составляются конкатенациями переменных, которые предполагаются словами, и констант, которые принадлежат алфавиту.

Существует ли алгоритм решения любого уравнения в словах? Ответ положительный.

Эта задача оказалась не очень простой. В последнее время появились более простые (но по-прежнему нетривильные) решения этой задачи. В данном цикле занятий будет разобран пример такого алгоритма и (возможно) будет также разобран гораздо более эффективный алгоритм для решения уравнения в словах, когда заранее предписаны длины словарных переменных.