Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revision Previous revision
Next revision
Previous revision
fischer:teaching:tir-ws2018 [2018-11-06 09:32]
Johannes Fischer [Stundenplan Vorlesung]
fischer:teaching:tir-ws2018 [2019-01-21 16:26] (current)
Johannes Fischer [Stundenplan Vorlesung]
Line 3: Line 3:
  
 ===== Neuigkeiten ===== ===== Neuigkeiten =====
-  * 6.11.2018: Skript+Übungsblatt 5 online +  * 08.01.19neues Skript online. 
-  * 30.10.18: Skript+Übungsblatt 4 online +  * 06.01.19neues Skript online. Frohes neues Jahr! 
-  * 22.10.18: Skript+Übungsblatt ​online +  * 11.12.18: neues Skript + Übungsblatt ​online 
-  * 16.10.18: Skript+Übungsblatt 2 online +  * 10.12.18: neues Skript online 
-  * 9.10.18: Skript+Übungsblatt ​online +  * 27.11.18: Skript+Übungsblatt ​online
- +
 ===== Inhalt ===== ===== Inhalt =====
  
Line 31: Line 29:
   * 22.10.: Suffix-Arrays in O(n) Zeit   * 22.10.: Suffix-Arrays in O(n) Zeit
   * 29.10.: LCP-Arrays und LZ77 in O(n) Zeit   * 29.10.: LCP-Arrays und LZ77 in O(n) Zeit
-  * 6.11.: LZ78 in O(n log σ) Zeit, Suche in Suffixarrays in O(n log n) und O(n +log n) Zeit, O(1)-RMQs in O(n log n) Platz+  * 5.11.: LZ78 in O(n log σ) Zeit, Suche in Suffixarrays in O(n log n) und O(n+log n) Zeit, O(1)-RMQs in O(n log n) Platz 
 +  * 12.11.: RMQ und LCA in O(1) Zeit und O(n) Platz 
 +  * 19.11.: BWT und Einführung in die Rückwärtssuche 
 +  * 26.11.: Rückwärtssuche;​ Rank in Bitvektoren,​ Wavelet Trees 
 +  * 03.12.: Y-fast Tries und Approximate Pattern Matching 
 +  * 10.12.: Komprimierter FM-Index 
 +  * 17.12.: Suffix-Array Sampling 
 +  * 7.1.: Inverted Indexes 
 +  * 14.1.: Document Retrieval; Compressed Suffix Trees 
 +  * 21.1.: Compressed RMQ und P/NSV
 ===== Skriptum ===== ===== Skriptum =====
-  * {{fischer:​teaching:​tir-ws2018:​script-tir-ws18.pdf |Version}} ​vom 16.10.18. ​(Wird forlaufend erneuert.)+  * {{fischer:​teaching:​tir-ws2018:​script-tir-ws18.pdf |aktuelle ​Version}} (Wird forlaufend erneuert.)
  
 ===== Übungsblätter ===== ===== Übungsblätter =====
Line 41: Line 48:
   - {{:​fischer:​teaching:​tir-ws2018:​ue4.pdf|Übungsblatt 4}}   - {{:​fischer:​teaching:​tir-ws2018:​ue4.pdf|Übungsblatt 4}}
   - {{:​fischer:​teaching:​tir-ws2018:​ue5.pdf|Übungsblatt 5}}   - {{:​fischer:​teaching:​tir-ws2018:​ue5.pdf|Übungsblatt 5}}
 +  - {{:​fischer:​teaching:​tir-ws2018:​ue6.pdf|Übungsblatt 6}}
 +  - {{:​fischer:​teaching:​tir-ws2018:​ue7.pdf|Übungsblatt 7}}
 +  - {{:​fischer:​teaching:​tir-ws2018:​ue8.pdf|Übungsblatt 8}}
 +  - {{:​fischer:​teaching:​tir-ws2018:​ue9.pdf|Übungsblatt 9}}
 ===== Abschlussprojekte ===== ===== Abschlussprojekte =====
  
