Gute Praktiken zum Schreiben von Algorithmen

Hier geht es darum, wie effektiv wir einen Algorithmus zur Hand ausdrücken können. Ich brauche das für meine Grundausbildung.

Ich verstehe, dass es keine Standardmethode zum Schreiben eines Pseudocodes gibt. Unterschiedliche Autoren folgen unterschiedlichen Konventionen.

Es wäre hilfreich, wenn die Leute hier darauf hinweisen würden, wie sie vorgehen und das Beste denken.

Gibt es ein Buch, das sich ausführlich damit beschäftigt?

Das Schreiben von Pseudocode ist wie das Schreiben von Code: Es ist nicht besonders wichtig, welchem ​​Standard Sie folgen, solange Sie (und die Leute, mit denen Sie schreiben) tatsächlich einem Standard folgen .

Um es festzuhalten, hier ist der eigenwillige Standard, den ich in meinen Vorlesungsskripten, Forschungsarbeiten und dem nächsten Buch verwende.

• Verwenden Sie die standardmäßige imperative Syntax für den Kontrollfluss und den Speicherzugriff - if, while, for, return, array [index], function (Argumente). Formulieren Sie "else if".

  • Verwenden Sie statt oder aber$field(record)$record.fieldrecord->field

• Verwenden Sie die mathematische Standardnotation für Mathematik: Schreiben Sie anstelle von , anstelle von , anstelle von , anstelle von , anstelle von , anstelle von , anstelle von , etc.$xy$x*ys ≤ t ¬ p $a\bmod b$a%b$s\le t$s <= t$\lnot p$!p π$\sqrt{x}$sqrt(x)$\pi$PI$\infty$MAX_INT

  • Verwenden Sie jedoch für die Zuweisung, um das Problem zu vermeiden .$x\gets y$==

  • Vermeiden Sie jedoch die Notation (und den Pseudocode!), Wenn Englisch klarer ist.

    • Vermeiden Sie symmetrisch Englisch, wenn die Notation klarer ist!

• Syntaktischen Zucker minimieren - Blockstruktur durch konsistente Einrückung angeben (à la Python). Lassen Sie zuckerhaltige Schlüsselwörter wie "Anfang / Ende" oder "Do / Od" oder "Fi" weg. Zeilennummern weglassen. Sie nicht betonen Schlüsselwörter wie „für“ oder „während“ oder „wenn“ , indem sie in einer anderen Einstellung typefaceoder Stil . Je. Tu es einfach nicht.

  • Sie können jedoch Algorithmusnamen und Konstanten in \ textsc {Small Caps}, Variablennamen in Kursivschrift und Literalzeichenfolgen in Sans Serif eingeben .

  • Fügen Sie jedoch \\[0.5ex]zwischen aussagekräftigen Codestücken eine kleine Menge vertikalen "Atempausen" ( ) ein.

• Geben Sie keine unwichtigen Details an. Wenn es egal ist, in welcher Reihenfolge Sie die Scheitelpunkte besuchen, sagen Sie einfach "für alle Scheitelpunkte".

Hier ist zum Beispiel eine rekursive Formulierung des Minimum-Spanning-Tree-Algorithmus von Borůvka . Ich habe zuvor als den Graphen definiert, der aus indem alle Kanten in der Menge , und Flatten als eine Unterroutine, die Schleifen und parallele Kanten entfernt.G $G / L$$G$$L$

Ich benutze meine eigene algorithmLaTeX-Umgebung , um Pseudocode zu setzen. (Es ist nur eine tabbingUmgebung innerhalb einer \fbox.) Hier ist mein Quellcode für Borůvkas Algorithmus:

\begin{algorithm}
	\textul{$\textsc{Borůvka}(G)$:}\+
\\	if $G$ has no edges\+
\\		return $\varnothing$\-
\\[0.5ex]
	$L \gets \varnothing$
\\	for each vertex $v$ of $G$\+
\\		add the lightest edge incident to $v$ to $L$\-
\\[0.5ex]
	return $L \cup \textsc{Borůvka}(\textsc{Flatten}(G / L))$
\end{algorithm}

Ich neige dazu, etwas zu verwenden, das der Python-Syntax ähnelt. Python ist dem Pseudocode bereits nahe genug, so dass mein Pseudocode in einigen Fällen in einen tatsächlichen Arbeitscode umgewandelt werden kann.

Wenn Sie einen bestimmten Code haben möchten (dh wenig bis gar keine Mathematik, in der Nähe der realen Programmierung), sollten Sie einen Code in Betracht ziehen, der tatsächlich kompiliert wird. Dies hat mehrere Vorteile:

• Sie erhalten Syntax-Hervorhebungen überall.
• Der Compiler überprüft die Syntax für Sie und erzwingt die Konsistenz.
• Sie können Ihre Implementierungen einem Komponententest unterziehen, um die Codequalität zu verbessern.
• Sie können den Algorithmus ausführen und gemessene Laufzeiten mit Analysen vergleichen (was erweiterte Analysetechniken motiviert).

Ein Professor an meiner Universität macht das in seinem Algorithmenkurs. Seine bevorzugte Sprache ist Modula. Ich denke jedoch nicht, dass es auf die Wahl der Sprache ankommt. Halten Sie sich einfach an eines (pro Paradigma), das am besten zu Ihrem Abstraktionsgrad passt.