Differences
This shows you the differences between two versions of the page.
| — |
fischer:abschlussarbeiten:nss [2019-08-06 13:01] (current) |
||
|---|---|---|---|
| Line 1: | Line 1: | ||
| + | ===== Efficient Computation of Nearest Smaller Suffixes ===== | ||
| + | ==== Beschreibung ==== | ||
| + | In dieser Arbeit soll eine effiziente Datenstruktur für //next// und //previous smaller suffix//-Anfragen gefunden werden. | ||
| + | Diese Anfragen sollen gegeben einem Text //T[1..n]// und einer Position //i// die Position //j// zurückgeben an der das //vorherige// (//j<i//) bzw. //nächste// (//j>i//) Suffix beginnt, welches lexikographisch kleiner ist (//T[i..n]>T[j..n])//. | ||
| + | Solche Anfragen werden unter anderem zum [[https://epubs.siam.org/doi/pdf/10.1137/15M1011032|Auffinden von Runs]] als auch zur [[https://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.190/Mitarbeiter/baier/gsaca.pdf|Konstruktion des Suffix Arrays]] benötigt. | ||
| + | |||
| + | ==== Typ ==== | ||
| + | Masterarbeit. | ||
| + | |||
| + | ==== Bearbeiter ==== | ||
| + | [[staff:ellert|Jonas Ellert]] | ||
| + | |||
| + | ==== Das sollten Sie mitbringen ==== | ||
| + | * Spaß an algorithmischen Problemstellungen | ||
| + | * gute Programmierkenntnisse in C++ | ||
| + | |||
| + | ==== Betreuer ==== | ||
| + | Bei Interesse wenden Sie sich bitte an [[staff:fischer|Johannes Fischer]] oder [[staff:kurpicz|Florian Kurpicz]] | ||