Topic outline

  • General

  • Seminar: Entwurf und Analyse von Datenstrukturen

    Umfang:

    5 ECTS, 2 SWS

    Zeit & Ort:

    mittwochs, 14:15–15:45 Uhr, SE III

    Voraussetzung:

    Algorithmen und Datenstrukturen (dringend empfohlen)

    Zielgruppe:

    Bachelor Informatik, Bachelor Luft- und Raumfahrt-Informatik, Master Informatik

    Dozenten:

    Alexander Wolff, Benedikt Budig, Krzysztof Fleszar, Fabian Lipp

    Anmeldung:

    über SB@Home zwischen 01.04.2016 und 30.04.2016

    Tragen Sie sich bitte außerdem möglichst bald als Teilnehmer in diesen Wuecampus-Kurs ein, falls Sie am Seminar teilnehmen möchten.

    Der erste Termin ist am 13. April 2016. An diesem Termin besprechen wir den Ablauf des Seminars und die Vortragsthemen. Aus diesem Grund bitten wir um vollständige Anwesenheit. Sie sollten sich vor diesem Termin schon Gedanken über ein mögliches Thema gemacht haben.

    • Thema

      In diesem Seminar werden fortgeschrittene Datenstrukturen behandelt, die dafür entworfen sind, bestimmte Anfragen effizient zu beantworten. Das Seminar knüpft an die Vorlesung "Algorithmen und Datenstrukturen" an. Die thematischen Schwerpunkte sind:

      • Datenstrukturen für geometrische Anfragen
        Solche Datenstrukturen verwalten geometrische Objekte. Geometrische Anfragen können effizient beantwortet werden, z.B. ob sich ein gegebener Punkt in einer bestimmten Region befindet. Die Anwendungen solcher Datenstrukturen sind vielfältig und beinhalten z.B. Computergrafik und GIS.
      • Balancierte Suchbäume
        Anfragen auf Suchbäumen haben nur dann beweisbar gute Laufzeiten, wenn der Baum balanciert ist, das heißt seine Höhe in Abhängigkeit von der Anzahl der Knoten begrenzt ist. Eine Möglichkeit zur Balancierung sind Rot-Schwarz-Bäume, die Sie in der Vorlesung bereits kennengelernt haben. In diesem Seminar wollen wir uns mit weiteren Möglichkeiten beschäftigen Bäume zu balancieren.
      • Dynamische Datenstrukturen für Graphen
        Aus der Vorlesung kennen Sie effiziente Algorithmen für gängige Graphenprobleme, z. B. Finden von minimalen Spannbäumen, Testen auf Zusammenhang. Dafür sind Sie bisher immer von statisch vorgegebenen Graphen ausgegangen. Es gibt allerdings auch Datenstrukturen, die für Veränderungen an den Graphen ausgelegt sind. Das heißt, dass die Lösung beispielsweise beim Hinzufügen oder Entfernen von Kanten mit wenig Aufwand aktualisiert werden kann.

      Lernziele

      Die TeilnehmerInnen lernen, sich intensiv in ein abgegrenztes Thema aus dem Themengebiet einzuarbeiten, dieses didaktisch aufzubereiten und den anderen KursteilnehmerInnen in einem Vortrag zu vermitteln. Dieses Thema und die zugrundeliegende Literatur sollen sie selbstständig finden und vorschlagen.

      Sie bekommen im Seminar einen Überblick über Entwurfstechniken für fortgeschrittene Datenstrukturen und dazugehörige Algorithmen und vertiefen ihre Kenntnisse in deren Analyse.

      Module

      Bei erfolgreicher Teilnahme wird die Leistung als (benotetes) Seminar für den Bachelor- oder Masterstudiengang Informatik bzw. Luft- und Raumfahrt-Informatik eingetragen.

  • Ablauf

    1. Im ersten Treffen werden wir einen kurzen Überblick über die drei Themengebiete geben und den Ablauf des Seminars erklären. Bei diesem Treffen wollen wir gemeinsam mit Ihnen Ihre Vortragsthemen festlegen. Wir erwarten daher, dass Sie bereits eine Literaturrecherche begonnen haben und ein mögliches Thema sowie dazugehörige Literatur mitbringen. Siehe dazu auch den Abschnitt Vortragsthemen.
    2. Im zweiten Treffen gibt jeder Teilnehmer einen kurzen Überblick über sein Thema (max. 5 Minuten, 3 Folien). Dies dient hauptsächlich dazu, schon frühzeitig Feedback zu erhalten und mögliche Fehler im eigentlichen Seminarvortrag zu vermeiden. Außerdem werden wir Genaueres zur Gestaltung der Vorträge und der Ausarbeitung sagen.
    3. In den folgenden Treffen finden die eigentlichen Vorträge der Teilnehmer statt. Neben dem Vortrag bleibt auch Zeit zur Diskussion der Themen und zum Feedback an die Vortragenden.

    • Vortragsthemen

      Grundlage jedes Vortragsthemas ist eine fortgeschrittene Datenstruktur. Quellen dafür sollen ein oder mehrere wissenschaftliche Artikel bzw. Lehrbücher sein. Wir geben keine konkreten Themen oder Quellen vor; stattdessen sollen Sie selbst Literaturrecherche betreiben und beim ersten Treffen mit uns ein Thema absprechen. Wir zeigen im Folgenden einige Anforderungen auf, die Ihr Thema erfüllen soll, und geben einige Hinweise, wie Sie ein geeignetes Thema finden können. Falls Sie Fragen dazu haben, sprechen sie uns an!

      Anforderungen an die Themen

      • Thema: stammt aus einem der drei Themenschwerpunkte (siehe oben) und wurde nicht im Rahmen der Vorlesung Algorithmen und Datenstrukturen behandelt.
      • Wissenschaftlicher Anspruch: die Datenstruktur wurde in einer wissenschaftlichen Arbeit oder in einem Lehrbuch diskutiert.
      • Theoretischer Anspruch: die Analyse der Datenstrukur ist nicht trivial, sondern enthält einen interessanten Beweis.
      • Anwendungsbezug: die Datenstruktur hat praktische oder theoretische Relevanz.
      • Geeigneter Umfang: die Datenstruktur kann im Rahmen eines Vortrags von 30 bis 60 Minuten sinnvoll vorgestellt und analysiert werden.
      • Geeigneter Schwierigkeitsgrad: der Vortrag muss mit Vorkenntnissen einzig aus der Vorlesung Algorithmen und Datenstrukturen verständlich sein.

      Tipps zur Themenfindung

      • Lehrbücher, beispielsweise:
        • de Berg, Cheong, van Kreveld, Overmars: Computational Geometry
        • Cormen, Leiserson, Rivest, Stein: Introduction to Algorithms
      • Die (englische) Wikipedia kann ein interessanter Startpunkt zur Themensuche sein. Natürlich sollten alle Themen mit "ordentlichen Quellen" (Konferenzpaper, Journal-Artikel, Lehrbücher) belegt sein. In guten Wikipedia-Artikeln finden Sie in der Regel Verweise auf diese Quellen. In der Wikipedia gibt es beispielsweise eine Übersichtsseite mit Datenstrukturen. Darunter sind viele Varianten von balancierten Bäumen und auch Datenstrukturen für geometrische Anfragen.
      • Demetrescu, Eppstein, Galil, Italiano: Dynamic Graph Algorithms (erreichbar aus dem Uni-Netz)
        Dieses Buchkapitel gibt einen Überblick über Algorithmen in diesem Bereich
      • Es gibt Suchmaschinen, die auf wissenschaftliche Artikel spezialisiert sind, zum Beispiel Google Scholar.

      • Vorträge

        • Ihr Vortrag sollte etwa 30–45 Minuten (einzeln) bzw. 45–60 Minuten (in Zweiergruppen) dauern.
        • Wir empfehlen für die Erstellung der Folien das kostenlose Programm ipe (verfügbar für Linux, Windows, Mac). Als Einstieg können Sie gerne einen Blick auf die Folien vom Einführungsvortrag werfen. Diese PDF-Datei können Sie mit ipe öffnen und weiterbearbeiten.
        • Gestalten Sie Ihren Vortrag abwechlungsreich und zeigen Sie Beispiele und Bilder. Beziehen Sie die Seminarteilnehmer mit Zwischenfragen oder kleinen Aufgaben mit ein.
        • Die Folien ihres Vortrages werden wir anschließend hier für alle Teilnehmer zur Verfügung stellen.

      • Ausarbeitungen

        Die Ausarbeitung zu ihrem Thema sollte etwa 10 Seiten (zuzüglich Titelseite) umfassen. Sie soll nicht nur einen Artikel zusammenfassen, sondern auch darüber hinaus gehen. Zum Einen eignet sich dafür das Material, dass sie durch eigene Literaturrecherche gefunden haben. Nehmen Sie auch Anregungen in ihre Ausarbeitung mit auf, die in der Diskussion nach Ihrem Vortrag geäußert werden.

        Die Ausarbeitungen sollen mit LaTeX erstellt werden. Wenn Sie noch keine Erfahrung mit LaTeX haben, können Sie beispielsweise an einem der kostenlosen Kurse im Rechenzentrum teilnehmen. Bitte verwenden Sie für Ihre Ausarbeitung die unten zur Verfügung gestellte Vorlage.

        Geben Sie zwei Wochen nach Ihrem Vortrag eine Vorabversion der Ausarbeitung bei Ihrem Betreuer ab. Von ihm erhalten Sie Feedback, das Sie für die endgültige Version nutzen können. Die Frist für die endgültige Abgabe ist Freitag, 26.08.2016.

      • Bewertung

        Voraussetzungen für das Bestehen des Seminars:

        • Halten einer Präsentation zum gewählten Thema
        • Anfertigen einer Ausarbeitung
        • Regelmäßige Teilnahme am Seminar und aktive Mitarbeit (einmaliges Fehlen bei einem Vortrag ist erlaubt)