Table of Contents
Proseminar String-Algorithmen
Inhalt
Wir beschäftigen uns mit grundlegenden Algorithmen auf Zeichenketten (Strings): suchen, sortieren und indexieren. Hierfür verwenden wir die folgenden Lehrbücher:
- Crochemore, M., Hancart, C., & Lecroq, T. (2007). Algorithms on Strings. Cambridge University Press. [CHL]
- Gusfield, D. (1997). Algorithms on Strings, Trees, and Sequences. Cambridge University Press. [G]
- Ohlebusch, E. (2013). Bioinformatics Algorithms. Oldenbusch-Verlag. [O] (neu online)
Die Bücher [CHL] und [G] sind bei im Büro von Dominik Köppl und Florian Kurpicz gegen Vorlage Ihres Personalausweises ausleihbar. Die Bücher [O], [Say] und [SW] sind im Universitätsnetz online verfügbar.
Lehrpersonen
Allgemeine Hinweise
Alle TN müssen vor Vorlesungsbeginn das Seminar Präsentationstechniken erfolgreich absolvieren.
Bitte beachten Sie die wichtigen Hinweise in diesem Merkblatt.
Themenliste
| Nr. | Thema | Material | Teilnehmer | Termin 1) | Betreuer |
|---|---|---|---|---|---|
| 1. | Naives String Matching, Boyer-Moore, Boyer-Moore-Horspool | [SW 760-761], [SW 770-773], [O 2.3] | fällt aus | ||
| 2. | Knuth-Morris-Pratt | [SW 762-769] | Thaqi | 14.10.2014 | Johannes Fischer |
| 3. | Searching Sets of Patterns | [CHL 2.2], [O 2.5] | Joschko | 21.10.2014 | Florian Kurpicz |
| 4. | Constant Extra-Space String Matching | [KKP] | fällt aus | ||
| 5. | Seminumerical String-Matching | [G 4.2-4.3] | Neumann | 04.11.2014 | Dominik Köppl |
| 6. | Karp-Rabin-Fingerprints and Hashing Strings | [SW 774-779], [G 4.4], [SW 460] | Knörr | 11.11.2014 | Dominik Köppl |
| 7. | Edit-Distanz und Alignment-Algorithmen | [O 8.1] | Büsscher | 18.11.2014 | Dominik Köppl |
| 8. | Regular-Expression-Search | [SW 788-804] | Schrewe | 25.11.2014 | Florian Kurpicz |
| 9. | Searching with Wildcards | [CHL 8.1] | Oesing | 02.12.2014 | Florian Kurpicz |
| 10. | Tries | [SW 730-752] | Liesbrock | 09.12.2014 | Johannes Fischer |
| 11. | Key-Indexed Counting and Ternary Quicksort | [SW 703-705], [SW 719-723] | Nehrke | 16.12.2014 | Dominik Köppl |
| 12. | Radix-Sort for Strings | [SW 706-718] | Lir | 06.01.2015 | Dominik Köppl |
| 13. | Suffix Arrays | [CHL 4.4], [G 7.14.2-7.14.3] | Püttmann | 13.01.2015 | Dominik Köppl |
| 14. | Longest Common Prefixes | [O 4.2], [G 7.14.4-7.14.5] | Frömberg | 20.01.2015 | Florian Kurpicz |
| 15. | Suffixbäume | [O 4.4], [G 5], [G 7.1-7.4] | Hilgenstock | 27.01.2015 | Johannes Fischer |
| 16. | Suffix-Automaten | [CHL 5.4-5.5] | Klassen | 27.01.2015 | Florian Kurpicz |
| 17. | Kompression: Huffman und Tunstall | [SW 810-838], [Say 3.7] | Rebohle | 03.02.2014 | Dominik Köppl |
| 18. | Kompression: Lempel-Ziv-Varianten | [SW 839-845] | fällt aus |
Zeitlicher Ablauf
Spätestens 2 Wochen vor dem Vortrag sollen Sie in einem halbstündigen Treffen mit Ihrem Betreuer die bis auf Feinkosmetik fertigen Folien zeigen und erklären können. Bitte vereinbaren Sie dieses Treffen rechtzeitig, also mindestens 4 Wochen vor dem Vortrag.
Spätestens 2 Wochen nach dem Vortrag müssen Sie die schriftliche Ausarbeitung abgeben (per Email als pdf). Die formalen Voraussetzungen zur schriftlichen Ausarbeitung sind dem o.g. Hinweisblatt zu entnehmen.
Beide Deadlines sind hart.
Voraussetzungen
Sie sollten Spaß an algorithmischen Problem und deren effizienter Lösung haben.
Ort und Zeit
Di 14 c.t. - 16, R202 (OH14). Erster Termin am 7.10.2014.
Es fand eine Vorbesprechung mit Themenvergabe in der letzten VL-Woche des SS'14 statt, und zwar am 15.7.2014 von 10 c.t. bis 12 Uhr im Raum 202 (OH14).