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:pg-plads [2019-07-10 09:02]
Patrick Dinklage
fischer:teaching:pg-plads [2019-10-16 15:59] (current)
Patrick Dinklage
Line 3: Line 3:
 ===== News ===== ===== News =====
  
-  * Das wöchentliche PG-Treffen wurde festgelegt auf **Mittwoch, 14-16 Uhr (c.t.)** und findet erstmalig am **16.10.2019** statt. +  * Das wöchentliche PG-Treffen wurde in der ersten Sitzung auf **Mittwoch, 10-12 Uhr (c.t.)** verlegt. Der neue Termin gilt ab dem 23.10.2019 
-  * Das PG-Blockseminar findet am **Do, 10.10.2019 und Fr., 11.10.2019** jeweils **ab 10:00 Uhr (s.t.)** statt.+  * <color #888888>Das wöchentliche PG-Treffen wurde festgelegt auf **Mittwoch, 14-16 Uhr (c.t.)** und findet erstmalig am **16.10.2019** statt.</​color>​ 
 +  * <color #888888>Das PG-Blockseminar findet am **Do, 10.10.2019** (OH12, Raum 3.030) ​und **Fr., 11.10.2019** ​(OH14, Raum 202) jeweils **ab 10:00 Uhr (s.t.)** statt.</​color>​ 
 +  * <color #​888888>​Die Einreichung der Implementierungen für die Bit Vector Coding Challenge soll bis **Mo, 07.10.2019 um 08:00 Uhr** erfolgen.</​color>​
   * <color #​888888>​Der Ersttermin der Projektgruppe findet am **09.07.2019** um **10:00** Uhr im Raum **OH12 3.030** statt.</​color>​   * <color #​888888>​Der Ersttermin der Projektgruppe findet am **09.07.2019** um **10:00** Uhr im Raum **OH12 3.030** statt.</​color>​
   * <color #​888888>​Die Einzelpräsentation findet am **03.06.2019** um **14:00** Uhr im Raum **OH14 202** statt.</​color>​   * <color #​888888>​Die Einzelpräsentation findet am **03.06.2019** um **14:00** Uhr im Raum **OH14 202** statt.</​color>​
Line 26: Line 28:
   * Vorgängerdatenstrukturen (z. B. van-Emde-Boas-Trees)   * Vorgängerdatenstrukturen (z. B. van-Emde-Boas-Trees)
  
-===== Seminar ​und Coding Challenge ​=====+===== Seminar =====
  
 Aufgabe im Seminar ist das Zusammentragen der in der vorgegebenen Literatur vorgestellten platzeffizienten Datenstrukturen. Dies umfasst Aufgabe im Seminar ist das Zusammentragen der in der vorgegebenen Literatur vorgestellten platzeffizienten Datenstrukturen. Dies umfasst
