Differences
This shows you the differences between two versions of the page.
fischer:teaching:pg-plads [2019-05-28 08:36] |
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. | ||