Differences
This shows you the differences between two versions of the page.
fischer:teaching:tir-ws2018 [2018-10-15 19:05] |
fischer:teaching:tir-ws2018 [2018-10-18 08:39] |
||
---|---|---|---|
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 25: | Line 26: | ||
===== Stundenplan Vorlesung ===== | ===== Stundenplan Vorlesung ===== | ||
* 8.10.: Tries | * 8.10.: Tries | ||
- | * 15.10.: Suffixbäume in O(n) Zeit | + | * 15.10.: Suffixbäume in O(n) Zeit, Suffix-Arrays in O(n log n) Zeit |
* TBC | * 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 ===== | ||
Line 37: | Line 39: | ||
==== 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") | ||
Line 46: | Line 46: | ||
* Die Wavelet-Matrix (Kapitel 6.2.5 aus Navarros Buch "Compact Data Structures: A Practical Approach") | * Die Wavelet-Matrix (Kapitel 6.2.5 aus Navarros Buch "Compact Data Structures: A Practical Approach") | ||
* Range Min-Max-Trees (Kapitel 7.1 aus Navarros Buch "Compact Data Structures: A Practical Approach") | * Range Min-Max-Trees (Kapitel 7.1 aus Navarros Buch "Compact Data Structures: A Practical Approach") | ||
+ | * XBWT?? | ||
==== Praxisprojekte ==== | ==== Praxisprojekte ==== |