Einblick in die Vorbereitung

Beginn

Um einen kleinen Einblick in unsere Übungsaufgaben zur Vorbereitung für die Prüfung zu geben, habe ich mir eine Aufgabe rausgesucht, die ich hier vorstellen möchte. Folgende Aufgabe ist besonders schön, da sie keinen hohen Abstraktionsgrad besitzt, sehr intuitiv ist und den Mehrwert von Algorithmen wiederspiegel.

Hauptteil

Die gewählte Aufgabe kommt aus dem Themengebiet der dynamischen Programmierung und lässt sich den Problemlösungsstrategien zuordnen. Es ist im Prinzip nur eine kleine Spielerei mit einer Folge von Buchstaben aus dem Alphabet.

Für die Aufgabe benötigen wir den Begriff einer Zeichenkette. Eine Zeichenkette ist die Anzahl der Folgen von Buchstaben. Die Zeichenkette Natura hat damit die Länge 6.
Folgende Schreibweise verdeutlicht den Kontext:

= N, = a, = t, = u, = r, = a.

Die Zeichenkette Plastik hat somit die Länge 7. Falls eine Zeichenkette keinen Buchstaben enthält, ist sie leer und wird mit bezeichnet.

Um eine Zeichenkette in eine andere zu überführen sind drei Operationen erlaubt. Man darf einzelne Buchstaben löschen, einfügen und einen Buchstaben durch einen anderen ersetzen.

So kann man beispielsweise Natura durch 8 Operationen in Plastik überführen:

1. N durch P ersetzen: Pature
2. a durch l ersetzen: Pltura
3. t durch a ersetzen: Plaura
4. u löschen: Plara
5. r durch s ersetzen: Plasa
6. a durch t ersetzen: Plast
7. i einfügen: Plasti
8. k einfügen: Plastik

Nun wird noch ein weiterer Begriff eingeführt:
Die obere Prozedur, um Natura in Plastik zu überführen, könnte eventuell auch mit weniger als 8 Operationen durchgeführt werden. Um diese minimale Anzahl an Operationen zu finden, berechnen wir mit der dynamischen Programmierung die Editierdistanz.

Formal ausgedrückt ist die Editierdistanz die minimale Anzahl an Operationen um die Zeichenkette in die Zeichenkette zu überführen.

Hinweis:
Nachfolgend gelte eine Rekursionsgleichung, die nicht hergeleitet oder bewiesen werden soll und an dieser Stelle als korrekt angesehen wird. Um nicht zu tief in formale Überlegungen einzusteigen, sind einige Vorgänge vereinfacht dargestellt.

= 0; = für 1 ; = für 1 ;

Wir berechnen nun in einer folgenden zweidimensionalen Feld die Editierdistanz von Natura in Plastik. Dabei kann man in den Spalten den Index beobachten, der von 0, … , eingetragen wurde. In den Zeilen wurde der Index von 0, … , eingetragen. Also jeweils in der Länge der Zeichenkette. Die Zeichenketten sind zugehörig verzeichnet.

		0	1	2	3	4	5	6	7
			P	l	a	s	t	i	k
0
1	N
2	a
3	t
4	u
5	r
6	a

Nun wird eine Zelle von als Eintrag D[, ] formalisiert und läuft von 1 und 1 .
D[,] wird dabei als eingetragen.
Als Beispiel wäre das Feld = 3, = 4, also D[3,4] anzusehen als D(Nat,Plas).

Nun folgen einige weitere Definitionen für die Einträge:
D[0, 0] = , enthält also leere Zeichenketten.
D[0, ] = , die Zeichenkette Natura ist hierbei als leere Zeichenkette definiert.
D[, 0] = , hierbei ist Plastik als leere Zeichenkette definiert.

Nun können wir endlich das erste Feld bestimmen. Wir beginnen mit dem Feld D[0,0]. Dieses finden wir in unseren Definitionen als und können dieses mit unserer Rekursionsgleichung abgleichen. Das Feld ist definiert als 0. Damit sieht unser erster Eintrag wie folgt aus:

		0	1	2	3	4	5	6	7
			P	l	a	s	t	i	k
