Mathematik > Lehrerfortbildungen > Kombinatorische Optimierung und Geometrie

Kombinatorische Optimierung und Geometrie

 

Frau P. Huhn
Packungsprobleme

Das Rucksackproblem, bei dem man mit Gewichten und Nutzen versehene Objekte unter Einhaltung eines Maximalgewichts einpacken und den Gesamtnutzen maximieren möchte, ist ein intuitiv verständliches Optimierungsproblem. Es gehört zu einer Klasse von Packungsproblemen, die eine Vielzahl von Anwendungen in der Praxis haben, aber trotz einfacher Formulierung theoretisch nur schwer zu lösende kombinatorische Optimierungsprobleme darstellen. Wir werden einfache Heuristiken und aufwändige exakte Lösungsverfahren, ebenso wie verwandte praktische Problemstellungen vorstellen und so einen Einblick in die kombinatorische Optimierung liefern.

Herr W. Klotz
Heiraten, aber wen?

Beim Heiratsproblem stehen sich n Männer und n Frauen gegenüber, die sich nur zum Teil kennen. Die Aufgabe besteht darin, n Paare zu bilden aus Partnern, die sich gegenseitig kennen. Damit das klappt, müssen je k Männer zusammen mindestens k der gegenüberstehenden Frauen kennen. Der Heiratssatz (Philip Hall, 1935) besagt, dass diese nahe liegende Bedingung nicht nur notwendig, sondern auch hinreichend ist für die Lösung der Aufgabe. Das Heiratsproblem (Matchingproblem) hat viele Varianten, Anwendungen und algorithmische Lösungen. Darüber wird berichtet.

Herr T. Sander
Quadratur des Quadrats

Im Jahre 1903 zeigte Max Dehn, dass ein Rechteck und Quadrate (insbesondere unterschiedlicher Größe), welche das Rechteck parkettieren, kommensurable Seiten besitzen. 1925 gelang erstmalig die explizite Parkettierung eines Rechtecks mit paarweise verschiedenen Quadraten und um 1940 entstanden die ersten entsprechenden Beispiele für ein Quadrat. Der Vortrag wird Problem und Lösungsmethoden beleuchten, wobei der Einsatz von Rechnern, aber auch Netzwerke elektrischer Ströme und das Kirchhoffsche Gesetz eine Rolle spielen.

Programm

09.30 - 09.45 Begrüßung
09.45 - 10.45 Packungsprobleme: Rucksackprobleme (Prof. Dr. P. Huhn)
10.45 - 11.15 Kaffeepause
11.15 - 12.15 Mehrdimensionale Packungsprobleme (Prof. Dr. P. Huhn)
12.15 - 13.30 Mittag
13.30 - 14.30 Heiraten, aber wen? (Prof. Dr. W. Klotz)
14.30 - 15.00 Kaffeepause
15.00 - 16.00 Quadratur des Quadrats (Dr. T. Sander)
16.00 - 16.30 Diskussion und Schlusswort
 
Thema
Kombinatorische Optimierung und Geometrie
Veranstaltung B404.640.213
Ort
Institut für Mathematik der TU Clausthal
Erzstraße 1
38678 Clausthal-Zellerfeld
Zeit
4. Oktober 2006
9.30 Uhr bis 16.30 Uhr
Referenten
Prof. Dr. P. Huhn,
Prof. Dr. W. Klotz,
Dr. T. Sander
Kontakt
Dr. Henning Behnke
Institut für Mathematik
Erzstraße 1
38678 Clausthal-Zellerfeld
Telefon: +49 5323 72-3183
Fax: +49 5323 72-2304
E-Mail: behnke@math.tu-clausthal.de

Sitemap  Datenschutz  Kontakt  Imprint
© TU Clausthal 2017