Differences
This shows you the differences between two versions of the page.
— |
fischer:teaching:pg-saca [2018-04-05 14:13] (current) |
||
---|---|---|---|
Line 1: | Line 1: | ||
+ | ====== PG SACABench ====== | ||
+ | Das bekannteste und wohl am besten erforschte Problem der Algorithmik ist das Sortieren eines Felds von Zahlen. Dieses Problem kann auf Strings übertragen werden: sortiere alle Suffixe eines Strings in lexikographischer Reihenfolge, z. B. //a//, //ana//, //bana// und //na// für den String //bana//. | ||
+ | Eine solche Sortierung ist der grundlegende Schritt vieler wichtiger Textindizes. Ziel dieser Projektgruppe ist die praktische Analyse und Verbesserung von bestehenden Algorithmen zur Suffixsortierung. | ||
+ | |||
+ | ===== News ===== | ||
+ | * Das Blockseminar findet am 05.04.2018 und 06.04.2018 jeweils von 9:00 Uhr bis 16:00 Uhr statt. Der Raum wird noch bekannt gegeben. | ||
+ | * Das erste Treffen findet am 31.01.2018 von 13:00 Uhr bis 15:00 Uhr im Raum OH12 3.030 statt. | ||
+ | * Themen für die erste Seminarphase hinzugefügt. | ||
+ | * Die PG kommt zustande. Weitere Informationen folgen ab dem 22.02.2018. | ||
+ | * <del>Die Einzelpräsentation findet am **20.12.2017** um **16:00** Uhr um Raum **OH14 202** statt.</del> | ||
+ | |||
+ | ===== Seminarthemen ===== | ||
+ | |||
+ | ^ ^ Autoren ^ Titel ^ | ||
+ | | 6. | Nong et al. | Two efficient algorithms for linear time suffix array construction | | ||
+ | | 7. | Nong | Practical linear-time O(1)-workspace suffix sorting for constant alphabets | | ||
+ | | 12. | Goto | Optimal Time and Space Construction of Suffix Arrays and LCP Arrays for Integer Alphabets | | ||
+ | | 5. | Fischer/Kurpicz | [[https://github.com/y-256/libdivsufsort|Dismantling DivSufSort]] | | ||
+ | | 4. | Manzini/Ferragina | Engineering a lightweight suffix array construction algorithm | | ||
+ | | 1. | Larsson/Sadakane | Faster suffix sorting | | ||
+ | | 2. | Schürmann/Stoye | An incomplex algorithm for fast suffix array construction | | ||
+ | | 3. | Baier | Linear-time suffix sorting - A new approach for suffix array construction | | ||
+ | | 8. | Maniscalco/Puglisi | An efficient, versatile approach to suffix sorting | | ||
+ | | 9. | Kärkkäinen/Sanders | Simple linear work suffix array construction | | ||
+ | | 10. | Nong/Zhang | Optimal lightweight construction of suffix arrays for constant alphabets | | ||
+ | | 11. | Dementiev et al. | Better external memory suffix array construction | | ||