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