Line 32: Line 34:
    - einen 25-30-minütigen Vortrag im Blockseminar und    - einen 25-30-minütigen Vortrag im Blockseminar und
    - eine 8-10-seitige Ausarbeitung mit der Idee, dass sie später in den PG-Bericht übernommen werden kann.    - eine 8-10-seitige Ausarbeitung mit der Idee, dass sie später in den PG-Bericht übernommen werden kann.
 +
 +Der Vortrag dient hauptsächlich dem Zweck, den anderen PG-Mitgliedern einen Überblick über das erarbeitete Thema zu geben. Es geht hier also weniger um die formale Vollständigkeit (Beweise usw.) als um eine didaktisch wertvolle Darbietung des Themas, so dass die anderen Mitglieder die Funktionsweise verstehen. Versetzen Sie sich in diese und überlegen Sie, welche Informationen wirklich zum Verständnis notwendig sind. Die Ausarbeitung sollte dann etwas tiefgreifender werden. Grundsätzlich richten Sie sich am besten an unsere {{:​fischer:​teaching:​allgemeine_seminarhinweise_ads.pdf |allgemeinen Seminarhinweise}} (Abschnitte 5-7, wobei der Vortrag eben nur rund 25 Minuten dauern soll).
 +
 +Die folgenden Punkte sollten rüberkommen:​
 +
 +  * Was ist die Problemstellung (informell und formal)?
 +  * Welche Anfragen beantwortet die vorgestelle Datenstruktur?​
 +  * Welche Zeit- und Platzschranken gelten für Konstruktion,​ Datenstruktur und Anfragen?
 +  * Was sind herauszustellende Teilprobleme und Teildatenstrukturen?​
 +  * Welche vergleichbaren Datenstrukturen gibt es und wie unterscheiden sie sich (grob)?
 +  * Gibt es bereits Implementierungen?​ Welche Eigenschaften haben diese, wie schneiden sie in bereits durchgeführten Vergleichen ab?
 +  * Sind bereits besondere Herausforderungen für eine Implementierung erkennbar?
  
 Die Ausarbeitungen sollen mit LaTeX geschrieben werden. Verwenden Sie hierzu den LIPIcs-Stil - eine Vorlage befindet sich [[https://​www.dagstuhl.de/​en/​publications/​lipics/​instructions-for-authors/​|hier]] (''​lipics-v2019-authors.zip''​). Die Ausarbeitungen sollen mit LaTeX geschrieben werden. Verwenden Sie hierzu den LIPIcs-Stil - eine Vorlage befindet sich [[https://​www.dagstuhl.de/​en/​publications/​lipics/​instructions-for-authors/​|hier]] (''​lipics-v2019-authors.zip''​).
Line 50: Line 64:
 |7| Minimal Perfect Hashing | [[https://​link.springer.com/​chapter/​10.1007%2F978-3-319-38851-9_23|Genuzio et al.: Fast Scalable Construction of (Minimal Perfect Hash) Functions]] | Broadword Programming,​ Gaussian Elimination | H.D.D. | |7| Minimal Perfect Hashing | [[https://​link.springer.com/​chapter/​10.1007%2F978-3-319-38851-9_23|Genuzio et al.: Fast Scalable Construction of (Minimal Perfect Hash) Functions]] | Broadword Programming,​ Gaussian Elimination | H.D.D. |
 |8| Planare Graphen | [[https://​link.springer.com/​chapter/​10.1007%2F978-3-319-62127-2_33|Ferres et al.: Fast and Compact Planar Embeddings]] | Duale Graphen, Spannbäume,​ Turán-Repräsentation | A.K. | |8| Planare Graphen | [[https://​link.springer.com/​chapter/​10.1007%2F978-3-319-62127-2_33|Ferres et al.: Fast and Compact Planar Embeddings]] | Duale Graphen, Spannbäume,​ Turán-Repräsentation | A.K. |
-|9| Range Minimum Queries | Kowalski & Gabrowski: Faster range minimum queries | kartesischer Baum | //(nicht vergeben)// |+|9| <del>Range Minimum Queries</​del> ​| Kowalski & Gabrowski: Faster range minimum queries | kartesischer Baum | //(nicht vergeben)// |
 |:::| ::: | Gawrychowski et al.: Compressed Range Minimum Queries | Sparse Table | ::: | |:::| ::: | Gawrychowski et al.: Compressed Range Minimum Queries | Sparse Table | ::: |
-|10| Vorgängerdatenstrukturen | [[https://​link.springer.com/​chapter/​10.1007%2F978-3-319-19929-0_30|Matsuoka et al.: Semi-dynamic Compact Index for Short Patterns and Succinct van Emde Boas Tree]] (nur Abschnitt 3) | van Emde Boas Tree, b-Bäume | F.B.L. ​|+|10| <del>Vorgängerdatenstrukturen</​del> ​| [[https://​link.springer.com/​chapter/​10.1007%2F978-3-319-19929-0_30|Matsuoka et al.: Semi-dynamic Compact Index for Short Patterns and Succinct van Emde Boas Tree]] (nur Abschnitt 3) | van Emde Boas Tree, b-Bäume | //(nicht vergeben)// ​|
 |:::| ::: | [[http://​algo2.iti.kit.edu/​dementiev/​files/​veb.pdf|Dementiev et al.: Engineering a Sorted List Data Structure for 32 Bit Keys]] | van Emde Boas Tree, Hashing | ::: | |:::| ::: | [[http://​algo2.iti.kit.edu/​dementiev/​files/​veb.pdf|Dementiev et al.: Engineering a Sorted List Data Structure for 32 Bit Keys]] | van Emde Boas Tree, Hashing | ::: |
  
-=== Bit Vector Coding Challenge ===+=== Ablauf === 
 + 
 +== Donnerstag, 10.10.2019 == 
 + 
 +Ort: OH12 3.030 
 + 
 +^ Zeit (s.t.) ^ Vortrag ^ 
 +| 10:00 - 10:15 | Einführung | 
 +| 10:15 - 11:00 | Document Retrieval (M.T.) | 
 +| 11:00 - 11:45 | Baumähnliche Graphen (M.F.) | 
 +| 11:45 - 12:30 | Planare Graphen (A.K.) | 
 +| 12:30 - 13:30 | Mittagspause | 
 +| 13:30 - 14:15 | Dynamische Bitvektoren mit Rank/Select (J.-P.T.) | 
 + 
 +== Freitag, 11.10.2019 == 
 + 
 +Ort: OH14 202 
 + 
 +^ Zeit (s.t.) ^ Vortrag ^ 
 +| 10:00 - 10:45 | Minimal Perfect Hashing 1 (A.H.) | 
 +| 10:45 - 11:30 | Minimal Perfect Hashing 2 (H.D.D.) | 
 +| 11:30 - 12:15 | Grammatikkompression (J.M.) | 
 +| 12:15 - 13:00 | Grammatiken / SLPs (J.T.) | 
 +| 13:00 - 14:00 | Mittagspause | 
 +| 14:00 - 15:00 | Bit Vector Coding Challenge ​
 + 
 +===== Coding Challenge =====
  
-In der Coding Challenge soll die Programmierung mit C++ im Rahmen von platzeffizienten Datenstrukturen aufgebaut bzw. aufgefrischt und vertieft werden.+In der Bit Vector ​Coding Challenge soll die Programmierung mit C++ im Rahmen von platzeffizienten Datenstrukturen aufgebaut bzw. aufgefrischt und vertieft werden.
  
-Der Code-Rahmen ​befindet ​sich hier: [[https://​github.com/​pdinklag/​bvcc]]+Der Code-Rahmen ​und die Aufgabenstellung befinden ​sich hier: [[https://​github.com/​pdinklag/​bvcc]]
  
-Er enthält funktionale,​ aber naive Implementierungen für Bitvektoren,​ Rank und Select, die durch durch eigene Lösungen ersetzt werden sollen. +Die Aufgaben sind zum Blockseminar zu erarbeiten, wo dann ein Benchmark durchgeführt wird, um den oder die Sieger zu ermitteln. Der Code-Rahmen enthält eine funktionale,​ aber wenig platzeffiziente Implementierung für Bitvektoren,​ Rank und Select, die durch eine eigene ersetzt werden soll.
-Die Aufgaben sind ebenfalls ​zum Blockseminar zu erarbeiten, wo ein Benchmark durchgeführt wird, um den oder die Sieger zu ermitteln.+
  
-Folgendes Bild hatte ich in der ersten PG-Sitzung zur Rank1-Datenstruktur produziert:+Folgendes Bild hatten wir in der ersten PG-Sitzung zur Rank1-Datenstruktur ​nach dem Buch von Navarro (Compact Data Structures) ​produziert:
 {{ :​fischer:​teaching:​pg-rank.pdf |}} {{ :​fischer:​teaching:​pg-rank.pdf |}}
 
Last modified: 2019-07-10 09:02 by Patrick Dinklage
DokuWikiRSS-Feed