Differences

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

Link to this comparison view

Both sides previous revision Previous revision
fischer:teaching:pg-plads [2019-07-10 09:02]
Patrick Dinklage
fischer:teaching:pg-plads [2019-07-15 10:46] (current)
Patrick Dinklage
Line 26: Line 26:
   * 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 32:
    - 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 55: Line 67:
 |:::| ::: | [[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 ===+===== 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