Untersuchung des Berechnungsaufwands bei Antwortmengenprogrammierung
--------------------------------------------------------------------

Diese Datei enthält Informationen die zur Nutzung der Daten auf dieser DVD nützlich sind.


Benutzerhinweise
----------------

Alle Daten auf dieser DVD, bis auf die im Verzeichnis "Texte" und seinen Unterverzeichnissen, unterliegen der GNU GENERAL PUBLIC LICENSE Version 2, Juni 1991. Näheres zu GNU GENERAL PUBLIC LICENSE im Verzeichnis "gpl". Die Rechte der Daten im Verzeichnis "Texte", entsprechen den Rechten so wie sie von den Autoren der einzelnen Dokumente vergeben werden.

Die Dateien "diplom_main.ps" und "diplom_main.pdf" im DVD Stammverzeichnis enthalten den Diplomtext.


Verzeichnisse
-------------

Texte: Das Verzeichnis "Texte" enthält untergliedert nach Bereichen, Dokumente die für diese Arbeit relevant sind. Im Unterverzeichnis "Sonstiges" sind Texte zu finden, die nicht aus dem KI-Bereich kommen.

gpl: Dieses Verzeichnis enthält die GNU GENERAL PUBLIC LICENSE in verschiednen Textformversionen.

BMTool: Dieses Verzeichnis enthält die Dateien zu dem BMTool Tool von Wolfgang Faber. BMTool dient zum Abspeichern und Auswerten von Daten, die von Smodels oder ähnlichen Programmen ausgegeben werden.

diplomtext: Dieses Verzeichnis enthält den Quelltext zur Dokumentation für die vorliegende Arbeit.

graphen: Enthält einige Diagramme in Schönform. Es diente als Recurce für die Dokumentation.


Folgende Verzeichnisse sind Testreihenverzeichnisse von Testreihen die näher in der Dokumentation beschrieben sind: cases; cases1; casesAll (wie cases nur wurde die richtige Anzahl der Antwortmengen abgespeichert); casesN; casesMix; casesCon; casesConR; graph1

Daneben gibt es noch weitere Testreihenverzeichnisse auf die nicht weiter eingegangen wurde:
casesMixNLA: Wie caseMix jedoch wurde bei smodels der lookahead ausgeschaltet. Die Daten sind wenig aussagekräftig, da keine Zeit war, aussagekräftige Bereiche zu erreichen.

casesNN1: Wie die Testreihe cases1 nur wird der Nomore++ 1.2 Solver verwendet.

racingR: Ist eine Testreihe für das racing robots Problem. Näheres dazu in der Datei "racingR.ps", die sich in diesem Verzeichnis befindet. In dieser Testreihe konnten nicht genügend Daten erhoben werden.

smod1Point: Dieses Verzeichnis enthält einige Unterverzeichnisse für die Verschiedenen Testreihen, für die in den Unterverzeichnissen für einen Testreihenpunkt mehrere Probleme generiert und dann, nur für diese Testpunkte, ausgewertet wurden. In ihm befinden sich also Untersuchungen für einzelne Testreihenpunkte.



Daten in den Testreihenverzeichnissen
-------------------------------------

Dateien:

Im nachfolgenden sind die Dateien, die in den Testreihenstammverzeichnissen zu finden sind, kurz beschrieben.
Das "*" Zeichen steht dabei für ein Namenszusatz der unterschiedliche Versionen der Datei voneinander abgrenzt, z.B. den Testreihengenerator für Smodels ("generator.cpp") von dem für Nomore++ ("generatorN.cpp").

generator*.cpp: Diese Datei enthält den Generator für die Testreihe. Namenszusätze sind: "Fak" für konstanten R/A Faktor; "A" für alle; "M" für gemischte Körperlänge; "C" für gemischte Körperlänge mit verbundenen Programmen; "N" für Nomore++ 
Die Generatordatei für die Testreihe graph1 heißt graph.cpp und für die Testreihe racing robots "genRR.cpp".
mersenne.cpp mersenne.h: Diese Dateien beinhalten eine Zufallsgenerator der für den Generator benötigt wird.

bereiche.txt: In dieser Datei sind die jeweiligen Bereiche angegeben für die die Testreihe erhoben wurde.

spoint*.txt: Hier werden die Parameter für den nächsten Starttestreihenpunkt gespeichert, bei ihm wird die Testreihen bei einem Neustart des Generators wieder aufgenommen. Die Werte werden in der Form: "Literale;Regeln;Atome;" gespeichert oder bei dem Namenszusatz "f" "Litaerale;Faktor;Atome".

