(J. Waldmann, Version: Ansatz 8. Juni 2020)
… dann gehören zu dessen Beschreibung:
Im Einzelnen:
Es muß deutlich werden, ob Sie den Algorithmus hier in der Arbeit selbst erfunden haben oder ob Sie eine Erfindung aus der Literatur zitieren.
Wenn Zitat, dann richtig: von wem erfunden, wann und wo publiziert? In der Publikation stehen dann bereits die Antworten auf die o.g. Fragen, die Sie deswegen kurz halten können. In der Verteidigung müssen Sie die Antworten aber trotzdem kennen.
Wenn die Antworten nicht in der Publikation stehen, dann ist die Quelle unwissenschaftlich und Sie sollten eine bessere suchen.
Unter dem Namen können Sie später (und früher - in der Einleitung) auf den Algorithmus Bezug nehmen. Wenn der Name fehlt, entstehen Formulierungen wie “unser Algorithmus”, “unser anderer Algorithmus”, “der Algorithmus aus Kapitel 3 mit der Variante von Kapitel 7”, bis dann keiner mehr weiß, was gemeint ist.
Zur Beschreibung von Ein- und Ausgabe gehört ganz wesentlich der Typ. Geben Sie diesen mittels Mengen, Relationen, Funktionen an. Beispiel: “Eingabe x und Ausgabe y ist jeweils eine Folge von ganzen Zahlen.”
Die gewünsche Beziehung zwischen Ein- und Ausgabe ist im allgemeinen eine (prädikaten)logische Formel. Für deren Notation sollen geeignete Begriffe vorher definiert werden, dann wird die Formel auch nicht zu lang oder kann durch eine exakte natürlichsprachliche Formulierung ersetzt werden. Beispiel: “Die Ausgabe ist die aufsteigend geordnete Permutation der Eingabe.” Das klappt, wenn “aufsteigend geordnet” und “Permutation” vorher erklärt (oder zitiert) wurden. Beachten Sie hier: “die .. Permutation” erfordert dann noch einen Beweis dafür, daß es immer genau eine solche gibt.
Gehen Sie auf konkrete Repräsentation der abstrakten Datenstruktren (z.B. Folge als balanciertert Baum, als einfach verkettete Liste von Byte-Arrays) erst dann ein, wenn es wichtig ist - normalerweise nur für Komplexitäts-Aussagen und da auch nicht immer. Der Plan der Implementierung sowie der Korrektheitsbeweis sollen ohne diese Details verständlich sein.
Der Plan sollte mathematik-nah notiert werden, weil das am besten zu Spezifikation und Beweis paßt. Falls Sie Pseudo-Code verwenden, dann eher funktional als imperativ.
Falls Sie noch imperativ denken, dann schreiben Sie “single-assignment-code”: jeder Bezeichner wird nur einmal benutzt, und zwar initialisiert. Geben Sie bei Deklaration jedes Bezeichners seinen Typ an sowie seinen Zweck, falls der aus dem Typ nicht erkennbar ist - dann ist aber der Typ falsch gewählt. Beispiel: schreiben Sie nicht s := 0; for i in ... do s+= x[i], sondern schreiben Sie s = sum(x), am besten in LaTeX. Falls es in Ihrer Programmiersprache oder -Standardbibliothek diese sum-Operation nicht gibt, ist die Sprache schlecht gewählt oder Sie haben die richtige Bibliothek nicht gefunden.
Unterscheiden Sie zwischen der Komplexität eines konkeren Algorithmus (dieser Abschnitt) und der Komplexität der Aufgabenstellung (nächster Abschnitt) In der Komplexitäts-Aussage soll das Kostenmodell deutlich werden. Bei geeigneter Abstraktion kann man die Diskussion von Implementierungsdetails auch hier noch vermeiden. Beispiel: “Mergesort benutzt Theta(n log n) Elementvergleiche” - wenn man nur diese zählt, ist es egal, wie die Folge implementiert ist. Separat ist zu diskutieren, ob diese Abstraktion vernünftig ist. Das kommt auf die Aufgabenstellung und den Anwendungsfall an. Oft kann man sich dadurch retten, daß man genau die Kostenmodelle aus der Literatur verwendet und diese nicht nochmals begründet - sondern zitiert.
Eine untere Komplexitätsschranke bedeutet: die spezifizierte Aufgabenstellung kann durch keine Algorithmus (asymptotisch) schneller gelöst werden. Bsp: für jedes vergleichsbasierte Sortieren eine Folgen von n Elementen gibt es eine Eingabe, bei der log_2(n Fakultät) Vergleiche ausgeführt werden.
Eine obere Komplexitätsschranke liefert jeder andere Algorithmus, der die gleiche Aufgabenstellung löst. Wenn der benutzte von Ihnen benutzte oder erfundene Algorithmus langsamer ist, dann muß das noch nicht falsch sein, aber gut begründet werden. Beispiel: wir benutzen Bubblesort (mit quadratischer Laufzeit), weil garantiert ist, daß alle Eingabefolgen die Länge 3 haben.
Falls es für Ihre Arbeit wesentlich ist, dann beschreiben Sie die Implementierung. Geben Sie dabei zunächst die konkreten Realisierungen der in der Spezifikation verwendeten abstrakten Datentypen an. Dann können Quelltextausschnitte folgen. Die Gutachter der Arbeit wollen aber keine Code-Review durchführen. Jedoch wollen sie Ihr Vorgehen nachvollziehen - anhand Ihre Beschreibung der wesentlichen Schritte.
Sie werden nicht alles selbst implementieren, sondern Bibliotheken von Dritten verwenden. Diese sind zu zitieren, siehe oben. Falls Sie doch alles selbst schreiben, führt das eher zu Verwunderung und Abwertung - die Gutachter nehmen dann an, daß Sie die Fachliteratur nicht kennen. Wenn Sie das Rad neu erfinden, müssen Sie das begründen.
Die Implementierungen der in Ihrere Arbeit beschriebenen Algorithmen sind Bausteine zur Aufgabenlösung. Zeigen Sie schließlich (und auch bereits in der Einleitung), wie man Ihre Software tatsächlich benutzt. Sehr zweckmäßig ist es dazu, wenn Sie eine Kommandozeilenschnittstelle einbauen, mit der Lösungsverfahren für die Gesamt-Aufgabe sowie für Teil-Aufgaben explizit aufgerufen und dabei Parameter variiert werden können.
Das ist nicht nur schließlich für den Anwender schön, sondern auch während der Entwicklung für Sie zum automatisieren Testen. Die Testfälle ergeben sich aus den jeweiligen Spezifikationen, siehe oben.
Ich empfehle immer, die Implementierung so zu schreiben, daß Sie damit (ohne manuelle Bedienvorgänge wie Quelltextänderungen oder Mausclicks, sondern allein durch Kommandozeilenoptionen) genau die Ausgabe-Dateien erzeugen können (Texte, Tabellen, Grafiken), die Sie in Ihre Arbeit einfügen möchten.