Mastervorlesung
Ausgewählte Kapitel der Algorithmik
im Sommersemester 2018
Veranstalter: | Prof. Dr. Christian Sohler |
Termine: | Vorlesung | Dienstag, 16-18 Uhr | OH12-1.055 | ab: 10.04.2018 |
.
| Übung | Dienstag, 10-12 Uhr | OH12-1.056 | ab: 17.04.2018 |
Beginn: | 10.04.2018 |
[
Aktuelles]
[
Inhalt]
[
Übungsblätter]
03.07.2018: Der
Übungsblatt 10 wurde veröffentlicht.
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