Text-Indexierung

  • Type: Vorlesung (V)
  • Semester: WS 17/18
  • Time: 19.10.2017
    09:45 - 11:15 wöchentlich
    50.34 Raum 236 50.34 INFORMATIK, Kollegiengebäude am Fasanengarten


    26.10.2017
    09:45 - 11:15 wöchentlich
    50.34 Raum 236 50.34 INFORMATIK, Kollegiengebäude am Fasanengarten

    02.11.2017
    09:45 - 11:15 wöchentlich
    50.34 Raum 236 50.34 INFORMATIK, Kollegiengebäude am Fasanengarten

    09.11.2017
    09:45 - 11:15 wöchentlich
    50.34 Raum 236 50.34 INFORMATIK, Kollegiengebäude am Fasanengarten

    16.11.2017
    09:45 - 11:15 wöchentlich
    50.34 Raum 236 50.34 INFORMATIK, Kollegiengebäude am Fasanengarten

    23.11.2017
    09:45 - 11:15 wöchentlich
    50.34 Raum 236 50.34 INFORMATIK, Kollegiengebäude am Fasanengarten

    30.11.2017
    09:45 - 11:15 wöchentlich
    50.34 Raum 236 50.34 INFORMATIK, Kollegiengebäude am Fasanengarten

    07.12.2017
    09:45 - 11:15 wöchentlich
    50.34 Raum 236 50.34 INFORMATIK, Kollegiengebäude am Fasanengarten

    14.12.2017
    09:45 - 11:15 wöchentlich
    50.34 Raum 236 50.34 INFORMATIK, Kollegiengebäude am Fasanengarten

    21.12.2017
    09:45 - 11:15 wöchentlich
    50.34 Raum 236 50.34 INFORMATIK, Kollegiengebäude am Fasanengarten

    11.01.2018
    09:45 - 11:15 wöchentlich
    50.34 Raum 236 50.34 INFORMATIK, Kollegiengebäude am Fasanengarten

    18.01.2018
    09:45 - 11:15 wöchentlich
    50.34 Raum 236 50.34 INFORMATIK, Kollegiengebäude am Fasanengarten

    25.01.2018
    09:45 - 11:15 wöchentlich
    50.34 Raum 236 50.34 INFORMATIK, Kollegiengebäude am Fasanengarten

    01.02.2018
    09:45 - 11:15 wöchentlich
    50.34 Raum 236 50.34 INFORMATIK, Kollegiengebäude am Fasanengarten

    08.02.2018
    09:45 - 11:15 wöchentlich
    50.34 Raum 236 50.34 INFORMATIK, Kollegiengebäude am Fasanengarten
  • Lecturer: Dr. Simon Gog
  • Lv-No.: 2400057
VoraussetzungenEmpfehlungen:

Kenntnisse aus der Vorlesung Algorithmentechnik werden vorausgesetzt.

BeschreibungIn der VorlesungText-Indexierung werden Algorithmen undDatenstrukturen vorgestellt, welche effizientes Suchen in großenDatenmengen ermöglichen. So kann etwa die Frage "Wie oft kommt MusterX?" in einer Laufzeit beantwortet werden, die nicht von der Länge derDatenmenge abhängt, sondern nur von der Länge des Musters X selbst.
Es werden in dieser Vorlesung neben klassischenIndex-Datenstrukturen, etwa Suffix Array und Suffix Tree, auchplatzeffiziente Strukturen, wie z. B. FM-Indizes, behandelt.
Lehrinhalt

In der Vorlesung werden nicht nur theoretische Ergebnisse aus dem Bereich der Text-Indexierung vermittelt, sondern auch praktische Anwendungen, wobei wir für letzteres auf die SDSL-Bibliothek zurückgreifen. Diese Bibliothek enthält alle Datenstrukturen, die in der Veranstaltung vorgestellt werden. Durch Übungsaufgaben und kleine Programmierprojekte wird der Stoff der Vorlesung vertieft und praktisch angewandt.

ArbeitsbelastungVorlesung mit Projekt/Experiment mit 3 SWS, 5 LP entsprechen ca. 150 Arbeitsstunden, davon

ca. 30 Std. Besuch der Vorlesung
ca. 60 Std. Vor- und Nachbereitung
ca. 30 Std. Bearbeiten des Projekts/Experiments
ca. 30 Std. Prüfungsvorbereitung

