Hauptseminar zu "Sublineare Algorithmen"
Dozent: Prof. Dr. Christian Sohler
Vorbesprechung:
Inhalte
Sehr große Datenmengen treten in vielen Anwendungen auf. Für Ihre Verarbeitung benötigt man spezielle Algorithmen, deren Ressourcenbedarf (Laufzeit, Speicherplatz) sublinear in der Größe der Eingabe ist. Im Gebiet der sublinearen Algorithmen wird die Entwicklung und Analyse solcher Algorithmen untersucht. Im Rahmen des Seminars sollen grundlegende Arbeiten aus den unterschiedlichen Teilgebieten der sublinearen Algorithmen besprochen werden. Folgende Teilgebiete werden betrachtet:
Im Property Testing wird untersucht, inwieweit man mit kleinen, zufälligen Stichproben entscheiden kann, ob ein sehr großes Objekt (z.B. ein Graph oder eine Funktion) eine gegebene Struktur hat oder sich deutlich von dieser Struktur unterscheidet.
Verteilungstesten hat sich aus dem Property Testing entwickelt und betrachtet Fragestellungen, bei denen Eigenschaften von Verteilungen getestet werden sollen.