Presseportal

Prof. Dr. Martin Grohe, Mitglied des Instituts für Informatik der Humboldt-Universit?t zu Berlin, wird im Rahmen der Reinhart Koselleck-Projekte der Deutschen Forschungsgemeinschaft (DFG) mit 1,25 Millionen Euro in den kommenden fünf Jahren gef?rdert. Die DFG er?ffnet in diesem Rahmen herausragenden Wissenschaftlerinnen und Wissenschaftlern die M?glichkeit, in hohem Ma? innovative oder im positiven Sinn risikobehaftete Projekte durchzuführen.

Im Mittelpunkt von Grohes Forschungsprojekt aus dem Gebiet der algorithmischen Graphentheorie steht das Graphenisomorphieproblem, das als eines der wichtigsten offenen Probleme der theoretischen Informatik gilt. Die Graphenisomorphie spielt eine wichtige Rolle, wenn es darum geht, zwei Objekte per Computer auf ihre Gleichheit beziehungsweise Ungleichheit zu untersuchen. ?Die ersten Anwendungen des Problems lagen in der Chemie, wo es um den Vergleich von gro?en Molekülen ging, die aus vielen Atomen zusammengesetzt sind. Das Problem hat aber auch zahlreiche Anwendungen in der Informatik, beispielsweise in der Künstlichen Intelligenz oder bei der Entwicklung von Programmiersprachen“, erkl?rt Grohe. Der theoretische Informatiker, der den Lehrstuhl Logik in der Informatik inne hat, untersucht in diesem Forschungsprojekt mit verschiedenen Ans?tzen die Komplexit?t des Isomorphieproblems. Ziel ist die Entwicklung eines effizienten Algorithmus zur L?sung des Problems. Auch die Studierenden werden profitieren, da eine Vorlesung zum Thema angeboten wird.

?Auch wenn das Problem nach wie vor offen ist, hat es im Laufe der vergangenen vierzig Jahre eine Fülle von Teilergebnissen ganz unterschiedlicher Natur gegeben, die auf Techniken aus verschiedenen Teilgebieten der theoretischen Informatik und der diskreten Mathematik beruhen“, so Grohe. Seit den frühen 1980er Jahren stehen bei der theoretischen Untersuchung des Isomorphieproblems gruppentheoretische Methoden im Vordergrund. Ausgangspunkt für Grohes Herangehensweise hingegen sind Techniken der modernen Graphenstrukturtheorie sowie Techniken aus der Logik, von denen bekannt ist, dass sie in engem Zusammenhang mit kombinatorischen Ans?tzen zur L?sung des Isomorphieproblems stehen.
?

WEITERE INFORMATIONEN

Prof. Dr. Martin Grohe ?
Institut für Informatik
Humboldt-Universit?t zu Berlin
Tel: 030 2093-3078
E-Mail: grohe@informatik.hu-berlin.de