ZielDie Studierenden erwerben ein systematisches Verständnis algorithmischer Fragestellungen und Lösungsansätze im Bereich der Text-Indexierung, das auf dem bestehenden Wissen im Themenbereich Algorithmik aufbaut. Außerdem können sie erlernte Techniken auf verwandte Fragestellungen anwenden und aktuelle Forschungsthemen im Bereich Text-Indexierung interpretieren und nachvollziehen.

Nach erfolgreicher Teilnahme an der Lehrveranstaltung können die Studierenden

  • Begriffe, Strukturen, grundlegende Problemdefinitionen und Algorithmen aus der Vorlesung erklären;
  • auswählen, welche Algorithmen und Datenstruktuen zur Lösung einer Fragestellung geeignet sind und diese ggf. den Anforderungen einer konkreten Problemstellung anpassen;
  • Algorithmen und Datenstrukturen ausführen, mathematisch präzise analysieren und die algorithmischen Eigenschaften beweisen.
PrüfungDie Erfolgskontrolle erfolgt in Form einer mündlichen Prüfung nach § 4 Abs. 2 Nr. 2 SPO und eines Projekts/Experiments als Erfolgskontrolle anderer Art nach § 4 Abs. 2 Nr. 3.

Gewichtung: 80 % mündliche Prüfung, 20 % Projekt/Experiment.

Prüfung

Vor der mündlichen Prüfung müssen Sie sich am Studierendenportal  für diese Veranstaltung anmelden. Einen Prüfungstermin vereinbaren Sie bitte direkt mit Herrn Dr. Gog, mit CC an blancani ∂does-not-exist.kit edu.

Übersicht

Voraussetzungen Empfehlungen:

Kenntnisse aus der Vorlesung Algorithmentechnik werden vorausgesetzt.
Beschreibung In der VorlesungText-Indexierung werden Algorithmen undDatenstrukturen vorgestellt, welche effizientes Suchen in großenDatenmengen ermöglichen. So kann etwa die Frage "Wie oft kommt MusterX?" in einer Laufzeit beantwortet werden, die nicht von der Länge derDatenmenge abhängt, sondern nur von der Länge des Musters X selbst.
Es werden in dieser Vorlesung neben klassischenIndex-Datenstrukturen, etwa Suffix Array und Suffix Tree, auchplatzeffiziente Strukturen, wie z. B. FM-Indizes, behandelt.
Lehrinhalt

In der Vorlesung werden nicht nur theoretische Ergebnisse aus dem Bereich der Text-Indexierung vermittelt, sondern auch praktische Anwendungen, wobei wir für letzteres auf die SDSL-Bibliothek zurückgreifen. Diese Bibliothek enthält alle Datenstrukturen, die in der Veranstaltung vorgestellt werden. Durch Übungsaufgaben und kleine Programmierprojekte wird der Stoff der Vorlesung vertieft und praktisch angewandt.
Arbeitsbelastung Vorlesung mit Projekt/Experiment mit 3 SWS, 5 LP entsprechen ca. 150 Arbeitsstunden, davon

ca. 30 Std. Besuch der Vorlesung
ca. 60 Std. Vor- und Nachbereitung
ca. 30 Std. Bearbeiten des Projekts/Experiments
ca. 30 Std. Prüfungsvorbereitung
Ziel Die Studierenden erwerben ein systematisches Verständnis algorithmischer Fragestellungen und Lösungsansätze im Bereich der Text-Indexierung, das auf dem bestehenden Wissen im Themenbereich Algorithmik aufbaut. Außerdem können sie erlernte Techniken auf verwandte Fragestellungen anwenden und aktuelle Forschungsthemen im Bereich Text-Indexierung interpretieren und nachvollziehen.

Nach erfolgreicher Teilnahme an der Lehrveranstaltung können die Studierenden

  • Begriffe, Strukturen, grundlegende Problemdefinitionen und Algorithmen aus der Vorlesung erklären;
  • auswählen, welche Algorithmen und Datenstruktuen zur Lösung einer Fragestellung geeignet sind und diese ggf. den Anforderungen einer konkreten Problemstellung anpassen;
  • Algorithmen und Datenstrukturen ausführen, mathematisch präzise analysieren und die algorithmischen Eigenschaften beweisen.
Prüfung Die Erfolgskontrolle erfolgt in Form einer mündlichen Prüfung nach § 4 Abs. 2 Nr. 2 SPO und eines Projekts/Experiments als Erfolgskontrolle anderer Art nach § 4 Abs. 2 Nr. 3.

Gewichtung: 80 % mündliche Prüfung, 20 % Projekt/Experiment.