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:

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).

1) Wie bei der Themenvergabe besprochen können sich die Termine im Laufe des Semesters verschieben.
 
Last modified: 2015-09-08 15:53 (external edit)
DokuWikiRSS-Feed