todo*.cpp todo*.txt: Mit der Datei "todo*.cpp" wird die Datei "todo*.txt" generiert. Diese enthält eine Liste von Parametern für die Testpunkte der Testreihe, welche noch generiert werden sollen. Für jeden Testpunkt gibt es eine Zeile der Form: "Literale;Regeln;Atome;" abgeschlossen wird die Datei mit der Zeile "0.". 
Es wird entweder die Methode für "spoint*.txt" oder "todo*.txt" zum Durchlaufen der Testpunkte verwendet. Wenn "todo*.txt" verwendet wird, fängt der Generator bei dem Testpunkt der ersten Zeile in ihr an. Der Generator löscht keine Zeilen aus der "todo*.txt" Datei.

Der Generator kann mit "strg + c" jederzeit abgebrochen werden. Dann sollte eine eventuelle Testpunktergebnisdatei im Verzeichnis "ergebnisse" die unvollständig ist (die Datei des letzten generierten Testpunktes kann unvollständig sein) gelöscht werden. Wenn die Datei "todo*.txt" verwendet wird, sollten manuell die Einträge gelöscht werden, von denen die Testpunkte nicht mehr generiert werden sollen (weil dies schon geschehen ist).

evalueAll*.cpp: Dieses Programm dient zum Auswerten der Testreihe. Dabei werden von den vorhandenen Daten Untertestreihen gebildet und für diese Tabellen und Diagramme in einem eigenen Unterverzeichnissen im Verzeichnis "tabellen" erzeugt.
Für dreidimensionalen Diagrammen werden nur großflächig erhobene Bereiche benutzt, allerdings können auch in diesem Bereiche ohne Daten vorhanden sein, so das solche Diagramme Teilweise irreführend sein können.
evalueAllIO*.cpp: Ist eine Hilfsdatei zu "evalueAll*.cpp". In ihr sind die Methoden zur Ein- und Ausgabe der Daten, für die Auswertung, zu finden.

info.txt: Enthält einige allgemeine Informationen. 


Verzeichnisse:

ergebnisse: In diesem Verzeichnis sind die Daten der erhobenen Testreihe des Testreihenverzeichnisses zu finden, näheres dazu im Abschnitt "Ergebnisformat".

tabellen: Hier sind die Auswertungen der Untertestreihen, meist in eigenen Unterverzeichnissen, zu finden, näheres dazu im Abschnitt "Diagramme". Diese Verzeichniss kann auch in komprimierter Form als zip-File vorliegen.


Allgemeine Abkürzungen
----------------------

A = Atome (atoms)
C;R = Regeln (rules)
L = (durchschnittliche) Körperliterale ((average) literals per body), wenn durchschnittlichen Literale angegeben sind (z.B. bei casesMix), sind sie mit 10 multipliziert, L12 bedeutet also durchschnittlich 1.2 Literale pro Körper
V = Knoten (vertices) oder dass der zugehörige Wert variabel ist
E = Kanten (edges)
F = Faktor mit dem etwas multipliziert wurde
D3 = dreidimensional

Die Kurznotation die meist verwendet wird, besteht jeweils aus der Abkürzung des entsprechenden Parameters gefolgt von dem Wert den er einnimmt oder einem "V" wenn er variabel ist, "A10RV" bedeutet bei 10 Atomen mit variabler Regelzahl.


Ergebnisformat
---------------

In den Testreihenverzeichnissen befindet sich jeweils ein Unterverzeichnis "ergebnisse", in diesem befinden sich die Ergebnisse der einzelnen Testläufe. Jeder Testpunkt besitzt dabei eine eigene "*.txt" Datei, in der meist (bis auf bei smod1Point) die Daten für 1000 Problem gespeichert sind. Im Dateinamen sind die Generierungsparameter gespeichert. Der Name der Testpunktdateien beginnen alle mit "atw" worauf die Generierungsparameter in der Kurznotation folgen.

Die Testpunktdatei beginnt immer mit einem Einleitungsteil, in der zuerst der verwendete Solver mit Versionsnummer steht und dann kommt der Tabellenanfang, danach kommt Zeilenweise die Testparameter (Problemparameter und Testergebnisse) für die einzelnen Probleme bzw. Programme, beendet wird die Datei mit dem Tabellenabschluss (der Form:"----+-----------+").

Die Testparameter für ein Problem (in einer Zeile) sind bei den Testreihen in der folgenden Reihenfolge gespeichert, dabei sind die Zeichen "|" und ";" die Trennzeichen für die Parameter in der Datei.
Bei der Anzahl der Antwortmenge steht "NV", wenn keine Antwortmengen gefunden wurden.

Bei den Testreihen cases haben die Testparameter für ein Problem die Form:
Problemname | Berechnungszeit; choice points; wrong choices; Anzahl der Antwortmenge; truth assignments; Anzahl der Atome; Anzahl der Regeln |

Bei den Testreihen cases ist die Anzahl der Atome und Regeln nicht für alle Testpunkten abgespeichert und bei der Anzahl der Antwortmenge steht immer "1", wenn Antwortmengen gefunden wurden (also nicht wie viele gefunden wurden).


