Informatik-Kolloquien
332. Informatik-Kolloquium
Öffentliche Verteidigung im Rahmen des Promotionsverfahrens
Herr Julian Pape-Lange, M.Sc.
TU Chemnitz
Fakultät für Informatik
Professur Theoretische Informatik
"Combinatorial Properties of Periodic Patterns in Compressed Strings"
Montag, 03.07.2023, 15:00 Uhr, Straße der Nationen 62, Böttcher-Bau, 1/336 (neu: A12.336)
Alle interessierten Personen sind herzlich eingeladen!
Zusammenfassung:
Die hier zu verteidigende Dissertation beschäftigt sich mit kombinatorischen und algorithmischen Problemen zu einigen periodischen Textmustern. In dieser Disputation wird ein Textmuster vorgestellt, dessen Zählalgorithmus wegen seiner Vielseitigkeit von allgemeinem Interesse ist und erstmals von uns auf dem 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020) in internationaler Zusammenarbeit mit Mitsuru Funakoshi von der Kyushu-Universität veröffentlicht wurde.
Die diskrete azyklische Faltung ist eine Operation, die zwei Vektoren a und b der Länge n bekommt und die 2n+1 Summen mit Summanden der Form a_i * b_{k-i} berechnet. Es ist bekannt, dass die Faltung mit Hilfe der schnellen Fourier-Transformation oder der schnellen zahlentheoretischen Transformation in O(n log n) Operationen berechnet werden kann. Diese Dissertation erweitert die Faltung, indem wir für ein Polygon P die Summen auf die Summanden einschränken, deren Indexpaar in P liegt. Für ein Polygon mit k Eckpunkten und Umfang p braucht diese Faltung immer noch nur O(k+p(log p)^2 log k) Operationen.
Die Faltung und ihre nicht-rechteckige Erweiterung können verwendet werden, um kurze arithmetische Progressionen {i, i+d, i+2d} zu finden, deren zugehörige Zeichen im Text übereinstimmen. Obwohl diese Strukturen bereits von van der Waerden in den 1920er Jahren studiert wurden, war noch kein Algorithmus zum Zählen dieser "3-Subkadenzen" mit subquadratischer Laufzeit bekannt. In dieser Dissertation zeigen wir, dass sich 3-Subkadenzen und einige ihrer Varianten in quasilinearer Zeit zählen lassen.
Abstract:
The dissertation which is defended here deals with combinatoric and algorithmic problems of periodic string patterns. In this disputation, we present a string pattern which has a counting algorithm that is of general interest because of its versatility. We previously published this algorithm at the 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020) in international collaboration with Mitsuru Funakoshi from Kyushu university.
The discrete acyclic convolution is an operation that takes two vectors a and b of length n and calculates the 2n+1 sums with addends of the form a_i * b_{k-i}. It is well-known that the convolution can be calculated by fast Fourier transform or fast number theoretic transform in O(n log n) operations. This dissertation extends the convolution by restricting the sums to addends whose index pair lie in a polygon P. For polygons with k vertices and perimeter p, this non-rectangular convolution only needs O(k+p(log p)^2 log k) operations.
The convolution and its non-rectangular extension can be used to find short arithmetic progressions {i, i+d, i+2d} whose corresponding characters in the string are equal. Although these structures were already studied by van der Waerden in the 1920s, there was no known algorithm for counting these "3-subcadences" in subquadratic time. In this dissertation, we prove that 3-subcadence and several of their variants can be counted in quasilinear time.
