Übersicht

Inhalt

In dieser Vorlesung beschäftigen wir uns mir modernen Datenstrukturen für fundamentale Objekte wie Bäume, Graphen, Integers und Strings. Diese Datenstrukturen sind Grundlage für viele Anwendungen und ein wichtiger Bestandteil von effizienten Algorithmen. In dieser Vorlesung betrachten wir die Highlights aus verschiedenen Forschungsbereichen und werden dabei Techniken zur Lösung unterschiedlichster Probleme kennen lernen. Neben der theoretischen Analyse der Datenstrukturen werden wir uns auch mit der praktischen Performance der verschiedenen Datenstrukturen und ihren Einsatzgebieten beschäftigen.

Wichtige Informationen

• Vorlesungsaufzeichnungen aus dem letzten Semester sind hier verfügbar.
• Das Thema für das Projekt wird am 08.05.2023 bekannt gegeben.
• Die mündlichen Prüfungen finden am 12.09., 13.09. und 21.09. statt, der 22.09. ist vollständig belegt. Zur Terminvereinbarung senden Sie bitte eine Mail an Frau Blancani (blancani ∂does-not-exist.kit edu) und nennen Sie Ihren vollständigen Namen, Ihre Matrikelnummer, Ihr Studienfach (sofern es nicht Informatik ist) sowie die Version der Prüfungsordnung, nach der Sie studieren.
• Sie müssen sich rechtzeitig am Studierendenportal sowohl für die Übung als auch für die Prüfung anmelden, die Prüfungsanmeldung muss vor dem Prüfungstermin erfolgen.

Folien

1. Kapitel 00 Einführung: Folien und Folien ohne Animationen 
2. Kapitel 01 Bitvektoren: Folien und Folien ohne Animationen (Tafelbilder: 1, 2)
3. Kapitel 02 Succincte Bäume: Foline, Folien ohne Animationen und Handout (Tafelbilder: 1, 2)
4. Kapitel 03 Succincte Graphen: Folien, Folien ohne Animationen (Tafelbilder: 1, 2)
5. Kapitel 04 Predecessor- und RMQ-Anfragen: Folien und Folien ohne Animationen (Tafelbilder: 1, 2, 3)
6. Kapitel 05 Orthogonal Range Searching: Folien und Folien ohne Animationen (Tafelbilder: 1, 2, 3, 4, 5)
7. Kapitel 06 BSP-Bäume und PaCHash: Folien und Folien ohne Animationen (Tafelbilder: 1)
8. Kapitel 07 Suffix-Arrays und String B-Trees: Folien und Folien ohne Animationen (Tafelbilder: 1, 2, 3)
9. Kapitel 08 Komprimierte Suffix-Arrays: Folien und Folien ohne Animationen (Tafelbilder: 1, 2)
10. Kapitel 09 Temporäre Datenstrukturen: Folien und Folien ohne Animationen (Tafelbilder: 1, 2, 3)
11. Kapitel 10 Temporäre Datenstrukturen 2: Folien und Folien ohne Animationen (Tafelbilder: 1, 2)
12. Kapitel 11 Minimal Perfect Hashing: Folien und Folien ohne Animationen (Tafelbilder: 1, 2)
13. Kapitel 12 Dynamische Bitvektoren und Succincte Bäume: Folien und Folien ohne Animationen

Projekt

Eine detaillierte Projektbeschreibung gibt es hier.

• Beispielhafte Gliederung der Ausarbeitung
• Beispieleingaben: Predecessor und RMQs

Hinweise:

• Wenn eine Predecessor-Anfrage kleiner ist, als der kleinste Wert im Array, ist der größte 64-bit Wert zurückzugeben.
• Es gibt keine Präsentation; es muss lediglich eine Ausarbeitung geschrieben werden.
• Bei dem Ausgabeformat fehlt ein =-Zeichen. Das Format hat immer die Form <key>=<value>.