0		0
1	N
2	a
3	t
4	u
5	r
6	a

Als nächstes nehmen wir uns die Einträge vor, denen jeweils eine leere Zeichenkette gegenübersteht. Das sind die Felder = für 1 ; = für 1 .
Für diese Felder ist genau der Index definiert. Nun sieht unser Feld wie folgt aus:

		0	1	2	3	4	5	6	7
			P	l	a	s	t	i	k
0		0	1	2	3	4	5	6	7
1	N	1
2	a	2
3	t	3
4	u	4
5	r	5
6	a	6

Nun wird die Sache erst spannend. Als nächstes kommen unsere Fallunterscheidungen. Die Frage ist, was kommt in den Eintrag D[1,1]? Der Eintrag kann als = D(N,P) angesehen werden.

Wir müssen nun das Minimum aus drei Zellen bestimmen. Vereinfacht gesagt steht in der Rekursionsgleichung, dass wir in die Zelle über, links neben und schräg links oben schauen müssen. Links und rechts müssen wir einen Integer aufaddieren. Schräg links oben nur, wenn die jeweiligen Endungen der Zeichenketten ungleich sind.

Wenn wir in das Feld D schauen, ist schräg links oben der minimale Wert. Da N und P unterschiedlich sind, addieren wir eine 1 auf den Wert = 0 + 1.

		0	1	2	3	4	5	6	7
			P	l	a	s	t	i	k
0		0	1	2	3	4	5	6	7
1	N	1	1
2	a	2
3	t	3
4	u	4
5	r	5
6	a	6

Da sich in Natura kein P befindet, kann die komplette Zeile = 1 auf die selbe Weise ausgefüllt werden. Das gleiche gilt für Spalte , da sich in Plastik kein N befindet.

		0	1	2	3	4	5	6	7
			P	l	a	s	t	i	k
0		0	1	2	3	4	5	6	7
1	N	1	1	2	3	4	5	6	7
2	a	2	2
3	t	3	3
4	u	4	4
5	r	5	5
6	a	6	6

Bei Eintrag D[2,3] haben wir den ersten Fall, dass die Endungen gleich sind = d[Na,Pla]. Wir nehmen den Wert von schräg links oben und müssen nichts aufaddieren. Damit ergibt sich der Wert 2.

		0	1	2	3	4	5	6	7
			P	l	a	s	t	i	k
0		0	1	2	3	4	5	6	7
1	N	1	1	2	3	4	5	6	7
2	a	2	2	2	2
3	t	3	3	3
4	u	4	4	4
5	r	5	5	5
6	a	6	6	6

Die restlichen Werte werden nach dem selben Vorgehen anhand der Rekursionsgleichung durchgeführt. So erhält man auf einfachem Wege folgendes ausgefülltes Feld D.

		0	1	2	3	4	5	6	7
			P	l	a	s	t	i	k
0		0	1	2	3	4	5	6	7
1	N	1	1	2	3	4	5	6	7
2	a	2	2	2	2	3	4	5	6
3	t	3	3	3	3	3	3	4	5
4	u	4	4	4	4	4	4	4	5
5	r	5	5	5	5	5	5	5	5
6	a	6	6	6	6	6	6	6	6

Das optimale Ergebnis sind demnach 6 Operationen (unten rechts abzulesen).

Fazit

Das Verfahren kommt aus der Gentechnik. Man kann damit zwei Gensequenzen vergleichen und prüfen wie ähnlich sie sich sind. Zwei Dinge sind sehr ähnlich, wenn man sie durch wenige Veränderungen aufeinander überführen kann. Die dynamische Programmierung ist im wesentlichen das Ausfüllen solcher Tabellen. Das ganze Verfahren ist sehr einfach, wenn man die Rekursionsgleichung hat.

Im Falle, dass eine derartige Aufgabe in der Klausur gestellt wird, bekommen wir die Rekursionsgleichung gegeben.
Das war ein kleines Beispiel einer unserer Übungsaufgaben, in einem Tag findet die Klausur statt. Ich fühle mich inzwischen ganz gut vorbereitet!