Differences
This shows you the differences between two versions of the page.
| — |
fischer:teaching:as-ws2014 [2015-09-08 15:53] (current) |
||
|---|---|---|---|
| Line 1: | Line 1: | ||
| + | ====== 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**] | ||
| + | * [[http://www.uni-ulm.de/in/theo/m/ohlebusch/book-bioinformatics-algorithms.html | Ohlebusch, E. (2013). Bioinformatics Algorithms. Oldenbusch-Verlag.]] [**O**] <color red>(neu online)</color> | ||
| + | * [[http://proquest.tech.safaribooksonline.de/9780124157965 | Sayood, K. (2012) Introduction to Data Compression. Morgan Kaufmann, 4. Auflage.]] [**Say**] | ||
| + | * [[http://proquest.tech.safaribooksonline.de/book/software-engineering-and-development/algorithms/9780132762571 | Sedgewick, R., & Wayne, K. (2011) Algorithms. Addison-Wesley, 4. Auflage.]] [**SW**] | ||
| + | **Die Bücher [CHL] und [G] sind bei im Büro von [[staff:koeppl|Dominik Köppl]] und [[staff:kurpicz|Florian Kurpicz]] gegen Vorlage Ihres Personalausweises ausleihbar**. Die Bücher [O], [Say] und [SW] sind im Universitätsnetz online verfügbar. | ||
| + | ===== Lehrpersonen ===== | ||
| + | * [[staff:fischer|Prof. Dr. Johannes Fischer]] | ||
| + | * [[staff:koeppl|Dominik Köppl]] | ||
| + | * [[staff:kurpicz|Florian Kurpicz]] | ||
| + | |||
| + | ===== Allgemeine Hinweise ===== | ||
| + | Alle TN müssen vor Vorlesungsbeginn das [[fischer:teaching:pk-ws2014|Seminar Präsentationstechniken]] erfolgreich absolvieren. | ||
| + | |||
| + | Bitte beachten Sie die wichtigen Hinweise in diesem {{:fischer:teaching:allgemeine_proseminarhinweise.pdf|Merkblatt}}. | ||
| + | |||
| + | |||
| + | ===== Themenliste ===== | ||
| + | |||
| + | ^ Nr. ^ Thema ^ Material ^ Teilnehmer ^ Termin ((Wie bei der Themenvergabe besprochen können sich die Termine im Laufe des Semesters verschieben.)) ^ 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 | [[staff:fischer|Johannes Fischer]] | | ||
| + | | 3.| Searching Sets of Patterns | [CHL 2.2], [O 2.5] | Joschko | 21.10.2014 | [[staff:kurpicz|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 | [[staff:koeppl|Dominik Köppl]] | | ||
| + | | 6.| Karp-Rabin-Fingerprints and Hashing Strings | [SW 774-779], [G 4.4], [SW 460] | Knörr | 11.11.2014 | [[staff:koeppl|Dominik Köppl]] | | ||
| + | | 7.| Edit-Distanz und Alignment-Algorithmen | [O 8.1] | Büsscher | 18.11.2014 | [[staff:koeppl|Dominik Köppl]] | | ||
| + | | 8.| Regular-Expression-Search | [SW 788-804] | Schrewe | 25.11.2014 | [[staff:kurpicz|Florian Kurpicz]] | | ||
| + | | 9.| Searching with Wildcards | [CHL 8.1] | Oesing | 02.12.2014 | [[staff:kurpicz|Florian Kurpicz]] | | ||
| + | | 10.| Tries | [SW 730-752] | Liesbrock | 09.12.2014 | [[staff:fischer|Johannes Fischer]] | | ||
| + | | 11.| Key-Indexed Counting and Ternary Quicksort | [SW 703-705], [SW 719-723] | Nehrke | 16.12.2014 | [[staff:koeppl|Dominik Köppl]] | | ||
| + | | 12.| Radix-Sort for Strings | [SW 706-718] | Lir | 06.01.2015 | [[staff:koeppl|Dominik Köppl]] | | ||
| + | | 13.| Suffix Arrays | [CHL 4.4], [G 7.14.2-7.14.3] | Püttmann | 13.01.2015 | [[staff:koeppl|Dominik Köppl]] | | ||
| + | | 14.| Longest Common Prefixes | [O 4.2], [G 7.14.4-7.14.5] | Frömberg | 20.01.2015 | [[staff:kurpicz|Florian Kurpicz]] | | ||
| + | | 15.| Suffixbäume | [O 4.4], [G 5], [G 7.1-7.4] | Hilgenstock | 27.01.2015 | [[staff:fischer|Johannes Fischer]] | | ||
| + | | 16.| Suffix-Automaten | [CHL 5.4-5.5] | Klassen | 27.01.2015 | [[staff:kurpicz|Florian Kurpicz]] | | ||
| + | | 17.| Kompression: Huffman und Tunstall | [SW 810-838], [Say 3.7] | Rebohle | 03.02.2014 | [[staff:koeppl|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). | ||