Differences
This shows you the differences between two versions of the page.
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. |