Modul

Die Modulprüfung erfolgt in Form einer mündlichen Gesamtprüfung (ca. 30 min).

Absolventinnen und Absolventen

• kennen die behandelten Fragestellungen der kombinatorischen Optimierung und können diese erläutern,
• kennen typische Methoden zur probabilistischen Analyse von Algorithmen und kombinatorischen Optimierungsproblemen und können diese zur Lösung von konkreten Optimierungsproblemen einsetzen,
• sind mit wesentlichen Beweismethoden vertraut und können diese vorstellen,
• können selbstorganisiert und reflexiv arbeiten.

Keine

Gegenstand der Vorlesung ist die Analyse von Algorithmen und kombinatorischen Optimierungsproblemen in einem probabilistischen Rahmen. Die behandelten Fragestellungen lassen sich häufig mit Hilfe von (geometrischen) Graphen beschreiben. Untersucht wird dann das zu erwartende oder wahrscheinliche Verhalten eines Zielfunktionals des betrachteten Systems (Graphen). Neben asymptotischen Resultaten, die das Verhalten eines Systems zum Beispiel für wachsende Systemgröße beschreiben, werden quantitative Gesetzmäßigkeiten für Systeme fester Größe vorgestellt. Insbesondere behandelt werden

• das Problem langer gemeinsamer Teilfolgen,
• Packungsprobleme,
• das euklidische Problem des/der Handlungsreisenden,
• minimale euklidische Paarungen,
• minimale euklidische Spannbäume.

Für die Analyse von Problemen dieser Art wurden Techniken und Konzepte entwickelt, die in der Vorlesung vorgestellt und angewendet werden. Hierzu gehören

• Konzentrationsungleichungen und Konzentration von Maßen,
• Subadditivität und Superadditivität,
• Martingalmethoden,
• Isoperimetrie,
• Entropie.

Die Inhalte des Moduls "Wahrscheinlichkeitstheorie" werden dringend empfohlen.

Gesamter Arbeitsaufwand: 240 Stunden

Präsenzzeit: 90 Stunden

• Lehrveranstaltung einschließlich studienbegleitender Modulprüfung

Selbststudium: 150 Stunden

• Vertiefung der Studieninhalte durch häusliche Nachbearbeitung des Vorlesungsinhaltes
• Bearbeitung von Übungsaufgaben
• Vertiefung der Studieninhalte anhand geeigneter Literatur und Internetrecherche
• Vorbereitung auf die studienbegleitende Modulprüfung