Komplexität von Zählproblemen: GI-Dissertationspreis für Radu Curticapean

Logo: Gesellschaft für Informatik e.V.
Logo: Gesellschaft für Informatik e.V.

Bonn (pressrelations) –

Komplexität von Zählproblemen: GI-Dissertationspreis für Radu Curticapean

Für die beste Informatikdissertation im deutschsprachigen Raum ist in diesem Jahr Dr. rer. nat. Radu Curticapean ausgezeichnet worden. Radu Curticapean promovierte im Jahr 2015 zum Thema “Die einfachen, kleinen und langsamen Dinge zählen: Über die parametrisierte Komplexität von Zählproblemen” bei Prof. Dr. Markus Bläser an der Universität des Saarlandes.

Die abzählende Kombinatorik ist das Teilgebiet der Mathematik, in dem gezählt wird, auf wie viele Arten sich Bausteine zu komplexeren Gebilden zusammensetzen lassen. So kann man etwa fragen, auf wie viele Arten sich n Objekte in einer Reihe anordnen lassen. Während diese Anzahl noch durch die Fakultät n! = n*(n-1)*(n-2)*…*1 gegeben ist, lassen sich viele andere Größen oft nicht so leicht ausdrücken.

In der statistischen Physik etwa fragt man im Rahmen des Dimer-Modells, wie viele Möglichkeiten sich ergeben, wenn auf einem Gitter angeordnete Atome zu Paaren gruppiert werden sollen. Jedes Atom soll hier mit exakt einem seiner Gitternachbarn eine Bindung eingehen. Für spezielle Gitterarten lässt sich die Anzahl solcher Gruppierungen effizient mit Computern bestimmen.

In der Arbeit sind zum einen neue Methoden entwickelt worden, Varianten des Dimer-Modells und andere kombinatorische Probleme effizient mit Computern zu berechnen. Zum anderen wird für andere Probleme aufgezeigt, dass sie sich nach gängigen Annahmen der Informatik höchst unwahrscheinlich effizient berechnen lassen. Der Schwerpunkt der Arbeit liegt auf dieser “Negativabgrenzung”, die innerhalb der theoretischen Informatik als Komplexitätstheorie bekannt ist.

Die Gesellschaft für Informatik e.V. (GI) ist eine gemeinnützige Fachgesellschaft zur Förderung der Informatik in all ihren Aspekten und Belangen. Gegründet im Jahr 1969 ist die GI mit ihren heute rund 20.000 Mitgliedern die größte Vertretung von Informatikerinnen und Informatikern im deutschsprachigen Raum. Die Mitglieder der GI kommen aus Wissenschaft, Wirtschaft, öffentlicher Verwaltung, Lehre und Forschung.

Pressekontakt:

Cornelia Winter
Geschäftsführung
Gesellschaft für Informatik e.V. (GI)
Wissenschaftszentrum
Ahrstr. 45
53175 Bonn

Telefon.: +49 (0)228/302-145
Fax: +49 (0)228/302-167

Mail: gs@gi.de / WWW: http://www.gi.de

Leave a reply:

Your email address will not be published.

Time limit is exhausted. Please reload CAPTCHA.

Site Footer