Mitgliedschaft

Informatik-Lexikon

Fachbegriffe zu Informatik und deren Anwendung

Wir sind Informatik

Heidi Heilmann

"Ich bin GI-Mitglied seit über 30 Jahren, weil es mir irgendwann selbstverständlich erschien, in der GI mitzuarbeiten – was dann auch sehr schnell real geschah!"

 

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


Dissertationspreisträger Radu Curticapean mit GI-Präsident Peter Liggesmeyer

 

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.

 

Mit dieser Preisverleihung würdigen die beteiligten Gesellschaften - die Gesellschaft für Informatik e.V. (GI), das German Chapter of the ACM (GCHACM), die Oesterreichische Computer Gesellschaft (OCG) sowie die Schweizer Informatikgesellschaft (SI)- eine herausragende Arbeit, die auf dem Gebiet der Komplexitätstheorie einen nennenswerten Fortschritt darstellt.

 

Rin Foto des Preisträgers finden Sie hier zum Herunterladen.

 

 


Übermittlung Ihrer Stimme...

Bewertung:

schlecht
gut

Bewertung abgeben:

Kommentare

Keine Kommentare

Kommentar hinzufügen

Sie müssen angemeldet sein um Kommentare veröffentlichen zu dürfen.