Sprungmarken

Servicenavigation

       

Hauptnavigation

Bereichsnavigation

Mastervorlesung

Ausgewählte Kapitel der Algorithmik

im Sommersemester 2018



.
Veranstalter:Prof. Dr. Christian Sohler
Termine: VorlesungDienstag, 16-18 UhrOH12-1.055ab: 10.04.2018
ÜbungDienstag, 10-12 UhrOH12-1.056ab: 17.04.2018
Beginn: 10.04.2018


[Aktuelles] [Inhalt] [Übungsblätter]


Aktuelles

<b>NEU</b> 03.07.2018: Der Übungsblatt 10 wurde veröffentlicht.


Übungsblätter

Übungsblatt Besprechung
Übungsblatt 01 17.04.2018
Übungsblatt 02 24.04.2018
Übungsblatt 03 08.05.2018
Übungsblatt 04 15.05.2018
Übungsblatt 05 22.05.2018
Übungsblatt 06 29.05.2018
Übungsblatt 07 12.06.2018
Übungsblatt 08 19.06.2018
Übungsblatt 09 26.06.2018
<b>NEU</b> Übungsblatt 10 03.07.2018



Inhalt



Thema der Veranstaltung ist "Algorithmische Grundlagen der Analyse sehr großer Datenmengen (Big Data)". Im Rahmen der Veranstaltung werden Algorithmen und Entwurfstechniken aus dem Gebiet der Analyse großer Datenmengen gelehrt. Mögliche Themen sind unter anderem:

  • sublineare Approximationsalgorithmen
    Die Analyse der Struktur sehr großer Graphen (soziale Netzwerke, Webgraph, etc.) stellt die Algorithmik aufgrund der Größe der Graphen vor große Herausforderungen. Ein Ansatz ist die Verwendung von Stichprobenverfahren. Doch wie kann man Stichproben aus einem großen Graphen ziehen und dabei noch sinnvolle Informationen erhalten? Wir werden einige sublineare Approximationsalgorithmen kennenlernen (z.B. für die Kosten eines minimalen Spannbaums), die dies leisten.

  • Kernmengen
    Unter Kernmengen versteht man Zusammenfassungen von Daten, die eine Eingabemenge bezüglich eines Optimierungsproblems approximieren. Kernmengen haben Anwendungen in Approximationsalgorithmen, verteilten Algorithmen und Datenstromalgorithmen. Wir werden einige Konstruktionen und Techniken kennenlernen, die insbesondere für Algorithmen im Bereich der Datenanalyse relevant sind.

  • Verteilungstesten
    Wieviele Beispiele muss man aus einer Verteilung über den Zahlen {1,...,n} ziehen, um approximativ sagen zu können, ob es sich um die Gleichverteilung handelt? Wenn wir Zugriff auf zwei Verteilungen über Zahlen aus dem Bereich {1,...,n} haben, können wir effizient zwischen den Fällen unterscheiden, dass die Verteilungen identisch sind und dass sie sich signifikant unterscheiden? Wir werden einige Algorithmen kennenlernen, die diese Probleme mit sublinear vielen Beispielen lösen.

  • Datenstromalgorithmen
    Datenstromalgorithmen dienen der Verarbeitung von Datenmengen, die sogar zu groß sind, um diese abzuspeichern. Daher darf ein Datenstromalgorithmus nur sublinearen Speicherplatz verwenden. Wir werden Algorithmen für die Approximation der Anzahl der Elemente eines Datenstroms entwickeln. Dann werden wir versuchen, häufig vorkommende Elemente zu identifizieren und andere Kennzahlen wie Frequenzmomente zu approximieren.




Letzte Änderung am 03.07.2018 von A. Krivošija