Hasso-Plattner-Institut
  
Hasso-Plattner-Institut
Prof. Dr. Tobias Friedrich
  
 

Formalisierungen

Autor: Timo Kötzing

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.

  1. Grundlagen von Formalisierungen;
  2. Spielraum;
  3. 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) zusammenhangende 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.

  • Zahlen (als primitive Datentypen): \(\mathbb{N,Z,Q,R,C}\).
  • 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.
  • Punktwolken (z. B. zur Formalisierung von Punkten im euklidischen Raum); \(\mathbb{R}^d\), wobei \(d\) die Dimension ist.
  • Funktionen; \(f\colon A \rightarrow B\).

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.

Überblick

Was haben wir gelernt?

  1. Mit Formalisierungungen übersetzen wir sprachlich gegebene Aufgaben in formale Spezifikationen.
  2. Dabei gibt es einen Interpretationsspielraum.
  3. Die Formalisierung steht auch im Wechselspiel mit anderen Abschnitten des Algorithmendesigns.