SPP 1307:  Algorithm Engineering

• Fachliche Zuordnung: Informatik, System- und Elektrotechnik
• Förderung: Förderung von 2007 bis 2016
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 29058954

Effiziente Algorithmen und Datenstrukturen sind Grundvoraussetzung für anspruchsvolle Computeranwendungen, die mit großen Datenmengen auf immer komplexerer Hardware umgehen. Zum Beispiel haben Algorithmen für Internetsuchmaschinen die Art verändert, wie wir mit Wissen und Information umgehen. Ausgefeilte Algorithmen zur Sequenzierung des menschlichen Genoms haben diesen entscheidenden Durchbruch der Biowissenschaft um mehrere Jahre beschleunigt. Algorithmik - die systematische Entwicklung effizienter Algorithmen - ist deshalb entscheidend für die Umsetzung technologischer Möglichkeiten in Anwendungen mit großer Bedeutung für Technik, Wirtschaft, Wissenschaft und unser tägliches Leben.
Die Lösung der anstehenden Probleme wird aber behindert durch eine über Jahrzehnte gewachsene Kluft zwischen dem Wissensstand der Algorithmentheorie und der praktischen Anwendung von Algorithmen. Das Algorithm Engineering tritt an, diese Kluft zwischen Theorie und Praxis zu überbrücken. Schlüssel dazu ist eine breitere Methodik, die den traditionellen Dreiklang der Algorithmentheorie von Entwurf, Analyse und beweisbaren Leistungsgarantien deutlich erweitert. Kern des Algorithm Engineering ist ein Kreislauf aus Entwurf, Analyse, Implementierung und experimenteller Bewertung von Algorithmen. Hinzu kommen vielfältige Querbezüge zu konkreten Anwendungen, Arbeit an wieder verwendbaren Bibliotheken von Algorithmenimplementierungen und realistische Modelle für moderne Hardware und wichtige algorithmische Fragestellungen.
Das Schwerpunktprogramm soll zu einem nachhaltigen Innovationsschub bei der Anwendung von Algorithmen führen, indem es das Algorithm Engineering schneller vorantreibt, weiter entwickelt, breiter etabliert und stärker vernetzt. Wir sehen eine echte Chance, dass das Algorithm Engineering zu einem weltweit sichtbaren Markenzeichen der deutschen Informatik wird, das auch die Wettbewerbsfähigkeit der deutschen Wirtschaft stärkt. Langfristiges Ziel ist eine nachhaltige Überbrückung von Lücken zwischen Theorie und Praxis.

• DFG-Verfahren: Schwerpunktprogramme
• Internationaler Bezug: Schweiz

Projekte

• Algorithm Engineering für dynamische Graphenoptimierungsprobleme in konkreten Anwendungen (Antragsteller Müller-Hannemann, Matthias )
• Algorithm Engineering für MONET und verwandte Abdeckungsprobleme (Antragsteller Mundhenk, Martin )
• Algorithm Engineering für Netzwerkprobleme (Antragstellerin Albers, Susanne )
• Algorithm Engineering für Probleme der Computergrafik (Antragsteller Meyer auf der Heide, Friedhelm )
• Algorithm Engineering für Real-Time Scheduling und Routing (Antragsteller Eisenbrand, Friedrich ;  Skutella, Martin )
• Algorithm Engineering zur Methodenentwicklung im randomisierten Runden (Antragsteller Doerr, Benjamin )
• Algorithmen für komplexe Schedulingprobleme (Antragsteller Möhring, Rolf H. )
• Algorithms for Data Stream Processing (Antragsteller Kliemann, Lasse )
• Algorithms for Modern Hardware: Flash Memory (Antragsteller Meyer, Ulrich )
• Anwendungsorientierte Indexstrukturen für Approximate Pattern Matching (Antragsteller Mayr, Ernst W. )
• Clusterung statischer und zeitbehafteter Graphen (Antragstellerin Wagner, Dorothea )
• Design, Analyse, Implementierung und experimentelle Auswertung von Algorithmen zum Genomvergleich mit der SeqAn Softwarebibliothek (Antragsteller Reinert, Knut )
• Effiziente Indexdatenstrukturen und Sprachverarbeitung für semantische Volltextsuche (Antragstellerin Bast, Hannah )
• Effiziente Suche in sehr großen Textmengen, Datenbanken und Ontologien (Antragstellerin Bast, Hannah )
• Einfache und schnelle Implementierung von exakten Optimierungsalgorithmen mit SCIL (Antragsteller Althaus, Ernst ;  Buchheim, Christoph )
• Engineering efficient algorithms for the basic algorithmic toolbox with emphasis on algorithm libraries, memory hierarchies and parallelism (Antragsteller Sanders, Peter )
• Engineering von Matching- und Überdeckungsalgorithmen in großen Graphen und Hypergraphen (Antragsteller Srivastav, Anand )
• Entwicklung einer praxisnahen Theorie für Clusteringalgorithmen durch datengetriebene Modellierung und Analyse (Antragsteller Blömer, Johannes ;  Sohler, Christian )
• Entwurf und Analyse anwendungsbezogener geometrischer Algorithmen (Antragsteller Alt, Helmut )
• Exakte Ganzzahlige Optimierung (Antragsteller Grötschel, Martin )
• Externe zielgerichtete Suche in impliziten Graphen (Antragsteller Steffen, Bernhard )
• Generische Dekompositionsalgorithmen für ganzzahlige Programme (Antragsteller Lübbecke, Marco )
• Gestörte Diffusion für die Partitionierung und Clusteranalyse von Graphen (Antragsteller Monien, Burkhard )
• Koordination und Infrastruktur, Präsentation der Ergebnisse des SPP auf internationalen Workshops und Tagungen (Antragsteller Sanders, Peter )
• Kunst! - Exakte Algorithmen für Kunstgalerieprobleme (Antragsteller Kröller, Alexander )
• Planarisierungsverfahren im Automatischen Zeichnen von Graphen (Antragstellerin Mutzel, Petra )
• RoboRithmics: Algorithmische und praktische Methoden zur Steuerung eines autonomen Explorationsroboters (Antragsteller Fekete, Sándor )
• Robuste Algorithmen für diskrete Optimierungsprobleme (Antragstellerin Schöbel, Anita )
• Schnellere Algorithmen für harte Probleme wie Subset Sum, Syndromdekodierung in linearen Codes und dem Kürzesten Vektor Problem mit zahlreichen Anwendungen in der Komplexitätstheorie und der Kryptographie (Antragsteller May, Alexander )
• Stochastische Lokale Suche bei SAT-Solvern (Antragsteller Schöning, Uwe )
• Strukturbasiertes Algorithm Engineering für SAT-Solving (Antragsteller Kaufmann, Ph.D., Michael )

• Sprecher: Professor Dr. Peter Sanders