Bei den Testreihen cases1, casesAll,  casesMix, casesMixNLA, casesCon, casesConR, graph1, racingR und smod1Point haben die Testparameter für ein Problem die Form:
Problemname | Berechnungszeit; choice points; wrong choices; Anzahl der Antwortmenge; truth assignments; Anzahl der Atome; Anzahl der Regeln; Suchraum (search space) |

Bei der Testreihe graph1 gibt es noch ein zusätzliches Verzeichnis "ergebnisseL" indem für die Testpunkte Dateien stehen, in denen ein Parameter für die durchschnittlichen Literalanzahl pro Regelkörper angegeben ist. Da es bei Smodels noch zusätzliche Konstrukte zu den normalen Regeln gibt (z.B. choice rules) ist der ermittelte Wert für die durchschnittlichen Literalanzahl pro Regelkörper, nur ein Schätzwert.
Bei der vorliegenden Version des Generators für graph1 und racingR wird hinter dem Wert für den Suchraum noch der Wert für die durchschnittlichen Literalanzahl pro Regelkörper ausgegeben (getrennt durch ein ";").


Bei casesN haben die Testparameter für ein Problem die Form:
Problemname | Berechnungszeit; choice points; Anzahl der Antwortmenge; Anzahl der Atome; Anzahl der Regeln |

Bei den Testreihen casesN ist die Anzahl der Atome und Regeln nicht für alle Testpunkten abgespeichert und bei der Anzahl der Antwortmenge steht immer "1", wenn Antwortmengen gefunden wurden (also nicht wie viele gefunden wurden).


Bei casesNN1 haben die Testparameter für ein Problem die Form:
Problemname | Berechnungszeit; choice points; choices; Anzahl der Antwortmenge |


Untertestreihen Namen
---------------------

Im Verzeichniss "tabellen" befinden sich für die Untertestreihen jeweils ein Verzeichnis beginnend mit "erg" gefolgt von der Beschreibung der Untertestreihe in der Notation der allgemeinen Abkürzungen.
"erL2A100CV" bedeutet beispielsweise: Die Diagramme beziehen sich auf die Untertestreihen mit 2 Literalen pro Körper und bei den Programmen waren 100 Atome möglich, die Regelanzahl ist variabel (oder frei) und damit auf der x-Achse aufgetragen.


Diagramme
---------

Die Namen von Verzeichnissen für Untertestreihen beginnen mit "erg" für Ergebnisse, gefolgt von einen Namenskürzel für die Bezeichnung der Untertestreiche. Dieser Namenskürzel ist in allgemeiner Notation, Parameter, die für die Testreihe frei sind, werden von einem "V" gefolgt. Das Kürzel "D3" am Anfang des Namenskürzels bedeutet, dass die Testreihe in 3 dimensionale Diagrammen dargestellt wird.

In den Untertestreihenverzeichnisse befindet sich noch zwei "*.txt" Datei. Die Datei "HS*.txt" enthält eine Tabelle mit Tabellenkopf, deren Spalten mit dem Zeichen ";" voneinander getrennt sind (die Datei kann z.B. als Excel-Import verwendet werden).
Die Datei "HSGr*.txt" enthält eine Tabelle mit den gleichen Daten ohne Kopf und mit Leerzeichen als Spaltentrennzeichen (sie kann z.B. als Gnuplot Eingabe dienen). Die Reihenfolge der Werte kann in der Methode "writeResultBl()" der Datei "evalueAllIO*.cpp" der Testreihe nachgeschlagen werden.

Es gibt zwei Arten von Diagrammen und Untertestreihen, zweidimensionale und dreidimensionale.
Der Name von Diagrammen besteht aus mehreren Komponenten.

Dreidimensionale Diagramme und Untertestreihen sind in zwei Generierungsparametern variabel, diese sind im Verzeichnissnamen mit einem dahinterstehenden "V" gekennzeichnet, die variablen Parameter besitzen sie als x-Achse und als y-Achse.

Zweidimensionale Diagramme und Untertestreihen sind in einen Generierungsparameter variabel, dieser ist im Verzeichnissnamen mit einem dahinterstehenden "V" gekennzeichnet, den variabel Parameter besitzen sie als x-Achse.

Da die Diagramme auf dieser DVD größtenteils automatisch generiert wurden, sind sie teilweise kritisch zu betrachten. Gerade die dreidimensionalen Diagramme sehen teilweise seltsam aus, weil Gnuplot Schwierigkeiten hatte die Kurvenoberfläche aus den gegebenen Daten zu berechnen, da Gnuplot wohl einige Zwischenwerte fehlten.


Abkürzungen von Namen bei Ergebnisdiagrammen
---------------------------------------------

Alle Diagrammdateien sind "*.ps" Dateien die mit Gnuplot generiert wurden. 

