Hier besprechen wir den ersten Schritt zu jedem Algorithmendesign: die Formalisierung der Aufgabenstellung aus einem sprachlich gegebenen Problem.
Dabei gehen wir in den folgenden Schritten vor.
Grundlagen von Formalisierungen;
Spielraum;
Prozess.
Was beinhaltet eine Formalisierung?
Eine Formalisierung fängt immer mit einem sprachlich gegebenen Problem an. Schauen wir uns zum Beispiel die folgende komplexe Beschreibung aus der Bioinformatik an.
Gegeben ist das Protein-Protein-Interaction-Netzwerk (PPI-Netzwerk), welches für je zwei Proteine angibt, ob eine Interaktion zwischen diesen beiden Proteinen besteht. Zu jedem Protein ist eine Zahl \(b\) bekannt, welche die durschnittliche Ausprägung des Proteins im menschlichen Körper beschreibt. Wir suchen nun einen sogenannten Pathway, eine (im PPI-Netzwerk) zusammenhängende Menge von Proteinen, die alle besonders stark ausgeprägt sind. Konkret wollen wir das Produkt aus der Anzahl der Proteine im Pathway und der Ausprägung des minimal ausgeprägten Proteins im Pathway maximieren.
Diese erst einmal schwer verdauliche Beschreibung soll nun formalisiert werden, also überführt werden in eine formale Algorithmenspezifikation. Aber wie geht man so eine Formalisierung an?
Wir halten fest: Eine sprachlich gegebene Aufgabe muss interpretiert werden; damit gelangen wir zu einer formalen Spezifikation für einen zu findenden Algorithmus. Zentral in jeder Formalisierung sind dabei die folgenden vier Punkte.
Eingabe;
Ausgabe;
Korrektheitsbedingung;
Interpretation.
Die ersten drei Punkte ergeben die Spezifikation des Algorithmus; der vierte Punkt stellt die Verbindung zur gegebenen, sprachlichen Formulierung her. Wir nutzen die folgenden Datentypen zur Spezifikation von Eingabe und Ausgabe.
Wahrheitswerte (Booleans): \(\{1,0\}\) bzw. in Worten \(\{\)True, False\(\}\).
Arrays (zur Formalisierung von angeordneten Objekten); immer gebunden an einen Typ von Elementen.
Mengen (zur Formalisierung von nicht-angeordneten Objekten); immer gebunden an einen Typ von Elementen.
Strings (z. B. zur Formalisierung von Wörtern, Sätzen oder DNA-Sequenzen); z. B. \(\{0,1\}^*, \{A,T,C,G\}^*\).
Graphen (z. B. zur Formalisierung von Netzen); \(G = (V,E)\), wobei \(V\) die Menge der Knoten und \(E\) die Menge der Kanten ist. Graphen werden in TI2 richtig eingeführt.
Punktwolken (z. B. zur Formalisierung von Punkten im euklidischen Raum); \(\mathbb{R}^d\), wobei \(d\) die Dimension ist.
Funktionen; \(f\colon A \rightarrow B\). Ihr solltet euch hier überlegen, wie sich eine gegebene Funktion als Datenstruktur speichern lässt und was die Ausführungszeit dadurch ist. Zum Beispiel könnte eine Funktion, die als Eingabe natürliche Zahlen zwischen \(0\) und \(n\) akzeptiert, als Array der Länge \(n+1\) gespeichert werden.
Beispiel
Wir kommen jetzt auf unser Eingangsbeispiel mit den PPI-Netzwerken zurück und geben eine Interpretation.
Spielraum
Wir halten fest: Interpretationen sind nicht eindeutig; eine gute Formalisierung bietet Alternativen an und geht auf deren Plausibilität ein.
Prozess des Algorithmendesigns
Wir halten fest: Das folgende Diagramm stellt den Prozess des Algorithmendesigns dar.
Was haben wir gelernt?
Mit Formalisierungungen übersetzen wir sprachlich gegebene Aufgaben in formale Spezifikationen.
Dabei gibt es einen Interpretationsspielraum.
Die Formalisierung steht auch im Wechselspiel mit anderen Abschnitten des Algorithmendesigns.
Algorithm Engineering
Our research focus is on theoretical computer science and algorithm engineering. We are equally interested in the mathematical foundations of algorithms and developing efficient algorithms in practice. A special focus is on random structures and methods.
