Bonnes pratiques pour l'écriture d'algorithmes

Il s'agit de l'efficacité avec laquelle nous pouvons exprimer un algorithme à portée de main. J'en ai besoin pour mon enseignement de premier cycle.

Je comprends qu'il n'y a pas de moyen standard d'écrire un pseudo-code. Différents auteurs suivent différentes conventions.

Il serait utile que les gens ici soulignent la façon dont ils suivent et pensent le meilleur.

Y a-t-il un livre qui traite de cela en détail?

Écrire un pseudocode, c'est comme écrire du code: Peu importe la norme que vous suivez, tant que vous (et les personnes avec qui vous écrivez) suivez réellement une norme.

Mais pour mémoire, voici la norme idiosyncrasique que j'utilise dans mes notes de cours, mes articles de recherche et mon prochain livre.

• Utilisez la syntaxe impérative standard pour le flux de contrôle et l'accès à la mémoire - if, while, for, return, array [index], function (arguments). Épelez «sinon si».

  • Mais utilisez au lieu de ou$field(record)$record.fieldrecord->field

• Utilisez la notation mathématique standard pour les mathématiques - Écrivez au lieu de , a mod b au lieu de , s ≤ t au lieu de , ¬ p au lieu de , $xy$x*y$a\bmod b$a%b$s\le t$s <= t$\lnot p$!p au lieu de,πau lieu de,∞au lieu de, etc.$\sqrt{x}$sqrt(x)$\pi$PI$\infty$MAX_INT

  • Mais utilisez pour l'affectation, pour éviter le problème.$x\gets y$==

  • Mais évitez complètement la notation (et le pseudocode!) Si l'anglais est plus clair.

    • Symétriquement, évitez l'anglais si la notation est plus claire!

• Minimiser le sucre syntaxique - Indiquer la structure des blocs par indentation cohérente (à la Python). Omettez les mots clés sucrés comme "début / fin" ou "do / od" ou "fi". Omettez les numéros de ligne. Ne pas mettre l' accent sur des mots clés comme « pour » ou « tout » ou « si » en les plaçant dans un autre typefaceou de style . Déjà. Mais ne le fais pas.

  • Mais composez les noms et les constantes de l'algorithme dans \ textesc {petites majuscules}, les noms des variables en italique et les chaînes littérales en sans serif.

  • Mais ajoutez une petite quantité d'espace de "respiration" vertical ( \\[0.5ex]) entre des morceaux de code significatifs.

• Ne spécifiez pas de détails sans importance. Si l'ordre dans lequel vous visitez les sommets n'a pas d'importance, dites simplement "pour tous les sommets".

Par exemple, voici une formulation récursive de l' algorithme d'arbre couvrant minimal de Borůvka . J'ai précédemment défini comme le graphique obtenu à partir de G en contractant toutes les arêtes de l'ensemble L , et Flatten comme une sous-routine qui supprime les boucles et les arêtes parallèles.$G / L$$G$$L$

J'utilise mon propre algorithmenvironnement LaTeX léger pour composer le pseudocode. (C'est juste un tabbingenvironnement à l'intérieur d'un \fbox.) Voici mon code source pour l'algorithme de Borůvka:

\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}

J'ai tendance à utiliser quelque chose qui ressemble à la syntaxe Python. Python est déjà assez proche du pseudocode que, dans certains cas, mon pseudocode peut devenir un code de travail réel.

Si vous voulez avoir un code défini (c'est-à-dire peu ou pas de mathématiques, proche de la vraie programmation), vous voudrez peut-être envisager d'avoir du code qui compile réellement. Cela présente plusieurs avantages:

• Vous obtenez la coloration syntaxique partout.
• Le compilateur vérifie la syntaxe pour vous et applique la cohérence.
• Vous pouvez tester vos implémentations à l'unité pour améliorer la qualité du code.
• Vous pouvez exécuter l'algorithme et comparer les durées d'exécution mesurées aux analyses (motivant ainsi des techniques d'analyse avancées).

Un professeur de mon université le fait dans son cours d'algorithmes. Sa langue de prédilection est Modula. Mais je ne pense pas que le choix particulier de la langue compte. Restez-en à un (par paradigme) qui correspond le mieux à votre niveau d'abstraction.