Differences

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

Link to this comparison view

fischer:teaching:pg-plads [2019-05-28 08:31]
fischer:teaching:pg-plads [2019-05-28 08:37]
Line 2: Line 2:
 **Platzeffiziente Datenstrukturen** (//succinct data structures//​) sind solche, die Anfragen effizient beantworten können und deren Speicherplatzverbrauch dabei möglichst nah an der theoretischen unteren Schranke liegt. Ein einfaches Beispiel ist das Zählen von 0- oder 1-Bits in Bitstrings bis zu einer bestimmten Position: Ohne Vorverarbeitung ist dies einfach in linearer Zeit in der Länge des Strings möglich. Es gibt jedoch platzeffiziente Datenstrukturen,​ die diese so genannten //​rank//​-Anfragen in konstanter Zeit beantworten und dabei nur sublinear viel Speicherplatz benötigen. Diese bieten u. a. die Grundlage für platzeffiziente Darstellungen von Bäumen mit nur //2n + o(n)// Bits (bei Knotenzahl //n//). **Platzeffiziente Datenstrukturen** (//succinct data structures//​) sind solche, die Anfragen effizient beantworten können und deren Speicherplatzverbrauch dabei möglichst nah an der theoretischen unteren Schranke liegt. Ein einfaches Beispiel ist das Zählen von 0- oder 1-Bits in Bitstrings bis zu einer bestimmten Position: Ohne Vorverarbeitung ist dies einfach in linearer Zeit in der Länge des Strings möglich. Es gibt jedoch platzeffiziente Datenstrukturen,​ die diese so genannten //​rank//​-Anfragen in konstanter Zeit beantworten und dabei nur sublinear viel Speicherplatz benötigen. Diese bieten u. a. die Grundlage für platzeffiziente Darstellungen von Bäumen mit nur //2n + o(n)// Bits (bei Knotenzahl //n//).
  
 +=== Ziel der PG ===
 Ziel der Projektgruppe ist der Entwurf und die Implementierung einer hochperformanten,​ erweiterbaren C++-Bibliothek verschiedener platzeffizienter Datenstrukturen sowie das Benchmarking dieser Bibliothek im Rahmen typischer Anwendungsfälle der entwickelten Datenstrukturen. Ziel der Projektgruppe ist der Entwurf und die Implementierung einer hochperformanten,​ erweiterbaren C++-Bibliothek verschiedener platzeffizienter Datenstrukturen sowie das Benchmarking dieser Bibliothek im Rahmen typischer Anwendungsfälle der entwickelten Datenstrukturen.
 +
 +=== Themenbereiche ===
 +Die zu implementierenden Datenstrukturen gehören zu folgenden Themenbereichen:​
 +
 +  * Document Retrieval
 +  * Finden von Wiederholungen in Strings
 +  * Grammatikbasiere Textkompression (z. B. Re-Pair)
 +  * Graphen
 +  * Perfekte Hashfunktionen
 +  * Suchbäume (z. B. Rot-Schwarz-Bäume)
 +  * Vorgängerdatenstrukturen (z. B. van-Emde-Boas-Trees)
  
 ===== News ===== ===== News =====
   * Die Einzelpräsentation findet am **03.06.2019** um **14:00** Uhr um Raum **OH14 202** statt.   * Die Einzelpräsentation findet am **03.06.2019** um **14:00** Uhr um Raum **OH14 202** statt.
 
Last modified: 2020-09-25 08:48 by Patrick Dinklage
DokuWikiRSS-Feed