Dynamiczne algorytmy tekstowe

Speaker(s)

Piotr Sankowski

Affiliation

Uniwersytet Warszawski

Date

May 5, 2011, 12:15 p.m.

Room

room 5870

Seminar

Seminar Algorithms

---

Tematem tego seminarium będzie technika stworzona przez K. Mehlhorn, R. Sundar i C. Uhrigw pracy "Maintaining dynamic sequences under equality tests in polylogarithmic time", która umożliwia dynamiczne utrzymywanie informacji o sekwencjach i pozwala na wykonywanie na nich testów równości. Opowiem także o uogólnieniu i poprawieniu tego wyniku przez S. Alstrup, G. S. Brodal, i T. Rauhe w "Pattern Matching in Dynamic Text", które oprócz przyspieszania czasu działania pozwala na dynamiczne wyszukiwanie podsłów.

---