Am 6. Juli 2016 referiert Prof. Helmut Alt der Freien Universität Berlin zum Thema "Logik und Komplexität und ihre Anwendung auf Packungsprobleme". Der Vortrag beginnt um 17 Uhr in Hörsaal 5 und richtet sich insbesondere an alle Studierenden und Lehrenden der IT-Studiengänge sowie an Interessierte an einem Überblick zu den genannten Gebieten.

Zum Vortrag:

Anfang des 20. Jahrhunderts glaubten Mathematiker, vor allem David Hilbert, dass man einen Algorithmus finden könne, der alle in formaler Logik formulierten mathematischen Aussagen beweist oder widerlegt. Hilbert plädierte für einen Optimismus in der Forschung und lebte nach seinem Motto "Wir müssen wissen, wir werden wissen". In den dreißiger Jahren folgte der bahnbrechende Beweis von Kurt Friedrich Gödel, dass selbst arithmetische Aussagen über ganze Zahlen unentscheidbar sind, also ein solcher Algorithmus dafür nicht existiert. Im Gegensatz dazu sind jedoch solche Aussagen über reelle Zahlen entscheidbar, wie von Alfred Tarski 1948 gezeigt wurde. Später wurden auch, speziell von John Francis Canny, Algorithmen beschränkter Komplexität gefunden. Diese können auf viele Probleme, insbesondere in der algorithmischen Geometrie angewandt werden.

Der Vortrag gibt einen Überblick über diese Entwicklungen und beschreibt Anwendungen vor allem auf Packungsprobleme, das heißt die Aufgabe, eine gegebene Menge von geometrischen Objekten in einen möglichst kleinen Behälter zu packen.

Zum Referenten:

Der Referent Prof. Dr. Helmut Alt hat die Forschungsgruppe Theoretische Informatik an der FU Berlin aufgebaut. Sie unterhält inzwischen ein dichtes Netzwerk mit Wissenschaftlern weltweit für einen regen Austausch und eine akademische Zusammenarbeit. Die algorithmische Geometrie ist ein Forschungsschwerpunkt dieser Gruppe. Sie bietet exzellente Möglichkeiten für eine Promotion im Anschluss an ein Master-Studium. Prof. Sebastian Iwanowski hält engen Kontakt zu den Wissenschaftlern der Gruppe, da er selbst in dieser Forschungsgruppe promoviert hat.

Über das Kolloquium hinaus übernimmt Prof. Alt am darauffolgenden Tag, dem 7. Juli, die englischsprachige Algorithmikvorlesung von Prof. Iwanowski, die um 9:30 Uhr in HS 3 stattfindet. Das dort behandelte Thema sind Flussalgorithmen.

Kolloquium in Kürze:

Was: Kolloquium: Logik und Komplexität und ihre Anwendung auf Packungsprobleme
Wann: 6. Juli, 17 Uhr
Wo: Hörsaal 5