Differences
This shows you the differences between two versions of the page.
fischer:teaching:tir-ws2018 [2018-10-09 09:28] |
fischer:teaching:tir-ws2018 [2018-10-18 08:34] |
||
---|---|---|---|
Line 3: | Line 3: | ||
===== Neuigkeiten ===== | ===== Neuigkeiten ===== | ||
+ | * 16.10.18: Skript+Übungsblatt 2 online | ||
* 9.10.18: Skript+Übungsblatt 1 online | * 9.10.18: Skript+Übungsblatt 1 online | ||
* 17.8.2018: Seite online | * 17.8.2018: Seite online | ||
Line 24: | Line 25: | ||
===== Stundenplan Vorlesung ===== | ===== Stundenplan Vorlesung ===== | ||
- | TBA | + | * 8.10.: Tries |
+ | * 15.10.: Suffixbäume in O(n) Zeit, Suffix-Arrays in O(n log n) Zeit | ||
+ | * TBC | ||
===== Skriptum ===== | ===== Skriptum ===== | ||
- | * {{fischer:teaching:tir-ws2018:script-tir-ws18.pdf |Version}} vom 09.10.18. (Wird forlaufend erneuert.) | + | * {{fischer:teaching:tir-ws2018:script-tir-ws18.pdf |Version}} vom 16.10.18. (Wird forlaufend erneuert.) |
===== Übungsblätter ===== | ===== Übungsblätter ===== | ||
- {{:fischer:teaching:tir-ws2018:ue1.pdf|Übungsblatt 1}},{{:fischer:teaching:enwiki-titles.part.txt.gz|Wortliste}} für Aufgabe 2 und 3 | - {{:fischer:teaching:tir-ws2018:ue1.pdf|Übungsblatt 1}},{{:fischer:teaching:enwiki-titles.part.txt.gz|Wortliste}} für Aufgabe 2 und 3 | ||
+ | - {{:fischer:teaching:tir-ws2018:ue2.pdf|Übungsblatt 2}} | ||
===== Abschlussprojekte ===== | ===== Abschlussprojekte ===== | ||
- | Die letzten 2-3 Übungstermine nutzen wir zu einem Mini-Seminar, bei dem jeder Stud. eine Thema präsentieren soll. | + | Die letzten 4 Übungstermine nutzen wir zu einem Mini-Seminar, bei dem jeder Stud. eine Thema präsentieren soll. |
==== Theorieprojekte ==== | ==== Theorieprojekte ==== | ||
Ziel ist es, einen die Vorlesung ergänzenden Aspekt aus einem wissenschaftlichen Artikel oder aus einem Buch in ca. 25 Minuten vorzustellen. | Ziel ist es, einen die Vorlesung ergänzenden Aspekt aus einem wissenschaftlichen Artikel oder aus einem Buch in ca. 25 Minuten vorzustellen. | ||
- | * Der Φ-Algorithmus aus Kärkkäinen, J., Manzini, G., & Puglisi, S. J. (2009): Permuted longest-common-prefix array. In //Annual Symposium on Combinatorial Pattern Matching// (pp. 181-192). Springer Berlin Heidelberg. | + | * U. Beier: On Undetected Redundancy in the Burrows-Wheeler Transform. Proc. CPM'18, article no. 3. LIPIcs Band 105. |
- | * Der DC3-Algorithmus zur Suffixsortierung (Kapitel 4.1.1 aus Ohlebuschs Buch "Bioinformatics Algorithms") | + | |
* Ultraschnelle LZ77-Faktorisierung (Kapitel 5.2.2 aus Ohlebuschs Buch "Bioinformatics Algorithms") | * Ultraschnelle LZ77-Faktorisierung (Kapitel 5.2.2 aus Ohlebuschs Buch "Bioinformatics Algorithms") | ||
- | * Ultraschnelle Textsuche mit dem Suffix-Array (Kapitel 7.14.4 aus Gusfields Buch "Algorithms on Strings, Trees, and Sequences") | ||
* kompakte Suffix-Automaten (Kap. 5.5 aus Crochemore et al.'s Buch "Algorithms on Strings") | * kompakte Suffix-Automaten (Kap. 5.5 aus Crochemore et al.'s Buch "Algorithms on Strings") | ||
* Platzeffiziente Konstruktion der BWT (Kapitel 9.3 in Mäkinen et al.'s Buch "Genome Scale Algorithm Design") | * Platzeffiziente Konstruktion der BWT (Kapitel 9.3 in Mäkinen et al.'s Buch "Genome Scale Algorithm Design") |