Bei der Beschriftung der zweidimensionalen Diagrammen kommt zuerst der Parameter für die x-Achse, dann "_", gefolgt von dem Kürzel für den Parameter der y-Achse, dann "_" gefolgt von der Beschreibung der Untertestreihe in der Notation der allgemeinen Abkürzungen.
"R_maxc_L2A100CV.ps" bedeutet beispielsweise: Auf der x-Achse sind die Regeln aufgetragen, auf der y-Achse die maximalen choice points, die Diagramme beziehen sich auf die Untertestreihen mit 2 Literalen pro Körper und bei den Programmen waren 100 Atome möglich, die Regelanzahl ist variabel und damit auf der x-Achse aufgetragen.

Die Beschriftung der dreidimensionalen Diagrammen ist analog zu der der zweidimensionalen Diagramme nur fehlt meist der erste Teil für den x-Achsen Parameter, da diese im allgemeine die Regel- und Atomanzahl ist. 
Bei der Testreihe Graph sind die x-Achse und y-Achse Parameter jeweils die Knoten- und Kantenanzahl, außer wenn die Diagrammdatei mit "AR_" beginnt, dann sind es jeweils die Regel- und Atomanzahlen.

Die x-Achse und y-Achse Kürzel sind nachfolgend zu finden.

x-Achse

allgemeine Abkürzungen
Kürzel	Bedeutung
R	Regeln
A	Atome
RdA	Regeln/Atome
E	Kanten (edges)
V	Knoten (vertices) oder dass der zugehörige Wert variabel ist
EdV	Kanten/Knoten


y-Achse

positiv bedeutet: für die erfüllbaren Programme
negativ bedeutet: für die unerfüllbaren Programme
log bedeutet: die Achse bzw. der Parameter ist logarithmisch eingeteilt 

Kürzel	Bedeutung
t	Durchschnittliche Zeit
e	Generierte Programme für den Testpunkt 
c	Durchschnittliche choice points
wc	Durchschnittliche wrong choices
dc	Durchschnittliche (choice points)-(wrong choices)
mt	Zeit Median
mc	Median der choice point 
mwc	Median der wrong choices
mint	Minimale Zeit
minc	Minimale choice points
minwc	Minimale wrong choices
maxc	Maximale choice points
maxc	Maximale choice points
at	Durchschnittliche Anzahl von Atome in den Programmen
rl	Durchschnittliche Anzahl von Regeln in den Programmen
ss	Durchschnittlicher Suchraum (search space)
sp_t	Minimale Zeit minus Maximale Zeit
sp_ss	Minimale Suchraum minus Maximale Suchraum
var_t	Zeit Varianz
var_c	Varianz der choice point
var_dc (choice points)-(wrong choices) Varianz
var_ss Suchraum Varianz
CdT	Durchschnittlicher choice point (/) Zeit Quotient ((choice point)/Zeit)
var_CdT choice point (/) Zeit Quotient ((choice point)/Zeit) Varianz
WCdT	Durchschnittliche wrong choices (/) Zeit Quotient ((wrong choices)/Zeit)
var_WCdT wrong choices (/) Zeit Quotient ((wrong choices)/Zeit) Varianz
var_wc wrong choices Varianz
epn	Erfüllbare, unerfüllbare und alle Programme 
tpn	Durchschnittliche Zeit für erfüllbare, unerfüllbare und alle Programme 
cpn	Durchschnittliche choice points für erfüllbare, unerfüllbare und alle Programme  
wcpn	Durchschnittliche wrong choices für erfüllbare, unerfüllbare und alle Programme  
sspn	Durchschnittliche search space für erfüllbare, unerfüllbare und alle Programme  
mtc	Maximal Zeit in 10 Zeitintervallen 
tc	Durchschnittliche Zeit für 10 Zeitintervalle 
ssmm	Durchschnittliche, minimale Und maximal search space 
m_ntpt Durchschnittliche (negative Zeit) - (positive Zeit) 
d_ntpt Durchschnittliche (negative Zeit)/(positive Zeit) 
d_log_ntpt Durchschnittliche log(negativ Zeit)/log(positive Zeit) 
m_ncpc Durchschnittliche (negative choice points)-(positive choice points) 
d_ncpc Durchschnittliche (negative choice points)/(positive choice points) 
d_log_ncpc Durchschnittliche log(negative choice points)/log(positive choice points) 
m_nwcpwc Durchschnittliche (negative wrong choices)-(positive wrong choices) 
d_nwcpwc Durchschnittliche (negative wrong choices)/(positive wrong choices) 
d_log_nwcpwc Durchschnittliche log(negative wrong choices)/log(positive wrong choices)
cp	Durchschnittliche choice points

Bei der Testreihe casesNN1 bedeutet c durchschnittliche choices und nicht durchschnittliche choice points.
























