Удивительная математика в алгоритмах на строках. Семинар 1

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

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