61213 Seminar Diskrete Optimierung ,,Diskrepanztheorie'' A. Srivastav
2-std., Do. 9.30-11.00, Beginn: 29. 4.
R509, Haus Informatik I, Hermann-Rodewald-Str. 3
Zielgruppe: Studierende der Mathematik und Informatik nach dem Vordiplom und Stipendiaten des Graduiertenkollegs
Basis: Grundvorlesungen Mathematik
Inhalte:
Das Thema des Seminars ist die Theorie der kombinatorischen und geometrischen Diskrepanzen. Die Diskrepanztheorie hat ihre Wurzeln in der Untersuchung der Irregularitäten der Verteilung von Zahlenfolgen aus dem Intervall [0,1]. Van der Corput (1935) vermutete, daß jede unendliche Folge in [0,1] eine beliebig große Abweichung von einer perfekt gleichverteilten Folge aufweist. Diese Vermutung wurde zuerst von von Aardanne-Ehrenfest 1945 bewiesen. Mit der van der Corputschen Vermutung entstand der Diskrepanzbegriff als quantitatives Maß für die Irregularität der Verteilung einer gegebenen, unendlichen Folge oder Punktmenge.
Nachfolgend wurde der Diskrepanzbegriff in verschiedene Richtungen verallgemeinert, und es stellte sich heraus, daß Diskrepanzen in verschiedenen Bereichen der reinen und angewandten Mathematik, aber auch beim Entwurf effizienter Algorithmen in der theoretischen Informatik von Bedeutung sind.
Das typische Problem in der kombinatorischen Diskrepanztheorie ist die balancierte 2-Färbung eines Mengensystems: Gegeben ein System S von Teilmengen einer Grundmenge X, man finde eine rot-blau Färbung von X, so daß in jeder Menge aus S der Betrag der Differenz zwischen der Anzahl rot gefärbter Punkte und der Anzahl blau gefärbter Punkte möglichst klein ist. Die Diskrepanz einer gegebenen 2-Färbung ist das Maximum dieser Zahlen über S, und die Diskrepanz von S ist die minimal mögliche Diskrepanz einer 2-Färbung von S. Die kombinatorische Diskrepanztheorie untersucht die Abhängigkeit der Diskrepanz von verschiedenen, kombinatorischen Parametern des betrachteten Mengensystems.
Bei geometrischen Problemen ist das Hauptanliegen die Bestimmung des asymptotischen Verhaltens einer n-Punkte Menge in einem Raum fester Dimension, wobei die Diskrepanz bezüglich geometrischer Objektklassen gemessen wird (Hyperebenen,achsenparallele Quader, Vollkugeln).
Literatur: Originalarbeiten
Mail an WebMaster |
[Mon Oct 20 14:24:33 MET DST 1997] |
Impressum |