Друзья!
В этот вторник (15.04.25) на учебном семинаре выступит Минасян Левон.

Прилагаем анонс его доклада:

Мы обсудим одну из красивейших в CS конструкций - суффиксное дерево.
До появления этой структуры(1973) Дональд Кнут выдвигал гипотезы о том, что некоторые задачи в теории алгоритмов строк являются неразрешимыми за линейное время. Ее появление в 1973 и оптимальный алгоритм ее построения, оба созданные П. Винером опровергли гипотезы Кнута. Суффиксное дерево позволяет оптимально решать огромное число различных задач на строках. Его преимущество в том, что им удобно пользоваться, однако его построение нетривиально, и оно станет центральным объектом моего рассказа. Мы обсудим алгоритм, предложенный Э. Укконеном в 1995 - он является самым простым для понимания из всех, и при этом оптимален. В конце, если останется время, мы поговорим про связанные задачи и про альтернативные структуры.

Ждем вас 15.04.25 в 16 20 в аудитории 108


#нис_complex_networks