Differences

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

Link to this comparison view

fischer:teaching:tir-ws2018 [2018-11-12 16:12]
fischer:teaching:tir-ws2018 [2018-11-13 16:59]
Line 3: Line 3:
  
 ===== Neuigkeiten ===== ===== Neuigkeiten =====
 +  * Doodle für Abschlussprojekte läuft!
 +  * 13.11.18: Skript+Übungsblatt 6 online
   * 6.11.2018: Skript+Übungsblatt 5 online   * 6.11.2018: Skript+Übungsblatt 5 online
   * 30.10.18: Skript+Übungsblatt 4 online   * 30.10.18: Skript+Übungsblatt 4 online
   * 22.10.18: Skript+Übungsblatt 3 online   * 22.10.18: Skript+Übungsblatt 3 online
-  * 16.10.18: Skript+Übungsblatt 2 online 
-  * 9.10.18: Skript+Übungsblatt 1 online 
- 
  
 ===== Inhalt ===== ===== Inhalt =====
Line 32: Line 31:
   * 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   * 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
 +  * 13.11.: RMQ und LCA in O(1) Zeit und O(n) Platz
 ===== 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 41:
   - {{:​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}}
 ===== Abschlussprojekte ===== ===== Abschlussprojekte =====
  
-Die letzten 4 Ü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. 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 ==== +  ​U. Beier: ​//On Undetected Redundancy in the Burrows-Wheeler Transform//. Proc. CPM'​18,​ article no. 3. LIPIcs Band 105. 
-Ziel ist es, einen die Vorlesung ergänzenden Aspekt aus einem wissenschaftlichen Artikel oder aus einem Buch in ca. 25 Minuten vorzustellen. +  ​Platzeffiziente Konstruktion der BWT (Kapitel 9.3 in Mäkinen et al.'s Buch "​Genome Scale Algorithm Design"​) 
-  ​U. Beier: On Undetected Redundancy in the Burrows-Wheeler Transform. Proc. CPM'​18,​ article no. 3. LIPIcs Band 105. +  ​Bidirektionale BWT (Kapitel 9.4 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"​) +  ​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)! 
-  ​Bidirektionale BWT (Kapitel 9.4 in Mäkinen et al.'s Buch "​Genome Scale Algorithm Design"​) +  ​Compressed Suffix Arrays (Kapitel 11.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"​) +  ​- 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.) 
-  ​Compressed Suffix Arrays (Kapitel 11.1 aus Navarros Buch "​Compact Data Structures: A Practical Approach"​) +  ​LZ77: Ultraschnelle Berechnung (Kapitel 5.2.2 aus Ohlebuschs Buch "​Bioinformatics Algorithms"​) 
-  ​* XBWT?? +  ​- LZ-Index (Abschnitt 13.2.2 in Navarros Buch "​Compact Data Structures: A Practical Approach",​ mit den notwendigen Ergänzungen aus vorangegangenen Kapiteln) 
-  ​LZ77: anderer Algo +  - 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) 
-  ​Runs-Berechnung ​oder Runs-Schranke+  - 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.) 
 +  - Level Ancestor Queries in Bäumen (M. Bender and M. Farach-Colton:​ //The Level Ancestor Problem Simplified//​. Theor. Comput. Sci. 321: 5–12, 2004.), evtl. mit Anwendungen in LZ78 (Abschnitte aus unserem Skript)
  
-==== 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: 2019-01-21 16:26 (external edit)
DokuWikiRSS-Feed