Türme von Hanoi:
Etwas Allgemeines zu den Türmen von Hanoi:
Die obenstehenden Zeichnung verdeutlicht das rekursive
Lösungsschema für das Problem der Türme von Hanoi
mit drei Scheiben.
Die drei Zahlen in den Kreisen geben an, auf welchem Stab welche Scheibe
liegt. Die Stäbe sind von links nach rechts durchnumeriert. Die
erste Zahl gibt den Stab an, auf dem die kleinste Scheibe liegt, die
zweite Zahl den Stab, auf dem die mittlere Scheibe liegt und die dritte
den Stab, auf dem die größte Scheibe liegt.
Programm:
Folgendes Prolog-Programm wurde mit dem Messtool PMT analysiert:
/* prolog tutorial 2.3 Towers of Hanoi puzzle */
move(1,X,Y,_) :-
write('Move top disk from '),
write(X),
write(' to '),
write(Y),
nl.
move(N,X,Y,Z) :-
N>1,
M is N-1,
move(M,X,Z,Y),
move(1,X,Y,_),
move(M,Z,Y,X).
Callgraph:
Das Programm liefert folgenden Call-Graphen:
Die Schlinge am einzigen Knoten des Graphen (move/4) kennzeichnet
den rekursiven Aufbau des Prädikats move.
Messungen:
Programm:
Folgende Kennzahlen wurden durch das PMT-Programm ermittelt:
Anzahl der Programmzeilen (brutto) |
17 |
Anzahl der Programmzeilen (netto) |
12 |
Anzahl der Kommentare |
1 |
Kommentar-Code-Verhältnis |
0.08333 |
Anzahl Prozeduren |
1 |
Anzahl Klauseln |
2 |
Anzahl Kommandos |
0 |
Anzahl Ziele |
0
|
Anzahl direkter rekursiver Aufrufe |
3 |
Kantenanzahl des Call-Graphen |
1 |
Knotenanzahl des Call-Graphen |
1 |
Verbindungsdichte |
1 |
Breite des Call-Graphen |
1 |
Höhe des Call-Graphen |
1 |
hierarchische Komplexität |
1 |
strukturelle Komplexität |
3 |
Fenton's Impurity-Metrik |
0 |
Yin-Winchester-Metrik
|
0
|
Prozeduren:
Das PMT-Programm ermittelte folgende Bewertung der Prozeduren:
Klauseln:
Die durch das PMT-Programm ermittelte Bewertung der Klauseln:
Erfahrungswerte:
Wert: |
Prozeduren: |
Klauseln: |
DGMc: |
28.996 |
8.589 |
DGMs: |
13.345 |
4.131 |
Ausgangsgrad: |
1.000 |
|
Eingangsgrad: |
1.000 |
|
Teilziele: |
8.193 |
3.607 |
Anzahl direkter Rekursionen: |
2.716 |
0.065 |
Anzahl Cuts: |
0.000 |
0.000 |
Die zulässige bzw. kritische Abweichung war jeweils
0.000.
Auswertung:
Programm:
Das Programm hat brutto 17 Zeilen, wovon netto noch 12
Zeilen gezählt werden. Da das Program nur aus zwei Regeln und einem
Kommentar besteht, kann man daraus schließen, dass der Autor versucht
hat, die Lesbarkeit des Programms zu erhöhen, indem er jeweils
einen Teilausdruck in eine eigene Zeile schreibt. Das Verhältnis
Kommentare zu Programmzeilen (0.08333) ist daher etwas irreführend.
Andererseits dient der Kommentar lediglich als eine Versionsinformation
und trägt nicht zum weiteren Verständnis des für sich
schon leichtverständlichen Codes bei.
Die Anzahl direkt rekursiver Aufrufe und die strukturelle
Komplexität haben den Zahlenwert 3; die Anzahlen für Callgraph-Ecken,
Callgraph-Knoten, Verbindungsdichte usw. haben alle den Wert eins und
die Anzahl der Ziele bzw. die Anzahl der Kommandos ist null.
Lediglich bei der Berechnung der Metriken scheint ein
Fehler aufgetreten zu sein. Die Yin-Winchester-Metrik (definiert als
kanten-knoten+1) sollte statt null den Wert (1 - 1 + 1 = 1) und die
Fenton's Impurity-Metrik (definiert als 2*(kantenzahl-knotenzahl+1)/(n-1)(n-2))
sollte auch einen anderen Wert als null liefern.
Prozeduren:
Der Eingangsgrad bzw. der Ausgangsgrad beträgt jeweils
eins; die Anzahl von rufenden, gerufenen Calls bzw. direkt rekursiver
Calls ergibt drei. Es wird kein Cut-Operator benutzt, was man an Cut
= 0 erkennen kann.
Das Programm besteht aus zwei Klauseln die gleichzeitig
auch Regeln sind (NoC=NoR=2). Die Anzahl der Teilziele beträgt
neun.
Die voreingestellten Erfahrungswerte entsprechen in etwa
den gemessenen Werten.
Klauseln:
Bei der Auswertung der Klausel-Messung erkennt man leicht,
dass beide Klauseln Regeln sind. Die erste Regel (move/4/1) hat vier
Teilziele, keine Calls und keinen Cut-Operator. Die zweite Regel (move/4/2)
besitzt fünf Teilziele, drei Aufrufe nutzerdefinierter Prozeduren,
drei direkt rekursive Calls und auch keinen Cut-Operator.
Auch hier entsprechen die voreingestellten Erfahrungswerte
in etwa den gemessenen Werten.
Bemerkungen:
Das PMT-Programm scheint als 16bit-Windows-Anwendung Probleme
bei Rechnern mit viel Arbeitsspeicher zu haben. Bei dem Versuch eine
Prolog-Datei auf solch einem Rechner zu öffnen, stürzt das
Programm regelmäßig ab. Auf älteren Rechnern treten
hingegen keine Probleme auf. Die Bedienung des Programmes ist weitgehend
selbsterklärend.
Da das analysierte Programm relativ kurz und einfach ist, sind die
Ergebnisse übersichtlich und leicht verständlich.
Legende:
NG: |
Anzahl der Teilziele |
NC: |
Anzahl der Aufrufe nutzerdefinierter Prozeduren |
ID: |
Eingangsgrad (Anzahl der rufenden Komponenten einer Prozedur) |
OD: |
Ausgangsgrad (Anzahl der gerufenden Komponenten aus einer Prozedur) |
IC: |
Anzahl der rufenden Calls insgesamt |
OC: |
Anzahl der gerufenen Calls insgesamt |
NR: |
Anzahl direkt rekursiver Calls |
DGMc: |
Datengraphkomplexität |
DGMs: |
Datengraphhöhe |
Cut: |
Anzahl der Cuts |
NoC: |
Anzahl der Klauseln |
NoR: |
Anzahl der Regeln |
Typ: |
Fakt (F) oder Regel (R) |
|