Was ist Algorithmik?
Algorithmen sind der Kernbaustein jeder Software. Egal, ob es zum Beispiel um mathematische Berechnungen geht, um die Ausgabe von Auskünften, um das Auffinden, Aufbereiten und Analysieren von Geschäftsdaten, die Erkennung von geschriebener oder gesprochener Sprache oder auch um die Kontrolle und Steuerung elektrischer oder mechanischer Geräte: Wann immer die Software auf eine Eingabe (durch einen Benutzer oder von Sensoren) reagiert, ist die Reaktion durch einen Algorithmus berechnet worden.
Algorithmen sind im Grunde Kochrezepte, die dem Computer sagen, was für Operationen er durchführen soll, um auf eine Eingabe die richtige Antwort zu geben. Die Eingabe kann zum Beispiel auch Information über das menschliche Erbgut sein, und die erwünschte Ausgabe ist die Entschlüsselung dieses Erbguts. Oder die Eingabe besteht aus Wetterdaten des heutigen Tages, und die erwünschte Ausgabe ist eine Prognose für das morgige Wetter. Auch dies sind zwei Beispiele für algorithmische Problemstellungen.
Ein Algorithmus soll nicht nur richtig reagieren, sondern auch möglichst schnell und dafür auch nicht allzu viel Speicherplatz im Computer belegen. Es gibt also gute Algorithmen (nämlich schnelle und speicherplatzsparende) und weniger gute. Oft ist die algorithmische Problemstellung auch so komplex, dass es überhaupt keinen guten Algorithmus geben kann. Dann gibt man sich notgedrungen mit "fast korrekten" Algorithmen zufrieden, und der Fehler, den der Algorithmus begeht, ist ein drittes Kriterium dafür, wie gut oder schlecht er ist.
Das Kernproblem der Algorithmik ist, zu jeder Problemstellung einen möglichst guten Algorithmus zu finden. Somit erfüllt die Algorithmik eine Querschnittsfunktion innerhalb der Informatik.
Als Fachdisziplin ist die Algorithmik ein Kind der Theoretischen Informatik. Die Theoretische Informatik versucht, grundlegende Fragen der Informatik mit mathematischen Methoden anzugehen. In der Algorithmik spiegelt sich das darin wider, dass man traditionell versucht, die Güte von Algorithmen mathematisch zu beschreiben und die Korrektheit dieser Beschreibung wiederum mathematisch zu beweisen.
Relativ gut im Griff hat man den "schlimmstmöglichen Fall", das heißt, man kann recht gut obere Schranken berechnen, wie schlecht die Güte des Algorithmus sein kann, egal wie die Eingabedaten aussehen. In der Praxis zeigt sich allerdings immer wieder, dass solche Schranken viel zu schwach sind, vor allem, weil die schlimmstmöglichen denkbaren Eingabedaten oft künstlich konstruiert sind und in der Realität mit Sicherheit gar nicht auftreten würden.
Alternativ hat man versucht, das Verhalten von Algorithmen im "durchschnittlichen Fall" zu berechnen. Aber dies scheitert einerseits an unüberwindlichen mathematischen Schwierigkeiten, andererseits meist schon an der Unmöglichkeit, den durchschnittlichen Fall überhaupt mathematisch klar zu definieren.
Man kommt also mit beweisbarer Mathematik allein nicht weiter bei der Entwicklung besserer Algorithmen. Im Grunde muss
man die Problemstellung soweit verfeinern, dass die Eingabedaten aus der realen Anwendung immer noch enthalten sind, die (künstlichen) schlimmstmöglichen Daten aber ausgeschlossen werden. Oft wird dann die mathematische Behandlung sehr einfach, das heißt, die wirkliche Herausforderung ist jetzt, die "richtige" Verfeinerung zu finden.
Die Trennlinie zwischen Realweltdaten und schlimmstmöglichen Daten ist zwar meist mit Händen zu greifen, entzieht sich aber
oft der Formalisierung. Eine Idee ist, eine "weiche" Trennlinie zu ziehen, indem man bestimmte Kenngrößen für Eingabedaten identifiziert, die zwei Eigenschaften haben müssen: Erstens sind die Werte dieser Kenngrößen für Realweltdaten aller Erfahrung nach typischerweise klein; zweitens lassen sich Algorithmen finden, die auf Eingabedaten mit kleinen Werten dieser Kenngrößen sehr akkurat und effizient sind.
Ein simples Alltagsbeispiel mag die Grundidee verdeutlichen: Wenn die Daten aller Studierenden einer Universität nach Matrikelnummern sortiert sind, lässt sich der Datensatz, der zu einer bestimmten Matrikelnummer gehört, sehr schnell systematisch einkreisen und auffinden. Sind die Daten hingegen nicht nach Matrikelnummern sortiert, muss man alle Datensätze der Reihe nach durchgehen, was um Größenordnungen länger dauert. Der hier interessierende Fall tritt ein, wenn die Datensätze "beinahe" nach der Matrikelnummer sortiert sind, zum Beispiel wenn sie nach Einschreibedatum sortiert sind. Die "Einkreisealgorithmen" für den Fall einer echten Sortierung kann man auf einen solchen Fall anpassen, und diese
angepassten Algorithmen sind um so effizienter, je stärker die Datensätze in sich nach Matrikelnummern sortiert sind. Die Distanz zur vollständigen Sortierung ist also die entscheidende Kenngröße.
Im Fachgebiet Algorithmik an der TU Darmstadt wird die systematische Betrachtung solcher Kenngrößen momentan zum Schwerpunkt der Grundlagenforschung ausgebaut. Unsere Arbeitsgruppe hat im Laufe der Jahre umfangreiche Erfahrungen in Industrieprojekten aus verschiedenen Anwendungsgebieten der Informatik gesammelt. Zum Zeitpunkt der Abfassung dieses Texts arbeiten wir gerade an drei Projekten, in denen bessere Algorithmen als bisher bekannt entwickelt werden sollen: für die Berechnung schneller, preiswerter und bequemer Bahnverbindungen; für die optimale Auslastung von Stahlwerken; für den optimalen Durchsatz bei der Bestückung von PC-Platinen in automatischen Fertigungsstraßen.
Der Brückenschlag zwischen Theorie und Praxis ist das letztendliche Ziel unserer Aktivitäten in der Forschung und auch in der Lehre.