You are here: WS2008 > CoCo (14 Feb 2012, MichaelRitter)

 

 
Computational Convexity - Optimale Containment Probleme

Vorlesung

 

Dozent: Dr. René Brandenberg
Übungsleitung: Dr. René Brandenberg

Aktuelles Termine Was ist Computational Convexity? Was bedeutet Optimales Containment? An wen richtet sich die Vorlesung? Anrechenbarkeit? Übungsblätter

Aktuelles

  • 6. März 2009: Vorlesungsskipt: jetzt vollständig.
  • 14. Feb. 2008: Vorlesungsskipt: zunächst Kapitel 1-5. Der Rest folgt demnächst.
  • 11. Dez. 2008: Der Beweis der $\mathbb{NP}$-Vollständigkeit von $\sc{Parmax}[-1,1]_p$ aus der Vorlesung vor 3 Jahren Normmaximierung über Parallelotopen
  • 9. Nov. 2008: $l_s(K)$ wird es in der nächsten Vorlesung definiert. Diesen Teil von Aufgabe 2.5 bitte auslassen.
  • 31. Okt. 2008: Eine kurze Übersicht zu komplexitätstheoretischen Grundlagen aus der Vorlesung vor 3 Jahren: Komplexitätstheorie
  • 23. Okt. 2008: Die Übungen fangen ab der dritten Woche um 16.00 Uhr an.
  • 29. Sept. 2008: Wir fangen in der ersten Semesterwoche, Donnerstag 16. Oktober, mit zwei Vorlesungen (12-14 Uhr und 16-18 Uhr) an.

Termine

  Tag Uhrzeit Raum Hinweise  
Vorlesung Do 12:30 - 14:00 MI 02.08.011   Studienbeitraege Banner
Übung Do 16:00 - 17:30 MI 02.04.011 zweiwöchig Studienbeitraege Banner

Was ist Computational Convexity?

Obwohl auch als Teil der Algorithmischen Geometrie aufgefasst, stammen ihre Ideen und Techniken eher aus Gebieten wie der Linearen Programmierung, der Polyedrische Kombinatorik und der Algorithmischen Theorie der Konvexen Körper, welche sich alle drei rückwirkend unter den Begriff der Computational Convexity einordnen lassen.

In der Computational Convexity werden zwei in der Algorithmischen Geometrie nicht unbedingt gängige Sachverhalte betont: zum einen werden oftmals allgemeine normierte Räume betrachtet, zum anderen wird die Dimension bei den behandelten Problemstellungen explizit als Teil des Inputs verstanden, wie es in der Linearen Programmierung üblich ist.

Was bedeutet Optimales Containment?

Von Containment Problemen spricht man bei Aufgabenstellungen, deren Ziel die Bestimmung oder Approximation extremaler Körper einer gegebenen Klasse ist, welche in einer gegebenen Menge enthalten sind oder diese enthalten. Beispielhaft betrachte man den folgenden Grundtyp eines allgemeinen Containment Problems (Entscheidungsversion). Sei dazu $d$ eine natürliche Zahl, $\\mathcal{C}_d$ eine Familie von abgeschlossenen konvexen Teilmengen des $\mathbb{R}^d$ und $\omega_d:\mathcal{C}_d \to \mathbb{R}$ ein nicht-negatives und bezüglich der Mengeninklusion monotones Funktional. Weiter sei $\Gamma = (\mathcal{C}_d)_{d \in \mathbb{N}}$ und $\Omega=(\omega_d)_{d \in \mathbb{N}}$. Damit lässt sich folgendes Problem stellen:

$(\Gamma, \Omega)$-INBODY

Eingabe: $d \in \mathbb{N}$, $K \subset \mathbb{R}^d$ ein konvexer Körper und $\lambda \in \mathbb{Q}_+$. Frage: Existiert ein $C \in \mathcal{C}_d$, sodass $C \subset K$ und $\omega_d(C) \ge \lambda$?

Ein wichtiger Spezialfall der Containment Probleme sind die Radien konvexer Körper. Die Bestimmung der vier Grundradien (In-, Umradius, Dicke und Durchmesser) ist ein klassisches Problem der Konvexgeometrie.

demo10.png
Darstellung der Einbettung einer Kreisscheibe mit maximalem Radius in einen Würfel.

Aufgrund zahlreicher Anwendungen, sowohl in anderen mathematischen Teildisziplinen als auch in der Medizin (z.B. bei der Mustererkennung oder der automatisierten Operationsplanung), Robotik, Visualisierung, Materialwissenschaft oder der Genetik, ist die Radienberechnung in den letzten Jahren in den Fokus vieler wissenschaftlicher Veröffentlichungen gerückt. Auch Verallgemeinerungen der Radienproblematik, die in den Bereich des optimalen Containments fallen, besitzen zahlreiche Anwendungen, wie etwa bei Shape-Fitting-, Clustering- und Datenreduktionsaufgaben. Auch hier gibt es zahlreiche neue Resultate.

An wen richtet sich die Veranstaltung?

An mathematischem Wissen vorausgesetzt wird eine solide Grundausbildung in Analysis, Linearer Algebra und Optimierung 1 (Lineare Programmierung). Kenntnisse im Bereich der Konvexen Analysis und der Kombinatorischen Optimierung helfen, sind aber nicht zwingend notwendig. Damit richtet sich die Vorlesung an alle Mathematiker und Informatiker (mit Nebenfach Mathematik) ab dem fünften Fachsemester.

üfung

Anrechenbarkeit

Für die Studierenden der Mathematik können Vorlesung und Übung als 3 SWS für eine Hauptdiplomsprüfung im Bereich der Angewandten Mathematik oder Vertiefungsfach anerkannt werden.

Die Anrechenbarkeit wurde mit Prof. Gritzmann und Prof. Taraz abgesprochen. Beide sind bereit Studierende über die Inhalte der Veranstaltung zu prüfen. Sollten Sie die Veranstaltung bei einem anderen Prüfer einbringen wollen, so klären Sie bitte im voraus, ob dieser dazu bereit ist.

Übungsblätter

Übungsblatt Hinweise
Blatt 01  
Blatt 02  
Blatt 03  
Blatt 04  
Blatt 05  
Blatt 06  
Topic revision: r91 - 14 Feb 2012 - 17:53:37 - MichaelRitter
 
Bottomleft LogoBottomright Logo
Impressum  |  Disclaimer und Rechtshinweise  |  AnregungenCopyright Technische Universität München, M9