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-05-28 08:36]
Patrick Dinklage
fischer:teaching:pg-plads [2019-05-28 08:37] (current)
Patrick Dinklage
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.
  
 
Last modified: 2019-05-28 08:37 by Patrick Dinklage
DokuWikiRSS-Feed