-Die letzten ​Übungstermine nutzen wir zu einem Mini-Seminar,​ bei dem jeder Stud. eine Thema präsentieren soll. +Die letzten ​Übungstermine nutzen wir zu einem Mini-Seminar,​ bei dem jeder Stud. ein Thema präsentieren soll. Ziel ist es, einen die Vorlesung ergänzenden Aspekt aus einem wissenschaftlichen Artikel oder aus einem Buch in ca. 25 Minuten vorzustellen. 
-==== Theorieprojekte ==== + 
-Ziel ist es, einen die Vorlesung ergänzenden Aspekt aus einem wissenschaftlichen Artikel oder aus einem Buch in ca. 25 Minuten vorzustellen. +=== 7.1.19 === 
-  ​U. Beier: On Undetected Redundancy in the Burrows-Wheeler Transform. Proc. CPM'​18,​ article no. 3. LIPIcs Band 105. +  ​U. Beier: ​//On Undetected Redundancy in the Burrows-Wheeler Transform//. Proc. CPM'​18,​ article no. 3. LIPIcs Band 105. **Osthues** 
-  ​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"​) ​**Böcker** 
-  ​Bidirektionale BWT (Kapitel 9.4 in Mäkinen et al.'s Buch "​Genome Scale Algorithm Design"​) +  ​Bidirektionale BWT (Kapitel 9.4 in Mäkinen et al.'s Buch "​Genome Scale Algorithm Design"​) ​**Michaelis** 
-  * Range Min-Max-Trees (Kapitel 7.1 aus Navarros Buch "​Compact Data Structures: A Practical Approach"​) +  ​- BWT für Bäume (Abschnitt 2 in P. Ferragina et al.: //​Compressing and Indexing Labeled Trees, with Applications//​. J. ACM 57(1), Article No. 4, 2009.) ​**Metz** 
-  * Compressed Suffix Arrays (Kapitel 11.1 aus Navarros Buch "​Compact Data Structures: A Practical Approach"​) + 
-  * XBWT??+=== 13.1.19 === 
 +  - Range Min-Max-Trees (Kapitel 7.1 aus Navarros Buch "​Compact Data Structures: A Practical Approach"​). Hier bitte eine geeignete Auswahl treffen (d.h. reduzieren)! **Haldimann** 
 +  ​- LZ77: Ultraschnelle Berechnung (Kapitel 5.2.2 aus Ohlebuschs Buch "​Bioinformatics Algorithms"​) ​**Bertram** 
 +  - LZ-Index (Abschnitt 13.2.2 in Navarros Buch "​Compact Data Structures: A Practical Approach",​ mit den notwendigen Ergänzungen aus vorangegangenen Kapiteln) **Brümmer** 
 + 
 +=== 20.1.19 === 
 +  - Compressed Suffix Arrays (Kapitel 11.1 aus Navarros Buch "​Compact Data Structures: A Practical Approach"​) ​**Pink** 
 +  ​- obere Schranke für die Anzahl an Runs (Abschnitt 3 in H. Bannai et al.: //The "​Runs"​ Theorem//. SIAM J. Computing 46(5), pp 1501-1514, 2017) **Bode** 
 +  - Runs-Berechnung in O(n) Zeit (Abschnitt 4.1 in H. Bannai et al.: //The "​Runs"​ Theorem//. SIAM J. Computing 46(5), pp 1501-1514, 2017.) **Schinner**
  
-==== Praxisprojekte ==== 
-Ziel ist es, in der Vorlesung eingeführte Algorithmen und Datenstrukturen gut zu implementieren und anhand von realistischen Eingaben auf Platzbedarf und Laufzeit zu testen sowie mit konkurrierenden Verfahren zu vergleichen. Auch hier soll am Ende eine ca. 25-minütige Präsentation stehen. 
-  * Vergleich von Suffix Arrays und Inverted Indexes bei der Beantwortung von Suchanfragen 
-  * Praktische Evaluation der Level-Ancestor-Datenstruktur 
-  * ... 
 ===== Ort und Zeit ===== ===== Ort und Zeit =====
   * Vorlesung: Mo 14-16 c.t. (SRG1 1.001)   * Vorlesung: Mo 14-16 c.t. (SRG1 1.001)
   * Übungsgruppe:​ Mo 16-18 s.t. (SRG1 1.001)   * Übungsgruppe:​ Mo 16-18 s.t. (SRG1 1.001)
 
Last modified: 2018-11-06 09:32 by Johannes Fischer
DokuWikiRSS-Feed