Trace-Tabelle

Eine Trace-Tabelle, deutsch auch Ablaufverfolgungstabelle ist ein Werkzeug, um den Ablauf von Algorithmen nachzuverfolgen und zu protokollieren. In einer Trace-Tabelle wird für jeden Schritt im Ablauf des Algorithmus die jeweils aktuelle Belegung aller Variablen festgehalten. So kann zum Beispiel für fehlerhafte Algorithmen nachverfolgt werden, an welcher Stelle der Ablauf schiefgeht. Trace-Tabellen sind darum wertvolle Werkzeuge für das Debugging.

Beispiel

input n
i = 1
fak = 0
while i <= n do
    fak = fak · i
    i = i + 1
endwhile
print fak

Ein Algorithmus, um Fakultäten zu berechnen

Dieser Pseudocode zeigt einen Algorithmus, der die Fakultät einer eingegebenen Zahl berechnen soll. Die Fakultät $n!$ ist das Produkt $1\cdot 2\cdot 3\cdot \dots \cdot n$.

Der Algorithmus arbeitet folgendermaßen: In Zeile 1 wird n eingelesen, in den Zeilen 2 und 3 werden die Laufvariable i und der Akkumulator fak initialisiert, in der bedingten Wiederholung der Zeilen 4 bis 7 wird i so lange erhöht und auf fak aufmultipliziert, bis n erreicht ist. Danach wird das Ergebnis ausgegeben.

So sollte es sein.

Tatsächlich ist das Ergebnis des Algorithmus jedes Mal 0, egal, was man eingibt. Mit einer Trace-Tabelle können wir nun herausfinden, was wirklich passiert. Die folgende Tabelle zeigt den Ablauf für die Eingabe $n=4$

Trace-Tabelle

Schritt	n	i	fak	Kommentar
1	4			n wird eingegeben
2		1		i wird initialisiert
3			0	fak wird initialisiert
5			0	fak wird auf ${\texttt {fak}}\cdot {\texttt {i}}=0\cdot 1=0$ gesetzt
6		2		i wird erhöht
5			0	fak wird auf ${\texttt {fak}}\cdot {\texttt {i}}=0\cdot 2=0$ gesetzt
6		3		i wird erhöht
5			0	fak wird auf ${\texttt {fak}}\cdot {\texttt {i}}=0\cdot 3=0$ gesetzt
6		4		i wird erhöht
5			0	fak wird auf ${\texttt {fak}}\cdot {\texttt {i}}=0\cdot 4=0$ gesetzt
6		5		i wird erhöht. Jetzt ist die Bedingung der Wiederholung nicht mehr erfüllt, die Wiederholung bricht ab und fak wird ausgegeben. Damit endet der Algorithmus.

Aus dieser Trace-Tabelle kann man das Problem schon ersehen: Dadurch, dass fak mit 0 initialisiert wurde und immer wieder mit 0 multipliziert wird, kann immer nur 0 als Ergebnis herauskommen.

Weblinks

• "Trace-Tabellen" auf inf-schule.de 🇩🇪